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.
Essendo Prim una modifica di Dijkstra vorrei risolvere principalmente Dijkstra.
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, String info) {
nodo1 = n1;
nodo2 = n2;
this.info = info;
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(nome);
if(x == null) {
mapArchi.put(n, ultimoArchi);
mapArchi.put(nodo2 + nodo1, ultimoArchi);
Arco nuovo = new Arco(nodo1, nodo2, peso, nome);
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] = inodoS;
dist[inodoS] = 0;
CodaConPriorita coda = FabbricaCodaConPriorita.crea(dimStandard);
for(int x = 0; x < ultimoNodi; x++) {
String j = arrayNodi[x].nome;
coda.inserisci(j, dist[x]);
}
while(!coda.eVuota()) {
Nodo u = new Nodo(coda.estraiPrimo()); //estraggo il primo cioè 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);
}
}
}
}
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();
}
<altri metodi>
}
Dijkstra 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