digraph

Documentation

Index

• func DepthFirstWalk(node Node, cb func(n Node) bool)
• func InDegree(nodes []Node) map[Node]int
• func OutDegree(nodes []Node) map[Node]int
• func ParseBasic(s string) map[string]*BasicNode
• func StronglyConnectedComponents(nodes []Node, excludeSingle bool) [][]Node
• func WriteDot(w io.Writer, nodes []Node) error
• type BasicEdge
  • func (b *BasicEdge) Head() Node
  • func (b *BasicEdge) String() string
  • func (b *BasicEdge) Tail() Node
• type BasicNode
  • func (b *BasicNode) AddEdge(edge Edge)
  • func (b *BasicNode) Edges() []Edge
  • func (b *BasicNode) String() string
• type Digraph
• type Edge
• type Node
  • func FilterDegree(degree int, degrees map[Node]int) []Node
  • func Sinks(nodes []Node) []Node
  • func Sources(nodes []Node) []Node
  • func Unreachable(start Node, nodes []Node) []Node

Functions

func DepthFirstWalk

func DepthFirstWalk(node Node, cb func(n Node) bool)

DepthFirstWalk performs a depth-first traversal of the nodes that can be reached from the initial input set. The callback is invoked for each visited node, and may return false to prevent vising any children of the current node

func InDegree

func InDegree(nodes []Node) map[Node]int

InDegree is used to compute the in-degree of nodes

func OutDegree

func OutDegree(nodes []Node) map[Node]int

OutDegree is used to compute the in-degree of nodes

func ParseBasic

func ParseBasic(s string) map[string]*BasicNode

ParseBasic is used to parse a string in the format of: a -> b ; edge name b -> c Into a series of basic node and basic edges

func StronglyConnectedComponents

func StronglyConnectedComponents(nodes []Node, excludeSingle bool) [][]Node

StronglyConnectedComponents implements Tarjan's algorithm to find all the strongly connected components in a graph. This can be used to detected any cycles in a graph, as well as which nodes partipate in those cycles. excludeSingle is used to exclude strongly connected components of size one.

func WriteDot

func WriteDot(w io.Writer, nodes []Node) error

WriteDot is used to emit a GraphViz compatible definition for a directed graph. It can be used to dump a .dot file.

Types

type BasicEdge

type BasicEdge struct {
	Name     string
	EdgeHead *BasicNode
	EdgeTail *BasicNode
}

BasicEdge is a digraph Edge that has a name, head and tail

func (*BasicEdge) Head

func (b *BasicEdge) Head() Node

func (*BasicEdge) String

func (b *BasicEdge) String() string

func (*BasicEdge) Tail

func (b *BasicEdge) Tail() Node

Tail returns the end point of the Edge

type BasicNode

type BasicNode struct {
	Name      string
	NodeEdges []Edge
}

BasicNode is a digraph Node that has a name and out edges

func (*BasicNode) AddEdge

func (b *BasicNode) AddEdge(edge Edge)

func (*BasicNode) Edges

func (b *BasicNode) Edges() []Edge

func (*BasicNode) String

func (b *BasicNode) String() string

type Digraph

type Digraph interface {
	// Nodes provides all the nodes in the graph
	Nodes() []Node

	// Sources provides all the source nodes in the graph
	Sources() []Node

	// Sinks provides all the sink nodes in the graph
	Sinks() []Node

	// Transpose reverses the edge directions and returns
	// a new Digraph
	Transpose() Digraph
}

Digraph is used to represent a Directed Graph. This means we have a set of nodes, and a set of edges which are directed from a source and towards a destination

type Edge

type Edge interface {
	// Head returns the start point of the Edge
	Head() Node

	// Tail returns the end point of the Edge
	Tail() Node
}

Edge represents a directed edge in a Digraph

type Node

type Node interface {
	// Edges returns the out edges for a given nod
	Edges() []Edge
}

Node represents a vertex in a Digraph

func FilterDegree

func FilterDegree(degree int, degrees map[Node]int) []Node

FilterDegree returns only the nodes with the desired degree. This can be used with OutDegree or InDegree

func Sinks

func Sinks(nodes []Node) []Node

Sinks is used to get the nodes with out-degree of 0

func Sources

func Sources(nodes []Node) []Node

Sources is used to get the nodes with in-degree of 0

func Unreachable

func Unreachable(start Node, nodes []Node) []Node

Unreachable starts at a given start node, performs a DFS from there, and returns the set of unreachable nodes.