yog - v3.1.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),
)

TarjanState

</> 
pub type TarjanState {
  TarjanState(
    index: Int,
    stack: List(Int),
    on_stack: dict.Dict(Int, Bool),
    indices: dict.Dict(Int, Int),
    low_links: dict.Dict(Int, Int),
    components: List(List(Int)),
  )
}

Constructors 

  • TarjanState(
  index: Int,
  stack: List(Int),
  on_stack: dict.Dict(Int, Bool),
  indices: dict.Dict(Int, Int),
  low_links: dict.Dict(Int, Int),
  components: List(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 connectivity. Articulation points (cut vertices) are nodes whose removal increases the number of connected connectivity.

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)

kosaraju

</> 
pub fn kosaraju(graph: model.Graph(n, e)) -> List(List(Int))

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:

  1. First DFS: Compute finishing times (nodes added to stack when DFS completes)
  2. Transpose the graph (reverse all edges) - O(1) operation!
  3. 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) for the visited set and finish stack

Example

let graph =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_edge(from: 1, to: 2, with: 1)
  |> model.add_edge(from: 2, to: 3, with: 1)
  |> model.add_edge(from: 3, to: 1, with: 1)

let sccs = connectivity.kosaraju(graph)
// => [[1, 2, 3]]  // All nodes form one SCC (cycle)

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

strongly_connected_components

</> 
pub fn strongly_connected_components(
  graph: model.Graph(n, e),
) -> List(List(Int))

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

✨ Search Document