search

package
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jun 18, 2015 License: Apache-2.0 Imports: 7 Imported by: 0

Documentation

Index

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

func BreadthFirstSearch(start, goal graph.Node, g graph.Graph) ([]graph.Node, int)

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

func DepthFirstSearch(start, goal graph.Node, g graph.Graph) []graph.Node

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

func Dominators(start graph.Node, g graph.Graph) map[int]Set

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

func IsPath(path []graph.Node, g graph.Graph) bool

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

func NullHeuristic(_, _ graph.Node) float64

An admissible, consistent heuristic that won't speed up computation time at all.

func PostDominators

func PostDominators(end graph.Node, g graph.Graph) map[int]Set

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

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

func Tarjan(g graph.Graph) [][]graph.Node

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

func UniformCost(e graph.Edge) float64

Assumes all edges in the graph have the same weight (including edges that don't exist!)

Types

type AllPathFunc

type AllPathFunc func(start, goal graph.Node) (path [][]graph.Node, cost float64, err error)

Finds all shortest paths between start and goal

type PathFunc

type PathFunc func(start, goal graph.Node) (path []graph.Node, cost float64, err error)

Finds one path between start and goal, which it finds is arbitrary

type Set

type Set map[int]graph.Node

A set is a set of nodes keyed in their integer identifiers.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL