[JAVA] Digrafo e nodi raggiungibili dal nodo sorgente

[Javino89]

Allora, provo con questa domanda. Ho un digrafo (la sua implementazione è in 1 altra discussione che ho aperto a cui nessuno ha risposto, si chiama Algoritmo digrafo o qualcosa di simile).

Devo fare questo:

Dato il grafo,un nodo sorgente ed un int x, resituire la Set<Integer> di nodi raggiungibili dal
nodo sorgente attraversando al massimo x archi. Consigli?

Il mio primo approccio (che non funziona granché) è questo:

public Set<Integer> maxHops(Graph g, int source, int max)
{
	List<Edge5R> e_visited = new ArrayList<Edge5R>();
	List<Integer> v_visited = new ArrayList<Edge5R>();
	Set<Integer> ris = new HashSet<Integer>();
	dfs(g,source,max,e_visited,v_visited,ris,0);
	return ris;
}

public void dfs(Graph g, int source, int max, List<Edge5R> e_visited, 
		List<Integer> v_visited, Set<Integer> ris, int cont)
{
	v_visited.add(source);
	if(cont <= max)
	{
		if(!ris.contains(source))
		{
			ris.add(source);
		}
	}
	for(Edge5R edge : Graph.outEdges(source))
	{
		if(!e_visited.contains(edge))
		{
			Integer w = edge.getDestination();
			
			if(!v_visited.contains(w))
			{
				e_visited.add(edge);
				dfs(g,w,max,e_visited,v_visited,ris,cont++);
			}
		}
	}
}

[bstefano79]

Nell'altra discussione il problema esposto sembra diverso da quello che vuoi fare qui

devi fare un metodo che dato due nodi ti restituisca vero (se c'è un arco fra i due) o falso (in caso contrario). Poi per ogni numero della matricola 1052001 chemi questo metodi Classe.metodo(1,0) Classe.metodo(0,5) finché o non trovi falso oppure non arrivi alla fine

[Javino89]

No aspetta. Infatti questo è 1 problema a parte diverso dall'altra discussione. Il problema dell'altra discussione l'ho risolto^^

[bstefano79]

non è molto semplice quello che chiedi
potresti fare qualcosa di ricorsivo dove il termine di fine ricorsione è ho raggiunto la massima lunghezza del cammino oppure dal nodo dove sono posso solo raggiungere un nodo in cui sono gia passato (l'ho buttata li per darti uno spunto)

[Javino89]

Guarda allora. Quello che dico si basa sul corso di fondamenti di informatica II che ho seguito.
Un algoritmo di visita dei grafi molto noto è la dfs, che al 99% si può applicare a questo
problema ed infatti il codice che ho scritto sopra si rifà alla dfs. L'approccio quindi è da considerarsi per forza ricorsivo perché farlo iterativo complicherebbe decisamente le cose. L'unica modifica che ho tentato di applicare è quella di introdurre una variabile intera che ho chiamato cont da far crescere ad ogni chiamata ricorsiva (la chiamata ricorsiva vuol dire che ho appena attraversato 1 arco) fino a farla arrivare al max (intero) e nel frattempo aggiungere i nodi incontrati se questi non sono già contenuti nella lista da riempire. Il problema è che non funziona bene, viene riempita male.. >.>

Edit: ora che ci penso una BFS potrebbe essere più indicata..

[bstefano79]

nel tuo codice ci sono svariati errori

public void dfs(Graph g, int source, int max, List<Edge5R> e_visited, 
		List<Integer> v_visited, Set<Integer> ris, int cont)
{
	v_visited.add(source);
	if(cont <= max)
	{
		if(!ris.contains(source))
		{
			ris.add(source);
		}
	
	       for(Edge5R edge : Graph.outEdges(source))
	       {
		   if(!e_visited.contains(edge))
		   {
			Integer w = edge.getDestination();
			
			if(!v_visited.contains(w))
			{
				e_visited.add(edge);
				dfs(g,w,max,e_visited,v_visited,ris,cont++);
			}
		}
	      }
        }
}

intanto il for lo puoi mettere direttamente dentro l'if perchè una volta raggiunto il massimo cammino è inutile controllare altri cammini.

Inoltre supponiamo che te chiami questa sequenza all'inizio
1,2,3,4 di lunghezza 4 te aggiungi i nodi 1,2,3,4 alla tua lista
ma se fosse possibile fare 1,4 nonostante 4 sia gia dentro la lista bisognerebbe andare avanti quindi non mi torna questa parte

if(!v_visited.contains(w))
{
	e_visited.add(edge);
	dfs(g,w,max,e_visited,v_visited,ris,cont++);
}

dovresti fare una cosa più complessa ad esempio dovresti avere una coppia (4,4) ovvero il nodo 4 l'ho visitato al passo 4 se trovo quel nodo con un numero di passi minore rifai la chiamata ricorsiva (4,2) il nodo 4 lo trovo anche al passo 2 visto che avevo (4,4) esegui la chiamata ugualmente e aggiorno (4,4) con (4,2)

[Javino89]

Allora il for non può andare dentro l'if perché non "vedrei" i lati uscenti dal nodo da scorrere. Inoltre devo restituire una lista con tutti i nodi raggiungibili dal nodo source percorrendo massimo int max archi. Quindi nel caso raggiungo il terzo arco oppure non è raggiungibile nessun altro nodo seguendo quel percorso, semplicemente DOVREBBE "tornare indietro" nelle chiamate ricorsive (immagina come se il contatore diminuisse fino a tornare a 0) per procedere con un eventuale altro arco uscente dal nodo source. Comunque ora non ho tempo per modificarlo, vedrò se posso stasera

[bstefano79]

ma se count>max perchè dovresti "vedere" i lati uscenti dal nodo da scorrere. Hai gia raggiunto il massimo del cammino degli altri archi non ti interessa più

poi supponi di avere questi archi (1,2)(1,3)(2,3)

da 1 puoi raggiungere direttamente 3 con un passo oppure lo puoi raggiungere con due passi passando da 2 senza dover tornare indietro

[Javino89]

Hai ragione la gestione di cont è completamente sbagliata. Bisogna ricordarsi che si sta utilizzando un metodo
ricorsivo.

Ipotizziamo di avere questo grafo:

0
(0->2)
1
(1->2)
2
(2->2)
(2->1)
(2->0)
(2->3)
3
(3->0)

Abbiamo:

dfs(0,0) = {0} //Il nodo raggiungibile percorrendo 0 archi e partendo da 0 è 0.
dfs(0,1) = {0,2}
dfs(0,2) = {0,1,2,3}
.
.
.

Ora che ci penso, cont non va incrementato in quel modo abominevole come ho fatto io, ma siccome la chiamata ricorsiva corrisponde all'aver attraversato un arco, dovrebbe esserci una cosa del genere:

if(!v_visited.contains(w))
{
	e_visited.add(edge);
	cont = 1 + dfs(g,w,max,e_visited,v_visited,ris,cont);
}

Che ne pensi? Ovviamente credo che non sia completo..
E' un macello uguale, devo cambiare il tipo di ritorno del metodo da void ad int.. >.>

[bstefano79]

il count va bene come lo hai fatto, ma il tutto va messo dentro l'if come ti ho detto io
poi leva questo controllo controllo
if(!v_visited.contains(w))
vedrai che funziona anche se per ora ti ripeterà alcuni nodi
vedremo poi come evitare le ripetizioni, intanto fai questa prova per vedere se i nodi restituiti sono giusti anche se ripetuti