Module

LayeredLayout.LayerAssignment.NetworkSimplex

Package: purescript-layered-layout
Repository: markgrafhq/purescript-layered-layout

Layer assignment via network simplex.

The Gansner-Koutsofios-North-Vo core lives in LayeredLayout.NetworkSimplex (shared with the post-routing graph compactor). This module adds the layering-specific wrapping:

Partition the graph into weakly-connected components and run the simplex on each (connectedComponents).
After each component's optimal layering is normalised, run a balancing pass that moves nodes whose in/out-degrees match to a less-populated layer when their feasible window allows it.

#networkSimplex Source

networkSimplex :: Array NodeId -> Array { src :: NodeId, tgt :: NodeId } -> Map NodeId Int

Run the network simplex layerer over the given node ids and edges. Each edge has weight 1 and delta 1 (the minimum span). The graph is split into weakly-connected components and the simplex runs independently on each one so disconnected sub-graphs all receive a feasible layering starting at zero. Balancing uses only the component's own layer filling, in its depth-first traversal order.

Modules: LayeredLayout; LayeredLayout.Aesthetics; LayeredLayout.Compaction.EdgeAwareScanlineConstraints; LayeredLayout.Compaction.HorizontalGraphCompactor; LayeredLayout.Compaction.LGraphToCGraphTransformer; LayeredLayout.Compaction.NetworkSimplexCompaction; LayeredLayout.Compaction.OneD; LayeredLayout.Compaction.VerticalSegment; LayeredLayout.Components; LayeredLayout.CoordAssignment; LayeredLayout.CrossingMin; LayeredLayout.CrossingMin.Constraints; LayeredLayout.CrossingMin.NorthSouth; LayeredLayout.CrossingMin.Ports; LayeredLayout.CycleRemoval; LayeredLayout.DummyNodes; LayeredLayout.EdgeLabels; LayeredLayout.EdgeLabels.SelfLoops; LayeredLayout.EdgeLabels.SelfLoops.Model; LayeredLayout.EdgeLabels.SelfLoops.Routing; LayeredLayout.EdgeRouting; LayeredLayout.EdgeRouting.HyperEdgeCycleDetector; LayeredLayout.EdgeRouting.HyperEdges; LayeredLayout.EdgeRouting.LineJump; LayeredLayout.EdgeRouting.Orthogonal; LayeredLayout.EdgeRouting.PortAssignment; LayeredLayout.Graph; LayeredLayout.Grid; LayeredLayout.JavaRandom; LayeredLayout.LayerAssignment; LayeredLayout.LayerAssignment.NetworkSimplex; LayeredLayout.NetworkSimplex; LayeredLayout.PortDistribution; LayeredLayout.PortDummies; LayeredLayout.Result