[JAVA] Generatore grafi random

[ragnonerodocet]

Buongiorno.

devo implementare in Java un applicazione che crei grafi pesati non direzionati random.

Ho pensato di fare in questo modo.

L'utente in input invia il numero N di nodi dell'albero, che deve essere maggiore o uguale a 4.

Creo a questo punto una matrice NxN, che mi servirà per segnare gli archi che connettono i nodi.

A questo punto, mi blocco un po'.

Per ogni nodo, scorro tutti gli altri, e con la funzione Math Random creo al 50% un arco tra di essi e sempre con Math gli attribuisco un valore casuale da 1 a 10.

NOn ho problemi in questo, ma potrebbe capitare un'occorrenza come questa.

A-------B-------C

D-------E

cioè il caso in cui il grafo non sia completamente connesso. E non voglio accada questo...

Oppure un'occorrenza in cui un nodo non è connesso a nessun'altro.

Questa seconda occorrenza è rarissima e si può risolvere facilmente vedendo a giochi fatti la matrice creata.

Ma il primo problema proprio non so come risolverlo.

Posto un po' di codice...

public Integer[][] matrix_generator ( int n ) {

this.matrix = new Integer[n][n];
for (int righe = 0; righe < n ; righe ++){
for (int colonne = 0; colonne < n ; colonne ++){
this.matrix[righe][colonne] = (int)(2*Math.random());
this.matrix[colonne][righe] = this.matrix[righe][colonne];
if (colonne == righe){
this.matrix[righe][colonne] = 0;
this.matrix[colonne][righe] = 0;
}
}
}

return this.matrix;

}

Praticamente assegno un 1 o uno 0 ad ogni possibile coppia riga-colonna, con l'esclusione del caso in cui un nodo sia collegato a se stesso.

Ora, il problema di un nodo non collegato a nulla è facilmente risolvibile: basta controllare che una riga (e quindi la colonna adiacente) non sia tutta composta di 0.

Ma capire dalla matrice se un sottografo non è connesso è più difficile.

QUalcuno ha suggerimenti a proposito?

[ragnonerodocet]

Ho implementato diversamente la funzione di riempimento per avere un algoritmo di riempimento più efficiente.

Da n^2 passi sono arrivato a 2*n, lineare...

public Integer[][] matrix_generator_v2 ( int n ) {

this.matrix = new Integer[n][n];

for (int righe = 0; righe < n ; righe ++){
for (int colonne = righe; colonne < n ; colonne ++){
this.matrix[righe][colonne] = (int)(2*Math.random());
this.matrix[colonne][righe] = this.matrix[righe][colonne];
}
}
for (int righe = 0; righe < n; righe ++){
this.matrix[righe][righe] = 0;
}



this.matrix_control(n);
return this.matrix;

}

Mettiamo che la matrice sia così composta

1.1 --- 1.2 --- 1.3 --- 1.4
2.1 --- 2.2 --- 2.3 --- 2.4
3.1 --- 3.2 --- 3.3 --- 3.4
4.1 --- 4.2 --- 4.3 --- 4.4

Invece di scorrere tutta la matrice, scorro prima tutta la prima riga, ed assegno casualmente valore 1 o 0. Se viene scelto un 1 in corrispondenza dell'arco 1.2 (prima riga, seconda colonna) è evidente che ci sarà un 1 anche nell'arco 2.1...

Quindi risparmio confronti.

Inoltre, non ha senso scorrere tutta la seconda riga, perchè ho già esaminato il punto 2.1....

Quindi nel secondo confronto esamino la sottomatrice quadrata senza la prima riga e la prima colonna, e agisco come prima.

2.2 --- 2.3 --- 2.4
3.2 --- 3.3 --- 3.4
4.2 --- 4.3 --- 4.4

Fino all'ultimo passaggio che analizza

4.4

Poi, con un semplice ciclo for, mi assicuro che tutti i valori della matrice con indici di riga e colonna uguali siano 0, perchè come detto non voglio avere un vertice connesso a se stesso.

Rimane vivo il caso in cui ci siano sottografi non connessi.

Come posso risolvere?