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.

Input

format

The first line specifies the calculation required. It must contain

format cycle

Links

Column	Description
1	l for link
2	src node name
3	dst node name

start

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

Example

format cycle
l a b
l b c
l c d
l d a

Algorithm

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.

Performance

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.