http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/RandomizedMaximalMatchingComputation.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/RandomizedMaximalMatchingComputation.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/RandomizedMaximalMatchingComputation.java new file mode 100644 index 0000000..577d7b6 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/RandomizedMaximalMatchingComputation.java @@ -0,0 +1,186 @@ +/* + * 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.bipartitematching; + +import java.io.IOException; + +import org.apache.giraph.graph.BasicComputation; +import org.apache.giraph.graph.Vertex; +import org.apache.hadoop.io.LongWritable; +import org.apache.hadoop.io.NullWritable; + +/** + * Randomized maximal bipartite graph matching algorithm implementation. It + * assumes all vertices whose ids are even are in the left part, and odd in the + * right. + */ +public class RandomizedMaximalMatchingComputation extends + BasicComputation<LongWritable, VertexValue, NullWritable, Message> { + + @Override + public void compute(Vertex<LongWritable, VertexValue, NullWritable> vertex, + Iterable<Message> messages) throws IOException { + + int phase = (int) (getSuperstep() % 4); + switch (phase) { + case 0: // "In phase 0 of a cycle," + // "each left vertex not yet matched" + if (isLeft(vertex)) { + if (isNotMatchedYet(vertex)) { + // "sends a message to each of its neighbors to request a match," + sendMessageToAllEdges(vertex, createRequestMessage(vertex)); + // "and then unconditionally votes to halt." + vertex.voteToHalt(); + } + } + // "If it sent no messages (because it is already matched, or has no + // outgoing edges), or if all the message recipients are already + // matched, it will never be reactivated. Otherwise, it will receive a + // response in two supersteps and reactivate." + break; + + case 1: // "In phase 1 of a cycle," + // "each right vertex not yet matched" + if (isRight(vertex)) { + if (isNotMatchedYet(vertex)) { + int i = 0; + for (Message msg : messages) { + // "randomly chooses one of the messages it receives," + Message reply = (i == 0) ? // (by simply granting the first one) + // "sends a message granting that request, and" + createGrantingMessage(vertex) : + // "sends messages to other requestors denying it." + createDenyingMessage(vertex); + sendMessage(new LongWritable(msg.getSenderVertex()), reply); + ++i; + } + // "Then it unconditionally votes to halt." + vertex.voteToHalt(); // XXX It is ambiguous if only unmatched right + // vertices must halt, or all right ones must. + } + } + break; + + case 2: // "In phase 2 of a cycle," + // "each left vertex not yet matched" + if (isLeft(vertex)) { + if (isNotMatchedYet(vertex)) { + // "chooses one of the grants it receives" + for (Message msg : messages) { + if (msg.isGranting()) { + // (by simply picking the first one) + // "and sends an acceptance message." + sendMessage(new LongWritable(msg.getSenderVertex()), + createGrantingMessage(vertex)); + // (and also record which vertex was matched) + vertex.getValue().setMatchedVertex(msg.getSenderVertex()); + break; + } + } + vertex.voteToHalt(); // XXX (Not in the original text) + // In fact, program may end prematurely + // unless only matched left vertices halt. + // "Left vertices that are already matched will never execute this + // phase, since they will not have sent a message in phase 0." + } + } + break; + + case 3: // "Finally, in phase 3," + // "an unmatched right vertex" + if (isRight(vertex)) { + if (isNotMatchedYet(vertex)) { + // "receives at most one acceptance message." + for (Message msg : messages) { + // "It notes the matched node" + vertex.getValue().setMatchedVertex(msg.getSenderVertex()); + break; + } + // "and unconditionally votes to halt" + vertex.voteToHalt(); // XXX Again, it's ambiguous if only unmatched + // right vertices must halt, or all right ones + // must. + // "it has nothing further to do." + } + } + break; + + default: + throw new IllegalStateException("No such phase " + phase); + } + } + + /** + * @param vertex + * The vertex to test + * @return Whether the vertex belongs to the left part + */ + boolean isLeft(Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return vertex.getId().get() % 2 == 1; + } + + /** + * @param vertex + * The vertex to test + * @return Whether the vertex belongs to the right part + */ + boolean isRight(Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return !isLeft(vertex); + } + + /** + * @param vertex + * The vertex to test + * @return Whether the vertex has a match + */ + private boolean isNotMatchedYet( + Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return !vertex.getValue().isMatched(); + } + + /** + * @param vertex + * Sending vertex + * @return A message requesting a match + */ + private Message createRequestMessage( + Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return new Message(vertex); + } + + /** + * @param vertex + * Sending vertex + * @return A message granting the match request + */ + private Message createGrantingMessage( + Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return new Message(vertex, true); + } + + /** + * @param vertex + * Sending vertex + * @return A message denying the match request + */ + private Message createDenyingMessage( + Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return new Message(vertex, false); + } + +}
http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/RandomizedMaximalMatchingComputation2FixedLeft.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/RandomizedMaximalMatchingComputation2FixedLeft.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/RandomizedMaximalMatchingComputation2FixedLeft.java new file mode 100644 index 0000000..33dfa44 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/RandomizedMaximalMatchingComputation2FixedLeft.java @@ -0,0 +1,186 @@ +/* + * 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.bipartitematching; + +import java.io.IOException; + +import org.apache.giraph.graph.BasicComputation; +import org.apache.giraph.graph.Vertex; +import org.apache.hadoop.io.LongWritable; +import org.apache.hadoop.io.NullWritable; + +/** + * Randomized maximal bipartite graph matching algorithm implementation. It + * assumes all vertices whose ids are even are in the left part, and odd in the + * right. + */ +public class RandomizedMaximalMatchingComputation2FixedLeft extends + BasicComputation<LongWritable, VertexValue, NullWritable, Message> { + + @Override + public void compute(Vertex<LongWritable, VertexValue, NullWritable> vertex, + Iterable<Message> messages) throws IOException { + + int phase = (int) (getSuperstep() % 4); + switch (phase) { + case 0: // "In phase 0 of a cycle," + // "each left vertex not yet matched" + if (isLeft(vertex)) { + if (isNotMatchedYet(vertex)) { + // "sends a message to each of its neighbors to request a match," + sendMessageToAllEdges(vertex, createRequestMessage(vertex)); + // "and then unconditionally votes to halt." + vertex.voteToHalt(); + } + } + // "If it sent no messages (because it is already matched, or has no + // outgoing edges), or if all the message recipients are already + // matched, it will never be reactivated. Otherwise, it will receive a + // response in two supersteps and reactivate." + break; + + case 1: // "In phase 1 of a cycle," + // "each right vertex not yet matched" + if (isRight(vertex)) { + if (isNotMatchedYet(vertex)) { + int i = 0; + for (Message msg : messages) { + // "randomly chooses one of the messages it receives," + Message reply = (i == 0) ? // (by simply granting the first one) + // "sends a message granting that request, and" + createGrantingMessage(vertex) : + // "sends messages to other requestors denying it." + createDenyingMessage(vertex); + sendMessage(new LongWritable(msg.getSenderVertex()), reply); + ++i; + } + // "Then it unconditionally votes to halt." + vertex.voteToHalt(); // XXX It is ambiguous if only unmatched right + // vertices must halt, or all right ones must. + } + } + break; + + case 2: // "In phase 2 of a cycle," + // "each left vertex not yet matched" + if (isLeft(vertex)) { + if (isNotMatchedYet(vertex)) { + // "chooses one of the grants it receives" + for (Message msg : messages) { + if (msg.isGranting()) { + // (by simply picking the first one) + // "and sends an acceptance message." + sendMessage(new LongWritable(msg.getSenderVertex()), + createGrantingMessage(vertex)); + // (and also record which vertex was matched) + vertex.getValue().setMatchedVertex(msg.getSenderVertex()); + vertex.voteToHalt(); // XXX (Not in the original text) + // Unless matched left vertices halt, + // program ends prematurely. + break; + } + } + // "Left vertices that are already matched will never execute this + // phase, since they will not have sent a message in phase 0." + } + } + break; + + case 3: // "Finally, in phase 3," + // "an unmatched right vertex" + if (isRight(vertex)) { + if (isNotMatchedYet(vertex)) { + // "receives at most one acceptance message." + for (Message msg : messages) { + // "It notes the matched node" + vertex.getValue().setMatchedVertex(msg.getSenderVertex()); + break; + } + // "and unconditionally votes to halt" + vertex.voteToHalt(); // XXX Again, it's ambiguous if only unmatched + // right vertices must halt, or all right ones + // must. + // "it has nothing further to do." + } + } + break; + + default: + throw new IllegalStateException("No such phase " + phase); + } + } + + /** + * @param vertex + * The vertex to test + * @return Whether the vertex belongs to the left part + */ + boolean isLeft(Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return vertex.getId().get() % 2 == 1; + } + + /** + * @param vertex + * The vertex to test + * @return Whether the vertex belongs to the right part + */ + boolean isRight(Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return !isLeft(vertex); + } + + /** + * @param vertex + * The vertex to test + * @return Whether the vertex has a match + */ + private boolean isNotMatchedYet( + Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return !vertex.getValue().isMatched(); + } + + /** + * @param vertex + * Sending vertex + * @return A message requesting a match + */ + private Message createRequestMessage( + Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return new Message(vertex); + } + + /** + * @param vertex + * Sending vertex + * @return A message granting the match request + */ + private Message createGrantingMessage( + Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return new Message(vertex, true); + } + + /** + * @param vertex + * Sending vertex + * @return A message denying the match request + */ + private Message createDenyingMessage( + Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return new Message(vertex, false); + } + +} http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/RandomizedMaximalMatchingComputation3FixedRight.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/RandomizedMaximalMatchingComputation3FixedRight.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/RandomizedMaximalMatchingComputation3FixedRight.java new file mode 100644 index 0000000..fc975d5 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/RandomizedMaximalMatchingComputation3FixedRight.java @@ -0,0 +1,187 @@ +/* + * 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.bipartitematching; + +import java.io.IOException; + +import org.apache.giraph.graph.BasicComputation; +import org.apache.giraph.graph.Vertex; +import org.apache.hadoop.io.LongWritable; +import org.apache.hadoop.io.NullWritable; + +/** + * Randomized maximal bipartite graph matching algorithm implementation. It + * assumes all vertices whose ids are even are in the left part, and odd in the + * right. + */ +public class RandomizedMaximalMatchingComputation3FixedRight extends + BasicComputation<LongWritable, VertexValue, NullWritable, Message> { + + @Override + public void compute(Vertex<LongWritable, VertexValue, NullWritable> vertex, + Iterable<Message> messages) throws IOException { + + int phase = (int) (getSuperstep() % 4); + switch (phase) { + case 0: // "In phase 0 of a cycle," + // "each left vertex not yet matched" + if (isLeft(vertex)) { + if (isNotMatchedYet(vertex)) { + // "sends a message to each of its neighbors to request a match," + sendMessageToAllEdges(vertex, createRequestMessage(vertex)); + // "and then unconditionally votes to halt." + vertex.voteToHalt(); + } + } + // "If it sent no messages (because it is already matched, or has no + // outgoing edges), or if all the message recipients are already + // matched, it will never be reactivated. Otherwise, it will receive a + // response in two supersteps and reactivate." + break; + + case 1: // "In phase 1 of a cycle," + // "each right vertex not yet matched" + if (isRight(vertex)) { + if (isNotMatchedYet(vertex)) { + int i = 0; + for (Message msg : messages) { + // "randomly chooses one of the messages it receives," + Message reply = (i == 0) ? // (by simply granting the first one) + // "sends a message granting that request, and" + createGrantingMessage(vertex) : + // "sends messages to other requestors denying it." + createDenyingMessage(vertex); + sendMessage(new LongWritable(msg.getSenderVertex()), reply); + ++i; + } + } + // "Then it unconditionally votes to halt." + vertex.voteToHalt(); // XXX (Not clear from the original text) + // Unless all right vertices halt, program + // enters an infinite loop. + } + break; + + case 2: // "In phase 2 of a cycle," + // "each left vertex not yet matched" + if (isLeft(vertex)) { + if (isNotMatchedYet(vertex)) { + // "chooses one of the grants it receives" + for (Message msg : messages) { + if (msg.isGranting()) { + // (by simply picking the first one) + // "and sends an acceptance message." + sendMessage(new LongWritable(msg.getSenderVertex()), + createGrantingMessage(vertex)); + // (and also record which vertex was matched) + vertex.getValue().setMatchedVertex(msg.getSenderVertex()); + vertex.voteToHalt(); // XXX (Not in the original text) + // Unless matched left vertices halt, + // program enters prematurely. + break; + } + } + // "Left vertices that are already matched will never execute this + // phase, since they will not have sent a message in phase 0." + } + } + break; + + case 3: // "Finally, in phase 3," + // "an unmatched right vertex" + if (isRight(vertex)) { + if (isNotMatchedYet(vertex)) { + // "receives at most one acceptance message." + for (Message msg : messages) { + // "It notes the matched node" + vertex.getValue().setMatchedVertex(msg.getSenderVertex()); + break; + } + } + // "and unconditionally votes to halt" + vertex.voteToHalt(); // XXX (Not clear from the original text) + // Unless all right vertices halt, program + // enters an infinite loop. + // "it has nothing further to do." + } + break; + + default: + throw new IllegalStateException("No such phase " + phase); + } + } + + /** + * @param vertex + * The vertex to test + * @return Whether the vertex belongs to the left part + */ + boolean isLeft(Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return vertex.getId().get() % 2 == 1; + } + + /** + * @param vertex + * The vertex to test + * @return Whether the vertex belongs to the right part + */ + boolean isRight(Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return !isLeft(vertex); + } + + /** + * @param vertex + * The vertex to test + * @return Whether the vertex has a match + */ + private boolean isNotMatchedYet( + Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return !vertex.getValue().isMatched(); + } + + /** + * @param vertex + * Sending vertex + * @return A message requesting a match + */ + private Message createRequestMessage( + Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return new Message(vertex); + } + + /** + * @param vertex + * Sending vertex + * @return A message granting the match request + */ + private Message createGrantingMessage( + Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return new Message(vertex, true); + } + + /** + * @param vertex + * Sending vertex + * @return A message denying the match request + */ + private Message createDenyingMessage( + Vertex<LongWritable, VertexValue, NullWritable> vertex) { + return new Message(vertex, false); + } + +} http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/VertexValue.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/VertexValue.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/VertexValue.java new file mode 100644 index 0000000..203f98e --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/VertexValue.java @@ -0,0 +1,77 @@ +/* + * 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.bipartitematching; + +import java.io.DataInput; +import java.io.DataOutput; +import java.io.IOException; + +import org.apache.hadoop.io.Writable; + +/** + * Vertex value for bipartite matching. + */ +public class VertexValue implements Writable { + + /** + * Whether this vertex has been matched already. + */ + private boolean matched = false; + /** + * The id of the matching vertex on the other side. + */ + private long matchedVertex = -1; + + public boolean isMatched() { + return matched; + } + + public long getMatchedVertex() { + return matchedVertex; + } + + /** + * Sets matched vertex. + * + * @param matchedVertex Matched vertex id + */ + public void setMatchedVertex(long matchedVertex) { + this.matched = true; + this.matchedVertex = matchedVertex; + } + + @Override + public void readFields(DataInput in) throws IOException { + this.matched = in.readBoolean(); + this.matchedVertex = in.readLong(); + } + + @Override + public void write(DataOutput out) throws IOException { + out.writeBoolean(matched); + out.writeLong(matchedVertex); + } + + @Override + public String toString() { + StringBuilder sb = new StringBuilder(); + sb.append(matched ? matchedVertex : "null"); + return sb.toString(); + } + +} http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/bipartitegraph-1.json ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/bipartitegraph-1.json b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/bipartitegraph-1.json new file mode 100644 index 0000000..1d38f70 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/bipartitegraph-1.json @@ -0,0 +1,6 @@ +[1, null, [2]] +[2, null, [1, 3]] +[3, null, [2, 4]] +[4, null, [3, 5]] +[5, null, [4, 6]] +[6, null, [5]] http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/package-info.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/package-info.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/package-info.java new file mode 100644 index 0000000..bbdd5b4 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/bipartitematching/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. + */ + +/** + * Example Giraph programs that (incorrectly) implement the Maxmimal Bipartite + * Matching algorithm mentioned in the original Pregel paper for demonstrating + * Graft's capture-visualize-reproduce functionalities. + */ +package org.apache.giraph.debugger.examples.bipartitematching; http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/exceptiondebug/BuggySimpleTriangleClosingComputation.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/exceptiondebug/BuggySimpleTriangleClosingComputation.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/exceptiondebug/BuggySimpleTriangleClosingComputation.java new file mode 100644 index 0000000..532bdd2 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/exceptiondebug/BuggySimpleTriangleClosingComputation.java @@ -0,0 +1,206 @@ +/* + * 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.exceptiondebug; + +import java.io.IOException; +import java.util.Map; +import java.util.Set; + +import org.apache.giraph.edge.Edge; +import org.apache.giraph.graph.BasicComputation; +import org.apache.giraph.graph.Vertex; +import org.apache.giraph.utils.ArrayListWritable; +import org.apache.hadoop.io.IntWritable; +import org.apache.hadoop.io.NullWritable; + +import com.google.common.base.Objects; +import com.google.common.collect.Maps; +import com.google.common.collect.Sets; + +/** + * Demonstrates triangle closing in simple, unweighted graphs for Giraph. + * + * Triangle Closing: Vertex A and B maintain out-edges to C and D The algorithm, + * when finished, populates all vertices' value with an array of Writables + * representing all the vertices that each should form an out-edge to (connect + * with, if this is a social graph.) In this example, vertices A and B would + * hold empty arrays since they are already connected with C and D. Results: If + * the graph is undirected, C would hold value, D and D would hold value C, + * since both are neighbors of A and B and yet both were not previously + * connected to each other. + * + * In a social graph, the result values for vertex X would represent people that + * are likely a part of a person X's social circle (they know one or more people + * X is connected to already) but X had not previously met them yet. Given this + * new information, X can decide to connect to vertices (peoople) in the result + * array or not. + * + * Results at each vertex are ordered in terms of the # of neighbors who are + * connected to each vertex listed in the final vertex value. The more of a + * vertex's neighbors who "know" someone, the stronger your social relationship + * is presumed to be to that vertex (assuming a social graph) and the more + * likely you should connect with them. + * + * In this implementation, Edge Values are not used, but could be adapted to + * represent additional qualities that could affect the ordering of the final + * result array. + */ +public class BuggySimpleTriangleClosingComputation extends + BasicComputation<IntWritable, IntWritable, NullWritable, IntWritable> { + /** Vertices to close the triangle, ranked by frequency of in-msgs */ + private final Map<IntWritable, Integer> closeMap = Maps + .<IntWritable, Integer>newHashMap(); + + @Override + public void compute(Vertex<IntWritable, IntWritable, NullWritable> vertex, + Iterable<IntWritable> messages) throws IOException { + if (getSuperstep() == 0) { + // send list of this vertex's neighbors to all neighbors + for (Edge<IntWritable, NullWritable> edge : vertex.getEdges()) { + sendMessageToAllEdges(vertex, edge.getTargetVertexId()); + } + } else { + for (IntWritable message : messages) { + // INTENTIONAL BUG: the original algorithm has these two lines, which + // avoids the + // NullPointerException, which the current code throws. + // final int current = (closeMap.get(message) == null) ? + // 0 : closeMap.get(message) + 1; + final int current = closeMap.get(message); + closeMap.put(message, current); + } + // make sure the result values are sorted and + // packaged in an IntArrayListWritable for output + Set<Pair> sortedResults = Sets.<Pair>newTreeSet(); + for (Map.Entry<IntWritable, Integer> entry : closeMap.entrySet()) { + sortedResults.add(new Pair(entry.getKey(), entry.getValue())); + } + IntArrayListWritable outputList = new IntArrayListWritable(); + for (Pair pair : sortedResults) { + if (pair.value > 0) { + outputList.add(pair.key); + } else { + break; + } + } + if (outputList.isEmpty()) { + vertex.setValue(new IntWritable(-1)); + } else { + vertex.setValue(outputList.get(0)); + } + } + vertex.voteToHalt(); + } + + /** Quick, immutable K,V storage for sorting in tree set */ + public static class Pair implements Comparable<Pair> { + /** + * key + * + * @param key + * the IntWritable key + */ + private final IntWritable key; + /** + * value + * + * @param value + * the Integer value + */ + private final Integer value; + + /** + * Constructor + * + * @param k + * the key + * @param v + * the value + */ + public Pair(IntWritable k, Integer v) { + key = k; + value = v; + } + + /** + * key getter + * + * @return the key + */ + public IntWritable getKey() { + return key; + } + + /** + * value getter + * + * @return the value + */ + public Integer getValue() { + return value; + } + + /** + * Comparator to quickly sort by values + * + * @param other + * the Pair to compare with THIS + * @return the comparison value as an integer + */ + @Override + public int compareTo(Pair other) { + return other.value - this.value; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof Pair) { + Pair other = (Pair) obj; + return Objects.equal(value, other.value); + } + return false; + } + + @Override + public int hashCode() { + return Objects.hashCode(value); + } + } + + /** + * Utility class for delivering the array of vertices THIS vertex should + * connect with to close triangles with neighbors + */ + @SuppressWarnings("serial") + public static class IntArrayListWritable extends + ArrayListWritable<IntWritable> { + /** Default constructor for reflection */ + public IntArrayListWritable() { + super(); + } + + /** Set storage type for this ArrayListWritable */ + @Override + public void setClass() { + setClass(IntWritable.class); + } + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/exceptiondebug/SimpleTriangleClosingDebugConfig.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/exceptiondebug/SimpleTriangleClosingDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/exceptiondebug/SimpleTriangleClosingDebugConfig.java new file mode 100644 index 0000000..6141702 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/exceptiondebug/SimpleTriangleClosingDebugConfig.java @@ -0,0 +1,34 @@ +/* + * 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.exceptiondebug; + +import org.apache.giraph.debugger.DebugConfig; +import org.apache.hadoop.io.IntWritable; +import org.apache.hadoop.io.NullWritable; + +/** + * Debug configuration file for SimpleTriangleClosingDebugConfig, that is + * configured to catch exceptions. + */ +public class SimpleTriangleClosingDebugConfig extends DebugConfig<IntWritable, + IntWritable, NullWritable, IntWritable, IntWritable> { + @Override + public boolean shouldCatchExceptions() { + return true; + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/exceptiondebug/package-info.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/exceptiondebug/package-info.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/exceptiondebug/package-info.java new file mode 100644 index 0000000..6ace622 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/exceptiondebug/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. + */ + +/** + * An example Giraph program to be debugged using Graft's exception capturing + * functionality. + */ +package org.apache.giraph.debugger.examples.exceptiondebug; http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringComputation.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringComputation.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringComputation.java new file mode 100644 index 0000000..c5aadfe --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringComputation.java @@ -0,0 +1,236 @@ +/* + * 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.graphcoloring; + +import java.io.IOException; + +import org.apache.giraph.debugger.examples.graphcoloring.GraphColoringMaster.Phase; +import org.apache.giraph.debugger.examples.graphcoloring.VertexValue.State; +import org.apache.giraph.graph.BasicComputation; +import org.apache.giraph.graph.Vertex; +import org.apache.hadoop.io.IntWritable; +import org.apache.hadoop.io.LongWritable; +import org.apache.hadoop.io.NullWritable; + +/** + * (Buggy) Giraph implementation of a randomized graph coloring algorithm. + */ +public class GraphColoringComputation extends + BasicComputation<LongWritable, VertexValue, NullWritable, Message> { + + /** + * Cached LongWritable for value one. + */ + private static final LongWritable ONE = new LongWritable(1); + /** + * The current phase. + */ + private Phase phase; + /** + * The current color to assign. + */ + private int colorToAssign; + + @Override + public void preSuperstep() { + phase = Phase.values()[((IntWritable) getAggregatedValue( + GraphColoringMaster.PHASE)).get()]; + colorToAssign = ((IntWritable) getAggregatedValue( + GraphColoringMaster.COLOR_TO_ASSIGN)).get(); + } + + @Override + public void compute(Vertex<LongWritable, VertexValue, NullWritable> vertex, + Iterable<Message> messages) throws IOException { + + // Treat already colored vertices as if it didn't exist in the graph. + if (vertex.getValue().isColored()) { + vertex.voteToHalt(); + return; + } + + State state = vertex.getValue().getState(); + // Nothing's left to do if this vertex has been placed in an independent set + // already. + if (state == State.IN_SET && phase != Phase.COLOR_ASSIGNMENT) { + aggregate(GraphColoringMaster.NUM_VERTICES_IN_SET, ONE); + return; + } + + // if (state == State.NOT_IN_SET && vertex.getNumEdges() == 0 && (phase == + // Phase.EDGE_CLEANING || phase == Phase.CONFLICT_RESOLUTION)) { + // aggregate(GraphColoringMaster.NUM_VERTICES_NOT_IN_SET, ONE); + // return; + // } + + switch (phase) { + case LOTTERY: + switch (state) { + case UNKNOWN: + // Unknown vertices will go through a lottery, and be put in + // "potentially in set" state with probability 1/2d where d is its + // degree. + if (vertex.getNumEdges() == 0) { + setVertexState(vertex, State.IN_SET); + } else if (Math.random() * vertex.getNumEdges() <= 1.0) { + setVertexState(vertex, State.TENTATIVELY_IN_SET); + sendMessageToAllEdges(vertex, new Message(vertex, + Message.Type.WANTS_TO_BE_IN_SET)); + } + break; + + default: + // Nothing to do for others. + break; + } + break; + + case CONFLICT_RESOLUTION: + switch (state) { + case TENTATIVELY_IN_SET: + // When a vertex potentially in set receives a message from its + // neighbor, it must resolve conflicts by deciding to put the vertex + // that has the minimum vertex id. + if (messages.iterator().hasNext()) { + long myId = vertex.getId().get(); + long minId = myId; + if (messages.iterator().hasNext()) { + for (Message message : messages) { + assert message.getType() == Message.Type.WANTS_TO_BE_IN_SET; + long neighborId = message.getSenderVertex(); + if (neighborId < minId) { + minId = neighborId; + } + } + if (minId == myId) { + // Otherwise, it's unknown whether this vertex will be in the + // final + // independent set. + setVertexState(vertex, State.UNKNOWN); + } else { + // Put this vertex in the independent set if it has the minimum + // id. + setVertexState(vertex, State.IN_SET); + sendMessageToAllEdges(vertex, new Message(vertex, + Message.Type.IS_IN_SET)); + } + + } + } else { + setVertexState(vertex, State.IN_SET); + sendMessageToAllEdges(vertex, new Message(vertex, + Message.Type.IS_IN_SET)); + } + break; + + default: + // Nothing to do for others. + break; + } + break; + + case EDGE_CLEANING: + // Count the number of messages received. + int numNeighborsMovedIntoSet = 0; + for (Message message : messages) { + assert message.getType() == Message.Type.IS_IN_SET; + vertex.removeEdges(new LongWritable(message.getSenderVertex())); + ++numNeighborsMovedIntoSet; + } + if (numNeighborsMovedIntoSet > 0) { + // At this phase, we know any vertex that received a notification from + // its neighbor cannot belong to the set. + setVertexState(vertex, State.NOT_IN_SET); + } else { + // Otherwise, we put the vertex back into unknown state, so they can go + // through another lottery. +// setVertexState(vertex, State.UNKNOWN); +// // XXX INTENTIONAL BUG: NOT_IN_SET vertices that did not receive any +// // IS_IN_SET message will also go back to UNKNOWN state, which is +// // undesired. + break; + } + break; + + case COLOR_ASSIGNMENT: + if (state == State.IN_SET) { + // Assign current cycle's color to all IN_SET vertices. + setVertexColor(vertex, colorToAssign); + // Aggregate number of colored vertices. + aggregate(GraphColoringMaster.NUM_VERTICES_COLORED, ONE); + } else { + // For all other vertices, move their state back to UNKNOWN, so they can + // go through another round of maximal independent set finding. + setVertexState(vertex, State.UNKNOWN); + } + break; + + default: + throw new IllegalStateException(); + } + + // Count the number of remaining unknown vertices. + switch (vertex.getValue().getState()) { + case UNKNOWN: + aggregate(GraphColoringMaster.NUM_VERTICES_UNKNOWN, ONE); + break; + + case TENTATIVELY_IN_SET: + aggregate(GraphColoringMaster.NUM_VERTICES_TENTATIVELY_IN_SET, ONE); + break; + + case NOT_IN_SET: + aggregate(GraphColoringMaster.NUM_VERTICES_NOT_IN_SET, ONE); + break; + + case IN_SET: + aggregate(GraphColoringMaster.NUM_VERTICES_IN_SET, ONE); + break; + + default: + break; + } + } + + /** + * Set the vertex color. + * + * @param vertex the vertex + * @param colorToAssign the color + */ + protected void setVertexColor( + Vertex<LongWritable, VertexValue, NullWritable> vertex, int colorToAssign) { + VertexValue value = vertex.getValue(); + value.setColor(colorToAssign); + vertex.setValue(value); + } + + /** + * Set the vertex state. + * + * @param vertex the vertex + * @param newState the new state + */ + protected void setVertexState( + Vertex<LongWritable, VertexValue, NullWritable> vertex, State newState) { + VertexValue value = vertex.getValue(); + value.setState(newState); + vertex.setValue(value); + } + +} http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringDebugConfig.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringDebugConfig.java new file mode 100644 index 0000000..75c2a18 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringDebugConfig.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.graphcoloring; + +import org.apache.giraph.debugger.DebugConfig; +import org.apache.hadoop.io.LongWritable; +import org.apache.hadoop.io.NullWritable; + +/** + * DebugConfig for graph coloring. + */ +public class GraphColoringDebugConfig + extends + DebugConfig<LongWritable, VertexValue, NullWritable, Message, Message> { + + @Override + public boolean shouldCheckVertexValueIntegrity() { + return true; + } + + @Override + public boolean isVertexValueCorrect(LongWritable vertexId, + VertexValue value) { + return value.isColored() && + value.getState().equals(VertexValue.State.IN_SET); + } + + @Override + public boolean shouldCheckMessageIntegrity() { + return true; + } + + @Override + public boolean isMessageCorrect(LongWritable srcId, LongWritable dstId, + Message message, long superstepNo) { + // TODO check message type validity based on phase + // TODO check message type validity based on sender and receiver's state + return message.getType() != null && srcId.get() != dstId.get(); + } + +} http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringMaster.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringMaster.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringMaster.java new file mode 100644 index 0000000..4e2aeb8 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringMaster.java @@ -0,0 +1,163 @@ +/* + * 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.graphcoloring; + +import org.apache.giraph.aggregators.IntMaxAggregator; +import org.apache.giraph.aggregators.LongSumAggregator; +import org.apache.giraph.master.DefaultMasterCompute; +import org.apache.hadoop.io.IntWritable; +import org.apache.hadoop.io.LongWritable; + +/** + * MasterCompute for graph coloring algorithm. + */ +public class GraphColoringMaster extends DefaultMasterCompute { + + /** + * Aggregator name for phase. + */ + public static final String PHASE = "phase"; + /** + * Aggregator name for color to assign. + */ + public static final String COLOR_TO_ASSIGN = "colorToAssign"; + /** + * Aggregator name for number of colored vertices. + */ + public static final String NUM_VERTICES_COLORED = "numVerticesColored"; + /** + * Aggregator name for number of unknown vertices. + */ + public static final String NUM_VERTICES_UNKNOWN = "numVerticesUnknown"; + /** + * Aggregator name for number of vertices in the independent set. + */ + public static final String NUM_VERTICES_IN_SET = "numVerticesInSet"; + /** + * Aggregator name for number of vertices not in the independent set. + */ + public static final String NUM_VERTICES_NOT_IN_SET = "numVerticesNotInSet"; + /** + * Aggregator name for number of vertices tentatively in the independent set. + */ + public static final String NUM_VERTICES_TENTATIVELY_IN_SET = + "numVerticesTentativelyInSet"; + + /** + * Phases in the graph coloring algorithm. + */ + public static enum Phase { + /** + * The phase we select unknown vertices to put into tentatively in-set. + */ + LOTTERY, + /** + * The phase we resolve conflicts between neighboring tentatively + * in-set vertices. + */ + CONFLICT_RESOLUTION, + /** + * The phase we remove edges of in-set vertices. + */ + EDGE_CLEANING, + /** + * The phase we assign colors to the in-set vertices. + */ + COLOR_ASSIGNMENT, + } + + /** + * Current color to assign. + */ + private int colorToAssign; + /** + * Current phase. + */ + private Phase phase; + + @Override + public void initialize() throws InstantiationException, + IllegalAccessException { + registerPersistentAggregator(COLOR_TO_ASSIGN, IntMaxAggregator.class); + colorToAssign = VertexValue.NO_COLOR; + registerPersistentAggregator(PHASE, IntMaxAggregator.class); + phase = null; + + registerPersistentAggregator(NUM_VERTICES_COLORED, LongSumAggregator.class); + registerAggregator(NUM_VERTICES_UNKNOWN, LongSumAggregator.class); + registerAggregator(NUM_VERTICES_TENTATIVELY_IN_SET, + LongSumAggregator.class); + registerAggregator(NUM_VERTICES_NOT_IN_SET, LongSumAggregator.class); + registerAggregator(NUM_VERTICES_IN_SET, LongSumAggregator.class); + } + + @Override + public void compute() { + if (phase != null) { + switch (phase) { + case LOTTERY: + // Move to conflict resolution after selecting a set of vertices. + phase = Phase.CONFLICT_RESOLUTION; + break; + + case CONFLICT_RESOLUTION: + // After resolving conflicts, move on to edge cleaning. + phase = Phase.EDGE_CLEANING; + break; + + case EDGE_CLEANING: + // We can assign colors to the vertices in the independent set if there + // are no remaining UNKNOWNs at a LOTTERY phase. + long numUnknown = ((LongWritable) getAggregatedValue( + NUM_VERTICES_UNKNOWN)).get(); + if (numUnknown == 0) { + // Set an aggregator telling each IN_SET vertex what color to assign. + setAggregatedValue(COLOR_TO_ASSIGN, new IntWritable(++colorToAssign)); + phase = Phase.COLOR_ASSIGNMENT; + } else { + // Repeat finding independent sets after cleaning edges. + // remaining. + phase = Phase.LOTTERY; + } + break; + + case COLOR_ASSIGNMENT: + long numColored = ((LongWritable) getAggregatedValue( + NUM_VERTICES_COLORED)).get(); + if (numColored == getTotalNumVertices()) { + // Halt when all vertices are colored. + haltComputation(); + return; + } + // Start a new cycle of finding maximal independent sets, after + // assigning colors. + phase = Phase.LOTTERY; + break; + + default: + throw new IllegalStateException(); + } + } else { + // First superstep, enter into lottery. + phase = Phase.LOTTERY; + } + + // Set an aggregator to communicate what phase we're in to all vertices. + setAggregatedValue(PHASE, new IntWritable(phase.ordinal())); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringMessageConstraintDebugConfig.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringMessageConstraintDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringMessageConstraintDebugConfig.java new file mode 100644 index 0000000..ae8f250 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringMessageConstraintDebugConfig.java @@ -0,0 +1,44 @@ +/* + * 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.graphcoloring; + +import org.apache.giraph.debugger.DebugConfig; +import org.apache.hadoop.io.LongWritable; +import org.apache.hadoop.io.NullWritable; + +/** + * DebugConfig for checking message constraints of graph coloring. + */ +public class GraphColoringMessageConstraintDebugConfig + extends + DebugConfig<LongWritable, VertexValue, NullWritable, Message, Message> { + + @Override + public boolean shouldCheckMessageIntegrity() { + return true; + } + + @Override + public boolean isMessageCorrect(LongWritable srcId, LongWritable dstId, + Message message, long superstepNo) { + // TODO check message type validity based on phase + // TODO check message type validity based on sender and receiver's state + return message.getType() != null && srcId.get() != dstId.get(); + } + +} http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringVertexValueConstraintDebugConfig.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringVertexValueConstraintDebugConfig.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringVertexValueConstraintDebugConfig.java new file mode 100644 index 0000000..0de6605 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/GraphColoringVertexValueConstraintDebugConfig.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.graphcoloring; + +import org.apache.giraph.debugger.DebugConfig; +import org.apache.hadoop.io.LongWritable; +import org.apache.hadoop.io.NullWritable; + +/** + * DebugConfig for checking vertex value constraints of graph coloring. + */ +public class GraphColoringVertexValueConstraintDebugConfig + extends + DebugConfig<LongWritable, VertexValue, NullWritable, Message, Message> { + + @Override + public boolean shouldCheckVertexValueIntegrity() { + return true; + } + + @Override + public boolean isVertexValueCorrect(LongWritable vertexId, + VertexValue value) { + return value.isColored() && + value.getState().equals(VertexValue.State.IN_SET); + } + +} http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/Message.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/Message.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/Message.java new file mode 100644 index 0000000..07068bd --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/Message.java @@ -0,0 +1,114 @@ +/* + * 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.graphcoloring; + +import java.io.DataInput; +import java.io.DataOutput; +import java.io.IOException; + +import org.apache.giraph.graph.Vertex; +import org.apache.hadoop.io.LongWritable; +import org.apache.hadoop.io.NullWritable; +import org.apache.hadoop.io.Writable; + +/** + * Message for graph coloring. + */ +public class Message implements Writable { + + /** + * Id of the vertex sending this message. + */ + private long senderVertex; + + /** + * Type of the message. + */ + public enum Type { + /** + * The sending vertex is tentatively in the set now. + */ + WANTS_TO_BE_IN_SET, + /** + * The sending vertex is in the independent set now. + */ + IS_IN_SET, + } + + /** + * Whether this message is a match request (null), or a message that grants + * (true) or denies (false) another one. + */ + private Message.Type type = Type.WANTS_TO_BE_IN_SET; + + /** + * Default constructor. + */ + public Message() { + } + + /** + * Constructs a message with sender initialized. + * + * @param vertex + * Sending vertex + */ + public Message(Vertex<LongWritable, VertexValue, NullWritable> vertex) { + this(vertex, Type.WANTS_TO_BE_IN_SET); + } + + /** + * Constructs a message with sender and type. + * + * @param vertex + * Sending vertex + * @param type + * The type of this message + */ + public Message(Vertex<LongWritable, VertexValue, NullWritable> vertex, + Type type) { + this.senderVertex = vertex.getId().get(); + this.type = type; + } + + public long getSenderVertex() { + return senderVertex; + } + + public Type getType() { + return type; + } + + @Override + public String toString() { + return type + " from " + senderVertex; + } + + @Override + public void readFields(DataInput in) throws IOException { + senderVertex = in.readLong(); + type = Type.values()[in.readInt()]; + } + + @Override + public void write(DataOutput out) throws IOException { + out.writeLong(senderVertex); + out.writeInt(type.ordinal()); + } + +} http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/VertexValue.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/VertexValue.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/VertexValue.java new file mode 100644 index 0000000..16d6311 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/VertexValue.java @@ -0,0 +1,125 @@ +/* + * 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.graphcoloring; + +import java.io.DataInput; +import java.io.DataOutput; +import java.io.IOException; + +import org.apache.hadoop.io.Writable; + +/** + * Vertex value for maximal independent set computation. + */ +public class VertexValue implements Writable { + + /** + * Value for an invalid color. + */ + public static final int NO_COLOR = -1; + + /** + * Color of the vertex. + */ + private int color = NO_COLOR; + + /** + * State of the vertex. + */ + public enum State { + /** + * Unknown state. + */ + UNKNOWN("U"), + /** + * State of tentatively in the independent set. + */ + TENTATIVELY_IN_SET("T"), + /** + * State of not in the independent set. + */ + NOT_IN_SET("N"), + /** + * State of being in the independent set. + */ + IN_SET("I"); + + /** + * Abbreviation string of the state. + */ + private final String abbreviation; + + /** + * Constructor with abbreviation string. + * @param abbreviation shorthand string for the state. + */ + private State(String abbreviation) { + this.abbreviation = abbreviation; + } + + public String getAbbreviation() { + return abbreviation; + } + + } + + /** + * State of the vertex. + */ + private State state = State.UNKNOWN; + + public State getState() { + return state; + } + + public void setState(State state) { + this.state = state; + } + + public void setColor(int color) { + this.color = color; + } + + public boolean isColored() { + return state == State.IN_SET && color != NO_COLOR; + } + + @Override + public void readFields(DataInput in) throws IOException { + state = State.values()[in.readInt()]; + color = in.readInt(); + } + + @Override + public void write(DataOutput out) throws IOException { + out.writeInt(state.ordinal()); + out.writeInt(color); + } + + @Override + public String toString() { + StringBuilder sb = new StringBuilder(); + sb.append("color="); + sb.append(color == NO_COLOR ? "?" : color); + sb.append(" ("); + sb.append(state.getAbbreviation()); + sb.append(")"); + return sb.toString(); + } + +} http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/package-info.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/package-info.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/package-info.java new file mode 100644 index 0000000..a686624 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/graphcoloring/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. + */ + +/** + * Example Giraph programs that (incorrectly) implement a graph coloring + * algorithm for demonstrating Graft's capture-visualize-reproduce + * functionalities. + */ +package org.apache.giraph.debugger.examples.graphcoloring; http://git-wip-us.apache.org/repos/asf/giraph/blob/8675c84a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/BuggyConnectedComponentsDebugComputationModified.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/BuggyConnectedComponentsDebugComputationModified.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/BuggyConnectedComponentsDebugComputationModified.java new file mode 100644 index 0000000..4cc3d7e --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/BuggyConnectedComponentsDebugComputationModified.java @@ -0,0 +1,104 @@ +/* + * 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.instrumented; + +import java.io.IOException; + +import org.apache.giraph.debugger.instrumenter.AbstractInterceptingComputation; +import org.apache.giraph.edge.Edge; +import org.apache.giraph.graph.Vertex; +import org.apache.hadoop.io.IntWritable; +import org.apache.hadoop.io.NullWritable; + +/** + * WARNING: This class is should be used only for development. It is put in the + * Graft source tree to demonstrate to users the two classes that Graft + * generates at runtime when instrumenting a {@link Computation} class. This is + * the example for {@link BuggyConnectedComponentsComputation}. The other class + * Graft generates is {@link BuggyConnectedComponentsDebugComputationToRun}. + * Please see the Graft documentation for more details on how Graft instruments + * {@link Computation} classes. + * + * 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 abstract class BuggyConnectedComponentsDebugComputationModified + extends AbstractInterceptingComputation<IntWritable, IntWritable, + NullWritable, IntWritable, IntWritable> { + + /** + * 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<IntWritable, IntWritable, NullWritable> vertex, + Iterable<IntWritable> messages) throws IOException { + int currentComponent = vertex.getValue().get(); + + if (getSuperstep() == 0) { + vertex.setValue(new IntWritable(currentComponent)); + for (Edge<IntWritable, NullWritable> edge : vertex.getEdges()) { + sendMessage(edge.getTargetVertexId(), vertex.getValue()); + } + vertex.voteToHalt(); + return; + } + + boolean changed = false; + // did we get a smaller id ? + for (IntWritable message : messages) { + int candidateComponent = message.get(); + // INTENTIONAL BUG: in the original algorithm the value of the comparison + // sign should be <. + if (candidateComponent > currentComponent) { + System.out.print("changing value in superstep: " + getSuperstep() + + " vertex.id: " + vertex.getId() + " newComponent: " + + candidateComponent + "\n"); + currentComponent = candidateComponent; + changed = true; + } + } + + // propagate new component id to the neighbors + if (changed) { + vertex.setValue(new IntWritable(currentComponent)); + for (Edge<IntWritable, 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/instrumented/BuggySimpleShortestPathsDebugComputationModified.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/BuggySimpleShortestPathsDebugComputationModified.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/BuggySimpleShortestPathsDebugComputationModified.java new file mode 100644 index 0000000..ad85ce1 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/BuggySimpleShortestPathsDebugComputationModified.java @@ -0,0 +1,116 @@ +/* + * 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.instrumented; + +import java.io.IOException; + +import org.apache.giraph.Algorithm; +import org.apache.giraph.conf.LongConfOption; +import org.apache.giraph.debugger.examples.simpledebug.SimpleShortestPathsMaster; +import org.apache.giraph.debugger.instrumenter.AbstractInterceptingComputation; +import org.apache.giraph.edge.Edge; +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; + +/** + * WARNING: This class is should be used only for development. It is put in the + * Graft source tree to demonstrate to users the two classes that Graft + * generates at runtime when instrumenting a {@link Computation} class. This is + * the example for {@link BuggySimpleShortestPathsComputation}. The other class + * Graft generates is {@link BuggySimpleShortestPathsDebugComputationToRun}. + * Please see the Graft documentation for more details on how Graft instruments + * {@link Computation} classes. + * + * Debug version of SimpleShortestPathsComputation. + */ +@Algorithm(name = "Shortest paths", description = "Finds all shortest paths" + + "from a selected vertex") +public abstract class BuggySimpleShortestPathsDebugComputationModified + extends AbstractInterceptingComputation<LongWritable, DoubleWritable, + FloatWritable, DoubleWritable, 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(BuggySimpleShortestPathsDebugComputationModified.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 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/instrumented/BuggySimpleTriangleClosingDebugComputationModified.java ---------------------------------------------------------------------- diff --git a/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/BuggySimpleTriangleClosingDebugComputationModified.java b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/BuggySimpleTriangleClosingDebugComputationModified.java new file mode 100644 index 0000000..10bccf1 --- /dev/null +++ b/giraph-debugger/src/main/java/org/apache/giraph/debugger/examples/instrumented/BuggySimpleTriangleClosingDebugComputationModified.java @@ -0,0 +1,216 @@ +/* + * 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.instrumented; + +import java.io.IOException; +import java.util.Map; +import java.util.Set; + +import org.apache.giraph.debugger.instrumenter.AbstractInterceptingComputation; +import org.apache.giraph.edge.Edge; +import org.apache.giraph.graph.Vertex; +import org.apache.giraph.utils.ArrayListWritable; +import org.apache.hadoop.io.IntWritable; +import org.apache.hadoop.io.NullWritable; + +import com.google.common.base.Objects; +import com.google.common.collect.Maps; +import com.google.common.collect.Sets; + +/** + * WARNING: This class is should be used only for development. It is put in the + * Graft source tree to demonstrate to users the two classes that Graft + * generates at runtime when instrumenting a {@link Computation} class. This is + * the example for {@link ConnectedComponentsComputation}. The other + * class Graft generates is + * {@link BuggySimpleTriangleClosingDebugComputationToRun}. Please see the Graft + * documentation for more details on how Graft instruments {@link Computation} + * classes. + * + * Demonstrates triangle closing in simple, unweighted graphs for Giraph. + * + * Triangle Closing: Vertex A and B maintain out-edges to C and D The algorithm, + * when finished, populates all vertices' value with an array of Writables + * representing all the vertices that each should form an out-edge to (connect + * with, if this is a social graph.) In this example, vertices A and B would + * hold empty arrays since they are already connected with C and D. Results: If + * the graph is undirected, C would hold value, D and D would hold value C, + * since both are neighbors of A and B and yet both were not previously + * connected to each other. + * + * In a social graph, the result values for vertex X would represent people that + * are likely a part of a person X's social circle (they know one or more people + * X is connected to already) but X had not previously met them yet. Given this + * new information, X can decide to connect to vertices (peoople) in the result + * array or not. + * + * Results at each vertex are ordered in terms of the # of neighbors who are + * connected to each vertex listed in the final vertex value. The more of a + * vertex's neighbors who "know" someone, the stronger your social relationship + * is presumed to be to that vertex (assuming a social graph) and the more + * likely you should connect with them. + * + * In this implementation, Edge Values are not used, but could be adapted to + * represent additional qualities that could affect the ordering of the final + * result array. + */ +public abstract class BuggySimpleTriangleClosingDebugComputationModified + extends AbstractInterceptingComputation<IntWritable, IntWritable, + NullWritable, IntWritable, IntWritable> { + /** Vertices to close the triangle, ranked by frequency of in-msgs */ + private final Map<IntWritable, Integer> closeMap = Maps + .<IntWritable, Integer>newHashMap(); + + @Override + public void compute(Vertex<IntWritable, IntWritable, NullWritable> vertex, + Iterable<IntWritable> messages) throws IOException { + if (getSuperstep() == 0) { + // send list of this vertex's neighbors to all neighbors + for (Edge<IntWritable, NullWritable> edge : vertex.getEdges()) { + sendMessageToAllEdges(vertex, edge.getTargetVertexId()); + } + } else { + for (IntWritable message : messages) { + // INTENTIONAL BUG: the original algorithm has these two lines, which + // avoids the + // NullPointerException, which the current code throws. + // final int current = (closeMap.get(message) == null) ? + // 0 : closeMap.get(message) + 1; + final int current = closeMap.get(message); + closeMap.put(message, current); + } + // make sure the result values are sorted and + // packaged in an IntArrayListWritable for output + Set<Pair> sortedResults = Sets.<Pair>newTreeSet(); + for (Map.Entry<IntWritable, Integer> entry : closeMap.entrySet()) { + sortedResults.add(new Pair(entry.getKey(), entry.getValue())); + } + IntArrayListWritable outputList = new IntArrayListWritable(); + for (Pair pair : sortedResults) { + if (pair.value > 0) { + outputList.add(pair.key); + } else { + break; + } + } + if (outputList.isEmpty()) { + vertex.setValue(new IntWritable(-1)); + } else { + vertex.setValue(outputList.get(0)); + } + } + vertex.voteToHalt(); + } + + /** Quick, immutable K,V storage for sorting in tree set */ + public static class Pair implements Comparable<Pair> { + /** + * key + * + * @param key + * the IntWritable key + */ + private final IntWritable key; + /** + * value + * + * @param value + * the Integer value + */ + private final Integer value; + + /** + * Constructor + * + * @param k + * the key + * @param v + * the value + */ + public Pair(IntWritable k, Integer v) { + key = k; + value = v; + } + + /** + * key getter + * + * @return the key + */ + public IntWritable getKey() { + return key; + } + + /** + * value getter + * + * @return the value + */ + public Integer getValue() { + return value; + } + + /** + * Comparator to quickly sort by values + * + * @param other + * the Pair to compare with THIS + * @return the comparison value as an integer + */ + @Override + public int compareTo(Pair other) { + return other.value - this.value; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj instanceof Pair) { + Pair other = (Pair) obj; + return Objects.equal(value, other.value); + } + return false; + } + + @Override + public int hashCode() { + return Objects.hashCode(value); + } + } + + /** + * Utility class for delivering the array of vertices THIS vertex should + * connect with to close triangles with neighbors + */ + @SuppressWarnings("serial") + public static class IntArrayListWritable extends + ArrayListWritable<IntWritable> { + /** Default constructor for reflection */ + public IntArrayListWritable() { + super(); + } + + /** Set storage type for this ArrayListWritable */ + @Override + public void setClass() { + setClass(IntWritable.class); + } + } +}
