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.utils.InternalVertexRunner;
24 import org.junit.Test;
25
26 import java.util.Map;
27
28 import static org.junit.Assert.assertEquals;
29
30
31
32
33 public class RandomWalkWithRestartComputationTest {
34
35
36
37
38 @Test
39 public void testToyData() throws Exception {
40
41 String[] graph = new String[] { "12 34 56", "34 78", "56 34 78", "78 34" };
42
43 GiraphConfiguration conf = new GiraphConfiguration();
44 conf.setInt(RandomWalkWithRestartComputation.SOURCE_VERTEX, 12);
45 conf.setInt(RandomWalkWithRestartComputation.MAX_SUPERSTEPS, 30);
46 conf.setFloat(
47 RandomWalkWithRestartComputation.TELEPORTATION_PROBABILITY, 0.25f);
48 conf.setComputationClass(RandomWalkWithRestartComputation.class);
49 conf.setOutEdgesClass(ByteArrayEdges.class);
50 conf.setVertexInputFormatClass(LongDoubleDoubleTextInputFormat.class);
51 conf.setVertexOutputFormatClass(
52 VertexWithDoubleValueDoubleEdgeTextOutputFormat.class);
53 conf.setWorkerContextClass(RandomWalkWorkerContext.class);
54 conf.setMasterComputeClass(RandomWalkVertexMasterCompute.class);
55
56 Iterable<String> results = InternalVertexRunner.run(conf, graph);
57
58 Map<Long, Double> steadyStateProbabilities =
59 RandomWalkTestUtils.parseSteadyStateProbabilities(results);
60
61
62 assertEquals(0.25, steadyStateProbabilities.get(12L), RandomWalkTestUtils.EPSILON);
63 assertEquals(0.354872, steadyStateProbabilities.get(34L),
64 RandomWalkTestUtils.EPSILON);
65 assertEquals(0.09375, steadyStateProbabilities.get(56L), RandomWalkTestUtils.EPSILON);
66 assertEquals(0.301377, steadyStateProbabilities.get(78L),
67 RandomWalkTestUtils.EPSILON);
68 }
69
70
71
72
73 @Test
74 public void testWeightedGraph() throws Exception {
75
76 String[] graph =
77 new String[] { "12 34:0.1 56:0.9", "34 78:0.9 56:0.1",
78 "56 12:0.1 34:0.8 78:0.1", "78 34:1.0" };
79
80 GiraphConfiguration conf = new GiraphConfiguration();
81 conf.setInt(RandomWalkWithRestartComputation.SOURCE_VERTEX, 12);
82 conf.setInt(RandomWalkWithRestartComputation.MAX_SUPERSTEPS, 30);
83 conf.setFloat(
84 RandomWalkWithRestartComputation.TELEPORTATION_PROBABILITY, 0.15f);
85 conf.setComputationClass(RandomWalkWithRestartComputation.class);
86 conf.setOutEdgesClass(ByteArrayEdges.class);
87 conf.setVertexInputFormatClass(
88 NormalizingLongDoubleDoubleTextInputFormat.class);
89 conf.setVertexOutputFormatClass(
90 VertexWithDoubleValueDoubleEdgeTextOutputFormat.class);
91 conf.setWorkerContextClass(RandomWalkWorkerContext.class);
92 conf.setMasterComputeClass(RandomWalkVertexMasterCompute.class);
93
94 Iterable<String> results = InternalVertexRunner.run(conf, graph);
95
96 Map<Long, Double> steadyStateProbabilities =
97 RandomWalkTestUtils.parseSteadyStateProbabilities(results);
98
99
100 assertEquals(0.163365, steadyStateProbabilities.get(12L),
101 RandomWalkTestUtils.EPSILON);
102 assertEquals(0.378932, steadyStateProbabilities.get(34L),
103 RandomWalkTestUtils.EPSILON);
104 assertEquals(0.156886, steadyStateProbabilities.get(56L),
105 RandomWalkTestUtils.EPSILON);
106 assertEquals(0.300816, steadyStateProbabilities.get(78L),
107 RandomWalkTestUtils.EPSILON);
108 }
109
110
111 }