Code for Moore's algorithm by Mark DiLascio

I wrote my program in C++ it read in an adjacency matrix from an infile and then sent the results to an outfile. I will post both files and my source code below. Also please note my programming skills are pretty weak.

Infile
0 1 0 0 0 0
1 0 1 0 1 0
0 1 0 1 0 0
0 0 1 0 1 0
0 1 0 1 0 1
0 0 0 0 1 0

Outfile
Here is the adjacency matrix used in this example.

0 1 0 0 0 0
1 0 1 0 1 0
0 1 0 1 0 0
0 0 1 0 1 0
0 1 0 1 0 1
0 0 0 0 1 0

This shows the distances away from A.

A B C D E F
0 1 2 3 2 3

The distance from point A to point F is 3!!

Code
/*
Mark DiLascio 20038889
Math 2346
Programming assignment 1
3/25/2012

This program takes an ajacency matrix and reads it into the program. The program then
conducts Moore's algorithm to that finds the shortest path between 2 verticies in a
graph. All edges must be the same length inorder to use Moore's algorithm.in this case we
are trying to find the distance between A and F.
This program is only intended to be used for the provided adjacency matrix in adjacency.txt
It worked for several other examples but more than likely will not work for all examples.
*/

#include <iostream> //declarations

#include <fstream>

#include <iomanip>

using namespace std;

int main()

{

int h, l, x; // variables

int dist [6]; // array for tracking distance

ofstream outfile;

ifstream infile;

outfile.open ("results.txt" , ios::app); // opens outfile

for (x=0; x<6; x=x+1) // initilizes all distances as zero.
{
dist [x] = 0;

}

outfile « "Here is the adjacency matrix used in this example."« endl « endl; // second endl is added for ease in reading outfile.

for(h=0; h<6; h=h+1) // This for loop reads in the adjacency matrix into an array
{ // int h represents the rows
for (l=0; l<6; l=l+1) // int l represents the columns
{
outfile « adj [h] [l] « " ";
}

outfile « endl;
} // This ends the section where the matrix is read in.

outfile « endl;

// Converts matrix to a triangular matrix. This is the first step needed to run my version of moore's algorithm.
// This only removes repeated data.
for(h=0; h<6; h=h+1)
{
for (l=0; l<6; l=l+1)
{
if (adj [h] [l] == 1) //removing redundant data to make my life easier!
{
}

}
}
// end conversion
// begin outputting new matrix

/*for(h=0; h<6; h=h+1) I decided for neatness of the outfile i would comment this section out.
{
for (l=0; l<6; l=l+1)
{outfile « adj [h] [l] « " ";
}
outfile « endl;
}
*/
end output

for (l=0; l<6; l=l+1) // For my algorithm the program begins in column 0 and then moves vertically down the matrix. When a
{ // connecting edge is discovered, (a 1 in the adjacency matrix) it takes that position and then checks
for (h=0; h<6; h=h+1) // it against the distance array. it takes the column number and then checks the distance matrix for the
{ // number in the row numbers location of the distance matrix. It then takes that number adds one and
if(adj [h] [l] == 1) // saves it as the distance for the column number.
{
if(dist [h]+1 < dist [l] || dist [l] == 0)
{
dist [l] = dist [h]+1; // saves the distance of the point on the graph in the distance matrix.

}
}
}
}

// Begins outputting the distance matrix. This shows the distance that all verticies are away from point A.
outfile « "This shows the distances away from A." « endl « endl; // labling of distance matrix

outfile « "A B C D E F" « endl; // labling of distance matrix

for (x=0; x<6; x=x+1) // outputting distance matrix
{

outfile « dist [x] « " ";
}

outfile « endl « endl; // for neatness of outfile.
outfile « "The distance from point A to point F is " « dist [5] « "!!" « endl;

return 0;
}

page revision: 2, last edited: 02 Apr 2012 18:02