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 ¶
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.
Types ¶
type BasicEdge ¶
type BasicEdge struct {
Name string
EdgeHead *BasicNode
EdgeTail *BasicNode
}
BasicEdge is a digraph Edge that has a name, head and tail
type BasicNode ¶
type BasicNode struct {
Name string
NodeEdges []Edge
}
BasicNode is a digraph Node that has a name and out edges
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 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.
Source Files