dag

package
v0.2.2 Latest Latest
Warning

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

 Go to latest Published: Dec 23, 2025 License: Apache-2.0 Imports: 3 Imported by: 0

Documentation

Overview

Package dag provides a directed acyclic graph (DAG) optimized for row-based layered layouts used in tower visualizations.

Overview

Stacktower renders dependency graphs as physical towers where blocks rest on what they depend on. This package provides the core data structure that organizes nodes into horizontal rows (layers), with edges connecting nodes in consecutive rows only.

The row-based constraint is essential for the Sugiyama-style layered graph drawing that powers tower visualizations. It enables efficient crossing detection and ordering algorithms.

Basic Usage

Create a new graph with New, add nodes with DAG.AddNode, and edges with DAG.AddEdge. Nodes must have unique IDs, and edges can only connect existing nodes in consecutive rows (From.Row+1 == To.Row): 

g := dag.New(nil)
g.AddNode(dag.Node{ID: "app", Row: 0})
g.AddNode(dag.Node{ID: "lib", Row: 1})
g.AddEdge(dag.Edge{From: "app", To: "lib"})

Query the graph structure with DAG.Children, DAG.Parents, DAG.NodesInRow, and related methods. Use DAG.Validate to verify structural integrity before rendering or transformations.

Node Types

The package supports three node kinds to handle real-world graph structures:

Subdivider nodes maintain a [Node.MasterID] linking back to their origin, allowing them to be visually merged into continuous vertical blocks during rendering. Auxiliary nodes act as "separator beams" that resolve impossible crossing patterns by grouping edges through a shared intermediate.

Edge Crossings

A key challenge in tower layouts is minimizing (ideally eliminating) edge crossings. When two edges cross, the corresponding blocks cannot physically support each other in a stacked tower.

The CountCrossings and CountLayerCrossings functions use a Fenwick tree (binary indexed tree) to count inversions in O(E log V) time, enabling fast evaluation of millions of candidate orderings during optimization.

Metadata

Both nodes and the graph itself support arbitrary metadata via Metadata maps. This is used to store package information (version, description, repository URL) and render options (style, seed) that flow through the pipeline. Metadata maps are never nil after creation - empty maps are automatically initialized.

Concurrency

DAG instances are not safe for concurrent use. Callers must synchronize access if multiple goroutines read or modify the same graph. Immutable operations like counting crossings on a read-only graph can safely run in parallel across different goroutines.

The [transform] subpackage provides graph transformations:

  • Transitive reduction (remove redundant edges)
  • Edge subdivision (break long edges into segments)
  • Span overlap resolution (insert separator beams)
  • Layer assignment (assign rows based on depth)

The [perm] subpackage provides permutation algorithms including the PQ-tree data structure for efficiently generating only valid orderings that preserve crossing-free constraints.

[transform]: github.com/matzehuels/stacktower/pkg/dag/transform [perm]: github.com/matzehuels/stacktower/pkg/dag/perm

Index

Examples

Constants

This section is empty.

Variables

View Source 
var (
	// ErrInvalidNodeID is returned by [DAG.AddNode] and [DAG.RenameNode] when
	// the node ID is empty. All nodes must have non-empty identifiers.
	ErrInvalidNodeID = errors.New("node ID must not be empty")

	// ErrDuplicateNodeID is returned by [DAG.AddNode] and [DAG.RenameNode] when
	// a node with the same ID already exists in the graph. Node IDs must be unique.
	ErrDuplicateNodeID = errors.New("duplicate node ID")

	// ErrUnknownSourceNode is returned by [DAG.AddEdge] when the From node
	// does not exist, or by [DAG.RenameNode] when the old ID is not found.
	ErrUnknownSourceNode = errors.New("unknown source node")

	// ErrUnknownTargetNode is returned by [DAG.AddEdge] when the To node
	// does not exist in the graph.
	ErrUnknownTargetNode = errors.New("unknown target node")

	// ErrInvalidEdgeEndpoint is returned by [DAG.Validate] when an edge
	// references a node that doesn't exist. This indicates graph corruption.
	ErrInvalidEdgeEndpoint = errors.New("invalid edge endpoint")

	// ErrNonConsecutiveRows is returned by [DAG.Validate] when an edge
	// connects nodes that are not in adjacent rows (From.Row+1 != To.Row).
	// All edges must connect consecutive rows for layered layouts.
	ErrNonConsecutiveRows = errors.New("edges must connect consecutive rows")

	// ErrGraphHasCycle is returned by [DAG.Validate] when a cycle is detected.
	// This indicates the graph is not a valid DAG. Cycles are detected using
	// depth-first search with white/gray/black coloring.
	ErrGraphHasCycle = errors.New("graph contains a cycle")
)

Functions

func CountCrossings 

func CountCrossings(g *DAG, orders map[int][]string) int

CountCrossings returns the total number of edge crossings for the given row orderings. It sums the crossings between each pair of consecutive rows. The orders map should contain node IDs in left-to-right order for each row. Rows without entries in the map are treated as empty.

Example: 

orders := map[int][]string{
    0: {"app", "cli"},           // row 0: app on left, cli on right
    1: {"lib1", "lib2", "lib3"}, // row 1: three nodes
}
crossings := dag.CountCrossings(g, orders)

This function is typically used during optimization to evaluate candidate orderings. It runs in O(R × E log V) time where R is the number of rows, E is edges per layer, and V is nodes per layer.

Example 
package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
)

func main() {
	// Count total crossings across all row pairs
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "A", Row: 0})
	_ = g.AddNode(dag.Node{ID: "B", Row: 0})
	_ = g.AddNode(dag.Node{ID: "C", Row: 1})
	_ = g.AddNode(dag.Node{ID: "D", Row: 1})
	_ = g.AddNode(dag.Node{ID: "E", Row: 2})
	_ = g.AddNode(dag.Node{ID: "F", Row: 2})

	// Create a crossing pattern
	_ = g.AddEdge(dag.Edge{From: "A", To: "D"})
	_ = g.AddEdge(dag.Edge{From: "B", To: "C"})
	_ = g.AddEdge(dag.Edge{From: "C", To: "F"})
	_ = g.AddEdge(dag.Edge{From: "D", To: "E"})

	orders := map[int][]string{
		0: {"A", "B"},
		1: {"C", "D"},
		2: {"E", "F"},
	}

	total := dag.CountCrossings(g, orders)
	fmt.Println("Total crossings:", total)
}

Output:

Total crossings: 2

func CountCrossingsIdx 

func CountCrossingsIdx(edges [][]int, upperPerm, lowerPerm []int, ws *CrossingWorkspace) int

CountCrossingsIdx counts crossings using index-based edges and permutations. This is an optimized version for the branch-and-bound search that avoids string lookups by using integer indices throughout.

The edges parameter should be a slice where edges[i] contains the indices (into the lower row) of all children of upper row node i. The upperPerm and lowerPerm parameters are permutations (orderings) of node indices. The ws parameter must be a workspace created with NewCrossingWorkspace with maxWidth >= len(lowerPerm).

This function is typically only used internally by optimization code that needs to evaluate thousands of orderings per second. Most callers should use CountCrossings or CountLayerCrossings instead.

Performance: O(E log V) where E is the total number of edges and V is len(lowerPerm).

func CountLayerCrossings 

func CountLayerCrossings(g *DAG, upper, lower []string) int

CountLayerCrossings counts edge crossings between two adjacent rows using a Fenwick tree (binary indexed tree) for O(E log V) performance where E is the number of edges between the rows and V is the number of nodes in the lower row.

Two edges (u1,v1) and (u2,v2) cross if and only if: 

pos(u1) < pos(u2) AND pos(v1) > pos(v2)

This is equivalent to counting inversions in the sequence of target positions when edges are sorted by source position. The Fenwick tree enables efficient inversion counting compared to the naive O(E²) algorithm.

Returns 0 if either row is empty or nil, as no crossings can exist without edges.

Example 
package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
)

func main() {
	// Count edge crossings between two rows
	// This uses a Fenwick tree for O(E log V) performance
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "a", Row: 0})
	_ = g.AddNode(dag.Node{ID: "b", Row: 0})
	_ = g.AddNode(dag.Node{ID: "x", Row: 1})
	_ = g.AddNode(dag.Node{ID: "y", Row: 1})

	// Create crossing edges: a→y, b→x (these cross when a is left of b)
	_ = g.AddEdge(dag.Edge{From: "a", To: "y"})
	_ = g.AddEdge(dag.Edge{From: "b", To: "x"})

	upper := []string{"a", "b"}
	lower := []string{"x", "y"}
	crossings := dag.CountLayerCrossings(g, upper, lower)
	fmt.Println("Crossings:", crossings)

	// Reorder to eliminate crossing
	upper = []string{"b", "a"}
	crossings = dag.CountLayerCrossings(g, upper, lower)
	fmt.Println("After reorder:", crossings)
}

Output:

Crossings: 1
After reorder: 0

func CountPairCrossings 

func CountPairCrossings(g *DAG, left, right string, adjOrder []string, useParents bool) int

CountPairCrossings counts how many crossings would result from swapping two adjacent nodes (left and right) in their row. If useParents is true, considers edges to the row above; otherwise, considers edges to the row below.

This is used by local search heuristics (e.g., adjacent node swapping) to decide whether a swap would reduce crossings. The adjOrder slice should contain the node IDs of the adjacent row in left-to-right order.

Returns 0 if either node has no edges to the adjacent row, or if no crossings would occur. This function does not modify the graph.

func CountPairCrossingsWithPos 

func CountPairCrossingsWithPos(g *DAG, left, right string, adjPos map[string]int, useParents bool) int

CountPairCrossingsWithPos is like CountPairCrossings but takes a precomputed position map for the adjacent row. This avoids repeated calls to PosMap when checking multiple swaps against the same adjacent row.

The adjPos map should map node IDs to their positions (0-indexed) in the adjacent row. Nodes not in the map are ignored.

func NodeIDs 

func NodeIDs(nodes []*Node) []string

NodeIDs extracts the ID from each node in a slice. Returns a new slice containing the IDs in the same order as the input. Returns an empty slice for a nil or empty input.

func NodePosMap 

func NodePosMap(nodes []*Node) map[string]int

NodePosMap creates a position lookup map from a slice of nodes. The returned map maps each node ID to its index in the slice. This is a convenience wrapper around PosMap for node slices. Returns an empty map for a nil or empty slice.

func PosMap 

func PosMap(ids []string) map[string]int

PosMap creates a position lookup map from a slice of node IDs. The returned map maps each ID to its index in the slice. This is commonly used to convert node orderings into fast position lookups for crossing calculations. Returns an empty map for a nil or empty slice.

Example 
package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
)

func main() {
	// Convert a node ordering to a position lookup map
	ordering := []string{"app", "lib", "core"}
	positions := dag.PosMap(ordering)

	fmt.Println("Position of 'lib':", positions["lib"])
	fmt.Println("Position of 'core':", positions["core"])
}

Output:

Position of 'lib': 1
Position of 'core': 2

Types

type CrossingWorkspace 

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

CrossingWorkspace provides reusable buffers for crossing calculations to avoid repeated allocations. Create with NewCrossingWorkspace and reuse across multiple calls to CountCrossingsIdx. This optimization matters when evaluating millions of candidate orderings during branch-and-bound search.

The workspace is not safe for concurrent use - each goroutine should have its own.

func NewCrossingWorkspace 

func NewCrossingWorkspace(maxWidth int) *CrossingWorkspace

NewCrossingWorkspace creates a workspace for counting crossings efficiently. The maxWidth parameter should be the maximum number of nodes in any single row across all calls that will use this workspace. Using a workspace smaller than needed will cause CountCrossingsIdx to produce incorrect results.

For typical use, set maxWidth to the size of the largest row in your graph: 

maxWidth := 0
for _, row := range g.RowIDs() {
    if n := len(g.NodesInRow(row)); n > maxWidth {
        maxWidth = n
    }
}
ws := dag.NewCrossingWorkspace(maxWidth)
Example 
package main

import (
	"github.com/matzehuels/stacktower/pkg/dag"
)

func main() {
	// Reuse a workspace for efficient crossing calculations
	// Determine maximum row width in your graph
	maxWidth := 10

	// Create a workspace sized for that maximum
	ws := dag.NewCrossingWorkspace(maxWidth)

	// Now use ws with CountCrossingsIdx for optimization loops
	// (typically used internally by ordering algorithms)
	_ = ws
}

type DAG 

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

DAG is a directed acyclic graph optimized for row-based layered layouts. Nodes are organized into horizontal rows (layers), and edges can only connect nodes in consecutive rows. This structure enables efficient crossing reduction algorithms for tower visualizations.

The zero value is not usable - use New to create a valid DAG instance. DAG is not safe for concurrent use without external synchronization.

Example (Basic) 
package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
)

func main() {
	// Create a simple dependency graph: app → lib → core
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "app", Row: 0})
	_ = g.AddNode(dag.Node{ID: "lib", Row: 1})
	_ = g.AddNode(dag.Node{ID: "core", Row: 2})
	_ = g.AddEdge(dag.Edge{From: "app", To: "lib"})
	_ = g.AddEdge(dag.Edge{From: "lib", To: "core"})

	fmt.Println("Nodes:", g.NodeCount())
	fmt.Println("Edges:", g.EdgeCount())
	fmt.Println("Rows:", g.RowCount())
}

Output:

Nodes: 3
Edges: 2
Rows: 3
Example (Metadata) 
package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
)

func main() {
	// Attach package metadata to nodes
	g := dag.New(dag.Metadata{"name": "my-project"})
	_ = g.AddNode(dag.Node{
		ID:  "fastapi",
		Row: 0,
		Meta: dag.Metadata{
			"version":     "0.100.0",
			"description": "FastAPI framework",
			"repo_stars":  70000,
		},
	})

	node, _ := g.Node("fastapi")
	fmt.Println("Package:", node.ID)
	fmt.Println("Version:", node.Meta["version"])
}

Output:

Package: fastapi
Version: 0.100.0
Example (Traversal) 
package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
)

func main() {
	// Build a graph with fan-out: app depends on auth and cache
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "app", Row: 0})
	_ = g.AddNode(dag.Node{ID: "auth", Row: 1})
	_ = g.AddNode(dag.Node{ID: "cache", Row: 1})
	_ = g.AddEdge(dag.Edge{From: "app", To: "auth"})
	_ = g.AddEdge(dag.Edge{From: "app", To: "cache"})

	// Query relationships
	fmt.Println("Children of app:", g.Children("app"))
	fmt.Println("Parents of auth:", g.Parents("auth"))
	fmt.Println("Out-degree of app:", g.OutDegree("app"))
}

Output:

Children of app: [auth cache]
Parents of auth: [app]
Out-degree of app: 2

func New 

func New(meta Metadata) *DAG

New creates an empty DAG with optional graph-level metadata. The metadata parameter can be nil, in which case an empty map is created. Graph-level metadata is typically used to store rendering options.

func (*DAG) AddEdge 

func (d *DAG) AddEdge(e Edge) error

AddEdge adds a directed edge between two existing nodes. Returns ErrUnknownSourceNode if the From node doesn't exist, or ErrUnknownTargetNode if the To node doesn't exist. The edge's Meta field is automatically initialized to an empty map if nil.

AddEdge does not validate that From.Row+1 == To.Row - use Validate to check this constraint after building the graph. Multiple edges between the same nodes are allowed (though unusual in dependency graphs).

func (*DAG) AddNode 

func (d *DAG) AddNode(n Node) error

AddNode adds a node to the graph and automatically indexes it by its Row. Returns ErrInvalidNodeID if the node ID is empty, or ErrDuplicateNodeID if a node with the same ID already exists. The node's Meta field is automatically initialized to an empty map if nil.

Node IDs must be unique across the entire graph, regardless of row assignment.

func (*DAG) Children 

func (d *DAG) Children(id string) []string

Children returns the IDs of nodes that this node has edges to (dependencies). Returns nil if the node has no children or doesn't exist. The returned slice should not be modified - use it as a read-only view.

func (*DAG) ChildrenInRow 

func (d *DAG) ChildrenInRow(id string, row int) []string

ChildrenInRow returns children of the node that are in the specified row. This is useful for row-by-row traversals in layered layouts. Returns nil if the node has no children in that row or doesn't exist.

Example 
package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
)

func main() {
	// Query children in a specific row
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "a", Row: 0})
	_ = g.AddNode(dag.Node{ID: "b", Row: 1})
	_ = g.AddNode(dag.Node{ID: "c", Row: 2})
	_ = g.AddNode(dag.Node{ID: "d", Row: 2})
	_ = g.AddEdge(dag.Edge{From: "a", To: "b"})
	_ = g.AddEdge(dag.Edge{From: "a", To: "c"}) // skips row 1
	_ = g.AddEdge(dag.Edge{From: "a", To: "d"}) // skips row 1

	// Find children specifically in row 2
	childrenInRow2 := g.ChildrenInRow("a", 2)
	fmt.Println("Children in row 2:", len(childrenInRow2))
}

Output:

Children in row 2: 2

func (*DAG) EdgeCount 

func (d *DAG) EdgeCount() int

EdgeCount returns the number of edges in the graph.

func (*DAG) Edges 

func (d *DAG) Edges() []Edge

Edges returns a copy of all edges in the graph. The order matches insertion order. Modifications to the returned slice or its edge structs do not affect the graph.

func (*DAG) InDegree 

func (d *DAG) InDegree(id string) int

InDegree returns the number of incoming edges to the node. Returns 0 if the node doesn't exist.

func (*DAG) MaxRow 

func (d *DAG) MaxRow() int

MaxRow returns the highest row index, or 0 if the graph is empty. For a non-empty graph, this is the bottom-most layer.

func (*DAG) Meta 

func (d *DAG) Meta() Metadata

Meta returns the graph-level metadata map. The returned map is never nil and can be safely modified.

func (*DAG) Node 

func (d *DAG) Node(id string) (*Node, bool)

Node returns the node with the given ID and true, or nil and false if not found. The returned node pointer refers to the actual node in the graph, so modifications affect the graph (except for ID changes - use RenameNode instead).

func (*DAG) NodeCount 

func (d *DAG) NodeCount() int

NodeCount returns the number of nodes in the graph.

func (*DAG) Nodes 

func (d *DAG) Nodes() []*Node

Nodes returns all nodes in the graph. The order is not guaranteed. The returned slice contains pointers to the actual node structs, so modifications affect the graph.

func (*DAG) NodesInRow 

func (d *DAG) NodesInRow(row int) []*Node

NodesInRow returns all nodes assigned to the given row. Returns nil if the row is empty or doesn't exist. The returned slice contains pointers to the actual nodes, so modifications affect the graph. The order is insertion order (order in which AddNode or SetRows added them).

func (*DAG) OutDegree 

func (d *DAG) OutDegree(id string) int

OutDegree returns the number of outgoing edges from the node. Returns 0 if the node doesn't exist.

func (*DAG) Parents 

func (d *DAG) Parents(id string) []string

Parents returns the IDs of nodes that have edges to this node (dependents). Returns nil if the node has no parents or doesn't exist. The returned slice should not be modified - use it as a read-only view.

func (*DAG) ParentsInRow 

func (d *DAG) ParentsInRow(id string, row int) []string

ParentsInRow returns parents of the node that are in the specified row. This is useful for row-by-row traversals in layered layouts. Returns nil if the node has no parents in that row or doesn't exist.

func (*DAG) RemoveEdge 

func (d *DAG) RemoveEdge(from, to string)

RemoveEdge removes the edge from→to if it exists. No error is returned if the edge does not exist. If multiple edges exist between the same nodes, only the first is removed.

func (*DAG) RenameNode 

func (d *DAG) RenameNode(oldID, newID string) error

RenameNode changes a node's ID, updating all edges and indices. Returns ErrInvalidNodeID if newID is empty, ErrUnknownSourceNode if oldID doesn't exist, or ErrDuplicateNodeID if newID is already in use.

This is an O(N+E) operation where N is the number of nodes and E is the number of edges, as all adjacency lists must be updated.

func (*DAG) RowCount 

func (d *DAG) RowCount() int

RowCount returns the number of distinct rows (layers) in the graph. Returns 0 for an empty graph. Rows don't need to be consecutive - a graph with nodes in rows 0 and 5 has RowCount() == 2.

func (*DAG) RowIDs 

func (d *DAG) RowIDs() []int

RowIDs returns all row indices in sorted ascending order. Returns an empty slice for an empty graph. Use this to iterate through rows from top to bottom.

func (*DAG) SetRows 

func (d *DAG) SetRows(rows map[string]int)

SetRows updates the row assignments for nodes and rebuilds the row index. Nodes not present in the rows map retain their current row assignment. This is typically used after layer assignment algorithms compute optimal depths.

The row index (used by NodesInRow) is completely rebuilt, so this operation is O(N) where N is the total number of nodes.

func (*DAG) Sinks 

func (d *DAG) Sinks() []*Node

Sinks returns nodes with no outgoing edges (leaves/terminals). These are typically low-level libraries with no dependencies. The order is not guaranteed. Returns nil for an empty graph.

func (*DAG) Sources 

func (d *DAG) Sources() []*Node

Sources returns nodes with no incoming edges (roots/entry points). These are typically application entry points or top-level packages. The order is not guaranteed. Returns nil for an empty graph.

Example 
package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
)

func main() {
	// Find root nodes (packages with no dependencies above them)
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "app", Row: 0})
	_ = g.AddNode(dag.Node{ID: "cli", Row: 0})
	_ = g.AddNode(dag.Node{ID: "shared", Row: 1})
	_ = g.AddEdge(dag.Edge{From: "app", To: "shared"})
	_ = g.AddEdge(dag.Edge{From: "cli", To: "shared"})

	sources := g.Sources()
	fmt.Println("Source count:", len(sources))
}

Output:

Source count: 2

func (*DAG) Validate 

func (d *DAG) Validate() error

Validate checks graph integrity and returns nil if valid. It verifies two constraints:

  1. All edges connect existing nodes in consecutive rows (From.Row+1 == To.Row)
  2. The graph is acyclic (no directed cycles exist)

Returns ErrInvalidEdgeEndpoint if an edge references a missing node, ErrNonConsecutiveRows if edges don't connect adjacent rows, or ErrGraphHasCycle if a cycle is detected. Use this before rendering or applying transformations that assume a valid DAG.

Cycle detection runs in O(N+E) time using depth-first search.

Example 
package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
)

func main() {
	// Validate checks for consecutive rows and cycles
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "a", Row: 0})
	_ = g.AddNode(dag.Node{ID: "b", Row: 1})
	_ = g.AddNode(dag.Node{ID: "c", Row: 2})
	_ = g.AddEdge(dag.Edge{From: "a", To: "b"})
	_ = g.AddEdge(dag.Edge{From: "b", To: "c"})

	if err := g.Validate(); err != nil {
		fmt.Println("Invalid:", err)
	} else {
		fmt.Println("Valid DAG")
	}
}

Output:

Valid DAG
Example (NonConsecutive) 
package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
)

func main() {
	// Edges must connect consecutive rows
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "a", Row: 0})
	_ = g.AddNode(dag.Node{ID: "b", Row: 2}) // skips row 1
	_ = g.AddEdge(dag.Edge{From: "a", To: "b"})

	if err := g.Validate(); err != nil {
		fmt.Println("Error:", err)
	}
}

Output:

Error: edges must connect consecutive rows

type Edge 

type Edge struct {
	From string   // Source node ID
	To   string   // Target node ID
	Meta Metadata // Arbitrary key-value metadata (never nil after AddEdge)
}

Edge represents a directed connection between two nodes in consecutive rows. For a valid edge, the target must be exactly one row below the source: dst.Row == src.Row + 1. This constraint is enforced by Validate.

type Metadata 

type Metadata map[string]any

Metadata stores arbitrary key-value pairs attached to nodes or the graph. It is commonly used to store package metadata (version, description, repo URL) or rendering options (style, seed). Metadata maps are never nil - they are automatically initialized to empty maps when needed.

type Node 

type Node struct {
	ID   string   // Unique identifier (also used as display label)
	Row  int      // Layer assignment (0 = root/top, increasing downward)
	Meta Metadata // Arbitrary key-value metadata (never nil after AddNode)

	// Kind indicates whether this is an original or synthetic node.
	Kind NodeKind
	// MasterID links subdivider chains back to their origin node.
	// For subdividers, EffectiveID() returns MasterID instead of ID.
	MasterID string
}

Node represents a vertex in the dependency graph with an assigned row (layer). Nodes can be original vertices from dependency data (NodeKindRegular) or synthetic nodes created during transformation (NodeKindSubdivider, NodeKindAuxiliary).

The zero value is not usable - ID and Row must be set before adding to a DAG.

Example (Synthetic) 
package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
)

func main() {
	// Synthetic nodes are created during graph transformation
	regular := dag.Node{ID: "lib", Kind: dag.NodeKindRegular}
	subdivider := dag.Node{ID: "lib_sub_1", Kind: dag.NodeKindSubdivider, MasterID: "lib"}
	auxiliary := dag.Node{ID: "Sep_1_a_b", Kind: dag.NodeKindAuxiliary}

	fmt.Println("Regular is synthetic:", regular.IsSynthetic())
	fmt.Println("Subdivider is synthetic:", subdivider.IsSynthetic())
	fmt.Println("Subdivider effective ID:", subdivider.EffectiveID())
	fmt.Println("Auxiliary is synthetic:", auxiliary.IsSynthetic())
}

Output:

Regular is synthetic: false
Subdivider is synthetic: true
Subdivider effective ID: lib
Auxiliary is synthetic: true

func (Node) EffectiveID 

func (n Node) EffectiveID() string

EffectiveID returns MasterID if set (for subdividers), otherwise the node's ID. This allows subdivider chains to be treated as a single logical entity during rendering, where they appear as continuous vertical blocks.

func (Node) IsAuxiliary 

func (n Node) IsAuxiliary() bool

IsAuxiliary reports whether the node is a helper for layout (e.g., separator beam). Auxiliary nodes are synthetic and resolve impossible crossing patterns.

func (Node) IsSubdivider 

func (n Node) IsSubdivider() bool

IsSubdivider reports whether the node was inserted to break a long edge. Subdivider nodes are synthetic and maintain a MasterID linking to their origin.

func (Node) IsSynthetic 

func (n Node) IsSynthetic() bool

IsSynthetic reports whether the node was created during graph transformation (subdivider or auxiliary), as opposed to an original graph vertex.

type NodeKind 

type NodeKind int

NodeKind distinguishes between original and synthetic nodes created during graph transformation. 

const (
	// NodeKindRegular represents an original graph node from dependency data.
	NodeKindRegular NodeKind = iota
	// NodeKindSubdivider represents a synthetic node inserted to subdivide a long edge.
	// Subdividers maintain a MasterID linking to their origin node.
	NodeKindSubdivider
	// NodeKindAuxiliary represents a helper node for layout (e.g., separator beams).
	// Auxiliary nodes resolve impossible crossing patterns by providing intermediate points.
	NodeKindAuxiliary
)

Source Files

View all Source files

Directories

Path Synopsis
Package perm provides permutation generation algorithms and the PQ-tree data structure for constrained ordering problems.
 Package perm provides permutation generation algorithms and the PQ-tree data structure for constrained ordering problems.
Package transform provides graph transformations that prepare a DAG for tower rendering.
 Package transform provides graph transformations that prepare a DAG for tower rendering.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.