This project has retired. For details please refer to its
Attic page.
SccComputationTestInMemory xref
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.giraph.examples.scc;
20
21 import java.util.AbstractMap.SimpleEntry;
22 import java.util.ArrayList;
23 import java.util.Arrays;
24 import java.util.Collections;
25 import java.util.HashMap;
26 import java.util.List;
27 import java.util.Map;
28 import java.util.Map.Entry;
29
30 import org.apache.giraph.conf.GiraphConfiguration;
31 import org.apache.giraph.edge.ByteArrayEdges;
32 import org.apache.giraph.graph.Vertex;
33 import org.apache.giraph.utils.InternalVertexRunner;
34 import org.apache.giraph.utils.TestGraph;
35 import org.apache.hadoop.io.LongWritable;
36 import org.apache.hadoop.io.NullWritable;
37 import org.junit.Assert;
38 import org.junit.Test;
39
40
41
42
43 public class SccComputationTestInMemory {
44 @SuppressWarnings("unchecked")
45 public static Entry<LongWritable, NullWritable>[] makeEdges(long... args) {
46 Entry<LongWritable, NullWritable> result[] = new Entry[args.length];
47 for (int i = 0; i < args.length; i++) {
48 result[i] = new SimpleEntry<LongWritable, NullWritable>(new LongWritable(
49 args[i]), NullWritable.get());
50 }
51 return result;
52 }
53
54
55
56
57
58
59
60
61
62 public static void addVertex(
63 TestGraph<LongWritable, SccVertexValue, NullWritable> graph, long id,
64 long... outgoingVertices) {
65 graph.addVertex(new LongWritable(id), new SccVertexValue(id),
66 makeEdges(outgoingVertices));
67 }
68
69 @Test
70 public void testToyData() throws Exception {
71 GiraphConfiguration conf = new GiraphConfiguration();
72 conf.setComputationClass(SccComputation.class);
73 conf.setMasterComputeClass(SccPhaseMasterCompute.class);
74 conf.setOutEdgesClass(ByteArrayEdges.class);
75
76
77 TestGraph<LongWritable, SccVertexValue, NullWritable> graph = new TestGraph<LongWritable, SccVertexValue, NullWritable>(
78 conf);
79
80 addVertex(graph, 0, 1, 2, 4);
81 addVertex(graph, 1, 3, 20);
82 addVertex(graph, 2, 3);
83 addVertex(graph, 3, 0);
84 addVertex(graph, 20, 21);
85 addVertex(graph, 21, 22);
86 addVertex(graph, 22, 23);
87 addVertex(graph, 23, 24);
88 addVertex(graph, 24, 25);
89 addVertex(graph, 25, 20);
90 addVertex(graph, 4, 5);
91 addVertex(graph, 5, 6);
92
93 TestGraph<LongWritable, SccVertexValue, NullWritable> results = InternalVertexRunner.runWithInMemoryOutput(conf, graph);
94
95 Map<Long, List<Long>> scc = parse(results);
96
97 List<Long> components = scc.get(3l);
98 Collections.sort(components);
99 Assert.assertEquals(Arrays.asList(0l, 1l, 2l, 3l), components);
100
101 Assert.assertEquals(Arrays.asList(4l), scc.get(4l));
102 Assert.assertEquals(Arrays.asList(5l), scc.get(5l));
103 Assert.assertEquals(Arrays.asList(6l), scc.get(6l));
104
105 components = scc.get(25l);
106 Collections.sort(components);
107 Assert.assertEquals(Arrays.asList(20l, 21l, 22l, 23l, 24l, 25l), components);
108 }
109
110 private Map<Long, List<Long>> parse(
111 TestGraph<LongWritable, SccVertexValue, NullWritable> g) {
112 Map<Long, List<Long>> scc = new HashMap<Long, List<Long>>();
113 for (Vertex<LongWritable, SccVertexValue, NullWritable> vertex : g) {
114 long sccId = vertex.getValue().get();
115 List<Long> verticesIds = scc.get(sccId);
116 if (verticesIds == null) {
117 List<Long> newScc = new ArrayList<Long>();
118 newScc.add(vertex.getId().get());
119 scc.put(sccId, newScc);
120 } else {
121 verticesIds.add(vertex.getId().get());
122 }
123 }
124 return scc;
125 }
126 }