Module

Data.Graph.Weighted.DAG

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

Directed Acyclic Graph (DAG) as a newtype over WeightedDigraph. Provides a smart constructor that validates acyclicity and DAG-specific algorithms like topological sort and layer computation.

#DAG Source

newtype DAG node weight

A Directed Acyclic Graph (DAG) wrapping a WeightedDigraph.

The smart constructor fromWeightedDigraph guarantees acyclicity. Use unsafeFromWeightedDigraph only when you know the input is acyclic.

#DAGError Source

data DAGError node

Error when attempting to create a DAG from a cyclic graph

Constructors

CycleDetected (Array node)

Instances

(Eq node) => Eq (DAGError node)
(Show node) => Show (DAGError node)

#fromWeightedDigraph Source

fromWeightedDigraph :: forall node weight. Ord node => WeightedDigraph node weight -> Either (DAGError node) (DAG node weight)

Create a DAG from a WeightedDigraph, validating that it's acyclic.

Returns Left (CycleDetected nodes) if a cycle is found.

#unsafeFromWeightedDigraph Source

unsafeFromWeightedDigraph :: forall node weight. WeightedDigraph node weight -> DAG node weight

Create a DAG without validation.

Warning: Only use this when you know the input is acyclic. Using this with a cyclic graph will cause infinite loops in algorithms like topologicalSort and depths.

#unsafeAddEdge Source

unsafeAddEdge :: forall node weight. Ord node => node -> node -> weight -> DAG node weight -> DAG node weight

Add an edge to the DAG without cycle validation.

Warning: Only use this when you know the edge won't create a cycle. This is useful for incremental building when you trust the input is acyclic.

#toWeightedDigraph Source

toWeightedDigraph :: forall node weight. DAG node weight -> WeightedDigraph node weight

Extract the underlying WeightedDigraph

#topologicalSort Source

topologicalSort :: forall node weight. Ord node => DAG node weight -> Array node

Compute topological sort using Kahn's algorithm.

Returns nodes in dependency order (sources first, sinks last). Since we've validated acyclicity, this always succeeds.

#depths Source

depths :: forall node weight. Ord node => DAG node weight -> Map node Int

Compute depth (distance from sources) for each node using BFS.

Source nodes have depth 0. Each node's depth is 1 + max depth of its predecessors. This is the "left-to-right" distance in Sankey terminology.

#heights Source

heights :: forall node weight. Ord node => DAG node weight -> Map node Int

Compute height (distance from sinks) for each node using reverse BFS.

Sink nodes have height 0. Each node's height is 1 + max height of its successors. This is the "right-to-left" distance in Sankey terminology.

#layers Source

layers :: forall node weight. Ord node => DAG node weight -> Map node Int

Compute layer assignment for each node.

Uses depth as the primary layer (same as Sankey's "Justify" alignment). This groups nodes that can be processed in parallel.

#sources Source

sources :: forall node weight. Ord node => DAG node weight -> Array node

Get source nodes (nodes with no incoming edges)

#sinks Source

sinks :: forall node weight. Ord node => DAG node weight -> Array node

Get sink nodes (nodes with no outgoing edges)

#nodes Source

nodes :: forall node weight. DAG node weight -> Array node

Get all nodes

#edges Source

edges :: forall node weight. DAG node weight -> Array (WeightedEdge node weight)

Get all edges

#outgoing Source

outgoing :: forall node weight. Ord node => node -> DAG node weight -> Array { target :: node, weight :: weight }

Get outgoing edges from a node

#incoming Source

incoming :: forall node weight. Ord node => node -> DAG node weight -> Array { source :: node, weight :: weight }

Get incoming edges to a node

#nodeCount Source

nodeCount :: forall node weight. DAG node weight -> Int

Get the number of nodes

#edgeCount Source

edgeCount :: forall node weight. DAG node weight -> Int

Get the number of edges

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