yog - v2.2.0

yog/connectivity

Types

Bridge

</>

Represents a bridge (critical edge) in an undirected graph. Bridges are stored as ordered pairs where the first node ID is smaller.

pub type Bridge =
  #(Int, Int)

ConnectivityResults

</>

Results from connectivity analysis containing bridges and articulation points.

pub type ConnectivityResults {
  ConnectivityResults(
    bridges: List(#(Int, Int)),
    articulation_points: List(Int),
  )
}

Constructors 

  • ConnectivityResults(
  bridges: List(#(Int, Int)),
  articulation_points: List(Int),
)

Values

analyze

</> 
pub fn analyze(
  in graph: model.Graph(n, e),
) -> 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.

Example

import yog
import yog/connectivity

let graph =
  yog.undirected()
  |> yog.add_node(1, Nil)
  |> yog.add_node(2, Nil)
  |> yog.add_node(3, Nil)
  |> yog.add_edge(from: 1, to: 2, with: Nil)
  |> yog.add_edge(from: 2, to: 3, with: Nil)

let results = connectivity.analyze(in: graph)
// results.bridges == [#(1, 2), #(2, 3)]
// results.articulation_points == [2]

Time Complexity: O(V + E)

✨ Search Document