Salve ragazzi!
Avrei bisogno di un vostro parere circa l'implementazione di un metodo che prende in input un grafo, 2 vertici e un intero e restituisce vero se esiste un cammino dal primo al secondo vertice di lunghezza k..
Io l'ho implementato così ma qualcosa a quanto pare non va!
il codice è
Codice:
public class TestGraph {

static final Object COLOR= new Object();
static final Object RED= new Object();

/** metodo che consente di stabilire se esiste un cammino (con tutti i vertici distinti)
di lunghezza k che connette u e v.*/
public static<V,E> boolean path(Graph<V,E> G, Vertex<V> u, Vertex<V> v, int k)
{
if (k==0)
{
if (u == v)
return true;
else return false;
}
u.put(COLOR, RED);//colora il vertice u di rosso
Iterable<Edge<E>> incidentEdges = G.incidentEdges(u); // restituisce una collezione iterabile dei vertici adiacenti a u
for (Edge<E> arco: incidentEdges)
{
Vertex<V> w = G.opposite(u, arco);//restiuisce l'arco adiacente a u
if (w == v)
return true;
if (w.get(COLOR) != RED) //se il vertice non è colorato di rosso
{
if (!path(G, w, v, k--))
continue;
return true;
}
}
return false;
}

public static void main(String [] args)
{
Graph<String, Integer> G= new AdjacencyListGraph<String, Integer>();
Vertex<String> u = G.insertVertex("u");
Vertex<String> v = G.insertVertex("v");
Vertex<String> w = G.insertVertex("w");
Vertex<String> x = G.insertVertex("x");
Vertex<String> a = G.insertVertex("a");
G.insertEdge(u, v, 1);
G.insertEdge(u, w, 2);
G.insertEdge(w, x, 3);
G.insertEdge(v, x, 4);
G.insertEdge(w, a, 5);
G.insertEdge(a, x, 6);
System.out.println(path(G, u, a, 2)); //QUI FUNZIONA
System.out.println(path(G, u, a, 4)); //QUI NO
}
}

Le system.out.println del main dovrebbero restituirmi entrambe true ma non è così..
inoltre, se cancello la prima stampa la seconda mi restituisce true.. Quindi forse il problema è che quando chiamo la seconda volta il metodo path m restituisce false perchè alcuni vertici sono già stati colorati nella precedente chiamata e non li considera...
Dunque, è questo il problema oppure altro? Come posso poi risolverlo?
Spero tanto che qualcuno possa aiutarmi!! Grazie a tutti!
Ciao