A directed graph. The implementation and API mimic that of networkx.DiGraph in networkx-1.11. networkx implements graphs as nested dicts; it uses dicts all the way down, no lists. Some major differences between this implementation and that of networkx-1.11 are: * This
| 15 | from parse_dependency import dependencyNames |
| 16 | |
| 17 | class DiGraph: |
| 18 | """A directed graph. |
| 19 | |
| 20 | The implementation and API mimic that of networkx.DiGraph in networkx-1.11. |
| 21 | networkx implements graphs as nested dicts; it uses dicts all the way |
| 22 | down, no lists. |
| 23 | |
| 24 | Some major differences between this implementation and that of |
| 25 | networkx-1.11 are: |
| 26 | |
| 27 | * This omits edge and node attribute data, because we never use them |
| 28 | yet they add additional code complexity. |
| 29 | |
| 30 | * This returns iterator objects when possible instead of collection |
| 31 | objects, because it simplifies the implementation and should provide |
| 32 | better performance. |
| 33 | """ |
| 34 | |
| 35 | def __init__(self): |
| 36 | self.__nodes = {} |
| 37 | |
| 38 | def add_node(self, node): |
| 39 | if node not in self.__nodes: |
| 40 | self.__nodes[node] = DiGraphNode() |
| 41 | |
| 42 | def add_edge(self, src, dest): |
| 43 | self.add_node(src) |
| 44 | self.add_node(dest) |
| 45 | self.__nodes[src].adj.add(dest) |
| 46 | |
| 47 | def nodes(self): |
| 48 | """Iterate over the nodes in the graph.""" |
| 49 | return self.__nodes.keys() |
| 50 | |
| 51 | def descendants(self, node): |
| 52 | """ |
| 53 | Iterate over the nodes reachable from the given start node, excluding |
| 54 | the start node itself. Each node in the graph is yielded at most once. |
| 55 | """ |
| 56 | |
| 57 | # Implementation detail: Do a breadth-first traversal because it is |
| 58 | # easier than depth-first. |
| 59 | |
| 60 | # All nodes seen during traversal. |
| 61 | seen = set() |
| 62 | |
| 63 | # The stack of nodes that need visiting. |
| 64 | visit_me = [] |
| 65 | |
| 66 | # Bootstrap the traversal. |
| 67 | seen.add(node) |
| 68 | for x in self.__nodes[node].adj: |
| 69 | if x not in seen: |
| 70 | seen.add(x) |
| 71 | visit_me.append(x) |
| 72 | |
| 73 | while visit_me: |
| 74 | x = visit_me.pop() |