Documentation
¶
Overview ¶
Package graphalg implements common graph algorithms.
Index ¶
- func DomFrontier(g graph.BiGraph, root int, idom []int) [][]int
- func IDom(g graph.BiGraph, root int) []int
- func PostOrder(g graph.Graph, root int) []int
- func PreOrder(g graph.Graph, root int) []int
- func Reverse(xs []int) []int
- func SimplifyMulti(g graph.Graph) graph.Weighted
- type DomTree
- type Euler
- type NodeMarks
- type SCCFlags
- type SCCGraph
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DomFrontier ¶
DomFrontier returns the dominance frontier of each node in g. idom must be IDom(g, root). idom may be nil, in which case this computes IDom.
func IDom ¶
IDom returns the immediate dominator of each node of g. Nodes that don't have an immediate dominator (including root) are assigned -1.
func Reverse ¶
Reverse reverses xs in place and returns the slice. This is useful in conjunction with PreOrder and PostOrder to compute reverse post-order and reverse pre-order.
func SimplifyMulti ¶
SimplifyMulti simplifies a multigraph to a weighted simple graph.
If g is a weighted graph, each edge in the result receives the sum of the weights of the combined edges in g. If g is not weighted, each edge in g is assumed to have a weight of 1.
Types ¶
type DomTree ¶
type DomTree struct {
// contains filtered or unexported fields
}
DomTree is a dominator tree.
It also satisfies the BiGraph interface, which edges pointing toward children.
type Euler ¶
type Euler struct {
// Enter is called when a node a first visited. It may be nil.
Enter func(n int)
// Exit is called when all of the children of n have been
// visited. It may be nil.
//
// Calls to Enter and Exit are always paired in nested order.
Exit func(n int)
}
Euler visits a graph using an Euler tour.
For a tree, the Euler tour is well-defined and unique (given an ordering of the children of a node). For a general graph, this uses the tree formed by the pre-order traversal of the graph.
type NodeMarks ¶
type NodeMarks struct {
// contains filtered or unexported fields
}
NodeMarks is a structure for marking nodes in a graph.
func NewNodeMarks ¶
func NewNodeMarks() *NodeMarks
NewNodeMarks returns a node mark set with no marks set.
type SCCFlags ¶
type SCCFlags int
SCCFlags is a set of optional analyses to perform when constructing strongly-connected components.
const ( // SCCSubnodeComponent instructs SCC to record a mapping from // subnode to component ID containing that subnode. SCCSubnodeComponent SCCFlags = 1 << iota // SCCEdges instructs SCC to record edges between components. // Otherwise, the resulting SCC graph will have a node for // each strongly-connected component, but no edges. SCCEdges )
type SCCGraph ¶
type SCCGraph struct {
// contains filtered or unexported fields
}
SCCGraph is a set of strongly-connected components of another graph.
Each strongly-connected component is a node in this graph. The components are numbered in reverse topological sort order.
If the graph was constructed with flag SCCEdges, then it also has edges between the components that follow the edges in the underlying graph.
func SCC ¶
SCC computes the strongly-connected components of graph g.
This implements Tarjan's strongly connected components algorithm [1]. It runs in O(V + E) time and O(V) space.
[1] Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing, 1 (2): 146–160.
func (*SCCGraph) Out ¶
Out returns the IDs of the components for which there are any edges in the underlying graph from component cid.
Graph g must have been constructed with flag SCCEdges. Otherwise this returns nil.
func (*SCCGraph) SubnodeComponent ¶
SubnodeComponent returns the component ID (a node ID in g) of sub-graph node subID (a node ID in the underlying graph).
Graph g must have been constructed with flag SCCSubnodeComponent.
Source Files