toposort

Documentation

Index

• Variables
• type Graph
  • func (g *Graph[T]) AddEdge(from, to T)
  • func (g *Graph[T]) AddNode(n T)
  • func (g *Graph[T]) DetTopologicalOrder(cmp func(a, b T) int) ([]T, error)
  • func (g *Graph[T]) ImplicitNodeReferences() map[T]map[T]bool
  • func (g *Graph[T]) TopologicalOrder() ([]T, error)

Variables

var ErrCycle = errors.New("graph has at least one cycle")

Types

type Graph

type Graph[T comparable] struct {
	// contains filtered or unexported fields
}

Graph is a directed graph represented using an adjacency list. Its nodes have type T. An empty Graph object is ready to use.

func (*Graph[T]) AddEdge

func (g *Graph[T]) AddEdge(from, to T)

AddEdge adds the directed edge from the from node to the to node to the graph if it does not already exist, in which case it does nothing. If nodes from and/or to do not already exist, they are added implicitly.

func (*Graph[T]) AddNode

func (g *Graph[T]) AddNode(n T)

AddNode adds the node n to the graph if it does not already exist, in which case it does nothing.

func (*Graph[T]) DetTopologicalOrder

func (g *Graph[T]) DetTopologicalOrder(cmp func(a, b T) int) ([]T, error)

DetTopologicalOrder is a deterministic version of TopologicalSort which has higher cyclomatic complexity. See TopologicalSort for further documentation.

func (*Graph[T]) ImplicitNodeReferences

func (g *Graph[T]) ImplicitNodeReferences() map[T]map[T]bool

ImplicitNodeReferences returns a map of nodes with the set of their incoming and outgoing references for all nodes which were referenced in an AddEdge call but not added via an explicit AddNode. If the length of the returned map is zero, all referenced nodes were explicitly added. This can be used to check for bad references in dependency trees.

func (*Graph[T]) TopologicalOrder

func (g *Graph[T]) TopologicalOrder() ([]T, error)

TopologicalOrder sorts the nodes in the graph according to their topological order (aka. dependency order) and returns a valid order. Note that this implementation returns the reverse order of a "standard" topological order, i.e. if edge A -> B exists, it returns B, A. This is more convenient for solving dependency ordering problems, as a normal dependency graph will sort according to execution order. Further note that there can be multiple such orderings and any of them might be returned. Even multiple invocations of TopologicalOrder can return different orderings. If no such ordering exists (i.e. the graph contains at least one cycle), an error is returned.