toposort/sort.go

// Copyright 2015 The Vanadium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package toposort implements topological sort.  For details see:
// http://en.wikipedia.org/wiki/Topological_sorting
package toposort

// 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.
type Sorter struct {
	values map[interface{}]int // maps from user-provided value to index in nodes
	nodes  []*node             // the graph to sort
}

// node represents a node in the graph.
type node struct {
	value    interface{}
	children []*node
}

func (s *Sorter) getOrAddNode(value interface{}) *node {
	if s.values == nil {
		s.values = make(map[interface{}]int)
	}
	if index, ok := s.values[value]; ok {
		return s.nodes[index]
	}
	s.values[value] = len(s.nodes)
	newNode := &node{value: value}
	s.nodes = append(s.nodes, newNode)
	return newNode
}

// 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 (s *Sorter) AddNode(value interface{}) {
	s.getOrAddNode(value)
}

// 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 (s *Sorter) AddEdge(from interface{}, to interface{}) {
	fromN, toN := s.getOrAddNode(from), s.getOrAddNode(to)
	fromN.children = append(fromN.children, toN)
}

// 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.
func (s *Sorter) Sort() (sorted []interface{}, cycles [][]interface{}) {
	// The strategy is the standard simple approach of performing DFS on the
	// graph.  Details are outlined in the above wikipedia article.
	done := make(map[*node]bool)
	for _, n := range s.nodes {
		cycles = appendCycles(cycles, n.visit(done, make(map[*node]bool), &sorted))
	}
	return
}

// visit performs DFS on the graph, and fills in sorted and cycles as it
// traverses.  We use done to indicate a node has been fully explored, and
// visiting to indicate a node is currently being explored.
//
// The cycle collection strategy is to wait until we've hit a repeated node in
// visiting, and add that node to cycles and return.  Thereafter as the
// recursive stack is unwound, nodes append themselves to the end of each cycle,
// until we're back at the repeated node.  This guarantees that if the graph is
// cyclic we'll return at least one of the cycles.
func (n *node) visit(done, visiting map[*node]bool, sorted *[]interface{}) (cycles [][]interface{}) {
	if done[n] {
		return
	}
	if visiting[n] {
		cycles = [][]interface{}{{n.value}}
		return
	}
	visiting[n] = true
	for _, child := range n.children {
		cycles = appendCycles(cycles, child.visit(done, visiting, sorted))
	}
	done[n] = true
	*sorted = append(*sorted, n.value)
	// Update cycles.  If it's empty none of our children detected any cycles, and
	// there's nothing to do.  Otherwise we append ourselves to the cycle, iff the
	// cycle hasn't completed yet.  We know the cycle has completed if the first
	// and last item in the cycle are the same, with an exception for the single
	// item case; self-cycles are represented as the same node appearing twice.
	for cx := range cycles {
		len := len(cycles[cx])
		if len == 1 || cycles[cx][0] != cycles[cx][len-1] {
			cycles[cx] = append(cycles[cx], n.value)
		}
	}
	return
}

// appendCycles returns the combined cycles in a and b.
func appendCycles(a [][]interface{}, b [][]interface{}) [][]interface{} {
	for _, bcycle := range b {
		a = append(a, bcycle)
	}
	return a
}

// DumpCycles dumps the cycles returned from Sorter.Sort, using toString to
// convert each node into a string.
func DumpCycles(cycles [][]interface{}, toString func(n interface{}) string) string {
	var str string
	for cyclex, cycle := range cycles {
		if cyclex > 0 {
			str += " "
		}
		str += "["
		for nodex, node := range cycle {
			if nodex > 0 {
				str += " <= "
			}
			str += toString(node)
		}
		str += "]"
	}
	return str
}