Encontrar todos los ciclos en gráficos no dirigidos

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 …

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 / \ BC \ 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é.

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 aquí

 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 cycles = new List(); 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 cycles = new ArrayList(); /** * @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; } } 

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() 

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 

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

 std::vector< std::vector > Graph::findAllCycles() { std::vector< std::vector > cycles; std::function)> findNewCycles = [&]( std::vector sub_path ) { auto visisted = []( vertex_t v, const std::vector & path ){ return std::find(path.begin(),path.end(),v) != path.end(); }; auto rotate_to_smallest = []( std::vector path ){ std::rotate(path.begin(), std::min_element(path.begin(), path.end()), path.end()); return path; }; auto invert = [&]( std::vector path ){ std::reverse(path.begin(),path.end()); return rotate_to_smallest(path); }; auto isNew = [&cycles]( const std::vector & 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 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(1,edge.v1) ); findNewCycles( std::vector(1,edge.v2) ); } } 

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

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.

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> cycles = new HashSet<>(); static void findNewCycles(ArrayList 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 newPath = new ArrayList<>(); newPath.add(next); newPath.addAll((path)); findNewCycles(newPath); } else if (path.size() > 2 && next == path.get(path.size() - 1)) { List 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 path = new ArrayList<>(); path.add(graph[i][j]); findNewCycles(path); } for (List c : cycles) { System.out.println(c); } } 

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() 

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 
    Intereting Posts