ordering

Documentation

Overview

Package ordering provides algorithms for determining the left-to-right arrangement of nodes within each row of a layered graph.

The Ordering Problem

In tower visualizations, blocks must physically rest on what they depend on. This requires eliminating edge crossings—if edges cross, the corresponding blocks cannot support each other. Finding an ordering with zero crossings (or minimum crossings when zero is impossible) is NP-hard.

This package provides multiple algorithms with different tradeoffs:

• Barycentric: Fast heuristic, O(n log n) per pass
• OptimalSearch: Exact algorithm with branch-and-bound pruning

Barycentric Heuristic

The Barycentric orderer implements the classic Sugiyama barycenter method with weighted median refinement. It positions each node near the average position of its neighbors, then iteratively improves through alternating top-down and bottom-up sweeps.

The algorithm:

1. Initialize the top row (alphabetically or by structure)
2. For each subsequent row, sort nodes by their parents' average positions
3. Apply transpose passes to swap adjacent nodes that reduce crossings
4. Alternate sweep direction (top-down, bottom-up) for several passes
5. Return the best ordering found

This runs in milliseconds even for large graphs, but provides no optimality guarantee. It's used both standalone and as the initial bound for optimal search.

Optimal Search

OptimalSearch uses branch-and-bound with PQ-tree pruning to find the true minimum-crossing ordering. The key innovations:

• PQ-tree constraints: Children of the same parent should be adjacent; subdivider chains must stay together. This prunes invalid orderings.

• Barycentric initialization: The heuristic provides a tight initial bound, enabling aggressive pruning from the start.

• Incremental crossing count: Crossings are computed layer-by-layer using Fenwick trees, with early termination when the bound is exceeded.

• Parallel search: Multiple starting permutations are explored concurrently using goroutines.

For most real-world dependency graphs (dozens to low hundreds of nodes), optimal search finds the true minimum in seconds. A configurable timeout ensures graceful fallback to the best-found solution.

Usage

The Orderer interface allows algorithms to be used interchangeably:

var orderer ordering.Orderer = ordering.Barycentric{Passes: 24}
orders := orderer.OrderRows(g)  // map[row][]nodeID

For optimal search with progress reporting:

orderer := ordering.OptimalSearch{
    Timeout: 30 * time.Second,
    Progress: func(explored, pruned, best int) {
        fmt.Printf("Explored %d, pruned %d, best=%d\n", explored, pruned, best)
    },
}
orders := orderer.OrderRows(g)

Quality Presets

The Quality type provides preset configurations:

• QualityFast: 100ms timeout, suitable for interactive use
• QualityBalanced: 5s timeout, good for most graphs
• QualityOptimal: 60s timeout, for publication-quality output

Algorithm Selection

Use barycentric for:

• Large graphs (hundreds of nodes)
• Interactive/preview rendering
• When "good enough" suffices

Use optimal search for:

• Publication or showcase output
• Smaller graphs where crossing-free is achievable
• When visual quality is critical

Example (OrdererInterface)

package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
	"github.com/matzehuels/stacktower/pkg/render/tower/ordering"
)

func main() {
	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"})

	// Both orderers implement the same interface
	var orderer ordering.Orderer

	// Fast heuristic for interactive use
	orderer = ordering.Barycentric{Passes: 12}
	fastOrders := orderer.OrderRows(g)

	// Exact algorithm for publication quality
	orderer = ordering.OptimalSearch{Timeout: ordering.DefaultTimeoutFast}
	optimalOrders := orderer.OrderRows(g)

	fmt.Println("Fast result rows:", len(fastOrders))
	fmt.Println("Optimal result rows:", len(optimalOrders))
}

Output:

Fast result rows: 2
Optimal result rows: 2

Index

• Constants
• type Barycentric
  • func (b Barycentric) OrderRows(g *dag.DAG) map[int][]string
• type ContextOrderer
• type DebugInfo
• type OptimalSearch
  • func (o OptimalSearch) OrderRows(g *dag.DAG) map[int][]string
• type Orderer
• type Quality
• type RowDebugInfo

Examples

• Package (OrdererInterface)
• Barycentric
• Barycentric (CrossingMinimization)
• OptimalSearch
• Quality

Constants

const (
	DefaultTimeoutFast     = 100 * time.Millisecond
	DefaultTimeoutBalanced = 5 * time.Second
	DefaultTimeoutOptimal  = 60 * time.Second
)

Types

type Barycentric

type Barycentric struct {
	Passes int
}

Barycentric implements a fast heuristic for edge crossing minimization based on the Sugiyama framework. It iteratively reorders rows by the average position (barycenter) of their neighbors in adjacent rows.

Example

package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
	"github.com/matzehuels/stacktower/pkg/render/tower/ordering"
)

func main() {
	// Create a graph with potential for crossings
	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.AddNode(dag.Node{ID: "db", Row: 2})
	_ = g.AddEdge(dag.Edge{From: "app", To: "auth"})
	_ = g.AddEdge(dag.Edge{From: "app", To: "cache"})
	_ = g.AddEdge(dag.Edge{From: "auth", To: "db"})
	_ = g.AddEdge(dag.Edge{From: "cache", To: "db"})

	// Barycentric orderer with 24 refinement passes
	orderer := ordering.Barycentric{Passes: 24}
	orders := orderer.OrderRows(g)

	fmt.Println("Row count:", len(orders))
	fmt.Println("Row 1 has 2 nodes:", len(orders[1]) == 2)
}

Output:

Row count: 3
Row 1 has 2 nodes: true

Example (CrossingMinimization)

package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
	"github.com/matzehuels/stacktower/pkg/render/tower/ordering"
)

func main() {
	// Classic crossing example: X pattern
	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
	_ = g.AddEdge(dag.Edge{From: "a", To: "y"})
	_ = g.AddEdge(dag.Edge{From: "b", To: "x"})

	// Before ordering, this creates a crossing
	initialCrossings := dag.CountLayerCrossings(g, []string{"a", "b"}, []string{"x", "y"})
	fmt.Println("Initial crossings:", initialCrossings)

	// Barycentric ordering eliminates the crossing
	orderer := ordering.Barycentric{}
	orders := orderer.OrderRows(g)

	finalCrossings := dag.CountLayerCrossings(g, orders[0], orders[1])
	fmt.Println("After ordering:", finalCrossings)
}

Output:

Initial crossings: 1
After ordering: 0

func (Barycentric) OrderRows

func (b Barycentric) OrderRows(g *dag.DAG) map[int][]string

OrderRows implements the Orderer interface using the barycentric heuristic.

type ContextOrderer

type ContextOrderer interface {
	Orderer
	OrderRowsContext(ctx context.Context, g *dag.DAG) map[int][]string
}

ContextOrderer is an Orderer that supports cancellation and timeouts via a context.

type DebugInfo

type DebugInfo struct {
	Rows      []RowDebugInfo
	MaxDepth  int
	TotalRows int
}

DebugInfo contains diagnostic information about the optimal search process.

type OptimalSearch

type OptimalSearch struct {
	Progress func(explored, pruned, best int)
	Timeout  time.Duration
	Debug    func(info DebugInfo)
}

OptimalSearch implements a branch-and-bound search algorithm to find the mathematically optimal horizontal ordering (minimum crossings). It uses PQ-trees to prune the search space to only include orderings that satisfy structural constraints (Consecutive Ones Property).

Example

package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/dag"
	"github.com/matzehuels/stacktower/pkg/render/tower/ordering"
)

func main() {
	g := dag.New(nil)
	_ = g.AddNode(dag.Node{ID: "app", Row: 0})
	_ = g.AddNode(dag.Node{ID: "a", Row: 1})
	_ = g.AddNode(dag.Node{ID: "b", Row: 1})
	_ = g.AddNode(dag.Node{ID: "c", Row: 1})
	_ = g.AddEdge(dag.Edge{From: "app", To: "a"})
	_ = g.AddEdge(dag.Edge{From: "app", To: "b"})
	_ = g.AddEdge(dag.Edge{From: "app", To: "c"})

	// Optimal search with progress callback
	var explored int
	orderer := ordering.OptimalSearch{
		Timeout: ordering.DefaultTimeoutFast,
		Progress: func(exp, pruned, best int) {
			explored = exp
		},
	}
	orders := orderer.OrderRows(g)

	fmt.Println("Found ordering:", len(orders) > 0)
	fmt.Println("Explored states:", explored >= 0)
}

Output:

Found ordering: true
Explored states: true

func (OptimalSearch) OrderRows

func (o OptimalSearch) OrderRows(g *dag.DAG) map[int][]string

OrderRows implements the Orderer interface by performing an optimal search.

type Orderer

type Orderer interface {
	OrderRows(g *dag.DAG) map[int][]string
}

Orderer is an interface for horizontal row ordering algorithms. An orderer determines the horizontal sequence of nodes in each row to minimize edge crossings.

type Quality

type Quality int

Quality represents the desired trade-off between ordering speed and quality.

Example

package main

import (
	"fmt"

	"github.com/matzehuels/stacktower/pkg/render/tower/ordering"
)

func main() {
	// Quality presets provide sensible timeout defaults
	fmt.Println("Fast timeout:", ordering.DefaultTimeoutFast)
	fmt.Println("Balanced timeout:", ordering.DefaultTimeoutBalanced)
	fmt.Println("Optimal timeout:", ordering.DefaultTimeoutOptimal)
}

Output:

Fast timeout: 100ms
Balanced timeout: 5s
Optimal timeout: 1m0s

const (
	QualityFast Quality = iota
	QualityBalanced
	QualityOptimal
)

type RowDebugInfo

type RowDebugInfo struct {
	Row        int
	NodeCount  int
	Candidates int
}

RowDebugInfo contains diagnostic information for a single row during search.