CODEWITHSUNDEEP
algorithmgraph-algorithmdirected-graph
vindyz
vindyz

Reputation: 1101

counting number of cycles in a digraph

I came across this interesting problem of counting number of cycles in a digraph.

For detecting a cycle in graph we can use DFS, but in order to detect number of cycles, DFS wont be of much use, as some edges will be common in some cycles.

I am trying to figure out if spanning tree might be of any help here.

Any thoughts?

Upvotes: 2

Views: 947

Answers (1)

pvoosten
pvoosten

Reputation: 3287

Here is an algorithm to derive a structure to help solve the cycle count problem:

  • For each node, derive the indegree (the number of incoming edges) and the outdegree.
  • Remove all nodes with indegree zero. Those are not part of a cycle. From their successors, subtract 1 from the indegree. From their predecessors, subtract 1 from the outdegree.
  • Remove all nodes with outdegree zero, since they can't be part of a cycle either. Like before, subtract indegrees and outdegrees from neighboring nodes accordingly.
  • Repeat the 2 previous steps until there are no more nodes with indegree or outdegree zero. Now all remaining nodes are part of a cycle.
  • All nodes with indegree=1 or outdegree=1 can be combined with their predecessor or successor respectively. The nodes can be combined in a list, because they will be on all the exact same cycles.

The remaining graph has only nodes with both indegree and outdegree greater than or equal to 2. It contains references to nodes of the original graph.

  • Now find the strongly connected components in the remaining graph.
    • Singular nodes are found for cycles that can only be traversed in a single possible way, i.e. a single cycle.
    • Subgraphs with multiple (at least 3) combined nodes signify more complex cycle structures. The cycles can be counted according to the appropriate definition of the cycle count. Counting can be done with backtracking.

Upvotes: 4

Related Questions