Documentation
¶
Overview ¶
Package toposort implements topological sort. For details see: http://en.wikipedia.org/wiki/Topological_sorting
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DumpCycles ¶
DumpCycles dumps the cycles returned from Sorter.Sort, using toString to convert each node into a string.
Types ¶
type Sorter ¶
type Sorter struct {
// contains filtered or unexported fields
}
Sorter implements a topological sorter. Add nodes and edges to the sorter to describe the graph, and call Sort to retrieve topologically-sorted nodes. The zero Sorter describes an empty graph.
func (*Sorter) AddEdge ¶
func (s *Sorter) AddEdge(from interface{}, to interface{})
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 (*Sorter) AddNode ¶
func (s *Sorter) AddNode(value interface{})
AddNode adds a node. Arbitrary value types are supported, but the values must be comparable; they'll be used as map keys. Typically this is only used to add nodes with no incoming or outgoing edges.
func (*Sorter) Sort ¶
func (s *Sorter) Sort() (sorted []interface{}, cycles [][]interface{})
Sort 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.
Source Files