Graph Routines
Representation of a graph in a file
We will store a graph in a disk file as follows.
The first line of the graph file contains the number of nodes in the graph and a flag (true=1, false=0) indicating whether or not the graph is directed.
This is followed by a list of edges; one on each line.
Each line consists of the index/number of the source node, the index/number of the destination node and the edgeweight.
Here are examples of graphs stored as data files.
Read in a graph from a graph file.
Get the name of the input graph file and open the file.
From the graph file,
Read in the number of Nodes, N and the directed flag (true=1, false=0)
Read in each edge consisting of a source node, destination node and edgeweight
and store the edges in an array called edgelist.
Create an empty graph, G, simply by declaring it.
Use the makegraph method of our graph class to populate the graph.
Makegraph takes as input the number of nodes, the directed flag and the
edgelist.
Internally, graphs of our graph class consist of
- an integer specifying the number of nodes in the graph
- a boolean specifying if it is a directed graph and
- an array of N nodes. Each node is numbered by its index (1..N). This array is called an adjacency list.
A node is a member of the node class and consists of three components,
(1) information about the node
(2) the degree of the node (the number of other nodes it is adjacent to) and
(3) a pointer to a linked list of edges incident with the node.
An edge is a member of the edge class and consists of
- the index of the destination node
- an edgeweight and
- a pointer to the next edge in the list
Makegraph should read in each edge from edgelist and (if the edge is not already in the list) place it at the beginning of the linked list of edges for the source node. If the graph is undirected it will also place the edge at the beginning of the linked list of edges for the destination node.
Write graph to a file
Get the name of the output graph file.
Write the number of nodes and directed flag (0=undirected, 1=directed) to the first line of the graph file.
For each node (1..N)
Traverse the linked list of edges for node N and
write each edge to the output file, one edge per line.
end for
Determine if a graph is connected
This algorithm will determine if a graph is connected by determining what nodes are "reachable" from a given starting node. The algorithm can be easily modified to identify the components of a graph.
Create an array of size N called Reachable and initialize each element to false indicating that no nodes are currently reachable.
Let the starting (first) node be node 1.
Reachable[1] = true; // node 1 is reachable from itself.
nodesReached = 1; //nodesReached equals the number of nodes reachable from 1 discovered so far.
Let Q be a queue of nodes, initially empty.
q.enque(1);
while(not Q.empty and nodesReached < numberOfNodes)
Q.deq(n)
for each node, m, adjacent to node n
if(not Reachable[m])
Reachable[m] = true; //node is now reachable so mark it.
nodesReached++;
Q.enque(m);
end if
end for
end while
if (nodesReached==numberofNodes)
return true //graph is connected
else return false //graph is not connected
end if
Determine if an undirected graph is a tree
Determine if graph is connected.
If not connected
then it is not a tree because it is not connected.
else if number of edges == number of nodes - 1
then it is a tree
else it is not a tree //and it contains a cycle
end if
end if
Find the shortest path from node u to node v using Dijkstra's algorithm
This may be done in order N2 time as follows.
Let S be the set of nodes to which we know the shortest path from u.
S may be implemented as an array such that S(n) = 1 means n is in S and S(n) = 0 means n is not in S.
Initialize S to all 0s since initially S is empty.
Declare an array SK such that SK(n) is the length of the shortest path currently known from u to n.
Initialize each element of SK to infinity (-1) since we know of no shortest paths initially.
Declare an array of integers of size N called FROM.
FROM(n) is the node that immediately precedes n in the path from u to n that gave the value currently in SK(n).
Initialize FROM to all 0s.
S(u) = 1 since we know the shortest path from u to u.
SK(u) = 0 since we know the length of the shortest path from u to u = 0.
Find the next node of S as follows.
Find the node, x not in S, with the smallest value in SK.
It can be shown that this value is the shortest path from u to x.
Therefore we may add x to S since we now know the shortest path from u to x.
while x != v // if x = v then we have found the shortest path from u to v and we are finished.
S = S U {x}. (S[x] = 1)
Since we have added node x to S (because we have discovered the shortest path
from u to x) we may now have discovered shorter paths to nodes adjacent to x.
For each node, y, adjacent to x
if SK(y) > SK(x) + dist(x, y) // of course infinity=-1 is considered larger than any positive integer.
then SK(y) = SK(x) + dist(x, y)
FROM[y] = x // since we have found a shorter path from u to y.
end for
Find the node, x not in S, with the smallest value in SK.
We have found the shortest path from u to x.
end while
At this point in the algorithm SK[v] holds the length of the shortest path from u to v.
We can display the nodes in the path by using the FROM array as follows.
x = v;
while (x != u)
cout << x << "-";
x = FROM[x];
end while
cout << x;
Find MWST (MCST) using Prim's algorithm.
Prim's algorithm finds the minimum weight (or cost, etc.) spanning tree of a
graph.
It is a simple greedy algorithm.
Let T be the set of nodes that are in the MWST so far.
T is implemented as an array of boolean.
T(n) = 1 indicates n is in T and T(n) = 0 indicates n is not in T where n is a node number.
T may be initialized to the set {1}. I.e., T(1) = 1 and all other entries are zero.
Let minCost be an array such that minCost[i].cost is the cost, c, of the cheapest edge discovered so far connecting a member of T to i (where i is not in T) and minCost[i].node is the node, n, that i is connected to in T.
I.e., edge (i,n) has cost c and is not in the MWST.
Let v = 1, the only node in T
while T does not contain all the nodes of the graph
for each node, m, adjacent to v
if m is not in T
then update minCost[m]
(I.e., if edgecost(v, m) < minCost[m].cost
then minCost[m].cost = edgecost((v, m)) and
minCost[m].node = v
end if
end for
Find the least cost edge that connects a node, u, of T with a node, v, not in T by searching array minCost. Only inspect nodes in minCost that are not in T; i.e. nodes where T(n) = 0.
Add v to T and add the edge (u, v) to the list of edges of our MWST.
This is done simply by making T(v) = 1. minCost[v].node already = u and minCost[v].cost already equals the cost of edge (u, v).
end while
Generate a random tree, T
Let the number of nodes = N (so the number of edges will be N-1).
Create array, nodes[], to hold the node numbers (1..N)
nodes is initialized so that node[i] = i;
Create an array called edgelist of size at least N-1 to hold the edges of T.
The tree, T, will be constructed node by node (or equivalently edge by edge).
The edges thus far added to T will be store in an array called edgelist.
Each element of edges will contain a source node number, a destination node number and an edgeweight.
When the tree, T, has, say, M nodes, nodes[1] through nodes[M] will contain the node numbers of those nodes. nodes[M+1] through nodes[N] will contain the node numbers of those nodes not yet in the tree.
M = 0; // Let tree, T, be empty.
M = 1; // Add node 1 to T
while (M < N)
Select at random a node, n1, in T from nodes[1] ... nodes[M] and a node, n2,
outside of T from nodes[M+1] ... nodes[N].
If the graph is directed then randomly determine the direction of the edge.
Add the edge to the edgelist.
M++; //increment the number of nodes in T.
swap nodes[n2] and nodes[M] (this adds node n2 to T by placing it in the last "M" position of nodes in T)
end while
Create adjacency lists from the edgelist or write the edgelist to a file as required.
Generate random graph, G
Determine number of nodes, N, and number of edges, E and whether the graph is to be directed or undirected.
Generate a random spanning tree. (See Generate a random tree above).
The graph now consists of an array of nodes and each node contains a pointer to a list of the nodes it is adjacent to (see Read in a graph from a graph file above.)
Next, select the remaining E-(N-1) edges at random and add them to G.
To select an edge at random
if the graph is weighted then select a weight at random.
select a node, u, at random from those nodes with outdegree < N-1.
select another node, v, from those nodes that are not in u's edgelist
Add edge (u, v) to u's adjacency list and if undirected to v's adjacency list.
Top of this page 
Home page 
