Data.Graph.Decomposition

biconnectedComponents :: forall node. Ord node => SimpleGraph node -> Array (Set (Tuple node node))

Find all biconnected components (as sets of edges). Each component is a maximal subgraph with no cut vertex.

articulationPoints :: forall node. Ord node => SimpleGraph node -> Set node

Find all articulation points (cut vertices). A vertex is an articulation point if removing it disconnects the graph.

bridges :: forall node. Ord node => SimpleGraph node -> Array (Tuple node node)

Find all bridges (cut edges). An edge is a bridge iff it is the sole edge in a biconnected component.

detectBipartite :: forall node. Ord node => SimpleGraph node -> Either (Array node) { partA :: Set node, partB :: Set node }

Test if a graph is bipartite. Returns Right (partA, partB) if bipartite, or Left oddCycle if not.

data BlockCutNode node

A node in the block-cut tree

Constructors

• Block Int (Set node)
• CutVertex node

blockCutTree :: forall node. Ord node => SimpleGraph node -> { blocks :: Array (Set node), cutVertices :: Set node, tree :: Array { from :: Int, to :: Int } }

Build the block-cut tree from a graph. The tree's internal structure mirrors how the graph decomposes: blocks (dense subgraphs) connected at cut vertices (junction points).

type DecompositionMetrics = { articulationPointCount :: Int, biconnectedComponentCount :: Int, bridgeCount :: Int, isBipartite :: Boolean, isTree :: Boolean, maxBlockSize :: Int, treelikeness :: Number }

decompositionMetrics :: forall node. Ord node => SimpleGraph node -> DecompositionMetrics

Compute structural decomposition metrics for a graph

type TestGraphs = { barbell :: SimpleGraph String, bowtie :: SimpleGraph String, cycle5 :: SimpleGraph String, cycle6 :: SimpleGraph String, diamond :: SimpleGraph String, k33 :: SimpleGraph String, k5 :: SimpleGraph String, path4 :: SimpleGraph String, star8 :: SimpleGraph String, tree10 :: SimpleGraph String }

testGraphs :: TestGraphs

Collection of canonical test graphs with known properties