Trovare tutti i cicli in un grafico diretto

Come posso trovare (scorrere su) TUTTI i cicli in un grafico diretto da / a un determinato nodo?

Ad esempio, voglio qualcosa di simile a questo:

A->B->A A->B->C->A 

ma non: B-> C-> B

Ho trovato questa pagina nella mia ricerca e poiché i cicli non sono uguali a componenti fortemente connessi, ho continuato a cercare e, infine, ho trovato un algoritmo efficiente che elenca tutti i cicli (elementari) di un grafico diretto. È di Donald B. Johnson e la carta può essere trovata al seguente link:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

Un’implementazione java può essere trovata in:

http://normalisiert.de/code/java/elementaryCycles.zip

Una dimostrazione di Mathematica dell’algoritmo di Johnson può essere trovata qui , l’implementazione può essere scaricata da destra ( “Scarica il codice dell’autore” ).

Nota: in realtà, ci sono molti algoritmi per questo problema. Alcuni di loro sono elencati in questo articolo:

http://dx.doi.org/10.1137/0205007

Secondo l’articolo, l’algoritmo di Johnson è il più veloce.

La prima ricerca della profondità con il backtracking dovrebbe funzionare qui. Mantieni una matrice di valori booleani per tenere traccia di se hai già visitato un nodo. Se si esauriscono i nuovi nodes per andare a (senza colpire un nodo che si è già stati), quindi tornare indietro e provare un ramo diverso.

Il DFS è facile da implementare se si dispone di un elenco di adiacenze per rappresentare il grafico. Ad esempio adj [A] = {B, C} indica che B e C sono figli di A.

Ad esempio, pseudo-codice qui sotto. “start” è il nodo da cui parti.

 dfs(adj,node,visited): if (visited[node]): if (node == start): "found a path" return; visited[node]=YES; for child in adj[node]: dfs(adj,child,visited) visited[node]=NO; 

Chiama la funzione sopra con il nodo di avvio:

 visited = {} dfs(adj,start,visited) 

Prima di tutto – non vuoi veramente cercare di trovare letteralmente tutti i cicli perché se c’è 1 allora c’è un numero infinito di quelli. Ad esempio ABA, ABABA ecc. Oppure potrebbe essere ansible unire 2 cicli in un ciclo di tipo 8 ecc. Ecc. L’approccio significativo è cercare tutti i cosiddetti cicli semplici, quelli che non si incrociano tranne nel punto iniziale / finale. Quindi se lo desideri puoi generare combinazioni di cicli semplici.

Uno degli algoritmi di base per la ricerca di tutti i cicli semplici in un grafico diretto è questo: eseguire un attraversamento in profondità di tutti i percorsi semplici (quelli che non si incrociano) nel grafico. Ogni volta che il nodo corrente ha un successore nello stack, viene scoperto un semplice ciclo. Consiste degli elementi in pila che iniziano con il successore identificato e terminano con la cima della pila. Il primo attraversamento di profondità di tutti i percorsi semplici è simile alla prima ricerca di profondità ma non contrassegni / registri nodes visitati diversi da quelli attualmente in pila come punti di arresto.

L’algoritmo della forza bruta di cui sopra è terribilmente inefficiente e in aggiunta a quello genera più copie dei cicli. È tuttavia il punto di partenza di molteplici algoritmi pratici che applicano vari miglioramenti al fine di migliorare le prestazioni ed evitare la duplicazione del ciclo. Sono stato sorpreso di scoprire qualche tempo fa che questi algoritmi non sono prontamente disponibili nei libri di testo e sul web. Così ho fatto qualche ricerca e implementato 4 algoritmi di questo tipo e 1 algoritmo per cicli in grafici non orientati in una libreria Java open source qui: http://code.google.com/p/niographs/ .

A proposito, dal momento che ho menzionato i grafi non orientati: l’algoritmo per quelli è diverso. Costruisci uno spanning tree e quindi ogni spigolo che non fa parte dell’albero forma un semplice ciclo insieme ad alcuni bordi dell’albero. I cicli trovati in questo modo formano una cosiddetta base ciclica. Tutti i cicli semplici possono quindi essere trovati combinando 2 o più cicli di base distinti. Per maggiori dettagli vedi ad esempio questo: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

La scelta più semplice che ho trovato per risolvere questo problema era usare la lib python chiamata networkx .

Implementa l’algoritmo di Johnson menzionato nella migliore risposta di questa domanda, ma rende abbastanza semplice l’esecuzione.

In breve è necessario quanto segue:

 import networkx as nx import matplotlib.pyplot as plt # Create Directed Graph G=nx.DiGraph() # Add a list of nodes: G.add_nodes_from(["a","b","c","d","e"]) # Add a list of edges: G.add_edges_from([("a","b"),("b","c"), ("c","a"), ("b","d"), ("d","e"), ("e","a")]) #Return a list of cycles described as a list o nodes list(nx.simple_cycles(G)) 

Risposta: [[‘a’, ‘b’, ‘d’, ‘e’], [‘a’, ‘b’, ‘c’]]

inserisci la descrizione dell'immagine qui

Chiarire:

  1. Componenti fortemente collegati troveranno tutti i sottografi che contengono almeno un ciclo e non tutti i cicli possibili nel grafico. Ad esempio, se si prendono tutte le componenti fortemente connesse e si comprime / raggruppa / unisce ciascuna di esse in un nodo (cioè un nodo per componente), si otterrà un albero senza cicli (un DAG in realtà). Ogni componente (che è fondamentalmente un sottografo con almeno un ciclo in esso) può contenere molti più cicli possibili internamente, quindi SCC NON troverà tutti i cicli possibili, troverà tutti i possibili gruppi che hanno almeno un ciclo e se si raggruppa loro, quindi il grafico non avrà cicli.

  2. per trovare tutti i cicli semplici in un grafico, come altri hanno menzionato, l’algoritmo di Johnson è un candidato.

Mi è stata data questa domanda come intervista una volta, ho il sospetto che questo sia successo a te e tu stai venendo qui per chiedere aiuto. Rompa il problema in tre domande e diventa più facile.

  1. come si determina il prossimo percorso valido
  2. come si determina se un punto è stato utilizzato
  3. come evitare di attraversare nuovamente lo stesso punto

Problema 1) Utilizzare il pattern iteratore per fornire un modo per iterare i risultati del percorso. Un buon posto per mettere la logica per ottenere il prossimo percorso è probabilmente il “moveNext” del tuo iteratore. Per trovare un percorso valido, dipende dalla struttura dei dati. Per me è stata una tabella sql piena di valide opzioni di percorso, quindi ho dovuto creare una query per ottenere le destinazioni valide fornite da una fonte.

Problema 2) Spingi ogni nodo come li trovi in ​​una raccolta man mano che li ottieni, questo significa che puoi vedere se stai “raddoppiando” su un punto molto facilmente interrogando la collezione che stai costruendo al volo.

Problema 3) Se in qualsiasi momento vedi che stai raddoppiando, puoi estrarre le cose dalla raccolta e “eseguire il backup”. Quindi da quel punto prova a “andare avanti” di nuovo.

Hack: se stai usando SQL Server 2008 ci sono alcune nuove “gerarchie” che puoi usare per risolvere rapidamente questo se si strutturano i dati in un albero.

Ci sono due passaggi (algoritmi) coinvolti nella ricerca di tutti i cicli in un DAG.

Il primo passo è usare l’algoritmo di Tarjan per trovare il set di componenti fortemente connessi.

  1. Inizia da qualsiasi vertice arbitrario.
  2. DFS da quel vertice. Per ogni nodo x, mantieni due numeri, dfs_index [x] e dfs_lowval [x]. dfs_index [x] memorizza quando quel nodo viene visitato, mentre dfs_lowval [x] = min (dfs_low [k]) dove k è tutti i figli di x che non è il genitore diretto di x nell’albero dfs-spanning.
  3. Tutti i nodes con lo stesso dfs_lowval [x] si trovano nello stesso componente fortemente connesso.

Il secondo passo è trovare i cicli (percorsi) all’interno dei componenti connessi. Il mio suggerimento è di usare una versione modificata dell’algoritmo di Hierholzer.

L’idea è:

  1. Scegli qualsiasi vertice iniziale v, e segui una scia di spigoli da quel vertice fino a tornare a v. Non è ansible rimanere bloccati in nessun vertice tranne v, perché il grado pari di tutti i vertici assicura che, quando il sentiero entra in un altro vertice w ci deve essere un bordo inutilizzato lasciando w. Il tour formato in questo modo è un tour chiuso, ma potrebbe non coprire tutti i vertici e i bordi del grafico iniziale.
  2. Finché esiste un vertice v che appartiene al tour corrente ma che ha bordi adiacenti non parte del tour, inizia un’altra traccia da v, seguendo i bordi inutilizzati fino a tornare a v, e unisciti al tour formato in questo modo verso il tour precedente.

Ecco il link a un’implementazione Java con un caso di test:

http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html

Nel caso del grafico non orientato, un articolo pubblicato di recente ( elenco ottimale di cicli e percorsi st nei grafici non orientati) offre una soluzione asintoticamente ottimale. Puoi leggerlo qui http://arxiv.org/abs/1205.2766 o qui http://dl.acm.org/citation.cfm?id=2627951 So che non risponde alla tua domanda, ma dal titolo di la tua domanda non menziona la direzione, potrebbe comunque essere utile per la ricerca di Google

Inizia dal nodo X e controlla tutti i nodes figlio (i nodes padre e figlio sono equivalenti se non diretti). Contrassegna quei nodes figli come figli di X. Da qualsiasi nodo figlio A, contrassegna che sono figli di essere figli di A, X ‘, dove X’ è contrassegnato come a 2 passi di distanza.). Se successivamente colpisci X e lo contrassegni come figlio di X ”, significa che X è in un ciclo a 3 nodes. Backtracking al suo genitore è facile (così com’è, l’algoritmo non ha supporto per questo, quindi potresti trovare qualsiasi genitore abbia X ‘).

Nota: se il grafico non è orientato o presenta spigoli bidirezionali, questo algoritmo diventa più complicato, assumendo che non si desideri attraversare lo stesso bordo due volte per un ciclo.

Se quello che vuoi è trovare tutti i circuiti elementari in un grafico puoi usare l’algoritmo CE, di JAMES C. TIERNAN, trovato su un foglio dal 1970.

L’algoritmo EC molto originale come sono riuscito a implementarlo in php (spero che non ci siano errori è mostrato sotto). Può trovare anche dei loop se ce ne sono. I circuiti in questa implementazione (che tenta di clonare l’originale) sono gli elementi non zero. Zero qui rappresenta la non esistenza (nulla come la conosciamo).

A parte ciò che segue, segue un’altra implementazione che fornisce l’algoritmo più indipendente, questo significa che i nodes possono partire da qualsiasi luogo anche da numeri negativi, ad esempio -4, -3, -2, .. ecc.

In entrambi i casi è necessario che i nodes siano sequenziali.

Potrebbe essere necessario studiare il documento originale, James C. Tiernan Elementary Circuit Algorithm

 

"; $G = array( 1=>array(1,2,3), 2=>array(1,2,3), 3=>array(1,2,3) ); define('N',key(array_slice($G, -1, 1, true))); $P = array(1=>0,2=>0,3=>0,4=>0,5=>0); $H = array(1=>$P, 2=>$P, 3=>$P, 4=>$P, 5=>$P ); $k = 1; $P[$k] = key($G); $Circ = array(); #[Path Extension] EC2_Path_Extension: foreach($G[$P[$k]] as $j => $child ){ if( $child>$P[1] and in_array($child, $P)===false and in_array($child, $H[$P[$k]])===false ){ $k++; $P[$k] = $child; goto EC2_Path_Extension; } } #[EC3 Circuit Confirmation] if( in_array($P[1], $G[$P[$k]])===true ){//if PATH[1] is not child of PATH[current] then don't have a cycle $Circ[] = $P; } #[EC4 Vertex Closure] if($k===1){ goto EC5_Advance_Initial_Vertex; } //afou den ksana theoreitai einai asfales na svisoume for( $m=1; $m<=N; $m++){//H[P[k], m] <- O, m = 1, 2, . . . , N if( $H[$P[$k-1]][$m]===0 ){ $H[$P[$k-1]][$m]=$P[$k]; break(1); } } for( $m=1; $m<=N; $m++ ){//H[P[k], m] <- O, m = 1, 2, . . . , N $H[$P[$k]][$m]=0; } $P[$k]=0; $k--; goto EC2_Path_Extension; #[EC5 Advance Initial Vertex] EC5_Advance_Initial_Vertex: if($P[1] === N){ goto EC6_Terminate; } $P[1]++; $k=1; $H=array( 1=>array(1=>0,2=>0,3=>0,4=>0,5=>0), 2=>array(1=>0,2=>0,3=>0,4=>0,5=>0), 3=>array(1=>0,2=>0,3=>0,4=>0,5=>0), 4=>array(1=>0,2=>0,3=>0,4=>0,5=>0), 5=>array(1=>0,2=>0,3=>0,4=>0,5=>0) ); goto EC2_Path_Extension; #[EC5 Advance Initial Vertex] EC6_Terminate: print_r($Circ); ?>

allora questa è l’altra implementazione, più indipendente dal grafico, senza goto e senza valori di matrice, invece usa le chiavi dell’array, il percorso, il grafico e i circuiti sono memorizzati come chiavi di array (usa i valori dell’array se vuoi, basta cambiare la richiesta Linee). Il grafico di esempio inizia da -4 per mostrare la sua indipendenza.

 array(-4=>true,-3=>true,-2=>true), -3=>array(-4=>true,-3=>true,-2=>true), -2=>array(-4=>true,-3=>true,-2=>true) ); $C = array(); EC($G,$C); echo "
"; print_r($C); function EC($G, &$C){ $CNST_not_closed = false; // this flag indicates no closure $CNST_closed = true; // this flag indicates closure // define the state where there is no closures for some node $tmp_first_node = key($G); // first node = first key $tmp_last_node = $tmp_first_node-1+count($G); // last node = last key $CNST_closure_reset = array(); for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){ $CNST_closure_reset[$k] = $CNST_not_closed; } // define the state where there is no closure for all nodes for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){ $H[$k] = $CNST_closure_reset; // Key in the closure arrays represent nodes } unset($tmp_first_node); unset($tmp_last_node); # Start algorithm foreach($G as $init_node => $children){#[Jump to initial node set] #[Initial Node Set] $P = array(); // declare at starup, remove the old $init_node from path on loop $P[$init_node]=true; // the first key in P is always the new initial node $k=$init_node; // update the current node // On loop H[old_init_node] is not cleared cause is never checked again do{#Path 1,3,7,4 jump here to extend father 7 do{#Path from 1,3,8,5 became 2,4,8,5,6 jump here to extend child 6 $new_expansion = false; foreach( $G[$k] as $child => $foo ){#Consider each child of 7 or 6 if( $child>$init_node and isset($P[$child])===false and $H[$k][$child]===$CNST_not_closed ){ $P[$child]=true; // add this child to the path $k = $child; // update the current node $new_expansion=true;// set the flag for expanding the child of k break(1); // we are done, one child at a time } } }while(($new_expansion===true));// Do while a new child has been added to the path # If the first node is child of the last we have a circuit if( isset($G[$k][$init_node])===true ){ $C[] = $P; // Leaving this out of closure will catch loops to } # Closure if($k>$init_node){ //if k>init_node then alwaya count(P)>1, so proceed to closure $new_expansion=true; // $new_expansion is never true, set true to expand father of k unset($P[$k]); // remove k from path end($P); $k_father = key($P); // get father of k $H[$k_father][$k]=$CNST_closed; // mark k as closed $H[$k] = $CNST_closure_reset; // reset k closure $k = $k_father; // update k } } while($new_expansion===true);//if we don't wnter the if block m has the old k$k_father_old = $k; // Advance Initial Vertex Context }//foreach initial }//function ?>

Ho analizzato e documentato la CE, ma sfortunatamente la documentazione è in greco.

Mi sono imbattuto nel seguente algoritmo che sembra essere più efficiente dell’algoritmo di Johnson (almeno per i grafici più grandi). Tuttavia non sono sicuro delle sue prestazioni rispetto all’algoritmo di Tarjan.
Inoltre, ho controllato solo per i triangoli finora. Se interessati, vedere “Arboricity and Subgraph Listing Algorithms” di Norishige Chiba e Takao Nishizeki ( http://dx.doi.org/10.1137/0214017 )

non puoi fare una piccola funzione ricorsiva per attraversare i nodes?

 readDiGraph( string pathSoFar, Node x) { if(NoChildren) MasterList.add( pathsofar + Node.name ) ; foreach( child ) { readDiGraph( pathsofar + "->" + this.name, child) } } 

se hai una tonnellata di nodes, finirai per esaurire lo stack

Soluzione Javascript che utilizza elenchi collegati disgiunti. Può essere aggiornato per disgiungere le foreste impostate per tempi di esecuzione più rapidi.

 var input = '5\nYYNNN\nYYYNN\nNYYNN\nNNNYN\nNNNNY' console.log(input); //above solution should be 3 because the components are //{0,1,2}, because {0,1} and {1,2} therefore {0,1,2} //{3} //{4} //MIT license, authored by Ling Qing Meng //'4\nYYNN\nYYYN\nNYYN\nNNNY' //Read Input, preformatting var reformat = input.split(/\n/); var N = reformat[0]; var adjMatrix = []; for (var i = 1; i < reformat.length; i++) { adjMatrix.push(reformat[i]); } //for (each person x from 1 to N) CREATE-SET(x) var sets = []; for (var i = 0; i < N; i++) { var s = new LinkedList(); s.add(i); sets.push(s); } //populate friend potentials using combinatorics, then filters var people = []; var friends = []; for (var i = 0; i < N; i++) { people.push(i); } var potentialFriends = k_combinations(people,2); for (var i = 0; i < potentialFriends.length; i++){ if (isFriend(adjMatrix,potentialFriends[i]) === 'Y'){ friends.push(potentialFriends[i]); } } //for (each pair of friends (xy) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y) for (var i = 0; i < friends.length; i++) { var x = friends[i][0]; var y = friends[i][1]; if (FindSet(x) != FindSet(y)) { sets.push(MergeSet(x,y)); } } for (var i = 0; i < sets.length; i++) { //sets[i].traverse(); } console.log('How many distinct connected components?',sets.length); //Linked List data structures neccesary for above to work function Node(){ this.data = null; this.next = null; } function LinkedList(){ this.head = null; this.tail = null; this.size = 0; // Add node to the end this.add = function(data){ var node = new Node(); node.data = data; if (this.head == null){ this.head = node; this.tail = node; } else { this.tail.next = node; this.tail = node; } this.size++; }; this.contains = function(data) { if (this.head.data === data) return this; var next = this.head.next; while (next !== null) { if (next.data === data) { return this; } next = next.next; } return null; }; this.traverse = function() { var current = this.head; var toPrint = ''; while (current !== null) { //callback.call(this, current); put callback as an argument to top function toPrint += current.data.toString() + ' '; current = current.next; } console.log('list data: ',toPrint); } this.merge = function(list) { var current = this.head; var next = current.next; while (next !== null) { current = next; next = next.next; } current.next = list.head; this.size += list.size; return this; }; this.reverse = function() { if (this.head == null) return; if (this.head.next == null) return; var currentNode = this.head; var nextNode = this.head.next; var prevNode = this.head; this.head.next = null; while (nextNode != null) { currentNode = nextNode; nextNode = currentNode.next; currentNode.next = prevNode; prevNode = currentNode; } this.head = currentNode; return this; } } /** * GENERAL HELPER FUNCTIONS */ function FindSet(x) { for (var i = 0; i < sets.length; i++){ if (sets[i].contains(x) != null) { return sets[i].contains(x); } } return null; } function MergeSet(x,y) { var listA,listB; for (var i = 0; i < sets.length; i++){ if (sets[i].contains(x) != null) { listA = sets[i].contains(x); sets.splice(i,1); } } for (var i = 0; i < sets.length; i++) { if (sets[i].contains(y) != null) { listB = sets[i].contains(y); sets.splice(i,1); } } var res = MergeLists(listA,listB); return res; } function MergeLists(listA, listB) { var listC = new LinkedList(); listA.merge(listB); listC = listA; return listC; } //access matrix by i,j -> returns 'Y' or 'N' function isFriend(matrix, pair){ return matrix[pair[0]].charAt(pair[1]); } function k_combinations(set, k) { var i, j, combs, head, tailcombs; if (k > set.length || k <= 0) { return []; } if (k == set.length) { return [set]; } if (k == 1) { combs = []; for (i = 0; i < set.length; i++) { combs.push([set[i]]); } return combs; } // Assert {1 < k < set.length} combs = []; for (i = 0; i < set.length - k + 1; i++) { head = set.slice(i, i+1); tailcombs = k_combinations(set.slice(i + 1), k - 1); for (j = 0; j < tailcombs.length; j++) { combs.push(head.concat(tailcombs[j])); } } return combs; } 

DFS dal nodo di avvio s, tenere traccia del percorso DFS durante l’attraversamento e registrare il percorso se si trova un fronte dal nodo v nel percorso verso s. (v, s) è un back-edge nell’albero DFS e quindi indica un ciclo che contiene s.

Per quanto riguarda la tua domanda sul ciclo di permutazione , leggi qui: https://www.codechef.com/problems/PCYCLE

Puoi provare questo codice (inserisci la dimensione e il numero di cifre):

 # include using namespace std; int main() { int n; scanf("%d",&n); int num[1000]; int visited[1000]={0}; int vindex[2000]; for(int i=1;i<=n;i++) scanf("%d",&num[i]); int t_visited=0; int cycles=0; int start=0, index; while(t_visited < n) { for(int i=1;i<=n;i++) { if(visited[i]==0) { vindex[start]=i; visited[i]=1; t_visited++; index=start; break; } } while(true) { index++; vindex[index]=num[vindex[index-1]]; if(vindex[index]==vindex[start]) break; visited[vindex[index]]=1; t_visited++; } vindex[++index]=0; start=index+1; cycles++; } printf("%d\n",cycles,vindex[0]); for(int i=0;i<(n+2*cycles);i++) { if(vindex[i]==0) printf("\n"); else printf("%d ",vindex[i]); } } 

Le varianti basate su DFS con i bordi posteriori troveranno infatti dei cicli, ma in molti casi NON saranno cicli minimi . In generale DFS ti dà il flag che c’è un ciclo ma non è abbastanza buono per trovare effettivamente i cicli. Ad esempio, immagina 5 cicli diversi che condividono due bordi. Non esiste un modo semplice per identificare i cicli usando solo DFS (comprese le varianti di backtracking).

L’algoritmo di Johnson fornisce infatti tutti i cicli semplici e unici e ha una buona complessità di tempo e spazio.

Ma se vuoi trovare solo i cicli MINIMALI (il che significa che ci può essere più di un ciclo che attraversa qualsiasi vertice e siamo interessati a trovarne di minimi) E il tuo grafico non è molto grande, puoi provare a usare il semplice metodo qui sotto. È MOLTO semplice ma piuttosto lento rispetto a quello di Johnson.

Quindi, uno dei modi più semplici per trovare i cicli MINIMALI è usare l’algoritmo di Floyd per trovare percorsi minimi tra tutti i vertici usando la matrice di adiacenza. Questo algoritmo non è neanche lontanamente ottimale come quello di Johnson, ma è così semplice e il suo ciclo interno è talmente stretto che per i grafici più piccoli (<= 50-100 nodi) è assolutamente logico utilizzarlo. La complessità temporale è O (n ^ 3), la complessità dello spazio O (n ^ 2) se si utilizza il rilevamento genitore e O (1) se non lo si fa. Prima di tutto, troviamo la risposta alla domanda se c'è un ciclo. L'algoritmo è semplicissimo. Di seguito è riportato lo snippet in Scala.

  val NO_EDGE = Integer.MAX_VALUE / 2 def shortestPath(weights: Array[Array[Int]]) = { for (k <- weights.indices; i <- weights.indices; j <- weights.indices) { val throughK = weights(i)(k) + weights(k)(j) if (throughK < weights(i)(j)) { weights(i)(j) = throughK } } } 

Originariamente questo algoritmo opera su un grafico a bordo ponderato per trovare tutti i percorsi più brevi tra tutte le coppie di nodes (da qui l'argomento dei pesi). Affinché funzioni correttamente è necessario fornire 1 se esiste un margine diretto tra i nodes o NO_EDGE altrimenti. Dopo l'esecuzione dell'algoritmo, è ansible controllare la diagonale principale, se ci sono valori inferiori a NO_EDGE rispetto a questo nodo partecipa a un ciclo di lunghezza uguale al valore. Ogni altro nodo dello stesso ciclo avrà lo stesso valore (sulla diagonale principale).

Per ribuild il ciclo stesso, è necessario utilizzare una versione leggermente modificata dell'algoritmo con il monitoraggio principale.

  def shortestPath(weights: Array[Array[Int]], parents: Array[Array[Int]]) = { for (k <- weights.indices; i <- weights.indices; j <- weights.indices) { val throughK = weights(i)(k) + weights(k)(j) if (throughK < weights(i)(j)) { parents(i)(j) = k weights(i)(j) = throughK } } } 

La matrice dei genitori inizialmente dovrebbe contenere l'indice del vertice di origine in una cella di bordo se c'è un margine tra i vertici e -1 altrimenti. Dopo il ritorno della funzione, per ogni spigolo si farà riferimento al nodo genitore nell'albero del percorso più breve. E poi è facile recuperare i cicli effettivi.

Tutto sumto abbiamo il seguente programma per trovare tutti i cicli minimi

  val NO_EDGE = Integer.MAX_VALUE / 2; def shortestPathWithParentTracking( weights: Array[Array[Int]], parents: Array[Array[Int]]) = { for (k <- weights.indices; i <- weights.indices; j <- weights.indices) { val throughK = weights(i)(k) + weights(k)(j) if (throughK < weights(i)(j)) { parents(i)(j) = parents(i)(k) weights(i)(j) = throughK } } } def recoverCycles( cycleNodes: Seq[Int], parents: Array[Array[Int]]): Set[Seq[Int]] = { val res = new mutable.HashSet[Seq[Int]]() for (node <- cycleNodes) { var cycle = new mutable.ArrayBuffer[Int]() cycle += node var other = parents(node)(node) do { cycle += other other = parents(other)(node) } while(other != node) res += cycle.sorted } res.toSet } 

e un piccolo metodo principale solo per testare il risultato

  def main(args: Array[String]): Unit = { val n = 3 val weights = Array(Array(NO_EDGE, 1, NO_EDGE), Array(NO_EDGE, NO_EDGE, 1), Array(1, NO_EDGE, NO_EDGE)) val parents = Array(Array(-1, 1, -1), Array(-1, -1, 2), Array(0, -1, -1)) shortestPathWithParentTracking(weights, parents) val cycleNodes = parents.indices.filter(i => parents(i)(i) < NO_EDGE) val cycles: Set[Seq[Int]] = recoverCycles(cycleNodes, parents) println("The following minimal cycle found:") cycles.foreach(c => println(c.mkString)) println(s"Total: ${cycles.size} cycle found") } 

e l'output è

 The following minimal cycle found: 012 Total: 1 cycle found