1/*2 * Licensed to the Apache Software Foundation (ASF) under one3 * or more contributor license agreements. See the NOTICE file4 * distributed with this work for additional information5 * regarding copyright ownership. The ASF licenses this file6 * to you under the Apache License, Version 2.0 (the7 * "License"); you may not use this file except in compliance8 * with the License. You may obtain a copy of the License at9 *10 * http://www.apache.org/licenses/LICENSE-2.011 *12 * Unless required by applicable law or agreed to in writing, software13 * 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 and16 * limitations under the License.17 */1819package org.apache.giraph.io;
2021importstatic org.junit.Assert.assertEquals;
22importstatic org.junit.Assert.assertFalse;
23importstatic org.junit.Assert.assertTrue;
2425import java.io.IOException;
26import java.util.Map;
2728import org.apache.giraph.BspCase;
29import org.apache.giraph.conf.GiraphConfiguration;
30import org.apache.giraph.edge.ByteArrayEdges;
31import org.apache.giraph.edge.Edge;
32import org.apache.giraph.factories.VertexValueFactory;
33import org.apache.giraph.graph.Vertex;
34import org.apache.giraph.graph.VertexValueCombiner;
35import org.apache.giraph.io.formats.IdWithValueTextOutputFormat;
36import org.apache.giraph.io.formats.IntIntNullTextVertexInputFormat;
37import org.apache.giraph.io.formats.IntIntTextVertexValueInputFormat;
38import org.apache.giraph.io.formats.IntNullReverseTextEdgeInputFormat;
39import org.apache.giraph.io.formats.IntNullTextEdgeInputFormat;
40import org.apache.giraph.utils.ComputationCountEdges;
41import org.apache.giraph.utils.IntIntNullNoOpComputation;
42import org.apache.giraph.utils.InternalVertexRunner;
43import org.apache.hadoop.io.IntWritable;
44import org.apache.hadoop.io.NullWritable;
45import org.junit.Test;
4647import com.google.common.collect.Maps;
4849/**50 * A test case to ensure that loading a graph from vertices and edges works as51 * expected.52 */53publicclassTestVertexEdgeInputextendsBspCase {
54publicTestVertexEdgeInput() {
55super(TestVertexEdgeInput.class.getName());
56 }
5758// It should be able to build a graph starting from the edges only.59// Vertices should be implicitly created with default values.60 @Test
61publicvoid testEdgesOnly() throws Exception {
62 String[] edges = new String[] {
63"1 2",
64"2 3",
65"2 4",
66"4 1"67 };
6869 GiraphConfiguration conf = new GiraphConfiguration();
70 conf.setComputationClass(ComputationCountEdges.class);
71 conf.setOutEdgesClass(ByteArrayEdges.class);
72 conf.setEdgeInputFormatClass(IntNullTextEdgeInputFormat.class);
73 conf.setVertexOutputFormatClass(IdWithValueTextOutputFormat.class);
74 Iterable<String> results = InternalVertexRunner.run(conf, null, edges);
7576 Map<Integer, Integer> values = parseResults(results);
7778// Check that all vertices with outgoing edges have been created79 assertEquals(3, values.size());
80// Check the number of edges for each vertex81 assertEquals(1, (int) values.get(1));
82 assertEquals(2, (int) values.get(2));
83 assertEquals(1, (int) values.get(4));
84 }
8586// It should be able to build a graph starting from the edges only.87// Using ReverseEdgeDuplicator it should also create the reverse edges.88// Vertices should be implicitly created with default values.89 @Test
90publicvoid testEdgesOnlyWithReverse() throws Exception {
91 String[] edges = new String[] {
92"1 2",
93"2 3",
94"2 4",
95"4 1"96 };
9798 GiraphConfiguration conf = new GiraphConfiguration();
99 conf.setComputationClass(ComputationCountEdges.class);
100 conf.setOutEdgesClass(ByteArrayEdges.class);
101 conf.setEdgeInputFormatClass(IntNullReverseTextEdgeInputFormat.class);
102 conf.setVertexOutputFormatClass(IdWithValueTextOutputFormat.class);
103 Iterable<String> results = InternalVertexRunner.run(conf, null, edges);
104105 Map<Integer, Integer> values = parseResults(results);
106107// Check that all vertices with outgoing edges have been created108 assertEquals(4, values.size());
109// Check the number of edges for each vertex110 assertEquals(2, (int) values.get(1));
111 assertEquals(3, (int) values.get(2));
112 assertEquals(1, (int) values.get(3));
113 assertEquals(2, (int) values.get(4));
114 }
115116/**117 * Simple vertex value combiner that sums up the vertex values.118 */119publicstaticclassIntSumVertexValueCombinerimplements VertexValueCombiner<IntWritable> {
120 @Override
121publicvoid combine(IntWritable originalVertexValue, IntWritable vertexValue) {
122 originalVertexValue.set(originalVertexValue.get() + vertexValue.get());
123 }
124 }
125126// It should be able to build a graph by specifying vertex value data127// and combining the duplicates (summation). Edges should be added as well.128 @Test
129publicvoid testVertexValueCombiner() throws Exception {
130 String[] vertices = new String[] {
131"1 75 2",
132"2 34 3",
133"3 13",
134"4 32",
135"1 11",
136"2 23 1",
137"2 3"138 };
139140 GiraphConfiguration conf = new GiraphConfiguration();
141 conf.setComputationClass(IntIntNullNoOpComputation.class);
142 conf.setOutEdgesClass(ByteArrayEdges.class);
143 conf.setVertexInputFormatClass(IntIntNullTextVertexInputFormat.class);
144 conf.setVertexValueCombinerClass(IntSumVertexValueCombiner.class);
145 conf.setVertexOutputFormatClass(IdWithValueTextOutputFormat.class);
146147// Run a job with a vertex that does nothing148 Iterable<String> results = InternalVertexRunner.run(conf, vertices);
149150 Map<Integer, Integer> values = parseResults(results);
151152// Check that all vertices were created153 assertEquals(4, values.size());
154// Check that the vertices have been created with correct values155 assertEquals(86, (int) values.get(1));
156 assertEquals(60, (int) values.get(2));
157 assertEquals(13, (int) values.get(3));
158 assertEquals(32, (int) values.get(4));
159160// Run a job with a vertex that counts outgoing edges161 conf.setComputationClass(ComputationCountEdges.class);
162 results = InternalVertexRunner.run(conf, vertices);
163164// Check that the edges were added as well165 values = parseResults(results);
166 assertEquals(1, (int) values.get(1));
167 assertEquals(2, (int) values.get(2));
168 assertEquals(0, (int) values.get(3));
169 assertEquals(0, (int) values.get(4));
170 }
171172// It should be able to build a graph by specifying vertex value data173// and edges as separate input formats.174 @Test
175publicvoid testMixedVertexValueEdgeFormat() throws Exception {
176 String[] vertices = new String[] {
177"1 75",
178"2 34",
179"3 13",
180"4 32"181 };
182 String[] edges = new String[] {
183"1 2",
184"2 3",
185"2 4",
186"4 1",
187"5 3"188 };
189190 GiraphConfiguration conf = new GiraphConfiguration();
191 conf.setComputationClass(IntIntNullNoOpComputation.class);
192 conf.setOutEdgesClass(ByteArrayEdges.class);
193 conf.setVertexInputFormatClass(IntIntTextVertexValueInputFormat.class);
194 conf.setEdgeInputFormatClass(IntNullTextEdgeInputFormat.class);
195 conf.setVertexOutputFormatClass(IdWithValueTextOutputFormat.class);
196197// Run a job with a vertex that does nothing198 Iterable<String> results = InternalVertexRunner.run(conf, vertices, edges);
199200 Map<Integer, Integer> values = parseResults(results);
201202// Check that all vertices with either initial values or outgoing edges203// have been created204 assertEquals(5, values.size());
205// Check that the vertices have been created with correct values206 assertEquals(75, (int) values.get(1));
207 assertEquals(34, (int) values.get(2));
208 assertEquals(13, (int) values.get(3));
209 assertEquals(32, (int) values.get(4));
210// A vertex with edges but no initial value should have the default value211 assertEquals(0, (int) values.get(5));
212213// Run a job with a custom VertexValueFactory214 conf.setVertexValueFactoryClass(TestVertexValueFactory.class);
215 results = InternalVertexRunner.run(conf, vertices, edges);
216 values = parseResults(results);
217// A vertex with edges but no initial value should have been constructed218// by the custom factory219 assertEquals(3, (int) values.get(5));
220221 conf = new GiraphConfiguration();
222 conf.setComputationClass(ComputationCountEdges.class);
223 conf.setOutEdgesClass(ByteArrayEdges.class);
224 conf.setVertexInputFormatClass(IntIntTextVertexValueInputFormat.class);
225 conf.setEdgeInputFormatClass(IntNullTextEdgeInputFormat.class);
226 conf.setVertexOutputFormatClass(IdWithValueTextOutputFormat.class);
227228// Run a job with a vertex that counts outgoing edges229 results = InternalVertexRunner.run(conf, vertices, edges);
230231 values = parseResults(results);
232233// Check the number of edges for each vertex234 assertEquals(1, (int) values.get(1));
235 assertEquals(2, (int) values.get(2));
236 assertEquals(0, (int) values.get(3));
237 assertEquals(1, (int) values.get(4));
238 assertEquals(1, (int) values.get(5));
239 }
240241// It should be able to build a graph by specifying vertices and edges242// as separate input formats.243 @Test
244publicvoid testMixedVertexEdgeFormat() throws Exception {
245 String[] vertices = new String[] {
246"1 75 2 3",
247"2 34 1 5",
248"3 13",
249"4 32"250 };
251 String[] edges = new String[] {
252"1 2",
253"2 3",
254"2 4",
255"4 1",
256"5 3"257 };
258259 GiraphConfiguration conf = new GiraphConfiguration();
260 conf.setComputationClass(IntIntNullNoOpComputation.class);
261 conf.setOutEdgesClass(ByteArrayEdges.class);
262 conf.setVertexInputFormatClass(IntIntNullTextVertexInputFormat.class);
263 conf.setEdgeInputFormatClass(IntNullTextEdgeInputFormat.class);
264 conf.setVertexOutputFormatClass(IdWithValueTextOutputFormat.class);
265266// Run a job with a vertex that does nothing267 Iterable<String> results = InternalVertexRunner.run(conf, vertices, edges);
268269 Map<Integer, Integer> values = parseResults(results);
270271// Check that all vertices with either initial values or outgoing edges272// have been created273 assertEquals(5, values.size());
274// Check that the vertices have been created with correct values275 assertEquals(75, (int) values.get(1));
276 assertEquals(34, (int) values.get(2));
277 assertEquals(13, (int) values.get(3));
278 assertEquals(32, (int) values.get(4));
279// A vertex with edges but no initial value should have the default value280 assertEquals(0, (int) values.get(5));
281282// Run a job with a custom VertexValueFactory283 conf.setVertexValueFactoryClass(TestVertexValueFactory.class);
284 results = InternalVertexRunner.run(conf, vertices, edges);
285 values = parseResults(results);
286// A vertex with edges but no initial value should have been constructed287// by the custom factory288 assertEquals(3, (int) values.get(5));
289290 conf = new GiraphConfiguration();
291 conf.setComputationClass(ComputationCountEdges.class);
292 conf.setOutEdgesClass(ByteArrayEdges.class);
293 conf.setVertexInputFormatClass(IntIntNullTextVertexInputFormat.class);
294 conf.setEdgeInputFormatClass(IntNullTextEdgeInputFormat.class);
295 conf.setVertexOutputFormatClass(IdWithValueTextOutputFormat.class);
296297// Run a job with a vertex that counts outgoing edges298 results = InternalVertexRunner.run(conf, vertices, edges);
299300 values = parseResults(results);
301302// Check the number of edges for each vertex303 assertEquals(3, (int) values.get(1));
304 assertEquals(4, (int) values.get(2));
305 assertEquals(0, (int) values.get(3));
306 assertEquals(1, (int) values.get(4));
307 assertEquals(1, (int) values.get(5));
308 }
309310// It should use the specified input OutEdges class.311 @Test
312publicvoid testDifferentInputEdgesClass() throws Exception {
313 String[] edges = new String[] {
314"1 2",
315"2 3",
316"2 4",
317"4 1"318 };
319320 GiraphConfiguration conf = new GiraphConfiguration();
321 conf.setComputationClass(TestComputationCheckEdgesType.class);
322 conf.setOutEdgesClass(ByteArrayEdges.class);
323 conf.setInputOutEdgesClass(TestOutEdgesFilterEven.class);
324 conf.setEdgeInputFormatClass(IntNullTextEdgeInputFormat.class);
325 conf.setVertexOutputFormatClass(IdWithValueTextOutputFormat.class);
326 Iterable<String> results = InternalVertexRunner.run(conf, null, edges);
327328 Map<Integer, Integer> values = parseResults(results);
329330// Check that all vertices with outgoing edges in the input have been331// created332 assertEquals(3, values.size());
333// Check the number of edges for each vertex (edges with odd target id334// should have been removed)335 assertEquals(1, (int) values.get(1));
336 assertEquals(1, (int) values.get(2));
337 assertEquals(0, (int) values.get(4));
338 }
339340publicstaticclassTestComputationCheckEdgesTypeextends341ComputationCountEdges {
342 @Override
343publicvoid compute(Vertex<IntWritable, IntWritable, NullWritable> vertex,
344 Iterable<NullWritable> messages) throws IOException {
345 assertFalse(vertex.getEdges() instanceof TestOutEdgesFilterEven);
346 assertTrue(vertex.getEdges() instanceof ByteArrayEdges);
347super.compute(vertex, messages);
348 }
349 }
350351publicstaticclassTestVertexValueFactory352implements VertexValueFactory<IntWritable> {
353 @Override
354public IntWritable newInstance() {
355returnnew IntWritable(3);
356 }
357 }
358359publicstaticclassTestOutEdgesFilterEven360extends ByteArrayEdges<IntWritable, NullWritable> {
361 @Override
362publicvoid add(Edge<IntWritable, NullWritable> edge) {
363if (edge.getTargetVertexId().get() % 2 == 0) {
364super.add(edge);
365 }
366 }
367 }
368369privatestatic Map<Integer, Integer> parseResults(Iterable<String> results) {
370 Map<Integer, Integer> values = Maps.newHashMap();
371for (String line : results) {
372 String[] tokens = line.split("\\s+");
373int id = Integer.valueOf(tokens[0]);
374int value = Integer.valueOf(tokens[1]);
375 values.put(id, value);
376 }
377return values;
378 }
379 }