Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CyclicError ¶
type CyclicError[T comparable] struct { Cycle []T }
CyclicError is returned when the input graph has a cycle.
func (*CyclicError[T]) Error ¶
func (e *CyclicError[T]) Error() string
type Graph ¶
Graph represents a directed graph.
func (*Graph[T]) AddEdge ¶
func (g *Graph[T]) AddEdge(source, destination T)
AddEdge adds a directed edge from source to destination. This should be interpreted as "$source depends on $destination," not "$source comes before "$destination." In the topologically sorted output, $destination will come before $source.
func (*Graph[T]) AddNode ¶
func (g *Graph[T]) AddNode(n T)
AddNode adds a node to the graph without adding any edges. [AddEdge] implicitly creates nodes, so this function is only needed in the case where you have a node with no edges to or from it.
This function is always safe to call. You can call it before adding edges to the node or after adding edges. It is idempotent.
func (*Graph[T]) TopologicalSort ¶
TopologicalSort performs a topological sort. For all edges a->b, the output will have b before a.
For the same graph, the same result will be returned, regardless of the order of Add*() calls, and regardless of Go's random map iteration order.
If there is a cycle in the graph, an error message will be returned that names the nodes involved in the cycle.
Source Files