dag

Documentation

Overview

Package dag provides the Directed-Acyclic-Graph (DAG) primitives required by Terramate. The nodes can be added by providing both the descendants and ancestors of each node but only the descendant -> ancestors relationship is kept.

Index

• Constants
• type DAG
  • func New() *DAG
  • func (d *DAG) AddNode(id ID, value interface{}, descendants, ancestors []ID) error
  • func (d *DAG) AncestorsOf(id ID) []ID
  • func (d *DAG) HasCycle(id ID) bool
  • func (d *DAG) IDs() []ID
  • func (d *DAG) Node(id ID) (interface{}, error)
  • func (d *DAG) Order() []ID
  • func (d *DAG) Validate() (reason string, err error)
• type ID
• type Visited

Constants

const (
	ErrDuplicateNode errors.Kind = "duplicate node"
	ErrNodeNotFound  errors.Kind = "node not found"
	ErrCycleDetected errors.Kind = "cycle detected"
)

Errors returned by operations on the DAG.

Types

type DAG

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

DAG is a Directed-Acyclic Graph

func New

func New() *DAG

New creates a new empty Directed-Acyclic-Graph.

func (*DAG) AddNode

func (d *DAG) AddNode(id ID, value interface{}, descendants, ancestors []ID) error

AddNode adds a new node to the dag. The lists of descendants and ancestors defines its edge. The value is anything related to the node that needs to be retrieved later when processing the DAG.

func (*DAG) AncestorsOf

func (d *DAG) AncestorsOf(id ID) []ID

AncestorsOf returns the list of ancestor node ids of the given id.

func (*DAG) HasCycle

func (d *DAG) HasCycle(id ID) bool

HasCycle returns true if the DAG has a cycle.

func (*DAG) IDs

func (d *DAG) IDs() []ID

IDs returns the sorted list of node ids.

func (*DAG) Node

func (d *DAG) Node(id ID) (interface{}, error)

Node returns the node with the given id.

func (*DAG) Order

func (d *DAG) Order() []ID

Order returns the topological order of the DAG. The node ids are lexicographic sorted whenever possible to give a consistent output.

func (*DAG) Validate

func (d *DAG) Validate() (reason string, err error)

Validate the DAG looking for cycles.

type ID

type ID string

ID of nodes

type Visited

type Visited map[ID]struct{}

Visited in a map of visited dag nodes by id. Note: it's not concurrent-safe.