Homework: Generating Graphs

Question

I need to simulate a discrete event simulator and for that I need to generate a network consisting of 30 nodes and then check if the generated graph is directed or not. Can anyone guide me on how to start with this. I should not be using the boost library to do this. Yes this is an assignment, I need an advice to start with. I just need few pointers to go ahead.

#define MAXNODES 30

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

Is the above struct definition correct?

Answer 1

I think you need to define your particular version of 'directedness' first. What is the basis for deciding whether one node precedes another? Are you just going to, for example, assign a random number to each node? If so, your struct seems incomplete. It would at least need an extra data element to hold that node's positional value...

Answer 2

I am assuming that you may generate any random graph. I'm also assuming that you're familiar with the adjacency matrix representation of a graph.

If that is the case, I'd use an adjacency matrix representation of a graph. You'd use a 2D array to represent this.

So your graph would be defined as:

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

Is your graph unweighted or weighted? If it is unweighted, then each element of your matrix (graph[3][7], for example) will have either a 0 or 1. If it is a 0, then there is no edge connecting nodes 3 and 7 (in this example), and if there is a 1, then there is indeed an edge.

If its weighted, then a 0 still means there is no edge, but a number (1, 9, 234, anything) indicates the weight of that edge.

So you can use a loop to fill in a number for each array element - so, go through each pair of nodes and randomly assign a weight (0 for no edge, or some number if there is an edge, as per weighted-vs-unweighted.)

So to answer your question, checking for "directedness" is easy. If a graph is directed, then graph[3][7] and graph[7][3] will have the same value. So you can check for every pair (graph[i][j] and graph[j][i]) to see if the values are equal. You are seeing if the matrix is symmetric.

If it is not symmetric (so [3][7] has 0, but [7][3] has 1) then there is only an edge in one direction - making it directed. And if each pair has two values ([3][7] = 5, [7][3] = 21) then the graph is directed, since the weight changes depending on the direction you're traveling.