This class represents a graph skeleton, meaning a vertex set and a directed edge set. It contains the attributes *V* and *E*, and the methods *load*, *getparents*, *getchildren*, and *toporder*.
| 31 | import sys |
| 32 | |
| 33 | class GraphSkeleton(Dictionary): |
| 34 | ''' |
| 35 | This class represents a graph skeleton, meaning a vertex set and a directed edge set. It contains the attributes *V* and *E*, and the methods *load*, *getparents*, *getchildren*, and *toporder*. |
| 36 | |
| 37 | ''' |
| 38 | |
| 39 | def __init__(self): |
| 40 | self.V = None |
| 41 | '''A list of names of vertices.''' |
| 42 | self.E = None |
| 43 | '''A list of [origin, destination] pairs of vertices that constitute edges.''' |
| 44 | self.alldata = None |
| 45 | '''(Inherited from dictionary) A variable that stores a key-indexable dictionary once it is loaded from a file.''' |
| 46 | |
| 47 | def load(self, path): |
| 48 | ''' |
| 49 | Load the graph skeleton from a text file located at *path*. |
| 50 | |
| 51 | Text file must be a plaintext .txt file with a JSON-style representation of a dict. Dict must contain the top-level keys "V" and "E" with the following formats:: |
| 52 | |
| 53 | { |
| 54 | 'V': ['<vertex_name_1>', ... , '<vertex_name_n'], |
| 55 | 'E': [['vertex_of_origin', 'vertex_of_destination'], ... ] |
| 56 | } |
| 57 | |
| 58 | Arguments: |
| 59 | 1. *path* -- The path to the file containing input data (e.g., "mydictionary.txt"). |
| 60 | |
| 61 | Attributes modified: |
| 62 | 1. *V* -- The set of vertices. |
| 63 | 2. *E* -- The set of edges. |
| 64 | |
| 65 | ''' |
| 66 | self.dictload(path) |
| 67 | self.V = self.alldata["V"] |
| 68 | self.E = self.alldata["E"] |
| 69 | |
| 70 | # free unused memory |
| 71 | del self.alldata |
| 72 | |
| 73 | def getparents(self, vertex): |
| 74 | ''' |
| 75 | Return the parents of *vertex* in the graph skeleton. |
| 76 | |
| 77 | Arguments: |
| 78 | 1. *vertex* -- The name of the vertex whose parents the function finds. |
| 79 | |
| 80 | Returns: |
| 81 | A list containing the names of the parents of the vertex. |
| 82 | |
| 83 | ''' |
| 84 | assert (vertex in self.V), "The graph skeleton does not contain this vertex." |
| 85 | |
| 86 | parents = [] |
| 87 | for pair in self.E: |
| 88 | if (pair[1] == vertex): |
| 89 | parents.append(pair[0]) |
| 90 | return parents |