package toposort

import "cuelang.org/go/internal/core/toposort"

Index ¶

• Constants
• func VertexFeatures(ctx *adt.OpContext, v *adt.Vertex) []adt.Feature
• type Cycle
• func (cycle *Cycle) RotateToStartAt(start *Node)
• type Graph
• func (graph *Graph) Sort(index adt.StringIndexer) []adt.Feature
• func (graph *Graph) StronglyConnectedComponents() []*StronglyConnectedComponent
• type GraphBuilder
• func NewGraphBuilder(allowEdges bool) *GraphBuilder
• func (builder *GraphBuilder) AddEdge(from, to adt.Feature)
• func (builder *GraphBuilder) Build() *Graph
• func (builder *GraphBuilder) EnsureNode(feature adt.Feature) *Node
• type Node
• func (n *Node) IsSorted() bool
• func (n *Node) SafeName(index adt.StringIndexer) string
• type Nodes
• func (nodes Nodes) Features() []adt.Feature
• type StronglyConnectedComponent
• func (scc *StronglyConnectedComponent) ElementaryCycles() []*Cycle

Constants ¶

const (
	NodeUnsorted     = -1
	NodeInCurrentScc = -2
)

Functions ¶

func VertexFeatures ¶

func VertexFeatures(ctx *adt.OpContext, 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 (graph *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(allowEdges bool) *GraphBuilder

NewGraphBuilder is the constructor for GraphBuilder.

If you disallow edges, then nodes can still be added to the graph, and the GraphBuilder.AddEdge method will not error, but edges will never be added between nodes. This has the effect that topological ordering is not possible.

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) SafeName ¶

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

SafeName returns a string useful for debugging, regardless of the type of the feature. So for IntLabels, you'll get back `1`, `10` etc; for identifiers, you may get back a string with quotes in it, eg `"runs-on"`. So this is not useful for comparisons, but it is useful (and safe) for debugging.

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.

Source Files ¶

cycles.go graph.go scc.go vertex.go