[Hama Wiki] Trivial Update of "SSSP" by edwardyoon

[Apache Wiki <wi...@apache.org>]

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 edwardyoon:
http://wiki.apache.org/hama/SSSP?action=diff&rev1=7&rev2=8

  == Single Source Shortest Paths ==
  
-  * Uses the SSSP algorithm described in the Google Pregel paper
+  * The SSSP algorithm described in the Google Pregel paper was used.
+  * Introduces IO usage, partitioning based on hashing of vertextID, and collective communication.
-  * Introduces partitioning and collective communication
-  * Lets the user submit his/her own SequenceFile to calculate the SSSP's
- 
  
  == Implementation ==
  
+ TODO: describe internal algorithm shows how it can be implemented using Hama BSP 
- 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 ==
  
+ TODO: 
- {{{
- 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 
-     Paris  / Berlin:25
- }}}
- 
- 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 or exceptions.
-  * you watch out for leading and trailing whitespaces in the names, this will cause vertices to not find each other! For instance "_Paris" is not "Paris".
-  * every adjacent vertex can be somewhere found within the SequenceFile as a key.
-  * 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
- 
- == Sample adjacency list SequenceFile ==
- 
- '''For HAMA-0.3.0:'''
- 
- You can download an adjacencylist SequenceFile containing 2,031,215 vertices and 24,787,849 edges, named with cities in the world and random weights. 
- It is arround 1.14GB large and can be downloaded here:
- 
- http://hama-shortest-paths.googlecode.com/svn/trunk/hama-gsoc/files/cities-adjacencylist/adjacencylist.seq2
- 
- You can run it with
- 
- {{{
- hama/bin/hama jar ../hama-0.x.0-examples.jar sssp Klewno sample/output PATH_TO_THE_SEQUENCEFILE
- }}}
- 
- Obviously you have to replace "PATH_TO_THE_SEQUENCEFILE" with the path where the sample file is stored.
- 
- You can adjust the starting vertex city (here: "Klewno") to the city you want, I'm pretty sure the graph contains it.
- 
- '''For versions newer than Hama-0.3.0'''
- 
- For the releases newer than Hama-0.3.0 we improved the partitioning and changed the SequenceFile to a TextFile.
- You can download it here:
- 
- http://hama-shortest-paths.googlecode.com/svn/trunk/hama-gsoc/files/cities-adjacencylist/sssp-adjacencylist.txt
- 
- You can run it with
- 
- {{{
- hama/bin/hama jar ../hama-0.x.0-examples.jar sssp Klewno sample/output PATH_TO_THE_TXT_FILE
- }}}
- 
- Obviously you have to replace "PATH_TO_THE_TXT_FILE" with the path where the sample file is stored.
- This file contains the same vertices as the sequencefile above.
  
  Have fun! If you are facing problems, feel free to ask questions on the official mailing list.