Iterate over the nodes reachable from the given start node, excluding the start node itself. Each node in the graph is yielded at most once.
(self, node)
| 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() |
| 75 | assert x in seen |
| 76 | yield x |
| 77 | |
| 78 | for y in self.__nodes[x].adj: |
| 79 | if y not in seen: |
| 80 | seen.add(y) |
| 81 | visit_me.append(y) |
| 82 | |
| 83 | class DiGraphNode: |
| 84 | def __init__(self): |
no test coverage detected