Updated Branches: refs/heads/trunk 9c47b670a -> 0e0414784
Fix GIRAPH-577 (adds missing files) Project: http://git-wip-us.apache.org/repos/asf/giraph/repo Commit: http://git-wip-us.apache.org/repos/asf/giraph/commit/0e041478 Tree: http://git-wip-us.apache.org/repos/asf/giraph/tree/0e041478 Diff: http://git-wip-us.apache.org/repos/asf/giraph/diff/0e041478 Branch: refs/heads/trunk Commit: 0e0414784b2ecd7b63dced8cf69aa0854106116d Parents: 9c47b67 Author: Alessandro Presta <[email protected]> Authored: Fri Mar 29 11:27:54 2013 -0700 Committer: Alessandro Presta <[email protected]> Committed: Fri Mar 29 11:27:54 2013 -0700 ---------------------------------------------------------------------- .../giraph/utils/InMemoryVertexInputFormat.java | 110 ++++++++ .../java/org/apache/giraph/utils/TestGraph.java | 217 +++++++++++++++ .../ConnectedComponentsVertexTestInMemory.java | 147 ++++++++++ 3 files changed, 474 insertions(+), 0 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/giraph/blob/0e041478/giraph-core/src/main/java/org/apache/giraph/utils/InMemoryVertexInputFormat.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/main/java/org/apache/giraph/utils/InMemoryVertexInputFormat.java b/giraph-core/src/main/java/org/apache/giraph/utils/InMemoryVertexInputFormat.java new file mode 100644 index 0000000..0ed9155 --- /dev/null +++ b/giraph-core/src/main/java/org/apache/giraph/utils/InMemoryVertexInputFormat.java @@ -0,0 +1,110 @@ +/* + * 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.utils; + +import java.io.IOException; +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; +import org.apache.giraph.bsp.BspInputSplit; +import org.apache.giraph.graph.Vertex; +import org.apache.giraph.io.VertexInputFormat; +import org.apache.giraph.io.VertexReader; +import org.apache.hadoop.io.Writable; +import org.apache.hadoop.io.WritableComparable; +import org.apache.hadoop.mapreduce.InputSplit; +import org.apache.hadoop.mapreduce.JobContext; +import org.apache.hadoop.mapreduce.TaskAttemptContext; + +/** + * An input format that reads the input graph in memory. Used for unit tests. + * + * @param <I> The Input + * @param <V> The vertex type + * @param <E> The edge type + * @param <M> The message type + */ +public class InMemoryVertexInputFormat<I extends WritableComparable, + V extends Writable, + E extends Writable, + M extends Writable> + extends VertexInputFormat<I, V, E, M> { + /** The graph */ + private static TestGraph GRAPH; + + public static void setGraph(TestGraph graph) { + InMemoryVertexInputFormat.GRAPH = graph; + } + + public static TestGraph getGraph() { + return GRAPH; + } + + @Override + public List<InputSplit> getSplits(JobContext context, int minSplitCountHint) + throws IOException, InterruptedException { + // This is meaningless, the VertexReader will generate all the test + // data. + List<InputSplit> inputSplitList = new ArrayList<InputSplit>(); + for (int i = 0; i < minSplitCountHint; ++i) { + inputSplitList.add(new BspInputSplit(i, minSplitCountHint)); + } + return inputSplitList; + } + + @Override + public VertexReader<I, V, E, M> createVertexReader(InputSplit inputSpplit, + TaskAttemptContext context) throws IOException { + + return new VertexReader<I, V, E, M>() { + /** The iterator */ + private Iterator<Vertex<I, V, E, M>> vertexIterator; + private Vertex<I, V, E, M> currentVertex; + + @Override + public void initialize(InputSplit inputSplit, + TaskAttemptContext context) { + vertexIterator = GRAPH.iterator(); + } + + @Override + public boolean nextVertex() { + if (vertexIterator.hasNext()) { + currentVertex = vertexIterator.next(); + return true; + } + return false; + } + + @Override + public Vertex<I, V, E, M> getCurrentVertex() { + return currentVertex; + } + + @Override + public void close() { + } + + @Override + public float getProgress() { + return 0; + } + }; + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/0e041478/giraph-core/src/main/java/org/apache/giraph/utils/TestGraph.java ---------------------------------------------------------------------- diff --git a/giraph-core/src/main/java/org/apache/giraph/utils/TestGraph.java b/giraph-core/src/main/java/org/apache/giraph/utils/TestGraph.java new file mode 100644 index 0000000..e5c2fdd --- /dev/null +++ b/giraph-core/src/main/java/org/apache/giraph/utils/TestGraph.java @@ -0,0 +1,217 @@ +/* + * 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.utils; + +import java.util.HashMap; +import java.util.Iterator; +import java.util.List; +import java.util.Map.Entry; + +import org.apache.giraph.conf.GiraphClasses; +import org.apache.giraph.conf.GiraphConfiguration; +import org.apache.giraph.conf.ImmutableClassesGiraphConfiguration; +import org.apache.giraph.edge.Edge; +import org.apache.giraph.edge.EdgeFactory; +import org.apache.giraph.graph.Vertex; +import org.apache.hadoop.io.Writable; +import org.apache.hadoop.io.WritableComparable; + +import com.google.common.base.Objects; +import com.google.common.collect.Lists; +import com.google.common.collect.Maps; + +/** + * TestGraph class for in-memory testing. + * + * @param <I> Vertex index type + * @param <V> Vertex type + * @param <E> Edge type + * @param <M> Message type + */ +public class TestGraph<I extends WritableComparable, + V extends Writable, + E extends Writable, + M extends Writable> + implements Iterable<Vertex<I, V, E, M>> { + /** The vertex values */ + private final HashMap<I, Vertex<I, V, E, M>> vertices = Maps.newHashMap(); + /** The configuration */ + private ImmutableClassesGiraphConfiguration<I, V, E, M> conf; + + /** + * Constructor requiring classes + * + * @param classes Should have vertex and edge classes set. + */ + public TestGraph(GiraphClasses<I, V, E, M> classes) { + super(); + setConf(classes); + } + + public HashMap<I, Vertex<I, V, E, M>> getVertices() { + return vertices; + } + + /** + * Clear all data + * + */ + public void clear() { + vertices.clear(); + } + + /** + * Add vertex with given ID + * + * @param id the index + * @param value the value + * @param edges all edges + * @return this + */ + public TestGraph<I, V, E, M> addVertex(I id, V value, + Entry<I, E>... edges) { + Vertex<I, V, E, M> v = makeVertex(id, value, edges); + vertices.put(id, v); + return this; + } + + /** + * Add an edge to an existing vertex + * + * @param vertexId Edge origin + * @param edgePair The edge + * @return this + */ + public TestGraph<I, V, E, M> addEdge(I vertexId, Entry<I, E> edgePair) { + if (!vertices.containsKey(vertexId)) { + Vertex<I, V, E, M> v = getConf().createVertex(); + v.initialize(vertexId, getConf().createVertexValue()); + vertices.put(vertexId, v); + } + vertices.get(vertexId) + .addEdge((Edge<I, E>) EdgeFactory.create(edgePair.getKey(), + edgePair.getValue())); + return this; + } + + /** + * Add an edge to an existing vertex + * + * @param vertexId Edge origin + * @param toVertex Edge destination + * @param edgeValue Edge value + * @return this + */ + public TestGraph<I, V, E, M> addEdge(I vertexId, I toVertex, E edgeValue) { + if (!vertices.containsKey(vertexId)) { + Vertex<I, V, E, M> v = getConf().createVertex(); + v.initialize(vertexId, getConf().createVertexValue()); + vertices.put(vertexId, v); + } + vertices.get(vertexId) + .addEdge((Edge<I, E>) EdgeFactory.create(toVertex, edgeValue)); + return this; + } + /** + * An iterator over the ids + * + * @return the iterator + */ + public Iterator<I> idIterator() { + return vertices.keySet().iterator(); + } + + /** + * An iterator over the vertices + * + * @return the iterator + */ + public Iterator<Vertex<I, V, E, M>> iterator() { + return vertices.values().iterator(); + } + + /** + * Return a given vertex + * + * @param id the id + * @return the value + */ + public Vertex<I, V, E, M> getVertex(I id) { + return vertices.get(id); + } + + /** + * Create edges for given ids + * + * @param destEdgess ids to which the edges link + * @return an iterable containing the edges + */ + protected Iterable<Edge<I, E>> + createEdges(Entry<I, E>... destEdgess) { + List<Edge<I, E>> edgesList = Lists.newArrayList(); + for (Entry<I, E> e: destEdgess) { + edgesList.add((Edge<I, E>) EdgeFactory.create(e.getKey(), e.getValue())); + } + return edgesList; + } + + /** + * Create a vertex + * + * @param id the id of the vertex + * @param value the vertex value + * @param edges edges to other vertices + * @return a new vertex + */ + protected Vertex<I, V, E, M> makeVertex(I id, V value, + Entry<I, E>... edges) { + @SuppressWarnings("unchecked") + Vertex<I, V, E, M> vertex = getConf().createVertex(); + vertex.initialize(id, value, createEdges(edges)); + return vertex; + } + + /** + * Get the configuration + * + * @return the configuration + */ + public ImmutableClassesGiraphConfiguration<I, V, E, M> getConf() { + return conf; + } + + /** + * Create a configuration from giraph classes + * + * @param classes Should have vertex and edge class set + */ + public void setConf(GiraphClasses<I, V, E, M> classes) { + GiraphConfiguration giraphConf = new GiraphConfiguration(); + giraphConf.setVertexClass(classes.getVertexClass()); + giraphConf.setVertexEdgesClass(classes.getVertexEdgesClass()); + giraphConf.setVertexValueFactoryClass(classes.getVertexValueFactoryClass()); + + conf = new ImmutableClassesGiraphConfiguration(giraphConf); + } + + @Override + public String toString() { + return Objects.toStringHelper(this).add("vertices", vertices).toString(); + } +} http://git-wip-us.apache.org/repos/asf/giraph/blob/0e041478/giraph-examples/src/test/java/org/apache/giraph/examples/ConnectedComponentsVertexTestInMemory.java ---------------------------------------------------------------------- diff --git a/giraph-examples/src/test/java/org/apache/giraph/examples/ConnectedComponentsVertexTestInMemory.java b/giraph-examples/src/test/java/org/apache/giraph/examples/ConnectedComponentsVertexTestInMemory.java new file mode 100644 index 0000000..27cd267 --- /dev/null +++ b/giraph-examples/src/test/java/org/apache/giraph/examples/ConnectedComponentsVertexTestInMemory.java @@ -0,0 +1,147 @@ +/* + * 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 com.google.common.base.Splitter; +import com.google.common.collect.HashMultimap; +import com.google.common.collect.ImmutableMap; +import com.google.common.collect.Iterables; +import com.google.common.collect.SetMultimap; +import org.apache.giraph.combiner.MinimumIntCombiner; +import org.apache.giraph.conf.GiraphClasses; +import org.apache.giraph.graph.Vertex; +import org.apache.giraph.io.formats.IdWithValueTextOutputFormat; +import org.apache.giraph.io.formats.IntIntNullIntTextInputFormat; +import org.apache.giraph.utils.InternalVertexRunner; +import org.apache.giraph.utils.TestGraph; +import org.apache.giraph.edge.ByteArrayEdges; +import org.apache.giraph.edge.EdgeFactory; +import org.apache.giraph.edge.VertexEdges; +import org.apache.hadoop.io.IntWritable; +import org.apache.hadoop.io.NullWritable; +import org.apache.hadoop.io.Writable; +import org.apache.log4j.Logger; +import org.junit.Test; + +import java.util.Map; +import java.util.Map.Entry; +import java.util.AbstractMap.SimpleEntry; +import java.util.Set; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertTrue; + +/** + * Tests for {@link ConnectedComponentsVertex} + */ +public class ConnectedComponentsVertexTestInMemory { + public static Entry<IntWritable, NullWritable>[] makeEdges(int... args){ + Entry<IntWritable, NullWritable> result[] = + new Entry[args.length]; + for (int i=0; i<args.length; i++){ + result[i] = new SimpleEntry<IntWritable, NullWritable>( + new IntWritable(args[i]), NullWritable.get()); + } + return result; + } + /** + * A local integration test on toy data + */ + @Test + public void testToyData() throws Exception { + GiraphClasses<IntWritable, + IntWritable, + NullWritable, + IntWritable > classes = new GiraphClasses(); + classes.setVertexClass(ConnectedComponentsVertex.class); + classes.setVertexEdgesClass(ByteArrayEdges.class); + classes.setCombinerClass(MinimumIntCombiner.class); + + TestGraph<IntWritable, IntWritable, NullWritable, IntWritable> graph = + new TestGraph<IntWritable, + IntWritable, + NullWritable, + IntWritable> (classes); + // a small graph with three components + graph.addVertex(new IntWritable(1), new IntWritable(1), makeEdges(2, 3)) + .addVertex(new IntWritable(2), new IntWritable(2), makeEdges(1, 4, 5)) + .addVertex(new IntWritable(3), new IntWritable(3), makeEdges(1, 4)) + .addVertex(new IntWritable(4), new IntWritable(4), + makeEdges(2, 3, 5, 13)) + .addVertex(new IntWritable(5), new IntWritable(5), + makeEdges(2, 4, 12, 13)) + .addVertex(new IntWritable(12), new IntWritable(12), makeEdges(5, 13)) + .addVertex(new IntWritable(13), new IntWritable(13), makeEdges(4, 5, 12)) + .addVertex(new IntWritable(6), new IntWritable(6), makeEdges(7, 8)) + .addVertex(new IntWritable(7), new IntWritable(7), makeEdges(6, 10, 11)) + .addVertex(new IntWritable(8), new IntWritable(8), makeEdges(6, 10)) + .addVertex(new IntWritable(10), new IntWritable(10), makeEdges(7, 8, 11)) + .addVertex(new IntWritable(11), new IntWritable(11), makeEdges(7, 10)) + .addVertex(new IntWritable(9), new IntWritable(9)); + + Map<String, String> emptyParams = ImmutableMap.of(); + + // run internally + TestGraph<IntWritable, IntWritable, NullWritable, IntWritable> results = + InternalVertexRunner.run(classes, emptyParams, graph); + + SetMultimap<Integer,Integer> components = parseResults(results); + + Set<Integer> componentIDs = components.keySet(); + assertEquals(3, componentIDs.size()); + assertTrue(componentIDs.contains(1)); + assertTrue(componentIDs.contains(6)); + assertTrue(componentIDs.contains(9)); + + Set<Integer> componentOne = components.get(1); + assertEquals(7, componentOne.size()); + assertTrue(componentOne.contains(1)); + assertTrue(componentOne.contains(2)); + assertTrue(componentOne.contains(3)); + assertTrue(componentOne.contains(4)); + assertTrue(componentOne.contains(5)); + assertTrue(componentOne.contains(12)); + assertTrue(componentOne.contains(13)); + + Set<Integer> componentTwo = components.get(6); + assertEquals(5, componentTwo.size()); + assertTrue(componentTwo.contains(6)); + assertTrue(componentTwo.contains(7)); + assertTrue(componentTwo.contains(8)); + assertTrue(componentTwo.contains(10)); + assertTrue(componentTwo.contains(11)); + + Set<Integer> componentThree = components.get(9); + assertEquals(1, componentThree.size()); + assertTrue(componentThree.contains(9)); + } + + private SetMultimap<Integer,Integer> parseResults( + TestGraph<IntWritable, IntWritable, NullWritable, IntWritable> results) { + SetMultimap<Integer,Integer> components = HashMultimap.create(); + for (Vertex<IntWritable, + IntWritable, + NullWritable, + IntWritable> vertex: results) { + int component = vertex.getValue().get(); + components.put(component, vertex.getId().get()); + } + return components; + } +}
