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
|
// 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"
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/traverse"
)
// Weighted is a weighted graph. It is a subset of graph.Weighted.
type Weighted interface {
// Weight returns the weight for the edge between
// x and y with IDs xid and yid if Edge(xid, yid)
// returns a non-nil Edge.
// If x and y are the same node or there is no
// joining edge between the two nodes the weight
// value returned is implementation dependent.
// Weight returns true if an edge exists between
// x and y or if x and y have the same ID, false
// otherwise.
Weight(xid, yid int64) (w float64, ok bool)
}
// Weighting is a mapping between a pair of nodes and a weight. It follows the
// semantics of the Weighter interface.
type Weighting func(xid, yid int64) (w float64, ok bool)
// UniformCost returns a Weighting that returns an edge cost of 1 for existing
// edges, zero for node identity and Inf for otherwise absent edges.
func UniformCost(g traverse.Graph) Weighting {
return func(xid, yid int64) (w float64, ok bool) {
if xid == yid {
return 0, true
}
if e := g.Edge(xid, yid); e != nil {
return 1, true
}
return math.Inf(1), false
}
}
// Heuristic returns an estimate of the cost of travelling between two nodes.
type Heuristic func(x, y graph.Node) float64
// HeuristicCoster wraps the HeuristicCost method. A graph implementing the
// interface provides a heuristic between any two given nodes.
type HeuristicCoster interface {
HeuristicCost(x, y graph.Node) float64
}
|
