CMPT431 Project: All-Pairs Shortest Path

Group: 31

Members:

• Ben Smus
• Terence Cheung
• Lily Yang

Input Graph Data

To test the system, you would first need to generate the data you want and the expectation is that the graph is going to be weighted directed/undirected graph. If there's no path from A -> B, then you should represent the weight as i which means infinity.

For simplicity, we've created a python script called random_graph.py which will allow you to create a graph of any size to test the program with.

Here's the command to generate input graphs of various sizes:

python3 input_graph/random_graph.py 100 ./input_graph/random_graph_100.txt

We've already generated input graph sizes of 50, 100, 200 ... 3000 for our experiments so you can use the prebuilt sample graphs when running the program or you can generate your own using the command above.

Running the program

We assume you will be running these commands at the root of your directory, if you are not, please make sure you are.

# this is needed so that output files can write to this directory
mkdir -p distance_matrix

# if you want to print the before and after shortest distance on a selected set of vertices to verify correctness you can use this when building the executables
# we've built into the system to print 6 sets of vertices only so you can compare serial, parallel and distributed versions for correctness

make PRINT=1

# if you don't want to see the distances of 6 sets of vertices as part of your output, just run this to build the executables

make all

# running the serial version using random_graph_1000.txt

./floyd_serial_threaded --mode 0 --inputFile=./input_graph/random_graph_1000.txt --outputFile=./distance_matrix/random_graph_serial_1000.txt

# running the parallel version using random_graph_1000.txt with 4 threads

./floyd_serial_threaded --np 4 --mode 1 --inputFile=./input_graph/random_graph_1000.txt --outputFile=./distance_matrix/random_graph_parallel_1000.txt

# running the distributed version of the program, you will need to submit the slurm script we provided
# we have set up the slurm script to run on 4 processes, and using the same input data of 1000 nodes

sbatch project_slurm.script

# Once you have generated the file which contains the distance matrix, you can print out the actual shortest path between any pair of vertices.
# E.g. between start=3, end=2:

./print_shortest_path --graph=./input_graph/random_graph_1000.txt --distances=./distance_matrix/random_graph_parallel_1000.txt --start=3 --end=2

Verifying correctness of the program

With the make PRINT=1 option, you will only get a selected set of vertices to make checking for correctness visually easier, but if you want to make sure the entire distance matrix result is correct, you can use the diff tool

You must first complete the section Running the program so you can get the output file with the resulting matrix of all pairs shortest paths.

Testing is done by comparing output from the serial implementation with output file produced by complicated program.

So when you run the serial program on an input file and generate an output file, and then run (for example) the mpi program on an input file and generate an output file, those files should be identical.

diff -w ./distance_matrix/random_graph_serial_1000.txt ./distance_matrix/random_graph_parallel_1000.txt

diff -w ./distance_matrix/random_graph_serial_1000.txt ./distance_matrix/random_graph_distrib_1000.txt

# there shouldn't be any diffs when you run the 2 commands above which shows to you that the programs are generating correct results