topo

Documentation

Index

• func BronKerbosch(g graph.Undirected) [][]graph.Node
• func ConnectedComponents(g graph.Undirected) [][]graph.Node
• func CyclesIn(g graph.Directed) [][]graph.Node
• func IsPathIn(g graph.Graph, path []graph.Node) bool
• func Sort(g graph.Directed) (sorted []graph.Node, err error)
• func TarjanSCC(g graph.Directed) [][]graph.Node
• func VertexOrdering(g graph.Undirected) (order []graph.Node, cores [][]graph.Node)
• type Unorderable
  • func (e Unorderable) Error() string

Functions

func BronKerbosch

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

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

func ConnectedComponents

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

ConnectedComponents returns the connected components of the undirected graph g.

func CyclesIn

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

CyclesIn 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 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 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 VertexOrdering

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

VertexOrdering returns the vertex ordering and the k-cores of the undirected graph g.

Types

type Unorderable

type Unorderable [][]graph.Node

Unorderable is an error containing sets of unorderable graph.Nodes.

func (Unorderable) Error

func (e Unorderable) Error() string

Error satisfies the error interface.