Computes the the parents for each vertex as determined through breadth-first search :return: parents for each vertex :rtype: dict
(self)
| 86 | return components, parents |
| 87 | |
| 88 | def bfs(self): |
| 89 | """ |
| 90 | Computes the the parents for each vertex as determined through breadth-first search |
| 91 | :return: parents for each vertex |
| 92 | :rtype: dict |
| 93 | """ |
| 94 | parents = {} |
| 95 | to_visit = queue.Queue() |
| 96 | |
| 97 | for vertex in self.get_vertex(): |
| 98 | to_visit.put(vertex) |
| 99 | |
| 100 | while not to_visit.empty(): |
| 101 | v = to_visit.get() |
| 102 | |
| 103 | for neighbor in self.get_neighbor(v): |
| 104 | if neighbor not in parents: |
| 105 | parents[neighbor] = v |
| 106 | to_visit.put(neighbor) |
| 107 | |
| 108 | return parents |
| 109 | |
| 110 | def contains_cycle(self): |
| 111 | """ |