Newsgroup: it.comp.lang.c
Titolo: ALgo sui grafi e percorsi

Ho un grafo orientato con archi pesati.
Vorrei avere in output TUTTI i possibili percorsi da un nodo A ad un nodo B
del grafo.
Conosco le due visite BFS e DFS, ma la prima mi da in output solo il
percorso minimo da A a B, mentre la DFS mi da un percorso qualunque da A a B
ma non tutti.
Avete suggerimenti o consigli?
Grazie

 del grafo.
Allora.
Mi sembra piu' una domanda da it...informatica,
visto che quello che ti serve prima di tutto e'
un algoritmo e solo secondariamente una implementazione.
Comunque.
Il fatto che gli archi siano pesati e' chiaramente ininfluente,
visto che vuoi tutti i cammini, mantre
e' importante il fatto che gli archi siano diretti.
La cosa e' piuttosto semplice da fare ricorsivamente,
ma c'e' una cosa che non e' chiara:
tutti i cammini posssibili potrebbero essere infiniti,
se non specifichi altre condizioni: se nel grafo
c'e' un ciclo potrei percorrerlo un numero arbitrario
di volte prima di arrivare a B.
Chiaramente bisogna imporre qualche limitazione.
Le due piu' immediate sono:
che un cammino
1) non  puo' passare due volte dallo stesso arco
2) non  puo' passare due volte dallo stesso nodo
quale/quali di queste due condizioni vuoi soddisfare ?
non e' la stessa cosa.
ciao,
g.

 non e' la stessa cosa.
In realtà ho semplificato di molto la cosa. Ci sono dei vincoli legati al
peso degli archi.
Non posso imporre nessuna delle due condizioni indicate da te altrimenti
escludere alcuni percorsi.
Ad esempio:
                                             A
                                          /       \
                                      B            C
                                         \         /
                                             D
                                              |
                                             E
Vorrei in output sia A,B,D,E che A,C,D,E
Imponendo le tue condizioni ne perderei uno.
Suggerimenti?

 Suggerimenti?
se a D aggiungi un collegamento ad A gli archi pero' diventano infiniti..
avresti A,B,D,E - A,B,D,A,B,D,E - A,B,D,A,B,D,A,B,D,E ecc.
devi avere qualche condizione...

 ha scritto nel messaggio
news:AjWcc.36898$rM4.1...@news4.tin.it...

Come dicevo ho una condizione da verificare al passaggio su ogni arco.
Scusa, ma nel grafo non c'e' l'arco da E ad A !!!!!
Diciamo che ho un certo budget ed al passaggio su ogni arco il budget viene
incrementato oppure decrementato e la condizione è di trovare tutti i
percorsi tra A ed E che mantengano il budget al di sopra di un certo valoro
in ogni istante.
Ciao

 in ogni istante.
urka! ma quindi le condizioni del grafo cambiano ad ogni passaggio ??
mi pare un po' complicatuccio...

 ha scritto nel messaggio
news:bjXcc.25996$hc5.1...@news3.tin.it...

No. Facciamo una cosa. Ti riscrivo il problema.
Problema
Vi sono N città collegate da m strade. Un commerciante di tè, con la propria
auto, parte da una città ci e deve arrivare ad una città cj. Durante il
viaggio, ad ogni città ck, il commerciante:
  a.. guadagna una quantità di denaro pari a tk;
  b.. spende una quantità di denaro pari a ak per mangiare e pernottare in
un albergo;
Inoltre, su ogni strada da un città ck ad una citta cm:
  a.. paga un pedaggio pkm
  b.. spende una quantità di denaro pari a dkm per la manutenzione
dell'auto.
Supposto che il commerciante inizialmente abbia una somma di denaro pari a
C, si vuole sapere se esistono e quali sono i percorsi che può fare in modo
che, in ogni momento del viaggio, tale somma sia sempre maggiore di una
quantità T.
----------------------------------------------------------------------------
----
Si supponga che tutte le informazioni siano in due file. Nel primo ci sono
le informazioni rigurdanti la somma C, la quantità T e le città nel formato:
C T <città-i> <città-j>
.
.
<città-k>  tk ak
.
.
Nel secondo file ci sono le informazioni riguardanti i collegamenti tra le
città nel seguente formato:
.
.
<città-k> <città-m> pkm dkm
.
.
Inoltre si è pensato di accorpare i costi ed i guadagna in una unica
informazione da disporre sugli archi uscenti.Ecco quanto.Grazie

 Imponendo le tue condizioni ne perderei uno.
No. non hai letto bene quello che ho scritto.
Io ho detto che le condizioni si applicano ad ogni
cammino, non all'insieme dei cammini.
Quindi, anche imponendo entrambe le condizioni
(cioe' non ripassare due volte dallo stesso arco,
o dallo stesso nodo)
si otterrebbero entrambe le due soluzioni di cui sopra,
perche' singolarmente nessuna viola le condizioni.
Ho letto sommariamente il problema nella sua
interezza. Che e' ben diverso da quello
che avevi proposto. Continuo a pensare che
sei nel gruppo sbagliato, perche' qui
il C c'entra poco.
In ogni caso qualche osservazione
1) intanto accorpiamo le informazioni:
ad ogni citta' sara' associato un valore
bk = tk-ak che e' quello
che complessivamente guadagna o perde passando
dalla citta'.
Inoltre ad ogni arco sara' associato un costo
sk = pkm+dkm
che indica quanto costa percorrere l'arco.
In realta' il problema e' leggermente ambiguo perche'
non specifica esattamente la sequenza delle incidenze
dei costi e ricavi sul budget del venditore.
Cioe' possiamo supporre che lui possa percorrere un
arco di costo sk solo se il suo budget attuale e'
maggiore di sk (indipendentemente da quanto guadagnera'
nella citta' raggiunta). Cosi' come possiamo supporre
che l'albergo lui lo paghi alla fine e non all'inizio
della giornata (quindi che possa arrivare in una citta'
anche se non ha soldi per pagare l'albergo, purche' sia
preventivato un guadagno per quella citta' tale da permettere
il pagamento.
Comunque quello che dicevo prima a proposito delle
condizioni da imporre per evitare possibili
soluzioni "infinite" e' sempre valido.
Se il grafo e' tale che il bilancio per ogni nodo
e' negativo (cioe' ci perde sempre) allora e'
chiaro che le soluzioni possibili sono finite.
Se invece il grafo contiene un ciclo che percorso
mi da un bilancio positivo allora, se non impongo
ulteriori condizioni, ci possono essere infinite soluzioni
di lunghezza arbitraria.
considera per esempio quattro citta':
A,B,C,D.  Con soli 4 archi:
A->B, B->C, C->B, C->D.
e devo andare da A a D.
La soluzione consiste in A->B->C->D.
Se pero', ad esempio, l'arco B->C e l'arco
C->B mi costano 10 ma nelle citta' B e C guadagno,
ad esempio, 15 e 7, cioe' complessivamente 22 > 20,
allora ho infinite soluzioni :
A->B->C->D,  A->B->C->B->C->D, etc.etc.
Per questo dicevo che bisogna imporre qualche tipo
di vincolo, o sapere a priori che non esistono
cicli con bilancio positivo (cosa che mi sembra
improbabile).
Quindi, secondo me, il problema va corredato di qualche
vincolo aggiuntivo.
O, come dicevo, il fatto che ogni SINGOLO cammino non
possa ripassare dalla stessa citta' o dalla stessa strada,
oppure imporre un vincolo sulla lunghezza del cammino
(cioe' imporre un tempo massimo entro il quale il venditore
vuole arrivare a destinazione).
Imponendo uno o piu' di questi vincoli il problema
ammette un numero finito di soluzioni.
Una alternativa piu' sofisticata (ma credo che esuli
da questo esercizietto di informatica) consisterebbe
nell'implementare un meccanismo per riconoscere
l'esistenza di cicli a bilancio positivo e
fermarsi segnalandoli.
Comunque, non imponendo vincoli (o imponendo un vincolo
sulla lunghezza massima del cammino) il problema
si risolve comunque con una paginetta di codice.
Quindi
Prima soluzione, senza imporre vincoli
sul fatto di ripassare dallo stesso arco o citta'
-------------------------------------------------
Supponiamo di dover andare da A a Z con budget BU.
Scrivi una routine ricorsiva alla quale passi
una citta' X (la citta' dove sei appena stato),
un cammino L
(il cammino da A a X, tipicamente una lista di nodi o di archi)
il budget attuale B
La routine fa la seguente cosa:
1) se X==Z allora ho raggiunto la destinazione.
invoco una funzione Output(L,B) che in qualche
modo stampa o memorizza la soluzione corrente,
costituita dal L (un cammino da A a Z) e dai soldi
che mi sono rimasti (B).
Return.
2) (qui X!=Z)
Controllo se la lunghezza del cammino L e' maggiore
del limite imposto. Se e' cosi' ritorno senza
far nulla.
3) PER OGNI strada E che esce da X e porta a Y.
se la strada E ha un costo tale che la posso percorrere,
e se la citta' Y nella quale arrivo ha un bilancio
tale che la posso attraversare,
allora:
a) aggiungo Y al cammino L.
b) invoco me stessa con il nuovo cammino L e il
budged modificato in base a E e Y
c) al ritorno della chiamata ricorsiva tolgo Y da L
(molto importante!).
return.
Questa piu' o meno e' la struttura.
Se per esempio vuoi imporre di non passare 2 volte
dalla stessa citta', allora puoi controllare se Y
e' gia' contenuta in L.
La routine ricorsiva andra' invocata la prima
volta passandogli il nodo iniziale A, il budged iniziale
e una L che puo' essere vuota (se in L memorizzi gli archi)
o contenere A (se in L memorizzi la sequenza dei nodi).
Quale struttura dati usare per implementare L dipende
dai tuoi gusti. Tieni conto che e' una struttura
che viene modificata solo in fondo (aggiunte, cancellazioni).
ciao,
g.

è normale che la dfs non percorra tutto il grafo!
è cosi che funziona.
hai bisogno di richiamarla piu volte per esempio:
void chiama_dfs(NODO *Grafo,int num_vet)
{
int i=0;
/* Fase di inizializzazione */
for (;i < num_vet;i++)
      Grafo[i].color=WHITE;
/*ogni volta che dfs termina cerchi di nuovo
il primo non visitato e fai iniziare la visita da questo*/
for (i=0;i < num_vet;i++)
      if (Grafo[i].color == WHITE)
        {
// se il colore del vertice è white non è stato ancora visitato
           count=1;
           index[num_life].punt=&Grafo[i];
           dfs(Grafo,&Grafo[i],num_life,&count);
        }
}