[Java] Cammini tra due nodi

[Giobbo]

Ciao a tutti.
Vado subito al punto. Ho un grafo rappresentato come segue:
public class Grafo {

private HashMap<Nodo, HashSet<Arco>>

...

}

dove la chiave dell'HashMap è il nodo e il valore è l'insieme degli archi che lo toccano.
Ora, io dovrei, dati due nodi, trovare tutti i percorsi che li uniscono che differiscano per almeno un arco.
Francamente, non so da che parte cominciare per implementare la soluzione.

Concettualmente, la mia idea sarebbe questa: lo potrei implementare come una visita in profondità, ma a differenza di quella "classica" mi pare di poter dire che non posso usare la colorazione dei nodi per capire dove sono già passato, visto che ogni volta che sono su un nodo e considero un diverso arco uscente, sto creando un potenziale nuovo cammino.
Perciò ciascuno di questi cammini dovrà avere una propria "memoria" su quali nodi sono stati già visitati.

Per cui ogni volta che prendo in considerazione un nuovo arco, dovrei passare il cammino corrente fino al genitore (sotto forma di lista di nodi). Inoltre dovrei creare un duplicato della lista per ciascun nuovo nodo in cui arrivo. In questo modo da questa lista il nuovo nodo guarderà per capire cosa è stato già visitato e cosa no, e la aggiornerà aggiungendovi il prossimo arco visitato.

Ulteriormente, mi viene in mente un'altra differenza con la visita in profondità tradizionale. Infatti, raggiunto il nodo traguardo T non mi devo fermare: ogni volta che lo tocco, dovrei salvare il cammino corrente (che è quello dato dal nodo precedente più ovviamente il nodo traguardo) in una lista di soluzioni, cioè di cammini tra P e T, proseguendo con la visita come se niente fosse. Mi fermerei quando non ci sono più archi visitabili.

Credo che questa soluzione concettuale potrebbe andare bene (o sbaglio?), ma il mio problema è: come la implemento?
Ovviamente serve una funzione ricorsiva. Ma mi trovo bloccato ad applicarla alla mia struttura dati.

Ringrazio già ora chiunque abbia la pazienza e la voglia per darmi un aiuto o anche solo qualche suggerimento.

[sottovento]

Hai gia' dato un'occhiata all'algoritmo di Dijkstra?
http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra

EDIT - scusa, ho riletto il tuo testo piu' attentamente.
Viene spontanea una domanda: sei sicuro che esista una soluzione? Sai gia' che il problema e' NP completo, ma magari puoi tentare una soluzione nel caso il numero di nodi rimanga limitato. Ma con le ipotesi che hai fatto e' comunque difficile.

[Giobbo]

Hai gia' dato un'occhiata all'algoritmo di Dijkstra?
http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra

EDIT - scusa, ho riletto il tuo testo piu' attentamente.
Viene spontanea una domanda: sei sicuro che esista una soluzione? Sai gia' che il problema e' NP completo, ma magari puoi tentare una soluzione nel caso il numero di nodi rimanga limitato. Ma con le ipotesi che hai fatto e' comunque difficile.


Purtroppo, come ti sei accorto tu stesso, Dijkstra non è utilizzabile nel mio caso.
Oramai per finire l'esercizio mi mancano solamente due metodi da implementare:

- percorso di minima durata tra due nodi dati, questo risolvibile sì con l'algoritmo di Dijkstra

- trovare tutti i percorsi tra due nodi dati, che è il problema che ho esposto sopra. Con questo veramente non so che pesci prendere. Se l'esercizio lo richiede presumo che possa essere fatto in qualche modo.

[sottovento]

- trovare tutti i percorsi tra due nodi dati, che è il problema che ho esposto sopra. Con questo veramente non so che pesci prendere. Se l'esercizio lo richiede presumo che possa essere fatto in qualche modo.

Scusami, stavo per pubblicarti qualche elucubrazione quando ho visto questo link:
http://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes

Prova a darci un'occhiata, se fa al caso tuo....

[Giobbo]

Sbattendoci la testa, alla fine ho trovato una soluzione. La metto per completezza.
Non so quanto sia effettivamente "elegante", ma fa quello che deve fare


private void trovaPercorsi(LinkedList<Tratta> visitati, String arr) {
Tratta t = visitati.getLast();
String v = t.getArrivo();
LinkedList<Tratta> fermate_vic = this.fermateColl(v);
// esamino le fermate vicine
for (Tratta fer : fermate_vic) {
if (contieneFermata(visitati, fer)) {
continue;
}
if (fer.getArrivo().equals(arr)) {
visitati.add(fer);
stampaPercorso(visitati);
visitati.removeLast();
break;
}
}
for (Tratta fer : fermate_vic) {
if (contieneFermata(visitati, fer) || fer.getArrivo().equals(arr)) {
continue;
}
visitati.addLast(fer);
trovaPercorsi(visitati, arr, percorso, flag);
visitati.removeLast();
}
}

dove:
- la LinkedList visitati contiene i nodi (o meglio, le tratte visitate, da cui poi ricavo i nodi) fino a quel momento visitati. Alla prima chiamata del metodo, essa contiene solamente il nodo di partenza.
- la stringa arr contiene il nome del nodo di arrivo
- il metodo fermateColl restituisce la lista dei nodi collegati al nodo che chiama il metodo.
- il metodo contieneFermata restituisce true se la lista contiene il nodo specificato (entrambe passate come argomenti)
- il metodo stampaPercorso chiaramente stampa il contenuto della lista visitati, che non contiene altro che una serie di nodi da quello di partenza a quello di arrivo

[Giobbo]

Devo chiedere nuovamente aiuto.
Risolto il problema precedente, devo ora trovare il cammino minimo tra due nodi dati.
Tale problema è risolvibile con l'algoritmo di Dijkstra, e fino a qui ci sono.
Devo però applicarlo al mio grafo, che è definito tramite la struttura dati:


HashMap<String, HashSet<Archi>>

dove String è il nome del mio nodo.
Mi trovo un po' spaesato perché tutti gli esempi che ho trovato utilizzano i numeri per identificare i nodi e tramite questi popolano in modo corretto i due set (o liste) relative alla distanza e al nodo precedente nel cammino.
Come posso fare? Utilizzare due ulteriori HashMap<String, Integer> e HashMap<String, String> per le due strutture di supporto può essere una soluzione?

EDIT: ho provato a buttare giù qualcosa.
Ecco il codice che ho scritto:

public void percorsoBreve(String par, String arr) {
Set<String> fermate = this.collegamenti.keySet();
Iterator it = fermate.iterator();
HashMap<String, Integer> distanza = new HashMap<>();
HashMap<String, String> precedente = new HashMap<>();
String fer;
LinkedList<Tratta> fermate_vic;
int supp;
while(it.hasNext()) {
fer = (String) it.next();
System.out.println("Alle due hashmap aggiungo la fermata " + fer);
distanza.put(fer, Integer.MAX_VALUE-1);
precedente.put(fer, null);
}

distanza.put(par, 0);
int alt;
int dis;
String s;
while(!fermate.isEmpty()) {
fer = distanzaPiuBreve(distanza, fermate);
System.out.println("Sto iterando sulla fermata " + fer);
fermate.remove(fer);
supp = distanza.get(fer);
if (fer.equals(arr))
break;
if (supp == Integer.MAX_VALUE-1)
break;
System.out.println("Copio le tratte di " + fer);
fermate_vic = this.fermateColl(fer);
for (Tratta t : fermate_vic) {
dis = t.getLunghezza();
s = t.getArrivo();
alt = supp + dis;
if (alt < distanza.get(s)) {
distanza.put(s, alt);
precedente.put(s, fer);
}
}
}
stampaPercorsoBreve(precedente, arr);
}

Il metodo distanzaPiuBreve cerca nel Set fermate la fermata avente la distanza minore associata ed è così definito:

private String distanzaPiuBreve(HashMap<String, Integer> distanza,
Set<String> fermate) {
Iterator it = fermate.iterator();
String s;
String minore = null;
int min = -1;
int c;
while (it.hasNext()) {
s = (String) it.next();
c = distanza.get(s);
if (min == -1) {
min = c;
minore = s;
}
else {
if (c<min) {
min = c;
minore = s;
}
}
}
return minore;
}

Mentre il metodo stampaPercorsoBreve ha il compito di stampare il percorso trovato ed è così definito:

private void stampaPercorsoBreve(HashMap<String, String> precedente,
String arr) {
String s;
Stack<String> output = new Stack<>();
s = precedente.get(arr);
while (s!=null) {
output.add(s);
s = precedente.get(s);
}
for (int i=output.size(); i>0; i--) {
s = output.remove(i);
s = ", ";
}
System.out.println(s);
}

Ora, quando utilizzo il metodo fermateColl (che mi restituisce l'insieme degli archi collegati al nodo che passo come argomento) mi viene lanciata un'eccezione NullPointerException.
E la cosa avrebbe senso. Se non che il medesimo metodo utilizzato in maniera assolutamente identica funziona perfettamente e correttamente quando lo invoco nell'altro meccanismo di ricerca di tutti i percorsi (quello del messaggio precedente, per intenderci).
Come è possibile? A me pare assurdo e francamente incomprensibile.
Per curiosità ho provato a lanciare i due diversi metodi (ricerca di tutti i percorsi e ricerca del percorso più breve) nella medesima esecuzione, e (mi ripeto, assurdamente) il metodo funziona normalmente nel primo caso mentre nel secondo mi lancia l'errore.
Al momento sono un po' avvilito...

Per completezza, vi posto il testo del metodo in questione:

private LinkedList<Tratta> fermateColl(String f) {
HashSet<Tratta> tratte = this.collegamenti.get(f);
LinkedList<Tratta> fermate_vic = new LinkedList<>();
Iterator iterator = tratte.iterator();
Tratta tratta;
while(iterator.hasNext()) {
tratta = (Tratta) iterator.next();
fermate_vic.add(tratta);
}
return fermate_vic;
}