2
\$\begingroup\$

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()
\$\endgroup\$
2
\$\begingroup\$

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.)

\$\endgroup\$
  • \$\begingroup\$ Thanks Ryan, love your comments, and vote up. One confusion, for your comments, For the case of a non-cycle, one of its nodes lacks an in-pointing edge., do you have a simple prove or clarification why non cycle requires one node lacks an in-pointing edge? If you found it by some external document/wiki reference, could you point to me? :) \$\endgroup\$ – Lin Ma Feb 6 '17 at 1:18
  • \$\begingroup\$ When I wrote the second statement, I was thinking of the simplest non-cycle, a straight line: A->B, B->C, C->D etc. The beginning node has no "in". So the number of nodes with "in > 0" (B,C and D) is 1 less than the total number of nodes (A,B,C,D). In fact, all graphs without cycles will have at least one vertex without an "in" somewhere. This comes from (is a corollary of) a rule from graph theory: that every acyclic graph has a topological ordering. (But not the reverse: All graphs with points without "ins" are not necessarily acyclic.) \$\endgroup\$ – Ryan Mills Feb 6 '17 at 5:31
  • \$\begingroup\$ In summary: [graph is acyclic] means that [graph has topological ordering] which means that [graph has at least one node with no "in"]. And, going the other way: [graph has no zero-in-degree nodes] means that [graph has no topological ordering] which means that [graph is cyclic] \$\endgroup\$ – Ryan Mills Feb 6 '17 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.