"Fossies" - the Fresh Open Source Software Archive 
Member "gdrive-2.1.1/vendor/github.com/soniakeys/graph/sssp.go" (28 May 2021, 25256 Bytes) of package /linux/misc/gdrive-2.1.1.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Go source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
1 // Copyright 2013 Sonia Keys
2 // License MIT: http://opensource.org/licenses/MIT
3
4 package graph
5
6 import (
7 "container/heap"
8 "fmt"
9 "math"
10 )
11
12 // rNode holds data for a "reached" node
13 type rNode struct {
14 nx NI
15 state int8 // state constants defined below
16 f float64 // "g+h", path dist + heuristic estimate
17 fx int // heap.Fix index
18 }
19
20 // for rNode.state
21 const (
22 unreached = 0
23 reached = 1
24 open = 1
25 closed = 2
26 )
27
28 type openHeap []*rNode
29
30 // A Heuristic is defined on a specific end node. The function
31 // returns an estimate of the path distance from node argument
32 // "from" to the end node. Two subclasses of heuristics are "admissible"
33 // and "monotonic."
34 //
35 // Admissible means the value returned is guaranteed to be less than or
36 // equal to the actual shortest path distance from the node to end.
37 //
38 // An admissible estimate may further be monotonic.
39 // Monotonic means that for any neighboring nodes A and B with half arc aB
40 // leading from A to B, and for heuristic h defined on some end node, then
41 // h(A) <= aB.ArcWeight + h(B).
42 //
43 // See AStarA for additional notes on implementing heuristic functions for
44 // AStar search methods.
45 type Heuristic func(from NI) float64
46
47 // Admissible returns true if heuristic h is admissible on graph g relative to
48 // the given end node.
49 //
50 // If h is inadmissible, the string result describes a counter example.
51 func (h Heuristic) Admissible(g LabeledAdjacencyList, w WeightFunc, end NI) (bool, string) {
52 // invert graph
53 inv := make(LabeledAdjacencyList, len(g))
54 for from, nbs := range g {
55 for _, nb := range nbs {
56 inv[nb.To] = append(inv[nb.To],
57 Half{To: NI(from), Label: nb.Label})
58 }
59 }
60 // run dijkstra
61 // Dijkstra.AllPaths takes a start node but after inverting the graph
62 // argument end now represents the start node of the inverted graph.
63 f, dist, _ := inv.Dijkstra(end, -1, w)
64 // compare h to found shortest paths
65 for n := range inv {
66 if f.Paths[n].Len == 0 {
67 continue // no path, any heuristic estimate is fine.
68 }
69 if !(h(NI(n)) <= dist[n]) {
70 return false, fmt.Sprintf("h(%d) = %g, "+
71 "required to be <= found shortest path (%g)",
72 n, h(NI(n)), dist[n])
73 }
74 }
75 return true, ""
76 }
77
78 // Monotonic returns true if heuristic h is monotonic on weighted graph g.
79 //
80 // If h is non-monotonic, the string result describes a counter example.
81 func (h Heuristic) Monotonic(g LabeledAdjacencyList, w WeightFunc) (bool, string) {
82 // precompute
83 hv := make([]float64, len(g))
84 for n := range g {
85 hv[n] = h(NI(n))
86 }
87 // iterate over all edges
88 for from, nbs := range g {
89 for _, nb := range nbs {
90 arcWeight := w(nb.Label)
91 if !(hv[from] <= arcWeight+hv[nb.To]) {
92 return false, fmt.Sprintf("h(%d) = %g, "+
93 "required to be <= arc weight + h(%d) (= %g + %g = %g)",
94 from, hv[from],
95 nb.To, arcWeight, hv[nb.To], arcWeight+hv[nb.To])
96 }
97 }
98 }
99 return true, ""
100 }
101
102 // AStarA finds a path between two nodes.
103 //
104 // AStarA implements both algorithm A and algorithm A*. The difference in the
105 // two algorithms is strictly in the heuristic estimate returned by argument h.
106 // If h is an "admissible" heuristic estimate, then the algorithm is termed A*,
107 // otherwise it is algorithm A.
108 //
109 // Like Dijkstra's algorithm, AStarA with an admissible heuristic finds the
110 // shortest path between start and end. AStarA generally runs faster than
111 // Dijkstra though, by using the heuristic distance estimate.
112 //
113 // AStarA with an inadmissible heuristic becomes algorithm A. Algorithm A
114 // will find a path, but it is not guaranteed to be the shortest path.
115 // The heuristic still guides the search however, so a nearly admissible
116 // heuristic is likely to find a very good path, if not the best. Quality
117 // of the path returned degrades gracefully with the quality of the heuristic.
118 //
119 // The heuristic function h should ideally be fairly inexpensive. AStarA
120 // may call it more than once for the same node, especially as graph density
121 // increases. In some cases it may be worth the effort to memoize or
122 // precompute values.
123 //
124 // Argument g is the graph to be searched, with arc weights returned by w.
125 // As usual for AStar, arc weights must be non-negative.
126 // Graphs may be directed or undirected.
127 //
128 // If AStarA finds a path it returns a FromList encoding the path, the arc
129 // labels for path nodes, the total path distance, and ok = true.
130 // Otherwise it returns ok = false.
131 func (g LabeledAdjacencyList) AStarA(w WeightFunc, start, end NI, h Heuristic) (f FromList, labels []LI, dist float64, ok bool) {
132 // NOTE: AStarM is largely duplicate code.
133
134 f = NewFromList(len(g))
135 labels = make([]LI, len(g))
136 d := make([]float64, len(g))
137 r := make([]rNode, len(g))
138 for i := range r {
139 r[i].nx = NI(i)
140 }
141 // start node is reached initially
142 cr := &r[start]
143 cr.state = reached
144 cr.f = h(start) // total path estimate is estimate from start
145 rp := f.Paths
146 rp[start] = PathEnd{Len: 1, From: -1} // path length at start is 1 node
147 // oh is a heap of nodes "open" for exploration. nodes go on the heap
148 // when they get an initial or new "g" path distance, and therefore a
149 // new "f" which serves as priority for exploration.
150 oh := openHeap{cr}
151 for len(oh) > 0 {
152 bestPath := heap.Pop(&oh).(*rNode)
153 bestNode := bestPath.nx
154 if bestNode == end {
155 return f, labels, d[end], true
156 }
157 bp := &rp[bestNode]
158 nextLen := bp.Len + 1
159 for _, nb := range g[bestNode] {
160 alt := &r[nb.To]
161 ap := &rp[alt.nx]
162 // "g" path distance from start
163 g := d[bestNode] + w(nb.Label)
164 if alt.state == reached {
165 if g > d[nb.To] {
166 // candidate path to nb is longer than some alternate path
167 continue
168 }
169 if g == d[nb.To] && nextLen >= ap.Len {
170 // candidate path has identical length of some alternate
171 // path but it takes no fewer hops.
172 continue
173 }
174 // cool, we found a better way to get to this node.
175 // record new path data for this node and
176 // update alt with new data and make sure it's on the heap.
177 *ap = PathEnd{From: bestNode, Len: nextLen}
178 labels[nb.To] = nb.Label
179 d[nb.To] = g
180 alt.f = g + h(nb.To)
181 if alt.fx < 0 {
182 heap.Push(&oh, alt)
183 } else {
184 heap.Fix(&oh, alt.fx)
185 }
186 } else {
187 // bestNode being reached for the first time.
188 *ap = PathEnd{From: bestNode, Len: nextLen}
189 labels[nb.To] = nb.Label
190 d[nb.To] = g
191 alt.f = g + h(nb.To)
192 alt.state = reached
193 heap.Push(&oh, alt) // and it's now open for exploration
194 }
195 }
196 }
197 return // no path
198 }
199
200 // AStarAPath finds a shortest path using the AStarA algorithm.
201 //
202 // This is a convenience method with a simpler result than the AStarA method.
203 // See documentation on the AStarA method.
204 //
205 // If a path is found, the non-nil node path is returned with the total path
206 // distance. Otherwise the returned path will be nil.
207 func (g LabeledAdjacencyList) AStarAPath(start, end NI, h Heuristic, w WeightFunc) ([]NI, float64) {
208 f, _, d, _ := g.AStarA(w, start, end, h)
209 return f.PathTo(end, nil), d
210 }
211
212 // AStarM is AStarA optimized for monotonic heuristic estimates.
213 //
214 // Note that this function requires a monotonic heuristic. Results will
215 // not be meaningful if argument h is non-monotonic.
216 //
217 // See AStarA for general usage. See Heuristic for notes on monotonicity.
218 func (g LabeledAdjacencyList) AStarM(w WeightFunc, start, end NI, h Heuristic) (f FromList, labels []LI, dist float64, ok bool) {
219 // NOTE: AStarM is largely code duplicated from AStarA.
220 // Differences are noted in comments in this method.
221
222 f = NewFromList(len(g))
223 labels = make([]LI, len(g))
224 d := make([]float64, len(g))
225 r := make([]rNode, len(g))
226 for i := range r {
227 r[i].nx = NI(i)
228 }
229 cr := &r[start]
230
231 // difference from AStarA:
232 // instead of a bit to mark a reached node, there are two states,
233 // open and closed. open marks nodes "open" for exploration.
234 // nodes are marked open as they are reached, then marked
235 // closed as they are found to be on the best path.
236 cr.state = open
237
238 cr.f = h(start)
239 rp := f.Paths
240 rp[start] = PathEnd{Len: 1, From: -1}
241 oh := openHeap{cr}
242 for len(oh) > 0 {
243 bestPath := heap.Pop(&oh).(*rNode)
244 bestNode := bestPath.nx
245 if bestNode == end {
246 return f, labels, d[end], true
247 }
248
249 // difference from AStarA:
250 // move nodes to closed list as they are found to be best so far.
251 bestPath.state = closed
252
253 bp := &rp[bestNode]
254 nextLen := bp.Len + 1
255 for _, nb := range g[bestNode] {
256 alt := &r[nb.To]
257
258 // difference from AStarA:
259 // Monotonicity means that f cannot be improved.
260 if alt.state == closed {
261 continue
262 }
263
264 ap := &rp[alt.nx]
265 g := d[bestNode] + w(nb.Label)
266
267 // difference from AStarA:
268 // test for open state, not just reached
269 if alt.state == open {
270
271 if g > d[nb.To] {
272 continue
273 }
274 if g == d[nb.To] && nextLen >= ap.Len {
275 continue
276 }
277 *ap = PathEnd{From: bestNode, Len: nextLen}
278 labels[nb.To] = nb.Label
279 d[nb.To] = g
280 alt.f = g + h(nb.To)
281
282 // difference from AStarA:
283 // we know alt was on the heap because we found it marked open
284 heap.Fix(&oh, alt.fx)
285 } else {
286 *ap = PathEnd{From: bestNode, Len: nextLen}
287 labels[nb.To] = nb.Label
288 d[nb.To] = g
289 alt.f = g + h(nb.To)
290
291 // difference from AStarA:
292 // nodes are opened when first reached
293 alt.state = open
294 heap.Push(&oh, alt)
295 }
296 }
297 }
298 return
299 }
300
301 // AStarMPath finds a shortest path using the AStarM algorithm.
302 //
303 // This is a convenience method with a simpler result than the AStarM method.
304 // See documentation on the AStarM and AStarA methods.
305 //
306 // If a path is found, the non-nil node path is returned with the total path
307 // distance. Otherwise the returned path will be nil.
308 func (g LabeledAdjacencyList) AStarMPath(start, end NI, h Heuristic, w WeightFunc) ([]NI, float64) {
309 f, _, d, _ := g.AStarM(w, start, end, h)
310 return f.PathTo(end, nil), d
311 }
312
313 // implement container/heap
314 func (h openHeap) Len() int { return len(h) }
315 func (h openHeap) Less(i, j int) bool { return h[i].f < h[j].f }
316 func (h openHeap) Swap(i, j int) {
317 h[i], h[j] = h[j], h[i]
318 h[i].fx = i
319 h[j].fx = j
320 }
321 func (p *openHeap) Push(x interface{}) {
322 h := *p
323 fx := len(h)
324 h = append(h, x.(*rNode))
325 h[fx].fx = fx
326 *p = h
327 }
328
329 func (p *openHeap) Pop() interface{} {
330 h := *p
331 last := len(h) - 1
332 *p = h[:last]
333 h[last].fx = -1
334 return h[last]
335 }
336
337 // BellmanFord finds shortest paths from a start node in a weighted directed
338 // graph using the Bellman-Ford-Moore algorithm.
339 //
340 // WeightFunc w must translate arc labels to arc weights.
341 // Negative arc weights are allowed but not negative cycles.
342 // Loops and parallel arcs are allowed.
343 //
344 // If the algorithm completes without encountering a negative cycle the method
345 // returns shortest paths encoded in a FromList, path distances indexed by
346 // node, and return value end = -1.
347 //
348 // If it encounters a negative cycle reachable from start it returns end >= 0.
349 // In this case the cycle can be obtained by calling f.BellmanFordCycle(end).
350 //
351 // Negative cycles are only detected when reachable from start. A negative
352 // cycle not reachable from start will not prevent the algorithm from finding
353 // shortest paths from start.
354 //
355 // See also NegativeCycle to find a cycle anywhere in the graph, and see
356 // HasNegativeCycle for lighter-weight negative cycle detection,
357 func (g LabeledDirected) BellmanFord(w WeightFunc, start NI) (f FromList, dist []float64, end NI) {
358 a := g.LabeledAdjacencyList
359 f = NewFromList(len(a))
360 dist = make([]float64, len(a))
361 inf := math.Inf(1)
362 for i := range dist {
363 dist[i] = inf
364 }
365 rp := f.Paths
366 rp[start] = PathEnd{Len: 1, From: -1}
367 dist[start] = 0
368 for _ = range a[1:] {
369 imp := false
370 for from, nbs := range a {
371 fp := &rp[from]
372 d1 := dist[from]
373 for _, nb := range nbs {
374 d2 := d1 + w(nb.Label)
375 to := &rp[nb.To]
376 // TODO improve to break ties
377 if fp.Len > 0 && d2 < dist[nb.To] {
378 *to = PathEnd{From: NI(from), Len: fp.Len + 1}
379 dist[nb.To] = d2
380 imp = true
381 }
382 }
383 }
384 if !imp {
385 break
386 }
387 }
388 for from, nbs := range a {
389 d1 := dist[from]
390 for _, nb := range nbs {
391 if d1+w(nb.Label) < dist[nb.To] {
392 // return nb as end of a path with negative cycle at root
393 return f, dist, NI(from)
394 }
395 }
396 }
397 return f, dist, -1
398 }
399
400 // BellmanFordCycle decodes a negative cycle detected by BellmanFord.
401 //
402 // Receiver f and argument end must be results returned from BellmanFord.
403 func (f FromList) BellmanFordCycle(end NI) (c []NI) {
404 p := f.Paths
405 var b Bits
406 for b.Bit(end) == 0 {
407 b.SetBit(end, 1)
408 end = p[end].From
409 }
410 for b.Bit(end) == 1 {
411 c = append(c, end)
412 b.SetBit(end, 0)
413 end = p[end].From
414 }
415 for i, j := 0, len(c)-1; i < j; i, j = i+1, j-1 {
416 c[i], c[j] = c[j], c[i]
417 }
418 return
419 }
420
421 // HasNegativeCycle returns true if the graph contains any negative cycle.
422 //
423 // HasNegativeCycle uses a Bellman-Ford-like algorithm, but finds negative
424 // cycles anywhere in the graph. Also path information is not computed,
425 // reducing memory use somewhat compared to BellmanFord.
426 //
427 // See also NegativeCycle to obtain the cycle, and see BellmanFord for
428 // single source shortest path searches.
429 func (g LabeledDirected) HasNegativeCycle(w WeightFunc) bool {
430 a := g.LabeledAdjacencyList
431 dist := make([]float64, len(a))
432 for _ = range a[1:] {
433 imp := false
434 for from, nbs := range a {
435 d1 := dist[from]
436 for _, nb := range nbs {
437 d2 := d1 + w(nb.Label)
438 if d2 < dist[nb.To] {
439 dist[nb.To] = d2
440 imp = true
441 }
442 }
443 }
444 if !imp {
445 break
446 }
447 }
448 for from, nbs := range a {
449 d1 := dist[from]
450 for _, nb := range nbs {
451 if d1+w(nb.Label) < dist[nb.To] {
452 return true // negative cycle
453 }
454 }
455 }
456 return false
457 }
458
459 // NegativeCycle finds a negative cycle if one exists.
460 //
461 // NegativeCycle uses a Bellman-Ford-like algorithm, but finds negative
462 // cycles anywhere in the graph. If a negative cycle exists, one will be
463 // returned. The result is nil if no negative cycle exists.
464 //
465 // See also HasNegativeCycle for lighter-weight cycle detection, and see
466 // BellmanFord for single source shortest paths.
467 func (g LabeledDirected) NegativeCycle(w WeightFunc) (c []NI) {
468 a := g.LabeledAdjacencyList
469 f := NewFromList(len(a))
470 p := f.Paths
471 for n := range p {
472 p[n] = PathEnd{From: -1, Len: 1}
473 }
474 dist := make([]float64, len(a))
475 for _ = range a {
476 imp := false
477 for from, nbs := range a {
478 fp := &p[from]
479 d1 := dist[from]
480 for _, nb := range nbs {
481 d2 := d1 + w(nb.Label)
482 to := &p[nb.To]
483 if fp.Len > 0 && d2 < dist[nb.To] {
484 *to = PathEnd{From: NI(from), Len: fp.Len + 1}
485 dist[nb.To] = d2
486 imp = true
487 }
488 }
489 }
490 if !imp {
491 return nil
492 }
493 }
494 var vis Bits
495 a:
496 for n := range a {
497 end := NI(n)
498 var b Bits
499 for b.Bit(end) == 0 {
500 if vis.Bit(end) == 1 {
501 continue a
502 }
503 vis.SetBit(end, 1)
504 b.SetBit(end, 1)
505 end = p[end].From
506 if end < 0 {
507 continue a
508 }
509 }
510 for b.Bit(end) == 1 {
511 c = append(c, end)
512 b.SetBit(end, 0)
513 end = p[end].From
514 }
515 for i, j := 0, len(c)-1; i < j; i, j = i+1, j-1 {
516 c[i], c[j] = c[j], c[i]
517 }
518 return c
519 }
520 return nil // no negative cycle
521 }
522
523 // A NodeVisitor is an argument to some graph traversal methods.
524 //
525 // Graph traversal methods call the visitor function for each node visited.
526 // Argument n is the node being visited.
527 type NodeVisitor func(n NI)
528
529 // An OkNodeVisitor function is an argument to some graph traversal methods.
530 //
531 // Graph traversal methods call the visitor function for each node visited.
532 // The argument n is the node being visited. If the visitor function
533 // returns true, the traversal will continue. If the visitor function
534 // returns false, the traversal will terminate immediately.
535 type OkNodeVisitor func(n NI) (ok bool)
536
537 // BreadthFirst2 traverses a graph breadth first using a direction
538 // optimizing algorithm.
539 //
540 // The code is experimental and currently seems no faster than the
541 // conventional breadth first code.
542 //
543 // Use AdjacencyList.BreadthFirst instead.
544 func BreadthFirst2(g, tr AdjacencyList, ma int, start NI, f *FromList, v OkNodeVisitor) int {
545 if tr == nil {
546 var d Directed
547 d, ma = Directed{g}.Transpose()
548 tr = d.AdjacencyList
549 }
550 switch {
551 case f == nil:
552 e := NewFromList(len(g))
553 f = &e
554 case f.Paths == nil:
555 *f = NewFromList(len(g))
556 }
557 if ma <= 0 {
558 ma = g.ArcSize()
559 }
560 rp := f.Paths
561 level := 1
562 rp[start] = PathEnd{Len: level, From: -1}
563 if !v(start) {
564 f.MaxLen = level
565 return -1
566 }
567 nReached := 1 // accumulated for a return value
568 // the frontier consists of nodes all at the same level
569 frontier := []NI{start}
570 mf := len(g[start]) // number of arcs leading out from frontier
571 ctb := ma / 10 // threshold change from top-down to bottom-up
572 k14 := 14 * ma / len(g) // 14 * mean degree
573 cbt := len(g) / k14 // threshold change from bottom-up to top-down
574 // var fBits, nextb big.Int
575 fBits := make([]bool, len(g))
576 nextb := make([]bool, len(g))
577 zBits := make([]bool, len(g))
578 for {
579 // top down step
580 level++
581 var next []NI
582 for _, n := range frontier {
583 for _, nb := range g[n] {
584 if rp[nb].Len == 0 {
585 rp[nb] = PathEnd{From: n, Len: level}
586 if !v(nb) {
587 f.MaxLen = level
588 return -1
589 }
590 next = append(next, nb)
591 nReached++
592 }
593 }
594 }
595 if len(next) == 0 {
596 break
597 }
598 frontier = next
599 if mf > ctb {
600 // switch to bottom up!
601 } else {
602 // stick with top down
603 continue
604 }
605 // convert frontier representation
606 nf := 0 // number of vertices on the frontier
607 for _, n := range frontier {
608 // fBits.SetBit(&fBits, n, 1)
609 fBits[n] = true
610 nf++
611 }
612 bottomUpLoop:
613 level++
614 nNext := 0
615 for n := range tr {
616 if rp[n].Len == 0 {
617 for _, nb := range tr[n] {
618 // if fBits.Bit(nb) == 1 {
619 if fBits[nb] {
620 rp[n] = PathEnd{From: nb, Len: level}
621 if !v(nb) {
622 f.MaxLen = level
623 return -1
624 }
625 // nextb.SetBit(&nextb, n, 1)
626 nextb[n] = true
627 nReached++
628 nNext++
629 break
630 }
631 }
632 }
633 }
634 if nNext == 0 {
635 break
636 }
637 fBits, nextb = nextb, fBits
638 // nextb.SetInt64(0)
639 copy(nextb, zBits)
640 nf = nNext
641 if nf < cbt {
642 // switch back to top down!
643 } else {
644 // stick with bottom up
645 goto bottomUpLoop
646 }
647 // convert frontier representation
648 mf = 0
649 frontier = frontier[:0]
650 for n := range g {
651 // if fBits.Bit(n) == 1 {
652 if fBits[n] {
653 frontier = append(frontier, NI(n))
654 mf += len(g[n])
655 fBits[n] = false
656 }
657 }
658 // fBits.SetInt64(0)
659 }
660 f.MaxLen = level - 1
661 return nReached
662 }
663
664 // DAGMinDistPath finds a single shortest path.
665 //
666 // Shortest means minimum sum of arc weights.
667 //
668 // Returned is the path and distance as returned by FromList.PathTo.
669 //
670 // This is a convenience method. See DAGOptimalPaths for more options.
671 func (g LabeledDirected) DAGMinDistPath(start, end NI, w WeightFunc) ([]NI, float64, error) {
672 return g.dagPath(start, end, w, false)
673 }
674
675 // DAGMaxDistPath finds a single longest path.
676 //
677 // Longest means maximum sum of arc weights.
678 //
679 // Returned is the path and distance as returned by FromList.PathTo.
680 //
681 // This is a convenience method. See DAGOptimalPaths for more options.
682 func (g LabeledDirected) DAGMaxDistPath(start, end NI, w WeightFunc) ([]NI, float64, error) {
683 return g.dagPath(start, end, w, true)
684 }
685
686 func (g LabeledDirected) dagPath(start, end NI, w WeightFunc, longest bool) ([]NI, float64, error) {
687 o, _ := g.Topological()
688 if o == nil {
689 return nil, 0, fmt.Errorf("not a DAG")
690 }
691 f, dist, _ := g.DAGOptimalPaths(start, end, o, w, longest)
692 if f.Paths[end].Len == 0 {
693 return nil, 0, fmt.Errorf("no path from %d to %d", start, end)
694 }
695 return f.PathTo(end, nil), dist[end], nil
696 }
697
698 // DAGOptimalPaths finds either longest or shortest distance paths in a
699 // directed acyclic graph.
700 //
701 // Path distance is the sum of arc weights on the path.
702 // Negative arc weights are allowed.
703 // Where multiple paths exist with the same distance, the path length
704 // (number of nodes) is used as a tie breaker.
705 //
706 // Receiver g must be a directed acyclic graph. Argument o must be either nil
707 // or a topological ordering of g. If nil, a topologcal ordering is
708 // computed internally. If longest is true, an optimal path is a longest
709 // distance path. Otherwise it is a shortest distance path.
710 //
711 // Argument start is the start node for paths, end is the end node. If end
712 // is a valid node number, the method returns as soon as the optimal path
713 // to end is found. If end is -1, all optimal paths from start are found.
714 //
715 // Paths and path distances are encoded in the returned FromList and dist
716 // slice. The number of nodes reached is returned as nReached.
717 func (g LabeledDirected) DAGOptimalPaths(start, end NI, ordering []NI, w WeightFunc, longest bool) (f FromList, dist []float64, nReached int) {
718 a := g.LabeledAdjacencyList
719 f = NewFromList(len(a))
720 dist = make([]float64, len(a))
721 if ordering == nil {
722 ordering, _ = g.Topological()
723 }
724 // search ordering for start
725 o := 0
726 for ordering[o] != start {
727 o++
728 }
729 var fBetter func(cand, ext float64) bool
730 var iBetter func(cand, ext int) bool
731 if longest {
732 fBetter = func(cand, ext float64) bool { return cand > ext }
733 iBetter = func(cand, ext int) bool { return cand > ext }
734 } else {
735 fBetter = func(cand, ext float64) bool { return cand < ext }
736 iBetter = func(cand, ext int) bool { return cand < ext }
737 }
738 p := f.Paths
739 p[start] = PathEnd{From: -1, Len: 1}
740 f.MaxLen = 1
741 leaves := &f.Leaves
742 leaves.SetBit(start, 1)
743 nReached = 1
744 for n := start; n != end; n = ordering[o] {
745 if p[n].Len > 0 && len(a[n]) > 0 {
746 nDist := dist[n]
747 candLen := p[n].Len + 1 // len for any candidate arc followed from n
748 for _, to := range a[n] {
749 leaves.SetBit(to.To, 1)
750 candDist := nDist + w(to.Label)
751 switch {
752 case p[to.To].Len == 0: // first path to node to.To
753 nReached++
754 case fBetter(candDist, dist[to.To]): // better distance
755 case candDist == dist[to.To] && iBetter(candLen, p[to.To].Len): // same distance but better path length
756 default:
757 continue
758 }
759 dist[to.To] = candDist
760 p[to.To] = PathEnd{From: n, Len: candLen}
761 if candLen > f.MaxLen {
762 f.MaxLen = candLen
763 }
764 }
765 leaves.SetBit(n, 0)
766 }
767 o++
768 if o == len(ordering) {
769 break
770 }
771 }
772 return
773 }
774
775 // Dijkstra finds shortest paths by Dijkstra's algorithm.
776 //
777 // Shortest means shortest distance where distance is the
778 // sum of arc weights. Where multiple paths exist with the same distance,
779 // a path with the minimum number of nodes is returned.
780 //
781 // As usual for Dijkstra's algorithm, arc weights must be non-negative.
782 // Graphs may be directed or undirected. Loops and parallel arcs are
783 // allowed.
784 func (g LabeledAdjacencyList) Dijkstra(start, end NI, w WeightFunc) (f FromList, dist []float64, reached int) {
785 r := make([]tentResult, len(g))
786 for i := range r {
787 r[i].nx = NI(i)
788 }
789 f = NewFromList(len(g))
790 dist = make([]float64, len(g))
791 current := start
792 rp := f.Paths
793 rp[current] = PathEnd{Len: 1, From: -1} // path length at start is 1 node
794 cr := &r[current]
795 cr.dist = 0 // distance at start is 0.
796 cr.done = true // mark start done. it skips the heap.
797 nDone := 1 // accumulated for a return value
798 var t tent
799 for current != end {
800 nextLen := rp[current].Len + 1
801 for _, nb := range g[current] {
802 // d.arcVis++
803 hr := &r[nb.To]
804 if hr.done {
805 continue // skip nodes already done
806 }
807 dist := cr.dist + w(nb.Label)
808 vl := rp[nb.To].Len
809 visited := vl > 0
810 if visited {
811 if dist > hr.dist {
812 continue // distance is worse
813 }
814 // tie breaker is a nice touch and doesn't seem to
815 // impact performance much.
816 if dist == hr.dist && nextLen >= vl {
817 continue // distance same, but number of nodes is no better
818 }
819 }
820 // the path through current to this node is shortest so far.
821 // record new path data for this node and update tentative set.
822 hr.dist = dist
823 rp[nb.To].Len = nextLen
824 rp[nb.To].From = current
825 if visited {
826 heap.Fix(&t, hr.fx)
827 } else {
828 heap.Push(&t, hr)
829 }
830 }
831 //d.ndVis++
832 if len(t) == 0 {
833 return f, dist, nDone // no more reachable nodes. AllPaths normal return
834 }
835 // new current is node with smallest tentative distance
836 cr = heap.Pop(&t).(*tentResult)
837 cr.done = true
838 nDone++
839 current = cr.nx
840 dist[current] = cr.dist // store final distance
841 }
842 // normal return for single shortest path search
843 return f, dist, -1
844 }
845
846 // DijkstraPath finds a single shortest path.
847 //
848 // Returned is the path and distance as returned by FromList.PathTo.
849 func (g LabeledAdjacencyList) DijkstraPath(start, end NI, w WeightFunc) ([]NI, float64) {
850 f, dist, _ := g.Dijkstra(start, end, w)
851 return f.PathTo(end, nil), dist[end]
852 }
853
854 // tent implements container/heap
855 func (t tent) Len() int { return len(t) }
856 func (t tent) Less(i, j int) bool { return t[i].dist < t[j].dist }
857 func (t tent) Swap(i, j int) {
858 t[i], t[j] = t[j], t[i]
859 t[i].fx = i
860 t[j].fx = j
861 }
862 func (s *tent) Push(x interface{}) {
863 nd := x.(*tentResult)
864 nd.fx = len(*s)
865 *s = append(*s, nd)
866 }
867 func (s *tent) Pop() interface{} {
868 t := *s
869 last := len(t) - 1
870 *s = t[:last]
871 return t[last]
872 }
873
874 type tentResult struct {
875 dist float64 // tentative distance, sum of arc weights
876 nx NI // slice index, "node id"
877 fx int // heap.Fix index
878 done bool
879 }
880
881 type tent []*tentResult