graph

Documentation

Index

• Variables
• type DAG
  • func New() DAG
  • func (g *DAG) AddVertex(id string, parents []string) error
  • func (g *DAG) HasCycle() bool
  • func (g DAG) TopoSort() ([]string, error)
  • func (g DAG) Validate() error

Variables

var (
	// ErrDuplicateVertex indicates that a vertex with an
	// identical id exists in the DAG.
	ErrDuplicateVertex = errors.New("vertex already exists")
	// ErrVertexNoExist indicates that an id does not correspond
	// to a vertex in the DAG.
	ErrVertexNoExist = errors.New("vertex does not exist")
	// ErrCycle indicates that there is a cycle within the graph
	ErrCycle = errors.New("cycle exists")
)

Types

type DAG

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

DAG represents a Directed Acyclic Graph.

func New

func New() DAG

New returns a new DAG.

func (*DAG) AddVertex

func (g *DAG) AddVertex(id string, parents []string) error

AddVertex will add a vertex to the DAG with the adjacent parent verticies. Edges are assumed to travel from parents to children. If a vertex already exists, an error will be returned

func (*DAG) HasCycle

func (g *DAG) HasCycle() bool

HasCycle returns true if the graph contains a cycle.

func (DAG) TopoSort

func (g DAG) TopoSort() ([]string, error)

TopoSort performs a topological sort on the DAG and returns a slice of vertex ids in a valid topological order.

func (DAG) Validate

func (g DAG) Validate() error

Validate checks that all edges are valid. If a vertex references a non-existant vertex an error is returned. NOTE: this does not check for cycles. HasCycles does. this could maybe be a check within HasCycles and not part of the api?