yog - v2.1.0

yog/components

Types

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

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 = components.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