Circle check algorithm optimization for directed graph

Question

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:

1. 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 check_circle)?
2. 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[0],e[1])
    print g.check_circle()
    print g.check_circle_v2()

Answer 1

Avoid data duplication

You have:

• a dictionary self.out_neighbour
• a dictionary self.in_neighbour
• a set self.nodes

all of which store essentially the same data in slightly different formats. You can avoid duplicating the input data by doing the following:

• Combine out_neighbour and in_neighbour into a doubly-linked list. This would have the form:

  {
    "3":  {
              "in":  [2],
              "out": [1, 4]
          },
    "4":  {
              "in":  [3]
              "out": []
          },
     ...etc
  }        
  

All nodes in the input would appear as keys in a single dictionary (eg. nodes_dict). This also means you can:

• Eliminate the self.nodes list.

self.nodes is really only referred to once in your check_circle (or check_circle_v2) method, where you have:

        for root in self.nodes:

An equivalent list can be generated from the dictionary using:

        for root in self.nodes_dict.keys()     

Time complexity:

Depth-first search for cycle detection in directed graphs is supposed to scale according to \$\mathcal{O}(n)\$, where n is the number of vertices. Yours scales with \$\mathcal{O}(n^2)\$, because the list self.being.visited is itself read through by if n in self.being_visited every time you visit a node.

If speed is an issue, it may be better to use a dict for self.being.visited. The code to check it is exactly the same, but works in \$\mathcal{O}(1)\$.

Your question 1:

The efficiency improvment gained by using check_circle_v2 can be no more than a constant factor of the original implementation. This is because depth-first search is still being called, which has a runtime of \$\mathcal{O}(n)\$ in this case.

Also, what this constant factor is, exactly, depends on the ratio of no-in-degree nodes to nodes having ins.

The best case is a graph of size \$n\$, with \$n - 1\$ nodes each having an edge pointing to them (the only visual example I can think of is like a chaos flag from Warhammer40K).

The worst case is the reverse of the chaos flag graph, with all arrows pointing inward. Your check_circle_v2 will call dfs on every node except the center node. So, in terms of time complexity and worst case performance, check_circle_v2 is no better than the original.

Your question 2:

The statement is true. Requiring the graph to have no in-degree nodes means that:

• No. of nodes with (in > 0) \$=\$ No. of nodes

For the case of a non-cycle, one of its nodes lacks an in-pointing edge. So, by definition, for a non-cycle:

• No. of nodes with (in > 0) \$=\$ No. of nodes \$- 1\$

The only way to have a non-cycle in the graph given the first requirement is to create an in-degree node for it without adding a new node. And the only way to do that is to connect the non-cycle to the existing graph, with one or more edges pointing to it from the graph. Then, the problem must be restated in terms of the whole graph, which cannot be a non-cycle while fulfilling the first condition.

(Terminology note: It's cycle, not circle. Also, vertice is commonly used instead of node.)