dag

Documentation

Overview

Package dag implements a simple Directed Acyclical Graph (DAG) for deterministic topological sorts

It should not be externally exposed, and is intended to be a very simple dag implementation utilizing adjacency lists to store edges.

This package is intended to be used for small scales, where performance of the algorithms is not critical. (e.g. sub 10k entries) Thus none of the algorithms in here are benchmarked, and just have correctness checks.

Index

• type DAG
  • func NewDAG(nodes []string) DAG
  • func (dag *DAG) AddEdge(u, v string) error
  • func (dag *DAG) AddFirstElements(nodes ...string) error
  • func (dag *DAG) AddLastElements(nodes ...string) error
  • func (dag DAG) Copy() DAG
  • func (dag *DAG) ReplaceEdge(u, v string) error
  • func (dag DAG) TopologicalSort() []string

Types

type DAG

type DAG struct {
	// contains filtered or unexported fields
}

DAG struct maintains a directed acyclic graph, using adjacency lists to track edges.

func NewDAG

func NewDAG(nodes []string) DAG

func (*DAG) AddEdge

func (dag *DAG) AddEdge(u, v string) error

AddEdge checks if either edge between u and v exists and adds a directed edge from u -> v

func (*DAG) AddFirstElements

func (dag *DAG) AddFirstElements(nodes ...string) error

AddFirstElements sets the provided elements to be first in all orderings. So if were making an ordering over {A, B, C, D, E}, and elems provided is {D, B, A} then we are guaranteed that the total ordering will begin with {D, B, A}

func (*DAG) AddLastElements

func (dag *DAG) AddLastElements(nodes ...string) error

AddLastElements sets the provided elements to be last in all orderings. So if were making an ordering over {A, B, C, D, E}, and elems provided is {D, B, A} then we are guaranteed that the total ordering will end with {D, B, A}

func (DAG) Copy

func (dag DAG) Copy() DAG

Copy returns a new dag struct that is a copy of the original dag. Edges can be mutated in the copy, without altering the original.

func (*DAG) ReplaceEdge

func (dag *DAG) ReplaceEdge(u, v string) error

ReplaceEdge adds a directed edge from u -> v. it removes any edge that may already exist between the two.

func (DAG) TopologicalSort

func (dag DAG) TopologicalSort() []string

Returns a Topological Sort of the DAG, using Kahn's algorithm. https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm