giraph-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From apre...@apache.org
Subject git commit: updated refs/heads/trunk to 0e04147
Date Fri, 29 Mar 2013 18:28:19 GMT
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;
+  }
+}


Mime
View raw message