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