Connectivity (yog-fsharp)

Connectivity Module

Namespace: Yog
Assembly: Yog.FSharp.dll

Graph connectivity analysis - finding bridges, articulation points, and strongly connected components.

This module provides algorithms for analyzing the connectivity structure of graphs, identifying critical components whose removal would disconnect the graph.

Algorithms

Algorithm	Function	Use Case
Tarjan's Bridge-Finding	`analyze`	Find bridges and articulation points
Tarjan's SCC	`stronglyConnectedComponents`	Find SCCs in one pass
Kosaraju's Algorithm	`kosaraju`	Find SCCs using two DFS passes

Bridges vs Articulation Points

Bridge (cut edge): An edge whose removal increases the number of connected components. In a network, this represents a single point of failure.
Articulation Point (cut vertex): A node whose removal increases the number of connected components. These are critical nodes in the network.

Strongly Connected Components

A strongly connected component (SCC) is a maximal subgraph where every node is reachable from every other node. SCCs form a DAG when collapsed, useful for: - Identifying cycles in dependency graphs - Finding groups of mutually reachable web pages - Analyzing feedback loops in systems

All algorithms run in O(V + E) linear time.

References

Types

Type	Description
Bridge	Represents a bridge (critical edge) in an undirected graph. Bridges are stored as ordered pairs where the first node ID is smaller.
ConnectivityResults	Results from connectivity analysis containing bridges and articulation points.

Functions and values

Function or value Description


                
                  
                    
                      analyze graph

Full Usage: analyze graph

Parameters:

graph : Graph<'n, 'e>

Returns: ConnectivityResults

Analyzes an undirected graph to find all bridges and articulation points using Tarjan's algorithm in a single DFS pass.

Important: This algorithm is designed for undirected graphs. For directed graphs, use strongly connected components analysis instead.

Bridges are edges whose removal increases the number of connected components. Articulation points (cut vertices) are nodes whose removal increases the number of connected components.

Bridge ordering: Bridges are returned as (lower_id, higher_id) for consistency.

Time Complexity: O(V + E)

Example

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13:

open Yog.Model

let graph =
  empty Undirected
  |> addNode 1 ""
  |> addNode 2 ""
  |> addNode 3 ""
  |> addEdge 1 2 0
  |> addEdge 2 3 0

let results = analyze graph
// results.Bridges = [(1, 2); (2, 3)]
// results.ArticulationPoints = [2]

Use Cases

Network reliability analysis (finding single points of failure)
Road network planning (identifying critical roads)
Social network analysis (finding key connectors)
Biconnected component decomposition

namespace Yog

module Model from Yog
<summary> Core graph data structures and basic operations for the yog library. This module defines the fundamental `Graph` type and provides all basic operations for creating and manipulating graphs. The graph uses an adjacency list representation with dual indexing (both outgoing and incoming edges) for efficient traversal in both directions. </summary>

val graph: Graph<string,int>

val empty: graphType: GraphType -> Graph<'n,'e>
<summary> Creates a new empty graph of the specified type. ## Example ```fsharp let graph = Model.empty Directed ``` </summary>

union case GraphType.Undirected: GraphType
<summary> An undirected graph where edges are bidirectional. </summary>

val addNode: id: NodeId -> data: 'n -> graph: Graph<'n,'e> -> Graph<'n,'e>
<summary> Adds a node to the graph with the given ID and data. If a node with this ID already exists, its data will be replaced. ## Example ```fsharp graph |> addNode 1 "Node A" |> addNode 2 "Node B" ``` </summary>

val addEdge: src: NodeId -> dst: NodeId -> weight: 'e -> graph: Graph<'n,'e> -> Graph<'n,'e>
<summary> Adds an edge to the graph with the given weight. For directed graphs, adds a single edge from src to dst. For undirected graphs, adds edges in both directions. > **Note:** If `src` or `dst` have not been added via `addNode`, > the edge will still be created in the edge dictionaries, but the > nodes will be missing from `graph.Nodes`. This creates "ghost nodes" > that are traversable but invisible to functions that iterate over > nodes (e.g. `order`, `allNodes`). Use `addEdgeEnsured` to > auto-create missing endpoints with a default value. ## Example ```fsharp graph |> addEdge 1 2 10 ``` </summary>

val results: obj

graph : Graph<'n, 'e>

Returns: ConnectivityResults


                
                  
                    
                      kosaraju graph

Full Usage: kosaraju graph

Parameters:

graph : Graph<'n, 'e>

Returns: NodeId list list

Finds Strongly Connected Components (SCC) using Kosaraju's Algorithm.

Returns a list of components, where each component is a list of NodeIds. Kosaraju's algorithm uses two DFS passes and graph transposition:

First DFS: Compute finishing times (nodes added to stack when DFS completes)
Transpose the graph (reverse all edges) - O(1) operation!
Second DFS: Process nodes in reverse finishing time order on transposed graph

Time Complexity: O(V + E) where V is vertices and E is edges Space Complexity: O(V)

Example

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11:

let graph =
  empty Directed
  |> addNode 1 "A"
  |> addNode 2 "B"
  |> addNode 3 "C"
  |> addEdge 1 2 1
  |> addEdge 2 3 1
  |> addEdge 3 1 1  // Creates a cycle

let sccs = kosaraju graph
// => [[1; 2; 3]]  // All nodes form one SCC

Comparison with Tarjan's Algorithm

Kosaraju: Two DFS passes, requires graph transposition, simpler to understand
Tarjan: Single DFS pass, no transposition needed, uses low-link values

Both have the same O(V + E) time complexity, but Kosaraju may be preferred when: - The graph is already stored in a format supporting fast transposition - Simplicity and clarity are prioritized over single-pass execution

Use Cases

Same as Tarjan's: cycle detection, condensation graphs, 2-SAT
When you want a conceptually simpler algorithm
When graph transposition is already available (O(1) in Yog!)

val graph: obj

val sccs: obj

graph : Graph<'n, 'e>

Returns: NodeId list list


                
                  
                    
                      stronglyConnectedComponents graph

Full Usage: stronglyConnectedComponents graph

Parameters:

graph : Graph<'n, 'e>

Returns: NodeId list list

Finds Strongly Connected Components (SCC) using Tarjan's Algorithm. Returns a list of components, where each component is a list of NodeIds.

A strongly connected component is a maximal subgraph where every node is reachable from every other node. In other words, there's a path between any two nodes in the component.

Time Complexity: O(V + E)

Algorithm

Tarjan's algorithm uses a single DFS pass with a stack to track the current path. It assigns each node an index (discovery order) and a low-link value (the lowest index reachable from that node). When a node's low-link equals its index, it's the root of an SCC.

Example

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11:

let graph =
  empty Directed
  |> addNode 1 "A"
  |> addNode 2 "B"
  |> addNode 3 "C"
  |> addEdge 1 2 1
  |> addEdge 2 3 1
  |> addEdge 3 1 1  // Creates a cycle: 1->2->3->1

let sccs = stronglyConnectedComponents graph
// => [[1; 2; 3]]  // All nodes form one SCC (cycle)

Use Cases

Finding cycles in directed graphs
Condensation graph construction (SCC DAG)
2-SAT problem solving
Identifying "tightly coupled" modules in dependency graphs

Comparison with Kosaraju's Algorithm

Tarjan's: Single DFS pass, no transposition needed, uses low-link values
Kosaraju's: Two DFS passes, requires graph transposition, conceptually simpler

Both have the same O(V + E) time complexity. Tarjan's uses slightly less memory since it doesn't need the transposed graph.

val graph: obj

val sccs: obj

graph : Graph<'n, 'e>

Returns: NodeId list list