dfstopo

README

dfstopo

depth-first search topological sort

Algorithm

Borrowed from wikipedia

Inlined code incase wikipedia is edited.

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then return
    if n has a temporary mark then stop   (not a DAG)
    mark n with a temporary mark
    for each node m with an edge from n to m do
        visit(m)
    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

Note

This was implemented very quickly from the pseudocode above. As needed, I'll profile and refactor for performance.

Documentation

Index

• func ErrNotDAG() error
• type DirectedGraph
• type Node
  • func Sort(dg DirectedGraph) ([]Node, error)

Functions

func ErrNotDAG

func ErrNotDAG() error

ErrNotDAG returns the same error returned for a graph that is not a directed-acyclic graph.

Types

type DirectedGraph

type DirectedGraph map[Node]map[Node]struct{}

DirectedGraph is a map of nodes that map to other nodes.

type Node

type Node interface{}

Node can be anything. Since Node is a KeyType, it's up to the client to ensure it has the necessary comparison operators. https://golang.org/ref/spec#KeyType

func Sort

func Sort(dg DirectedGraph) ([]Node, error)

Sort performs a topological sort using depth-first search on a directed graph. If the graph is not acyclic, an error is returned.