Documentation
¶
Index ¶
- func AStar(start, goal graph.Node, g graph.Graph, cost graph.CostFunc, ...) (path []graph.Node, pathCost float64, nodesExpanded int)
- func BellmanFord(source graph.Node, g graph.Graph, cost graph.CostFunc) (paths map[int][]graph.Node, costs map[int]float64, err error)
- func BreadthFirstSearch(start, goal graph.Node, g graph.Graph) ([]graph.Node, int)
- func CopyDirectedGraph(dst graph.MutableDirectedGraph, src graph.DirectedGraph)
- func CopyUndirectedGraph(dst graph.MutableGraph, src graph.Graph)
- func DepthFirstSearch(start, goal graph.Node, g graph.Graph) []graph.Node
- func Dijkstra(source graph.Node, g graph.Graph, cost graph.CostFunc) (paths map[int][]graph.Node, costs map[int]float64)
- func Dominators(start graph.Node, g graph.Graph) map[int]Set
- func FloydWarshall(g graph.CrunchGraph, cost graph.CostFunc) (AllPathFunc, PathFunc)
- func IsPath(path []graph.Node, g graph.Graph) bool
- func Johnson(g graph.Graph, cost graph.CostFunc) (nodePaths map[int]map[int][]graph.Node, nodeCosts map[int]map[int]float64, ...)
- func Kruskal(dst graph.MutableGraph, g graph.EdgeListGraph, cost graph.CostFunc)
- func NullHeuristic(_, _ graph.Node) float64
- func PostDominators(end graph.Node, g graph.Graph) map[int]Set
- func Prim(dst graph.MutableGraph, g graph.EdgeListGraph, cost graph.CostFunc)
- func Tarjan(g graph.Graph) [][]graph.Node
- func UniformCost(e graph.Edge) float64
- type AllPathFunc
- type PathFunc
- type Set
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AStar ¶
func AStar(start, goal graph.Node, g graph.Graph, cost graph.CostFunc, heuristicCost graph.HeuristicCostFunc) (path []graph.Node, pathCost float64, nodesExpanded int)
Returns an ordered list consisting of the nodes between start and goal. The path will be the shortest path assuming the function heuristicCost is admissible. The second return value is the cost, and the third is the number of nodes expanded while searching (useful info for tuning heuristics). Negative Costs will cause bad things to happen, as well as negative heuristic estimates.
A heuristic is admissible if, for any node in the graph, the heuristic estimate of the cost between the node and the goal is less than or set to the true cost.
Performance may be improved by providing a consistent heuristic (though one is not needed to find the optimal path), a heuristic is consistent if its value for a given node is less than (or equal to) the actual cost of reaching its neighbors + the heuristic estimate for the neighbor itself. You can force consistency by making your HeuristicCost function return max(NonConsistentHeuristicCost(neighbor,goal), NonConsistentHeuristicCost(self,goal) - Cost(self,neighbor)). If there are multiple neighbors, take the max of all of them.
Cost and HeuristicCost take precedence for evaluating cost/heuristic distance. If one is not present (i.e. nil) the function will check the graph's interface for the respective interface: Coster for Cost and HeuristicCoster for HeuristicCost. If the correct one is present, it will use the graph's function for evaluation.
Finally, if neither the argument nor the interface is present, the function will assume UniformCost for Cost and NullHeuristic for HeuristicCost.
To run Uniform Cost Search, run A* with the NullHeuristic.
To run Breadth First Search, run A* with both the NullHeuristic and UniformCost (or any cost function that returns a uniform positive value.)
func BellmanFord ¶
func BellmanFord(source graph.Node, g graph.Graph, cost graph.CostFunc) (paths map[int][]graph.Node, costs map[int]float64, err error)
The Bellman-Ford Algorithm is the same as Dijkstra's Algorithm with a key difference. They both take a single source and find the shortest path to every other (reachable) node in the graph. Bellman-Ford, however, will detect negative edge loops and abort if one is present. A negative edge loop occurs when there is a cycle in the graph such that it can take an edge with a negative cost over and over. A -(-2)> B -(2)> C isn't a loop because A->B can only be taken once, but A<-(-2)->B-(2)>C is one because A and B have a bi-directional edge, and algorithms like Dijkstra's will infinitely flail between them getting progressively lower costs.
That said, if you do not have a negative edge weight, use Dijkstra's Algorithm instead, because it's faster.
Like Dijkstra's, along with the costs this implementation will also construct all the paths for you. In addition, it has a third return value which will be true if the algorithm was aborted due to the presence of a negative edge weight cycle.
func BreadthFirstSearch ¶
BreadthFirstSearch finds a path with a minimal number of edges from from start to goal.
BreadthFirstSearch returns the path found and the number of nodes visited in the search. The returned path is nil if no path exists.
Example ¶
package main
import (
"fmt"
"github.com/gonum/graph/concrete"
"github.com/gonum/graph/search"
)
func main() {
g := concrete.NewDirectedGraph()
var n0, n1, n2, n3 concrete.Node = 0, 1, 2, 3
g.AddDirectedEdge(concrete.Edge{n0, n1}, 1)
g.AddDirectedEdge(concrete.Edge{n0, n2}, 1)
g.AddDirectedEdge(concrete.Edge{n2, n3}, 1)
path, v := search.BreadthFirstSearch(n0, n3, g)
fmt.Println("path:", path)
fmt.Println("nodes visited:", v)
}
Output: path: [0 2 3] nodes visited: 4
func CopyDirectedGraph ¶
func CopyDirectedGraph(dst graph.MutableDirectedGraph, src graph.DirectedGraph)
Copies a graph into the destination; maintaining all node IDs. The destination need not be empty, though overlapping node IDs and conflicting edges will overwrite existing data.
func CopyUndirectedGraph ¶
func CopyUndirectedGraph(dst graph.MutableGraph, src graph.Graph)
Copies a graph into the destination; maintaining all node IDs. The destination need not be empty, though overlapping node IDs and conflicting edges will overwrite existing data.
func DepthFirstSearch ¶
Expands the first node it sees trying to find the destination. Depth First Search is *not* guaranteed to find the shortest path, however, if a path exists DFS is guaranteed to find it (provided you don't find a way to implement a Graph with an infinite depth.)
func Dijkstra ¶
func Dijkstra(source graph.Node, g graph.Graph, cost graph.CostFunc) (paths map[int][]graph.Node, costs map[int]float64)
Dijkstra's Algorithm is essentially a goalless Uniform Cost Search. That is, its results are roughly equivalent to running A* with the Null Heuristic from a single node to every other node in the graph -- though it's a fair bit faster because running A* in that way will recompute things it's already computed every call. Note that you won't necessarily get the same path you would get for A*, but the cost is guaranteed to be the same (that is, if multiple shortest paths exist, you may get a different shortest path).
Like A*, Dijkstra's Algorithm likely won't run correctly with negative edge weights -- use Bellman-Ford for that instead.
Dijkstra's algorithm usually only returns a cost map, however, since the data is available this version will also reconstruct the path to every node.
func Dominators ¶
A dominates B if and only if the only path through B travels through A.
This returns all possible dominators for all nodes, it does not prune for strict dominators, immediate dominators etc.
func FloydWarshall ¶
func FloydWarshall(g graph.CrunchGraph, cost graph.CostFunc) (AllPathFunc, PathFunc)
This function returns two functions: one that will generate all shortest paths between two nodes with ids i and j, and one that will generate just one path.
This algorithm requires the CrunchGraph interface which means it only works on graphs with dense node ids since it uses an adjacency matrix.
This algorithm isn't blazingly fast, but is relatively fast for the domain. It runs at O((number of vertices)^3) in best, worst, and average case, and successfully computes the cost between all pairs of vertices.
This function operates slightly differently from the others for convenience -- rather than generating paths and returning them to you, it gives you the option of calling one of two functions for each start/goal pair you need info for. One will return the path, cost, or an error if no path exists.
The other will return the cost and an error if no path exists, but it will also return ALL possible shortest paths between start and goal. This is not too much more expensive than generating one path, but it does obviously increase with the number of paths.
func IsPath ¶
IsPath returns true for a connected path within a graph.
IsPath returns true if, starting at path[0] and ending at path[len(path)-1], all nodes between are valid neighbors. That is, for each element path[i], path[i+1] is a valid successor.
As special cases, IsPath returns true for a nil or zero length path, and for a path of length 1 (only one node) but only if the node listed in path exists within the graph.
Graph must be non-nil.
func Johnson ¶
func Johnson(g graph.Graph, cost graph.CostFunc) (nodePaths map[int]map[int][]graph.Node, nodeCosts map[int]map[int]float64, err error)
Johnson's Algorithm generates the lowest cost path between every pair of nodes in the graph.
It makes use of Bellman-Ford and a dummy graph. It creates a dummy node containing edges with a cost of zero to every other node. Then it runs Bellman-Ford with this dummy node as the source. It then modifies the all the nodes' edge weights (which gets rid of all negative weights).
Finally, it removes the dummy node and runs Dijkstra's starting at every node.
This algorithm is fairly slow. Its purpose is to remove negative edge weights to allow Dijkstra's to function properly. It's probably not worth it to run this algorithm if you have all non-negative edge weights. Also note that this implementation copies your whole graph into a GonumGraph (so it can add/remove the dummy node and edges and reweight the graph).
Its return values are, in order: a map from the source node, to the destination node, to the path between them; a map from the source node, to the destination node, to the cost of the path between them; and a bool that is true if Bellman-Ford detected a negative edge weight cycle -- thus causing it (and this algorithm) to abort (if aborted is true, both maps will be nil).
func Kruskal ¶
func Kruskal(dst graph.MutableGraph, g graph.EdgeListGraph, cost graph.CostFunc)
Generates a minimum spanning tree for a graph using discrete.DisjointSet.
As with other algorithms with Cost, the precedence goes Argument > Interface > UniformCost.
The destination must be empty (or at least disjoint with the node IDs of the input)
func NullHeuristic ¶
An admissible, consistent heuristic that won't speed up computation time at all.
func PostDominators ¶
A Postdominates B if and only if all paths from B travel through A.
This returns all possible post-dominators for all nodes, it does not prune for strict postdominators, immediate postdominators etc.
func Prim ¶
func Prim(dst graph.MutableGraph, g graph.EdgeListGraph, cost graph.CostFunc)
Generates a minimum spanning tree with sets.
As with other algorithms that use Cost, the order of precedence is Argument > Interface > UniformCost.
The destination must be empty (or at least disjoint with the node IDs of the input)
func Tarjan ¶
Also known as Tarjan's Strongly Connected Components Algorithm. This returns all the strongly connected components in the graph.
A strongly connected component of a graph is a set of vertices where it's possible to reach any vertex in the set from any other (meaning there's a cycle between them.)
Generally speaking, a directed graph where the number of strongly connected components is equal to the number of nodes is acyclic, unless you count reflexive edges as a cycle (which requires only a little extra testing.)
An undirected graph should end up with as many SCCs as there are "islands" (or subgraphs) of connections, meaning having more than one strongly connected component implies that your graph is not fully connected.
func UniformCost ¶
Assumes all edges in the graph have the same weight (including edges that don't exist!)
Types ¶
type AllPathFunc ¶
Finds all shortest paths between start and goal
Source Files