[Algoritmo] Tutti i percorsi da un punto a un altro

[Alhazred]

Ho bisogno di un algoritmo che dati due nodi di un grafo orientato e con archi pesati, mi trovi tutti i percorsi dal primo nodo al secondo nodo e il peso totale di ogni percorso.

Quale algoritmo dovrei usare?
Stavo pensando a Dijkstra, ma serve a trovare il percorso più breve, non tutti i percorsi esistenti.

[Alhazred]

Aggiungo che il grafo ha dei cicli e i percorsi che li contengono non devono essere presi in considerazione.

[Alhazred]

Sono riuscito a scrivere una funzione che mi trova tutti i percorsi (stampandoli dalla funzione ci sono tutti), ma ho un problema nel restituirli.
Li metto in una variabile di tipo Set (avevo anche provato con ArrayList), ma quando vado a ciclare sul risultato restituto pare ci sia solo un nodo in ogni percorso, quindi è in realtà un non-percorso.
Non capisco se sbaglio a ciclare sul risultato o se sbaglio l'inserimento del percorso trovato nel Set.

Qui vi propongo il codice della classe che crea il grafo ed effettua la ricerca

import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Set;

public class GraphUtil {

    private Set<LinkedList<Vertex<String>>> bfs(Graph<String,Integer> g,
                                                LinkedList<Vertex<String>> visited,
                                                Set<LinkedList<Vertex<String>>> paths,
                                                Vertex<String> destination) {

        //vertici raggiungibili dal vertice corrente
        Collection<Vertex<String>> nodes = g.outVertices(visited.getLast());
        // esamina i vertici adiacenti
        for (Vertex<String> node : nodes) {
            if (visited.contains(node)) { //se il vertice corrente è già stato visitiato
                continue;
            }
            if (node.equals(destination)) { //se il vertice corrente è quello di destinazione
                visited.add(node);

                //inserisci la lista di vertici visited nella lista dei percorsi
                paths.add(visited);

                System.out.print("Percorso: ");
                for(Vertex<String> nodo : visited) {
                    System.out.print(nodo.getElement()); //stampa tutti i vertici del percorso trovato
                }
                System.out.println();
                System.out.println("Visited size: " + visited.size()); //numero di vertici nel percorso
                System.out.println();
                visited.removeLast();
                break;
            }
        }
        //ricorsione per la BFS
        for (Vertex<String> node : nodes) { //per tutti i vertici raggiungibili da quello corrente
            if (visited.contains(node) || node.equals(destination)) { //se è già stato visitato o se è quello cercato
                continue;
            }
            visited.addLast(node); //segna il vertice come visitato
            bfs(g, visited, paths, destination); //chiamo ricorsivamente la funzione bfs
            visited.removeLast(); //rimuovo l'ultimo vertice visitato
        }

        return paths; //ritorno i percorsi trovati
    }

    public static void main(String[] args) {
        Graph<String, Integer> gra = new Graph<String, Integer>();

        //creo i vertici
        Vertex<String> a = new Vertex<String>("a");
        Vertex<String> b = new Vertex<String>("b");
        Vertex<String> c = new Vertex<String>("c");
        Vertex<String> d = new Vertex<String>("d");
        Vertex<String> e = new Vertex<String>("e");
        Vertex<String> f = new Vertex<String>("f");

        //li inserisco nel grafo
        gra.insertVertex(a);
        gra.insertVertex(b);
        gra.insertVertex(c);
        gra.insertVertex(d);
        gra.insertVertex(e);
        gra.insertVertex(f);

        //inserisco nel grafo gli archi che congiungono i vertici
        gra.insertEdge(new Edge<String,Integer>(new Integer(2), "Linea 1", a, b));
        gra.insertEdge(new Edge<String,Integer>(new Integer(2), "Linea 1", b, a));
        gra.insertEdge(new Edge<String,Integer>(new Integer(1), "Linea 2", a, c));
        gra.insertEdge(new Edge<String,Integer>(new Integer(1), "Linea 2", c, a));
        gra.insertEdge(new Edge<String,Integer>(new Integer(5), "Linea 3", a, d));
        gra.insertEdge(new Edge<String,Integer>(new Integer(5), "Linea 3", d, a));
        gra.insertEdge(new Edge<String,Integer>(new Integer(2), "Linea 1", b, c));
        gra.insertEdge(new Edge<String,Integer>(new Integer(2), "Linea 1", c, b));
        gra.insertEdge(new Edge<String,Integer>(new Integer(3), "Linea 2", c, d));
        gra.insertEdge(new Edge<String,Integer>(new Integer(3), "Linea 2", d, c));
        gra.insertEdge(new Edge<String,Integer>(new Integer(1), "Linea 1", c, e));
        gra.insertEdge(new Edge<String,Integer>(new Integer(1), "Linea 1", e, c));
        gra.insertEdge(new Edge<String,Integer>(new Integer(1), "Linea 2", d, e));
        gra.insertEdge(new Edge<String,Integer>(new Integer(1), "Linea 2", e, d));
        gra.insertEdge(new Edge<String,Integer>(new Integer(5), "Linea 3", d, f));
        gra.insertEdge(new Edge<String,Integer>(new Integer(5), "Linea 3", f, d));
        gra.insertEdge(new Edge<String,Integer>(new Integer(2), "Linea 2", e, f));
        gra.insertEdge(new Edge<String,Integer>(new Integer(2), "Linea 2", f, e));

        Set<LinkedList<Vertex<String>>> percorsi = new HashSet<LinkedList<Vertex<String>>>();

        //collezione che conterrà i vertici visitati
        LinkedList<Vertex<String>> visited = new LinkedList<Vertex<String>>();
        visited.add(b); //aggiungo ai vertici visitati il vertice da cui iniziare la partenza

        //avvio la ricerca, e è il vertice di destinazione
        Set<LinkedList<Vertex<String>>> paths = new GraphUtil().bfs(gra, visited, percorsi, e);

        if(paths.size() > 0) { //se è stato trovato almeno un percorso
            Iterator<LinkedList<Vertex<String>>> lli = paths.iterator();
            while(lli.hasNext()) { //cicla su tutti i percorsi trovati
                LinkedList<Vertex<String>> path = lli.next(); //path dovrebbe contenere uno dei percorsi per ogni ciclo
                Iterator<Vertex<String>> li = path.iterator();
                Vertex<String> v1 = null;
                Vertex<String> v2 = null;
                int pesoTot = 0;

                System.out.println("Path size: " + path.size()); //stampa sempre 1

                if(path.size() > 1) { // se ci sono almeno 2 vertici nel percorso
                    v1 = li.next(); //vertice di partenza

                    while(li.hasNext()) {
                        v2 = li.next(); //sertice di arrivo

                        Edge<String,Integer> edge = gra.getEdge(v1,v2); //arco che conginge v1 e v2
                        System.out.println("From: " + v1.getElement().toString() + " - To: " + v2.getElement().toString()  + " - Through line: " + edge.getLine() );
                        pesoTot += edge.getWeight();

                        v1 = v2; //nuovo vertice di partenza
                    }
                    System.out.println("Peso totale: " + pesoTot);
                    System.out.println("------------------------------------");
                }
            }
        }
        else {
            System.out.println("nessun percorso");
        }
    }
}

Se volete il codice completo con tutte le classi (4) in modo da poterlo anche provare, l'ho messo qui in un file zip.

Cosa c'è che non va? Cosa sbaglio?

[wingman87]

Non ho letto approfonditamente però mi sembra che nel set inserisci sempre lo stesso oggetto (in momenti diversi ma si tratta sempre dello stesso oggetto)

[Alhazred]

Subito dopo l'inserimento nel Set stampo l'oggetto visited proprio per controllare questa cosa, ma mi stampa percorsi diversi, non sempre lo stesso, quindi dovrebbe essere a posto.

[wingman87]

Sì ma se non sbaglio (e non mi stupirebbe) l'oggetto visited è sempre lo stesso, solo che nel corso del programma il suo contenuto cambia

[Alhazred]

Allora non riesco proprio a capire perché

//questo dovrebbe assegnare sempre la stessa cosa a paths
paths.add(visited);

//mentre questo che è subito dopo stampa correttamente i diversi percorsi
System.out.print("Percorso: ");
for(Vertex<String> nodo : visited) {
    System.out.print(nodo.getElement()); //stampa tutti i vertici del percorso trovato
}

[wingman87]

Il motivo è abbastanza semplice: l'oggetto a cui si riferisce visited è sempre lo stesso (una lista), il suo contenuto invece cambia nel corso dell'algoritmo.
Per fare un esempio: tu inserisci in visited diversi nodi, finché non giungi a destinazione, e a quel punto inserisci visited in paths. Dopodiché rimuovi alcuni nodi da visited e ne inserisci altri (perché provi altri percorsi) e quando giungi nuovamente a destinazione lo reinserisci in paths. Ma l'oggetto che stai inserendo è in realtà lo stesso di prima solo che il suo contenuto è cambiato.

[Alhazred]

Ah, forse ho capito cosa intendi.
Quindi quando faccio
paths.add(visited)
non viene aggiunto un nuovo percorso, ma sovrascritto quello messo al giro precedente?

Se così fosse, come faccio ad inserire percorsi deversi dentro a paths?

[wingman87]

non viene aggiunto un nuovo percorso, ma sovrascritto quello messo al giro precedente?

In verità non accade proprio questo... Quello che succede è che nel set è già presente lo stesso oggetto visited che stai tentando di inserire, quindi non succede nulla.

Stasera se posso magari ti spiego in modo più esauriente, se non l'avrà già fatto qualcun altro

Per risolvere velocemente sostituirei:

paths.add(visited);

con

paths.add((LinkedList<Vertex<String>>)visited.clone());

Che in questo caso non credo dovrebbe crearti problemi.
Forse ci sono soluzioni migliori, però al momento non ho tempo di analizzare bene il codice per pensare a qualcosa di meglio.

[Alhazred]

Si, quella modifica mi ha risolto il problema.
Comunque se avessi tempo per una spiegazione mi interesserebbe.

[wingman87]

Per spiegare meglio però prendo un esempio più semplice:

List<String> nameList = new ArrayList<String>();
Set<List<String>> nameListsSet = new HashSet<List<String>>;
nameList.add("Michele");
nameList.add("Marta");
nameListsSet.add(nameList);

Cosa fa il metodo add? Si salva da qualche parte il riferimento nameList aggiungendolo al set (che al momento è vuoto)

nameList.add("Stefano");
nameList.add("Paola");
nameListsSet.add(nameList);

Cosa fa il metodo add? Controlla che nameListsSet non contenga un altro oggetto uguale a quello che sto inserendo (ricordiamoci che è un set).
Ma cosa contiene nameListsSet? Un riferimento a nameList, quindi proprio lo stesso oggetto (non solo uguale, ma proprio lo stesso) che sto cercando di inserire.
Visto che nameListsSet contiene già un oggetto uguale, il metodo add non fa nulla.

Come ulteriore conferma, prova il seguente codice:

List<String> nameList = new ArrayList<String>();
Set<List<String>> nameListsSet = new HashSet<List<String>>;
nameList.add("Michele");
nameList.add("Marta");
nameListsSet.add(nameList);
nameList.add("Stefano");
nameList.add("Paola");
for(List<String> names : nameListsSet){
	System.out.println("Inizio Lista");
	for(String name : names){
		System.out.println("\t" + name);
	}
	System.out.println("Fine Lista");
}

Anche se non ho reinserito nameList dopo aver aggiunto altri nomi, il set risulta contenerli lo stesso, questo perché il set contiene solo il riferimento alla lista. Quindi se tramite quello stesso riferimento effettuo ulteriori modifiche alla lista (nell'esempio le righe in verde), queste si constateranno in tutti i luoghi in cui quel riferimento viene usato (nell'esempio anche dentro al set).

[Alhazred]

Capito, ti ringrazio.