Module

Hylograph.Data.DAGTree

Package: purescript-hylograph-graph
Repository: afcondon/purescript-hylograph-graph

DAG Tree: Tree Layout with Extra Links

A DAG (Directed Acyclic Graph) Tree is a tree structure with additional cross-links that don't fit the tree hierarchy. This is useful for visualizing structures that are "mostly hierarchical" with some extra connections.

Examples:

Git commit graphs (tree + merge commits)
State machines (tree of states + back-edges)
The GUP flow diagram (tree + merge arrows)
Dependency graphs with highlighted cycles

== Design

The tree is laid out using standard algorithms (Tidy/Dendrogram), which assigns x,y positions to each node. The extra links are then rendered as paths between nodes using their computed positions.

This keeps tree layout clean while allowing graph-like visualizations.

== Usage

Build your tree structure with unique node IDs
Define extra links between node IDs
Apply tree layout to get positions
Render tree edges + extra links

let dagTree =
  { tree: mkTree root children
  , extraLinks:
      [ { source: "enter", target: "merge", linkType: "flow" }
      , { source: "update", target: "merge", linkType: "flow" }
      ]
  }

-- Layout tree
let positioned = layoutDAGTree Vertical dagTree

-- Render with Tree API
renderDAGTree positioned linkGenerator

#DAGTree Source

type DAGTree nodeId datum = { extraLinks :: Array (DAGLink nodeId), getId :: datum -> nodeId, tree :: Tree datum }

A tree structure with extra non-hierarchical links.

The tree defines the layout (determines node positions). The extra links are overlaid after layout.

#DAGLink Source

type DAGLink nodeId = { linkType :: String, source :: nodeId, target :: nodeId }

A link between two nodes that isn't part of the tree hierarchy.

These links are rendered after the tree layout is computed, using the positions assigned by the tree algorithm.

#PositionedDAGTree Source

type PositionedDAGTree nodeId datum = { extraLinks :: Array { linkType :: String, source :: PositionedNode datum, target :: PositionedNode datum }, nodeMap :: Map nodeId (PositionedNode datum), nodes :: Array (PositionedNode datum), treeLinks :: Array { source :: PositionedNode datum, target :: PositionedNode datum } }

A DAG tree after layout has been applied.

Contains positioned nodes and resolved link coordinates.

#PositionedNode Source

type PositionedNode datum = { datum :: datum, depth :: Int, x :: Number, y :: Number }

A node with its computed position from tree layout.

#dagTree Source

dagTree :: forall nodeId datum. Ord nodeId => Tree datum -> (datum -> nodeId) -> DAGTree nodeId datum

Create a DAG tree from a tree and ID extractor.

let dag = dagTree myTree _.id

#addLink Source

addLink :: forall nodeId datum. DAGLink nodeId -> DAGTree nodeId datum -> DAGTree nodeId datum

Add a single extra link to a DAG tree.

dag # addLink { source: "a", target: "b", linkType: "merge" }

#addLinks Source

addLinks :: forall nodeId datum f. Foldable f => f (DAGLink nodeId) -> DAGTree nodeId datum -> DAGTree nodeId datum

Add multiple extra links to a DAG tree.

dag # addLinks
  [ { source: "a", target: "c", linkType: "merge" }
  , { source: "b", target: "c", linkType: "merge" }
  ]

#layoutDAGTree Source

layoutDAGTree :: forall nodeId datum. Ord nodeId => TreeLayout -> { height :: Number, width :: Number } -> DAGTree nodeId datum -> PositionedDAGTree nodeId datum

Apply tree layout and resolve link positions.

This computes positions for all nodes using a tree layout algorithm, then resolves the extra links to their source/target coordinates.

The layout parameter determines orientation:

Vertical: root at top, children below
Horizontal: root at left, children right
Radial: root at center, children radiating out

Note: This is a simplified layout that doesn't use D3's tree algorithms. For production use with large trees, integrate with d3.tree() or d3.cluster().

#getNodePosition Source

getNodePosition :: forall nodeId datum. Ord nodeId => nodeId -> PositionedDAGTree nodeId datum -> Maybe { x :: Number, y :: Number }

Get position of a node by ID.

#getExtraLinkPositions Source

getExtraLinkPositions :: forall nodeId datum. PositionedDAGTree nodeId datum -> Array { linkType :: String, sourceX :: Number, sourceY :: Number, targetX :: Number, targetY :: Number }

Get source and target positions for all extra links.

Useful for generating path data for link rendering.

Modules: Data.Graph.Algorithms; Data.Graph.Layout; Data.Graph.Pathfinding; Data.Graph.Pathfinding.Traced; Data.Graph.Types; Data.Graph.Weighted; Data.Graph.Weighted.DAG; Hylograph.Data.DAGTree