Circle check algorithm optimization for directed graph
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.)