Software

For the implementation of our algorithm, we use a two-dimensional array of structures whose every element represents a link between any two nodes I and J. Each structure has two parameters – a link presence parameter and a link length parameter. The presence parameter indicates the presence or absence of a link between the two nodes I and J. If the value of link[i,j].presence is ‘0’, it means there is no link between I and J. If it is ‘1’, a link is present. The second parameter length indicates the physical length of the link, if present, in kms. If there is no link, its value is ‘0’.

Below is the declaration of the array and structure:

//Define a structure to store information about each link
struct linkdata {
int presence; //Tells us if a link is present or not
int length; //Tells us the link's length, if present
};
//Define a 2-D array of type 'data' and size 'nxn'
//Parameter 'MAX' is the maximum permissible number of nodes in the subnet
linkdata subnet[MAX]
[MAX];

When the program is run, the user is asked to enter the necessary details of the subnet, namely the number of nodes, the various links present and their lengths.

//Form array map of subnet
//Parameter 't' is the total number of nodes in our subnet (<=MAX)
cout<<"\n\nEnter the total number of nodes in the subnet: ";
cin>>t;
for(i=0;i<t-1;i++)
{
cout<<"\nEnter the number of nodes to which node "<<i+1<<" is connected: ";
cin>>x;
cout<<"\nEnter the numbers of those nodes one by one:";
for(j=0;j<x;j++)
{
cout<<"\n"<<j+1<<": ";
cin>>y;
subnet[i]
[y-1].presence=subnet[y-1]
[i].presence=1;
cout<<"\nEnter length of link from "<<i+1<<" to "<<y<<": ";
cin>>z;
subnet[i]
[y-1].length=subnet[y-1]
[i].length=z;
}
}

Alternately, the user can provide the location of the configuration file that contains these details (the format for such a file is fixed and must be strictly adhered to for successful operation of the program). Finally, the user is asked to enter the numbers of the “source” and “destination” nodes. Then the algorithm goes about finding the shortest route between these two nodes. This is finally displayed to the user in both textual and graphical form.



Graphical User Interface

The graphical interface provides a visual representation of the subnet map. Our GUI algorithm uses the circle() function to draw yellow circles representing individual nodes at equal spaces along the circumference of a larger, “invisible” circle whose center is the center of the screen. It then connects all those circles (nodes) that have links between them with white lines, using the line() function. Finally, the shortest path is highlighted by drawing it with a red line (see figure below).

Shortest path program screenshot

Figure 6: Shortest path program screenshot

The C library function setcolor() is used to set colors of various components. The user can exit the program from here by pressing any key.

Click here to download the program code (Turbo C++).