Hi, I need help with this c++ program. I tried but it is confused

Graphs

Min path

DESCRIPTION

Write a program that will display the minimum path between any two vertices in a given graph. The program will input the graph from a file provided by the user. It will prompt the user for entering the name of the start vertex and the end vertex. It will find the minimum path between the two vertices. It will display the minimum path showing all the vertices along the path. It will also display the total distance along the minimum path.

TESTING

Test the program for two data sets included in this module as text files. For each data set, carry out a number of test runs as listed below.

Data Set 1

Test the program for the data set 1 listed. Enter this data into a file and input the data from the file.

The data consists of two parts. In the first part, each line represents a vertex. It contain two values. The first value specifies the vertex number. The second value specifies the vertex name. The first part ends when a line contains -1 by itself. In the second part, each line represents an edge. It contains three values. The first two values specify two vertices connecting the edge. The third value specifies the weight of the edge. This part ends when a line contains -1 by itself.

0 SF

1 LA

2 CHICAGO

3 NY

4 PARIS

5 LONDON

-1

0 1 80

0 2 200

0 3 300

1 2 230

1 5 700

2 3 180

3 4 630

3 5 500

4 5 140

-1

Data Set 1: Test Run 1

Run the program using SF as the start vertex. Program input/output dialog is shown below. The user input is shown in bold.

Enter Start Vertex: SF

Enter End Vertex :LONDON

Min Path: SF LA LONDON 780

Data Set 1: Test Run 2

Enter Start Vertex: SF

Enter End Vertex : PARIS

Min Path: SF LA LONDON PARIS 920

Data Set 2:

Data set 2 is available in a file attached.

For data set 2, run the program several times: each time use the same vertex (the first vertex input) as the start vertex and a different vertex as the destination vertex till each vertex has been used as the destination vertex.

IMPLEMENTATION

MinPath algorithm finds the minimum path from a specified start vertex to a specified target (destination) vertex in a graph and displays the following.

The list of all the vertices in the minimum path from the start vertex to the target vertex.

The total distance from the start vertex to the target vertex along the above path.

Methodology

MinPath algorithm accomplishes the above by using a variation of BreadthFirst traversal algorithm covered in a previous assignment with the following additional provisions.

It uses a priority queue (PmainQ) instead of a regular queue.

In the queue, it enqueues a vertex as an item describing the vertex. The vertex item contains the following fields:

Total Accumulated Distance: The total distance from the start vertex to this vertex.

Path List: The list of all vertices in the path from the start vertex to this vertex. The list of vertices is stored as an array of ints (vertex numbers).

Path Length: The length of the above array.

In the priority queue (PmainQ), the vertex items are enqueued in ascending order of the Total Accumulated Distance values in the item vertices.

The item vertices are enqueued and dequeued form the PmainQ using a procedure similar to the BreadthFirst algorithm and is presented below.

You may use the code below as a guidance but I strongly encourage you to design your own algorithm

Enqueue the start vertex item in the priority queue: PmainQ.

Repeatedly: dequeue a vertex item and enqueue its adjacent vertex items as below

until the target vertex is found or the PmainQ becomes empty.

Dequeue a vertex item.

If (the dequeued vertex item is the target vertex item or PmainQ is empty)

go to step 3

Else

If it is not previously Marked Visited

Mark it visited.

Get a list of all its adjacent vertices.

Enqueue all adjacent vertices that are not previously marked visited into the PMainQ.

Algorithm

//The above methodology is presented below as an algorithm.

Enque the start vertex item in the PmainQ.

While ( !( PmainQ.isEmpty() ) )

{

Deque a vertex item from the PmainQ.

//Process the vertex item dequeued as follows.

If( vertex is unmarked )

{

If ( vertex is the target vertex )

break from the loop;

Mark the vertex as visited.

//Get a list of all its adjacent vertices by calling a method (say getAdjacent ) as below.

//(Note: getAdjacent returns adjacent vertices in a queue, adjacentQ, passed to it as below).

//(Note: getAdjacent returns vertices in order with the lowest numbered vertex first).

getAdjacent (vertex, adjacentQ)

//Process the adjacent vertices by dequeing them from the adjacent queue

//and enqueueing them in PmainQ as below.

While ( !( adjacentQ.isEmpty() ) )

{

Dequeue a vertex from adjacentQ.

If( adjacent vertex is unmarked )

{

Enqueue the adjacent vertex item in the PmainQ.

}

}

}

}

If the target vertex item is found,

Display the item contents including:

The total distance from the start vertex to the target vertex.

The list of all vertices along the above path.

Else

Display message: Vertex Not Found.

Another code example:

///***********************************************************

/// Purpose: Demonstration of implementing a graph as an

/// adjacency matrix

/// This code reads data from a text file which defines the

/// following undirected graph and adjacency matrix:

/// 0 1 2 3 4 5 6 7

/// (0) (1)---+ +---------------+

/// \ / | 0|0|0|1|0|0|0|0|0|

/// \ / | +---------------+

/// (2)---(3) | 1|0|0|0|1|0|0|0|1|

/// | |\ | +---------------+

/// | | \ | 2|1|0|0|1|0|1|0|0|

/// | | (4) | +---------------+

/// | | /| | 3|0|1|1|0|1|0|1|0|

/// | | / | | +---------------+

/// (5)---(6)--(7)--+ 4|0|0|0|1|0|0|1|1|

/// +---------------+

/// 5|0|0|1|0|0|0|1|0|

/// Graph structures are stored in +---------------+

/// an array. 6|0|0|0|1|1|1|0|1|

/// +---------------+

/// 7|0|1|0|0|1|0|1|0|

/// +---------------+

///***********************************************************

#include

#include /// Included to give access to atoi()

#include

#include

using namespace std;

#define NUMNODES 8

/// Structure used to define the graph nodes

struct Node

{

int index; /// Node number

char data[64]; /// Some data stored in the graph

};

bool getNextLine(ifstream& inF, char *line, int lineLen);

int main(void)

{

Node GraphNodes[NUMNODES]; /// Array of nodes in the graph

int AdjMatrix[NUMNODES][NUMNODES]; /// Matrix to define the graph links

ifstream inFile;

char line[81];

int i, j, idx, numLinks, link;

/// Initialize Adjacency Matrix to all 0s

for(i=0; i

for(j=0; j

AdjMatrix[i][j] = 0;

/// Try to open the file with the graph data

inFile.open("GraphData.txt", ios::in);

if(!inFile.is_open())

{

/// inFile.is_open() returns false if the file could not be found or

/// if for some other reason the open failed.

cout << "Unable to open file graph.txt. Program terminating... ";

return 1;

}

/// Since we know ahead of time there will be 8 nodes in the graph we can

/// read and skip the line giving the number of nodes.

getNextLine(inFile, line, 81);

/// Read all the graph data and build the adjacency matrix

for(i=0; i

{

/// Read the graph ID and use this as it's index in the graph

getNextLine(inFile, line, 81);

idx = atoi(line);

GraphNodes[idx].index = idx;

/// Read the graph string data and store it

getNextLine(inFile, line, 81);

strcpy(GraphNodes[idx].data, line);

/// Read the number of links for this node

getNextLine(inFile, line, 81);

numLinks = atoi(line);

/// Read all links and set the marker in the adjacency matrix

for(j=0; j

{

getNextLine(inFile, line, 81); /// Read next line

link = atoi(line); /// Get link index

AdjMatrix[idx][link] = 1; /// Set the link

}

}

inFile.close();

/// Print data for testing ...

cout << " Demonstration of a Graph implemented as an adjacency matrix. ";

cout << "(0) (1)---+ ";

cout << " \\ / | ";

cout << " \\ / | ";

cout << " (2)---(3) | ";

cout << " | |\\ | ";

cout << " | | \\ | ";

cout << " | | (4) | ";

cout << " | | /| | ";

cout << " | | / | | ";

cout << " (5)---(6)--(7)--+ ";

cout << " GRAPH DATA ";

cout << "------------------------------------------------------------ ";

cout << "Index Data String Links to ";

cout << "------------------------------------------------------------ ";

for(i=0; i

{

cout << " " << GraphNodes[i].index << " " <<

GraphNodes[i].data << "\t";

for(j=0; j

{

if(AdjMatrix[i][j] == 1)

cout << GraphNodes[j].index << " ";

}

cout << " "; /// end of line

}

cout << "------------------------------------------------------------ ";

cout << " Adjacency Matrix: ";

cout << " 0 1 2 3 4 5 6 7 ";

cout << " +---------------+ ";

for(i=0; i

{

cout << i << "|";

for(j=0; j

{

cout << AdjMatrix[i][j] << "|";

}

cout << " +---------------+ ";

}

return(0);

}

///-------------------------------------------

/// GetNextLine()

/// Read the next line from the file.

///-------------------------------------------

bool getNextLine(ifstream& inF, char *line, int lineLen)

{

int done = false;

while(!done)

{

inF.getline(line, lineLen);

if(inF.good()) /// If a line was successfully read

{

if(strlen(line) == 0) /// Skip any blank lines

continue;

else if(line[0] == '#') /// Skip any comment lines

continue;

else done = true; /// Got a valid data line so return with this line

}

else

{

strcpy(line, "");

return false; /// Flag end of file with null string

}

} /// end while

return true; /// Flag successful read

}