Homework: Generating Graphs
-
10-07-2019 - |
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?
Solution
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.
OTHER TIPS
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...