The graph500 benchmark is a relatively new benchmark which times the generation and standard BFS for large undirected graphs. A BFS of a graph assumes that the graph’s edges are the same unit length and can be directed or undirected. Dasgupta et.al. have a useful method for converting an graph G with unit lengths into
I am working on a version of this problem using distributed shared memory languages such as UPC.
I will post my code and results here when it’s done!
Shortest Paths
Below is an implementation that is easy to check, of Prims algorithm to find a minimum spanning tree on an undirected graph with randomly generated edge weights. These algorithms are useful in finding solutions to the Traveling salesman problem, which has been proven NP-Hard.
Graph1: Random distances (cost between 1-10) of an undirected graph of 5 nodes.
Solution of Graph 1 using Prims algorithm.
Increasing the number of nodes to only fifteen makes the Graph very difficult to check, but we can still find a solution.
And the solution for the 15 node case shows we can traverse all nodes with a minimum distance of 36.
I use Prim’s algorithm within MPI programs to determine the bandwidth between all of the nodes of my particular jobs, then I restructure my graph to place heavier communication on the fastest links. This works well for heterogeneous systems when I have long running jobs, 2 days or more, but doesn’t provide much performance benefit when all links are relatively the same and my job only runs for a few minutes or hours. I also use an Ant algorithm to move data around poor performing links, particularly when doing a lot of parallel I/O.
Below is the code for generating a random undirected graph, you can comment out the inp_gen() function and provide your own graph as “weights.inp” which could look something like the following adjacency matrix where the first line represents the number of nodes.
4
0 0 0 21
0 0 8 17
0 8 0 16
21 17 16 0
prims_undirected
For a directed graph with 20 nodes, use the code below:
prims_directed