[Java] Rappresentazione topologica di una rete

[Nemok]

Ciao ragazzi, avrei bisogno di qualche suggerimento su come rappresentare la topologia di una rete. Quello che mi serve è una rappresentazione della struttura, non devo fare una rappresentazione grafica.
Facciamo conto quindi di avere il grafo di una rete, nel quale ogni nodo rappresenta un'area (ad esempio una LAN), e gli archi rappresentano i collegamenti tra aree, con relativa banda associata.
Avevo pensato ad una matrice delle adiacenze, ma non ho ben chiaro come implementarla, tenendo conto che il grafo è dinamico (aree possono essere aggiunte o eliminate).

Il linguaggio di riferimento è java, qualche suggerimento?
:)

[thebol]

Crei un oggetto nodo(che rappresenta la tua area/Lan), che contiene al suo interno una linkedList che contiene a sua volta i riferimenti agli altri nodi.

Attenzione ai loop infiniti ;)

[Nemok]

Grazie thebol ;)
Dunque la soluzione che proponi presenta credo 2 problemi: il primo è che non puoi memorizzare direttamente il "peso" (banda) di un arco tra due nodi (aree). Il secondo è che forse diventa macchinoso l'estrapolazione del path tra due nodi qualsiasi. Potrei aver bisogno ad esempio di una funzinoe che date due aree mi dice qual'è la banda max di trasmissione tra le due (quindi il minimo delle bandwidth sul cammino area1 --> area2).

[thebol]

Grazie thebol ;)
Dunque la soluzione che proponi presenta credo 2 problemi: il primo è che non puoi memorizzare direttamente il "peso" (banda) di un arco tra due nodi (aree). Il secondo è che forse diventa macchinoso l'estrapolazione del path tra due nodi qualsiasi. Potrei aver bisogno ad esempio di una funzinoe che date due aree mi dice qual'è la banda max di trasmissione tra le due (quindi il minimo delle bandwidth sul cammino area1 --> area2).

Il primo problema è facilmente risolvibile.

Nella linkedList non salvi l'oggetto nodo, ma un oggetto arco, che contiene il nodo e il peso del collegamento.

Per l'altro problema, ti consiglio di guardare qualche algoritmo sui grafi(di solito presenti sui libri di algoritmi, ma trovi tonnellate di roba anche in rete)

[thebol]

Fra l'altro il tuo, è il classico e ben conosciuto problema del trovare il percorso fra 2 nodi migliore in un grafo pesato.

Non ricordo l'algoritmo da usare, ma se cerchi un attimo lo trovi(compresa la struttura dati da usare).

[luxorl]

Fra l'altro il tuo, è il classico e ben conosciuto problema del trovare il percorso fra 2 nodi migliore in un grafo pesato.

Non ricordo l'algoritmo da usare, ma se cerchi un attimo lo trovi(compresa la struttura dati da usare).

Algoritmo di Dijkstra..
http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra

O se lo vuoi per tutte le coppie di nodi un bel algoritmo di Floyd :D
http://it.wikipedia.org/wiki/Algoritmo_di_Floyd_-_Warshall

Per quest'ultimo hai bisogno della matrice delle adiacenze

[luxorl]

Comunque se vuoi implementarti una matrice delle adiacenze.. e il grafo è pesato.. devi crearti l'oggetto peso definendolo con un intero e definendo anche il concetto di peso infinito (arco tra due nodi inesistente)..
e poi crei una matrice di pesi n*n (n=numero nodi) ed ad ogni incrocio metti il peso dell'arco che esiste tra il nodo ni e il nodo nj... se non esiste nessun arco metti il peso infinito.. :)

dimentiavo che per definierti il peso infinito devi ridefinirti l'operazione di somma e di confronto.. :D

questa potrebbe essere una possibile implementazione (presa da delle dispense del mio corso di algoritmi.. quindi prendete le cose con le pinze)


public class Peso{

public Peso( int P ) {p = P; vinf = false;}

public Peso() {vinf = true;} // costruttore di peso infinito

public static final Peso inf = new Peso(); // costante peso infinito

public static Peso somma ( Peso P1, Peso P2 ){
return ( P1.vinf || P2.vinf )? inf: Peso(P1.p+P2.p);
}

public boolean minore(Peso P2){
return !vinf && (P2.vinf || P1.p < P2.p);
}

public static Peso min ( Peso P1, Peso P2 ){
return ( P1.minore(P2) )? P1: P2;
}

public boolean equals( Object P2 ){
if (! P2 instanceof Peso) return false;
return (P1.equals((Peso) P2);
}

public boolean equals( Peso P2 ){
return (P1.vinf && P2.vinf) ||
(!P1.vinf && !P2.vinf && P1.p == P2.p);
}

// conversione a intero
public int valInt() throws ValoreInfinito{
if (vinf) throw new VaoloreInfinito();
return p;
}

public void modPeso(int peso){
p = peso;
}

public boolean eInf(){return vinf;};

// variabili di istanza
private int p;
private boolean vinf;
}


public class ValoreInfinito extends Errore{};

[Nemok]

Grazie mille per i suggerimenti.
Il problema delle liste di adiacenza è che non è facile tenerle aggiornate. Nel mio caso non ho delle aree numerate (che renderebbero semplice la localizzazione nella matrice), bensì dei codici identificativi. Nel momento che viene aggiunto un nodo dunque sarebbe complesso aggiornare la matrice delle adiacenze...

[luxorl]

Grazie mille per i suggerimenti.
Il problema delle liste di adiacenza è che non è facile tenerle aggiornate. Nel mio caso non ho delle aree numerate (che renderebbero semplice la localizzazione nella matrice), bensì dei codici identificativi. Nel momento che viene aggiunto un nodo dunque sarebbe complesso aggiornare la matrice delle adiacenze...

potresti, ma questo è un suggerimento che butto così, trasformare i codici in semplici interi e tenerti traccia delle associazioni in una hashmap<chiave,valore> di java... usando come chiave il tuo codice e come valore il numero intero che gli hai assegnato :)