Spec: Auto-Layout (Graph Algorithms)

Overview

Implement automatic circuit layout using graph algorithms to arrange components and route wires for optimal readability without manual positioning. Supports both full auto-layout and selective re-layout of sub-sections.

Motivation

Manually arranging components in complex circuits is time-consuming. Imported netlists, auto-generated circuits (from boolean expressions or HDL), and messy hand-built circuits all benefit from automatic layout. Good auto-layout dramatically improves circuit readability.

Requirements

Functional Requirements

1. Full Auto-Layout: Automatically position all components and route all wires in the circuit.
2. Selective Layout: Auto-layout only selected components while keeping others fixed.
3. Layout Algorithms:
   • Layered/Sugiyama: For dataflow circuits (combinational logic, pipelines). Left-to-right or top-to-bottom flow.
   • Force-Directed: For general circuits without clear flow direction.
4. Wire Routing: After placement, auto-route wires using Manhattan routing with minimal crossings.
5. Constraint Respect: Honor user-locked component positions (pinned components stay in place).
6. Spacing Configuration: Configurable minimum spacing between components.
7. Flow Direction: User selects preferred signal flow direction (L→R, T→B, R→L, B→T).
8. Crossing Minimization: Algorithm actively minimizes wire crossings.
9. Grouping Awareness: Components in a group are laid out together as a cluster.
10. Preview Mode: Show a preview of the auto-layout result before applying (with undo support).
11. Incremental Layout: When adding a new component, suggest optimal placement relative to existing layout.

Non-Functional Requirements

• Layout computation completes in under 5 seconds for circuits with up to 500 components.
• Result must produce no overlapping components.
• Layout must respect grid snapping settings.
• Integrated with undo/redo (auto-layout is one undoable action).

Design

Algorithm Selection

Circuit Type	Best Algorithm	Rationale
Combinational (gates→output)	Layered (Sugiyama)	Clear input→output flow
Sequential (feedback loops)	Modified Layered + cycle breaking	Handles back-edges
General/messy	Force-directed (spring model)	No assumed flow

Layered Layout Pipeline (Sugiyama)

1. Cycle Removal → Break feedback loops with temporary edge reversal
2. Layer Assignment → Assign components to layers (longest-path method)
3. Crossing Reduction → Barycenter heuristic within layers
4. Coordinate Assignment → Brandes-Köpf algorithm for vertical alignment
5. Edge Routing → Manhattan routing with bend minimization

Force-Directed Layout

1. Initialize positions (random or current)
2. Iterate until convergence:
   - Repulsive force between all component pairs (Coulomb)
   - Attractive force along wires (Hooke's spring)
   - Apply forces with damping
3. Snap to grid
4. Route wires

Integration Point

public class AutoLayoutEngine
{
    public LayoutResult ComputeLayout(Circuit circuit, LayoutOptions options);
    public LayoutResult ComputePartialLayout(Circuit circuit, IEnumerable<Component> selected, LayoutOptions options);
}

public class LayoutOptions
{
    public LayoutAlgorithm Algorithm { get; set; }
    public FlowDirection Direction { get; set; }
    public double MinSpacing { get; set; }
    public bool RespectGroups { get; set; }
    public bool SnapToGrid { get; set; }
    public HashSet<Guid> LockedComponents { get; set; }
}

UI/UX

• Menu: Arrange → Auto-Layout (full circuit)
• Menu: Arrange → Layout Selection
• Toolbar button for quick access.
• Options dialog before layout (algorithm, direction, spacing).
• Preview overlay showing proposed positions before confirming.
• Keyboard shortcut: Ctrl+Shift+L.

Implementation Tasks

1. Create DigitalWorks.Routing/Layout/ namespace.
2. Implement graph abstraction (components as nodes, wires as edges).
3. Implement Sugiyama layered layout algorithm.
4. Implement force-directed layout algorithm.
5. Implement crossing minimization (barycenter heuristic).
6. Implement coordinate assignment with grid snapping.
7. Integrate with existing AutoRouter for post-layout wire routing.
8. Add layout preview overlay on canvas.
9. Create layout options dialog.
10. Integrate with undo/redo system (whole layout as one action).
11. Add incremental placement suggestion for new components.

Risks & Open Questions

• How to handle very large circuits (1000+ components) — progressive layout with LOD?
• Should the algorithm optimize for different objectives (compactness vs. readability)?
• How to handle macros — layout internal circuits separately?
• Should locked components act as fixed constraints or be moved slightly for better results?

Priority

Medium-High — Dramatically improves usability for complex circuits.