2

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?

Wolf
  • 9,679
  • 7
  • 62
  • 108
vindyz
  • 1,079
  • 2
  • 11
  • 23
  • How do you define the number of cycles? Every possible route from a node to itself? Or do you consider shortcuts differently? And by the way, with "diagraph", do you mean directed graph? – pvoosten Nov 13 '13 at 19:09
  • 1
    If you define "diagraph" as "directed acyclic graph", which seems to be a common "abbreviation", then there are by definition 0 cycles. If that's just a misspelling of "digraph" (meaning "directed graph"), as suggested by @pvoosten then that's a different matter... – twalberg Nov 13 '13 at 19:16
  • I meant digraph only. by cycle I mean, simple cycle , which may or may not share edges. for the sake of simplicity we can assume that they are not sharing any edges, just vertices. – vindyz Nov 13 '13 at 19:36
  • possible duplicate of [Best algorithm for detecting cycles in a directed graph](http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph) – Hooked Nov 13 '13 at 19:45
  • 1
    @Hooked The answers of that question point out how to detect whether there are cycles, not counting them. – pvoosten Nov 13 '13 at 19:55
  • @Hooked , its not a dup. This is about finding number of cycles. detection will return true if atleast one cycle exists, i need to find number of cycles. detection can be a subset of this question. – vindyz Nov 13 '13 at 19:56
  • @vindyz I see the spanning tree as a useful component in problems with weighted graphs. I don't see where you're heading with that. – pvoosten Nov 13 '13 at 20:13
  • @pvoosten & vindyz I've retracted my close vote, this is indeed not a duplicate. – Hooked Nov 13 '13 at 20:34
  • [This](http://cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph) may help. – artur grzesiak Nov 13 '13 at 22:41

1 Answers1

4

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.
pvoosten
  • 3,247
  • 27
  • 43