Compiti a casa: generare grafici

Question

Devo simulare un simulatore di eventi discreto e per questo devo generare una rete composta da 30 nodi e quindi verificare se il grafico generato è diretto o meno. Qualcuno può guidarmi su come iniziare con questo. Non dovrei usare la libreria boost per fare questo. Sì, questo è un compito, ho bisogno di un consiglio per cominciare. Ho solo bisogno di alcuni suggerimenti per andare avanti.

#define MAXNODES 30

struct {
int p;
int *incoming;
int *outgoing;
} NODE[MAXNODES]
//The struct defines each node and the neighbors to it. 

La definizione della struttura sopra è corretta?

Answer 1

Suppongo che tu possa generare qualsiasi grafico casuale. Suppongo anche che tu abbia familiarità con la rappresentazione della matrice di adiacenza di un grafico.

In tal caso, utilizzerei una rappresentazione matrice di adiacenza di un grafico . Utilizzeresti un array 2D per rappresentarlo.

Quindi il tuo grafico sarebbe definito come:

#define MAXNODES 30
int graph[MAXNODES][MAXNODES];

Il tuo grafico non è ponderato o ponderato? Se non è ponderato, ogni elemento della tua matrice ( graph [3] [7] , per esempio) avrà uno 0 o 1. Se è uno 0, allora non ci sono bordi connessi nodi 3 e 7 (in questo esempio), e se c'è un 1, allora c'è davvero un bordo.

Se è ponderato, uno 0 indica comunque che non c'è bordo, ma un numero (1, 9, 234, qualsiasi cosa) indica il peso di quel bordo.

Quindi puoi usare un ciclo per riempire un numero per ogni elemento dell'array - quindi, passa attraverso ogni coppia di nodi e assegna casualmente un peso (0 per nessun bordo, o qualche numero se c'è un bordo, come da ponderato -Vs-non ponderata.)

Quindi, per rispondere alla tua domanda, controllando " directness " è facile. Se viene diretto un grafico, il grafico [3] [7] e il grafico [7] [3] avranno lo stesso valore. Quindi puoi controllare ogni coppia (grafico [i] [j] e grafico [j] [i]) per vedere se i valori sono uguali. Stai vedendo se la matrice è simmetrica .

Se non è simmetrico (quindi [3] [7] ha 0, ma [7] [3] ha 1) allora c'è solo un bordo in una direzione - che lo rende diretto. E se ogni coppia ha due valori ([3] [7] = 5, [7] [3] = 21) il grafico è diretto, poiché il peso cambia a seconda della direzione che stai viaggiando.

Answer 2

Penso che tu debba prima definire la tua versione particolare di "orientamento". Qual è la base per decidere se un nodo precede un altro? Ad esempio, hai intenzione di assegnare un numero casuale a ciascun nodo? In tal caso, la tua struttura sembra incompleta. Avrebbe almeno bisogno di un ulteriore elemento di dati per contenere il valore posizionale di quel nodo ...