Grafo non orientato: algoritmi di Prim e Dijkstra

[sirmsym80]

Ciao, ho fatto questa classe sui grafi non orientati rappresentati mediante liste di adiacenza ed i cui nodi del grafo sono stringhe. I metodi vanno tutti eccetto l'algoritmo di Prim e Dijkstra. Prim applicato sul grafo

mi da questo risultato

che è ovviamente sbagliato.
Mentre Dijkstra non l'ho proprio provato perchè non riesco a finire di scrivere il codice.
Aiuti?

package grafi;

import coda.*;
import arrays.*;
import grafo.unionFind.*;
import java.util.*;
import java.lang.*;
import java.io.*;

public class GrafoNonOrientatoListeDiAdiacenza implements GrafoNonOrientato {

	static final int dimStandard = 100;
	private static double INFINITO = Double.MAX_VALUE;
	Nodo[] arrayNodi;
	Arco[] arrayArchi;
	int ultimoNodi;
	int ultimoArchi;
	boolean[] visitato;
	double[] peso;
	int[] padre;
	CodaConPriorita coda;
	UnionFindInt unionFind;
	Hashtable<String, Integer> mapNodi;
	Hashtable<String, Integer> mapArchi;
	private static Random gen = new Random();

	private class Arco {
		String nodo1;
		String nodo2;
		String info;
		double peso;

		private Arco()	{
			nodo1 = "";
			nodo2 = "";
			info = null;
			peso = 0;
		}

		private Arco(String n1, String n2, double peso) {
			nodo1 = n1;
			nodo2 = n2;
			info = null;
			this.peso = peso;
		}
	}

	private class Nodo {
		String nome;
		LinkedList<String> listeAd;

		private Nodo() {
			nome = "";
			listeAd = new LinkedList<String>();
		}

		private Nodo(String nome) {
			this.nome = nome;
			listeAd = new LinkedList<String>();
		}
	}

	public GrafoNonOrientatoListeDiAdiacenza() {
		arrayNodi = new Nodo[dimStandard];
		arrayArchi = new Arco[dimStandard];
		ultimoNodi = 0;
		ultimoArchi = 0;
		visitato = new boolean[dimStandard];
		peso = new double[dimStandard];
		padre = new int[dimStandard];
		coda = FabbricaCodaConPriorita.crea(dimStandard);
		unionFind = FabbricaUnionFindInt.crea(dimStandard);
		mapNodi = new Hashtable<String, Integer>(dimStandard);
		mapArchi = new Hashtable<String, Integer>(dimStandard);
	}

	public GrafoNonOrientatoListeDiAdiacenza(int n) {
		arrayNodi = new Nodo[n];
		arrayArchi = new Arco[n];
		ultimoNodi = 0;
		ultimoArchi = 0;
		visitato = new boolean[n];
		peso = new double[n];
		padre = new int[n];
		coda = FabbricaCodaConPriorita.crea(n);
		unionFind = FabbricaUnionFindInt.crea(n);
		mapNodi = new Hashtable<String, Integer>(n);
		mapArchi = new Hashtable<String, Integer>(n);
	}

	public int numNodi() {
		return ultimoNodi;
	}


	public int numArchi() {
		return ultimoArchi;
	}

	public void aggiungiNodo(String v) {
		Integer x = mapNodi.get(v);
		if(x == null) {
			mapNodi.put(v, ultimoNodi);
			arrayNodi[ultimoNodi] = new Nodo(v);
			ultimoNodi++;
		}
		else
			System.out.println("Nodo gia' esistente");
	}

	public void aggiungiArco(String nodo1, String nodo2, double peso, String nome) {
		Integer x1 = mapNodi.get(nodo1);
		Integer x2 = mapNodi.get(nodo2);
		if((x2 != null) && (x1 != null)) {
			String n = nodo1 + nodo2;
			Object x = mapArchi.get(n);
			if(x == null) {
				mapArchi.put(n, ultimoArchi);
				mapArchi.put(nodo2 + nodo1, ultimoArchi);
				Arco nuovo = new Arco(nodo1, nodo2, peso);
				arrayArchi[ultimoArchi] = nuovo;
				int ind = mapNodi.get(nodo1).intValue();
				int ind1 = mapNodi.get(nodo2).intValue();
				arrayNodi[ind].listeAd.add(nodo2);
				arrayNodi[ind1].listeAd.add(nodo1);
				ultimoArchi++;
			}
			else
				System.out.println("Arco gia' esistente");
		}
		else
			System.out.println("Nodi inesistenti");
	}


	public void dijkstra(String nodoS) {
		double[] dist = new double[dimStandard];
		for(int x = 0; x < ultimoNodi; x++) {
			dist[x] = INFINITO;
			padre[x] = -1;
		}
		Integer inodoS = mapNodi.get(nodoS);
		padre[inodoS] = nodoS;
		dist[inodoS] = 0;
		CodaConPriorita coda = FabbricaCodaConPriorita.crea(dimStandard);
		for(int x = 0; x < ultimoNodi; x++) {
			coda.inserisci(x, dist[x]);
			while(!coda.eVuota())
				Nodo u = new Nodo(coda.estraiPrimo());
			double cuv = arrayArchi[u].peso; //weight of the arch between the node u and the node v
			for(int v = 0; v < arrayNodi[u].listeAd.size(); v++) {
				if(dist[u] + cuv < dist[v]) {
					padre[v] = u;
					dist[v] = dist[u] + cuv;
					decreasePriority(v, dist[v], Q);
				}
			}
		}
	}

	public GrafoNonOrientato prim(String nodoS) {
		Integer inodo1 = mapNodi.get(nodoS);
		if(inodo1 == null)
			return null;
		GrafoNonOrientatoListeDiAdiacenza gg = new GrafoNonOrientatoListeDiAdiacenza(ultimoNodi);
		for(int i = 0; i < ultimoNodi; i++)
			visitato[i] = false;
		int inodo = mapNodi.get(nodoS).intValue();
		peso = new double[ultimoNodi];
		padre = new int[ultimoNodi];
		for(int i = 0; i < ultimoNodi; i++) {
			peso[i] = Double.POSITIVE_INFINITY;
			padre[i] = -1;
		}
		coda = FabbricaCodaConPriorita.crea(ultimoNodi);
		coda.inserisci(nodoS, 0.0);
		peso[inodo] = 0;
		while(!coda.eVuota()) {
			nodoS = coda.estraiPrimo();
			String nodoCorrente = arrayNodi[inodo].nome;
			gg.aggiungiNodo(nodoCorrente);
			visitato[inodo] = true;
			for(int i = 0; i < arrayNodi[inodo].listeAd.size(); i++) {
				String nodoVicino = arrayNodi[inodo].listeAd.get(i);
				int iarco = mapArchi.get(nodoVicino + nodoCorrente).intValue();
				int iNodoVicino = mapNodi.get(nodoVicino).intValue();
				if(!visitato[iNodoVicino]) {
					if(peso[iNodoVicino] > arrayArchi[iarco].peso) {
						if(peso[iNodoVicino] == Double.POSITIVE_INFINITY)
							coda.inserisci(nodoVicino, arrayArchi[iarco].peso);
						else
							coda.cambiaPriorita(nodoVicino, arrayArchi[iarco].peso);
						padre[iNodoVicino] = inodo;
						peso[iNodoVicino] = arrayArchi[iarco].peso;
					}
				}
			}
		}
		for(int i = 0; i < padre.length; i++) {
			if(padre[i] != -1) {
				String arcoNome = arrayNodi[padre[i]].nome + arrayNodi[i].nome;
				gg.aggiungiArco(arrayNodi[padre[i]].nome, arrayNodi[i].nome, peso[i], arcoNome);
			}
		}
		return gg;
	} 

        <altri metodi>
}

Grazie

[sirmsym80]

Nessuno?

[sirmsym80]

Kruskal funziona, l'ho messo a posto ma non riesco a fare Dijkstra e quindi Prim. Ho scritto Dijkstra in questo modo:

public void dijkstra(String nodoS) {
	double[] dist = new double[dimStandard];
	for(int x = 0; x < ultimoNodi; x++) { //per ogni nodo
		dist[x] = INFINITO; 
		padre[x] = -1;
	}		
	Integer inodoS = mapNodi.get(nodoS);
	padre[inodoS] = inodoS; 
	dist[inodoS] = 0;
	CodaConPriorita coda = FabbricaCodaConPriorita.crea(dimStandard);
	for(int x = 0; x < ultimoNodi; x++) { //per ogni nodo 
		String j = arrayNodi[x].nome;
		coda.inserisci(j, dist[x]);
	}		
	while(!coda.eVuota()) {
		Nodo u = new Nodo(coda.estraiPrimo()); //estraggo il primo cioe' quello con distanza minima
		Integer iU = mapNodi.get(u);
		for(int v = 0; v < arrayNodi[iU].listeAd.size(); v++) { //for each(Nodo v adiacente a u)
			double cuv = pesoArco(u.nome, arrayNodi[v].nome); 
			if(dist[iU] + cuv < dist[v]) {
				padre[v] = iU; 
				dist[v] = dist[iU] + cuv;
				coda.cambiaPriorita(arrayNodi[v].nome, dist[v]); //decreasePriority(v, dist[v], coda);
			}
		} //end for
	} //end while
}

public double pesoArco(String arco1, String arco2) {
	for(int i = 0; i < ultimoArchi; i++) {
		String nome1 = arrayArchi[i].nodo1 + arrayArchi[i].nodo2;
		String nome2 = arrayArchi[i].nodo2 + arrayArchi[i].nodo1;
		if(arrayArchi[i].info.compareTo(nome1) == 0 || arrayArchi[i].info.compareTo(nome2) == 0)
			return arrayArchi[i].peso;
	}
	throw new IllegalArgumentException();
}

Ma non riesco a testarlo poichè il metodo pesoArco non funziona. Tale metodo dovrebbe cercare nell'array di archi quello con i due estremi chiamati arco1 e arco2 e restituire il peso di quest'arco.
Quando vado a provare questo singolo metodo mi da errore dicendo che non lo trova. Eppure è dichiarato pubblico ed è inserito nella mia interfaccia. Dov'è il problema?
Grazie

[sirmsym80]

nessuno?

[joumvaer92]

Ciao, se vuoi ho il link di un package con un set di tutti gli algoritmi utili alle elaborazioni dei grafi:
http://graphstream-project.org/download/
queste sono le api:
http://graphstream-project.org/api/gs-algo/

[sirmsym80]

Non sono ancora riuscito a risolvere il problema di Dijkstra..
Quando compilo mi dice che c'è un errore (not a statement) alla riga

Nodo u = new Nodo(coda.estraiPrimo());

Non so come risolvere.. Sono bloccato..

[LeleFT]

In merito all'ultimo post, riporta esattamente il messaggio di errore del compilatore. Se ti dice "Not a statement" in quella riga, l'unica possibilità è che il metodo estraiPrimo() dell'oggetto "coda" sia void e non restituisca alcunché.

Verificalo... non avendo postato la classe CodaConPriorita posso solo fare questa supposizione.


Ciao.

[sirmsym80]

Originariamente inviato da LeleFT
In merito all'ultimo post, riporta esattamente il messaggio di errore del compilatore. Se ti dice "Not a statement" in quella riga, l'unica possibilità è che il metodo estraiPrimo() dell'oggetto "coda" sia void e non restituisca alcunché.

Verificalo... non avendo postato la classe CodaConPriorita posso solo fare questa supposizione.


Ciao.

Grazie per la risposta. Il compilatore mi da questi errori:

.../GrafoNonOrientatoListeDiAdiacenza.java: 179: not a statement
				Nodo u = new Nodo(coda.estraiPrimo()); //estraggo il primo cioè quello con distanza minima
				^
.../GrafoNonOrientatoListeDiAdiacenza.java: 179: ';' expected
				Nodo u = new Nodo(coda.estraiPrimo()); //estraggo il primo cioè quello con distanza minima
				    ^
2 errors

estraiPrimo() restituisce una stringa..

[sirmsym80]

Qualche idea?

[LeleFT]

No... dev'esserci qualche errore di sintassi prima, da qualche altra parte.
Posta tutto il file GrafoNonOrientatoListeDiAdiacenza.java


Ciao.