# ELK SPOrE Compaction

Property | Value
--- | ---
Identifier: | `org.eclipse.elk.sporeCompaction`
Meta Data Provider: | `options.SporeMetaDataProvider`

## Description

ShrinkTree is a compaction algorithm that maintains the topology of a layout. The relocation of diagram elements is based on contracting a spanning tree.

## Additional Documentation

The algorithm uses the programmatic structure of SPOrE, which stands for Structure, Processing Order, and Execution.

### The Three Phases

1. The structure phase extracts geometric information from the given layout to capture the topology that should be preserved during the subsequent adjustment of the layout.

   For this purpose, a Delaunay triangulation is implemented, which captures proximity information.

2. Now, the processing order for the last phase is determined and represented by a tree.

3. The execution phase traverses the previously constructed tree and applies an algorithm specific operation to each node.

### The ShrinkTree Approach

The functional principle is based on a modification of an overlap removal algorithm presented by Nachmanson et al. in “Node overlap removal by growing a tree”. First, the set of vertices corresponding to the nodes’ centers is Delaunay triangulated. Second, a spanning tree of the triangulation edges is constructed. Third, the spanning tree is shrunk pulling the nodes closer together.

### Use Case

Compacting the inclusion tree of a hierarchical Ptolemy model:

## Supported Options

Option | Default Value
--- | ---
Compaction Strategy | `CompactionStrategy.DEPTH_FIRST`
Cost Function for Spanning Tree | `SpanningTreeCostFunction.CIRCLE_UNDERLAP`
Debug Mode | `false`
Node Spacing | `8`
Orthogonal Compaction | `false`
Padding | `new ElkPadding(8)`
Root node for spanning tree construction | `null`
Root selection for spanning tree | `RootSelection.CENTER_NODE`
Structure Extraction Strategy | `StructureExtractionStrategy.DELAUNAY_TRIANGULATION`
Tree Construction Strategy | `TreeConstructionStrategy.MINIMUM_SPANNING_TREE`
Underlying Layout Algorithm | `<not defined>`

- Algorithms
- Draw2D Layout
- ELK Box
- ELK DisCo
- ELK Fixed
- ELK Force
- ELK Layered
- ELK Mr. Tree
- ELK Radial
- ELK Randomizer
- ELK Rectangle Packing
- ELK SPOrE Compaction
- ELK SPOrE Overlap Removal
- ELK Stress
- Graphviz Circo
- Graphviz Dot
- Graphviz FDP
- Graphviz Neato
- Graphviz Twopi
- Layout Options
- Activate Inside Self Loops
- Adapt Port Positions
- Add Unnecessary Bendpoints
- Additional Port Space
- Additional Wrapped Edges Spacing
- Alignment
- Allow Non-Flow Ports To Switch Sides
- Animate
- Animation Time Factor
- Annulus Wedge Criteria
- Aspect Ratio
- Bend Points
- BK Edge Straightening
- BK Fixed Alignment
- Box Layout Mode
- Comment Box
- Comment Comment Spacing
- Comment Node Spacing
- Compact Rows
- Compaction
- Compaction Step Size
- Compaction Strategy
- Components Spacing
- Concentrate Edges
- Connected Components Compaction
- Connected Components Compaction Strategy
- Connected Components Layout Algorithm
- Consider Model Order
- Consider Model Order for Components
- Content Alignment
- Correction Factor for Wrapping
- Cost Function for Spanning Tree
- Crossing Counter Node Order Influence
- Crossing Counter Port Order Influence
- Crossing Minimization Strategy
- Current position of a node in the order of nodes
- Cutting Strategy
- Cycle Breaking Strategy
- DCGraph
- Debug Mode
- Desired Edge Length
- Desired index of node
- Direction
- Direction Congruency
- Direction Priority
- Distance Model
- Distance Penalty When Improving Cuts
- Eades Repulsion
- Edge Center Label Placement Strategy
- Edge Edge Between Layer Spacing
- Edge Label Placement
- Edge Label Side Selection
- Edge Label Spacing
- Edge Node Between Layers Spacing
- Edge Node Spacing
- Edge Routing
- Edge Spacing
- Edge Thickness
- Edge Type
- Epsilon
- Expand Nodes
- Favor Straight Edges Over Balancing
- Feedback Edges
- Fill Polyominoes
- Fit Aspect Ratio
- Fixed Graph Size
- Fixed Position
- Font Name
- Font Size
- Force Model
- Force Node Model Order
- FR Temperature
- Generate Position and Layer IDs
- Graph Wrapping Strategy
- Greedy Switch Activation Threshold
- Greedy Switch Crossing Minimization
- Greedy Switch Crossing Minimization (hierarchical)
- Hierarchical Sweepiness
- Hierarchy Handling
- Hierarchy Handling (Graphviz Dot)
- High Degree Node Maximum Tree Height
- High Degree Node Threshold
- High Degree Node Treatment
- Horizontal spacing between Label and Port
- Hypernode
- Improve Cuts
- Improve Wrapped Edges
- Individual Spacing
- Individual Spacing (ELK Layered)
- Inline Edge Labels
- Inside Self Loop
- Interactive
- interactive Layout
- Interactive Reference Point
- Iteration Limit
- Iterations
- Iterations Factor
- Junction Points
- Label Angle
- Label Distance
- Label Manager
- Label Manager
- Label Node Spacing
- Label Spacing
- Layer Bound
- Layer Choice Constraint
- Layer Constraint
- Layer ID
- Layer Spacing Factor
- Layout Algorithm
- Layout Ancestors
- Layout Dimension
- Layout Partition
- Layout Partitioning
- Linear Segments Deflection Dampening
- List of Polyominoes
- Long Edge Ordering Strategy
- Manually Specified Cuts
- Margins
- Max Node Promotion Iterations
- Max. Iterations
- Maximal Animation Time
- Merge Edges
- Merge Hierarchy-Crossing Edges
- Minimal Animation Time
- MSD Freedom
- No Layout
- No Model Order
- Node Flexibility
- Node Flexibility Default
- Node Label Padding
- Node Label Placement
- Node Layering Strategy
- Node Node Between Layers Spacing
- Node Placement Strategy
- Node Promotion Strategy
- Node Self Loop Spacing
- Node Size Constraints
- Node Size Minimum
- Node Size Options
- Node Spacing
- Omit Node Micro Layout
- Only Area Approximation
- Optimization Goal
- Order ID
- Orthogonal Compaction
- Overlap Removal
- Padding
- Polyomino Primary Sorting Criterion
- Polyomino Secondary Sorting Criterion
- Polyomino Traversal Strategy
- Port Alignment
- Port Alignment (East)
- Port Alignment (North)
- Port Alignment (South)
- Port Alignment (West)
- Port Anchor Offset
- Port Border Offset
- Port Constraints
- Port Index
- Port Label Placement
- Port Labels Next to Port
- Port Side
- Port Sorting Strategy
- Port Spacing
- Position
- Position Choice Constraint
- Position ID
- Post Compaction Constraint Calculation
- Post Compaction Strategy
- Priority
- Priority (ELK Box)
- Priority (ELK Force)
- Priority (ELK Layered)
- Priority (ELK Mr. Tree)
- Progress Bar
- Radius
- Randomization Seed
- Repulsive Power
- Resolved Layout Algorithm
- Root node for spanning tree construction
- Root selection for spanning tree
- Scale Factor
- Search Order
- Self-Loop Distribution
- Self-Loop Ordering
- Semi-Interactive Crossing Minimization
- Separate Connected Components
- Shift Last Placed.
- Shortness Priority
- Shortness Priority (ELK Layered)
- Sloped Edge Zone Width
- Sloppy Spline Layer Spacing Factor
- Sorter
- Spacing Base Value
- Spline Routing Mode
- Straightness Priority
- Stress Epsilon
- Structure Extraction Strategy
- Target Width
- Thoroughness
- Translation Optimization
- Treat Port Labels as Group
- Tree Construction Strategy
- Underlying Layout Algorithm
- Upper Bound On Width [MinWidth Layerer]
- Upper Layer Estimation Scaling Factor [MinWidth Layerer]
- Upper limit for iterations of overlap removal
- Valid Indices for Wrapping
- Validate Graph
- Validate Options
- Validification Strategy
- Vertical spacing between Label and Port
- Weighting of Nodes
- Whether to run a supplementary scanline overlap check.
- Zoom to Fit
- Layout Option Groups
- box
- compaction
- compaction
- compaction.postCompaction
- componentCompaction
- considerModelOrder
- crossingMinimization
- crossingMinimization.greedySwitch
- crossingMinimization.greedySwitchHierarchical
- cycleBreaking
- debug
- edge
- edgeLabels
- edgeLabels
- edgeRouting
- edgeRouting.polyline
- edgeRouting.splines
- edgeRouting.splines.sloppy
- font
- highDegreeNodes
- insideSelfLoops
- layering
- layering.coffmanGraham
- layering.minWidth
- layering.nodePromotion
- nodeLabels
- nodePlacement
- nodePlacement.bk
- nodePlacement.linearSegments
- nodePlacement.networkSimplex
- nodePlacement.networkSimplex.nodeFlexibility
- nodeSize
- overlapRemoval
- partitioning
- polyomino
- port
- portAlignment
- portLabels
- priority
- processingOrder
- spacing
- spacing
- structure
- wrapping
- wrapping.cutting
- wrapping.cutting.msd
- wrapping.multiEdge
- wrapping.singleEdge
- wrapping.validify