topologysort

Documentation

Index

• type TopologySortError
  • func TopologySort(incomingEdges [][]bool, inDegrees []int) (topoSorted []int, errs []TopologySortError)
  • func (e TopologySortError) Error() string

Types

type TopologySortError

type TopologySortError struct {
	OnId                        int   `json:"onID"`
	UnresolvedIncomingEdgesFrom []int `json:"unresolvedIncomingEdgesFrom"`
}

TopologySortError is an error returned for any unresolved dependency after sorting The error marks the ID of the node left with unresolved incoming edges after sorting, as well as the IDs of the nodes still pointing to it.

func TopologySort

func TopologySort(incomingEdges [][]bool, inDegrees []int) (topoSorted []int, errs []TopologySortError)

TopologySort implements Kahn's algorithm for topological sorting As an input to the algorithm it takes a directed graph represented as a dependency matrix of incoming edges. To simplify checking full resolution/sort failure a precomputed slice of inDegrees per node must be provided as well. Indices in the incomingEdges dependency matrix and inDegrees slice need to match - e.g. if incomingEdges[i] marks two edges as 'true', inDegrees[i] must equal 2.

Successful sorting - which is guaranteed for acyclic directed graphs - will see all edges resolved, leaving each node with an inDegree of zero.

In case of cycles in the graph some nodes will be left with unresolved edges (inDegree > 0) - in this case a list of TopologySortError will be returned, marking each node id with unresolved incoming edges and which node ids are still pointing to it.

func (TopologySortError) Error

func (e TopologySortError) Error() string