Updated Branches: refs/heads/trunk c5fe858e9 -> 3d4f31343
GIRAPH-670: [easy] Example Max Computation (nitay) Project: http://git-wip-us.apache.org/repos/asf/giraph/repo Commit: http://git-wip-us.apache.org/repos/asf/giraph/commit/3d4f3134 Tree: http://git-wip-us.apache.org/repos/asf/giraph/tree/3d4f3134 Diff: http://git-wip-us.apache.org/repos/asf/giraph/diff/3d4f3134 Branch: refs/heads/trunk Commit: 3d4f31343c3686435696e75ce88a75c9bffb024e Parents: c5fe858 Author: Nitay Joffe <[email protected]> Authored: Thu May 23 19:12:36 2013 -0400 Committer: Nitay Joffe <[email protected]> Committed: Wed Jun 5 09:27:36 2013 +0200 ---------------------------------------------------------------------- CHANGELOG | 2 + .../org/apache/giraph/examples/MaxComputation.java | 47 ++++++++++ .../apache/giraph/examples/MaxComputationTest.java | 67 +++++++++++++++ 3 files changed, 116 insertions(+), 0 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/giraph/blob/3d4f3134/CHANGELOG ---------------------------------------------------------------------- diff --git a/CHANGELOG b/CHANGELOG index 99d6958..fe0c8fd 100644 --- a/CHANGELOG +++ b/CHANGELOG @@ -1,6 +1,8 @@ Giraph Change Log Release 1.1.0 - unreleased + GIRAPH-670: [easy] Example Max Computation (nitay) + GIRAPH-675: Mutable edge iterator gets corrupted by calling vertex.getNumEdges() during iteration (apresta) http://git-wip-us.apache.org/repos/asf/giraph/blob/3d4f3134/giraph-examples/src/main/java/org/apache/giraph/examples/MaxComputation.java ---------------------------------------------------------------------- diff --git a/giraph-examples/src/main/java/org/apache/giraph/examples/MaxComputation.java b/giraph-examples/src/main/java/org/apache/giraph/examples/MaxComputation.java new file mode 100644 index 0000000..b97fc6d --- /dev/null +++ b/giraph-examples/src/main/java/org/apache/giraph/examples/MaxComputation.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.examples; + +import org.apache.giraph.graph.BasicComputation; +import org.apache.giraph.graph.Vertex; +import org.apache.hadoop.io.IntWritable; +import org.apache.hadoop.io.NullWritable; + +import java.io.IOException; + +/** + * Simple algorithm that computes the max value in the graph. + */ +public class MaxComputation extends BasicComputation<IntWritable, IntWritable, + NullWritable, IntWritable> { + @Override + public void compute(Vertex<IntWritable, IntWritable, NullWritable> vertex, + Iterable<IntWritable> messages) throws IOException { + boolean changed = false; + for (IntWritable message : messages) { + if (vertex.getValue().get() < message.get()) { + vertex.setValue(message); + changed = true; + } + } + if (getSuperstep() == 0 || changed) { + sendMessageToAllEdges(vertex, vertex.getValue()); + } + vertex.voteToHalt(); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/3d4f3134/giraph-examples/src/test/java/org/apache/giraph/examples/MaxComputationTest.java ---------------------------------------------------------------------- diff --git a/giraph-examples/src/test/java/org/apache/giraph/examples/MaxComputationTest.java b/giraph-examples/src/test/java/org/apache/giraph/examples/MaxComputationTest.java new file mode 100644 index 0000000..dd64484 --- /dev/null +++ b/giraph-examples/src/test/java/org/apache/giraph/examples/MaxComputationTest.java @@ -0,0 +1,67 @@ +/* + * 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.examples; + +import org.apache.giraph.conf.GiraphConfiguration; +import org.apache.giraph.io.formats.IdWithValueTextOutputFormat; +import org.apache.giraph.io.formats.IntIntNullTextInputFormat; +import org.apache.giraph.utils.InternalVertexRunner; +import org.junit.Test; + +import com.google.common.collect.Maps; + +import java.util.Map; + +import static org.junit.Assert.assertEquals; + +/** + * Test for max computation + */ +public class MaxComputationTest { + @Test + public void testMax() throws Exception { + String[] graph = { + "5 1", + "1 5 2", + "2 5", + }; + + GiraphConfiguration conf = new GiraphConfiguration(); + conf.setComputationClass(MaxComputation.class); + conf.setVertexInputFormatClass(IntIntNullTextInputFormat.class); + conf.setVertexOutputFormatClass(IdWithValueTextOutputFormat.class); + Iterable<String> results = InternalVertexRunner.run(conf, graph); + + Map<Integer, Integer> values = parseResults(results); + assertEquals(3, values.size()); + assertEquals(5, (int) values.get(1)); + assertEquals(5, (int) values.get(2)); + assertEquals(5, (int) values.get(5)); + } + + private static Map<Integer, Integer> parseResults(Iterable<String> results) { + Map<Integer, Integer> values = Maps.newHashMap(); + for (String line : results) { + String[] tokens = line.split("\\s+"); + int id = Integer.valueOf(tokens[0]); + int value = Integer.valueOf(tokens[1]); + values.put(id, value); + } + return values; + } +}
