topo

func BronKerbosch ¶

func BronKerbosch(g graph.Undirected) [][]graph.Node

BronKerbosch returns the set of maximal cliques of the undirected graph g.

func CliqueGraph ¶

func CliqueGraph(dst Builder, g graph.Undirected)

CliqueGraph builds the clique graph of g in dst using Clique and CliqueGraphEdge nodes and edges. The nodes returned by calls to Nodes on the nodes and edges of the constructed graph are the cliques and the common nodes between cliques respectively. The dst graph is not cleared.

func ConnectedComponents ¶

func ConnectedComponents(g graph.Undirected) [][]graph.Node

ConnectedComponents returns the connected components of the undirected graph g.

func DegeneracyOrdering ¶

func DegeneracyOrdering(g graph.Undirected) (order []graph.Node, cores [][]graph.Node)

DegeneracyOrdering returns the degeneracy ordering and the k-cores of the undirected graph g.

func DirectedCyclesIn ¶

func DirectedCyclesIn(g graph.Directed) [][]graph.Node

DirectedCyclesIn returns the set of elementary cycles in the graph g.

func IsPathIn ¶

func IsPathIn(g graph.Graph, path []graph.Node) bool

IsPathIn returns whether path is a path in g.

As special cases, IsPathIn returns true for a zero length path or for a path of length 1 when the node in path exists in the graph.

func KCore ¶

func KCore(k int, g graph.Undirected) []graph.Node

KCore returns the k-core of the undirected graph g with nodes in an optimal ordering for the coloring number.

func PathExistsIn ¶

func PathExistsIn(g graph.Graph, from, to graph.Node) bool

PathExistsIn returns whether there is a path in g starting at from extending to to.

PathExistsIn exists as a helper function. If many tests for path existence are being performed, other approaches will be more efficient.

func Sort ¶

func Sort(g graph.Directed) (sorted []graph.Node, err error)

Sort performs a topological sort of the directed graph g returning the 'from' to 'to' sort order. If a topological ordering is not possible, an Unorderable error is returned listing cyclic components in g with each cyclic component's members sorted by ID. When an Unorderable error is returned, each cyclic component's topological position within the sorted nodes is marked with a nil graph.Node.

func SortStabilized ¶

func SortStabilized(g graph.Directed, order func([]graph.Node)) (sorted []graph.Node, err error)

SortStabilized performs a topological sort of the directed graph g returning the 'from' to 'to' sort order, or the order defined by the in place order sort function where there is no unambiguous topological ordering. If a topological ordering is not possible, an Unorderable error is returned listing cyclic components in g with each cyclic component's members sorted by the provided order function. If order is nil, nodes are ordered lexically by node ID. When an Unorderable error is returned, each cyclic component's topological position within the sorted nodes is marked with a nil graph.Node.

func TarjanSCC ¶

func TarjanSCC(g graph.Directed) [][]graph.Node

TarjanSCC returns the strongly connected components of the graph g using Tarjan's algorithm.

A strongly connected component of a graph is a set of vertices where it's possible to reach any vertex in the set from any other (meaning there's a cycle between them.)

Generally speaking, a directed graph where the number of strongly connected components is equal to the number of nodes is acyclic, unless you count reflexive edges as a cycle (which requires only a little extra testing.)

func UndirectedCyclesIn ¶

func UndirectedCyclesIn(g graph.Undirected) [][]graph.Node

UndirectedCyclesIn returns a set of cycles that forms a cycle basis in the graph g. Any cycle in g can be constructed as a symmetric difference of its elements.