View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  package org.apache.giraph.edge;
19  
20  import static org.junit.Assert.assertEquals;
21  import static org.junit.Assert.assertTrue;
22  
23  import java.io.ByteArrayOutputStream;
24  import java.io.DataOutputStream;
25  import java.io.IOException;
26  import java.util.ArrayList;
27  import java.util.HashSet;
28  import java.util.Iterator;
29  import java.util.List;
30  import java.util.Set;
31  
32  import org.apache.giraph.conf.GiraphConfiguration;
33  import org.apache.giraph.conf.ImmutableClassesGiraphConfiguration;
34  import org.apache.giraph.utils.UnsafeByteArrayInputStream;
35  import org.apache.hadoop.io.LongWritable;
36  import org.apache.hadoop.io.NullWritable;
37  import org.apache.hadoop.io.Writable;
38  import org.junit.Assert;
39  import org.junit.Test;
40  
41  import com.google.common.collect.Lists;
42  
43  
44  public class LongDiffNullArrayEdgesTest {
45    private static Edge<LongWritable, NullWritable> createEdge(long id) {
46      return EdgeFactory.create(new LongWritable(id));
47    }
48  
49    private static void assertEdges(LongDiffNullArrayEdges edges, long... expected) {
50      int index = 0;
51      for (Edge<LongWritable, NullWritable> edge : edges) {
52        Assert.assertEquals(expected[index], edge.getTargetVertexId().get());
53        index++;
54      }
55      Assert.assertEquals(expected.length, index);
56    }
57  
58    @Test
59    public void testEdges() {
60      LongDiffNullArrayEdges edges = getEdges();
61  
62      List<Edge<LongWritable, NullWritable>> initialEdges = Lists.newArrayList(
63          createEdge(1), createEdge(2), createEdge(4));
64  
65      edges.initialize(initialEdges);
66      assertEdges(edges, 1, 2, 4);
67  
68      edges.add(EdgeFactory.createReusable(new LongWritable(3)));
69      assertEdges(edges, 1, 2, 3, 4);
70  
71      edges.remove(new LongWritable(2));
72      assertEdges(edges, 1, 3, 4);
73    }
74  
75    @Test
76    public void testPositiveAndNegativeEdges() {
77      LongDiffNullArrayEdges edges = getEdges();
78  
79      List<Edge<LongWritable, NullWritable>> initialEdges = Lists.newArrayList(
80          createEdge(1), createEdge(-2), createEdge(3), createEdge(-4));
81  
82      edges.initialize(initialEdges);
83      assertEdges(edges, -4, -2, 1, 3);
84  
85      edges.add(EdgeFactory.createReusable(new LongWritable(5)));
86      assertEdges(edges, -4, -2, 1, 3, 5);
87  
88      edges.remove(new LongWritable(-2));
89      assertEdges(edges, -4, 1, 3, 5);
90    }
91  
92    @Test
93    public void testMutateEdges() {
94      LongDiffNullArrayEdges edges = getEdges();
95  
96      edges.initialize();
97  
98      // Add 10 edges with id i, for i = 0..9
99      for (int i = 0; i < 10; ++i) {
100       edges.add(createEdge(i));
101     }
102 
103     // Use the mutable iterator to remove edges with even id
104     Iterator<MutableEdge<LongWritable, NullWritable>> edgeIt =
105         edges.mutableIterator();
106     while (edgeIt.hasNext()) {
107       if (edgeIt.next().getTargetVertexId().get() % 2 == 0) {
108         edgeIt.remove();
109       }
110     }
111 
112     // We should now have 5 edges
113     assertEquals(5, edges.size());
114     // The edge ids should be all odd
115     for (Edge<LongWritable, NullWritable> edge : edges) {
116       assertEquals(1, edge.getTargetVertexId().get() % 2);
117     }
118   }
119 
120   @Test
121   public void testSerialization() throws IOException {
122     LongDiffNullArrayEdges edges = getEdges();
123 
124     edges.initialize();
125 
126     // Add 10 edges with id i, for i = 0..9
127     for (int i = 0; i < 10; ++i) {
128       edges.add(createEdge(i));
129     }
130 
131     edges.trim();
132 
133     // Use the mutable iterator to remove edges with even id
134     Iterator<MutableEdge<LongWritable, NullWritable>> edgeIt =
135         edges.mutableIterator();
136     while (edgeIt.hasNext()) {
137       if (edgeIt.next().getTargetVertexId().get() % 2 == 0) {
138         edgeIt.remove();
139       }
140     }
141 
142     // We should now have 5 edges
143     assertEdges(edges, 1, 3, 5, 7, 9);
144 
145     ByteArrayOutputStream arrayStream = new ByteArrayOutputStream();
146     DataOutputStream tempBuffer = new DataOutputStream(arrayStream);
147 
148     edges.write(tempBuffer);
149 
150     byte[] binary = arrayStream.toByteArray();
151 
152     assertTrue("Serialized version should not be empty ", binary.length > 0);
153 
154     edges = getEdges();
155     edges.readFields(new UnsafeByteArrayInputStream(binary));
156 
157     assertEquals(5, edges.size());
158 
159     for (Edge<LongWritable, NullWritable> edge : edges) {
160       assertEquals(1, edge.getTargetVertexId().get() % 2);
161     }
162   }
163 
164   @Test
165   public void testParallelEdges() {
166     LongDiffNullArrayEdges edges = getEdges();
167 
168     List<Edge<LongWritable, NullWritable>> initialEdges = Lists.newArrayList(
169         createEdge(2), createEdge(2), createEdge(2));
170 
171     edges.initialize(initialEdges);
172     assertEquals(3, edges.size());
173 
174     edges.remove(new LongWritable(2));
175     assertEquals(0, edges.size());
176 
177     edges.add(EdgeFactory.create(new LongWritable(2)));
178     assertEquals(1, edges.size());
179 
180     edges.trim();
181     assertEquals(1, edges.size());
182   }
183 
184   @Test
185   public void testEdgeValues() {
186     LongDiffNullArrayEdges edges = getEdges();
187     Set<Long> testValues = new HashSet<Long>();
188     testValues.add(0L);
189     testValues.add((long) Integer.MAX_VALUE);
190     testValues.add(Long.MAX_VALUE);
191 
192     // shouldn't be working with negative IDs
193     // testValues.add((long) Integer.MIN_VALUE);
194     // testValues.add(Long.MIN_VALUE);
195 
196     List<Edge<LongWritable, NullWritable>> initialEdges =
197         new ArrayList<Edge<LongWritable, NullWritable>>();
198     for(Long id : testValues) {
199       initialEdges.add(createEdge(id));
200     }
201 
202     edges.initialize(initialEdges);
203     edges.trim();
204 
205     Iterator<MutableEdge<LongWritable, NullWritable>> edgeIt =
206         edges.mutableIterator();
207     while (edgeIt.hasNext()) {
208       long value = edgeIt.next().getTargetVertexId().get();
209       assertTrue("Unknown edge found " + value, testValues.remove(value));
210     }
211   }
212 
213   private LongDiffNullArrayEdges getEdges() {
214     GiraphConfiguration gc = new GiraphConfiguration();
215     ImmutableClassesGiraphConfiguration<LongWritable, Writable, NullWritable> conf =
216         new ImmutableClassesGiraphConfiguration<LongWritable, Writable, NullWritable>(gc);
217     LongDiffNullArrayEdges ret = new LongDiffNullArrayEdges();
218     ret.setConf(new ImmutableClassesGiraphConfiguration<LongWritable, Writable, NullWritable>(conf));
219     return ret;
220   }
221 
222   @Test
223   public void testAddedSmalerValues() {
224     LongDiffNullArrayEdges edges = getEdges();
225 
226     List<Edge<LongWritable, NullWritable>> initialEdges = Lists.newArrayList(
227         createEdge(100));
228 
229     edges.initialize(initialEdges);
230 
231     edges.trim();
232 
233     for (int i=0; i<16; i++) {
234       edges.add(createEdge(i));
235     }
236 
237     edges.trim();
238 
239     assertEquals(17, edges.size());
240   }
241 
242   @Test(expected=IllegalStateException.class)
243   public void testFailSafeOnPotentialOverflow() {
244     LongDiffNullArrayEdges edges = getEdges();
245 
246     List<Edge<LongWritable, NullWritable>> initialEdges = Lists.newArrayList(
247         createEdge(5223372036854775807L), createEdge(-4223372036854775807L));
248     edges.initialize(initialEdges);
249   }
250 
251   @Test
252   public void testAvoidOverflowWithZero() {
253     LongDiffNullArrayEdges edges = getEdges();
254 
255     List<Edge<LongWritable, NullWritable>> initialEdges = Lists.newArrayList(
256         createEdge(5223372036854775807L), createEdge(-4223372036854775807L), createEdge(0));
257     edges.initialize(initialEdges);
258     assertEdges(edges, -4223372036854775807L, 0, 5223372036854775807L);
259   }
260 }