Why topo.DirectedCyclesIn does not return all the cycles?

[Jonas Ritchi]

Hello.

I'm currently solving a problem, where using a directed graph with many cycles, I need to detect all the elementary circuits.

I've chosen gonum library and it's Johnson's algorithm. 

Given this graph by adjacency list: 

adjacencyList := [][]int64{
{1, 2, 3, 4},
{0, 2, 3, 4},
{0, 1, 3, 4},
{0, 1, 2, 4},
{0, 1, 2, 3},
}

This graph has 5 vertices in total, which are all connected to each other.

Running topo.DirectedCyclesIn results in total 84 cycles.

Now, my program needs only cares about certain vertices: for example only 0, so I need to filter out all 0 elementary circuits.

By filtering results by each vertex, I get:

0 -> 64 circuits

1 -> 15 circuits

2 -> 4 = [[2 3 2] [2 3 4 2] [2 4 2] [2 4 3 2]]

3 -> 1 = [[3 4 3]]

4 -> 0 = []

When I only care about the Vertex 0, it is fine, since it returns all circuits, but for others, the full cycles are missing.

What if I want to detect cycle [4 0 1 4] for example? Reconstructing the graph, and placing my wanted vertex in place 0, seems like an option, but it will get out of hand pretty quickly if I want to look at more desired vertices.

Full code:

```

package main

import (
"fmt"

"gonum.org/v1/gonum/graph/simple"
"gonum.org/v1/gonum/graph/topo"
)

func main() {
graph := simple.NewDirectedGraph()

adjacencyList := [][]int64{
{1, 2, 3, 4},
{0, 2, 3, 4},
{0, 1, 3, 4},
{0, 1, 2, 4},
{0, 1, 2, 3},
}

for i := 0; i < len(adjacencyList); i++ {
node := graph.NewNode()
graph.AddNode(node)
}

for i := 0; i < len(adjacencyList); i++ {
for j := 0; j < len(adjacencyList[i]); j++ {
graph.SetEdge(graph.NewEdge(graph.Node(int64(i)), graph.Node(adjacencyList[i][j])))
}
}

cycles := topo.DirectedCyclesIn(graph)
fmt.Println("Total Cycles found: ", len(cycles))

var filteredCycles [][]int64

var main int64 = 3
for _, cycle := range cycles {
isMain := cycle[0].ID() == main && cycle[len(cycle)-1].ID() == main

if !isMain {
continue
}

intCycle := make([]int64, len(cycle))
for i, node := range cycle {
intCycle[i] = node.ID()
}
filteredCycles = append(filteredCycles, intCycle)

}

fmt.Println("Filtered Cycles found: ", len(filteredCycles))
fmt.Println(filteredCycles)
}

```

[Dan Kortschak]

I think there is a misunderstanding of the significance of the ordering
of the nodes in each of the cycle slices; that is, there is no
significance. The first node in the cycle is just the first node that
the walk was chosen to start on (and the last node will always match,
so the second condition you have is redundant).

If you want to select circuits that include a given node, you will need
to check all nodes so, https://go.dev/play/p/z6hvTPZMJwR (names
marginally less misleading, but the notion of main does not make sense,
so it really shouldn't be called that).

Perhaps it would be helpful to provide an intuition of what it is that
you are trying to achieve?