incubator-hama-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Apache Wiki <wikidi...@apache.org>
Subject [Hama Wiki] Update of "SSSP" by thomasjungblut
Date Sat, 07 May 2011 17:42:11 GMT
Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Hama Wiki" for change notification.

The "SSSP" page has been changed by thomasjungblut.
http://wiki.apache.org/hama/SSSP

--------------------------------------------------

New page:
== Single Source Shortest Paths ==

 * Uses the SSSP algorithm described in the Google Pregel paper
 * Introduces partitioning and collective communication
 * Lets the user submit his/her own SequenceFile to calculate the SSSP's


== Implementation ==

For detailed questions in terms of implementation have a look at my blog.
It describes the algorithm and focuses on the main ideas showing implementation things.

http://codingwiththomas.blogspot.com/2011/05/shortest-path-finding-with-apache-hama.html

== Usage ==

{{{
hama/bin/hama jar ../hama-0.x.0-examples.jar sssp <name of the start vertex> <optional:
output path> <optional: path of your own sequencefile>
}}}

Change "x" to the version you are using!

Note: If you provide your own sequencefile, make sure you've set the output path.

'''The output path should never be the root path!'''

== Submit your own Graph ==

You can transform your graph as a adjacency list to fit into the input which Hama is going
to parse and calculate the shortest paths between the vertices.

The file that Hama can successfully parse is a SequenceFile that contains both Key and Value
as a Text. 

{{{
  K           /                V 
Vertex[Text] / AdjacentVertex : Weight [Text]
}}}

A vertex typically contains a name that uniquely identifies a vertex. So you are associating
a key vertex that just contains a name to another vertex (that contains its name) to the weight.
Both seperated by ":".

Let's look at this sample:

{{{
      K    /   V
    Berlin /  Paris : 25
    Berlin / London : 40
    London / Paris : 10
}}}

This will adjacent Berlin to Paris and London, and London to Paris with the given weights.

If you are familiar with MapReduce, this looks like a mapper output that can be easily reduced.


'''Notes:'''

Make sure...

 * your names are unique! Otherwise it will result in strange output.
 * it is only ONE file!
 * Key and Value are Text.class fields!
  * Value always contains only ONE vertex
  * Value is separated by ":" to split the name and the weight

Have fun! If you are facing problems, feel free to ask questions on the official mailing list.

Mime
View raw message