You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@giraph.apache.org by ed...@apache.org on 2014/12/08 20:21:42 UTC
[7/9] git commit: updated refs/heads/trunk to 8675c84
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/package-info.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/package-info.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/package-info.java
new file mode 100644
index 0000000..b50f00f
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/package-info.java
@@ -0,0 +1,22 @@
+/*
+ * 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.
+ */
+
+/**
+ * Instrumentation results of the example Giraph programs.
+ */
+package org.apache.giraph.debugger.examples.instrumented;
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/BuggyConnectedComponentsComputation.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/BuggyConnectedComponentsComputation.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/BuggyConnectedComponentsComputation.java
new file mode 100644
index 0000000..1a83a0e
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/BuggyConnectedComponentsComputation.java
@@ -0,0 +1,99 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.integrity;
+
+import java.io.IOException;
+
+import org.apache.giraph.edge.Edge;
+import org.apache.giraph.graph.BasicComputation;
+import org.apache.giraph.graph.Vertex;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.NullWritable;
+
+/**
+ * Implementation of the HCC algorithm that identifies connected components and
+ * assigns each vertex its "component identifier" (the smallest vertex id in the
+ * component)
+ *
+ * The idea behind the algorithm is very simple: propagate the smallest vertex
+ * id along the edges to all vertices of a connected component. The number of
+ * supersteps necessary is equal to the length of the maximum diameter of all
+ * components + 1
+ *
+ * The original Hadoop-based variant of this algorithm was proposed by Kang,
+ * Charalampos, Tsourakakis and Faloutsos in
+ * "PEGASUS: Mining Peta-Scale Graphs", 2010
+ *
+ * http://www.cs.cmu.edu/~ukang/papers/PegasusKAIS.pdf
+ */
+public class BuggyConnectedComponentsComputation extends
+ BasicComputation<LongWritable, LongWritable, NullWritable, LongWritable> {
+
+ /**
+ * Propagates the smallest vertex id to all neighbors. Will always choose to
+ * halt and only reactivate if a smaller id has been sent to it.
+ *
+ * @param vertex
+ * Vertex
+ * @param messages
+ * Iterator of messages from the previous superstep.
+ * @throws IOException
+ */
+ @Override
+ public void compute(Vertex<LongWritable, LongWritable, NullWritable> vertex,
+ Iterable<LongWritable> messages) throws IOException {
+ long currentComponent = vertex.getValue().get();
+
+ if (getSuperstep() == 0) {
+ vertex.setValue(vertex.getId());
+ for (Edge<LongWritable, NullWritable> edge : vertex.getEdges()) {
+ sendMessage(edge.getTargetVertexId(), vertex.getValue());
+ }
+ vertex.voteToHalt();
+ return;
+ }
+
+ boolean changed = false;
+ // did we get a smaller id ?
+ for (LongWritable message : messages) {
+ long candidateComponent = message.get();
+ // INTENTIONAL BUG: in the original algorithm the value of the comparison
+ // sign should be <.
+ // We note that this algorithm will end up finding the components
+ // correctly, but the ID of
+ // each component will be the minimum vertex ID in the component.
+ // In the original
+ // org.apache.giraph.examples.ConnectedComponentsComputation, the ID of
+ // each
+ // component is the maximum vertex ID in the component.
+ if (candidateComponent > currentComponent) {
+ currentComponent = candidateComponent;
+ changed = true;
+ }
+ }
+
+ // propagate new component id to the neighbors
+ if (changed) {
+ vertex.setValue(new LongWritable(currentComponent));
+ for (Edge<LongWritable, NullWritable> edge : vertex.getEdges()) {
+ sendMessage(edge.getTargetVertexId(), vertex.getValue());
+ }
+ }
+ vertex.voteToHalt();
+ }
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/CCFindingMissingReverseEdgeMsgIntegrityDebugConfig.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/CCFindingMissingReverseEdgeMsgIntegrityDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/CCFindingMissingReverseEdgeMsgIntegrityDebugConfig.java
new file mode 100644
index 0000000..ea1e056
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/CCFindingMissingReverseEdgeMsgIntegrityDebugConfig.java
@@ -0,0 +1,47 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.integrity;
+
+import org.apache.giraph.debugger.DebugConfig;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.NullWritable;
+
+/**
+ * Debug configuration file for ConnectedComponents, that is configured to check
+ * that in the second superstep, the value of a message sent from vertex u to v
+ * has to be greater than or equal to v's ID.
+ */
+public class CCFindingMissingReverseEdgeMsgIntegrityDebugConfig extends
+ DebugConfig<LongWritable, LongWritable, NullWritable, LongWritable,
+ LongWritable> {
+
+ @Override
+ public boolean shouldCheckMessageIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isMessageCorrect(LongWritable srcId, LongWritable dstId,
+ LongWritable message, long superstepNo) {
+ if (superstepNo == 1) {
+ return message.get() >= dstId.get();
+ } else {
+ return true;
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsDebugConfig.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsDebugConfig.java
new file mode 100644
index 0000000..5bb490a
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsDebugConfig.java
@@ -0,0 +1,55 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.integrity;
+
+import org.apache.giraph.debugger.DebugConfig;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.NullWritable;
+
+/**
+ * Debug configuration file for ConnectedComponents, that is configured to check
+ * the integrity of the vertex values: The current check is that the vertex
+ * value is less than or equal to the id of the vertex.
+ */
+public class ConnectedComponentsDebugConfig extends
+ DebugConfig<LongWritable, LongWritable, NullWritable, LongWritable,
+ LongWritable> {
+
+ @Override
+ public boolean shouldCheckVertexValueIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isVertexValueCorrect(LongWritable vertexId,
+ LongWritable value) {
+ return value.get() <= vertexId.get();
+ }
+
+ @Override
+ public boolean shouldCheckMessageIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isMessageCorrect(LongWritable srcId, LongWritable dstId,
+ LongWritable message, long superstepNo) {
+ return message.get() <= srcId.get();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsMsgIntegrityDebugConfig.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsMsgIntegrityDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsMsgIntegrityDebugConfig.java
new file mode 100644
index 0000000..61641a9
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsMsgIntegrityDebugConfig.java
@@ -0,0 +1,54 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.integrity;
+
+import org.apache.giraph.debugger.DebugConfig;
+import org.apache.giraph.graph.Vertex;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.NullWritable;
+
+/**
+ * Debug configuration file for ConnectedComponents, that is configured to check
+ * the integrity of the messages sent: The current check is that the message
+ * value is less than or equal to the id of the source vertex.
+ */
+public class ConnectedComponentsMsgIntegrityDebugConfig extends DebugConfig<
+ LongWritable, LongWritable, NullWritable, LongWritable, LongWritable> {
+
+ @Override
+ public boolean shouldCatchExceptions() {
+ return false;
+ }
+
+ @Override
+ public boolean shouldDebugVertex(
+ Vertex<LongWritable, LongWritable, NullWritable> vertex, long superstepNo) {
+ return false;
+ }
+
+ @Override
+ public boolean shouldCheckMessageIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isMessageCorrect(LongWritable srcId, LongWritable dstId,
+ LongWritable message, long superstepNo) {
+ return message.get() <= srcId.get();
+ }
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsRandomVerticesDebugConfig.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsRandomVerticesDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsRandomVerticesDebugConfig.java
new file mode 100644
index 0000000..f737739
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsRandomVerticesDebugConfig.java
@@ -0,0 +1,38 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.integrity;
+
+import org.apache.giraph.debugger.DebugConfig;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.NullWritable;
+
+/**
+ * Debug configuration file for ConnectedComponents, that is configured to
+ * capture a random set of 10 vertices.
+ */
+public class ConnectedComponentsRandomVerticesDebugConfig extends DebugConfig<
+ LongWritable, LongWritable, NullWritable, LongWritable, LongWritable> {
+
+ /**
+ * @return the number of random vertices that Graft should capture, which is
+ * set to 10 in our case.
+ */
+ public int numberOfRandomVerticesToCapture() {
+ return 10;
+ }
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsVValueIntegrityDebugConfig.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsVValueIntegrityDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsVValueIntegrityDebugConfig.java
new file mode 100644
index 0000000..ff01276
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/ConnectedComponentsVValueIntegrityDebugConfig.java
@@ -0,0 +1,54 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.integrity;
+
+import org.apache.giraph.debugger.DebugConfig;
+import org.apache.giraph.graph.Vertex;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.NullWritable;
+
+/**
+ * Debug configuration file for ConnectedComponents, that is configured to check
+ * the integrity of the vertex values: The current check is that the vertex
+ * value is less than or equal to the id of the vertex.
+ */
+public class ConnectedComponentsVValueIntegrityDebugConfig extends DebugConfig<
+ LongWritable, LongWritable, NullWritable, LongWritable, LongWritable> {
+
+ @Override
+ public boolean shouldCatchExceptions() {
+ return false;
+ }
+
+ @Override
+ public boolean shouldDebugVertex(
+ Vertex<LongWritable, LongWritable, NullWritable> vertex, long superstepNo) {
+ return false;
+ };
+
+ @Override
+ public boolean shouldCheckVertexValueIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isVertexValueCorrect(LongWritable vertexId, LongWritable
+ value) {
+ return value.get() <= vertexId.get();
+ }
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/package-info.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/package-info.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/package-info.java
new file mode 100644
index 0000000..8b944af
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/integrity/package-info.java
@@ -0,0 +1,24 @@
+/*
+ * 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.
+ */
+
+/**
+ * An example Giraph program to be debugged using Graft's integrity check
+ * functionality.
+ */
+package org.apache.giraph.debugger.examples.integrity;
+
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMComputation.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMComputation.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMComputation.java
new file mode 100644
index 0000000..f212c66
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMComputation.java
@@ -0,0 +1,111 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.mwm;
+
+import java.io.IOException;
+
+import org.apache.giraph.edge.Edge;
+import org.apache.giraph.graph.BasicComputation;
+import org.apache.giraph.graph.Vertex;
+import org.apache.hadoop.io.DoubleWritable;
+import org.apache.hadoop.io.LongWritable;
+
+/**
+ * The implementation of an approximate maximum weight matching algorithm.
+ * Vertices pick their max-weight neighbors and if two vertices u and v pick
+ * each other, they are matched and removed from the graph. Edges
+ * pointing to u and v are also removed from the graph.
+ */
+public class MWMComputation extends
+ BasicComputation<LongWritable, VertexValue, DoubleWritable, LongWritable> {
+
+ @Override
+ public void compute(Vertex<LongWritable, VertexValue, DoubleWritable> vertex,
+ Iterable<LongWritable> messages) throws IOException {
+ if (getSuperstep() > 500) {
+ vertex.voteToHalt();
+ }
+ long phase = getSuperstep() % 2;
+ if (vertex.getValue().isMatched() || vertex.getNumEdges() == 0) {
+ vertex.voteToHalt();
+ return;
+ }
+ if (phase == 0) {
+ removeEdges(vertex, messages);
+ if (vertex.getNumEdges() == 0) {
+ vertex.voteToHalt();
+ return;
+ }
+ long maxValueVertexID = pickMaxValueVertex(vertex);
+ vertex.getValue().setMatchedID(maxValueVertexID);
+ vertex.setValue(vertex.getValue());
+ sendMessage(new LongWritable(maxValueVertexID), vertex.getId());
+ } else if (phase == 1) {
+ long matchedID = vertex.getValue().getMatchedID();
+ boolean isMatched = false;
+ for (LongWritable matchingVertexID : messages) {
+ if (matchingVertexID.get() == matchedID) {
+ isMatched = true;
+ break;
+ }
+ }
+ if (isMatched) {
+ vertex.getValue().setMatched(true);
+ vertex.setValue(vertex.getValue());
+ sendMessageToAllEdges(vertex, vertex.getId());
+ vertex.voteToHalt();
+ }
+ }
+ }
+
+ /**
+ * Remove edges.
+ *
+ * @param vertex the vertex
+ * @param messages the incoming messages
+ */
+ private void removeEdges(
+ Vertex<LongWritable, VertexValue, DoubleWritable> vertex,
+ Iterable<LongWritable> messages) {
+ for (LongWritable matchedNbr : messages) {
+ vertex.removeEdges(matchedNbr);
+ }
+ }
+
+ /**
+ * @param vertex the vertex
+ * @return the max id among neighbor vertices
+ */
+ private long pickMaxValueVertex(
+ Vertex<LongWritable, VertexValue, DoubleWritable> vertex) {
+ long maxWeightNbrID = -1;
+ double maxWeight = -1.0;
+ for (Edge<LongWritable, DoubleWritable> edge : vertex.getEdges()) {
+ if (maxWeightNbrID == -1) {
+ maxWeightNbrID = edge.getTargetVertexId().get();
+ maxWeight = edge.getValue().get();
+ } else {
+ if (edge.getValue().get() > maxWeight) {
+ maxWeightNbrID = edge.getTargetVertexId().get();
+ maxWeight = edge.getValue().get();
+ }
+ }
+ }
+ return maxWeightNbrID;
+ }
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMDebugConfig.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMDebugConfig.java
new file mode 100644
index 0000000..863a1c7
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMDebugConfig.java
@@ -0,0 +1,54 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.mwm;
+
+import org.apache.giraph.debugger.DebugConfig;
+import org.apache.hadoop.io.DoubleWritable;
+import org.apache.hadoop.io.LongWritable;
+
+/**
+ * DebugConfig for max weight matching.
+ */
+public class MWMDebugConfig
+ extends
+ DebugConfig<LongWritable, VertexValue, DoubleWritable, LongWritable,
+ LongWritable> {
+
+ @Override
+ public boolean shouldCheckVertexValueIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isVertexValueCorrect(LongWritable vertexId,
+ VertexValue value) {
+ return value.getMatchedID() != vertexId.get();
+ }
+
+ @Override
+ public boolean shouldCheckMessageIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isMessageCorrect(LongWritable srcId, LongWritable dstId,
+ LongWritable message, long superstepNo) {
+ return message.get() == srcId.get();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMMessageConstraintDebugConfig.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMMessageConstraintDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMMessageConstraintDebugConfig.java
new file mode 100644
index 0000000..e90ea25
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMMessageConstraintDebugConfig.java
@@ -0,0 +1,43 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.mwm;
+
+import org.apache.giraph.debugger.DebugConfig;
+import org.apache.hadoop.io.DoubleWritable;
+import org.apache.hadoop.io.LongWritable;
+
+/**
+ * DebugConfig for checking message constraints of max weight matching.
+ */
+public class MWMMessageConstraintDebugConfig
+ extends
+ DebugConfig<LongWritable, VertexValue, DoubleWritable, LongWritable,
+ LongWritable> {
+
+ @Override
+ public boolean shouldCheckMessageIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isMessageCorrect(LongWritable srcId, LongWritable dstId,
+ LongWritable message, long superstepNo) {
+ return message.get() == srcId.get();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMVertexValueConstraintDebugConfig.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMVertexValueConstraintDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMVertexValueConstraintDebugConfig.java
new file mode 100644
index 0000000..75cdc1b
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/MWMVertexValueConstraintDebugConfig.java
@@ -0,0 +1,43 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.mwm;
+
+import org.apache.giraph.debugger.DebugConfig;
+import org.apache.hadoop.io.DoubleWritable;
+import org.apache.hadoop.io.LongWritable;
+
+/**
+ * DebugConfig for checking vertex value constraint for max weight matching.
+ */
+public class MWMVertexValueConstraintDebugConfig
+ extends
+ DebugConfig<LongWritable, VertexValue, DoubleWritable, LongWritable,
+ LongWritable> {
+
+ @Override
+ public boolean shouldCheckVertexValueIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isVertexValueCorrect(LongWritable vertexId,
+ VertexValue value) {
+ return value.getMatchedID() != vertexId.get();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/VertexValue.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/VertexValue.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/VertexValue.java
new file mode 100644
index 0000000..2a07b83
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/VertexValue.java
@@ -0,0 +1,89 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.mwm;
+
+import java.io.DataInput;
+import java.io.DataOutput;
+import java.io.IOException;
+
+import org.apache.hadoop.io.Writable;
+
+/**
+ * Vertex value for MWM.
+ */
+public class VertexValue implements Writable {
+
+ /**
+ * A constant to store for the matchedID fields of unmatched vertices.
+ */
+ public static final long NOT_MATCHED_ID = -1;
+
+ /**
+ * Id of the matched vertex with this.
+ */
+ private long matchedID;
+ /**
+ * Whether the vertex has been already matched.
+ */
+ private boolean isMatched;
+
+ /**
+ * Default constructor.
+ */
+ public VertexValue() {
+ this.setMatchedID(NOT_MATCHED_ID);
+ this.setMatched(false);
+ }
+
+ public long getMatchedID() {
+ return matchedID;
+ }
+
+ public void setMatchedID(long matchedID) {
+ this.matchedID = matchedID;
+ }
+
+ public boolean isMatched() {
+ return isMatched;
+ }
+
+ public void setMatched(boolean isMatched) {
+ this.isMatched = isMatched;
+ }
+ @Override
+ public void readFields(DataInput in) throws IOException {
+ setMatchedID(in.readLong());
+ setMatched(in.readBoolean());
+ }
+
+ @Override
+ public void write(DataOutput out) throws IOException {
+ out.writeLong(getMatchedID());
+ out.writeBoolean(isMatched());
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder sb = new StringBuilder();
+ sb.append("matchedID=");
+ sb.append(getMatchedID() == NOT_MATCHED_ID ? "?" : getMatchedID());
+ sb.append("\tisMatched=" + isMatched());
+ return sb.toString();
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/package-info.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/package-info.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/package-info.java
new file mode 100644
index 0000000..08b2e57
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/mwm/package-info.java
@@ -0,0 +1,26 @@
+/*
+ * 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.
+ */
+
+/**
+ * This is the Giraph implementation of an approximate maximum weight matching
+ * algorithm. It is used to demonstrate that Graft can help users find problems
+ * in their input graphs. In this case, if there are asymmetric weigths on
+ * the weights of the input graph, then this algorithm will get into an
+ * infinite loop.
+ */
+package org.apache.giraph.debugger.examples.mwm;
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/package-info.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/package-info.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/package-info.java
new file mode 100644
index 0000000..a4aa81e
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/package-info.java
@@ -0,0 +1,23 @@
+/*
+ * 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.
+ */
+
+/**
+ * Giraph I/O formats for the buggy example Giraph programs to be debugged
+ * with Graft.
+ */
+package org.apache.giraph.debugger.examples;
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/pagerank/SimplePageRankComputation.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/pagerank/SimplePageRankComputation.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/pagerank/SimplePageRankComputation.java
new file mode 100644
index 0000000..491b9c1
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/pagerank/SimplePageRankComputation.java
@@ -0,0 +1,94 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.pagerank;
+
+import java.io.IOException;
+
+import org.apache.giraph.comm.WorkerClientRequestProcessor;
+import org.apache.giraph.graph.BasicComputation;
+import org.apache.giraph.graph.GraphState;
+import org.apache.giraph.graph.GraphTaskManager;
+import org.apache.giraph.graph.Vertex;
+import org.apache.giraph.worker.WorkerContext;
+import org.apache.giraph.worker.WorkerGlobalCommUsage;
+import org.apache.hadoop.io.DoubleWritable;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.NullWritable;
+import org.apache.log4j.Logger;
+
+/**
+ * Simple PageRank implementation in Giraph to be easily run with Graft.
+ */
+public class SimplePageRankComputation extends
+ BasicComputation<LongWritable, DoubleWritable, NullWritable, DoubleWritable> {
+
+ /** Sum aggregator name */
+ public static final String SUM_AGG = "sum";
+ /** Min aggregator name */
+ public static final String MIN_AGG = "min";
+ /** Max aggregator name */
+ public static final String MAX_AGG = "max";
+ /** Number of supersteps for this test */
+ private static int MAX_SUPERSTEPS = 10;
+ /** Logger */
+ private static final Logger LOG = Logger
+ .getLogger(SimplePageRankComputation.class);
+
+ @Override
+ public void initialize(
+ GraphState graphState,
+ WorkerClientRequestProcessor<LongWritable, DoubleWritable, NullWritable>
+ workerClientRequestProcessor,
+ GraphTaskManager<LongWritable, DoubleWritable, NullWritable>
+ graphTaskManager,
+ WorkerGlobalCommUsage workerGlobalCommUsage, WorkerContext workerContext) {
+ MAX_SUPERSTEPS = workerContext.getConf().getInt(
+ getClass().getName() + ".maxSupersteps", 10);
+ super.initialize(graphState, workerClientRequestProcessor,
+ graphTaskManager, workerGlobalCommUsage, workerContext);
+ }
+
+ @Override
+ public void compute(
+ Vertex<LongWritable, DoubleWritable, NullWritable> vertex,
+ Iterable<DoubleWritable> messages) throws IOException {
+ if (getSuperstep() >= 1) {
+ double sum = 0;
+ for (DoubleWritable message : messages) {
+ sum += message.get();
+ }
+ DoubleWritable vertexValue = new DoubleWritable(
+ (0.15f / getTotalNumVertices()) + 0.85f * sum);
+ vertex.setValue(vertexValue);
+ aggregate(MAX_AGG, vertexValue);
+ aggregate(MIN_AGG, vertexValue);
+ aggregate(SUM_AGG, new LongWritable(1));
+ // LOG.info(vertex.getId() + ": PageRank=" + vertexValue + " max=" +
+ // getAggregatedValue(MAX_AGG) + " min=" + getAggregatedValue(MIN_AGG));
+ }
+
+ if (getSuperstep() < MAX_SUPERSTEPS) {
+ long edges = vertex.getNumEdges();
+ sendMessageToAllEdges(vertex, new DoubleWritable(vertex.getValue().get() /
+ edges));
+ } else {
+ vertex.voteToHalt();
+ }
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/pagerank/SimplePageRankMasterCompute.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/pagerank/SimplePageRankMasterCompute.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/pagerank/SimplePageRankMasterCompute.java
new file mode 100644
index 0000000..a4890ab
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/pagerank/SimplePageRankMasterCompute.java
@@ -0,0 +1,41 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.pagerank;
+
+import org.apache.giraph.aggregators.DoubleMaxAggregator;
+import org.apache.giraph.aggregators.DoubleMinAggregator;
+import org.apache.giraph.aggregators.LongSumAggregator;
+import org.apache.giraph.master.DefaultMasterCompute;
+
+/**
+ * Master compute associated with {@link SimplePageRankComputation}.
+ * It registers required aggregators.
+ */
+public class SimplePageRankMasterCompute extends
+ DefaultMasterCompute {
+ @Override
+ public void initialize() throws InstantiationException,
+ IllegalAccessException {
+ registerAggregator(SimplePageRankComputation.SUM_AGG,
+ LongSumAggregator.class);
+ registerPersistentAggregator(SimplePageRankComputation.MIN_AGG,
+ DoubleMinAggregator.class);
+ registerPersistentAggregator(SimplePageRankComputation.MAX_AGG,
+ DoubleMaxAggregator.class);
+ }
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/pagerank/package-info.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/pagerank/package-info.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/pagerank/package-info.java
new file mode 100644
index 0000000..0209586
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/pagerank/package-info.java
@@ -0,0 +1,22 @@
+/*
+ * 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.
+ */
+
+/**
+ * Simple PageRank implementation in Giraph to be easily run with Graft.
+ */
+package org.apache.giraph.debugger.examples.pagerank;
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkComputation.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkComputation.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkComputation.java
new file mode 100644
index 0000000..c39d314
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkComputation.java
@@ -0,0 +1,145 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.randomwalk;
+
+import java.io.IOException;
+import java.util.Random;
+
+import org.apache.giraph.comm.WorkerClientRequestProcessor;
+import org.apache.giraph.edge.Edge;
+import org.apache.giraph.graph.BasicComputation;
+import org.apache.giraph.graph.GraphState;
+import org.apache.giraph.graph.GraphTaskManager;
+import org.apache.giraph.graph.Vertex;
+import org.apache.giraph.worker.WorkerContext;
+import org.apache.giraph.worker.WorkerGlobalCommUsage;
+import org.apache.hadoop.io.IntWritable;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.NullWritable;
+
+/**
+ * Random walk implementation in Giraph with short-overflow bugs.
+ */
+public class RandomWalkComputation extends
+ BasicComputation<LongWritable, IntWritable, NullWritable, IntWritable> {
+
+ /**
+ * Default number of initial walkers.
+ */
+ private static final int DEFAULT_NUM_WALKERS = 100;
+ /**
+ * Default length of the random walk.
+ */
+ private static final int DEFAULT_LENGTH_OF_WALK = 20;
+
+ /**
+ * Array for storing the number of walkers for each neighbor of a vertex.
+ */
+ private short[] messagesToNeighbors = new short[2];
+ /**
+ * Initial number of walkers.
+ */
+ private int initialNumWalkers;
+ /**
+ * Length of the random walk.
+ */
+ private int lengthOfWalk;
+
+ @Override
+ public void initialize(
+ GraphState graphState,
+ WorkerClientRequestProcessor<LongWritable, IntWritable, NullWritable>
+ workerClientRequestProcessor,
+ GraphTaskManager<LongWritable, IntWritable, NullWritable> graphTaskManager,
+ WorkerGlobalCommUsage workerGlobalCommUsage, WorkerContext workerContext) {
+ super.initialize(graphState, workerClientRequestProcessor,
+ graphTaskManager, workerGlobalCommUsage, workerContext);
+
+ initialNumWalkers = getConf().getInt(
+ getClass().getName() + ".initialNumWalkers", DEFAULT_NUM_WALKERS);
+ lengthOfWalk = getConf().getInt(getClass().getName() + ".walkLength",
+ DEFAULT_LENGTH_OF_WALK);
+ }
+
+ @Override
+ public void compute(Vertex<LongWritable, IntWritable, NullWritable> vertex,
+ Iterable<IntWritable> messages) throws IOException {
+ // Halt after the walk reaches a certain length.
+ if (getSuperstep() > lengthOfWalk) {
+ vertex.voteToHalt();
+ return;
+ }
+ short numWalkersHere = 0;
+ if (getSuperstep() == 0) {
+ // At the first superstep, start from an initial number of walkers.
+ numWalkersHere += initialNumWalkers;
+ } else {
+ // Otherwise, count the number of walkers arrived at this vertex.
+ for (IntWritable messageValue : messages) {
+ numWalkersHere += messageValue.get();
+ }
+ }
+ vertex.setValue(new IntWritable(numWalkersHere));
+ moveWalkersToNeighbors(numWalkersHere, vertex);
+ }
+
+ /**
+ * Move walkers to neighbors by sending messages.
+ *
+ * @param numMessagesToSend total number of walkers to send out
+ * @param vertex the vertex sending messages
+ */
+ private void moveWalkersToNeighbors(int numMessagesToSend,
+ Vertex<LongWritable, IntWritable, NullWritable> vertex) {
+ Iterable<Edge<LongWritable, NullWritable>> edges = vertex.getEdges();
+ int neighborsLength = vertex.getNumEdges();
+ if (messagesToNeighbors.length < neighborsLength) {
+ messagesToNeighbors = new short[neighborsLength];
+ } else {
+ for (int i = 0; i < neighborsLength; ++i) {
+ messagesToNeighbors[i] = 0;
+ }
+ }
+ Random random = new Random();
+ if (neighborsLength == 0) {
+ // When there's no out-edge, let each walker jump to a random vertex in
+ // the graph.
+ for (int i = 0; i < numMessagesToSend; ++i) {
+ sendMessage(
+ new LongWritable(random.nextInt((int) getTotalNumVertices())),
+ new IntWritable(1));
+ }
+ } else {
+ // Otherwise, distribute the walkers on this vertex to each neighbor.
+ for (int i = 0; i < numMessagesToSend; ++i) {
+ int neighborIdIndex = random.nextInt(neighborsLength);
+ messagesToNeighbors[neighborIdIndex] += 1;
+ }
+ // Then, send out messages containing the number of walkers.
+ int i = 0;
+ for (Edge<LongWritable, NullWritable> edge : edges) {
+ if (messagesToNeighbors[i] != 0) {
+ sendMessage(edge.getTargetVertexId(), new IntWritable(
+ messagesToNeighbors[i]));
+ }
+ i++;
+ }
+ }
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkDebugConfig.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkDebugConfig.java
new file mode 100644
index 0000000..2fff99d
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkDebugConfig.java
@@ -0,0 +1,55 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.randomwalk;
+
+import org.apache.giraph.debugger.DebugConfig;
+import org.apache.hadoop.io.IntWritable;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.NullWritable;
+
+/**
+ * DebugConfig for random walk algorithm.
+ */
+public class RandomWalkDebugConfig
+ extends
+ DebugConfig<LongWritable, IntWritable, NullWritable, IntWritable,
+ IntWritable> {
+
+ @Override
+ public boolean shouldCheckVertexValueIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isVertexValueCorrect(LongWritable vertexId,
+ IntWritable value) {
+ return value.get() > 0;
+ }
+
+ @Override
+ public boolean shouldCheckMessageIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isMessageCorrect(LongWritable srcId, LongWritable dstId,
+ IntWritable message, long superstepNo) {
+ return message.get() > 0;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkMessageConstraintDebugConfig.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkMessageConstraintDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkMessageConstraintDebugConfig.java
new file mode 100644
index 0000000..4d47538
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkMessageConstraintDebugConfig.java
@@ -0,0 +1,56 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.randomwalk;
+
+import org.apache.giraph.debugger.DebugConfig;
+import org.apache.giraph.graph.Vertex;
+import org.apache.hadoop.io.IntWritable;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.NullWritable;
+
+/**
+ * DebugConfig for checking message constraint in random walk implementation.
+ */
+public class RandomWalkMessageConstraintDebugConfig
+ extends
+ DebugConfig<LongWritable, IntWritable, NullWritable, IntWritable,
+ IntWritable> {
+
+ @Override
+ public boolean shouldCatchExceptions() {
+ return false;
+ }
+
+ @Override
+ public boolean shouldDebugVertex(
+ Vertex<LongWritable, IntWritable, NullWritable> vertex, long superstepNo) {
+ return false;
+ }
+
+ @Override
+ public boolean shouldCheckMessageIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isMessageCorrect(LongWritable srcId, LongWritable dstId,
+ IntWritable message, long superstepNo) {
+ return message.get() > 0;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkVertexValueConstraintDebugConfig.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkVertexValueConstraintDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkVertexValueConstraintDebugConfig.java
new file mode 100644
index 0000000..7678b12
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/RandomWalkVertexValueConstraintDebugConfig.java
@@ -0,0 +1,57 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.randomwalk;
+
+import org.apache.giraph.debugger.DebugConfig;
+import org.apache.giraph.graph.Vertex;
+import org.apache.hadoop.io.IntWritable;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.NullWritable;
+
+/**
+ * DebugConfig for checking vertex value constraints of random walk
+ * implementation.
+ */
+public class RandomWalkVertexValueConstraintDebugConfig
+ extends
+ DebugConfig<LongWritable, IntWritable, NullWritable, IntWritable,
+ IntWritable> {
+
+ @Override
+ public boolean shouldCatchExceptions() {
+ return false;
+ }
+
+ @Override
+ public boolean shouldDebugVertex(
+ Vertex<LongWritable, IntWritable, NullWritable> vertex, long superstepNo) {
+ return false;
+ }
+
+ @Override
+ public boolean shouldCheckVertexValueIntegrity() {
+ return true;
+ }
+
+ @Override
+ public boolean isVertexValueCorrect(LongWritable vertexId, IntWritable
+ value) {
+ return value.get() >= 0;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/package-info.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/package-info.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/package-info.java
new file mode 100644
index 0000000..a9e330d
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/randomwalk/package-info.java
@@ -0,0 +1,22 @@
+/*
+ * 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.
+ */
+
+/**
+ * Example Giraph random walk algorithm.
+ */
+package org.apache.giraph.debugger.examples.randomwalk;
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/BuggySimpleShortestPathsComputation.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/BuggySimpleShortestPathsComputation.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/BuggySimpleShortestPathsComputation.java
new file mode 100644
index 0000000..0a1d909
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/BuggySimpleShortestPathsComputation.java
@@ -0,0 +1,106 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.simpledebug;
+
+import java.io.IOException;
+
+import org.apache.giraph.Algorithm;
+import org.apache.giraph.conf.LongConfOption;
+import org.apache.giraph.edge.Edge;
+import org.apache.giraph.graph.BasicComputation;
+import org.apache.giraph.graph.Vertex;
+import org.apache.hadoop.io.DoubleWritable;
+import org.apache.hadoop.io.FloatWritable;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.log4j.Logger;
+
+/**
+ * Debug version of SimpleShortestPathsComputation.
+ */
+@Algorithm(name = "Shortest paths", description = "Finds all shortest paths" +
+ "from a selected vertex")
+public class BuggySimpleShortestPathsComputation extends BasicComputation<
+ LongWritable, DoubleWritable, FloatWritable, DoubleWritable> {
+
+ /** The shortest paths id */
+ public static final LongConfOption SOURCE_ID = new LongConfOption(
+ "SimpleShortestPathsVertex.sourceId", 1, "The shortest paths id");
+ /** Class logger */
+ private static final Logger LOG = Logger
+ .getLogger(BuggySimpleShortestPathsComputation.class);
+
+ /**
+ * Is this vertex the source id?
+ *
+ * @param vertex
+ * Vertex
+ * @return True if the source id
+ */
+ private boolean isSource(Vertex<LongWritable, ?, ?> vertex) {
+ return vertex.getId().get() == SOURCE_ID.get(getConf());
+ }
+
+ @Override
+ public void compute(
+ Vertex<LongWritable, DoubleWritable, FloatWritable> vertex,
+ Iterable<DoubleWritable> messages) throws IOException {
+ // We do a dummy read of the aggregator below because for now we only
+ // intercept an aggregator
+ // if at least one vertex reads it.
+ LongWritable aggregatedValue = getAggregatedValue(
+ SimpleShortestPathsMaster.NV_DISTANCE_LESS_THAN_THREE_AGGREGATOR);
+ if (aggregatedValue != null) {
+ System.out.print("NV_DISTANCE_LESS_THAN_THREE_AGGREGATOR: " +
+ aggregatedValue.get() + "\n");
+ }
+ if (getSuperstep() == 0) {
+ vertex.setValue(new DoubleWritable(isSource(vertex) ? 0d :
+ Double.MAX_VALUE));
+ }
+ double previousValue = vertex.getValue().get();
+ double minDist = previousValue;
+ for (DoubleWritable message : messages) {
+ minDist = Math.min(minDist, message.get());
+ }
+ if (LOG.isDebugEnabled()) {
+ LOG.debug("Vertex " + vertex.getId() + " got minDist = " + minDist +
+ " vertex value = " + vertex.getValue());
+ }
+ if (minDist < vertex.getValue().get() || getSuperstep() == 0 &&
+ minDist == 0) {
+ vertex.setValue(new DoubleWritable(minDist));
+ for (Edge<LongWritable, FloatWritable> edge : vertex.getEdges()) {
+ double distance = minDist + edge.getValue().get();
+ if (LOG.isDebugEnabled()) {
+ LOG.debug("Vertex " + vertex.getId() + " sent to " +
+ edge.getTargetVertexId() + " = " + distance);
+ }
+ // INTENTIONAL BUG:Instead of sending the distance (i.e. by adding edge
+ // values),
+ // we send minDist, which is the vertex value.
+ sendMessage(edge.getTargetVertexId(), new DoubleWritable(minDist));
+ }
+ }
+ if (previousValue > 3 && minDist <= 3) {
+ aggregate(
+ SimpleShortestPathsMaster.NV_DISTANCE_LESS_THAN_THREE_AGGREGATOR,
+ new LongWritable(1));
+ }
+ vertex.voteToHalt();
+ }
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/SimpleShortestPathsDebugConfig.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/SimpleShortestPathsDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/SimpleShortestPathsDebugConfig.java
new file mode 100644
index 0000000..f2006e6
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/SimpleShortestPathsDebugConfig.java
@@ -0,0 +1,43 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.simpledebug;
+
+import org.apache.giraph.debugger.DebugConfig;
+import org.apache.giraph.graph.Vertex;
+import org.apache.hadoop.io.DoubleWritable;
+import org.apache.hadoop.io.FloatWritable;
+import org.apache.hadoop.io.LongWritable;
+
+/**
+ * Debug configuration file for SimpleShortestPathDebugComputation.
+ */
+public class SimpleShortestPathsDebugConfig extends DebugConfig<LongWritable,
+ DoubleWritable, FloatWritable, DoubleWritable, DoubleWritable> {
+
+ @Override
+ public boolean shouldDebugSuperstep(long superstepNo) {
+ return true;
+ }
+
+ @Override
+ public boolean shouldDebugVertex(
+ Vertex<LongWritable, DoubleWritable, FloatWritable> vertex,
+ long superstepNo) {
+ return true;
+ }
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/SimpleShortestPathsMaster.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/SimpleShortestPathsMaster.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/SimpleShortestPathsMaster.java
new file mode 100644
index 0000000..e2559cc
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/SimpleShortestPathsMaster.java
@@ -0,0 +1,75 @@
+/*
+ * 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.
+ */
+package org.apache.giraph.debugger.examples.simpledebug;
+
+import org.apache.giraph.aggregators.LongSumAggregator;
+import org.apache.giraph.debugger.examples.exceptiondebug.BuggySimpleTriangleClosingComputation;
+import org.apache.giraph.graph.Computation;
+import org.apache.giraph.master.DefaultMasterCompute;
+import org.apache.hadoop.io.LongWritable;
+
+/**
+ * Master compute associated with {@link BuggySimpleShortestPathsComputation}.
+ * It handles dangling nodes.
+ */
+public class SimpleShortestPathsMaster extends DefaultMasterCompute {
+
+ /**
+ * Name of the aggregator keeping the number of vertices which have distance
+ * less than three to the source vertex.
+ */
+ public static final String NV_DISTANCE_LESS_THAN_THREE_AGGREGATOR =
+ "nvWithDistanceLessThanThree";
+
+ @SuppressWarnings({ "unchecked", "rawtypes" })
+ @Override
+ public void compute() {
+ System.out.print("Running SimpleShortestPathsMaster.compute. superstep " +
+ getSuperstep() + "\n");
+ LongWritable aggregatorValue = getAggregatedValue(
+ NV_DISTANCE_LESS_THAN_THREE_AGGREGATOR);
+ if (aggregatorValue != null) {
+ System.out.print("At Master.compute() with aggregator: " +
+ aggregatorValue.get() + "\n");
+ }
+ // if (getSuperstep() == 2) {
+ // throw new IllegalArgumentException("DUMMY EXCEPTION FOR TESTING");
+ // }
+
+ // Dummy code for testing Instrumenter analysis
+ if (getSuperstep() == 100000) {
+ // which is extremely less likely to happen,
+ setComputation(BuggySimpleTriangleClosingComputation.class);
+ } else if (getSuperstep() == 200000) {
+ try {
+ setComputation((Class<? extends Computation>) Class.forName(
+ "org.apache.giraph.debugger.examples.integrity." +
+ "ConnectedComponentsActualComputation"));
+ } catch (ClassNotFoundException e) {
+ e.printStackTrace();
+ }
+ }
+ }
+
+ @Override
+ public void initialize() throws InstantiationException,
+ IllegalAccessException {
+ registerPersistentAggregator(NV_DISTANCE_LESS_THAN_THREE_AGGREGATOR,
+ LongSumAggregator.class);
+ }
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/package-info.java
----------------------------------------------------------------------
diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/package-info.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/package-info.java
new file mode 100644
index 0000000..dd3d603
--- /dev/null
+++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/simpledebug/package-info.java
@@ -0,0 +1,22 @@
+/*
+ * 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.
+ */
+
+/**
+ * A simple example Giraph program that can be easily debugged using Graft.
+ */
+package org.apache.giraph.debugger.examples.simpledebug;