package toposort

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

Index ¶

• Constants
• func VertexFeatures(ctx *adt.OpContext, v *adt.Vertex) []adt.Feature
• 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

Constants ¶

const (
	NodeUnsorted = -1
)

Functions ¶

func VertexFeatures ¶

func VertexFeatures(ctx *adt.OpContext, v *adt.Vertex) []adt.Feature

Types ¶

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. We first calculate the strongly-connected-components (SCCs) of the graph. If the graph has no cycles then there will be 1 SCC per graph node, which we then walk topologically. When there is a choice as to which SCC to enter into next, a lexicographical comparison is done, and minimum feature chosen.

If the graph has cycles, then there will be at least one SCC containing several nodes. When we choose to enter this SCC, we use a lexicographical ordering of its nodes. This avoids the need for expensive and complex analysis of cycles: the maximum possible number of cycles rises with the factorial of the number of nodes in a component.

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
}

Source Files ¶

graph.go scc.go vertex.go