# digraph

package
Version: v0.11.7 Latest Latest

Go to latest
Published: Apr 10, 2018 License: MPL-2.0

## Documentation ¶

### 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.

#### 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
EdgeTail *BasicNode
}```

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

`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 (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

// 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.