Find cycles easily

Help
1

Is there any easy way to find cycles in graphs?

  1. List their node names?
  2. Or highlight with red color their edges or nodes somehow to notice them easily on huge graph?

For example, here I need nodes:
10-11-12
7-7
or at least the whole chain (9-10-11-12-13-14 and 5-6-7-8), because I have many such chains without cycles in a large graph and a few chains with cycles and want to find them quickly.

 digraph {rankdir=LR;
1 -> 2
2 -> 3
3 -> 4
5 -> 6
6 -> 7
7 -> 7
7 -> 8
9 -> 10
10 -> 11
11 -> 12
12 -> 10
12 -> 13
13 -> 14
}

изображение
изображение781×299 11 KB

2

It might be useful to look at the acyclic tool in graphviz.

If it doesn’t do quite what you need, it’s still very hackable If you can code in the ancient “C“ language.

1 Like
3

Here is a hacked version of the cycle (gvpr) program (written by Emden?) that comes with the Graphviz source.
Save it in a file named cycleColor.gvpr and use it like so:
gvpr -cf cycleColor.gvpr myFile.gv >mybetterFile.gv

cycleColor:

/*
  a hacked version of the "cycle" gvpr program found in the Graphviz source

  Detect directed cycles 
*/
BEG_G{
  int      cnt, i;
  node_t   tp, hp;
  node_t   stack[node_t];
  edge_t   anEdge;
  string   Tail[], Head[];
  $tvtype = TV_prepostfwd;
  $tvroot = fstnode($);
}
N {
  if (stack[$]) {
    stack[$] = NULL;
  } else if ($tvedge == NULL) { /* current root */
    stack[$] = $;
  } else {
    stack[$] = $tvedge.tail;
  }
}
E {
  if (stack[$.head]) {
    tp = $.tail;
    hp = $.head;
    $.color="red";
    tp.color="green";
    while (tp != $.head) {
      tp.color="green";
      hp.color="green";
      hp = tp;
      tp = stack[tp];
      anEdge=isEdge(tp, hp, "");
      anEdge.color="red";
    }
  }
}

Giving:

o
o683×277 17.4 KB

1 Like
4

Wow!!! Unbelievable!
That’s exactly what I need!
Thanks!

5

Somebody should make an AI assistant that can help people to do all these useful things, just using natural language, and some kind of nice display front end probably d3-graphviz.

2 Likes