toposort

package
v0.11.2 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jan 22, 2025 License: Apache-2.0 Imports: 6 Imported by: 0

Documentation

Index

Constants

View Source
const (
	NodeUnsorted     = -1
	NodeInCurrentScc = -2
)

Variables

This section is empty.

Functions

func VertexFeatures

func VertexFeatures(index adt.StringIndexer, v *adt.Vertex) []adt.Feature

Types

type Cycle

type Cycle struct {
	Nodes Nodes
}

func (*Cycle) RotateToStartAt

func (cycle *Cycle) RotateToStartAt(start *Node)

type Graph

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

func (*Graph) Sort

func (self *Graph) Sort(index adt.StringIndexer) []adt.Feature

Sort the features of the graph into a single slice.

As far as possible, a topological sort is used.

Whenever there is choice as to which feature should occur next, a lexicographical comparison is done, and minimum feature chosen.

Whenever progress cannot be made due to needing to enter into cycles, the cycle to enter into, and the node of that cycle with which to start, is selected based on:

  1. minimising the number of incoming edges that are violated
  2. chosing a node which was reachable as early as possible
  3. chosing a node with a smaller feature name (lexicographical)

func (*Graph) StronglyConnectedComponents

func (graph *Graph) StronglyConnectedComponents() []*StronglyConnectedComponent

Calculate the Strongly Connected Components of the graph. https://en.wikipedia.org/wiki/Strongly_connected_component

The components returned are topologically sorted (forwards), and form a DAG (this is the "condensation graph").

type GraphBuilder

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

func NewGraphBuilder

func NewGraphBuilder() *GraphBuilder

func (*GraphBuilder) AddEdge

func (builder *GraphBuilder) AddEdge(from, to adt.Feature)

Adds an edge between the two features. Nodes for the features will be created if they don't already exist. This method is idempotent: multiple calls with the same arguments will not create multiple edges, nor error.

func (*GraphBuilder) Build

func (builder *GraphBuilder) Build() *Graph

func (*GraphBuilder) EnsureNode

func (builder *GraphBuilder) EnsureNode(feature adt.Feature) *Node

Ensure that a node for this feature exists. This is necessary for features that are not necessarily connected to any other feature.

type Node

type Node struct {
	Feature  adt.Feature
	Outgoing Nodes
	Incoming Nodes
	// contains filtered or unexported fields
}

func (*Node) IsSorted

func (n *Node) IsSorted() bool

func (*Node) Name

func (n *Node) Name(index adt.StringIndexer) string

type Nodes

type Nodes []*Node

func (Nodes) Features

func (nodes Nodes) Features() []adt.Feature

type StronglyConnectedComponent

type StronglyConnectedComponent struct {
	Nodes    Nodes
	Outgoing []*StronglyConnectedComponent
	Incoming []*StronglyConnectedComponent
	// contains filtered or unexported fields
}

func (*StronglyConnectedComponent) ElementaryCycles

func (scc *StronglyConnectedComponent) ElementaryCycles() []*Cycle

Calculate the Elementary Cycles (EC) within the current Strongly Connected Component (SCC).

If the component contains no cycles (by definition, this means the component contains only a single node), then the slice returned will be empty.

In general:

  1. If a component contains two or more nodes then it contains at least one cycle.
  2. A single node can be involved in many cycles.
  3. This method finds all cycles within a component, but does not include cycles that are merely rotations of each other. I.e. every cycle is unique, ignoring rotations.
  4. The cycles returned are unsorted: each cycle is itself in no particular rotation, and the complete slice of cycles is similarly unsorted.

The complexity of this algorithm is O((n+e)*c) where

  • n: number of nodes in the SCC
  • e: number of edges between the nodes in the SCC
  • c: number of cycles discovered

Donald B Johnson: Finding All the Elementary Circuits of a Directed Graph. SIAM Journal on Computing. Volumne 4, Nr. 1 (1975), pp. 77-84.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL