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 <alessandro@fb.com>
Authored: Fri Mar 29 11:27:54 2013 -0700
Committer: Alessandro Presta <alessandro@fb.com>
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;
+ }
+}
|