path

package
v1.0.5 Latest Latest
Warning

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

Go to latest
Published: Aug 24, 2015 License: Apache-2.0 Imports: 8 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Dominators

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

PostDominatores returns all dominators for all nodes in g. It does not prune for strict post-dominators, immediate dominators etc.

A dominates B if and only if the only path through B travels through A.

func Kruskal

func Kruskal(dst graph.MutableUndirected, g EdgeListerGraph)

Kruskal generates a minimum spanning tree of g by greedy tree coalesence, placing the result in the destination. The destination is not cleared first.

func NullHeuristic

func NullHeuristic(_, _ graph.Node) float64

NullHeuristic is an admissible, consistent heuristic that will not speed up computation.

func PostDominators

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

PostDominatores returns all post-dominators for all nodes in g. It does not prune for strict post-dominators, immediate post-dominators etc.

A post-dominates B if and only if all paths from B travel through A.

func Prim

Prim generates a minimum spanning tree of g by greedy tree extension, placing the result in the destination. The destination is not cleared first.

Types

type AllShortest

type AllShortest struct {
	// contains filtered or unexported fields
}

AllShortest is a shortest-path tree created by the DijkstraAllPaths, FloydWarshall or JohnsonAllPaths all-pairs shortest paths functions.

func DijkstraAllPaths

func DijkstraAllPaths(g graph.Graph) (paths AllShortest)

DijkstraAllPaths returns a shortest-path tree for shortest paths in the graph g. If the graph does not implement graph.Weighter, graph.UniformCost is used. DijkstraAllPaths will panic if g has a negative edge weight.

The time complexity of DijkstrAllPaths is O(|V|.|E|+|V|^2.log|V|).

func FloydWarshall

func FloydWarshall(g graph.Graph) (paths AllShortest, ok bool)

FloydWarshall returns a shortest-path tree for the graph g or false indicating that a negative cycle exists in the graph. If the graph does not implement graph.Weighter, graph.UniformCost is used.

The time complexity of FloydWarshall is O(|V|^3).

func JohnsonAllPaths

func JohnsonAllPaths(g graph.Graph) (paths AllShortest, ok bool)

JohnsonAllPaths returns a shortest-path tree for shortest paths in the graph g. If the graph does not implement graph.Weighter, graph.UniformCost is used.

The time complexity of JohnsonAllPaths is O(|V|.|E|+|V|^2.log|V|).

func (AllShortest) AllBetween

func (p AllShortest) AllBetween(u, v graph.Node) (paths [][]graph.Node, weight float64)

AllBetween returns all shortest paths from u to v and the weight of the paths. Paths containing zero-weight cycles are not returned.

func (AllShortest) Between

func (p AllShortest) Between(u, v graph.Node) (path []graph.Node, weight float64, unique bool)

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.

func (AllShortest) Weight

func (p AllShortest) Weight(u, v graph.Node) float64

Weight returns the weight of the minimum path between u and v.

type EdgeListerGraph

type EdgeListerGraph interface {
	graph.Undirected
	Edges() []graph.Edge
}

EdgeListerGraph is an undirected graph than returns its complete set of edges.

type Heuristic

type Heuristic func(x, y graph.Node) float64

Heuristic returns an estimate of the cost of travelling between two nodes.

type HeuristicCoster

type HeuristicCoster interface {
	HeuristicCost(x, y graph.Node) float64
}

HeuristicCoster wraps the HeuristicCost method. A graph implementing the interface provides a heuristic between any two given nodes.

type Shortest

type Shortest struct {
	// contains filtered or unexported fields
}

Shortest is a shortest-path tree created by the BellmanFordFrom or DijkstraFrom single-source shortest path functions.

func AStar

func AStar(s, t graph.Node, g graph.Graph, h Heuristic) (path Shortest, expanded int)

AStar finds the A*-shortest path from s to t in g using the heuristic h. The path and its cost are returned in a Shortest along with paths and costs to all nodes explored during the search. The number of expanded nodes is also returned. This value may help with heuristic tuning.

The path will be the shortest path if the heuristic is admissible. A heuristic is admissible if for any node, n, in the graph, the heuristic estimate of the cost of the path from n to t is less than or equal to the true cost of that path.

If h is nil, AStar will use the g.HeuristicCost method if g implements HeuristicCoster, falling back to NullHeuristic otherwise. If the graph does not implement graph.Weighter, graph.UniformCost is used. AStar will panic if g has an A*-reachable negative edge weight.

func BellmanFordFrom

func BellmanFordFrom(u graph.Node, g graph.Graph) (path Shortest, ok bool)

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 graph.Weighter, graph.UniformCost is used.

The time complexity of BellmanFordFrom is O(|V|.|E|).

func DijkstraFrom

func DijkstraFrom(u graph.Node, g graph.Graph) Shortest

DijkstraFrom returns a shortest-path tree for a shortest path from u to all nodes in the graph g. If the graph does not implement graph.Weighter, graph.UniformCost is used. DijkstraFrom will panic if g has a u-reachable negative edge weight.

The time complexity of DijkstrFrom is O(|E|+|V|.log|V|).

func (Shortest) From

func (p Shortest) From() graph.Node

From returns the starting node of the paths held by the Shortest.

func (Shortest) To

func (p Shortest) To(v graph.Node) (path []graph.Node, weight float64)

To returns a shortest path to v and the weight of the path.

func (Shortest) WeightTo

func (p Shortest) WeightTo(v graph.Node) float64

WeightTo returns the weight of the minimum path to v.

Directories

Path Synopsis

Jump to

Keyboard shortcuts

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