Module

Data.Graph.Algorithms

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

Graph algorithms for directed graphs.

This module provides a comprehensive suite of algorithms for analyzing directed graphs, including:

Reachability: BFS-based traversal to find all reachable nodes
Topological Sort: Layer computation for DAGs using Data.Graph
Transitive Reduction: Remove redundant edges while preserving reachability
Cycle Detection: DFS with three-color marking to find cycles
Connected Components: Find components treating graph as undirected
Strongly Connected Components: Tarjan's algorithm for directed components
Centrality Measures: In-degree, out-degree, and combined centrality
PageRank: Iterative importance scoring with configurable damping
Community Detection: Label propagation with modularity scoring

All algorithms work with SimpleGraph, a simple adjacency-list representation. Convert to/from TaskNode arrays using the conversion utilities.

#SimpleGraph Source

type SimpleGraph node = { edges :: Map node (Set node), nodes :: Array node }

| Simple Graph Representation (Adjacency List) Simple graph as adjacency list (node -> set of targets)

#TaskNode Source

type TaskNode node = { depends :: Array node, id :: node }

| Topological Sort with Layers A node with dependencies

#LayeredNode Source

type LayeredNode node = { depends :: Array node, id :: node, layer :: Int }

A node with computed layer information

#GraphMetrics Source

type GraphMetrics = { averageDegree :: Number, componentCount :: Int, density :: Number, edgeCount :: Int, isConnected :: Boolean, isDAG :: Boolean, nodeCount :: Int }

| Graph Metrics Comprehensive metrics about a graph

#reachableFrom Source

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

| Reachability Analysis Compute all nodes reachable from a given node via BFS Uses tail recursion for efficiency

#buildGraph Source

buildGraph :: forall node. Ord node => Array (TaskNode node) -> Graph node (TaskNode node)

Build a Data.Graph from task nodes Graph k v = Graph (Map k (Tuple v (List k)))

#getTopologicalOrder Source

getTopologicalOrder :: forall node. Ord node => Array (TaskNode node) -> List node

Get topological order using Data.Graph.topologicalSort

#computeLayers Source

computeLayers :: forall node. Ord node => Array (TaskNode node) -> Map node Int

Compute layers from topological sort Layer 0: nodes with no dependencies Layer N: nodes whose dependencies are all in layers < N

#addLayers Source

addLayers :: forall node. Ord node => Array (TaskNode node) -> Array (LayeredNode node)

Add layer information to task nodes

#transitiveReduction Source

transitiveReduction :: forall node. Ord node => SimpleGraph node -> SimpleGraph node

| Transitive Reduction Remove transitive edges from a graph An edge A → C is transitive if there exists a path A → B → C Returns a new graph with only the essential (non-transitive) edges

#getRemovedEdges Source

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

Get edges that were removed by transitive reduction

#getAllEdges Source

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

Get all edges from a graph as an array of tuples

#hasCycle Source

hasCycle :: forall node. Ord node => SimpleGraph node -> Boolean

| Cycle Detection Check if a directed graph has a cycle using DFS with coloring

Uses three colors:

White (unvisited)
Gray (currently in DFS stack)
Black (completely processed)

A back edge to a gray node indicates a cycle.

#findCycle Source

findCycle :: forall node. Ord node => SimpleGraph node -> Maybe (Array node)

Find a cycle in the graph, if one exists

Returns the nodes forming the cycle (in order).

#isDAG Source

isDAG :: forall node. Ord node => SimpleGraph node -> Boolean

Check if graph is a DAG (Directed Acyclic Graph)

#connectedComponents Source

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

| Connected Components Find all connected components in an undirected graph

Note: Treats the graph as undirected (ignores edge direction). Returns an array of sets, where each set is a connected component.

#isConnected Source

isConnected :: forall node. Ord node => SimpleGraph node -> Boolean

Check if the graph is connected (as undirected)

#degreeCentrality Source

degreeCentrality :: forall node. Ord node => SimpleGraph node -> Map node Number

| Centrality Measures Compute degree centrality for all nodes

Degree centrality = (in-degree + out-degree) / (n - 1) where n is the number of nodes

#inDegreeCentrality Source

inDegreeCentrality :: forall node. Ord node => SimpleGraph node -> Map node Number

Compute in-degree centrality

In-degree centrality = in-degree / (n - 1)

#outDegreeCentrality Source

outDegreeCentrality :: forall node. Ord node => SimpleGraph node -> Map node Number

Compute out-degree centrality

Out-degree centrality = out-degree / (n - 1)

#graphMetrics Source

graphMetrics :: forall node. Ord node => SimpleGraph node -> GraphMetrics

Compute all basic metrics for a graph

#density Source

density :: forall node. Ord node => SimpleGraph node -> Number

Graph density: ratio of actual edges to possible edges

For directed graphs: |E| / (|V| * (|V| - 1)) Returns 0 for graphs with fewer than 2 nodes

#averageDegree Source

averageDegree :: forall node. Ord node => SimpleGraph node -> Number

Average degree (in + out) per node

#stronglyConnectedComponents Source

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

| Strongly Connected Components (Tarjan's Algorithm) Find all strongly connected components using Tarjan's algorithm

Returns components in reverse topological order (leaf components first). Each component is a set of nodes that are mutually reachable.

#isSCC Source

isSCC :: forall node. Ord node => SimpleGraph node -> Boolean

Check if a graph is a single SCC (strongly connected)

#pageRank Source

pageRank :: forall node. Ord node => SimpleGraph node -> Map node Number

Compute PageRank scores for all nodes

Uses the default configuration (damping factor 0.85, 100 iterations).

#pageRankWithConfig Source

pageRankWithConfig :: forall node. Ord node => PageRankConfig -> SimpleGraph node -> Map node Number

Compute PageRank with custom configuration

#PageRankConfig Source

type PageRankConfig = { dampingFactor :: Number, iterations :: Int, tolerance :: Number }

| PageRank Configuration for PageRank algorithm

#labelPropagation Source

labelPropagation :: forall node. Ord node => SimpleGraph node -> Map node node

| Community Detection (Label Propagation) Community detection using label propagation

Each node starts with its own label. In each iteration, nodes adopt the most common label among their neighbors. Returns a map from node to community label (using a representative node ID).

#modularity Source

modularity :: forall node. Ord node => SimpleGraph node -> Map node node -> Number

Compute modularity of a community assignment

Modularity measures how good a community structure is. Higher values (max 1.0) indicate better community separation.

#taskNodesToSimpleGraph Source

taskNodesToSimpleGraph :: forall node. Ord node => Array (TaskNode node) -> SimpleGraph node

| Conversion Utilities Convert TaskNode array to SimpleGraph

#simpleGraphToTaskNodes Source

simpleGraphToTaskNodes :: forall node. Ord node => SimpleGraph node -> Array (TaskNode node)

Convert SimpleGraph to TaskNode array

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