graph

Documentation

Index

• func DFSAll(g Graph, enter, exit func(Node))
• func DebugString(g Graph) string
• func OutDegree(g Graph, n Node) int
• func PerEdge(g Graph, fn func(e Edge))
• type Edge
• type Graph
  • func NewAdjacencyGraph(nodes []Node, edges []Edge) Graph
• type Node
  • func PostOrder(g Graph) []Node
  • func ReversePostOrder(g Graph) []Node

Functions

func DFSAll

func DFSAll(g Graph, enter, exit func(Node))

DFSAll performs a depth first search of all nodes in g. If enter is non-nil, it is called on entry to a node. If exit is non-nil, it is called on exit from a node.

func DebugString

func DebugString(g Graph) string

DebugString returns a human readable string representation of g.

Sample output for a graph with nodes 1,2,3:

1:
2: 1
3: 1 2

func OutDegree

func OutDegree(g Graph, n Node) int

OutDegree returns the out-degree for node n in g.

func PerEdge

func PerEdge(g Graph, fn func(e Edge))

PerEdge calls fn(edge) for every edge in g.

Types

type Edge

type Edge struct {
	Src, Dst Node
}

Edge is a directed graph edge.

type Graph

type Graph interface {
	// PerNode executes the supplied function exactly once per node.
	PerNode(func(n Node))

	// PerOutEdge executes the supplied function exactly once per edge from src.
	PerOutEdge(src Node, fn func(e Edge))

	// NodeLimit returns a number guaranteed to be larger than any
	// Node in the graph.  Many algorithms assume that NodeLimit
	// is not much larger than the number of Nodes in the graph,
	// so Graph implementations should use a relatively dense numeric
	// assignment for nodes.
	NodeLimit() int
}

Graph is an interface that represents a directed graph. Most users will want to use the `AdjacencyGraph` implementation of `Graph`, but it is easy to provide and use a custom `Graph` implementation if necessary.

func NewAdjacencyGraph

func NewAdjacencyGraph(nodes []Node, edges []Edge) Graph

NewAdjacencyGraph returns a Graph represented using adjacency lists.

It panics if it specified edge nodes aren't in nodes.

type Node

type Node int

Node is a small non-negative number that identifies a node in a directed graph. Node numbers should be kept proportional to the size of the graph (i.e., mostly densely packed) since different algorithms may allocate arrays indexed by the node number.

func PostOrder

func PostOrder(g Graph) []Node

PostOrder returns nodes in g in post-order.

func ReversePostOrder

func ReversePostOrder(g Graph) []Node

ReversePostOrder returns nodes in g in reverse-post-order.