This project has retired. For details please refer to its
Attic page.
SimpleShortestPathsComputationTest 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;
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
52
53 public class SimpleShortestPathsComputationTest {
54
55
56
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
87
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
116
117 @Test
118 public void testToyDataJson() throws Exception {
119
120
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
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
139 Iterable<String> results = InternalVertexRunner.run(conf, graph);
140
141 Map<Long, Double> distances = parseDistancesJson(results);
142
143
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
169
170 @Test
171 public void testToyData() throws Exception {
172
173
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
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
191 Iterable<String> results = InternalVertexRunner.run(conf, graph);
192
193 Map<Long, Double> distances = parseDistances(results);
194
195
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 }