-
Notifications
You must be signed in to change notification settings - Fork 0
/
arc_flag_bi_dijkstra.go
178 lines (151 loc) · 6.48 KB
/
arc_flag_bi_dijkstra.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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
package shortest_path
import (
"container/heap"
g "github.com/dmholtz/graffiti/graph"
)
// BidirectionalArcFlagRouter implements the Router interface and improves bidirectional Dijkstra's algorithm by incorporating arc flags.
type BidirectionalArcFlagRouter[N g.Partitioner, E g.IFlaggedHalfEdge[W], W g.Weight] struct {
Graph g.Graph[N, E]
Transpose g.Graph[N, E]
MaxInitializerValue W
}
// String implements fmt.Stringer
func (r BidirectionalArcFlagRouter[N, E, W]) String() string {
return "Bidirectional ArcFlag Dijkstra"
}
// Bidirectional Dijkstra runs a forward search from the source node to the target node in parallel with
// a backward search in the backward graph (transpose) from the target node to the source node.
//
// Bidirectional search requires both the forward graph and its transpose (backward graph) as input parameters.
// In case of undirected graphs, the same argument may be passed for both parameters.
//
// Reference: https://www.homepages.ucl.ac.uk/~ucahmto/math/2020/05/30/bidirectional-dijkstra.html
func (r BidirectionalArcFlagRouter[N, E, W]) Route(source, target g.NodeId, recordSearchSpace bool) ShortestPathResult[W] {
var searchSpace []g.NodeId = nil
if recordSearchSpace {
searchSpace = make([]g.NodeId, 0)
}
// handle trivial search with source and target being the same node
if source == target {
return ShortestPathResult[W]{Length: W(0), Path: []g.NodeId{source}, PqPops: 0, SearchSpace: searchSpace}
}
dijkstraItemsForward := make([]*DijkstraPqItem[W], r.Graph.NodeCount(), r.Graph.NodeCount())
dijkstraItemsForward[source] = &DijkstraPqItem[W]{Id: source, Priority: 0, Predecessor: -1}
dijkstraItemsBackward := make([]*DijkstraPqItem[W], r.Transpose.NodeCount(), r.Transpose.NodeCount())
dijkstraItemsBackward[target] = &DijkstraPqItem[W]{Id: target, Priority: 0, Predecessor: -1}
pqForward := make(DijkstraPriorityQueue[W], 0)
heap.Init(&pqForward)
heap.Push(&pqForward, dijkstraItemsForward[source])
pqBackward := make(DijkstraPriorityQueue[W], 0)
heap.Init(&pqBackward)
heap.Push(&pqBackward, dijkstraItemsBackward[target])
// Once the algorithm terminates, mu contains the shortest path distance between source and target.
mu := r.MaxInitializerValue // initialize with the largest representable number of weight type W
middleNodeId := -1
sourcePart := r.Transpose.GetNode(source).Partition()
targetPart := r.Graph.GetNode(target).Partition()
pqPops := 0
for len(pqForward) > 0 && len(pqBackward) > 0 {
forwardPqItem := heap.Pop(&pqForward).(*DijkstraPqItem[W])
forwardNodeId := forwardPqItem.Id
backwardPqItem := heap.Pop(&pqBackward).(*DijkstraPqItem[W])
backwardNodeId := backwardPqItem.Id
pqPops += 2
if recordSearchSpace {
searchSpace = append(searchSpace, forwardNodeId)
searchSpace = append(searchSpace, backwardNodeId)
}
// forward search
for _, edge := range r.Graph.GetHalfEdgesFrom(forwardNodeId) {
successor := edge.To()
if !edge.IsFlagged(targetPart) {
continue
}
// find the reverse edge
var revEdge E
for _, e := range r.Transpose.GetHalfEdgesFrom(successor) {
if e.To() == forwardNodeId {
revEdge = e
break
}
}
if !revEdge.IsFlagged(sourcePart) {
continue
}
if dijkstraItemsForward[successor] == nil {
newPriority := dijkstraItemsForward[forwardNodeId].Priority + edge.Weight()
pqItem := DijkstraPqItem[W]{Id: successor, Priority: newPriority, Predecessor: forwardNodeId}
dijkstraItemsForward[successor] = &pqItem
heap.Push(&pqForward, &pqItem)
} else {
if updatedDistance := dijkstraItemsForward[forwardNodeId].Priority + edge.Weight(); updatedDistance < dijkstraItemsForward[successor].Priority {
dijkstraItemsForward[successor].Priority = updatedDistance
dijkstraItemsForward[successor].Predecessor = forwardNodeId
heap.Fix(&pqForward, dijkstraItemsForward[successor].index)
}
}
if x := dijkstraItemsBackward[successor]; x != nil && dijkstraItemsForward[forwardNodeId].Priority+edge.Weight()+x.Priority < mu {
mu = dijkstraItemsForward[forwardNodeId].Priority + edge.Weight() + x.Priority
dijkstraItemsForward[successor].Predecessor = forwardNodeId
middleNodeId = successor
}
}
// backward search
for _, edge := range r.Graph.GetHalfEdgesFrom(backwardNodeId) {
successor := edge.To()
if !edge.IsFlagged(sourcePart) {
continue
}
// find the reverse edge
var revEdge E
for _, e := range r.Graph.GetHalfEdgesFrom(successor) {
if e.To() == backwardNodeId {
revEdge = e
break
}
}
if !revEdge.IsFlagged(targetPart) {
continue
}
if dijkstraItemsBackward[successor] == nil {
newPriority := dijkstraItemsBackward[backwardNodeId].Priority + edge.Weight()
pqItem := DijkstraPqItem[W]{Id: successor, Priority: newPriority, Predecessor: backwardNodeId}
dijkstraItemsBackward[successor] = &pqItem
heap.Push(&pqBackward, &pqItem)
} else {
if updatedDistance := dijkstraItemsBackward[backwardNodeId].Priority + edge.Weight(); updatedDistance < dijkstraItemsBackward[successor].Priority {
dijkstraItemsBackward[successor].Priority = updatedDistance
dijkstraItemsBackward[successor].Predecessor = backwardNodeId
heap.Fix(&pqBackward, dijkstraItemsBackward[successor].index)
}
}
if x := dijkstraItemsForward[successor]; x != nil && dijkstraItemsBackward[backwardNodeId].Priority+edge.Weight()+x.Priority < mu {
mu = dijkstraItemsBackward[backwardNodeId].Priority + edge.Weight() + x.Priority
dijkstraItemsBackward[successor].Predecessor = backwardNodeId
middleNodeId = successor
}
}
// stopping criterion
if dijkstraItemsForward[forwardNodeId].Priority+dijkstraItemsBackward[backwardNodeId].Priority >= mu {
break
}
}
res := ShortestPathResult[W]{Length: W(-1), Path: make([]g.NodeId, 0), PqPops: pqPops, SearchSpace: searchSpace}
// check if path exists
if mu < r.MaxInitializerValue {
res.Length = mu
// sanity check: length == dijkstraItemsForward[middleNodeId].priority + dijkstraItemsBackward[middleNodeId].priority
if dijkstraItemsForward[middleNodeId] != nil && dijkstraItemsBackward[middleNodeId] != nil {
for nodeId := middleNodeId; nodeId != -1; nodeId = dijkstraItemsForward[nodeId].Predecessor {
res.Path = append([]int{nodeId}, res.Path...)
}
if res.Path[len(res.Path)-1] == middleNodeId {
res.Path = res.Path[0 : len(res.Path)-1]
}
for nodeId := middleNodeId; nodeId != -1; nodeId = dijkstraItemsBackward[nodeId].Predecessor {
res.Path = append(res.Path, nodeId)
}
}
}
return res
}