blob: cf96bc4e8ce455cbf4525e6a888c14f938a94e08 [file] [log] [blame]
// Copyright ©2015 The gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package path
import (
"math"
"math/rand"
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/simple"
)
// JohnsonAllPaths returns a shortest-path tree for shortest paths in the graph g.
// If the graph does not implement graph.Weighter, UniformCost is used.
//
// The time complexity of JohnsonAllPaths is O(|V|.|E|+|V|^2.log|V|).
func JohnsonAllPaths(g graph.Graph) (paths AllShortest, ok bool) {
jg := johnsonWeightAdjuster{
g: g,
from: g.From,
edgeTo: g.Edge,
}
if wg, ok := g.(graph.Weighter); ok {
jg.weight = wg.Weight
} else {
jg.weight = UniformCost(g)
}
paths = newAllShortest(g.Nodes(), false)
sign := int64(-1)
for {
// Choose a random node ID until we find
// one that is not in g.
jg.q = sign * rand.Int63()
if _, exists := paths.indexOf[jg.q]; !exists {
break
}
sign *= -1
}
jg.bellmanFord = true
jg.adjustBy, ok = BellmanFordFrom(johnsonGraphNode(jg.q), jg)
if !ok {
return paths, false
}
jg.bellmanFord = false
dijkstraAllPaths(jg, paths)
for i, u := range paths.nodes {
hu := jg.adjustBy.WeightTo(u)
for j, v := range paths.nodes {
if i == j {
continue
}
hv := jg.adjustBy.WeightTo(v)
paths.dist.Set(i, j, paths.dist.At(i, j)-hu+hv)
}
}
return paths, ok
}
type johnsonWeightAdjuster struct {
q int64
g graph.Graph
from func(graph.Node) []graph.Node
edgeTo func(graph.Node, graph.Node) graph.Edge
weight Weighting
bellmanFord bool
adjustBy Shortest
}
var (
// johnsonWeightAdjuster has the behaviour
// of a directed graph, but we don't need
// to be explicit with the type since it
// is not exported.
_ graph.Graph = johnsonWeightAdjuster{}
_ graph.Weighter = johnsonWeightAdjuster{}
)
func (g johnsonWeightAdjuster) Has(n graph.Node) bool {
if g.bellmanFord && n.ID() == g.q {
return true
}
return g.g.Has(n)
}
func (g johnsonWeightAdjuster) Nodes() []graph.Node {
if g.bellmanFord {
return append(g.g.Nodes(), johnsonGraphNode(g.q))
}
return g.g.Nodes()
}
func (g johnsonWeightAdjuster) From(n graph.Node) []graph.Node {
if g.bellmanFord && n.ID() == g.q {
return g.g.Nodes()
}
return g.from(n)
}
func (g johnsonWeightAdjuster) Edge(u, v graph.Node) graph.Edge {
if g.bellmanFord && u.ID() == g.q && g.g.Has(v) {
return simple.Edge{F: johnsonGraphNode(g.q), T: v}
}
return g.edgeTo(u, v)
}
func (g johnsonWeightAdjuster) Weight(x, y graph.Node) (w float64, ok bool) {
if g.bellmanFord {
switch g.q {
case x.ID():
return 0, true
case y.ID():
return math.Inf(1), false
default:
return g.weight(x, y)
}
}
w, ok = g.weight(x, y)
return w + g.adjustBy.WeightTo(x) - g.adjustBy.WeightTo(y), ok
}
func (johnsonWeightAdjuster) HasEdgeBetween(_, _ graph.Node) bool {
panic("path: unintended use of johnsonWeightAdjuster")
}
type johnsonGraphNode int64
func (n johnsonGraphNode) ID() int64 { return int64(n) }