You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hama.apache.org by ed...@apache.org on 2012/03/16 11:22:38 UTC
svn commit: r1301419 - in /incubator/hama/trunk: CHANGES.txt
graph/src/main/java/org/apache/hama/graph/VertexInterface.java
src/site/site.xml src/site/xdoc/hama_graph_tutorial.xml
src/site/xdoc/index.xml
Author: edwardyoon
Date: Fri Mar 16 10:22:37 2012
New Revision: 1301419
URL: http://svn.apache.org/viewvc?rev=1301419&view=rev
Log:
Add documentation for Graph package
Added:
incubator/hama/trunk/src/site/xdoc/hama_graph_tutorial.xml (with props)
Modified:
incubator/hama/trunk/CHANGES.txt
incubator/hama/trunk/graph/src/main/java/org/apache/hama/graph/VertexInterface.java
incubator/hama/trunk/src/site/site.xml
incubator/hama/trunk/src/site/xdoc/index.xml
Modified: incubator/hama/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/CHANGES.txt?rev=1301419&r1=1301418&r2=1301419&view=diff
==============================================================================
--- incubator/hama/trunk/CHANGES.txt (original)
+++ incubator/hama/trunk/CHANGES.txt Fri Mar 16 10:22:37 2012
@@ -4,6 +4,7 @@ Release 0.5 - Unreleased
NEW FEATURES
+ HAMA-517: Add documentation for Graph package (edwardyoon)
HAMA-518: Add MinIntCombiner to SSSP example (edwardyoon)
HAMA-367: Runtime Compression of BSP Messages to Improve the Performance (Apurv Verma via tjungblut)
HAMA-501: Add Avro RPC (tjungblut)
Modified: incubator/hama/trunk/graph/src/main/java/org/apache/hama/graph/VertexInterface.java
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/graph/src/main/java/org/apache/hama/graph/VertexInterface.java?rev=1301419&r1=1301418&r2=1301419&view=diff
==============================================================================
--- incubator/hama/trunk/graph/src/main/java/org/apache/hama/graph/VertexInterface.java (original)
+++ incubator/hama/trunk/graph/src/main/java/org/apache/hama/graph/VertexInterface.java Fri Mar 16 10:22:37 2012
@@ -25,23 +25,31 @@ import org.apache.hadoop.io.Writable;
public interface VertexInterface<MSGTYPE extends Writable> {
- /**
- * @return the vertex ID.
- */
+ /** @return the unique identification for the vertex. */
public String getVertexID();
-
+ /** @return the number of vertices in the input graph. */
+ public long getNumVertices();
+ /** The user-defined function */
public void compute(Iterator<MSGTYPE> messages) throws IOException;
-
+ /** @return a list of outgoing edges of this vertex in the input graph. */
public List<Edge> getOutEdges();
-
+ /** Sends a message to another vertex. */
public void sendMessage(Edge e, MSGTYPE msg) throws IOException;
-
+ /** Sends a message to neighbors */
public void sendMessageToNeighbors(MSGTYPE msg) throws IOException;
-
+ /** @return the superstep number of the current superstep (starting from 0). */
public long getSuperstepCount();
-
+ /**
+ * Sets the vertex value
+ *
+ * @param value
+ */
public void setValue(MSGTYPE value);
-
+ /**
+ * Gets the vertex value
+ *
+ * @return value
+ */
public MSGTYPE getValue();
}
Modified: incubator/hama/trunk/src/site/site.xml
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/site/site.xml?rev=1301419&r1=1301418&r2=1301419&view=diff
==============================================================================
--- incubator/hama/trunk/src/site/site.xml (original)
+++ incubator/hama/trunk/src/site/site.xml Fri Mar 16 10:22:37 2012
@@ -68,6 +68,7 @@
<item name="Getting Started" href="getting_started_with_hama.html" />
<item name="Hama on Clouds" href="hama_on_clouds.html" />
<item name="Hama BSP tutorial" href="hama_bsp_tutorial.html" />
+ <item name="Hama Graph tutorial" href="hama_graph_tutorial.html" />
<item name="Benchmarks" href="http://wiki.apache.org/hama/Benchmarks" />
<item name="Presentations" href="http://wiki.apache.org/hama/Presentations" />
<item name="Research Papers" href="http://wiki.apache.org/hama/Articles" />
Added: incubator/hama/trunk/src/site/xdoc/hama_graph_tutorial.xml
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/site/xdoc/hama_graph_tutorial.xml?rev=1301419&view=auto
==============================================================================
--- incubator/hama/trunk/src/site/xdoc/hama_graph_tutorial.xml (added)
+++ incubator/hama/trunk/src/site/xdoc/hama_graph_tutorial.xml Fri Mar 16 10:22:37 2012
@@ -0,0 +1,109 @@
+<?xml version="1.0" encoding="iso-8859-1"?>
+<!--
+ Licensed to the Apache Software Foundation (ASF) under one or more
+ contributor license agreements. See the NOTICE file distributed with
+ this work for additional information regarding copyright ownership.
+ The ASF licenses this file to You under the Apache License, Version 2.0
+ (the "License"); you may not use this file except in compliance with
+ the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+-->
+<document xmlns="http://maven.apache.org/XDOC/2.0"
+xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+xsi:schemaLocation="http://maven.apache.org/XDOC/2.0 http://maven.apache.org/xsd/xdoc-2.0.xsd">
+ <properties></properties>
+ <title>Graph Tutorial</title>
+ <body>
+ <section name="Hama Graph Tutorial"></section>
+ <p>This document describes the Graph computing framework and serves as a tutorial.</p>
+ <subsection name="Overview"></subsection>
+ <p>Hama includes the Graph package for vertex-centric graph computations.
+ Hama's Graph package allows you to program Google's Pregel style applications with simple programming interface.</p>
+
+ <subsection name="Vertex API"></subsection>
+
+ <p>Writing a Hama graph application involves subclassing the predefined Vertex class. Its template arguments define message value type.</p>
+ <pre class="green">
+ public abstract class Vertex<M extends Writable> implements VertexInterface<M> {
+
+ public void compute(Iterator<MSGTYPE> messages) throws IOException;
+ ..
+
+ }</pre>
+
+ <p>The user overrides the Compute() method, which will be executed at each active vertex in every superstep. Predefined Vertex methods allow Compute() to query information about the current vertex and its edges, and to send messages to other vertices. Compute() can inspect the value associated with its vertex via GetValue().</p>
+
+ <subsection name="Example: PageRankVertex"></subsection>
+ <p>To solve the Page Rank problem using Hama Graph, you can extends the Vertex class to create a PageRankVertex class.
+In this example, the algorithm described Google's Pregel paper was used. The value of a vertex represents the tentative page rank of the vertex. The graph is intialized with each vertex value equal to 1/numOfVertices. In each of the first 30 supersteps, each vertex sends its tentative page rank along all of its outgoing edges.
+<br/><br/>
+From Superstep 1 to 30, each vertex sums up the values arriving on all its messages and sets its tentative page rank to (1 - 0.85) / numOfVertices + (0.85 * sum).
+ </p>
+
+ <pre class="green">
+ public static class PageRankVertex extends Vertex<DoubleWritable> {
+
+ @Override
+ public void compute(Iterator<DoubleWritable> messages) throws IOException {
+ if (this.getSuperstepCount() == 0) {
+ this.setValue(new DoubleWritable(1.0 / (double) this.getNumVertices()));
+ }
+
+ if (this.getSuperstepCount() >= 1) {
+ double sum = 0;
+ while (messages.hasNext()) {
+ DoubleWritable msg = messages.next();
+ sum += msg.get();
+ }
+
+ double ALPHA = (1 - 0.85) / (double) this.getNumVertices();
+ this.setValue(new DoubleWritable(ALPHA + (0.85 * sum)));
+ }
+
+ if (this.getSuperstepCount() < this.getMaxIteration()) {
+ int numEdges = this.getOutEdges().size();
+ sendMessageToNeighbors(new DoubleWritable(this.getValue().get()
+ / numEdges));
+ }
+ }
+
+ public static void main(String[] args) throws IOException,
+ InterruptedException, ClassNotFoundException {
+ HamaConfiguration conf = new HamaConfiguration(new Configuration());
+ GraphJob pageJob = new GraphJob(conf, PageRank.class);
+ pageJob.setJobName("Pagerank");
+
+ pageJob.setVertexClass(PageRankVertex.class);
+ pageJob.setMaxIteration(30);
+
+ pageJob.setInputPath(new Path(args[0]));
+ pageJob.setOutputPath(new Path(args[1]));
+
+ if (args.length == 3) {
+ pageJob.setNumBspTask(Integer.parseInt(args[2]));
+ }
+
+ pageJob.setInputFormat(SequenceFileInputFormat.class);
+ pageJob.setPartitioner(HashPartitioner.class);
+ pageJob.setOutputFormat(SequenceFileOutputFormat.class);
+ pageJob.setOutputKeyClass(Text.class);
+ pageJob.setOutputValueClass(DoubleWritable.class);
+
+ long startTime = System.currentTimeMillis();
+ if (pageJob.waitForCompletion(true)) {
+ System.out.println("Job Finished in "
+ + (double) (System.currentTimeMillis() - startTime) / 1000.0
+ + " seconds");
+ }
+ }
+ }</pre>
+
+ </body>
+</document>
Propchange: incubator/hama/trunk/src/site/xdoc/hama_graph_tutorial.xml
------------------------------------------------------------------------------
svn:eol-style = native
Modified: incubator/hama/trunk/src/site/xdoc/index.xml
URL: http://svn.apache.org/viewvc/incubator/hama/trunk/src/site/xdoc/index.xml?rev=1301419&r1=1301418&r2=1301419&view=diff
==============================================================================
--- incubator/hama/trunk/src/site/xdoc/index.xml (original)
+++ incubator/hama/trunk/src/site/xdoc/index.xml Fri Mar 16 10:22:37 2012
@@ -66,6 +66,7 @@ xsi:schemaLocation="http://maven.apache.
<li><a href="getting_started_with_hama.html">Getting Started</a> with Hama.</li>
<li><a href="hama_on_clouds.html">Launch a Hama cluster</a> on Clouds.</li>
<li>Hama <a href="hama_bsp_tutorial.html">BSP Tutorial.</a></li>
+ <li>Hama <a href="hama_graph_tutorial.html">Graph Tutorial.</a></li>
<li><a href="http://wiki.apache.org/hama">Learn about</a> Hama and BSP by reading the documentation.</li>
</ul>
<subsection name="Getting Involved"></subsection>