Return-Path: X-Original-To: apmail-giraph-commits-archive@www.apache.org Delivered-To: apmail-giraph-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 3ACB7931E for ; Mon, 8 Dec 2014 19:21:40 +0000 (UTC) Received: (qmail 1565 invoked by uid 500); 8 Dec 2014 19:21:37 -0000 Delivered-To: apmail-giraph-commits-archive@giraph.apache.org Received: (qmail 1518 invoked by uid 500); 8 Dec 2014 19:21:37 -0000 Mailing-List: contact commits-help@giraph.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@giraph.apache.org Delivered-To: mailing list commits@giraph.apache.org Received: (qmail 1268 invoked by uid 99); 8 Dec 2014 19:21:37 -0000 Received: from tyr.zones.apache.org (HELO tyr.zones.apache.org) (140.211.11.114) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 08 Dec 2014 19:21:37 +0000 Received: by tyr.zones.apache.org (Postfix, from userid 65534) id 2B5BEA1E0FE; Mon, 8 Dec 2014 19:21:37 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: edunov@apache.org To: commits@giraph.apache.org Date: Mon, 08 Dec 2014 19:21:42 -0000 Message-Id: In-Reply-To: <8ef773d29e35473ea606b38b21202764@git.apache.org> References: <8ef773d29e35473ea606b38b21202764@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: [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 { + + /** + * 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 vertex, + Iterable messages) throws IOException { + long currentComponent = vertex.getValue().get(); + + if (getSuperstep() == 0) { + vertex.setValue(vertex.getId()); + for (Edge 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 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 { + + @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 { + + @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 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 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 { + + @Override + public void compute(Vertex vertex, + Iterable 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 vertex, + Iterable messages) { + for (LongWritable matchedNbr : messages) { + vertex.removeEdges(matchedNbr); + } + } + + /** + * @param vertex the vertex + * @return the max id among neighbor vertices + */ + private long pickMaxValueVertex( + Vertex vertex) { + long maxWeightNbrID = -1; + double maxWeight = -1.0; + for (Edge 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 { + + @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 { + + @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 { + + @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 { + + /** 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 + workerClientRequestProcessor, + GraphTaskManager + 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 vertex, + Iterable 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 { + + /** + * 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 + workerClientRequestProcessor, + GraphTaskManager 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 vertex, + Iterable 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 vertex) { + Iterable> 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 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 { + + @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 { + + @Override + public boolean shouldCatchExceptions() { + return false; + } + + @Override + public boolean shouldDebugVertex( + Vertex 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 { + + @Override + public boolean shouldCatchExceptions() { + return false; + } + + @Override + public boolean shouldDebugVertex( + Vertex 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 vertex) { + return vertex.getId().get() == SOURCE_ID.get(getConf()); + } + + @Override + public void compute( + Vertex vertex, + Iterable 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 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 { + + @Override + public boolean shouldDebugSuperstep(long superstepNo) { + return true; + } + + @Override + public boolean shouldDebugVertex( + Vertex 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) 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;