This project has retired. For details please refer to its Attic page.
SimpleShortestPathsComputationTest xref
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;
20  
21  import org.apache.giraph.conf.GiraphConfiguration;
22  import org.apache.giraph.edge.ByteArrayEdges;
23  import org.apache.giraph.edge.EdgeFactory;
24  import org.apache.giraph.graph.DefaultVertex;
25  import org.apache.giraph.graph.Vertex;
26  import org.apache.giraph.io.formats.JsonLongDoubleFloatDoubleVertexInputFormat;
27  import org.apache.giraph.io.formats.JsonLongDoubleFloatDoubleVertexOutputFormat;
28  import org.apache.giraph.utils.InternalVertexRunner;
29  import org.apache.giraph.utils.MockUtils;
30  import org.apache.hadoop.io.DoubleWritable;
31  import org.apache.hadoop.io.FloatWritable;
32  import org.apache.hadoop.io.LongWritable;
33  import org.json.JSONArray;
34  import org.json.JSONException;
35  import org.junit.Test;
36  import org.mockito.Mockito;
37  
38  import com.google.common.collect.Iterables;
39  import com.google.common.collect.Lists;
40  import com.google.common.collect.Maps;
41  
42  import java.util.Map;
43  import java.util.regex.Pattern;
44  
45  import static org.apache.giraph.examples.SimpleShortestPathsComputation.SOURCE_ID;
46  import static org.junit.Assert.assertEquals;
47  import static org.junit.Assert.assertNotNull;
48  import static org.junit.Assert.assertTrue;
49  
50  /**
51   * Contains a simple unit test for {@link SimpleShortestPathsComputation}
52   */
53  public class SimpleShortestPathsComputationTest {
54  
55    /**
56     * Test the behavior when a shorter path to a vertex has been found
57     */
58    @Test
59    public void testOnShorterPathFound() throws Exception {
60      Vertex<LongWritable, DoubleWritable, FloatWritable> vertex =
61          new DefaultVertex<LongWritable, DoubleWritable, FloatWritable>();
62      SimpleShortestPathsComputation computation =
63          new SimpleShortestPathsComputation();
64      MockUtils.MockedEnvironment<LongWritable, DoubleWritable, FloatWritable,
65          DoubleWritable> env = MockUtils.prepareVertexAndComputation(vertex,
66          new LongWritable(7L), new DoubleWritable(Double.MAX_VALUE), false,
67          computation, 1L);
68      Mockito.when(SOURCE_ID.get(env.getConfiguration())).thenReturn(2L);
69  
70      vertex.addEdge(EdgeFactory.create(
71          new LongWritable(10L), new FloatWritable(2.5f)));
72      vertex.addEdge(EdgeFactory.create(
73          new LongWritable(20L), new FloatWritable(0.5f)));
74  
75      computation.compute(vertex, Lists.newArrayList(new DoubleWritable(2),
76          new DoubleWritable(1.5)));
77  
78      assertTrue(vertex.isHalted());
79      assertEquals(1.5d, vertex.getValue().get(), 0d);
80  
81      env.verifyMessageSent(new LongWritable(10L), new DoubleWritable(4));
82      env.verifyMessageSent(new LongWritable(20L), new DoubleWritable(2));
83    }
84  
85    /**
86     * Test the behavior when a new, but not shorter path to a vertex has been
87     * found.
88     */
89    @Test
90    public void testOnNoShorterPathFound() throws Exception {
91      Vertex<LongWritable, DoubleWritable, FloatWritable> vertex =
92          new DefaultVertex<LongWritable, DoubleWritable, FloatWritable>();
93      SimpleShortestPathsComputation computation =
94          new SimpleShortestPathsComputation();
95      MockUtils.MockedEnvironment<LongWritable, DoubleWritable, FloatWritable,
96          DoubleWritable> env = MockUtils.prepareVertexAndComputation(vertex,
97          new LongWritable(7L), new DoubleWritable(0.5), false, computation, 1L);
98      Mockito.when(SOURCE_ID.get(env.getConfiguration())).thenReturn(2L);
99  
100     vertex.addEdge(EdgeFactory.create(new LongWritable(10L),
101         new FloatWritable(2.5f)));
102     vertex.addEdge(EdgeFactory.create(
103         new LongWritable(20L), new FloatWritable(0.5f)));
104 
105     computation.compute(vertex, Lists.newArrayList(new DoubleWritable(2),
106         new DoubleWritable(1.5)));
107 
108     assertTrue(vertex.isHalted());
109     assertEquals(0.5d, vertex.getValue().get(), 0d);
110 
111     env.verifyNoMessageSent();
112   }
113 
114   /**
115    * A local integration test on toy data
116    */
117   @Test
118   public void testToyDataJson() throws Exception {
119 
120     // a small four vertex graph
121     String[] graph = new String[] {
122         "[1,0,[[2,1],[3,3]]]",
123         "[2,0,[[3,1],[4,10]]]",
124         "[3,0,[[4,2]]]",
125         "[4,0,[]]"
126     };
127 
128     GiraphConfiguration conf = new GiraphConfiguration();
129     // start from vertex 1
130     SOURCE_ID.set(conf, 1);
131     conf.setComputationClass(SimpleShortestPathsComputation.class);
132     conf.setOutEdgesClass(ByteArrayEdges.class);
133     conf.setVertexInputFormatClass(
134         JsonLongDoubleFloatDoubleVertexInputFormat.class);
135     conf.setVertexOutputFormatClass(
136         JsonLongDoubleFloatDoubleVertexOutputFormat.class);
137 
138     // run internally
139     Iterable<String> results = InternalVertexRunner.run(conf, graph);
140 
141     Map<Long, Double> distances = parseDistancesJson(results);
142 
143     // verify results
144     assertNotNull(distances);
145     assertEquals(4, distances.size());
146     assertEquals(0.0, distances.get(1L), 0d);
147     assertEquals(1.0, distances.get(2L), 0d);
148     assertEquals(2.0, distances.get(3L), 0d);
149     assertEquals(4.0, distances.get(4L), 0d);
150   }
151 
152   private Map<Long, Double> parseDistancesJson(Iterable<String> results) {
153     Map<Long, Double> distances =
154         Maps.newHashMapWithExpectedSize(Iterables.size(results));
155     for (String line : results) {
156       try {
157         JSONArray jsonVertex = new JSONArray(line);
158         distances.put(jsonVertex.getLong(0), jsonVertex.getDouble(1));
159       } catch (JSONException e) {
160         throw new IllegalArgumentException(
161             "Couldn't get vertex from line " + line, e);
162       }
163     }
164     return distances;
165   }
166 
167   /**
168    * A local integration test on toy data
169    */
170   @Test
171   public void testToyData() throws Exception {
172 
173     // a small four vertex graph
174     String[] graph = new String[] {
175         "1 2:1.0 3:3.0",
176         "2 3:1.0 4:10.0",
177         "3 4:2.0",
178         "4"
179     };
180 
181     GiraphConfiguration conf = new GiraphConfiguration();
182     // start from vertex 1
183     SOURCE_ID.set(conf, 1);
184     conf.setComputationClass(SimpleShortestPathsComputation.class);
185     conf.setOutEdgesClass(ByteArrayEdges.class);
186     conf.setVertexInputFormatClass(LongDoubleFloatTextInputFormat.class);
187     conf.setVertexOutputFormatClass(
188         VertexWithDoubleValueNullEdgeTextOutputFormat.class);
189 
190     // run internally
191     Iterable<String> results = InternalVertexRunner.run(conf, graph);
192 
193     Map<Long, Double> distances = parseDistances(results);
194 
195     // verify results
196     assertNotNull(distances);
197     assertEquals(4, distances.size());
198     assertEquals(0.0, distances.get(1L), 0d);
199     assertEquals(1.0, distances.get(2L), 0d);
200     assertEquals(2.0, distances.get(3L), 0d);
201     assertEquals(4.0, distances.get(4L), 0d);
202   }
203 
204   private Map<Long, Double> parseDistances(Iterable<String> results) {
205     Map<Long, Double> distances =
206         Maps.newHashMapWithExpectedSize(Iterables.size(results));
207 
208     Pattern separator = Pattern.compile("[\t]");
209 
210     for (String line : results) {
211       String[] tokens = separator.split(line);
212       distances.put(Long.parseLong(tokens[0]), Double.parseDouble(tokens[1]));
213     }
214     return distances;
215   }
216 }