Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DumpCycles ¶
DumpCycles dumps the cycles returned from TopoSort, using toString to convert each node into a string.
func ShortestPath ¶
func ShortestPath[Node comparable, Edge any](g Graph[Node, Edge], from, to Node) []Edge
ShortestPath returns the shortest path from -> to in the graph g using Dijkstra's algorithm. The returned slice holds all the edges leading from the source to the destination.
func TopoSort ¶
func TopoSort[Node comparable, Edge any](g Graph[Node, Edge]) (sorted []Node, cycles [][]Node)
TopoSort returns the topologically sorted nodes, along with some of the cycles (if any) that were encountered. You're guaranteed that len(cycles)==0 iff there are no cycles in the graph, otherwise an arbitrary (but non-empty) list of cycles is returned.
If there are cycles the sorting is best-effort; portions of the graph that are acyclic will still be ordered correctly, and the cyclic portions have an arbitrary ordering.
Sort is deterministic; given the same sequence of inputs it always returns the same output, even if the inputs are only partially ordered.
Types ¶
type Graph ¶
type Graph[Node comparable, Edge any] interface { Edges(n Node) []Edge Nodes(e Edge) (from, to Node) AllNodes() []Node }
type Simple ¶
type Simple[Node comparable] struct { // contains filtered or unexported fields }
Simple implements Graph for a concrete set of comparable nodes.
func (*Simple[Node]) AddEdge ¶
func (g *Simple[Node]) AddEdge(from, to Node)
AddEdge adds nodes from and to, and adds an edge from -> to. You don't need to call AddNode first; the nodes will be implicitly added if they don't already exist. The direction means that from depends on to; i.e. to will appear before from in the sorted output. Cycles are allowed.
func (*Simple[Node]) AddNode ¶
func (g *Simple[Node]) AddNode(n Node)
AddNode adds a node. Typically this is only used to add nodes with no incoming or outgoing edges.
func (*Simple[Node]) AllNodes ¶
func (g *Simple[Node]) AllNodes() []Node
AllNodes implements Graph.AllNodes. Note: the caller should not mutate the returned slice.
func (*Simple[Node]) Edges ¶
func (g *Simple[Node]) Edges(n Node) [][2]Node
AllNodes implements Graph.Edges. Note: the caller should not mutate the returned slice.
func (*Simple[Node]) Graph ¶
Graph returns g as the Graph interface. This avoids the annoying explicit type conversion needed by the current Go generics implementation. See https://github.com/golang/go/issues/41176.
Source Files