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  
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   * Tests for {@link SccComputation}
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     * Connects the outgoingVertices to the given vertex id
56     * with null-valued edges.
57     * 
58     * @param graph
59     * @param id
60     * @param outgoingVertices
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 (LongWritable v : g.getVertices().keySet()) {
114       Vertex<LongWritable, SccVertexValue, NullWritable> vertex = g
115           .getVertex(v);
116       long sccId = vertex.getValue().get();
117       List<Long> verticesIds = scc.get(sccId);
118       if (verticesIds == null) {// New SCC
119         List<Long> newScc = new ArrayList<Long>();
120         newScc.add(vertex.getId().get());
121         scc.put(sccId, newScc);
122       } else {
123         verticesIds.add(vertex.getId().get());
124       }
125     }
126     return scc;
127   }
128 }