Encontrando todos os ciclos em grafos não direcionados

Eu preciso de um algoritmo de trabalho para encontrar todos os ciclos simples em um gráfico não direcionado. Eu sei que o custo pode ser exponencial e o problema é NP-completo, mas eu vou usá-lo em um pequeno gráfico (até 20-30 vértices) e os ciclos são pequenos em número.

Depois de uma longa pesquisa (principalmente aqui), ainda não tenho uma abordagem de trabalho. Aqui está um resumo da minha pesquisa:

Encontrando todos os ciclos em um gráfico não direcionado

Ciclos em um Gráfico Não Direcionado -> detecta somente se há um ciclo ou não

Encontrando polígonos dentro de um Graph não direcionado -> descrição muito boa, mas sem solução

Encontrar todos os ciclos em um grafo direcionado -> encontra ciclos somente em grafos direcionados

Detecta ciclos no gráfico não direcionado usando a biblioteca de charts de aumento

A única resposta que encontrei, que se aproxima do meu problema, é esta:

Encontre todos os ciclos no gráfico, redux

Parece que encontrar um conjunto básico de ciclos e XOR-los poderia fazer o truque. Encontrar um conjunto básico de ciclos é fácil, mas não entendo como combiná-los para obter todos os ciclos no gráfico …

    Para um grafo não direcionado, a abordagem padrão é procurar a chamada base do ciclo: um conjunto de ciclos simples a partir do qual é possível gerar, através de combinações, todos os outros ciclos. Estes não são necessariamente todos ciclos simples no gráfico. Considere, por exemplo, o seguinte gráfico:

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

    Existem 3 ciclos simples aqui: ABCA, BCDB e ABDCA. Você pode, no entanto, tomar cada 2 destes como uma base e obter o 3d como uma combinação do 2. Esta é uma diferença substancial de charts direcionados, onde não se pode combinar tão livremente ciclos devido à necessidade de observar a direção da borda.

    O algoritmo de linha de base padrão para encontrar uma base de ciclo para um gráfico não direcionado é: Construa uma tree de abrangência e, em seguida, para cada aresta que não faz parte da tree, construa um ciclo a partir dessa aresta e algumas arestas na tree. Tal ciclo deve existir porque de outra forma a borda seria parte da tree.

    Para o gráfico de amostra acima de uma tree de abrangência é, por exemplo, isto:

      A / \ BC \ D 

    As duas arestas que não estão na tree são BC e CD. E os ciclos simples correspondentes são ABCA e ABDCA.

    Você também pode construir a seguinte tree de abrangência:

      A / B ----- C \ D 

    E então os ciclos simples que você obtém são ABCA e BCDB.

    O algoritmo de linha de base pode ser refinado de maneiras diferentes. Tanto quanto é do meu conhecimento, o melhor refinamento pertence a Paton (K. Paton, um algoritmo para encontrar um conjunto fundamental de ciclos para um gráfico linear não direcionado, Comm. ACM 12 (1969), pp. 514-518.). Uma implementação de código aberto em Java está disponível aqui: http://code.google.com/p/niographs/ .

    Eu deveria ter mencionado como você combina ciclos simples da base do ciclo para formar novos ciclos simples. Você começa listando em qualquer ordem (mas fixa daqui em diante) todas as arestas do gráfico. Então, você representa os ciclos por seqüências de zeros e uns, colocando os mesmos nas posições das arestas que pertencem ao ciclo e os zeros nas posições das arestas que não fazem parte do ciclo. Então você faz o OR exclusivo de bits (XOR) das seqüências. A razão pela qual você faz XOR é que você deseja excluir arestas que pertencem a ambos os ciclos e, assim, tornar o ciclo combinado não-simples. Você precisa verificar também se os 2 ciclos têm ALGUMAS bordas comuns, verificando se o AND bit a bit das seqüências não é todo zeros. Caso contrário, o resultado do XOR será de dois ciclos separados, em vez de um novo ciclo simples.

    Aqui está um exemplo para o gráfico de amostra acima:

    Começamos listando as arestas: ((AB), (AC), (BC), (BD), (CD)). Então os ciclos simples ABCA, BDCB e ABDCA são representados como (1, 1, 1, 0, 0), (0, 0, 1, 1, 1) e (1, 1, 0, 1, 1). Agora podemos, por exemplo, XOR ABCA com BDCB e o resultado é (1, 1, 0, 1, 1) que é exatamente ABDCA. Ou podemos XOR ABCA e ABDCA com o resultado sendo (0, 0, 1, 1, 1). Qual é exatamente BDCB.

    Dada uma base de ciclo, você pode descobrir todos os ciclos simples examinando todas as combinações possíveis de 2 ou mais ciclos de base distintos. O procedimento é descrito em mais detalhes aqui: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf na página 14.

    Por uma questão de completude, eu notaria que parece possível (e ineficiente) usar algoritmos para encontrar todos os ciclos simples de um grafo direcionado. Cada borda do gráfico não direcionado pode ser substituída por duas bordas direcionadas indo em direções opostas. Então os algoritmos para charts direcionados devem funcionar. Haverá 1 ciclo “falso” de 2 nós para cada borda do grafo não direcionado que terá que ser ignorado e haverá uma versão no sentido horário e uma anti-horária de cada ciclo simples do grafo não direcionado. A implementação de código aberto em Java de algoritmos para encontrar todos os ciclos em um gráfico direcionado pode ser encontrada no link que já citei.

    A seguir, uma implementação de demonstração em C # (e Java, consulte o final da resposta) com base na primeira pesquisa detalhada.

    Um loop externo varre todos os nós do gráfico e inicia uma pesquisa em cada nó. Vizinhos do nó (de acordo com a lista de arestas) são adicionados ao caminho do ciclo. A recursion termina se não mais vizinhos não visitados puderem ser adicionados. Um novo ciclo é encontrado se o caminho for maior que dois nós e o próximo vizinho for o início do caminho. Para evitar ciclos duplicados, os ciclos são normalizados girando o menor nó para o início. Ciclos em ordenação invertida também são levados em conta.

    Esta é apenas uma implementação ingênua. O artigo clássico é: Donald B. Johnson. Encontrando todos os circuitos elementares de um grafo direcionado. SIAM J. Comput., 4 (1): 77-84, 1975.

    Uma pesquisa recente de algoritmos modernos pode ser encontrada aqui

     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; } } } 

    Os ciclos do gráfico de demonstração:

     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 

    O algoritmo codificado em 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, traduzi seu código para python. Cerca de 1/4 das linhas de código e mais claro para ler.

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

    Aqui está apenas uma versão muito fraca do MATLAB deste algoritmo adaptado do código python acima, para qualquer pessoa que possa precisar dele também.

     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 

    Aqui está uma versão em C ++ do código python acima:

     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) ); } } 

    Aqui está uma versão vb .net do código python acima:

     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 o localizador de ciclos acima tem alguns problemas. A versão C # não consegue encontrar alguns ciclos. Meu gráfico é:

      {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 exemplo, o ciclo: 1-9-3-12-5-10 não é encontrado. Eu também tentei a versão C ++, ela retorna um número muito grande (dezenas de milhões) de ciclos que aparentemente estão errados. Provavelmente, ele não corresponde aos ciclos.

    Desculpe, estou um pouco duro e não investiguei mais nada. Eu escrevi minha própria versão com base no post de Nikolay Ognyanov (muito obrigado pelo seu post). Para o gráfico acima, minha versão retorna 8833 ciclos e estou tentando verificar se está correta. A versão C # retorna 8397 ciclos.

    Inspirado por @LetterRip e @Axel Kemper Aqui está uma versão mais curta do 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); } } 

    Aqui está uma versão do nó do 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() 

    A versão do Matlab perdeu alguma coisa, a function findNewCycles (path) deve ser:

    function findNewCycles (caminho)

     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