blob: 5f49e93561bb9611caea7bc0cdaa455141e527ec [file] [log] [blame] [edit]
// 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 (
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/internal/linear"
"gonum.org/v1/gonum/graph/traverse"
)
// BellmanFordFrom returns a shortest-path tree for a shortest path from u to all nodes in
// the graph g, or false indicating that a negative cycle exists in the graph. If the graph
// does not implement Weighted, UniformCost is used.
//
// If g is a graph.Graph, all nodes of the graph will be stored in the shortest-path
// tree, otherwise only nodes reachable from u will be stored.
//
// The time complexity of BellmanFordFrom is O(|V|.|E|).
func BellmanFordFrom(u graph.Node, g traverse.Graph) (path Shortest, ok bool) {
if h, ok := g.(graph.Graph); ok {
if h.Node(u.ID()) == nil {
return Shortest{from: u}, true
}
path = newShortestFrom(u, graph.NodesOf(h.Nodes()))
} else {
if g.From(u.ID()) == graph.Empty {
return Shortest{from: u}, true
}
path = newShortestFrom(u, []graph.Node{u})
}
path.dist[path.indexOf[u.ID()]] = 0
path.negCosts = make(map[negEdge]float64)
var weight Weighting
if wg, ok := g.(Weighted); ok {
weight = wg.Weight
} else {
weight = UniformCost(g)
}
// Queue to keep track which nodes need to be relaxed.
// Only nodes whose vertex distance changed in the previous iterations
// need to be relaxed again.
queue := newBellmanFordQueue(path.indexOf)
queue.enqueue(u)
// TODO(kortschak): Consider adding further optimisations
// from http://arxiv.org/abs/1111.5414.
var loops int64
for queue.len() != 0 {
u := queue.dequeue()
uid := u.ID()
j := path.indexOf[uid]
to := g.From(uid)
for to.Next() {
v := to.Node()
vid := v.ID()
k, ok := path.indexOf[vid]
if !ok {
k = path.add(v)
}
w, ok := weight(uid, vid)
if !ok {
panic("bellman-ford: unexpected invalid weight")
}
joint := path.dist[j] + w
if joint < path.dist[k] {
path.set(k, joint, j)
if !queue.has(vid) {
queue.enqueue(v)
}
}
}
// The maximum number of edges in the relaxed subgraph is |V_r| * (|V_r|-1).
// If the queue-loop has more iterations than the maximum number of edges
// it indicates that we have a negative cycle.
maxEdges := int64(len(path.nodes)) * int64(len(path.nodes)-1)
if loops > maxEdges {
path.hasNegativeCycle = true
return path, false
}
loops++
}
return path, true
}
// BellmanFordAllFrom returns a shortest-path tree for shortest paths from u to all nodes in
// the graph g, or false indicating that a negative cycle exists in the graph. If the graph
// does not implement Weighted, UniformCost is used.
//
// If g is a graph.Graph, all nodes of the graph will be stored in the shortest-path
// tree, otherwise only nodes reachable from u will be stored.
//
// The time complexity of BellmanFordAllFrom is O(|V|.|E|).
func BellmanFordAllFrom(u graph.Node, g traverse.Graph) (path ShortestAlts, ok bool) {
if h, ok := g.(graph.Graph); ok {
if h.Node(u.ID()) == nil {
return ShortestAlts{from: u}, true
}
path = newShortestAltsFrom(u, graph.NodesOf(h.Nodes()))
} else {
if g.From(u.ID()) == graph.Empty {
return ShortestAlts{from: u}, true
}
path = newShortestAltsFrom(u, []graph.Node{u})
}
path.dist[path.indexOf[u.ID()]] = 0
path.negCosts = make(map[negEdge]float64)
var weight Weighting
if wg, ok := g.(Weighted); ok {
weight = wg.Weight
} else {
weight = UniformCost(g)
}
// Queue to keep track which nodes need to be relaxed.
// Only nodes whose vertex distance changed in the previous iterations
// need to be relaxed again.
queue := newBellmanFordQueue(path.indexOf)
queue.enqueue(u)
// TODO(kortschak): Consider adding further optimisations
// from http://arxiv.org/abs/1111.5414.
var loops int64
for queue.len() != 0 {
u := queue.dequeue()
uid := u.ID()
j := path.indexOf[uid]
for _, v := range graph.NodesOf(g.From(uid)) {
vid := v.ID()
k, ok := path.indexOf[vid]
if !ok {
k = path.add(v)
}
w, ok := weight(uid, vid)
if !ok {
panic("bellman-ford: unexpected invalid weight")
}
joint := path.dist[j] + w
if joint < path.dist[k] {
path.set(k, joint, j)
if !queue.has(vid) {
queue.enqueue(v)
}
} else if joint == path.dist[k] {
path.addPath(k, j)
}
}
// The maximum number of edges in the relaxed subgraph is |V_r| * (|V_r|-1).
// If the queue-loop has more iterations than the maximum number of edges
// it indicates that we have a negative cycle.
maxEdges := int64(len(path.nodes)) * int64(len(path.nodes)-1)
if loops > maxEdges {
path.hasNegativeCycle = true
return path, false
}
loops++
}
return path, true
}
// bellmanFordQueue is a queue for the Queue-based Bellman-Ford algorithm.
type bellmanFordQueue struct {
// queue holds the nodes which need to be relaxed.
queue linear.NodeQueue
// onQueue keeps track whether a node is on the queue or not.
onQueue []bool
// indexOf contains a mapping holding the id of a node with its index in the onQueue array.
indexOf map[int64]int
}
// enqueue adds a node to the bellmanFordQueue.
func (q *bellmanFordQueue) enqueue(n graph.Node) {
i, ok := q.indexOf[n.ID()]
switch {
case !ok:
panic("bellman-ford: unknown node")
case i < len(q.onQueue):
if q.onQueue[i] {
panic("bellman-ford: already queued")
}
case i == len(q.onQueue):
q.onQueue = append(q.onQueue, false)
case i < cap(q.onQueue):
q.onQueue = q.onQueue[:i+1]
default:
q.onQueue = append(q.onQueue, make([]bool, i-len(q.onQueue)+1)...)
}
q.onQueue[i] = true
q.queue.Enqueue(n)
}
// dequeue returns the first value of the bellmanFordQueue.
func (q *bellmanFordQueue) dequeue() graph.Node {
n := q.queue.Dequeue()
q.onQueue[q.indexOf[n.ID()]] = false
return n
}
// len returns the number of nodes in the bellmanFordQueue.
func (q *bellmanFordQueue) len() int { return q.queue.Len() }
// has returns whether a node with the given id is in the queue.
func (q bellmanFordQueue) has(id int64) bool {
idx, ok := q.indexOf[id]
if !ok || idx >= len(q.onQueue) {
return false
}
return q.onQueue[idx]
}
// newBellmanFordQueue creates a new bellmanFordQueue.
func newBellmanFordQueue(indexOf map[int64]int) bellmanFordQueue {
return bellmanFordQueue{
onQueue: make([]bool, len(indexOf)),
indexOf: indexOf,
}
}