blob: db6bb03f0a4ddf6b747d73476882f816ed70d418 [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"
"golang.org/x/exp/rand"
"gonum.org/v1/gonum/floats/scalar"
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/internal/ordered"
"gonum.org/v1/gonum/graph/internal/set"
"gonum.org/v1/gonum/mat"
)
// Shortest is a shortest-path tree created by the BellmanFordFrom, DijkstraFrom
// or AStar single-source shortest path functions.
type Shortest struct {
// from holds the source node given to
// the function that returned the
// Shortest value.
from graph.Node
// nodes hold the nodes of the analysed
// graph.
nodes []graph.Node
// indexOf contains a mapping between
// the id-dense representation of the
// graph and the potentially id-sparse
// nodes held in nodes.
indexOf map[int64]int
// dist and next represent the shortest
// paths between nodes.
//
// Indices into dist and next are
// mapped through indexOf.
//
// dist contains the distances
// from the from node for each
// node in the graph.
dist []float64
// next contains the shortest-path
// tree of the graph. The index is a
// linear mapping of to-dense-id.
next []int
// hasNegativeCycle indicates
// whether the Shortest includes
// a negative cycle. This should
// be set by the function that
// returned the Shortest value.
hasNegativeCycle bool
// negCosts holds negative costs
// between pairs of nodes to report
// negative cycles.
// negCosts must be initialised by
// routines that can handle negative
// edge weights.
negCosts map[negEdge]float64
}
// newShortestFrom returns a shortest path tree for paths from u
// initialised with the given nodes. The nodes held by the returned
// Shortest may be lazily added.
func newShortestFrom(u graph.Node, nodes []graph.Node) Shortest {
indexOf := make(map[int64]int, len(nodes))
uid := u.ID()
for i, n := range nodes {
indexOf[n.ID()] = i
if n.ID() == uid {
u = n
}
}
p := Shortest{
from: u,
nodes: nodes,
indexOf: indexOf,
dist: make([]float64, len(nodes)),
next: make([]int, len(nodes)),
}
for i := range nodes {
p.dist[i] = math.Inf(1)
p.next[i] = -1
}
p.dist[indexOf[uid]] = 0
return p
}
// add adds a node to the Shortest, initialising its stored index and returning, and
// setting the distance and position as unconnected. add will panic if the node is
// already present.
func (p *Shortest) add(u graph.Node) int {
uid := u.ID()
if _, exists := p.indexOf[uid]; exists {
panic("shortest: adding existing node")
}
idx := len(p.nodes)
p.indexOf[uid] = idx
p.nodes = append(p.nodes, u)
p.dist = append(p.dist, math.Inf(1))
p.next = append(p.next, -1)
return idx
}
// set sets the weight of the path from the node in p.nodes indexed by mid to the node
// indexed by to.
func (p Shortest) set(to int, weight float64, mid int) {
p.dist[to] = weight
p.next[to] = mid
if weight < 0 {
e := negEdge{from: mid, to: to}
c, ok := p.negCosts[e]
if !ok {
p.negCosts[e] = weight
} else if weight < c {
// The only ways that we can have a new weight that is
// lower than the previous weight is if either the edge
// has already been traversed in a negative cycle, or
// the edge is reachable from a negative cycle.
// Either way the reported path is returned with a
// negative infinite path weight.
p.negCosts[e] = math.Inf(-1)
}
}
}
// From returns the starting node of the paths held by the Shortest.
func (p Shortest) From() graph.Node { return p.from }
// WeightTo returns the weight of the minimum path to v. If the path to v includes
// a negative cycle, the returned weight will not reflect the true path weight.
func (p Shortest) WeightTo(vid int64) float64 {
to, toOK := p.indexOf[vid]
if !toOK {
return math.Inf(1)
}
return p.dist[to]
}
// To returns a shortest path to v and the weight of the path. If the path
// to v includes a negative cycle, one pass through the cycle will be included
// in path, but any path leading into the negative cycle will be lost, and
// weight will be returned as -Inf.
func (p Shortest) To(vid int64) (path []graph.Node, weight float64) {
to, toOK := p.indexOf[vid]
if !toOK || math.IsInf(p.dist[to], 1) {
return nil, math.Inf(1)
}
from := p.indexOf[p.from.ID()]
path = []graph.Node{p.nodes[to]}
weight = math.Inf(1)
if p.hasNegativeCycle {
seen := make(set.Ints)
seen.Add(from)
for to != from {
next := p.next[to]
if math.IsInf(p.negCosts[negEdge{from: next, to: to}], -1) {
weight = math.Inf(-1)
}
if seen.Has(to) {
break
}
seen.Add(to)
path = append(path, p.nodes[next])
to = next
}
} else {
n := len(p.nodes)
for to != from {
to = p.next[to]
path = append(path, p.nodes[to])
if n < 0 {
panic("path: unexpected negative cycle")
}
n--
}
}
ordered.Reverse(path)
return path, math.Min(weight, p.dist[p.indexOf[vid]])
}
// ShortestAlts is a shortest-path tree created by the BellmanFordAllFrom or DijkstraAllFrom
// single-source shortest path functions.
type ShortestAlts struct {
// from holds the source node given to
// the function that returned the
// ShortestAlts value.
from graph.Node
// nodes hold the nodes of the analysed
// graph.
nodes []graph.Node
// indexOf contains a mapping between
// the id-dense representation of the
// graph and the potentially id-sparse
// nodes held in nodes.
indexOf map[int64]int
// dist and next represent the shortest
// paths between nodes.
//
// Indices into dist and next are
// mapped through indexOf.
//
// dist contains the distances
// from the from node for each
// node in the graph.
dist []float64
// next contains the shortest-path
// tree of the graph. The index is a
// linear mapping of to-dense-id.
next [][]int
// hasNegativeCycle indicates
// whether the ShortestAlts includes
// a negative cycle. This should
// be set by the function that
// returned the ShortestAlts value.
hasNegativeCycle bool
// negCosts holds negative costs
// between pairs of nodes to report
// negative cycles.
// negCosts must be initialised by
// routines that can handle negative
// edge weights.
negCosts map[negEdge]float64
}
// newShortestAltsFrom returns a shortest path tree for all paths from u
// initialised with the given nodes. The nodes held by the returned
// Shortest may be lazily added.
func newShortestAltsFrom(u graph.Node, nodes []graph.Node) ShortestAlts {
indexOf := make(map[int64]int, len(nodes))
uid := u.ID()
for i, n := range nodes {
indexOf[n.ID()] = i
if n.ID() == uid {
u = n
}
}
p := ShortestAlts{
from: u,
nodes: nodes,
indexOf: indexOf,
dist: make([]float64, len(nodes)),
next: make([][]int, len(nodes)),
}
for i := range nodes {
p.dist[i] = math.Inf(1)
p.next[i] = nil
}
p.dist[indexOf[uid]] = 0
return p
}
// add adds a node to the ShortestAlts, initialising its stored index and returning, and
// setting the distance and position as unconnected. add will panic if the node is
// already present.
func (p *ShortestAlts) add(u graph.Node) int {
uid := u.ID()
if _, exists := p.indexOf[uid]; exists {
panic("shortest: adding existing node")
}
idx := len(p.nodes)
p.indexOf[uid] = idx
p.nodes = append(p.nodes, u)
p.dist = append(p.dist, math.Inf(1))
p.next = append(p.next, nil)
return idx
}
// set sets the weight of the path from the node in p.nodes indexed by mid to the node
// indexed by to.
func (p ShortestAlts) set(to int, weight float64, mid int) {
p.dist[to] = weight
p.next[to] = []int{mid}
if weight < 0 {
e := negEdge{from: mid, to: to}
c, ok := p.negCosts[e]
if !ok {
p.negCosts[e] = weight
} else if weight < c {
// The only ways that we can have a new weight that is
// lower than the previous weight is if either the edge
// has already been traversed in a negative cycle, or
// the edge is reachable from a negative cycle.
// Either way the reported path is returned with a
// negative infinite path weight.
p.negCosts[e] = math.Inf(-1)
}
}
}
// addPath adds a new path from the node in p.nodes indexed by mid to the node indexed
// by to. The weight of the path is expected to be the same as already existing paths
// between these nodes, but no check is made for this.
func (p ShortestAlts) addPath(to, mid int) {
// These are likely to be rare, so just loop over collisions.
for _, v := range p.next[to] {
if mid == v {
return
}
}
p.next[to] = append(p.next[to], mid)
}
// From returns the starting node of the paths held by the ShortestAlts.
func (p ShortestAlts) From() graph.Node { return p.from }
// WeightTo returns the weight of the minimum path to v. If the path to v includes
// a negative cycle, the returned weight will not reflect the true path weight.
func (p ShortestAlts) WeightTo(vid int64) float64 {
to, toOK := p.indexOf[vid]
if !toOK {
return math.Inf(1)
}
return p.dist[to]
}
// To returns a shortest path to v and the weight of the path. If more than
// one shortest path exists between u and v, a randomly chosen path will be
// returned and unique is returned false. If a cycle with zero weight exists
// in the path, it will not be included, but unique will be returned false.
// If the path to v includes a negative cycle, one pass through the cycle will
// be included in path, but any path leading into the negative cycle will be
// lost, and weight will be returned as -Inf.
func (p ShortestAlts) To(vid int64) (path []graph.Node, weight float64, unique bool) {
to, toOK := p.indexOf[vid]
if !toOK || math.IsInf(p.dist[to], 1) {
return nil, math.Inf(1), false
}
from := p.indexOf[p.from.ID()]
unique = true
path = []graph.Node{p.nodes[to]}
if p.hasNegativeCycle {
weight = math.Inf(1)
seen := make(set.Ints)
seen.Add(from)
for to != from {
c := p.next[to]
var next int
if len(c) != 1 {
unique = false
next = c[rand.Intn(len(c))]
} else {
next = c[0]
}
if math.IsInf(p.negCosts[negEdge{from: next, to: to}], -1) {
weight = math.Inf(-1)
unique = false
}
if seen.Has(to) {
break
}
seen.Add(to)
path = append(path, p.nodes[next])
to = next
}
weight = math.Min(weight, p.dist[p.indexOf[vid]])
} else {
seen := make([]int, len(p.nodes))
for i := range seen {
seen[i] = -1
}
seen[to] = 0
var next int
for from != to {
c := p.next[to]
if len(c) != 1 {
unique = false
next = c[rand.Intn(len(c))]
} else {
next = c[0]
}
if seen[next] >= 0 {
path = path[:seen[next]]
}
seen[next] = len(path)
path = append(path, p.nodes[next])
to = next
}
weight = p.dist[p.indexOf[vid]]
}
ordered.Reverse(path)
return path, weight, unique
}
// AllTo returns all shortest paths to v and the weight of the paths. Paths
// containing zero-weight cycles are not returned. If a negative cycle exists between
// u and v, paths is returned nil and weight is returned as -Inf.
func (p ShortestAlts) AllTo(vid int64) (paths [][]graph.Node, weight float64) {
from := p.indexOf[p.from.ID()]
to, toOK := p.indexOf[vid]
if !toOK || len(p.next[to]) == 0 {
if p.from.ID() == vid {
return [][]graph.Node{{p.nodes[from]}}, 0
}
return nil, math.Inf(1)
}
_, weight, unique := p.To(vid)
if math.IsInf(weight, -1) && !unique {
return nil, math.Inf(-1)
}
seen := make([]bool, len(p.nodes))
paths = p.allTo(from, to, seen, []graph.Node{p.nodes[to]}, nil)
weight = p.dist[to]
return paths, weight
}
// allTo recursively constructs a slice of paths extending from the node
// indexed into p.nodes by from to the node indexed by to. len(seen) must match
// the number of nodes held by the receiver. The path parameter is the current
// working path and the results are written into paths.
func (p ShortestAlts) allTo(from, to int, seen []bool, path []graph.Node, paths [][]graph.Node) [][]graph.Node {
seen[to] = true
if from == to {
if path == nil {
return paths
}
ordered.Reverse(path)
return append(paths, path)
}
first := true
for _, to := range p.next[to] {
if seen[to] {
continue
}
if first {
path = append([]graph.Node(nil), path...)
first = false
}
path = path[:len(path):len(path)]
paths = p.allTo(from, to, append([]bool(nil), seen...), append(path, p.nodes[to]), paths)
}
return paths
}
// negEdge is a key into the negative costs map used by Shortest and ShortestAlts.
type negEdge struct{ from, to int }
// AllShortest is a shortest-path tree created by the DijkstraAllPaths, FloydWarshall
// or JohnsonAllPaths all-pairs shortest paths functions.
type AllShortest struct {
// nodes hold the nodes of the analysed
// graph.
nodes []graph.Node
// indexOf contains a mapping between
// the id-dense representation of the
// graph and the potentially id-sparse
// nodes held in nodes.
indexOf map[int64]int
// dist, next and forward represent
// the shortest paths between nodes.
//
// Indices into dist and next are
// mapped through indexOf.
//
// dist contains the pairwise
// distances between nodes.
//
// Internally, edges on negative
// cycles are given a special NaN
// weight, NaN(0xdefaced).
// This is returned to the user as
// -Inf. This approach allows -Inf
// weight edges on simple paths to be
// distinguished from -Inf weight
// paths that contain negative cycles.
// The distinction is visible to the
// user through whether then path
// returned with a -Inf weight is
// nil or contains a set of nodes.
dist *mat.Dense
// next contains the shortest-path
// tree of the graph. The first index
// is a linear mapping of from-dense-id
// and to-dense-id, to-major with a
// stride equal to len(nodes); the
// slice indexed to is the list of
// intermediates leading from the 'from'
// node to the 'to' node represented
// by dense id.
// The interpretation of next is
// dependent on the state of forward.
next [][]int
// forward indicates the direction of
// path reconstruction. Forward
// reconstruction is used for Floyd-
// Warshall and reverse is used for
// Dijkstra.
forward bool
}
var (
// defaced is NaN(0xdefaced) used as a marker for -Inf weight edges
// within paths containing negative cycles. Routines marking these
// edges should use this value.
defaced = scalar.NaNWith(0xdefaced)
// defacedBits is the bit pattern we look for in AllShortest to
// identify the edges.
defacedBits = math.Float64bits(defaced)
)
// newAllShortest returns an all-pairs shortest path forest for paths with the
// given nodes. The forward flag indicates whether the path reconstruction is
// performed in the forward (Floyd-Warshall) or reverse (Dijkstra/Johnson's) order.
func newAllShortest(nodes []graph.Node, forward bool) AllShortest {
if len(nodes) == 0 {
return AllShortest{}
}
indexOf := make(map[int64]int, len(nodes))
for i, n := range nodes {
indexOf[n.ID()] = i
}
dist := make([]float64, len(nodes)*len(nodes))
for i := range dist {
dist[i] = math.Inf(1)
}
return AllShortest{
nodes: nodes,
indexOf: indexOf,
dist: mat.NewDense(len(nodes), len(nodes), dist),
next: make([][]int, len(nodes)*len(nodes)),
forward: forward,
}
}
// at returns a slice of node indexes into p.nodes for nodes that are mid points
// between nodes indexed by from and to.
func (p AllShortest) at(from, to int) (mid []int) {
return p.next[from+to*len(p.nodes)]
}
// set sets the weights of paths between node indexes into p.nodes for from and to
// passing through the nodes indexed by mid.
func (p AllShortest) set(from, to int, weight float64, mid ...int) {
p.dist.Set(from, to, weight)
p.next[from+to*len(p.nodes)] = append(p.next[from+to*len(p.nodes)][:0], mid...)
}
// add adds paths between node indexed in p.nodes by from and to passing through
// the nodes indexed by mid.
func (p AllShortest) add(from, to int, mid ...int) {
loop: // These are likely to be rare, so just loop over collisions.
for _, k := range mid {
for _, v := range p.next[from+to*len(p.nodes)] {
if k == v {
continue loop
}
}
p.next[from+to*len(p.nodes)] = append(p.next[from+to*len(p.nodes)], k)
}
}
// Weight returns the weight of the minimum path between u and v.
func (p AllShortest) Weight(uid, vid int64) float64 {
from, fromOK := p.indexOf[uid]
to, toOK := p.indexOf[vid]
if !fromOK || !toOK {
return math.Inf(1)
}
w := p.dist.At(from, to)
if math.Float64bits(w) == defacedBits {
return math.Inf(-1)
}
return w
}
// Between returns a shortest path from u to v and the weight of the path. If more than
// one shortest path exists between u and v, a randomly chosen path will be returned and
// unique is returned false. If a cycle with zero weight exists in the path, it will not
// be included, but unique will be returned false. If a negative cycle exists on the path
// from u to v, path will be returned nil, weight will be -Inf and unique will be false.
func (p AllShortest) Between(uid, vid int64) (path []graph.Node, weight float64, unique bool) {
from, fromOK := p.indexOf[uid]
to, toOK := p.indexOf[vid]
if !fromOK || !toOK || len(p.at(from, to)) == 0 {
if uid == vid {
if !fromOK {
return []graph.Node{node(uid)}, 0, true
}
return []graph.Node{p.nodes[from]}, 0, true
}
return nil, math.Inf(1), false
}
weight = p.dist.At(from, to)
if math.Float64bits(weight) == defacedBits {
return nil, math.Inf(-1), false
}
seen := make([]int, len(p.nodes))
for i := range seen {
seen[i] = -1
}
var n graph.Node
if p.forward {
n = p.nodes[from]
seen[from] = 0
} else {
n = p.nodes[to]
seen[to] = 0
}
path = []graph.Node{n}
unique = true
var next int
for from != to {
c := p.at(from, to)
if len(c) != 1 {
unique = false
next = c[rand.Intn(len(c))]
} else {
next = c[0]
}
if seen[next] >= 0 {
path = path[:seen[next]]
}
seen[next] = len(path)
path = append(path, p.nodes[next])
if p.forward {
from = next
} else {
to = next
}
}
if !p.forward {
ordered.Reverse(path)
}
return path, weight, unique
}
// AllBetween returns all shortest paths from u to v and the weight of the paths. Paths
// containing zero-weight cycles are not returned. If a negative cycle exists between
// u and v, paths is returned nil and weight is returned as -Inf.
func (p AllShortest) AllBetween(uid, vid int64) (paths [][]graph.Node, weight float64) {
from, fromOK := p.indexOf[uid]
to, toOK := p.indexOf[vid]
if !fromOK || !toOK || len(p.at(from, to)) == 0 {
if uid == vid {
if !fromOK {
return [][]graph.Node{{node(uid)}}, 0
}
return [][]graph.Node{{p.nodes[from]}}, 0
}
return nil, math.Inf(1)
}
weight = p.dist.At(from, to)
if math.Float64bits(weight) == defacedBits {
return nil, math.Inf(-1)
}
var n graph.Node
if p.forward {
n = p.nodes[from]
} else {
n = p.nodes[to]
}
seen := make([]bool, len(p.nodes))
paths = p.allBetween(from, to, seen, []graph.Node{n}, nil)
return paths, weight
}
// allBetween recursively constructs a slice of paths extending from the node
// indexed into p.nodes by from to the node indexed by to. len(seen) must match
// the number of nodes held by the receiver. The path parameter is the current
// working path and the results are written into paths.
func (p AllShortest) allBetween(from, to int, seen []bool, path []graph.Node, paths [][]graph.Node) [][]graph.Node {
if p.forward {
seen[from] = true
} else {
seen[to] = true
}
if from == to {
if path == nil {
return paths
}
if !p.forward {
ordered.Reverse(path)
}
return append(paths, path)
}
first := true
for _, n := range p.at(from, to) {
if seen[n] {
continue
}
if first {
path = append([]graph.Node(nil), path...)
first = false
}
if p.forward {
from = n
} else {
to = n
}
path = path[:len(path):len(path)]
paths = p.allBetween(from, to, append([]bool(nil), seen...), append(path, p.nodes[n]), paths)
}
return paths
}
type node int64
func (n node) ID() int64 { return int64(n) }