Documentation
¶
Overview ¶
Package algorithm provides useful generic algorithms.
Index ¶
- func ConnectedComponents[K comparable](g ComponentGraph[K]) map[K]map[K]struct{}
- func Dijkstra[K comparable, T Number](g Graph[K, T], source K, target *K, maxT T) map[K]T
- func Max[K comparable, T Number](distances map[K]T, maxT T) (maxKey K, maxDistance T)
- func PathTo[K comparable, T Number](g Graph[K, T], source K, target K, maxT T) map[K]T
- type ComponentGraph
- type Graph
- type Number
- type PriorityQueue
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ConnectedComponents ¶ added in v0.0.36
func ConnectedComponents[K comparable](g ComponentGraph[K]) map[K]map[K]struct{}
func Dijkstra ¶
func Dijkstra[K comparable, T Number](g Graph[K, T], source K, target *K, maxT T) map[K]T
Dijkstra performs Dijkstra's algorithm to find the shortest path from source to target. If target is nil, then all distances are calculated.
func Max ¶ added in v0.0.28
func Max[K comparable, T Number](distances map[K]T, maxT T) (maxKey K, maxDistance T)
Max finds the node with the maximum distance and returns its key and distance.
func PathTo ¶ added in v0.0.28
func PathTo[K comparable, T Number](g Graph[K, T], source K, target K, maxT T) map[K]T
PathTo finds the shortest path from one node to another but instead of returning all the distances, it only returns only the nodes (and their distances) along that path.
Types ¶
type ComponentGraph ¶ added in v0.0.36
type ComponentGraph[K comparable] interface { Less(k1, k2 K) bool Each(f func(key K)) EachNeighbor(from K, f func(from, to K)) }
ComponentGraph represents a graph that can find connected components.
type Graph ¶
type Graph[K comparable, T Number] interface { Distance(from, to K) T Each(f func(key K)) EachNeighbor(from K, f func(from, to K)) }
Graph represents a graph that can use Dijkstra's algorithm.
type Number ¶
type Number interface {
constraints.Integer | constraints.Unsigned | constraints.Float
}
Number is a number.
type PriorityQueue ¶
type PriorityQueue[K comparable] struct { // contains filtered or unexported fields }
PriorityQueue represents a queue that maintains its priority order.
func NewPriorityQueue ¶
func NewPriorityQueue[K comparable](less func(K, K) bool) *PriorityQueue[K]
NewPriorityQueue returns a new priority queue.
func (*PriorityQueue[K]) Fix ¶
func (pq *PriorityQueue[K]) Fix(key K)
Fix re-establishes the heap ordering after the element at key has changed its value. Changing the value of the element at key and then calling Fix is equivalent to, but less expensive than, calling Remove(key) followed by a Push of the new value. The complexity is O(log n) where n = h.Len().
func (*PriorityQueue[K]) Init ¶
func (pq *PriorityQueue[K]) Init()
Init establishes the heap invariants required by the other routines in this package. Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated. The complexity is O(n) where n = h.Len().
func (*PriorityQueue[K]) Len ¶
func (pq *PriorityQueue[K]) Len() int
Len returns the current number of items in the priority queue.
func (*PriorityQueue[K]) Pop ¶
func (pq *PriorityQueue[K]) Pop() K
Pop removes and returns the minimum element (according to Less) from the heap. The complexity is O(log n) where n = h.Len(). Pop is equivalent to Remove(h, 0).
func (*PriorityQueue[K]) Push ¶
func (pq *PriorityQueue[K]) Push(key K)
Push pushes the element x onto the heap. The complexity is O(log n) where n = h.Len().
func (*PriorityQueue[K]) Remove ¶
func (pq *PriorityQueue[K]) Remove(key K)
Remove removes and returns the element at index i from the heap. The complexity is O(log n) where n = h.Len().
Source Files