-
Notifications
You must be signed in to change notification settings - Fork 13
/
shortest_path.go
81 lines (71 loc) · 1.87 KB
/
shortest_path.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// Implements the FindShortestPath operation
// See the Spark implementation for details
package main
import (
"math"
)
type EdgeInfo struct {
src SphynxId
dst SphynxId
d float64
}
func doShortestPath(
edges *EdgeBundle,
edgeDistance *DoubleAttribute,
startingDistance *DoubleAttribute,
maxIterations int) *DoubleAttribute {
numVertices := len(startingDistance.Values)
numEdges := len(edges.Dst)
distance := DoubleAttribute{
Values: make([]float64, numVertices),
Defined: make([]bool, numVertices),
}
for i := 0; i < numVertices; i++ {
if startingDistance.Defined[i] {
distance.Values[i] = startingDistance.Values[i]
} else {
distance.Values[i] = math.Inf(1)
}
}
compressedEdges := make([]EdgeInfo, 0, numEdges)
for i := 0; i < numEdges; i++ {
if edgeDistance.Defined[i] {
e := EdgeInfo{
src: edges.Src[i],
dst: edges.Dst[i],
d: edgeDistance.Values[i],
}
compressedEdges = append(compressedEdges, e)
}
}
for moreWork := true; moreWork && maxIterations > 0; maxIterations-- {
moreWork = false
for _, e := range compressedEdges {
src := e.src
dst := e.dst
srcCurrentBest := distance.Values[src]
maybeBetter := srcCurrentBest + e.d
if maybeBetter < distance.Values[dst] {
distance.Values[dst] = maybeBetter
moreWork = true
}
}
}
for i := 0; i < numVertices; i++ {
distance.Defined[i] = distance.Values[i] != math.Inf(1)
}
return &distance
}
func init() {
operationRepository["ShortestPath"] = Operation{
execute: func(ea *EntityAccessor) error {
es := ea.getEdgeBundle("es")
edgeDistance := ea.getDoubleAttribute("edgeDistance")
startingDistance := ea.getDoubleAttribute("startingDistance")
maxIterations := int(ea.GetFloatParam("maxIterations"))
distance := doShortestPath(es, edgeDistance, startingDistance, maxIterations)
ea.output("distance", distance)
return nil
},
}
}