|
| 1 | +import queue |
| 2 | + |
| 3 | + |
| 4 | +class DirectedGraph(object): |
| 5 | + """ |
| 6 | + Directed Graph, with graph represented as an adjacency list |
| 7 | + """ |
| 8 | + |
| 9 | + def __init__(self): |
| 10 | + self.adjacency_list = {} |
| 11 | + |
| 12 | + def add_edge(self, source, destination): |
| 13 | + """ |
| 14 | + Adds an edge defined by vertices source and destination |
| 15 | + :param source: |
| 16 | + :param destination: |
| 17 | + :return: |
| 18 | + """ |
| 19 | + if source not in self.adjacency_list: |
| 20 | + self.adjacency_list[source] = set() |
| 21 | + self.adjacency_list[source].add(destination) |
| 22 | + |
| 23 | + def get_vertex(self): |
| 24 | + """ |
| 25 | + Generator for returning the next vertex from the adjacency list |
| 26 | + :return: |
| 27 | + """ |
| 28 | + for v in self.adjacency_list: |
| 29 | + yield v |
| 30 | + |
| 31 | + def get_edge(self, vertex): |
| 32 | + """ |
| 33 | + Generator for returning the next vertex adjacent to the given vertex |
| 34 | + :param vertex: |
| 35 | + :return: |
| 36 | + """ |
| 37 | + if vertex in self.adjacency_list: |
| 38 | + for u in self.adjacency_list[vertex]: |
| 39 | + yield u |
| 40 | + |
| 41 | + def dfs(self): |
| 42 | + """ |
| 43 | + Computes the initial source vertices for each connected component |
| 44 | + and the parents for each vertex as determined through depth-first-search |
| 45 | + :return: initial source vertices for each connected component, parents for each vertex |
| 46 | + :rtype: set, dict |
| 47 | + """ |
| 48 | + parents = {} |
| 49 | + components = set() |
| 50 | + to_visit = [] |
| 51 | + |
| 52 | + for vertex in self.get_vertex(): |
| 53 | + if vertex not in parents: |
| 54 | + components.add(vertex) |
| 55 | + else: |
| 56 | + continue |
| 57 | + |
| 58 | + to_visit.append(vertex) |
| 59 | + |
| 60 | + while to_visit: |
| 61 | + v = to_visit.pop() |
| 62 | + |
| 63 | + for neighbor in self.get_edge(v): |
| 64 | + if neighbor not in parents: |
| 65 | + parents[neighbor] = v |
| 66 | + to_visit.append(neighbor) |
| 67 | + |
| 68 | + return components, parents |
| 69 | + |
| 70 | + def bfs(self): |
| 71 | + """ |
| 72 | + Computes the the parents for each vertex as determined through breadth-first search |
| 73 | + :return: parents for each vertex |
| 74 | + :rtype: dict |
| 75 | + """ |
| 76 | + parents = {} |
| 77 | + to_visit = queue.Queue() |
| 78 | + |
| 79 | + for vertex in self.get_vertex(): |
| 80 | + to_visit.put(vertex) |
| 81 | + |
| 82 | + while not to_visit.empty(): |
| 83 | + v = to_visit.get() |
| 84 | + |
| 85 | + for neighbor in self.get_edge(v): |
| 86 | + if neighbor not in parents: |
| 87 | + parents[neighbor] = v |
| 88 | + to_visit.put(neighbor) |
| 89 | + |
| 90 | + return parents |
| 91 | + |
| 92 | + def contains_cycle(self): |
| 93 | + """ |
| 94 | + Determines if one of the connected components contains a cycle |
| 95 | + :return: true if one of the connected components contains a cycle |
| 96 | + :rtype: bool |
| 97 | + """ |
| 98 | + contains_cycle = False |
| 99 | + STATUS_STARTED = 1 |
| 100 | + STATUS_FINISHED = 2 |
| 101 | + |
| 102 | + for vertex in self.get_vertex(): |
| 103 | + statuses = {} |
| 104 | + to_visit = [vertex] |
| 105 | + |
| 106 | + while to_visit and not contains_cycle: |
| 107 | + v = to_visit.pop() |
| 108 | + |
| 109 | + if v in statuses: |
| 110 | + if statuses[v] == STATUS_STARTED: |
| 111 | + statuses[v] = STATUS_FINISHED |
| 112 | + else: |
| 113 | + statuses[v] = STATUS_STARTED |
| 114 | + to_visit.append(v) # add to stack to signal vertex has finished DFS |
| 115 | + |
| 116 | + for u in self.get_edge(v): |
| 117 | + if u in statuses: |
| 118 | + if statuses[u] == STATUS_STARTED: |
| 119 | + contains_cycle = True |
| 120 | + break |
| 121 | + else: |
| 122 | + to_visit.append(u) |
| 123 | + |
| 124 | + if contains_cycle: |
| 125 | + break |
| 126 | + |
| 127 | + return contains_cycle |
| 128 | + |
| 129 | + |
| 130 | +def main(): |
| 131 | + dg = DirectedGraph() |
| 132 | + dg.add_edge(0, 1) |
| 133 | + dg.add_edge(0, 5) |
| 134 | + dg.add_edge(1, 2) |
| 135 | + dg.add_edge(2, 4) |
| 136 | + dg.add_edge(2, 6) |
| 137 | + dg.add_edge(3, 2) |
| 138 | + dg.add_edge(5, 8) |
| 139 | + dg.add_edge(6, 5) |
| 140 | + dg.add_edge(7, 5) |
| 141 | + dg.add_edge(7, 5) |
| 142 | + # dg.add_edge(8, 0) # uncomment to create a cycle |
| 143 | + |
| 144 | + components, dfs_parents = dg.dfs() |
| 145 | + |
| 146 | + print("Components: ", components) |
| 147 | + print("Parents (dfs): ", dfs_parents) |
| 148 | + |
| 149 | + bfs_parents = dg.bfs() |
| 150 | + print("Parents (bfs): ", bfs_parents) |
| 151 | + |
| 152 | + print("Contains a cycle: ", dg.contains_cycle()) |
| 153 | + |
| 154 | + |
| 155 | +if __name__ == "__main__": |
| 156 | + main() |
0 commit comments