Here is my two versions of code to check if there is a circle for a directed graph. Any advice on performance improvements in terms of algorithm time complexity, code bugs or code style are highly appreciated.
More specifically, I have two questions:
- My v2 method (refer to
check_circle_v2) is an optimization which traverse only from in-degree zero nodes, and after DFS all in-degree zero nodes, I will check if there are still remaining nodes unvisited -- if yes, there are circle. I learned this method from some forum, but I am not sure if this algorithm truly has no bugs or truly have performance improvements comparing to straightforward dfs implementation in the code (refer to
- If there are no in-degree zero nodes, can I make a conclusion that the graph has circle? Is that always true?
from collections import defaultdict class Graph: def __init__(self): self.out_neighbour = defaultdict(list) # key has edge to value self.in_neighbour = defaultdict(list) # value has edge to key self.visited = set() self.nodes = set() self.being_visited = set() def add_edge(self, from_node, to_node): self.out_neighbour[from_node].append(to_node) self.in_neighbour[to_node].append(from_node) self.nodes.add(from_node) self.nodes.add(to_node) def check_circle_v2(self): for root in self.nodes: if root not in self.in_neighbour: if self.dfs(root): return True if len(self.visited) < len(self.nodes): return True return False def check_circle(self): for root in self.nodes: if root not in self.visited: if self.dfs(root): return True return False def dfs(self, node): self.being_visited.add(node) for n in self.out_neighbour[node]: if n in self.being_visited: return True # has circle elif n not in self.visited: if self.dfs(n): return True self.visited.add(node) self.being_visited.remove(node) return False if __name__ == "__main__": g = Graph() edges = [(1,2),(2,3),(3,1),(3,4)] # true edges = [(1, 2), (2, 3), (1, 3), (3, 4)] # false edges = [(4,1),(1,2),(3,2),(3,1)] # false for e in edges: g.add_edge(e,e) print g.check_circle() print g.check_circle_v2()