transform

Documentation

Overview

Package transform provides graph transformations that prepare a DAG for tower rendering.

Overview

Real-world dependency graphs rarely arrive in a form suitable for direct tower visualization. This package provides a normalization pipeline that transforms arbitrary DAGs into a canonical form where:

• Edges connect only consecutive rows (no long-spanning edges)
• Redundant transitive edges are removed
• Impossible crossing patterns are resolved with separator beams
• Nodes are assigned to rows based on their depth from roots

The Normalize function applies the complete pipeline in the correct order.

Transitive Reduction

TransitiveReduction removes redundant edges that can be inferred through other paths. If A→B and B→C exist, then A→C is redundant and removed.

This is critical for tower layouts because transitive edges create impossible geometry—a block cannot simultaneously rest on something two floors down while also having direct contact.

Edge Subdivision

Subdivide breaks long edges (spanning multiple rows) into chains of single-row hops by inserting subdivider nodes. For example:

Before: app (row 0) → core (row 3)
After:  app → app_sub_1 → app_sub_2 → core

Subdivider nodes maintain a MasterID linking back to their origin, allowing them to be visually merged into continuous vertical blocks during rendering.

This also extends all sink nodes (leaves) to the bottom row, ensuring the tower has a flat foundation.

Span Overlap Resolution

ResolveSpanOverlaps handles "tangle motifs"—graph patterns that guarantee edge crossings regardless of ordering. The classic example is a complete bipartite subgraph where multiple parents share multiple children.

Rather than accepting unavoidable crossings, this function inserts auxiliary "separator beam" nodes that group the edges through a shared intermediate:

Before: auth→logging, auth→metrics, api→logging, api→metrics (guaranteed crossing)
After:  auth→sep, api→sep, sep→logging, sep→metrics (no crossing possible)

Layer Assignment

AssignLayers computes the row (layer) for each node based on its depth from source nodes (those with no incoming edges). This uses a topological traversal to ensure parents are always in rows above their children.

Cycle Breaking

BreakCycles detects and removes edges that create cycles. While dependency graphs should be acyclic, real-world data sometimes contains circular dependencies. This function removes the minimum edges needed to restore acyclicity using a DFS-based approach.

Goroutine Safety

All functions in this package modify the input DAG in place and are NOT safe for concurrent use. Callers must ensure exclusive access to the DAG during transformation. The DAG itself is not internally synchronized.

Usage

For most use cases, call Normalize which applies all transformations:

g := dag.New(nil)
// ... populate graph ...
result := transform.Normalize(g) // Modifies g in place, returns metrics
fmt.Printf("Removed %d cycles, %d transitive edges\n",
    result.CyclesRemoved, result.TransitiveEdgesRemoved)

To skip specific transformations, use NormalizeWithOptions:

result := transform.NormalizeWithOptions(g, transform.NormalizeOptions{
    SkipTransitiveReduction: true, // Keep all edges
    SkipSeparators:          true, // Accept crossings
})

For fine-grained control, apply transformations individually in this order:

transform.BreakCycles(g)
transform.TransitiveReduction(g)
transform.AssignLayers(g)
transform.Subdivide(g)
transform.ResolveSpanOverlaps(g)

Index

• func AssignLayers(g *dag.DAG)
• func BreakCycles(g *dag.DAG) int
• func ResolveSpanOverlaps(d *dag.DAG)
• func Subdivide(g *dag.DAG)
• func TransitiveReduction(g *dag.DAG)
• type NormalizeOptions
• type TransformResult
  • func Normalize(g *dag.DAG) *TransformResult
  • func NormalizeWithOptions(g *dag.DAG, opts NormalizeOptions) *TransformResult

Examples

• AssignLayers
• BreakCycles
• Normalize
• NormalizeWithOptions
• NormalizeWithOptions (PreserveTransitive)
• NormalizeWithOptions (SkipSeparators)
• ResolveSpanOverlaps
• Subdivide
• TransitiveReduction

Functions

func AssignLayers

func AssignLayers(g *dag.DAG)

AssignLayers assigns nodes to horizontal rows (layers) based on their depth in the graph.

AssignLayers uses a longest-path algorithm via topological sort (Kahn's algorithm) to compute row assignments. Each node is placed at one plus the maximum row of any of its parents, ensuring that:

• Source nodes (no incoming edges) are at row 0
• All parents are strictly above their children
• Each node is pushed as deep as necessary to avoid parent conflicts

Existing row assignments in the DAG are overwritten.

Algorithm

AssignLayers performs a topological traversal:

1. Initialize all source nodes (in-degree 0) at row 0 and add to queue
2. Process queue: for each node, assign children to max(current_row + 1)
3. Decrement in-degree counters; add newly zero-degree nodes to queue
4. Repeat until queue is empty

Cycles

AssignLayers assumes the graph is acyclic. If cycles exist, nodes in the cycle will never reach zero in-degree and will remain at row 0 (their default). Run BreakCycles first to ensure correct layering.

Nil Handling

AssignLayers panics if g is nil. If g is empty (zero nodes), the function returns immediately.

Performance

Time complexity is O(V + E), where V is nodes and E is edges. Space complexity is O(V) for the queue and row/degree maps.

Example

package main

import (
	"fmt"

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

func main() {
	// Create graph without layer assignments
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "app"})  // Will be row 0
	_ = g.AddNode(dag.Node{ID: "lib"})  // Will be row 1
	_ = g.AddNode(dag.Node{ID: "core"}) // Will be row 2
	_ = g.AddEdge(dag.Edge{From: "app", To: "lib"})
	_ = g.AddEdge(dag.Edge{From: "lib", To: "core"})

	transform.AssignLayers(g)

	app, _ := g.Node("app")
	lib, _ := g.Node("lib")
	core, _ := g.Node("core")

	fmt.Println("app row:", app.Row)
	fmt.Println("lib row:", lib.Row)
	fmt.Println("core row:", core.Row)
}

Output:

app row: 0
lib row: 1
core row: 2

func BreakCycles

func BreakCycles(g *dag.DAG) int

BreakCycles removes back-edges from the graph to ensure it is a valid directed acyclic graph (DAG).

BreakCycles uses depth-first search with white/gray/black coloring to detect cycles. When a gray node is encountered (indicating a back-edge that would complete a cycle), that edge is marked for removal. The function returns the number of edges removed.

Algorithm

The DFS starts from all source nodes (nodes with in-degree 0), then visits any remaining unvisited nodes to handle disconnected components. A node is:

• white: not yet visited
• gray: currently being visited (on the DFS stack)
• black: fully processed (all descendants visited)

Any edge pointing to a gray node creates a cycle and is removed.

Edge Selection

When multiple edges could break a cycle, the choice is deterministic but not guaranteed to minimize the total number removed across all cycles. For minimal cycle-breaking, consider using a feedback arc set algorithm instead.

Nil Handling

BreakCycles panics if g is nil. If g is empty (zero nodes), it returns 0.

Performance

Time complexity is O(V + E) where V is nodes and E is edges. Space complexity is O(V) for the color map and recursion stack.

Example

package main

import (
	"fmt"

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

func main() {
	// Create a graph with a cycle (which shouldn't happen in deps, but might)
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "A"})
	_ = g.AddNode(dag.Node{ID: "B"})
	_ = g.AddNode(dag.Node{ID: "C"})
	_ = g.AddEdge(dag.Edge{From: "A", To: "B"})
	_ = g.AddEdge(dag.Edge{From: "B", To: "C"})
	_ = g.AddEdge(dag.Edge{From: "C", To: "A"}) // Creates cycle

	fmt.Println("Edges before:", g.EdgeCount())
	removed := transform.BreakCycles(g)
	fmt.Println("Edges after:", g.EdgeCount())
	fmt.Println("Removed:", removed)
}

Output:

Edges before: 3
Edges after: 2
Removed: 1

func ResolveSpanOverlaps

func ResolveSpanOverlaps(d *dag.DAG)

ResolveSpanOverlaps identifies and resolves impossible crossing patterns by inserting separator beam nodes.

ResolveSpanOverlaps detects "tangle motifs"—subgraph patterns where multiple parent nodes share multiple child nodes in a way that guarantees edge crossings regardless of child ordering. The canonical example is a complete bipartite graph K(2,2):

auth → logging    auth → metrics
api  → logging    api  → metrics

No matter how you order {logging, metrics}, edges must cross. Rather than accepting crossings, ResolveSpanOverlaps inserts a dag.NodeKindAuxiliary separator node that routes edges through a shared intermediate:

auth → separator → logging
api  → separator → metrics

This eliminates crossings by factoring shared dependencies through a beam.

Detection Algorithm

ResolveSpanOverlaps processes rows bottom-up. For each row, it:

1. Computes the "span" of each parent (min/max child positions)
2. Counts how many parent spans overlap each gap between children
3. Where 2+ parents overlap, inserts a separator and reroutes edges
4. Repeats until no overlaps remain (may insert multiple separators per row)

Separator Nodes

Separator nodes are inserted in a new row between parents and children, shifting all lower rows down. Separator IDs are generated as "Sep_row_firstChild_lastChild" with numeric suffixes if needed for uniqueness.

Eligibility Rules

A parent is eligible for separator insertion only if:

• It has 2+ children in the target row
• ALL its children are in that single row (no splitting across rows)
• None of its children are subdividers of the same master (avoids splitting logical columns)

Separators are inserted in gaps between children where canInsertBetween returns true (respects subdivider master boundaries).

Multiple Passes

ResolveSpanOverlaps may make multiple passes over a row, inserting separators iteratively until no overlaps remain. Each insertion shifts rows and recomputes spans.

Nil Handling

ResolveSpanOverlaps panics if d is nil. If d is empty (zero nodes), the function returns immediately.

Performance

Time complexity is O(R·P·C·I) where R is the number of rows, P is the average number of parents per row, C is children per parent, and I is the number of separator insertion iterations (typically 1-3). For typical dependency graphs, this is effectively O(V) where V is the number of nodes.

Space complexity is O(V) for tracking used node IDs.

Example

package main

import (
	"fmt"

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

func main() {
	// Create a complete bipartite graph K(2,2) - the classic crossing pattern
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "auth", Row: 0})
	_ = g.AddNode(dag.Node{ID: "api", Row: 0})
	_ = g.AddNode(dag.Node{ID: "logging", Row: 1})
	_ = g.AddNode(dag.Node{ID: "metrics", Row: 1})

	// Both parents connect to both children (guaranteed crossing)
	_ = g.AddEdge(dag.Edge{From: "auth", To: "logging"})
	_ = g.AddEdge(dag.Edge{From: "auth", To: "metrics"})
	_ = g.AddEdge(dag.Edge{From: "api", To: "logging"})
	_ = g.AddEdge(dag.Edge{From: "api", To: "metrics"})

	fmt.Println("Before resolution:")
	fmt.Println("  Nodes:", g.NodeCount())
	fmt.Println("  Edges:", g.EdgeCount())

	transform.ResolveSpanOverlaps(g)

	fmt.Println("After resolution:")
	fmt.Println("  Nodes:", g.NodeCount())
	fmt.Println("  Edges:", g.EdgeCount())

	// Check for separator nodes
	hasSeparator := false
	for _, n := range g.Nodes() {
		if n.IsAuxiliary() {
			hasSeparator = true
			break
		}
	}
	fmt.Println("  Separator inserted:", hasSeparator)
}

Output:

Before resolution:
  Nodes: 4
  Edges: 4
After resolution:
  Nodes: 5
  Edges: 4
  Separator inserted: true

func Subdivide

func Subdivide(g *dag.DAG)

Subdivide breaks edges that span multiple rows into sequences of single-row edges connected by synthetic subdivider nodes.

Subdivide ensures every edge in the graph connects nodes in consecutive rows (parent.Row + 1 == child.Row). Any edge spanning multiple rows is replaced by a chain of dag.NodeKindSubdivider nodes. For example:

Before: app (row 0) → core (row 3)  [spans 3 rows]
After:  app → app_sub_1 → app_sub_2 → core  [3 single-row edges]

Each subdivider maintains a MasterID field linking back to the original source node, allowing renderers to visually merge subdividers into continuous vertical blocks.

Sink Extension

Subdivide also extends all sink nodes (nodes with out-degree 0) to the bottom row of the graph by appending subdivider chains. This ensures tower layouts have a flat foundation where all columns reach the bottom.

Node IDs

Subdivider nodes are assigned unique IDs of the form "master_sub_row" (e.g., "app_sub_1"). If a collision occurs, a numeric suffix is appended ("app_sub_1__2"). All generated IDs are tracked to guarantee uniqueness.

Edge Metadata

Subdivide preserves edge metadata only on the final edge in each subdivided chain (the edge entering the original target). Intermediate subdivider edges have no metadata.

Nil Handling

Subdivide panics if g is nil. If g is empty (zero nodes), the function returns immediately.

Performance

Time complexity is O(V·D) where V is nodes and D is the maximum depth (row count), as each node may spawn subdividers equal to the depth. Space complexity is O(V) for tracking used IDs.

Example

package main

import (
	"fmt"

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

func main() {
	// Create graph with a long edge spanning multiple rows
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "app", Row: 0})
	_ = g.AddNode(dag.Node{ID: "deep", Row: 3}) // 3 rows below app
	_ = g.AddEdge(dag.Edge{From: "app", To: "deep"})

	fmt.Println("Before subdivide:")
	fmt.Println("  Nodes:", g.NodeCount())

	transform.Subdivide(g)

	fmt.Println("After subdivide:")
	fmt.Println("  Nodes:", g.NodeCount())

	// Check that subdivider nodes were created
	subdividers := 0
	for _, n := range g.Nodes() {
		if n.IsSubdivider() {
			subdividers++
		}
	}
	fmt.Println("  Subdividers:", subdividers)
}

Output:

Before subdivide:
  Nodes: 2
After subdivide:
  Nodes: 4
  Subdividers: 2

func TransitiveReduction

func TransitiveReduction(g *dag.DAG)

TransitiveReduction removes redundant edges from the graph.

TransitiveReduction removes any edge (u, v) where there exists an alternate path from u to v through at least one intermediate node. For example, if edges A→B, B→C, and A→C all exist, then A→C is redundant and is removed because A reaches C via B.

This simplifies visualization by showing only direct dependencies, which is critical for tower layouts where transitive edges create impossible geometry (a block cannot rest on both adjacent and distant floors simultaneously).

Algorithm

TransitiveReduction computes full transitive closure using DFS-based reachability, then removes any edge (u, v) where u can reach v through an intermediate node w (where u→w and w reaches v).

Nil Handling

TransitiveReduction panics if g is nil. If g is empty (zero nodes), the function returns immediately without error.

Performance

Time complexity is O(V²·E) in the worst case, where V is the number of nodes and E is the number of edges. For sparse graphs (typical dependency graphs with limited fan-out), performance approaches O(V·E).

Space complexity is O(V²) for the reachability matrix. For large dense graphs (thousands of nodes with high connectivity), this may consume significant memory.

Edge Metadata

TransitiveReduction preserves edge metadata for all non-redundant edges. Metadata on removed edges is discarded.

Example

package main

import (
	"fmt"

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

func main() {
	// A → B → C with transitive edge A → C
	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"})
	_ = g.AddEdge(dag.Edge{From: "A", To: "C"}) // Redundant

	fmt.Println("Before reduction:", g.EdgeCount(), "edges")
	transform.TransitiveReduction(g)
	fmt.Println("After reduction:", g.EdgeCount(), "edges")
}

Output:

Before reduction: 3 edges
After reduction: 2 edges

Types

type NormalizeOptions

type NormalizeOptions struct {
	// SkipCycleBreaking disables cycle detection and removal. Use only when
	// the input graph is guaranteed to be acyclic. If cycles exist and this
	// is true, subsequent transformations may behave incorrectly.
	SkipCycleBreaking bool

	// SkipTransitiveReduction disables removal of redundant edges. This
	// preserves all edges from the input but may result in cluttered
	// visualizations with impossible geometry in tower layouts.
	SkipTransitiveReduction bool

	// SkipSeparators disables insertion of separator beams for tangle motifs.
	// If true, the output may contain unavoidable edge crossings. Use this
	// when crossings are acceptable or when the graph structure guarantees
	// no overlaps.
	SkipSeparators bool
}

NormalizeOptions configures which transformations are applied by NormalizeWithOptions.

The zero value applies all transformations (equivalent to calling Normalize).

type TransformResult

type TransformResult struct {
	// CyclesRemoved is the number of back-edges removed by cycle breaking.
	// Zero indicates the input was already acyclic.
	CyclesRemoved int

	// TransitiveEdgesRemoved is the number of redundant edges removed by
	// transitive reduction. Higher values indicate more redundancy in the
	// original dependency graph.
	TransitiveEdgesRemoved int

	// SubdividersAdded is the number of synthetic subdivider nodes inserted
	// to break long edges into single-row segments. Higher values indicate
	// deeper dependency chains.
	SubdividersAdded int

	// SeparatorsAdded is the number of auxiliary separator beam nodes inserted
	// to resolve impossible crossing patterns. Non-zero values indicate the
	// presence of tangle motifs (e.g., complete bipartite subgraphs).
	SeparatorsAdded int

	// MaxRow is the final depth (maximum row number) after all transformations.
	// This represents the height of the tower layout.
	MaxRow int
}

TransformResult contains metrics about transformations applied to a DAG.

TransformResult is returned by Normalize and NormalizeWithOptions to provide visibility into what transformations occurred. This is useful for logging, debugging, and understanding graph complexity.

func Normalize

func Normalize(g *dag.DAG) *TransformResult

Normalize prepares a DAG for tower rendering by applying a sequence of transformations that satisfy the layout's structural constraints.

Normalize modifies g in place and returns transformation metrics. All transformations are applied in this specific order:

1. BreakCycles: Remove back-edges to ensure it is a true DAG.
2. TransitiveReduction: Remove redundant edges to simplify the visual.
3. AssignLayers: Assign horizontal rows (layers) based on node depth.
4. Subdivide: Break edges crossing multiple rows into single-row segments.
5. ResolveSpanOverlaps: Insert separator beams to resolve layout conflicts.

This order is critical: cycles must be broken before transitive reduction, layers must be assigned before subdivision, and span overlaps can only be detected after edges are subdivided into single-row segments.

To skip specific transformations, use NormalizeWithOptions.

Return Value

Normalize returns a TransformResult containing metrics about the transformations applied (cycles removed, edges reduced, nodes added, etc.). This is useful for logging and understanding graph complexity.

Nil Handling

Normalize panics if g is nil. The DAG must be non-nil, but may be empty (zero nodes). An empty DAG is returned unchanged with zero metrics.

Performance

Complexity is O(V²·E) in the worst case due to transitive reduction, where V is the number of nodes and E is the number of edges. For typical dependency graphs with limited fan-out, performance is near-linear.

Example

package main

import (
	"fmt"

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

func main() {
	// Build a raw dependency graph (not yet normalized)
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "app"})
	_ = g.AddNode(dag.Node{ID: "auth"})
	_ = g.AddNode(dag.Node{ID: "cache"})
	_ = g.AddNode(dag.Node{ID: "db"})

	// Dependencies: app → auth → db, app → cache → db, app → db (transitive)
	_ = g.AddEdge(dag.Edge{From: "app", To: "auth"})
	_ = g.AddEdge(dag.Edge{From: "app", To: "cache"})
	_ = g.AddEdge(dag.Edge{From: "app", To: "db"}) // Transitive - will be removed
	_ = g.AddEdge(dag.Edge{From: "auth", To: "db"})
	_ = g.AddEdge(dag.Edge{From: "cache", To: "db"})

	fmt.Println("Before normalize:")
	fmt.Println("  Nodes:", g.NodeCount())
	fmt.Println("  Edges:", g.EdgeCount())

	// Normalize: assigns layers, removes transitive edges, subdivides long edges
	result := transform.Normalize(g)

	fmt.Println("After normalize:")
	fmt.Println("  Nodes:", g.NodeCount())
	fmt.Println("  Edges:", g.EdgeCount())
	fmt.Println("  Rows:", g.RowCount())
	fmt.Println("Transformation metrics:")
	fmt.Println("  Cycles removed:", result.CyclesRemoved)
	fmt.Println("  Transitive edges removed:", result.TransitiveEdgesRemoved)
	fmt.Println("  Subdividers added:", result.SubdividersAdded)
}

Output:

Before normalize:
  Nodes: 4
  Edges: 5
After normalize:
  Nodes: 4
  Edges: 4
  Rows: 3
Transformation metrics:
  Cycles removed: 0
  Transitive edges removed: 1
  Subdividers added: 0

func NormalizeWithOptions

func NormalizeWithOptions(g *dag.DAG, opts NormalizeOptions) *TransformResult

NormalizeWithOptions prepares a DAG for tower rendering with configurable transformation steps.

NormalizeWithOptions is like Normalize but allows skipping specific transformations via opts. This is useful when:

• The input is known to be acyclic (skip cycle breaking)
• Transitive edges should be preserved (skip reduction)
• Edge crossings are acceptable (skip separators)

The transformations are applied in this order (unless skipped):

1. BreakCycles: Remove back-edges (unless opts.SkipCycleBreaking)
2. TransitiveReduction: Remove redundant edges (unless opts.SkipTransitiveReduction)
3. AssignLayers: Assign rows (always applied)
4. Subdivide: Break long edges (always applied)
5. ResolveSpanOverlaps: Insert separators (unless opts.SkipSeparators)

Layer assignment and edge subdivision are always applied because they are required for valid tower layouts.

Nil Handling

NormalizeWithOptions panics if g is nil. An empty DAG returns zero metrics.

Performance

See Normalize. Skipping transitive reduction reduces worst-case complexity from O(V²·E) to O(V·E).

Example

package main

import (
	"fmt"

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

func main() {
	// Build a graph that we know is already acyclic
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "api"})
	_ = g.AddNode(dag.Node{ID: "auth"})
	_ = g.AddNode(dag.Node{ID: "db"})
	_ = g.AddEdge(dag.Edge{From: "api", To: "auth"})
	_ = g.AddEdge(dag.Edge{From: "api", To: "db"}) // Transitive
	_ = g.AddEdge(dag.Edge{From: "auth", To: "db"})

	// Skip cycle breaking (we know it's acyclic) but keep transitive reduction
	result := transform.NormalizeWithOptions(g, transform.NormalizeOptions{
		SkipCycleBreaking: true,
	})

	fmt.Println("Cycles removed:", result.CyclesRemoved)
	fmt.Println("Transitive edges removed:", result.TransitiveEdgesRemoved)
	fmt.Println("Final edge count:", g.EdgeCount())
}

Output:

Cycles removed: 0
Transitive edges removed: 1
Final edge count: 2

Example (PreserveTransitive)

package main

import (
	"fmt"

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

func main() {
	// Sometimes you want to preserve all edges even if redundant
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "A"})
	_ = g.AddNode(dag.Node{ID: "B"})
	_ = g.AddNode(dag.Node{ID: "C"})
	_ = g.AddEdge(dag.Edge{From: "A", To: "B"})
	_ = g.AddEdge(dag.Edge{From: "B", To: "C"})
	_ = g.AddEdge(dag.Edge{From: "A", To: "C"}) // Keep this transitive edge

	result := transform.NormalizeWithOptions(g, transform.NormalizeOptions{
		SkipTransitiveReduction: true,
	})

	fmt.Println("Transitive edges removed:", result.TransitiveEdgesRemoved)
	fmt.Println("Subdividers added:", result.SubdividersAdded)
	// Note: Edge count increases due to subdividers for A→C (0→2 requires subdivider)
	fmt.Println("Final edge count:", g.EdgeCount())
}

Output:

Transitive edges removed: 0
Subdividers added: 1
Final edge count: 4

Example (SkipSeparators)

package main

import (
	"fmt"

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

func main() {
	// Accept edge crossings instead of inserting separator beams
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "auth"})
	_ = g.AddNode(dag.Node{ID: "api"})
	_ = g.AddNode(dag.Node{ID: "log"})
	_ = g.AddNode(dag.Node{ID: "metrics"})
	_ = g.AddEdge(dag.Edge{From: "auth", To: "log"})
	_ = g.AddEdge(dag.Edge{From: "auth", To: "metrics"})
	_ = g.AddEdge(dag.Edge{From: "api", To: "log"})
	_ = g.AddEdge(dag.Edge{From: "api", To: "metrics"})

	result := transform.NormalizeWithOptions(g, transform.NormalizeOptions{
		SkipSeparators: true,
	})

	fmt.Println("Separators added:", result.SeparatorsAdded)
	fmt.Println("Node count unchanged:", g.NodeCount() == 4)
}

Output:

Separators added: 0
Node count unchanged: true