sssp command

sssp2 command

Syntax:

sssp N seed -i in1 -o out1.file out1.mr 

sssp2 N seed -i in1 -o out1.file out1.mr 

• N = # of random starting vertices to choose
• seed = random number seed (positive integer)
• in1 = graph edges: Key = Vi Vj, Value = weight
• out1 = distance to each vertex: Key = Vi, Value = distance

Examples:

sssp 10 12345 -i mre -o sssp.dist mrdist
sssp2 10 12345 -i mre -o sssp.dist mrdist 

Description:

These are named commands which compute the shortest path to each vertex from a source vertex in an undirected graph. This is called a single-source shortest-path (SSSP) calculation. The source vertex is selected randomly. Each edge in the graph has a weight. The shortest-path distance to any other vertex is the minimum summed weight of a list of consecutive edges that connect the two vertices.

This calculation involves a breadth-first search on the graph. The MapReduce algorithms used for performing the SSSP calculation are described in the paper of (Plimpton). The sssp command implements the first of the two algorithms discussed in the paper. The sssp2 command implements the second of the two algorithms.

See the named command doc page for various ways in which the -i inputs and -o outputs for a named command can be specified.

In1 stores a set of edges with floating point weights, assumed to have no duplicates or self-edges. This means that either (Vi,Vj) or (Vj,Vi) appears, but not both. Also (Vi,Vi) does not appear. The input is unchanged by this command.

Out1 will store the list of vertices and the distance to each vertex. If the specified N > 1, then this will be the SSSP result for only the last source vertex randomly selected.

Related commands: none

(Plimpton) Plimpton and Devine, "MapReduce in MPI for Large-Scale Graph Algorithms", to appear in Parallel Computing (2011).