This project has retired. For details please refer to its
Attic page.
SimpleShortestPathsComputation 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.graph.BasicComputation;
22 import org.apache.giraph.conf.LongConfOption;
23 import org.apache.giraph.edge.Edge;
24 import org.apache.giraph.graph.Vertex;
25 import org.apache.hadoop.io.DoubleWritable;
26 import org.apache.hadoop.io.FloatWritable;
27 import org.apache.hadoop.io.LongWritable;
28 import org.apache.log4j.Logger;
29
30 import java.io.IOException;
31
32
33
34
35 @Algorithm(
36 name = "Shortest paths",
37 description = "Finds all shortest paths from a selected vertex"
38 )
39 public class SimpleShortestPathsComputation extends BasicComputation<
40 LongWritable, DoubleWritable, FloatWritable, DoubleWritable> {
41
42 public static final LongConfOption SOURCE_ID =
43 new LongConfOption("SimpleShortestPathsVertex.sourceId", 1,
44 "The shortest paths id");
45
46 private static final Logger LOG =
47 Logger.getLogger(SimpleShortestPathsComputation.class);
48
49
50
51
52
53
54
55 private boolean isSource(Vertex<LongWritable, ?, ?> vertex) {
56 return vertex.getId().get() == SOURCE_ID.get(getConf());
57 }
58
59 @Override
60 public void compute(
61 Vertex<LongWritable, DoubleWritable, FloatWritable> vertex,
62 Iterable<DoubleWritable> messages) throws IOException {
63 if (getSuperstep() == 0) {
64 vertex.setValue(new DoubleWritable(Double.MAX_VALUE));
65 }
66 double minDist = isSource(vertex) ? 0d : Double.MAX_VALUE;
67 for (DoubleWritable message : messages) {
68 minDist = Math.min(minDist, message.get());
69 }
70 if (LOG.isDebugEnabled()) {
71 LOG.debug("Vertex " + vertex.getId() + " got minDist = " + minDist +
72 " vertex value = " + vertex.getValue());
73 }
74 if (minDist < vertex.getValue().get()) {
75 vertex.setValue(new DoubleWritable(minDist));
76 for (Edge<LongWritable, FloatWritable> edge : vertex.getEdges()) {
77 double distance = minDist + edge.getValue().get();
78 if (LOG.isDebugEnabled()) {
79 LOG.debug("Vertex " + vertex.getId() + " sent to " +
80 edge.getTargetVertexId() + " = " + distance);
81 }
82 sendMessage(edge.getTargetVertexId(), new DoubleWritable(distance));
83 }
84 }
85 vertex.voteToHalt();
86 }
87 }