dag

README

dag

Algorithms on Directed Acyclic Graphs (DAG)

Documentation

Index

• Variables
• func DFS[T comparable](g DirectedGraph[T], startingNode T) ([]T, error)
• func TopologicalSort[T comparable](g DirectedGraph[T]) ([]T, error)
• type DirectedGraph
• type Simple
  • func NewSimple(m map[string][]string) Simple
  • func (g Simple) DependsOn(node string) []string
  • func (g Simple) Nodes() []string

Variables

var (
	ErrGraphHaveCycles = errors.New("the DAG have cycles")
)

Functions

func DFS

func DFS[T comparable](g DirectedGraph[T], startingNode T) ([]T, error)

depth first search with cycle detection

func TopologicalSort

func TopologicalSort[T comparable](g DirectedGraph[T]) ([]T, error)

sort the nodes is topological order returns ErrGraphHaveCycles if the graph have cycles

Types

type DirectedGraph

type DirectedGraph[T comparable] interface {
	// get all nodes present
	Nodes() []T

	// get a list of nodes that the argument node depends on
	DependsOn(T) []T
}

type Simple

type Simple map[string][]string

simple map implementation of the DirectedGraph interface

func NewSimple

func NewSimple(m map[string][]string) Simple

construct a DG from a map, making sure all nodes are represented

func (Simple) DependsOn

func (g Simple) DependsOn(node string) []string

func (Simple) Nodes

func (g Simple) Nodes() []string