Calcolo componenti biconesse
Buonasera,
Devo creare un programma che dato in input un grafo (in realtà l'input è un file che descrive il grafo ma non è come realizzare il grafo il problema) restituisca il numero di componenti connesse, biconesse e di nodi di taglio. Per calcolare le componenti connesse, pensavo di utilizzare una struttura union-find (inizialmente make su ogni nodo per creare dei "singoletti" contenenti il solo nodo, procedendo poi con le union fino a formare le componenti connesse... Ovviamente inizializzando anche una variabile al numero di nodi e decrementandola ogni volta che eseguo una union per tenere traccia facilmente del numero di componenti). Non saprei però come procedere per il calcolo delle componenti biconnesse (per i nodi di taglio immagino basti per ogni componente biconessa eliminare "a turno" un nodo e verificare se la componente è ancora connessa... Ma immagino anche sia possibile farlo in modo più efficiente XD). Qualcuno può aiutarmi?
Devo creare un programma che dato in input un grafo (in realtà l'input è un file che descrive il grafo ma non è come realizzare il grafo il problema) restituisca il numero di componenti connesse, biconesse e di nodi di taglio. Per calcolare le componenti connesse, pensavo di utilizzare una struttura union-find (inizialmente make su ogni nodo per creare dei "singoletti" contenenti il solo nodo, procedendo poi con le union fino a formare le componenti connesse... Ovviamente inizializzando anche una variabile al numero di nodi e decrementandola ogni volta che eseguo una union per tenere traccia facilmente del numero di componenti). Non saprei però come procedere per il calcolo delle componenti biconnesse (per i nodi di taglio immagino basti per ogni componente biconessa eliminare "a turno" un nodo e verificare se la componente è ancora connessa... Ma immagino anche sia possibile farlo in modo più efficiente XD). Qualcuno può aiutarmi?
Risposte
Ciao,
- componenti connesse: basta una visita DFS (oppure di specializzi una DFS-scheme)
- componenti biconnesse dovrebbe essere quelle fortemente connesse (sbaglio?): utilizzi quello che è chiamato DFS-scheme secondo l'algoritmo di Kosaraju
- nodi di taglio: iteri la DFS-scheme togliendo di volta in volta un nodo e vedi quante componenti connesse si creano.
la union-find è per risolvere le componenti connesse incrementali è un problema simile. Ma con un solo algoritmo strutturato come visite DFS risolvi ogni cosa
- componenti connesse: basta una visita DFS (oppure di specializzi una DFS-scheme)
- componenti biconnesse dovrebbe essere quelle fortemente connesse (sbaglio?): utilizzi quello che è chiamato DFS-scheme secondo l'algoritmo di Kosaraju
- nodi di taglio: iteri la DFS-scheme togliendo di volta in volta un nodo e vedi quante componenti connesse si creano.
la union-find è per risolvere le componenti connesse incrementali è un problema simile. Ma con un solo algoritmo strutturato come visite DFS risolvi ogni cosa
Io pensavo di utilizzare l'union-find perchè anche se mi interessa solo il numero di componenti connesse la ricerca dei nodi di taglio va fatta a partire da queste... Se poi mi dici che se ne può fare a meno meglio XD (mi basta una DFS in cui incremento un contatore ogni volta che chiama DFS-Visit in modo non ricorsivo).
Le componenti biconnesse non sono quelle fortemente connesse... Le fortemente connesse, se non erro, sono le classi di equivalenza rispetto alla mutua raggiungibilità dei nodi, mentre le biconesse sono quei sottografi massimali connessi per i quali se tolgo un nodo il grafo rimane ancora connesso. In pratica sono i sottografi che in questa immagine qui hanno lo stesso colore
Mentre i nodi con più di un colore sono i nodi di taglio.
Intanto grazie per la risposta
Le componenti biconnesse non sono quelle fortemente connesse... Le fortemente connesse, se non erro, sono le classi di equivalenza rispetto alla mutua raggiungibilità dei nodi, mentre le biconesse sono quei sottografi massimali connessi per i quali se tolgo un nodo il grafo rimane ancora connesso. In pratica sono i sottografi che in questa immagine qui hanno lo stesso colore
Mentre i nodi con più di un colore sono i nodi di taglio.
Intanto grazie per la risposta
L'utilizzo delle union-find è ben corretto per risolvere il problema di sapere le componenti connesse. Anche per gli altri due problemi puoi utilizzare lo stesso principio di iterazione eliminando i nodi e vedere quante componenti si creano.
Tieni conto che i nodi di taglio è una diretta implicazione del porblema di biconessione (io chiamo questo tipo di connettività: 2-connessione), i nodi che creano sconnessione (perciò biconnessione) sono i nodi di taglio.
Il mio era un consiglio, puoi utilizzare ciò che preferisci
La union-find è fin troppo per questo problema visto che non ti serve memorizzare nulla.
Tieni conto che la complessità computazionale sarà identica in entrambi i casi (tranne per le costanti...) perciò $O(|V|+|E|)$ per le componenti connesse.
Direi che per nodi di taglio o componenti biconnesse la complessità sia tipo $O(|V|(|V|+|E|))$ cioè per ogni nodo fai una visita. Ma secondo me si può tenere sulla stessa complessità di una visita DFS classica, utilizzando bene un DFS-scheme.
Per union-find i ragionamenti sono simili.
Tieni conto che i nodi di taglio è una diretta implicazione del porblema di biconessione (io chiamo questo tipo di connettività: 2-connessione), i nodi che creano sconnessione (perciò biconnessione) sono i nodi di taglio.
Il mio era un consiglio, puoi utilizzare ciò che preferisci
La union-find è fin troppo per questo problema visto che non ti serve memorizzare nulla.
Tieni conto che la complessità computazionale sarà identica in entrambi i casi (tranne per le costanti...) perciò $O(|V|+|E|)$ per le componenti connesse.
Direi che per nodi di taglio o componenti biconnesse la complessità sia tipo $O(|V|(|V|+|E|))$ cioè per ogni nodo fai una visita. Ma secondo me si può tenere sulla stessa complessità di una visita DFS classica, utilizzando bene un DFS-scheme.
Per union-find i ragionamenti sono simili.
Il mio era un consiglio, puoi utilizzare ciò che preferisci
La union-find è fin troppo per questo problema visto che non ti serve memorizzare nulla.
Mi hai convinto mi ero fatto un'idea sbagliata io XD ero abbastanza sicuro che fosse necessario anche sapere come sono fatte le componenti connesse. Visto che non serve è molto più semplice usare la DFS (anche perchè devo implementare da solo le strutture dati che uso senza usare cose offerte dal linguaggio di programmazione).
In sostanza da quanto ho capito per calcolare i nodi di taglio mi consigli di applicare la definizione... Ovvero elimino a turno tutti i nodi e vedo se si formano nuove componenti connesse (ho capito male?). Mentre per trovare le componenti biconesse?
La pagina di wikipedia inglese (da cui sembra presa quell'immagine - ma se hai usato quella italiana inizia a dare SEMPRE un'occhiata a quella inglese che è meglio) fornisce diversi algoritmi per il calcolo di queste componenti biconnesse.. Le idee principali sono comunque quelle già uscite nella discussione, BFS o union-find..
Non so se ho capito bene l'algoritmo... In pratica eseguo una DFS normale memorizzando per ogni vertice la sua profondità e quello che chiama lowpoint (la profondità più bassa tra quelle dei vicini dei suoi discendenti). Non ho capito cosa intende per profondità più bassa (non capisco se "più basso" si riferisce al valore numerico della profondità o alla profondità stessa... cioè vuole il massimo o il minimo?) e sopratutto cosa intende per vicini (basta che mi limito al sottoalbero radicato sotto il nodo o devo cercare anche in quello radicato sul nodo "fratello"?). Sopratutto non ho nemmeno idea di come dimostrare la correttezza dell'algoritmo (purtroppo devo dimostrare la correttezza di tutto quello che utilizzo e il prof ha avuto la brillante idea di non spiegare durante il corso nulla sulle componenti i-connesse o sui nodi di taglio...).
In ogni caso penso di potermi calcolare componenti connesse e biconnesse nella stessa visita mentre per i nodi di taglio devo per forza eseguire del lavoro a parte... O forse non ho capito assolutamente nulla XD
In ogni caso penso di potermi calcolare componenti connesse e biconnesse nella stessa visita mentre per i nodi di taglio devo per forza eseguire del lavoro a parte... O forse non ho capito assolutamente nulla XD
In fondo alla pagina di wikipedia ci sono i riferimenti agli articoli in cui gli algoritmi sono stati presentati per la prima volta (articoli che trovi facilmente con google..). Ti consiglio di leggere da lì. Volendo è anche possibile cercare la soluzione al problema 22-2 del libro di introduzione agli algoritmi di Cormen et al.
Ho trovato un flowchart dell'algoritmo che mi hai indicato tu ma continuo a non capirci comunque molto... Sopratutto perchè poi devo anche dimostrarne la correttezza.
Ps: perdona l'insistenza XD
Ps: perdona l'insistenza XD
"apatriarca":
BFS o union-find..
forse è un refuso di una D, ma con delle BFS mi pare non sia possibile trovare le componenti connesse, se non visitando più volte il grafo da nodi radice differenti.
I miei sono suggerimenti su cui partire, poi appoggio il consiglio di apatriarca: Google is your Friend!
soprattutto su problemi discussi in ogni dove.
Comunque per i problemi se non sono ancora chiari, basandomi su qualche variante DFS:
- componenti connesse sono UNA visita.
- biconnessione sono più ricorsioni (visite) da nodi differenti, se vedi che la componente non è sconnessa dopo aver tolto il nodo selezionato, hai trovato una componente biconnessa.
- nodi di taglio è il problema complementare della biconnessione, il nodo che rende sconnessa la componente è un nodo di taglio.
Quindi operativamente dovrei procedere cosi (se ho capito bene)
Lancio una DFS per scoprire il numero di componenti connesse;
Per ogni nodo del grafo:
Lancio una DFS per scoprire il numero di componenti connesse;
Per ogni nodo del grafo:
- rimuovo il nodo;
se rimuovendo il nodo cambia il numero di componenti connesse, questo è un nodo di taglio;
se non cambia allora fa parte di una componente biconessa (?);[/list:u:2i23v5n1]
Restituisco i risultati
Non mi è ancora chiaro però come riconoscere una componente biconessa... Se eliminando un nodo non cambia il numero di componenti connesse non è automatico che faccia parte di una componente biconessa.
Sì.. BFS era un refuso.. Intendevo dire DFS. Ma in ogni caso mi riferivo all'algoritmo descritto abbastanza male su wikipedia. Algoritmo che scopro per la prima volta e che quindi devo un po' studiarmi per poter essere di aiuto.. Qualche idea ce l'ho, ma prima di scrivere qualcosa cerco di informarmi un po' di più.
Ti suggerisco qualche piccolo esercizio per guidarti nella comprensione di quell'algoritmo sulla pagina di wikipedia.
Per prima cosa ci vuole una nuova definizione: una componente biconnessa è un sottografo massimale di \(G\) tale che ogni sua coppia di archi è contenuta in un ciclo semplice comune. Ti invito a provare che le due definizioni sono equivalenti.
Ti invito quindi a scegliere un nodo casuale come radice dell'algoritmo DFS. A questo punto considera due archi qualsiasi che partono da questa radice. Dimostra che la radice è un nodo di taglio se e solo se ha almeno due archi nell'albero depth-first risultante. Suggerimento: se il nodo e tutti i suoi figli fossero contenuti in una componente biconnessa (cioè se il nodo non fosse di taglio) allora, per ogni coppia di archi uscenti da esso, ci sarebbe un ciclo semplice che li contiene entrambi.
A questo punto considera un nodo qualsiasi dell'albero ottenuto applicando l'algoritmo DFS. Il nodo è di taglio se e solo se esiste un percorso che collega un suo figlio ad un suo ascendente. Hint: utilizza come prima il fatto che l'arco che lo collega al nodo genitore e l'arco che lo collega al nodo figlio dovrebbero far parte di un ciclo semplice.
A questo punto, per ogni nodo, definisci il valore \(v.low\) come al grado minore raggiungibile proseguendo con l'algoritmo DFS a partire da \(v\). Se per un nodo \(v\), \(v.low >= \deg v\), allora ti trovi con un nodo di taglio. Hint: vedi caso precedente.
A questo punto ti trovi con l'algoritmo di wikipedia e ad una sua dimostrazione..
Per prima cosa ci vuole una nuova definizione: una componente biconnessa è un sottografo massimale di \(G\) tale che ogni sua coppia di archi è contenuta in un ciclo semplice comune. Ti invito a provare che le due definizioni sono equivalenti.
Ti invito quindi a scegliere un nodo casuale come radice dell'algoritmo DFS. A questo punto considera due archi qualsiasi che partono da questa radice. Dimostra che la radice è un nodo di taglio se e solo se ha almeno due archi nell'albero depth-first risultante. Suggerimento: se il nodo e tutti i suoi figli fossero contenuti in una componente biconnessa (cioè se il nodo non fosse di taglio) allora, per ogni coppia di archi uscenti da esso, ci sarebbe un ciclo semplice che li contiene entrambi.
A questo punto considera un nodo qualsiasi dell'albero ottenuto applicando l'algoritmo DFS. Il nodo è di taglio se e solo se esiste un percorso che collega un suo figlio ad un suo ascendente. Hint: utilizza come prima il fatto che l'arco che lo collega al nodo genitore e l'arco che lo collega al nodo figlio dovrebbero far parte di un ciclo semplice.
A questo punto, per ogni nodo, definisci il valore \(v.low\) come al grado minore raggiungibile proseguendo con l'algoritmo DFS a partire da \(v\). Se per un nodo \(v\), \(v.low >= \deg v\), allora ti trovi con un nodo di taglio. Hint: vedi caso precedente.
A questo punto ti trovi con l'algoritmo di wikipedia e ad una sua dimostrazione..
Grazie per le spiegazioni!
Rileggendo un po' il mio post mi sono accorto di alcuni possibili errori/inesattezze. Non ho però tempo di controllarle bene. Ti consiglio quindi di controllarle confrontandole con wikipedia e, se ce l'hai, con il libro di algoritmi di Cormen. Ci darò poi un'occhiata meglio anche io più tardi.
A quanto pare non posso usare questa soluzione perchè la consegna la esclude (il testo completo è uscito ieri e non avevo ancora guardato...). Però potrei sempre sfruttare il fatto che una componente biconnessa è contenuta in un ciclo (o sbaglio?).
"apatriarca":
A questo punto considera un nodo qualsiasi dell'albero ottenuto applicando l'algoritmo DFS. Il nodo è di taglio se e solo se esiste un percorso che collega un suo figlio ad un suo ascendente. Hint: utilizza come prima il fatto che l'arco che lo collega al nodo genitore e l'arco che lo collega al nodo figlio dovrebbero far parte di un ciclo semplice.
secondo me è più chiaro sottolineare la struttura dell'albero di copertura dfs. Un nodo $N$ è di taglio ssse il
sottoalbero di uno dei suoi fi gli non ha archi verso un predecessore di N. Ma direi comunque che le definizioni collidono.
Non ho approfondito la versione scritta in wiki:
ma il lowbound non si riferisce al livello dell'albero, perciò alla distanza dalla radice (nodo) considerata?
A quanto pare non posso usare questa soluzione perchè la consegna la esclude (il testo completo è uscito ieri e non avevo ancora guardato...).
a quale soluzione ti riferisci, a quella basata su più DFS, quella utilizzata dal apatriarca-Comen->wiki...
a quale soluzione ti riferisci, a quella basata su più DFS, quella utilizzata dal apatriarca-Comen->wiki...
A quella che è "spiegata" su wikipedia. Infatti ero orientato ad utilizzare quella basata su più dfs... Solo che non riesco a capire ancora come contare le componenti biconesse a partire da DFS.
La mia idea è:
1 - Conto il numero di componenti connesse (usando DFS modificata in modo che prima di chiamare DFS-Visit incrementi un contatore);
2 - Per ogni nodo:
- rimuovo il nodo;
conto il numero di componenti connesse;
se il numero cambia è un nodo di taglio;
se non cambia fa parte di una componente biconnessa;
reinserisco il nodo;[/list:u:um76tkwq]
Solo che appunto non ho ancora capito come contare il numero di componenti biconesse
Per curiosità, come mai non puoi utilizzare quell'algoritmo? Che cosa dice il testo dell'esercizio?
Forse proprio perché mi occupo di topologia algebrica e i cicli hanno una così grande importanza, credo che la definizione data in precedenza porti ad algoritmi in generale migliori. La seguente è un abbozzo di idea che devo ancora ben rifinire..
1. Calcolare le componenti connesse e i cicli semplici del grafo usando l'algoritmo DFS.
2. Se due cicli hanno almeno due nodi in comune, appartengono alla stessa componente biconnessa. Unendo i cicli in questo modo credo possa essere possibile ottenere quasi tutte le componenti biconnesse. Dovrebbero rimanerci fuori solo le componenti biconnesse composte da coppie di nodi collegate da un arco.
3. I nodi di taglio sono a questo punto i nodi che appartengono a più di una componente biconnessa.
Che cosa ne pensate di questo abbozzo? Ho l'impressione che l'unione dei cicli si possa in qualche modo tentare già durante la visita DFS, ma non mi vengono in mente grosse idee (probabilmente finirebbe per diventare uguale all'algoritmo che non puoi usare in effetti...).
Forse proprio perché mi occupo di topologia algebrica e i cicli hanno una così grande importanza, credo che la definizione data in precedenza porti ad algoritmi in generale migliori. La seguente è un abbozzo di idea che devo ancora ben rifinire..
1. Calcolare le componenti connesse e i cicli semplici del grafo usando l'algoritmo DFS.
2. Se due cicli hanno almeno due nodi in comune, appartengono alla stessa componente biconnessa. Unendo i cicli in questo modo credo possa essere possibile ottenere quasi tutte le componenti biconnesse. Dovrebbero rimanerci fuori solo le componenti biconnesse composte da coppie di nodi collegate da un arco.
3. I nodi di taglio sono a questo punto i nodi che appartengono a più di una componente biconnessa.
Che cosa ne pensate di questo abbozzo? Ho l'impressione che l'unione dei cicli si possa in qualche modo tentare già durante la visita DFS, ma non mi vengono in mente grosse idee (probabilmente finirebbe per diventare uguale all'algoritmo che non puoi usare in effetti...).
Questa volta non è più un abbozzo. Esattamente come le componenti connesse sono le classi di equivalenza secondo la relazione che lega due punti se esiste un percorso nel grafo che li lega, le componente biconnesse sono le classi di equivalenza secondo la relazione che lega due archi se questi sono contenuti nello stesso ciclo. Un possibile algoritmo potrebbe essere quindi quello di "fondere" l'algoritmo per la ricerca di cicli con quello di calcolare le classi di equivalenza di una relazione (usando la solita disjoint set data structure). Per esempio possiamo applicare l'algoritmo DFS e unire le classi di equivalenza di tutti gli archi che si trovano in un ciclo comune. Per la complessità stessa dei due algoritmi, questo algoritmo è lineare. Con qualche piccola modifica dovrebbe essere possibile anche trovare i nodi di taglio (per esempio memorizzando per ogni nodo il primo arco uscente facente parte di un ciclo).
Per curiosità, come mai non puoi utilizzare quell'algoritmo? Che cosa dice il testo dell'esercizio?
Nella consegna c'era scritto di non utilizzare l'algoritmo di Tarjan... Però questa mattina ne abbiamo parlato col professore e ha deciso che invece possiamo utilizzarlo (in sostanza era convinto che lo avessimo visto a lezione mentre in realtà abbiamo soltanto parlato di componenti fortemente connesse... Quindi ha cambiato idea) a patto che facciamo una dimostrazione completa. A questo punto credo proprio che utilizzerò quell'algoritmo li
per caso sai dove posso trovarne una spiegazione più approfondita? Voglio capirlo per bene (sopratutto perchè devo dimostrarlo...)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo