You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@giraph.apache.org by ma...@apache.org on 2017/06/02 18:38:36 UTC
git commit: updated refs/heads/trunk to ea7753f
Repository: giraph
Updated Branches:
refs/heads/trunk e2f82b25d -> ea7753f06
JIRA-1149
closes #40
Project: http://git-wip-us.apache.org/repos/asf/giraph/repo
Commit: http://git-wip-us.apache.org/repos/asf/giraph/commit/ea7753f0
Tree: http://git-wip-us.apache.org/repos/asf/giraph/tree/ea7753f0
Diff: http://git-wip-us.apache.org/repos/asf/giraph/diff/ea7753f0
Branch: refs/heads/trunk
Commit: ea7753f06b2fe66df61b63a49558ff80ac3a09bb
Parents: e2f82b2
Author: Dionysios Logothetis <di...@fb.com>
Authored: Fri Jun 2 11:38:18 2017 -0700
Committer: Maja Kabiljo <ma...@fb.com>
Committed: Fri Jun 2 11:38:18 2017 -0700
----------------------------------------------------------------------
.../apache/giraph/edge/IdAndNullArrayEdges.java | 5 +
.../giraph/edge/IdAndValueArrayEdges.java | 9 +
.../giraph/edge/IdAndNullArrayEdgesTest.java | 242 ++++++++++++++++++
.../giraph/edge/IdAndValueArrayEdgesTest.java | 244 +++++++++++++++++++
4 files changed, 500 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/giraph/blob/ea7753f0/giraph-core/src/main/java/org/apache/giraph/edge/IdAndNullArrayEdges.java
----------------------------------------------------------------------
diff --git a/giraph-core/src/main/java/org/apache/giraph/edge/IdAndNullArrayEdges.java b/giraph-core/src/main/java/org/apache/giraph/edge/IdAndNullArrayEdges.java
index 0799c64..6e12318 100644
--- a/giraph-core/src/main/java/org/apache/giraph/edge/IdAndNullArrayEdges.java
+++ b/giraph-core/src/main/java/org/apache/giraph/edge/IdAndNullArrayEdges.java
@@ -21,6 +21,7 @@ import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
import java.util.Iterator;
+import java.util.NoSuchElementException;
import org.apache.giraph.conf.ImmutableClassesGiraphConfigurable;
import org.apache.giraph.conf.ImmutableClassesGiraphConfiguration;
@@ -75,6 +76,7 @@ public class IdAndNullArrayEdges<I extends WritableComparable>
@Override
public void initialize(int capacity) {
+ neighbors.clear();
neighbors.setCapacity(capacity);
}
@@ -158,6 +160,9 @@ public class IdAndNullArrayEdges<I extends WritableComparable>
@Override
public MutableEdge<I, NullWritable> next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
neighbors.getIntoW(offset++, representativeEdge.getTargetVertexId());
return representativeEdge;
}
http://git-wip-us.apache.org/repos/asf/giraph/blob/ea7753f0/giraph-core/src/main/java/org/apache/giraph/edge/IdAndValueArrayEdges.java
----------------------------------------------------------------------
diff --git a/giraph-core/src/main/java/org/apache/giraph/edge/IdAndValueArrayEdges.java b/giraph-core/src/main/java/org/apache/giraph/edge/IdAndValueArrayEdges.java
index c22dbc3..5af4fec 100644
--- a/giraph-core/src/main/java/org/apache/giraph/edge/IdAndValueArrayEdges.java
+++ b/giraph-core/src/main/java/org/apache/giraph/edge/IdAndValueArrayEdges.java
@@ -21,6 +21,7 @@ import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
import java.util.Iterator;
+import java.util.NoSuchElementException;
import org.apache.giraph.conf.ImmutableClassesGiraphConfigurable;
import org.apache.giraph.conf.ImmutableClassesGiraphConfiguration;
@@ -78,7 +79,9 @@ public class IdAndValueArrayEdges<I extends WritableComparable,
@Override
public void initialize(int capacity) {
+ neighborIds.clear();
neighborIds.setCapacity(capacity);
+ neighborEdgeValues.clear();
neighborEdgeValues.setCapacity(capacity);
}
@@ -162,6 +165,9 @@ public class IdAndValueArrayEdges<I extends WritableComparable,
@Override
public Edge<I, E> next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
neighborIds.getIntoW(index, representativeEdge.getTargetVertexId());
neighborEdgeValues.getIntoW(index, representativeEdge.getValue());
index++;
@@ -220,6 +226,9 @@ public class IdAndValueArrayEdges<I extends WritableComparable,
@Override
public MutableEdge<I, E> next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
representativeEdge.setIndex(index++);
return representativeEdge;
}
http://git-wip-us.apache.org/repos/asf/giraph/blob/ea7753f0/giraph-core/src/test/java/org/apache/giraph/edge/IdAndNullArrayEdgesTest.java
----------------------------------------------------------------------
diff --git a/giraph-core/src/test/java/org/apache/giraph/edge/IdAndNullArrayEdgesTest.java b/giraph-core/src/test/java/org/apache/giraph/edge/IdAndNullArrayEdgesTest.java
new file mode 100644
index 0000000..0b4803a
--- /dev/null
+++ b/giraph-core/src/test/java/org/apache/giraph/edge/IdAndNullArrayEdgesTest.java
@@ -0,0 +1,242 @@
+/*
+ * 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.edge;
+
+import com.google.common.collect.Lists;
+import org.apache.giraph.conf.GiraphConfiguration;
+import org.apache.giraph.conf.GiraphConstants;
+import org.apache.giraph.conf.ImmutableClassesGiraphConfiguration;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.NullWritable;
+import org.apache.hadoop.io.Writable;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Set;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+
+public class IdAndNullArrayEdgesTest {
+ private static Edge<LongWritable, NullWritable> createEdge(long id) {
+ return EdgeFactory.create(new LongWritable(id));
+ }
+
+ private static void assertEdges(IdAndNullArrayEdges edges, long... expected) {
+ int index = 0;
+ for (Edge<LongWritable, NullWritable> edge :
+ (Iterable<Edge<LongWritable, NullWritable>>) edges) {
+ Assert.assertEquals(expected[index], edge.getTargetVertexId().get());
+ index++;
+ }
+ Assert.assertEquals(expected.length, index);
+ }
+
+ private IdAndNullArrayEdges getEdges() {
+ GiraphConfiguration gc = new GiraphConfiguration();
+ GiraphConstants.VERTEX_ID_CLASS.set(gc, LongWritable.class);
+ GiraphConstants.EDGE_VALUE_CLASS.set(gc, NullWritable.class);
+ ImmutableClassesGiraphConfiguration<LongWritable, Writable, NullWritable> conf =
+ new ImmutableClassesGiraphConfiguration<LongWritable, Writable, NullWritable>(gc);
+ IdAndNullArrayEdges ret = new IdAndNullArrayEdges();
+ ret.setConf(
+ new ImmutableClassesGiraphConfiguration<LongWritable, Writable, NullWritable>(conf));
+ return ret;
+ }
+
+ @Test
+ public void testEdges() {
+ IdAndNullArrayEdges edges = getEdges();
+
+ List<Edge<LongWritable, NullWritable>> initialEdges = Lists.newArrayList(
+ createEdge(1), createEdge(2), createEdge(4));
+
+ edges.initialize(initialEdges);
+ assertEdges(edges, 1, 2, 4);
+
+ edges.add(EdgeFactory.createReusable(new LongWritable(3)));
+ assertEdges(edges, 1, 2, 4, 3); // order matters, it's an array
+
+ edges.remove(new LongWritable(2));
+ assertEdges(edges, 1, 3, 4);
+ }
+
+ @Test
+ public void testInitialize() {
+ IdAndNullArrayEdges edges = getEdges();
+
+ List<Edge<LongWritable, NullWritable>> initialEdges = Lists.newArrayList(
+ createEdge(1), createEdge(2), createEdge(4));
+
+ edges.initialize(initialEdges);
+ assertEdges(edges, 1, 2, 4);
+
+ edges.add(EdgeFactory.createReusable(new LongWritable(3)));
+ assertEdges(edges, 1, 2, 4, 3);
+
+ edges.initialize();
+ assertEquals(0, edges.size());
+ }
+
+ @Test
+ public void testMutateEdges() {
+ IdAndNullArrayEdges edges = getEdges();
+
+ edges.initialize();
+
+ // Add 10 edges with id i, for i = 0..9
+ for (int i = 0; i < 10; ++i) {
+ edges.add(createEdge(i));
+ }
+
+ // Use the mutable iterator to remove edges with even id
+ Iterator<MutableEdge<LongWritable, NullWritable>> edgeIt =
+ edges.mutableIterator();
+ while (edgeIt.hasNext()) {
+ if (edgeIt.next().getTargetVertexId().get() % 2 == 0) {
+ edgeIt.remove();
+ }
+ }
+
+ // We should now have 5 edges
+ assertEquals(5, edges.size());
+ // The edge ids should be all odd
+ for (Edge<LongWritable, NullWritable> edge :
+ (Iterable<Edge<LongWritable, NullWritable>>) edges) {
+ assertEquals(1, edge.getTargetVertexId().get() % 2);
+ }
+ }
+
+ @Test
+ public void testSerialization() throws IOException {
+ IdAndNullArrayEdges edges = getEdges();
+
+ edges.initialize();
+
+ // Add 10 edges with id i, for i = 0..9
+ for (int i = 0; i < 10; ++i) {
+ edges.add(createEdge(i));
+ }
+
+ // Use the mutable iterator to remove edges with even id
+ Iterator<MutableEdge<LongWritable, NullWritable>> edgeIt =
+ edges.mutableIterator();
+ while (edgeIt.hasNext()) {
+ if (edgeIt.next().getTargetVertexId().get() % 2 == 0) {
+ edgeIt.remove();
+ }
+ }
+
+ // We should now have 5 edges
+ assertEdges(edges, 9, 1, 7, 3, 5); // id order matter because of the implementation
+
+ ByteArrayOutputStream arrayStream = new ByteArrayOutputStream();
+ DataOutputStream tempBuffer = new DataOutputStream(arrayStream);
+
+ edges.write(tempBuffer);
+ tempBuffer.close();
+
+ byte[] binary = arrayStream.toByteArray();
+
+ assertTrue("Serialized version should not be empty ", binary.length > 0);
+
+ edges = getEdges();
+ edges.readFields(new DataInputStream(new ByteArrayInputStream(binary)));
+
+ assertEquals(5, edges.size());
+
+ long[] ids = new long[]{9, 1, 7, 3, 5};
+ int index = 0;
+
+ for (Edge<LongWritable, NullWritable> edge :
+ (Iterable<Edge<LongWritable, NullWritable>>) edges) {
+ assertEquals(ids[index], edge.getTargetVertexId().get());
+ index++;
+ }
+ assertEquals(ids.length, index);
+ }
+
+ @Test
+ public void testParallelEdges() {
+ IdAndNullArrayEdges edges = getEdges();
+
+ List<Edge<LongWritable, NullWritable>> initialEdges = Lists.newArrayList(
+ createEdge(2), createEdge(2), createEdge(2));
+
+ edges.initialize(initialEdges);
+ assertEquals(3, edges.size());
+
+ edges.remove(new LongWritable(2));
+ assertEquals(0, edges.size());
+
+ edges.add(EdgeFactory.create(new LongWritable(2)));
+ assertEquals(1, edges.size());
+
+ assertEquals(1, edges.size());
+ }
+
+ @Test
+ public void testEdgeValues() {
+ IdAndNullArrayEdges edges = getEdges();
+ Set<Long> testValues = new HashSet<Long>();
+ testValues.add(0L);
+ testValues.add((long) Integer.MAX_VALUE);
+ testValues.add(Long.MAX_VALUE);
+
+ List<Edge<LongWritable, NullWritable>> initialEdges =
+ new ArrayList<Edge<LongWritable, NullWritable>>();
+ for(Long id : testValues) {
+ initialEdges.add(createEdge(id));
+ }
+
+ edges.initialize(initialEdges);
+
+ Iterator<MutableEdge<LongWritable, NullWritable>> edgeIt =
+ edges.mutableIterator();
+ while (edgeIt.hasNext()) {
+ long value = edgeIt.next().getTargetVertexId().get();
+ assertTrue("Unknown edge found " + value, testValues.remove(value));
+ }
+ }
+
+ @Test
+ public void testAddedSmallerValues() {
+ IdAndNullArrayEdges edges = getEdges();
+
+ List<Edge<LongWritable, NullWritable>> initialEdges = Lists.newArrayList(
+ createEdge(100));
+
+ edges.initialize(initialEdges);
+
+ for (int i=0; i<16; i++) {
+ edges.add(createEdge(i));
+ }
+
+ assertEquals(17, edges.size());
+ }
+}
http://git-wip-us.apache.org/repos/asf/giraph/blob/ea7753f0/giraph-core/src/test/java/org/apache/giraph/edge/IdAndValueArrayEdgesTest.java
----------------------------------------------------------------------
diff --git a/giraph-core/src/test/java/org/apache/giraph/edge/IdAndValueArrayEdgesTest.java b/giraph-core/src/test/java/org/apache/giraph/edge/IdAndValueArrayEdgesTest.java
new file mode 100644
index 0000000..70c1042
--- /dev/null
+++ b/giraph-core/src/test/java/org/apache/giraph/edge/IdAndValueArrayEdgesTest.java
@@ -0,0 +1,244 @@
+/*
+ * 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.edge;
+
+import com.google.common.collect.Lists;
+import org.apache.giraph.conf.GiraphConfiguration;
+import org.apache.giraph.conf.GiraphConstants;
+import org.apache.giraph.conf.ImmutableClassesGiraphConfiguration;
+import org.apache.hadoop.io.DoubleWritable;
+import org.apache.hadoop.io.LongWritable;
+import org.apache.hadoop.io.Writable;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Set;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+
+public class IdAndValueArrayEdgesTest {
+ private static Edge<LongWritable, DoubleWritable> createEdge(long id) {
+ return EdgeFactory.create(new LongWritable(id), new DoubleWritable((double) id));
+ }
+
+ private static void assertEdges(IdAndValueArrayEdges edges, long... expected) {
+ int index = 0;
+ for (Edge<LongWritable, DoubleWritable> edge :
+ (Iterable<Edge<LongWritable, DoubleWritable>>) edges) {
+ Assert.assertEquals(expected[index], edge.getTargetVertexId().get());
+ Assert.assertEquals((double) expected[index], edge.getValue().get(), 0.00001);
+ index++;
+ }
+ Assert.assertEquals(expected.length, index);
+ }
+
+ private IdAndValueArrayEdges getEdges() {
+ GiraphConfiguration gc = new GiraphConfiguration();
+ GiraphConstants.VERTEX_ID_CLASS.set(gc, LongWritable.class);
+ GiraphConstants.EDGE_VALUE_CLASS.set(gc, DoubleWritable.class);
+ ImmutableClassesGiraphConfiguration<LongWritable, Writable, DoubleWritable> conf =
+ new ImmutableClassesGiraphConfiguration<LongWritable, Writable, DoubleWritable>(gc);
+ IdAndValueArrayEdges ret = new IdAndValueArrayEdges();
+ ret.setConf(
+ new ImmutableClassesGiraphConfiguration<LongWritable, Writable, DoubleWritable>(conf));
+ return ret;
+ }
+
+ @Test
+ public void testEdges() {
+ IdAndValueArrayEdges edges = getEdges();
+
+ List<Edge<LongWritable, DoubleWritable>> initialEdges = Lists.newArrayList(
+ createEdge(1), createEdge(2), createEdge(4));
+
+ edges.initialize(initialEdges);
+ assertEdges(edges, 1, 2, 4);
+
+ edges.add(EdgeFactory.createReusable(new LongWritable(3), new DoubleWritable(3.0)));
+ assertEdges(edges, 1, 2, 4, 3); // order matters, it's an array
+
+ edges.remove(new LongWritable(2));
+ assertEdges(edges, 1, 3, 4);
+ }
+
+ @Test
+ public void testInitialize() {
+ IdAndValueArrayEdges edges = getEdges();
+
+ List<Edge<LongWritable, DoubleWritable>> initialEdges = Lists.newArrayList(
+ createEdge(1), createEdge(2), createEdge(4));
+
+ edges.initialize(initialEdges);
+ assertEdges(edges, 1, 2, 4);
+
+ edges.add(EdgeFactory.createReusable(new LongWritable(3), new DoubleWritable(3.0)));
+ assertEdges(edges, 1, 2, 4, 3); // order matters, it's an array
+
+ edges.initialize();
+ assertEquals(0, edges.size());
+ }
+
+ @Test
+ public void testMutateEdges() {
+ IdAndValueArrayEdges edges = getEdges();
+
+ edges.initialize();
+
+ // Add 10 edges with id i, for i = 0..9
+ for (int i = 0; i < 10; ++i) {
+ edges.add(createEdge(i));
+ }
+
+ // Use the mutable iterator to remove edges with even id
+ Iterator<MutableEdge<LongWritable, DoubleWritable>> edgeIt =
+ edges.mutableIterator();
+ while (edgeIt.hasNext()) {
+ if (edgeIt.next().getTargetVertexId().get() % 2 == 0) {
+ edgeIt.remove();
+ }
+ }
+
+ // We should now have 5 edges
+ assertEquals(5, edges.size());
+ // The edge ids should be all odd
+ for (Edge<LongWritable, DoubleWritable> edge :
+ (Iterable<Edge<LongWritable, DoubleWritable>>) edges) {
+ assertEquals(1, edge.getTargetVertexId().get() % 2);
+ }
+ }
+
+ @Test
+ public void testSerialization() throws IOException {
+ IdAndValueArrayEdges edges = getEdges();
+
+ edges.initialize();
+
+ // Add 10 edges with id i, for i = 0..9
+ for (int i = 0; i < 10; ++i) {
+ edges.add(createEdge(i));
+ }
+
+ // Use the mutable iterator to remove edges with even id
+ Iterator<MutableEdge<LongWritable, DoubleWritable>> edgeIt =
+ edges.mutableIterator();
+ while (edgeIt.hasNext()) {
+ if (edgeIt.next().getTargetVertexId().get() % 2 == 0) {
+ edgeIt.remove();
+ }
+ }
+
+ // We should now have 5 edges
+ assertEdges(edges, 9, 1, 7, 3, 5); // id order matter because of the implementation
+
+ ByteArrayOutputStream arrayStream = new ByteArrayOutputStream();
+ DataOutputStream tempBuffer = new DataOutputStream(arrayStream);
+
+ edges.write(tempBuffer);
+ tempBuffer.close();
+
+ byte[] binary = arrayStream.toByteArray();
+
+ assertTrue("Serialized version should not be empty ", binary.length > 0);
+
+ edges = getEdges();
+ edges.readFields(new DataInputStream(new ByteArrayInputStream(binary)));
+
+ assertEquals(5, edges.size());
+
+ long[] ids = new long[]{9, 1, 7, 3, 5};
+ int index = 0;
+
+ for (Edge<LongWritable, DoubleWritable> edge :
+ (Iterable<Edge<LongWritable, DoubleWritable>>) edges) {
+ assertEquals(ids[index], edge.getTargetVertexId().get());
+ assertEquals((double) ids[index], edge.getValue().get(), 0.00001);
+ index++;
+ }
+ assertEquals(ids.length, index);
+ }
+
+ @Test
+ public void testParallelEdges() {
+ IdAndValueArrayEdges edges = getEdges();
+
+ List<Edge<LongWritable, DoubleWritable>> initialEdges = Lists.newArrayList(
+ createEdge(2), createEdge(2), createEdge(2));
+
+ edges.initialize(initialEdges);
+ assertEquals(3, edges.size());
+
+ edges.remove(new LongWritable(2));
+ assertEquals(0, edges.size());
+
+ edges.add(EdgeFactory.create(new LongWritable(2), new DoubleWritable(2.0)));
+ assertEquals(1, edges.size());
+
+ assertEquals(1, edges.size());
+ }
+
+ @Test
+ public void testEdgeValues() {
+ IdAndValueArrayEdges edges = getEdges();
+ Set<Long> testValues = new HashSet<Long>();
+ testValues.add(0L);
+ testValues.add((long) Integer.MAX_VALUE);
+ testValues.add(Long.MAX_VALUE);
+
+ List<Edge<LongWritable, DoubleWritable>> initialEdges =
+ new ArrayList<Edge<LongWritable, DoubleWritable>>();
+ for(Long id : testValues) {
+ initialEdges.add(createEdge(id));
+ }
+
+ edges.initialize(initialEdges);
+
+ Iterator<MutableEdge<LongWritable, DoubleWritable>> edgeIt =
+ edges.mutableIterator();
+ while (edgeIt.hasNext()) {
+ long value = edgeIt.next().getTargetVertexId().get();
+ assertTrue("Unknown edge found " + value, testValues.remove(value));
+ }
+ }
+
+ @Test
+ public void testAddedSmallerValues() {
+ IdAndValueArrayEdges edges = getEdges();
+
+ List<Edge<LongWritable, DoubleWritable>> initialEdges = Lists.newArrayList(
+ createEdge(100));
+
+ edges.initialize(initialEdges);
+
+ for (int i=0; i<16; i++) {
+ edges.add(createEdge(i));
+ }
+
+ assertEquals(17, edges.size());
+ }
+}