Strongly Connected Component

[Menthos]

Piccola richiesta al pubblico informatico in sala...

Visto che la maggior parte di voi ha sicuramente fatto (e presumo passato) un esame che riguarda l'algoritmica, volevo chiedervi se eravate in possesso di un algoritmo (preferibilmente in c++) che lavorasse sui grafi. In particolare mi servirebbe un algoritmo che dato un grafo mi dice tutte le componeti connesse presenti in esso...

"Dato un grafo diretto G=(V,E), una componente fortemente connessa (SCC, Strongly Connected Component) è un insieme massimale di vertici U sottoinsieme di V tale che per ogni coppia di vertici u e v in U, u è raggiungibile da v e viceversa."


Sperando in un aiutino da parte vostra (e dei vostri archivi), magari anche in pseudocodice, vi saluto cordialmente!

[Twins]

Piccola richiesta al pubblico informatico in sala...

Visto che la maggior parte di voi ha sicuramente fatto (e presumo passato) un esame che riguarda l'algoritmica, volevo chiedervi se eravate in possesso di un algoritmo (preferibilmente in c++) che lavorasse sui grafi. In particolare mi servirebbe un algoritmo che dato un grafo mi dice tutte le componeti connesse presenti in esso...

"Dato un grafo diretto G=(V,E), una componente fortemente connessa (SCC, Strongly Connected Component) è un insieme massimale di vertici U sottoinsieme di V tale che per ogni coppia di vertici u e v in U, u è raggiungibile da v e viceversa."


Sperando in un aiutino da parte vostra (e dei vostri archivi), magari anche in pseudocodice, vi saluto cordialmente!

domani con l'apertura degli uffici e con la conseguente necessità di cazzeggiare uno dei nostri top-nerd sarà a sua totale disposizione grazie ed arrivederci scherzi a parte credo che tanek marphil o sanvegeta dovrebbero poterti aiutare se nn leggono ora cercali via pm domani

[Tanek]

Ho paura di questo appellativo da "Top-nerd" (tra l'altro nell'altro 3d nei momenti in cui ho un po' di tempo sto scrivendo un reply chilometrico...)

Ad ogni modo, non mi ricordo molto di questo argomento, mi dispiace :/ (ad essere sinceri non ricordo nemmeno in che esame le ho fatte queste cose, forse Ricerca Operativa quando l'avevo seguita al VO, boh)

[Axet]

Piccola richiesta al pubblico informatico in sala...
Visto che la maggior parte di voi ha sicuramente fatto (e presumo passato) un esame che riguarda l'algoritmica, volevo chiedervi se eravate in possesso di un algoritmo (preferibilmente in c++) che lavorasse sui grafi. In particolare mi servirebbe un algoritmo che dato un grafo mi dice tutte le componeti connesse presenti in esso...
"Dato un grafo diretto G=(V,E), una componente fortemente connessa (SCC, Strongly Connected Component) è un insieme massimale di vertici U sottoinsieme di V tale che per ogni coppia di vertici u e v in U, u è raggiungibile da v e viceversa."
Sperando in un aiutino da parte vostra (e dei vostri archivi), magari anche in pseudocodice, vi saluto cordialmente!

Chiarisci meglio:
1) cosa intendi con componente connessa, perchè usi una notazione ambigua (vedi sotto)?
2) attenzione perchè usi due termini PESANTEMENTE differenti. Componente connessa e componente FORTEMENTE connessa sono due cose diverse. Vuol dire che il grafo su cui lavori è diverso: nel primo caso si parla di un grafo generico nel secondo di un grafo ORIENTATO.
Da come la poni, seppur erroneamente, pare che tu voglia contare le componenti connesse all'interno di un grafo, il che può anche essere visto come il contare il numero di alberi all'interno di una foresta.
Per fare questo esiste la DFS (depth-first search) anche se poi la devi lievemente modificare per inserire un miserissimo contatore, di cui non riesco a trovare una buona implementazione in pseudocodice (quella di wiki fa merda). Prova a cercare ^^

edit:
provando a scrivere di mia mano lo pseudocodice..

DFS(V)
cont = 0
for each vert € V do
{
if colour(vert) == white
{
cont++
colour(vert) == gray
DFS-VISIT(vert)
}
colour(vert) = black
}
return(cont)


Come funziona? Ad ogni nodo vi è associato un colore: bianco se ancora non è stato esplorato, grigio se sta venendo esplorato e nero se è stato completamente esplorato.
La funzione più esterna, DFS, fa scorrere tutti i vertici appartenenti al grafo. Quando ne trova uno bianco (cioè subito all'inizio e poi dipende da se ci sono o meno componenti sconnesse) fa partire la DFS-VISIT (che non ti scrivo ma è una banalissima funzione di ricerca in profondita con la peculiarità di cmq associare un colore ad ogni nodo che scopre).
Quando la dfs visit ha finito, si torna al livello superiore e il programma continua a iterare in questa maniera.
Se il grafo è connesso allora il valore ritornato sarà 1, perchè la dfs selezionerà un nodo all'interno del grafo e la dfs-visit lo esplorerà tutto (ricerca in profondità -> esplora il grafo) marchiando quindi ogni nodo come visitato. Quando poi la DFS andrà a cercare per altri nodi "white" non ne troverà.

Se invece il grafo è sconnesso, dopo la prima e pressochè obbligatoria iterazione con la DFS-VISIT, la suddetta verrà "lanciata" dalla DFS tante volte quante sono le componenti connesse all'interno del grafo sconnesso.
In sintesi, quanti sono gli alberi all'interno della foresta (tanto parlare di alberi o grafi è uguale in questo caso, gli alberi sono dei grafi con date restrizioni).

riedit:
la procedura l'ho scritta io a mano in 2 minuti mentre sto aspettando che la mia morosa faccia un orale, magari c'è qualche errorino anche se non mi pare, cmq il concetto di fondo è quello.
Ora implementala ^O^

[Axet]

domani con l'apertura degli uffici e con la conseguente necessità di cazzeggiare uno dei nostri top-nerd sarà a sua totale disposizione grazie ed arrivederci scherzi a parte credo che tanek marphil o sanvegeta dovrebbero poterti aiutare se nn leggono ora cercali via pm domani

Ma che deve fare marphil che è ing gestionale

[Twins]

Ma che deve fare marphil che è ing gestionale

La ringraziamo per la segnalazione,di contro il suo nominativo è stato inserito nell'archivio grazie ed arrivederci

[San Vegeta]

io sinceramente non ne ho... se dovessi implementarlo mi basterebbe avere la definizione e magari un caso di esempio, però se lo faccio lo faccio lunedì al work... oggi m'è toccato prendere un giorno di ferie perchè mi ammalo sempre di venerdì ed è un po' figura di merda mettersi in malattia al venerdì... quindi 0 programmazione oggi :/

pseudocodice qui

http://en.wikipedia.org/wiki/Tarjan%...ents_algorithm [Tarjan's Algorithm]

esistono diverse implementazioni in java, magari trovi del codice sorgente in giro jung è una di queste, non so se è compilata o codice sorgente

[Hador]

axet che lo ha fatto da poco se lo ricorda sicuramente più di me, cmq ho il tomo di algoritmi a casa se non hai risolto da solo (con la dfs) poi lo cerco e te lo posto.
Data la definizione sta cercando le componenti fortemente connesse, in ogni caso anche se sta roba la puoi in teoria fare solo sugli orientati vale anche per i non orientati (o viceversa, ma sono sicuro).

cmq cercati Kosaraju, Tarjan e Gabow. Gli ultimi 2 dovrebbero essere meglio. Se sei in palla sta sera evoco il 400 pagine di "elementi di algoritmi", elementi proprio
Implementazioni strane o inventate faranno cmq cagare, a meno che tu non sia un genio dell'algoritmica vege

la procedura l'ho scritta io a mano in 2 minuti mentre sto aspettando che la mia morosa faccia un orale

suona malissimo lo sai?

[Axet]

axet che lo ha fatto da poco se lo ricorda sicuramente più di me, cmq ho il tomo di algoritmi a casa se non hai risolto da solo (con la dfs) poi lo cerco e te lo posto.
Data la definizione sta cercando le componenti fortemente connesse, in ogni caso anche se sta roba la puoi in teoria fare solo sugli orientati vale anche per i non orientati (o viceversa, ma sono sicuro).
cmq cercati Kosaraju, Tarjan e Gabow. Gli ultimi 2 dovrebbero essere meglio. Se sei in palla sta sera evoco il 400 pagine di "elementi di algoritmi", elementi proprio

Si ma dipende che deve fare. Se deve contare le componenti CONNESSE all'interno di un grafo (che poi ovviamente può a sua volta essere connesso cioè con un numero totale di componenti connesse pari a 1, ovviamente dipendente dalla struttura del grafo stesso) allora la DFS con la mini-modifica del contatore è perfetta.

Se deve contare le componenti fortemente connesse all'interno di un grafo allora va bene l'algoritmo postato da vege (nota: che io manco conoscevo, non l'abbiamo affrontato al corso, ma a leggere lo pseudocodice e la descrizione è perfetto per il compito).

Il fatto che lui nella descrizione iniziale ha usato indipendentemente due termini, che definiscono cose differenti, per indicare la stessa cosa.. quindi è un "filo" ambiguo

Implementazioni strane o inventate faranno cmq cagare, a meno che tu non sia un genio dell'algoritmica vege

Del resto la complessità computazionale non esiste mica a caso ^^

suona malissimo lo sai?

[Menthos]

Chiarisci meglio:
1) cosa intendi con componente connessa, perchè usi una notazione ambigua (vedi sotto)?
2) attenzione perchè usi due termini PESANTEMENTE differenti. Componente connessa e componente FORTEMENTE connessa sono due cose diverse. Vuol dire che il grafo su cui lavori è diverso: nel primo caso si parla di un grafo generico nel secondo di un grafo ORIENTATO.
Da come la poni, seppur erroneamente, pare che tu voglia contare le componenti connesse all'interno di un grafo, il che può anche essere visto come il contare il numero di alberi all'interno di una foresta.
Per fare questo esiste la DFS (depth-first search) anche se poi la devi lievemente modificare per inserire un miserissimo contatore, di cui non riesco a trovare una buona implementazione in pseudocodice (quella di wiki fa merda). Prova a cercare ^^

edit:
provando a scrivere di mia mano lo pseudocodice..

DFS(V)
cont = 0
for each vert € V do
{
if colour(vert) == white
{
cont++
colour(vert) == gray
DFS-VISIT(vert)
}
colour(vert) = black
}
return(cont)


Come funziona? Ad ogni nodo vi è associato un colore: bianco se ancora non è stato esplorato, grigio se sta venendo esplorato e nero se è stato completamente esplorato.
La funzione più esterna, DFS, fa scorrere tutti i vertici appartenenti al grafo. Quando ne trova uno bianco (cioè subito all'inizio e poi dipende da se ci sono o meno componenti sconnesse) fa partire la DFS-VISIT (che non ti scrivo ma è una banalissima funzione di ricerca in profondita con la peculiarità di cmq associare un colore ad ogni nodo che scopre).
Quando la dfs visit ha finito, si torna al livello superiore e il programma continua a iterare in questa maniera.
Se il grafo è connesso allora il valore ritornato sarà 1, perchè la dfs selezionerà un nodo all'interno del grafo e la dfs-visit lo esplorerà tutto (ricerca in profondità -> esplora il grafo) marchiando quindi ogni nodo come visitato. Quando poi la DFS andrà a cercare per altri nodi "white" non ne troverà.

Se invece il grafo è sconnesso, dopo la prima e pressochè obbligatoria iterazione con la DFS-VISIT, la suddetta verrà "lanciata" dalla DFS tante volte quante sono le componenti connesse all'interno del grafo sconnesso.
In sintesi, quanti sono gli alberi all'interno della foresta (tanto parlare di alberi o grafi è uguale in questo caso, gli alberi sono dei grafi con date restrizioni).

riedit:
la procedura l'ho scritta io a mano in 2 minuti mentre sto aspettando che la mia morosa faccia un orale, magari c'è qualche errorino anche se non mi pare, cmq il concetto di fondo è quello.
Ora implementala ^O^

Il grafo è FORTEMENTE connesso, quindi è un grafo orientato. Per componente fortemente connessa all'interno di un grafo intendo quelle componenti che creano un ciclo. Chiaramente una semplice DFS (quindi ricerca in profondità) non basta, il procedimento sarebbe questo:

1 -Chiamare DFS(G) per computare f[v] (l’ordine finale di visita) per ogni vertice v
2 -Calcolare il grafo trasposto G’ di G
3- Chiamare DFS(G’), ma nel ciclo principale della DFS e si considerino i vertici in ordine decrescente di f[v]
4- Restituire i vertici di ciascun albero calcolato con la DFS(G’) come una SCC (STRONGLY connected component)


C'è anche un modo per farlo con i colori, inventato da un simpaticone di nome Tarjan... però avrei voluto uno pseudocodice di questo particolare metodo. No problem!

[Alkabar]

Scusate, cosi' a leggerlo sembra che lui voglia trovare il sottografo di un grafo orientato in cui i vertici sono completamente connessi, cioe' da ogni vertice puo' arrivare a un altro del sotto gravo e viceversa.

Do una occhiata in giro, ma non penso sia il depth first. Mi viene in mente solo un algoritmo atroce, ma prima guardo in giro aspe.

[Alkabar]

Il grafo è FORTEMENTE connesso, quindi è un grafo orientato. Per componente fortemente connessa all'interno di un grafo intendo quelle componenti che creano un ciclo. Chiaramente una semplice DFS (quindi ricerca in profondità) non basta, il procedimento sarebbe questo:
1 -Chiamare DFS(G) per computare f[v] (l’ordine finale di visita) per ogni vertice v
2 -Calcolare il grafo trasposto G’ di G
3- Chiamare DFS(G’), ma nel ciclo principale della DFS e si considerino i vertici in ordine decrescente di f[v]
4- Restituire i vertici di ciascun albero calcolato con la DFS(G’) come una SCC (STRONGLY connected component)
C'è anche un modo per farlo con i colori, inventato da un simpaticone di nome Tarjan... però avrei voluto uno pseudocodice di questo particolare metodo. No problem!

Ah ecco. Non ci guardo nemmeno, non ho voglia di cagare mattoni.

[Axet]

Il grafo è FORTEMENTE connesso, quindi è un grafo orientato. Per componente fortemente connessa all'interno di un grafo intendo quelle componenti che creano un ciclo. Chiaramente una semplice DFS (quindi ricerca in profondità) non basta, il procedimento sarebbe questo:
1 -Chiamare DFS(G) per computare f[v] (l’ordine finale di visita) per ogni vertice v
2 -Calcolare il grafo trasposto G’ di G
3- Chiamare DFS(G’), ma nel ciclo principale della DFS e si considerino i vertici in ordine decrescente di f[v]
4- Restituire i vertici di ciascun albero calcolato con la DFS(G’) come una SCC (STRONGLY connected component)
C'è anche un modo per farlo con i colori, inventato da un simpaticone di nome Tarjan... però avrei voluto uno pseudocodice di questo particolare metodo. No problem!

Vabbè se il problema è formalizzato così è ovvio che la soluzione che ti ho dato non va bene, il fatto è che come l'avevi spiegato all'inizio si capiva tutto e niente

Quello che chiedi qua è decisamente più complesso.. troppo sbatta

edit:
che poi.. non conosco nel dettaglio l'algoritmo di tarjan, ma guardando così ad occhio non mi sembra abbia un'elevata complessità computazionale.
Per farlo come dici tu il costo invece è decisamente maggiore.. a che pro quindi?

[Hador]

introduzione agli algoritmi e alle strutture dati della mcgraw hill, vero menthos?
dovrei leggermi il capitolo e buttarlo giu, ma dato che lo ho fatto 2 anni fa e che è da stamattina che mi sparo lambda calcolo mi sa che lo faccio fare a te

axet si capiva sei tu che nn hai capito na mazza, a vedere se è connesso ci vuole nulla

[Axet]

axet si capiva sei tu che nn hai capito na mazza, a vedere se è connesso ci vuole nulla

Non mi pareva così scontato dal primo reply eh t_t
Inoltre non ci vuole nulla se uno lo sa fare, se uno non sa come fare non è detto.. ho visto gente che si tagliava le vene per cose molto più semplici