Documentation
¶
Index ¶
- func Dominators(start graph.Node, g graph.Graph) map[int]internal.Set
- func Kruskal(dst graph.MutableUndirected, g EdgeListerGraph)
- func NullHeuristic(_, _ graph.Node) float64
- func PostDominators(end graph.Node, g graph.Graph) map[int]internal.Set
- func Prim(dst graph.MutableUndirected, g EdgeListerGraph)
- type AllShortest
- type EdgeListerGraph
- type Heuristic
- type HeuristicCoster
- type Shortest
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Dominators ¶
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 ¶
NullHeuristic is an admissible, consistent heuristic that will not speed up computation.
func PostDominators ¶
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 ¶
func Prim(dst graph.MutableUndirected, g EdgeListerGraph)
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 ¶
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 ¶
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.
type EdgeListerGraph ¶
type EdgeListerGraph interface {
graph.Undirected
Edges() []graph.Edge
}
EdgeListerGraph is an undirected graph than returns its complete set of edges.
type HeuristicCoster ¶
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 ¶
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 ¶
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 ¶
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|).
Source Files
Directories