graph - protocolo - Encontrar todos los ciclos en gráficos no dirigidos

open graphs

Question

Necesito un algoritmo de trabajo para encontrar todos los ciclos simples en un gráfico no dirigido. Sé que el costo puede ser exponencial y el problema es NP-completo, pero voy a usarlo en un pequeño gráfico (hasta 20-30 vértices) y los ciclos son pequeños en número.

Después de una larga investigación (principalmente aquí) aún no tengo un enfoque de trabajo. Aquí hay un resumen de mi búsqueda:

Encontrar todos los ciclos en un gráfico no dirigido

Ciclos en un gráfico no dirigido -> detecta solo si hay un ciclo o no

Encontrar polígonos dentro de un Gráfico no dirigido -> descripción muy bonita, pero no hay solución

Encontrar todos los ciclos en un gráfico dirigido -> encuentra ciclos solo en gráficos dirigidos

Detecta ciclos en gráfico no dirigido usando la biblioteca de gráficos de impulso

La única respuesta que encontré, que se acerca a mi problema, es esta:

Encuentra todos los ciclos en gráfico, redux

Parece que encontrar un conjunto básico de ciclos y XOR-ing podría hacer el truco. Encontrar un conjunto básico de ciclos es fácil, pero no entiendo cómo combinarlos para obtener todos los ciclos en el gráfico ...

Answer 1

Aquí hay una versión C ++ del código python anterior:

std::vector< std::vector<vertex_t> > Graph::findAllCycles()
{
std::vector< std::vector<vertex_t> > cycles;
std::function<void(std::vector<vertex_t>)> findNewCycles = [&]( std::vector<vertex_t> sub_path )
{
auto visisted = []( vertex_t v, const std::vector<vertex_t> & path ){
return std::find(path.begin(),path.end(),v) != path.end();
};
auto rotate_to_smallest = []( std::vector<vertex_t> path ){
std::rotate(path.begin(), std::min_element(path.begin(), path.end()), path.end());
return path;
};
auto invert = [&]( std::vector<vertex_t> path ){
std::reverse(path.begin(),path.end());
return rotate_to_smallest(path);
};
auto isNew = [&cycles]( const std::vector<vertex_t> & path ){
return std::find(cycles.begin(), cycles.end(), path) == cycles.end();
};
vertex_t start_node = sub_path[0];
vertex_t next_node;
// visit each edge and each node of each edge
for(auto edge : edges)
{
if( edge.has(start_node) )
{
vertex_t node1 = edge.v1, node2 = edge.v2;
if(node1 == start_node)
next_node = node2;
else
next_node = node1;
if( !visisted(next_node, sub_path) )
{
// neighbor node not on path yet
std::vector<vertex_t> sub;
sub.push_back(next_node);
sub.insert(sub.end(), sub_path.begin(), sub_path.end());
findNewCycles( sub );
}
else if( sub_path.size() > 2 && next_node == sub_path.back() )
{
// cycle found
auto p = rotate_to_smallest(sub_path);
auto inv = invert(p);
if( isNew(p) && isNew(inv) )
cycles.push_back( p );
}
}
}
};
for(auto edge : edges)
{
findNewCycles( std::vector<vertex_t>(1,edge.v1) );
findNewCycles( std::vector<vertex_t>(1,edge.v2) );
}
}

Answer 2

Aquí hay una versión MATLAB muy corta de este algoritmo adaptado del código python anterior, para cualquier persona que pueda necesitarlo también.

function cycleList = searchCycles(edgeMap)
tic
global graph cycles numCycles;
graph = edgeMap;
numCycles = 0;
cycles = {};
for i = 1:size(graph,1)
for j = 1:2
findNewCycles(graph(i,j))
end
end
% print out all found cycles
for i = 1:size(cycles,2)
cycles{i}
end
% return the result
cycleList = cycles;
toc
function findNewCycles(path)
global graph cycles numCycles;
startNode = path(1);
nextNode = nan;
sub = [];
% visit each edge and each node of each edge
for i = 1:size(graph,1)
node1 = graph(i,1);
node2 = graph(i,2);
if node1 == startNode
nextNode = node2;
elseif node2 == startNode
nextNode = node1;
end
if ~(visited(nextNode, path))
% neighbor node not on path yet
sub = nextNode;
sub = [sub path];
% explore extended path
findNewCycles(sub);
elseif size(path,2) > 2 && nextNode == path(end)
% cycle found
p = rotate_to_smallest(path);
inv = invert(p);
if isNew(p) && isNew(inv)
numCycles = numCycles + 1;
cycles{numCycles} = p;
end
end
end
function inv = invert(path)
inv = rotate_to_smallest(path(end:-1:1));
% rotate cycle path such that it begins with the smallest node
function new_path = rotate_to_smallest(path)
[~,n] = min(path);
new_path = [path(n:end), path(1:n-1)];
function result = isNew(path)
global cycles
result = 1;
for i = 1:size(cycles,2)
if size(path,2) == size(cycles{i},2) && all(path == cycles{i})
result = 0;
break;
end
end
function result = visited(node,path)
result = 0;
if isnan(node) && any(isnan(path))
result = 1;
return
end
for i = 1:size(path,2)
if node == path(i)
result = 1;
break
end
end

Answer 3

Aquí hay una versión del nodo del código python.

const graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]]
let cycles = []
function main() {
for (const edge of graph) {
for (const node of edge) {
findNewCycles([node])
}
}
for (cy of cycles) {
console.log(cy.join('',''))
}
}
function findNewCycles(path) {
const start_node = path[0]
let next_node = null
let sub = []
// visit each edge and each node of each edge
for (const edge of graph) {
const [node1, node2] = edge
if (edge.includes(start_node)) {
next_node = node1 === start_node ? node2 : node1
}
if (notVisited(next_node, path)) {
// eighbor node not on path yet
sub = [next_node].concat(path)
// explore extended path
findNewCycles(sub)
} else if (path.length > 2 && next_node === path[path.length - 1]) {
// cycle found
const p = rotateToSmallest(path)
const inv = invert(p)
if (isNew(p) && isNew(inv)) {
cycles.push(p)
}
}
}
}
function invert(path) {
return rotateToSmallest([...path].reverse())
}
// rotate cycle path such that it begins with the smallest node
function rotateToSmallest(path) {
const n = path.indexOf(Math.min(...path))
return path.slice(n).concat(path.slice(0, n))
}
function isNew(path) {
const p = JSON.stringify(path)
for (const cycle of cycles) {
if (p === JSON.stringify(cycle)) {
return false
}
}
return true
}
function notVisited(node, path) {
const n = JSON.stringify(node)
for (const p of path) {
if (n === JSON.stringify(p)) {
return false
}
}
return true
}
main()

Answer 4

Aquí hay una versión vb .net del código python anterior:

Module Module1
'' Graph modelled as list of edges
Public graph As Integer(,) = {{{1, 2}, {1, 3}, {1, 4}, {2, 3},
{3, 4}, {2, 6}, {4, 6}, {7, 8},
{8, 9}, {9, 7}}
Public cycles As New List(Of Integer())()
Sub Main()
For i As Integer = 0 To graph.GetLength(0) - 1
For j As Integer = 0 To graph.GetLength(1) - 1
findNewCycles(New Integer() {graph(i, j)})
Next
Next
For Each cy As Integer() In cycles
Dim s As String
s = cy(0)
For i As Integer = 1 To cy.Length - 1
s = s & "," & cy(i)
Next
Console.WriteLine(s)
Debug.Print(s)
Next
End Sub
Private Sub findNewCycles(path As Integer())
Dim n As Integer = path(0)
Dim x As Integer
Dim [sub] As Integer() = New Integer(path.Length) {}
For i As Integer = 0 To graph.GetLength(0) - 1
For y As Integer = 0 To 1
If graph(i, y) = n Then
'' edge referes to our current node
x = graph(i, (y + 1) Mod 2)
If Not visited(x, path) Then
'' neighbor node not on path yet
[sub](0) = x
Array.Copy(path, 0, [sub], 1, path.Length)
'' explore extended path
findNewCycles([sub])
ElseIf (path.Length > 2) AndAlso (x = path(path.Length - 1)) Then
'' cycle found
Dim p As Integer() = normalize(path)
Dim inv As Integer() = invert(p)
If isNew(p) AndAlso isNew(inv) Then
cycles.Add(p)
End If
End If
End If
Next
Next
End Sub
Private Function equals(a As Integer(), b As Integer()) As Boolean
Dim ret As Boolean = (a(0) = b(0)) AndAlso (a.Length = b.Length)
Dim i As Integer = 1
While ret AndAlso (i < a.Length)
If a(i) <> b(i) Then
ret = False
End If
i += 1
End While
Return ret
End Function
Private Function invert(path As Integer()) As Integer()
Dim p As Integer() = New Integer(path.Length - 1) {}
For i As Integer = 0 To path.Length - 1
p(i) = path(path.Length - 1 - i)
Next
Return normalize(p)
End Function
'' rotate cycle path such that it begins with the smallest node
Private Function normalize(path As Integer()) As Integer()
Dim p As Integer() = New Integer(path.Length - 1) {}
Dim x As Integer = smallest(path)
Dim n As Integer
Array.Copy(path, 0, p, 0, path.Length)
While p(0) <> x
n = p(0)
Array.Copy(p, 1, p, 0, p.Length - 1)
p(p.Length - 1) = n
End While
Return p
End Function
Private Function isNew(path As Integer()) As Boolean
Dim ret As Boolean = True
For Each p As Integer() In cycles
If equals(p, path) Then
ret = False
Exit For
End If
Next
Return ret
End Function
Private Function smallest(path As Integer()) As Integer
Dim min As Integer = path(0)
For Each p As Integer In path
If p < min Then
min = p
End If
Next
Return min
End Function
Private Function visited(n As Integer, path As Integer()) As Boolean
Dim ret As Boolean = False
For Each p As Integer In path
If p = n Then
ret = True
Exit For
End If
Next
Return ret
End Function

Módulo final

Answer 5

Axel, he traducido tu código a Python. Aproximadamente 1/4 de las líneas de código y más claras para leer.

graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]]
cycles = []
def main():
global graph
global cycles
for edge in graph:
for node in edge:
findNewCycles([node])
for cy in cycles:
path = [str(node) for node in cy]
s = ",".join(path)
print(s)
def findNewCycles(path):
start_node = path[0]
next_node= None
sub = []
#visit each edge and each node of each edge
for edge in graph:
node1, node2 = edge
if start_node in edge:
if node1 == start_node:
next_node = node2
else:
next_node = node1
if not visited(next_node, path):
# neighbor node not on path yet
sub = [next_node]
sub.extend(path)
# explore extended path
findNewCycles(sub);
elif len(path) > 2 and next_node == path[-1]:
# cycle found
p = rotate_to_smallest(path);
inv = invert(p)
if isNew(p) and isNew(inv):
cycles.append(p)
def invert(path):
return rotate_to_smallest(path[::-1])
# rotate cycle path such that it begins with the smallest node
def rotate_to_smallest(path):
n = path.index(min(path))
return path[n:]+path[:n]
def isNew(path):
return not path in cycles
def visited(node, path):
return node in path
main()

Answer 6

Inspirado por @LetterRip y @Axel Kemper Aquí hay una versión más corta de Java:

public static int[][] graph =
{
{1, 2}, {2, 3}, {3, 4}, {2, 4},
{3, 5}
};
public static Set<List<Integer>> cycles = new HashSet<>();
static void findNewCycles(ArrayList<Integer> path) {
int start = path.get(0);
int next = -1;
for (int[] edge : graph) {
if (start == edge[0] || start == edge[1]) {
next = (start == edge[0]) ? edge[1] : edge[0];
if (!path.contains(next)) {
ArrayList<Integer> newPath = new ArrayList<>();
newPath.add(next);
newPath.addAll((path));
findNewCycles(newPath);
} else if (path.size() > 2 && next == path.get(path.size() - 1)) {
List<Integer> normalized = new ArrayList<>(path);
Collections.sort(normalized);
cycles.add(normalized);
}
}
}
}
public static void detectCycle() {
for (int i = 0; i < graph.length; i++)
for (int j = 0; j < graph[i].length; j++) {
ArrayList<Integer> path = new ArrayList<>();
path.add(graph[i][j]);
findNewCycles(path);
}
for (List<Integer> c : cycles) {
System.out.println(c);
}
}

Answer 7

La siguiente es una implementación de demostración en C # (y Java, ver el final de la respuesta) basada en la primera búsqueda de profundidad.

Un bucle externo escanea todos los nodos del gráfico e inicia una búsqueda desde cada nodo. Los vecinos del nodo (de acuerdo con la lista de bordes) se agregan a la ruta del ciclo. La recursividad finaliza si no se pueden agregar más vecinos no visitados. Se encuentra un nuevo ciclo si la ruta es más larga que dos nodos y el siguiente vecino es el inicio de la ruta. Para evitar ciclos duplicados, los ciclos se normalizan girando el nodo más pequeño al inicio. Los ciclos en orden invertido también se tienen en cuenta.

Esto es solo una implementación ingenua. El periódico clásico es: Donald B. Johnson. Encontrar todos los circuitos elementales de un grafo dirigido. SIAM J. Comput., 4 (1): 77 - 84, 1975.

Una encuesta reciente de algoritmos modernos se puede encontrar here

using System;
using System.Collections.Generic;
namespace akCyclesInUndirectedGraphs
{
class Program
{
// Graph modelled as list of edges
static int[,] graph =
{
{1, 2}, {1, 3}, {1, 4}, {2, 3},
{3, 4}, {2, 6}, {4, 6}, {7, 8},
{8, 9}, {9, 7}
};
static List<int[]> cycles = new List<int[]>();
static void Main(string[] args)
{
for (int i = 0; i < graph.GetLength(0); i++)
for (int j = 0; j < graph.GetLength(1); j++)
{
findNewCycles(new int[] {graph[i, j]});
}
foreach (int[] cy in cycles)
{
string s = "" + cy[0];
for (int i = 1; i < cy.Length; i++)
s += "," + cy[i];
Console.WriteLine(s);
}
}
static void findNewCycles(int[] path)
{
int n = path[0];
int x;
int[] sub = new int[path.Length + 1];
for (int i = 0; i < graph.GetLength(0); i++)
for (int y = 0; y <= 1; y++)
if (graph[i, y] == n)
// edge referes to our current node
{
x = graph[i, (y + 1) % 2];
if (!visited(x, path))
// neighbor node not on path yet
{
sub[0] = x;
Array.Copy(path, 0, sub, 1, path.Length);
// explore extended path
findNewCycles(sub);
}
else if ((path.Length > 2) && (x == path[path.Length - 1]))
// cycle found
{
int[] p = normalize(path);
int[] inv = invert(p);
if (isNew(p) && isNew(inv))
cycles.Add(p);
}
}
}
static bool equals(int[] a, int[] b)
{
bool ret = (a[0] == b[0]) && (a.Length == b.Length);
for (int i = 1; ret && (i < a.Length); i++)
if (a[i] != b[i])
{
ret = false;
}
return ret;
}
static int[] invert(int[] path)
{
int[] p = new int[path.Length];
for (int i = 0; i < path.Length; i++)
p[i] = path[path.Length - 1 - i];
return normalize(p);
}
// rotate cycle path such that it begins with the smallest node
static int[] normalize(int[] path)
{
int[] p = new int[path.Length];
int x = smallest(path);
int n;
Array.Copy(path, 0, p, 0, path.Length);
while (p[0] != x)
{
n = p[0];
Array.Copy(p, 1, p, 0, p.Length - 1);
p[p.Length - 1] = n;
}
return p;
}
static bool isNew(int[] path)
{
bool ret = true;
foreach(int[] p in cycles)
if (equals(p, path))
{
ret = false;
break;
}
return ret;
}
static int smallest(int[] path)
{
int min = path[0];
foreach (int p in path)
if (p < min)
min = p;
return min;
}
static bool visited(int n, int[] path)
{
bool ret = false;
foreach (int p in path)
if (p == n)
{
ret = true;
break;
}
return ret;
}
}
}

Los ciclos para el gráfico de demostración:

1,3,2
1,4,3,2
1,4,6,2
1,3,4,6,2
1,4,6,2,3
1,4,3
2,6,4,3
7,9,8

El algoritmo codificado en Java:

import java.util.ArrayList;
import java.util.List;
public class GraphCycleFinder {
// Graph modeled as list of edges
static int[][] graph =
{
{1, 2}, {1, 3}, {1, 4}, {2, 3},
{3, 4}, {2, 6}, {4, 6}, {7, 8},
{8, 9}, {9, 7}
};
static List<int[]> cycles = new ArrayList<int[]>();
/**
* @param args
*/
public static void main(String[] args) {
for (int i = 0; i < graph.length; i++)
for (int j = 0; j < graph[i].length; j++)
{
findNewCycles(new int[] {graph[i][j]});
}
for (int[] cy : cycles)
{
String s = "" + cy[0];
for (int i = 1; i < cy.length; i++)
{
s += "," + cy[i];
}
o(s);
}
}
static void findNewCycles(int[] path)
{
int n = path[0];
int x;
int[] sub = new int[path.length + 1];
for (int i = 0; i < graph.length; i++)
for (int y = 0; y <= 1; y++)
if (graph[i][y] == n)
// edge refers to our current node
{
x = graph[i][(y + 1) % 2];
if (!visited(x, path))
// neighbor node not on path yet
{
sub[0] = x;
System.arraycopy(path, 0, sub, 1, path.length);
// explore extended path
findNewCycles(sub);
}
else if ((path.length > 2) && (x == path[path.length - 1]))
// cycle found
{
int[] p = normalize(path);
int[] inv = invert(p);
if (isNew(p) && isNew(inv))
{
cycles.add(p);
}
}
}
}
// check of both arrays have same lengths and contents
static Boolean equals(int[] a, int[] b)
{
Boolean ret = (a[0] == b[0]) && (a.length == b.length);
for (int i = 1; ret && (i < a.length); i++)
{
if (a[i] != b[i])
{
ret = false;
}
}
return ret;
}
// create a path array with reversed order
static int[] invert(int[] path)
{
int[] p = new int[path.length];
for (int i = 0; i < path.length; i++)
{
p[i] = path[path.length - 1 - i];
}
return normalize(p);
}
// rotate cycle path such that it begins with the smallest node
static int[] normalize(int[] path)
{
int[] p = new int[path.length];
int x = smallest(path);
int n;
System.arraycopy(path, 0, p, 0, path.length);
while (p[0] != x)
{
n = p[0];
System.arraycopy(p, 1, p, 0, p.length - 1);
p[p.length - 1] = n;
}
return p;
}
// compare path against known cycles
// return true, iff path is not a known cycle
static Boolean isNew(int[] path)
{
Boolean ret = true;
for(int[] p : cycles)
{
if (equals(p, path))
{
ret = false;
break;
}
}
return ret;
}
static void o(String s)
{
System.out.println(s);
}
// return the int of the array which is the smallest
static int smallest(int[] path)
{
int min = path[0];
for (int p : path)
{
if (p < min)
{
min = p;
}
}
return min;
}
// check if vertex n is contained in path
static Boolean visited(int n, int[] path)
{
Boolean ret = false;
for (int p : path)
{
if (p == n)
{
ret = true;
break;
}
}
return ret;
}
}

Answer 8

La versión de Matlab omitió algo, la función findNewCycles (ruta) debería ser:

función findNewCycles (ruta)

global graph cycles numCycles;
startNode = path(1);
nextNode = nan;
sub = [];
% visit each edge and each node of each edge
for i = 1:size(graph,1)
node1 = graph(i,1);
node2 = graph(i,2);
if (node1 == startNode) || (node2==startNode) %% this if is required
if node1 == startNode
nextNode = node2;
elseif node2 == startNode
nextNode = node1;
end
if ~(visited(nextNode, path))
% neighbor node not on path yet
sub = nextNode;
sub = [sub path];
% explore extended path
findNewCycles(sub);
elseif size(path,2) > 2 && nextNode == path(end)
% cycle found
p = rotate_to_smallest(path);
inv = invert(p);
if isNew(p) && isNew(inv)
numCycles = numCycles + 1;
cycles{numCycles} = p;
end
end
end
end

Answer 9

Para un gráfico no dirigido, el enfoque estándar es buscar una llamada base de ciclo: un conjunto de ciclos simples a partir de los cuales se puede generar mediante combinaciones de todos los demás ciclos. Estos no son necesariamente todos los ciclos simples en el gráfico. Considere por ejemplo el siguiente gráfico:

 A
/ /
B ----- C
/ /
D

Aquí hay 3 ciclos simples: ABCA, BCDB y ABDCA. Sin embargo, puede tomar cada 2 de estos como base y obtener el 3d como una combinación del 2. Esto es una diferencia sustancial de los gráficos dirigidos donde uno no puede combinar ciclos tan libremente debido a la necesidad de observar la dirección del borde.

El algoritmo de referencia estándar para encontrar una base de ciclo para un gráfico no dirigido es este: construya un árbol de expansión y luego para cada borde que no sea parte del árbol, construya un ciclo desde ese borde y algunos bordes en el árbol. Tal ciclo debe existir porque de lo contrario el borde sería parte del árbol.

Para el gráfico de muestra de arriba, un árbol de expansión es, por ejemplo, este:

 A
/ /
B C
/
D

Los 2 bordes que no están en el árbol son BC y CD. Y los ciclos simples correspondientes son ABCA y ABDCA.

También puedes construir el siguiente árbol de expansión:

 A
/
B ----- C
/
D

Y luego los ciclos simples que obtienes son ABCA y BCDB.

El algoritmo de línea de base se puede refinar de diferentes maneras. Que yo sepa, el mejor refinamiento pertenece a Paton (K. Paton, un algoritmo para encontrar un conjunto fundamental de ciclos para un gráfico lineal no dirigido, Comm. ACM 12 (1969), pp. 514-518). Una implementación de código abierto en Java está disponible aquí: http://code.google.com/p/niographs/ .

Debería haber mencionado cómo combinas ciclos simples de la base del ciclo para formar nuevos ciclos simples. Comience enumerando en cualquier orden (pero fijo en el más allá) todos los bordes del gráfico. Luego, representa los ciclos por secuencias de ceros y unos colocando los que están en las posiciones de los bordes que pertenecen al ciclo y los ceros en las posiciones de los bordes que no son parte del ciclo. A continuación, realiza O exclusivo en modo bit (XOR) de las secuencias. La razón por la que hace XOR es que quiere excluir los bordes que pertenecen a ambos ciclos y así hacer que el ciclo combinado no sea simple. También debe comprobar que los 2 ciclos tienen ALGUNOS bordes comunes comprobando que el AND bit a bit de las secuencias no es todo ceros. De lo contrario, el resultado de XOR será de 2 ciclos disjuntos en lugar de un nuevo ciclo simple.

Aquí hay un ejemplo para el gráfico de muestra anterior:

Comenzamos enumerando los bordes: ((AB), (AC), (BC), (BD), (CD)). Luego, los ciclos simples ABCA, BDCB y ABDCA se representan como (1, 1, 1, 0, 0), (0, 0, 1, 1, 1) y (1, 1, 0, 1, 1). Ahora podemos, por ejemplo, XOR ABCA con BDCB y el resultado es (1, 1, 0, 1, 1) que es exactamente ABDCA. O podemos XOR ABCA y ABDCA con el resultado de (0, 0, 1, 1, 1). Que es exactamente BDCB.

Dada una base de ciclo, puede descubrir todos los ciclos simples al examinar todas las combinaciones posibles de 2 o más ciclos básicos distintos. El procedimiento se describe con más detalle aquí: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf en la página 14.

En aras de la exhaustividad, notaría que parece posible (e ineficiente) usar algoritmos para encontrar todos los ciclos simples de un gráfico dirigido. Cada borde del gráfico no dirigido puede reemplazarse por 2 bordes dirigidos que van en direcciones opuestas. Entonces los algoritmos para gráficos dirigidos deberían funcionar. Habrá 1 ciclo "falso" de 2 nodos para cada borde del gráfico no dirigido que deberá ignorarse y habrá una versión en sentido horario y una antihoraria de cada ciclo simple del gráfico no dirigido. La implementación de código abierto en Java de algoritmos para encontrar todos los ciclos en un gráfico dirigido se puede encontrar en el enlace que ya cité.

Answer 10

Parece que el buscador de ciclos anterior tiene algunos problemas. La versión de C # no puede encontrar algunos ciclos. Mi gráfica es:

 {2,8},{4,8},{5,8},{1,9},{3,9},{4,9},{5,9},{6,9},{1,10},
{4,10},{5,10},{6,10},{7,10},{1,11},{4,11},{6,11},{7,11},
{1,12},{2,12},{3,12},{5,12},{6,12},{2,13},{3,13},{4,13},
{6,13},{7,13},{2,14},{5,14},{7,14}

Por ejemplo, el ciclo: 1-9-3-12-5-10 no se encuentra. Probé la versión C ++ también, devuelve un gran número (decenas de millones) de ciclos que aparentemente es incorrecto. Probablemente, no coincide con los ciclos.

Lo siento, estoy un poco arruinado y no he investigado más. Escribí mi propia versión basada en la publicación de Nikolay Ognyanov (muchas gracias por su publicación). Para el gráfico anterior, mi versión devuelve 8833 ciclos y estoy intentando verificar que sea correcta. La versión C # devuelve 8397 ciclos.