Documentation
¶
Overview ¶
Package cycle demonstrates cycle detection in a directed graph.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ErrCycle = errors.New("cycle error")
ErrCycle means the graph has a cycle.
Functions ¶
func HasCycle ¶
HasCycle uses depth-first search to detect cycles in the graph. It reports first found cycle.
The initial idea was brought from x/tools/go/analysis/validate.go^1, where Validate() uses colors to:
keep track of the nodes while parsing through the graph.
build a cycle path by traversing nodes that are marked grey (in-progress).
ensure there are no duplicate root nodes. A sub-graph without cycles has all nodes marked black. A unique root node is marked finished. A duplicate root node would have finished-mark set twice.
This code takes a different approach: it uses a single seen-map to keep track of visited nodes and a path-stack to report cycle, which hopefully is more readable for the following reasons:
no cognitive load to keep track of color/node-state association (white, grey, black, finished are not intuitive to associate with not-seen, seen, no-cycles, unique-root node states correspondingly in Validate()).
the cycle path is available right away for quick error reporting if the node was visited in DFS, making error generation quick and easy. Of course the logic can be encapsulated in a function, but current version avoids it for readability.
Types ¶
type CycleError ¶
type CycleError []*Node
CycleError holds a cycle in the graph.
func (CycleError) Error ¶
func (err CycleError) Error() string
Error implements [builin.error] interface.
Source Files