Documentation
¶
Index ¶
- 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)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
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 a maximum spanning tree of the graph rooted at seed.
func (*Graph[S, T]) MaximumSpanningTreeContext ¶
MaximumSpanningTreeContext is the context-aware variant of Graph.MaximumSpanningTree.
func (*Graph[S, T]) MinimumSpanningTree ¶
MinimumSpanningTree returns a minimum spanning tree of the graph rooted at seed.
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 positive value.
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 non-negative values (Dijkstra precondition).
Source Files
Directories