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
- type BasicNode
- type Digraph
- type Edge
- type Node
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DepthFirstWalk ¶
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 ParseBasic ¶
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 ¶
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.
Types ¶
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 ¶
FilterDegree returns only the nodes with the desired degree. This can be used with OutDegree or InDegree
func Unreachable ¶
Unreachable starts at a given start node, performs a DFS from there, and returns the set of unreachable nodes.