Documentation
¶
Index ¶
- Variables
- type Graph
- func (g *Graph[S, T]) ConnectedGraph(seed S) *Graph[S, T]
- func (g *Graph[S, T]) ConnectedGraphContext(ctx context.Context, seed S) (*Graph[S, T], error)
- func (g *Graph[S, T]) MaximumSpanningTree(seed S) *Graph[S, T]
- func (g *Graph[S, T]) MaximumSpanningTreeContext(ctx context.Context, seed S) (*Graph[S, T], error)
- func (g *Graph[S, T]) MinimumSpanningTree(seed S) *Graph[S, T]
- func (g *Graph[S, T]) MinimumSpanningTreeContext(ctx context.Context, seed S) (*Graph[S, T], error)
- func (g *Graph[S, T]) PutEdge(tail, head S, weight float32)
- func (g *Graph[S, T]) PutVertex(key S, value T)
- func (g *Graph[S, T]) ShortestPathTree(seed S, costFunc func(x float32) float32) *Graph[S, T]
- func (g *Graph[S, T]) ShortestPathTreeContext(ctx context.Context, seed S, costFunc func(x float32) float32) (*Graph[S, T], error)
- type InvalidShortestPathCostError
Constants ¶
This section is empty.
Variables ¶
var ErrInvalidShortestPathCost = errors.New("shortest-path tree requires finite, non-negative costs")
ErrInvalidShortestPathCost reports a cost that violates Dijkstra's finite, non-negative cost precondition. Callers can use errors.Is to distinguish invalid graph data or a cost transform from cancellation and other traversal failures.
Functions ¶
This section is empty.
Types ¶
type Graph ¶
type Graph[S comparable, T any] struct { Vertices map[S]T `json:"vertices,omitempty"` Edges map[S]map[S]float32 `json:"edges,omitempty"` }
func NewGraph ¶
func NewGraph[S comparable, T any]() *Graph[S, T]
func (*Graph[S, T]) ConnectedGraph ¶
func (*Graph[S, T]) ConnectedGraphContext ¶
ConnectedGraphContext is the context-aware variant of ConnectedGraph. It returns ctx.Err() as soon as the context is cancelled or its deadline has expired, so callers can short-circuit large traversals.
Implementation: classic FIFO-queue BFS. Each reachable vertex is enqueued exactly once, each outgoing edge is visited exactly once, giving O(V+E) time and O(V) auxiliary memory. The prior round-based loop re-scanned connected.Edges every iteration for O(V·(V+E)).
func (*Graph[S, T]) MaximumSpanningTree ¶
MaximumSpanningTree returns the maximum-weight rooted directed arborescence over every vertex reachable from seed. See Graph.MinimumSpanningTree for the directed semantics.
func (*Graph[S, T]) MaximumSpanningTreeContext ¶
MaximumSpanningTreeContext is the context-aware variant of Graph.MaximumSpanningTree.
func (*Graph[S, T]) MinimumSpanningTree ¶
MinimumSpanningTree returns the minimum-cost rooted directed arborescence over every vertex reachable from seed. Lantern edges are directed, so this is not an undirected Prim MST: every non-seed vertex has exactly one selected incoming edge and remains reachable from seed in the result.
func (*Graph[S, T]) MinimumSpanningTreeContext ¶
MinimumSpanningTreeContext is the context-aware variant of Graph.MinimumSpanningTree.
func (*Graph[S, T]) ShortestPathTree ¶
ShortestPathTree
- ShortestPathTree returns a shortest path tree of the graph from the seed.
- The costFunc is a function that returns the cost of the edge.
- Typically, if the weight means like `importance`, the costFunc is a function that returns the 1 / weight.
- It is calculated by Dijkstra's algorithm, so the costFunc must return a
- finite, non-negative value. This convenience variant returns nil when that
- precondition is violated; callers that need the typed error should use
- ShortestPathTreeContext.
func (*Graph[S, T]) ShortestPathTreeContext ¶
func (g *Graph[S, T]) ShortestPathTreeContext(ctx context.Context, seed S, costFunc func(x float32) float32) (*Graph[S, T], error)
ShortestPathTreeContext is the context-aware variant of ShortestPathTree.
Implementation: classic Dijkstra with relaxation against the original graph. A dist[v] table tracks the best known cost from seed; whenever a shorter path is discovered, dist/prev are updated and a new PQ entry is pushed. Stale entries (top.Priority worse than the current dist[u]) are skipped on pop. Each vertex is therefore settled at most once and each edge is relaxed at most once, giving O((V+E) log V) time and O(V) active PQ entries.
The previous implementation called ConnectedGraphContext first (an extra O(V+E) walk plus a full subgraph copy) and used a pivot/position trick without a distance table, which allowed the PQ to grow to O(E). Both are avoided here.
PriorityQueue is a max-heap; priorities are negated so the smallest dist surfaces first. costFunc must return finite, non-negative values (Dijkstra precondition). Costs and candidate distances are validated before they enter the queue: negative costs can otherwise make a reachable cycle relax forever, while NaN/Inf makes priority ordering undefined.
type InvalidShortestPathCostError ¶ added in v0.18.0
InvalidShortestPathCostError identifies the edge cost or candidate distance that made a shortest-path-tree traversal unsafe. It unwraps to ErrInvalidShortestPathCost so callers need not parse its diagnostic text.
func (*InvalidShortestPathCostError) Error ¶ added in v0.18.0
func (e *InvalidShortestPathCostError) Error() string
func (*InvalidShortestPathCostError) Unwrap ¶ added in v0.18.0
func (e *InvalidShortestPathCostError) Unwrap() error
Source Files
Directories