Cycles
This option finds the cycles in a graph. A cycle is a path that visits no vertex more than once and returns to its starting point. For undirected graphs, 'cycles' that involve shuttling back and forth along a single edge are ignored.
The first line specifies the calculation required. It must contain
format cycle
| Column | Description |
|---|---|
| 1 | l for link |
| 2 | src node name |
| 3 | dst node name |
By default all cycles in the graph are found. If this line is included the cycles are limited to those that include the specified 'starting' vertex.
| Column | Description |
|---|---|
| 1 | s |
| 2 | starting vertex name |
format cycle
l a b
l b c
l c d
l d a
The algorithm is a modified depth first search. When a previously visited vertex is reached, the Dijsktra algorithm is applied to find the path that forms the shortest cycle that leads back to the back edge to the previously visited vertex.
Processing the Zachary test data set ( https://en.wikipedia.org/wiki/Zachary%27s_karate_club ) requires 4 milliseconds to find the 42 cycles, while building the histogram takes 2 microseconds.