Algoritmo per digrafo

[Javino89]

Salve forum. Allora io devo risolvere un problema:

Data la mia matricola (che sta in un array), devo verificare se nel digrafo (grafo diretto) esiste almeno un percorso che
attraversa nell'ordine tutti i vertici (Integer) con etichetta pari alle cifre della matricola.

Esempio:

se la matricola e' 1052001 il metodo restituisce true se esiste un percorso che attraversa esattamente i vertici 1,0,5,2,0,0,1
nello stesso ordine in cui compaiono nella matricola (percorrendo eventualmente piu' volte gli stessi archi del grafo se necessario).

Avevo pensato di calcolare tutti i percorsi possibili partendo dal vertice corrispondente alla cifra più significativa della
matricola (quella più a sinistra) ottenendo una lista di liste. Passare questa lista di liste ad un metodo ausiliario
assieme alla matricola e verificare se in questa lista di liste vi è una lista contenente la stessa identica sequenza
di vertici indicati dalla matricola.

Penso che di dovrebbe specializzare una dfs. Avete qualche idea?

Questo è il codice che ho scritto fino ad ora:

Classe Edge5R

public final class Edge5R {
    private final int destination;
    private final int source;

    public Edge5R(int source, int destination) {
        this.source = source;
        this.destination = destination;
    }

    @Override
    public String toString() {
        return "(" + source + "->" + destination + ")";
    }

    /**
     * vertice di destinazione
     *
     * @return
     */
    public int getDestination() {
        return destination;
    }

    /**
     * vertice sorgente
     *
     * @return
     */
    public int getSource() {
        return source;
    }
}

Classe che rappresenta il grafo

import java.util.*;

public class Graph5RImpl implements Graph5R
{
    private HashMap<Integer, List<Edge5R>> graph;

    public Graph5RImpl()
    {
        graph = new HashMap<Integer, List<Edge5R>>();
    }
    
    public boolean containsVertex(int vertex)
    {
        return this.graph.containsKey(vertex);
    }

    public Collection<Edge5R> edges()
    {
        Collection<Edge5R> ris = new ArrayList<Edge5R>();
        Collection<List<Edge5R>> values = graph.values();
        Iterator<List<Edge5R>> it = values.iterator();
        while(it.hasNext())
        {
            List<Edge5R> curr = it.next();
            ris.addAll(curr);
        }
        return ris;
    }

    public Edge5R getEdge(int source, int destination)
    {
        List<Edge5R> e = graph.get(source);
        if(e != null)
        {
            Iterator<Edge5R> it = e.iterator();
            while(it.hasNext())
            {
                Edge5R curr = it.next();
                if(curr.getDestination() == destination)
                {
                    return curr;
                }
            }
        }
        return null;
    }

    public void insertEdge(Edge5R edge)
    {
        int source = edge.getSource();
        int destination = edge.getDestination();
        List<Edge5R> esource = graph.get(source);
        if(esource == null)
        {
            esource = new LinkedList<Edge5R>();
            graph.put(source,esource);
        }
        esource.add(edge);
        List<Edge5R> edestination = graph.get(destination);
        if(edestination == null)
        {
            edestination = new LinkedList<Edge5R>();
            graph.put(destination, edestination);
        }
    }

    public void insertVertex(int v)
    {
        List<Edge5R> e = graph.get(v);
        if(e == null)
        {
            e = new LinkedList<Edge5R>();
            graph.put(v,e);
        }
    }

    public Collection<Edge5R> outEdges(int source)
    {
        List<Edge5R> e = graph.get(source);
        if(e != null)
        {
            return e;
        }
        else
            return new LinkedList<Edge5R>();
    }

    public Collection<Integer> outVertices(int source)
    {
        Collection<Integer> ris = new LinkedList<Integer>();
        List<Edge5R> e = graph.get(source);
        if(e != null)
        {
            Iterator<Edge5R> it = e.iterator();
            while(it.hasNext())
            {
                Edge5R curr = it.next();
                ris.add(curr.getDestination());
            }
            return ris;
        }
        return new LinkedList<Integer>();
    }

    public Collection<Integer> vertices()
    {
        Collection<Integer> ris = new HashSet<Integer>();
        Set<Integer> s = graph.keySet();
        if(s != null)
        {
            Iterator<Integer> it = s.iterator();
            while(it.hasNext())
            {
                Integer curr = it.next();
                ris.add(curr);
                ris.addAll(outVertices(curr));
            }
            return ris;
        }
        return new LinkedList<Integer>();
    }
}

Classe con altri metodi ausiliari di visita e creazione random del grafo

import java.util.*;

public class HomeworkR5Impl extends HomeworkR5
{
    public Graph5R createEmptyGraph()
    {
        Graph5R graph = new Graph5RImpl();
        return graph;
    }

    public Graph5R createRandomGraph(int n, int m)
    {
        Graph5R ris = new Graph5RImpl();
        for(int i = 0; i < n; i++)
        {
            if(!ris.containsVertex(i))
            {
                ris.insertVertex(i);
            }
        }
        Collection<Integer> vertices = ris.vertices();
        int[] v = new int[vertices.size()];
        int i = 0;
        Iterator<Integer> it = vertices.iterator();
        while(it.hasNext())
        {
            Integer curr = it.next();
            v[i] = curr;
            i++;
        }
        for(int j=0; j<m; j++)
        {
            int source = 0;
            int destination = 0;
            while(source == destination)
            {
                source = extremeRandom(v);
                destination = extremeRandom(v);
            }
            if(ris.getEdge(source, destination)==null)
            {
                Edge5R edge = new Edge5R(source,destination);
                ris.insertEdge(edge);
            }            
        }
        return ris;
    }

    private int extremeRandom(int[] v)
    {
        int dim = v.length;
        int pos = (int)Math.random()*dim;
        return v[pos];
    }

    public boolean existPathMatricola(Graph5R graph)
    {
        //Da completare, MI RIFERISCO A QUESTO METODO
    }

    public int[] matricola()
    {
        int[] ris = {1,2,5,7,2,3,0};
        return ris;
    }

    public Set<Integer> maxHop(Graph5R graph, int source, int maxHops)
    {
        //Da completare
    }
}

Ho omesso le interfacce..

Vi prego non ditermi che devo implementare il Floyd-Warshall ..

Ogni tanto aggiorno il post perché mi viene qualche idea..

Ho pensato che si potrebbe fare una DFS diretta partendo dal vertice S corrispondente dalla cifra della matricola più significativa. Da questo otterrei tutti i vertici raggiungibili da S. Ottenuti i vertici raggiungibili da S vado ad isolarmi i percorsi fra S e i vertici da esso raggiungibili e poi verificare se tra questi percorsi ce n'è uno che segue le cifre della matricola.. help mi sto intrippando un sacco xD

[Javino89]

Va bhe ho capito lasciamo perdere. Tanto è una scemenza. Devo seguire un percorso obbligato di vertici, non serve nessun algoritmo ricorsivo o specifico per grafi.