graph

Documentation

Index

• Variables
• func Diff(a, b *Graph) []string
• type Graph
  • func New(nodes ...Node) *Graph
  • func (g *Graph) AddNodes(nodes ...Node) error
  • func (g *Graph) Connect(from, to Node) error
  • func (g *Graph) Cycles() (cycles [][]Node)
  • func (g *Graph) Incoming(n Node) (nodes map[Node]struct{}, err error)
  • func (g *Graph) IsLeaf(n Node) (bool, error)
  • func (g *Graph) IsRoot(n Node) (bool, error)
  • func (g *Graph) Outgoing(n Node) (nodes map[Node]struct{}, err error)
  • func (g *Graph) StronglyConnectedComponents() (components [][]Node)
  • func (g *Graph) TopologicalSort() []Node
  • func (g *Graph) Walk(fn VisitFunc)
  • func (g *Graph) WalkFrom(node Node, fn VisitFunc) error
• type Node
• type VisitFunc

Variables

var (
	// ErrDuplicateNode is returned when a node is attempted to
	// be inserted when it is already present
	ErrDuplicateNode = errors.New("node already exists in graph")
	// ErrMissingNode is returned when a node is reference which
	// does not exist within the graph
	ErrMissingNode = errors.New("node is not present in graph")
)

Functions

func Diff

func Diff(a, b *Graph) []string

Diff returns a string slice of differences between graphs a and b

Types

type Graph

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

Graph is a graph datastructure which contains nodes with directed edges between them

func New

func New(nodes ...Node) *Graph

New constructs a new graph from a set of Nodes

func (*Graph) AddNodes

func (g *Graph) AddNodes(nodes ...Node) error

AddNodes adds the provided nodes to the graph

func (*Graph) Connect

func (g *Graph) Connect(from, to Node) error

Connect constructs and edge from one node to another

func (*Graph) Cycles

func (g *Graph) Cycles() (cycles [][]Node)

Cycles detects and returns any cycles found within the graph

func (*Graph) Incoming

func (g *Graph) Incoming(n Node) (nodes map[Node]struct{}, err error)

Incoming returns a set of nodes which are directed from the provided node

func (*Graph) IsLeaf

func (g *Graph) IsLeaf(n Node) (bool, error)

IsLeaf returns true if the node has no outgoing edges within the graph

func (*Graph) IsRoot

func (g *Graph) IsRoot(n Node) (bool, error)

IsRoot returns true if the node has no incoming edges within the graph

func (*Graph) Outgoing

func (g *Graph) Outgoing(n Node) (nodes map[Node]struct{}, err error)

Outgoing returns a set of nodes which are directed to from the provided node

func (*Graph) StronglyConnectedComponents

func (g *Graph) StronglyConnectedComponents() (components [][]Node)

StronglyConnectedComponents returns the set of strongly connected components within the graph

func (*Graph) TopologicalSort

func (g *Graph) TopologicalSort() []Node

TopologicalSort returns the set of nodes within the graph topologically sorted

func (*Graph) Walk

func (g *Graph) Walk(fn VisitFunc)

Walk calls each visit func on each node in depth first order

func (*Graph) WalkFrom

func (g *Graph) WalkFrom(node Node, fn VisitFunc) error

WalkFrom traverses the outgoing nodes to the leaves of the graph from the provided node

type Node

type Node interface{}

Node is a vertex in a graph

type VisitFunc

type VisitFunc func(Node) error

VisitFunc is a function which takes a Node and returns an error