Computes the initial source vertices for each connected component and the parents for each vertex as determined through depth-first-search :return: initial source vertices for each connected component, parents for each vertex :rtype: set, dict
(self)
| 57 | yield u |
| 58 | |
| 59 | def dfs(self): |
| 60 | """ |
| 61 | Computes the initial source vertices for each connected component |
| 62 | and the parents for each vertex as determined through depth-first-search |
| 63 | :return: initial source vertices for each connected component, parents for each vertex |
| 64 | :rtype: set, dict |
| 65 | """ |
| 66 | parents = {} |
| 67 | components = set() |
| 68 | to_visit = [] |
| 69 | |
| 70 | for vertex in self.get_vertex(): |
| 71 | if vertex not in parents: |
| 72 | components.add(vertex) |
| 73 | else: |
| 74 | continue |
| 75 | |
| 76 | to_visit.append(vertex) |
| 77 | |
| 78 | while to_visit: |
| 79 | v = to_visit.pop() |
| 80 | |
| 81 | for neighbor in self.get_neighbor(v): |
| 82 | if neighbor not in parents: |
| 83 | parents[neighbor] = v |
| 84 | to_visit.append(neighbor) |
| 85 | |
| 86 | return components, parents |
| 87 | |
| 88 | def bfs(self): |
| 89 | """ |