Documentation

Overview

    Package topo provides graph topology analysis functions.

    Index

    Examples

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    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 Equal

              func Equal(a, b graph.Graph) bool

                Equal returns whether two graphs are topologically equal. To be considered topologically equal, a and b must have identical sets of nodes and be identically traversable.

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

                            Example (TwoSAT)
                            Output:
                            
                            system 0 is not satisfiable
                            system 1 is satisfiable: 𝑥_a:true 𝑥_b:true 𝑥_c:true 𝑥_d:true 𝑥_e:true 𝑥_f:true 𝑥_g:false 𝑥_h:true 𝑥_i:true 𝑥_j:false 𝑥_k:true 𝑥_l:true
                            system 2 is satisfiable: Gonum:true fun:true
                            

                            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.

                              Types

                              type Builder

                              type Builder interface {
                              	AddNode(graph.Node)
                              	SetEdge(graph.Edge)
                              }

                                Builder is a pure topological graph construction type.

                                type Clique

                                type Clique struct {
                                	// contains filtered or unexported fields
                                }

                                  Clique is a node in a clique graph.

                                  func (Clique) ID

                                  func (n Clique) ID() int64

                                    ID returns the node ID.

                                    func (Clique) Nodes

                                    func (n Clique) Nodes() []graph.Node

                                      Nodes returns the nodes in the clique.

                                      type CliqueGraphEdge

                                      type CliqueGraphEdge struct {
                                      	// contains filtered or unexported fields
                                      }

                                        CliqueGraphEdge is an edge in a clique graph.

                                        func (CliqueGraphEdge) From

                                        func (e CliqueGraphEdge) From() graph.Node

                                          From returns the from node of the edge.

                                          func (CliqueGraphEdge) Nodes

                                          func (e CliqueGraphEdge) Nodes() []graph.Node

                                            Nodes returns the common nodes in the cliques of the underlying graph corresponding to the from and to nodes in the clique graph.

                                            func (CliqueGraphEdge) ReversedEdge

                                            func (e CliqueGraphEdge) ReversedEdge() graph.Edge

                                              ReversedEdge returns a new CliqueGraphEdge with the edge end points swapped. The nodes of the new edge are shared with the receiver.

                                              func (CliqueGraphEdge) To

                                              func (e CliqueGraphEdge) To() graph.Node

                                                To returns the to node of the edge.

                                                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.