Gabow's algorithm
You are encouraged to solve this task according to the task description, using any language you may know.
- Problem Statement
Gabow's algorithm is an algorithm used to find strongly connected components (SCCs) in a digraph.
Given a directed graph (digraph) with V vertices and E edges, where vertices are represented as integers from 0 to V-1 and edges are directed from one vertex to another, design an algorithm to identify all strongly connected components (SCCs). A strongly connected component is a maximal subset of vertices in the digraph such that for every pair of vertices v and w in the subset, there exists a directed path from v to w and from w to v. The algorithm should:
- Compute the number of SCCs in the digraph.
- Assign each vertex to its corresponding SCC.
- Provide a way to query whether two vertices belong to the same SCC.
- Return the component identifier for any given vertex.
- Input
- A directed graph G represented as an adjacency list, where:
- V is the number of vertices (non-negative integer).
- Edges are provided as pairs (v, w), indicating a directed edge from vertex v to vertex w.
- The vertices are integers in the range [0, V-1].
- Output
- The total number of strongly connected components in the digraph.
- An assignment of each vertex to a unique component identifier (an integer ≥ 0).
- A mechanism to check if two vertices v and w are strongly connected (i.e., belong to the same SCC).
- The ability to retrieve the component ID of any vertex v.
- Constraints
- V ≥ 0 (the graph can be empty).
- Edges (v, w) must satisfy 0 ≤ v, w < V.
- The graph may contain cycles, self-loops, or parallel edges (though parallel edges are effectively ignored in this implementation as duplicates in adjacency lists are allowed but not explicitly handled).
- Example
Consider a digraph with V = 13 vertices and the following edges:
(4, 2), (2, 3), (3, 2), (6, 0), (0, 1), (2, 0), (11, 12), (12, 9), (9, 10), (9, 11), (8, 9), (10, 12), (0, 5), (5, 4), (3, 5), (6, 4), (6, 9), (7, 6), (7, 8), (8, 7), (5, 3), (0, 6)
- Compute the SCCs.
- Determine how many SCCs exist.
- List the vertices in each SCC.
- Check if specific pairs of vertices (e.g., 0 and 3, 0 and 7) are strongly connected.
C++
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <stack>
#include <stdexcept>
#include <string>
#include <vector>
/**
* Representation of a directed graph, or digraph, using adjacency lists.
* Vertices are identified by integers starting from zero.
*/
class Digraph {
public:
Digraph(const uint32_t& a_vertex_count) {
if ( a_vertex_count < 0 ) {
throw std::invalid_argument("Number of vertices must be non-negative");
}
vertex_count = a_vertex_count;
edge_count = 0;
adjacency_lists = { vertex_count, std::vector<uint32_t>() };
}
void add_edge(const uint32_t& from, const uint32_t& to) {
validate_vertex(from);
validate_vertex(to);
adjacency_lists[from].emplace_back(to);
edge_count++;
}
std::string to_string() {
std::string result = "Digraph has " + std::to_string(vertex_count) + " vertices and "
+ std::to_string(edge_count) + " edges" + "\n" + "Adjacency lists:" + "\n";
for ( uint32_t vertex = 0; vertex < vertex_count; ++vertex ) {
result += ( vertex < 10 ? " " : "" ) + std::to_string(vertex) + ": ";
std::sort(adjacency_lists[vertex].begin(), adjacency_lists[vertex].end());
for ( const uint32_t& adjacent : adjacency_lists[vertex] ) {
result += std::to_string(adjacent) + " ";
}
result += "\n";
}
return result;
}
uint32_t get_vertex_count() const {
return vertex_count;
}
uint32_t get_edge_count() const {
return edge_count;
}
std::vector<uint32_t> get_adjacency_list(const uint32_t& vertex) const {
validate_vertex(vertex);
return adjacency_lists[vertex];
}
private:
void validate_vertex(const uint32_t& vertex) const {
if ( vertex < 0 || vertex >= vertex_count ) {
throw std::invalid_argument(
"Vertex must be between 0 " + std::to_string(vertex_count) + ": " + std::to_string(vertex));
}
}
uint32_t vertex_count;
uint32_t edge_count;
std::vector<std::vector<uint32_t>> adjacency_lists;
};
/**
* Determination of the strongly connected components (SCC's) of a directed graph using Gabow's algorithm.
*/
class Gabow_SCC {
public:
Gabow_SCC(const Digraph& digraph) {
visited.assign(digraph.get_vertex_count(), false);
component_IDs.assign(digraph.get_vertex_count(), UNDEFINED);
preorders.assign(digraph.get_vertex_count(), UNDEFINED);
preorder_count = 0;
scc_count = 0;
for ( uint32_t vertex = 0; vertex < digraph.get_vertex_count(); ++vertex ) {
if ( ! visited[vertex] ) {
depth_first_search(digraph, vertex);
}
}
}
// Return, for each vertex, a list of its strongly connected vertices
std::vector<std::vector<uint32_t>> get_components() {
std::vector<std::vector<uint32_t>> components = { scc_count, std::vector<uint32_t>() };
for ( uint32_t vertex = 0; vertex < visited.size(); ++vertex ) {
const uint32_t component_id = get_component_ID(vertex);
if ( component_id != UNDEFINED ) { // This would normally be true
components[component_id].emplace_back(vertex);
} else {
// Could be caused by the digraph edges being changed by the user
throw std::invalid_argument(
"Warning: Vertex " + std::to_string(vertex) + " has no SCC ID assigned.");
}
}
return components;
}
// Return whether or not vertices 'v' and 'w' are in the same strongly connected component.
bool is_strongly_connected(const uint32_t& v, const uint32_t& w) const {
validate_vertex(v);
validate_vertex(w);
// If either vertex was not visited, for example, due to it being in an unconnected graph component,
// its component_ID will be 'UNDEFINED', and they cannot be strongly connected unless
// the graph is empty or has isolated vertices which is handled by the return condition below.
return component_IDs[v] != UNDEFINED && component_IDs[v] == component_IDs[w];
}
// Return the component ID of the strong component containing 'vertex'.
uint32_t get_component_ID(const uint32_t& vertex) const {
validate_vertex(vertex);
return component_IDs[vertex];
}
uint32_t get_scc_count() const {
return scc_count;
}
private:
void depth_first_search(const Digraph& digraph, const uint32_t& vertex) {
visited[vertex] = true;
preorders[vertex] = preorder_count;
preorder_count++;
visited_vertices_stack.push(vertex);
auxiliary_stack.push(vertex);
for ( const uint32_t& adjacent : digraph.get_adjacency_list(vertex) ) {
if ( ! visited[adjacent] ) {
depth_first_search(digraph, adjacent);
// If 'adjacent' is visited, but not yet assigned to a SCC,
// then 'adjacent' is on the current depth first path,
// or in a SCC which has already been processed in this depth first path,
// and this will be handled by the 'auxiliary_stack'.
} else if ( component_IDs[adjacent] == UNDEFINED ) {
// Pop vertices from the 'auxiliary_stack'
// until the top vertex has a preorder <= preorder of 'adjacent'.
// This maintains the invariant that 'auxiliary_stack' contains a path of potential SCC roots.
while ( ! auxiliary_stack.empty() && preorders[auxiliary_stack.top()] > preorders[adjacent] ) {
auxiliary_stack.pop();
}
}
}
// 'vertex' is the root of a SCC,
// if it remains on top of the 'auxiliary_stack' after exploring all of its descendants and back-edges.
if ( ! auxiliary_stack.empty() && auxiliary_stack.top() == vertex ) {
auxiliary_stack.pop();
// Pop vertices from the 'auxiliart_stack' until 'vertex' is popped,
// and assign these vertices the current strongly connected component id.
while ( ! visited_vertices_stack.empty() ) {
const uint32_t adjacent = visited_vertices_stack.top();
visited_vertices_stack.pop();
component_IDs[adjacent] = scc_count;
if ( adjacent == vertex ) {
break;
}
}
scc_count++;
}
}
void validate_vertex(const uint32_t& vertex) const {
const uint32_t visited_count = visited.size();
if ( vertex < 0 || vertex >= visited_count ) {
throw std::invalid_argument(
"Vertex " + std::to_string(vertex) + " is not between 0 and " + std::to_string(visited_count - 1));
}
}
std::vector<bool> visited; // stores the vertices that have been visited
std::vector<uint32_t> component_IDs; // the unique id number of each strongly connected component
std::vector<uint32_t> preorders; // stores the preorder of vertices
uint32_t preorder_count; // the number of preorders of vertices
uint32_t scc_count; // the number of strongly connected components
std::stack<uint32_t> visited_vertices_stack; // stores vertices in the order of their visit
std::stack<uint32_t> auxiliary_stack; // auxiliary stack for finding SCC roots
const uint32_t UNDEFINED = -1;
};
int main() {
struct Edge {
uint32_t from;
uint32_t to;
};
const std::vector<Edge> edges = { Edge{4, 2}, Edge{2, 3}, Edge{3, 2}, Edge{6, 0}, Edge{0, 1}, Edge{2, 0},
Edge{11, 12}, Edge{12, 9}, Edge{9, 10}, Edge{9, 11}, Edge{8, 9}, Edge{10, 12}, Edge{0, 5}, Edge{5, 4},
Edge{3, 5}, Edge{6, 4}, Edge{6, 9}, Edge{7, 6}, Edge{7, 8}, Edge{8, 7}, Edge{5, 3}, Edge{0, 6} };
Digraph digraph(13);
for ( const Edge& edge : edges ) {
digraph.add_edge(edge.from, edge.to);
}
std::cout << "Constructed digraph:" << std::endl;
std::cout << digraph.to_string() << std::endl;
Gabow_SCC gabow_SCC(digraph);
std::cout << "It has " << gabow_SCC.get_scc_count() << " strongly connected components." << std::endl;
const std::vector<std::vector<uint32_t>> components = gabow_SCC.get_components();
std::cout << "\n" << "Components:" << std::endl;
for ( uint32_t i = 0; i < components.size(); ++i ) {
std::cout << "Component " << i << ": ";
for ( const uint32_t& vertex : components[i] ) {
std::cout << vertex << " ";
}
std::cout << std::endl;
}
// Example usage of the is_strongly_connected() and get_component_ID() methods
std::cout << "\n" << "Example connectivity checks:" << std::boolalpha << std::endl;
std::cout << "Vertices 0 and 3 strongly connected? " << gabow_SCC.is_strongly_connected(0, 3) << std::endl;
std::cout << "Vertices 0 and 7 strongly connected? " << gabow_SCC.is_strongly_connected(0, 7) << std::endl;
std::cout << "Vertices 9 and 12 strongly connected? " << gabow_SCC.is_strongly_connected(9, 12) << std::endl;
std::cout << "Component ID of vertex 5: " << gabow_SCC.get_component_ID(5) << std::endl;
std::cout << "Component ID of vertex 8: " << gabow_SCC.get_component_ID(8) << std::endl;
}
- Output:
Constructed digraph: Digraph has 13 vertices and 22 edges Adjacency lists: 0: 1 5 6 1: 2: 0 3 3: 2 5 4: 2 5: 3 4 6: 0 4 9 7: 6 8 8: 7 9 9: 10 11 10: 12 11: 12 12: 9 It has 4 strongly connected components. Components: Component 0: 1 Component 1: 9 10 11 12 Component 2: 0 2 3 4 5 6 Component 3: 7 8 Example connectivity checks: Vertices 0 and 3 strongly connected? true Vertices 0 and 7 strongly connected? false Vertices 9 and 12 strongly connected? true Component ID of vertex 5: 2 Component ID of vertex 8: 3
CLU
#extend
edge = struct[from: int, to: int]
digraph = cluster is create, cons2, get_vertex_count, get_edge_count,
add_edge, adjacency_list, vertices
rep = record[
vertex_count: int,
edge_count: int,
adjacency_lists: array[array[int]]
]
create = proc (vertex_count: int) returns (cvt)
return(down(cons2(vertex_count, sequence[edge]$[])))
end create
cons2 = proc (vertex_count: int, edges: sequence[edge])
returns (cvt) signals (bad_vertex)
dg: rep := rep${
vertex_count: vertex_count,
edge_count: 0,
adjacency_lists:
array[array[int]]$fill_copy(0, vertex_count, array[int]$[])
}
for e: edge in sequence[edge]$elements(edges) do
add_edge(up(dg), e) resignal bad_vertex
end
return(dg)
end cons2
vertices = iter (dg: cvt) yields (int)
for v: int in int$from_to(0, dg.vertex_count-1) do
yield(v)
end
end vertices
validate_vertex = proc (dg: cvt, vertex: int) signals (bad_vertex)
if vertex < 0 cor vertex >= dg.vertex_count then
signal bad_vertex
end
end validate_vertex
add_edge = proc (dg: cvt, e: edge) signals (bad_vertex)
validate_vertex(up(dg), e.from) resignal bad_vertex
validate_vertex(up(dg), e.to) resignal bad_vertex
array[int]$addh(dg.adjacency_lists[e.from], e.to)
dg.edge_count := dg.edge_count + 1
end add_edge
get_vertex_count = proc (dg: cvt) returns (int)
return(dg.vertex_count)
end get_vertex_count
get_edge_count = proc (dg: cvt) returns (int)
return(dg.edge_count)
end get_edge_count
adjacency_list = proc (dg: cvt, vertex: int)
returns (sequence[int]) signals (bad_vertex)
validate_vertex(up(dg), vertex) resignal bad_vertex
return(sequence[int]$a2s(dg.adjacency_lists[vertex]))
end adjacency_list
end digraph
gabow_ssc = cluster is create, components, get_scc_count,
is_strongly_connected, component_id
undefined = -1
rep = record[
visited: array[bool],
component_ids: array[int],
preorders: array[int],
scc_count: int,
preorder_count: int,
visited_vertices_stack: array[int],
aux_stack: array[int]
]
create = proc (dg: digraph) returns (cvt)
gs: rep := rep${
visited: array[bool]$fill(0, dg.vertex_count, false),
component_ids: array[int]$fill(0, dg.vertex_count, undefined),
preorders: array[int]$fill(0, dg.vertex_count, undefined),
scc_count: 0,
preorder_count: 0,
visited_vertices_stack: array[int]$[],
aux_stack: array[int]$[]
}
for vertex: int in digraph$vertices(dg) do
if ~gs.visited[vertex] then
dfs(gs, dg, vertex)
end
end
return(gs)
end create
components = iter (gs: cvt) yields (sequence[int])
cs: array[array[int]] :=
array[array[int]]$fill_copy(0, gs.scc_count, array[int]$[])
for vertex: int in array[bool]$indexes(gs.visited) do
id: int := component_id(up(gs), vertex)
array[int]$addh(cs[id], vertex)
end
for component: array[int] in array[array[int]]$elements(cs) do
yield(sequence[int]$a2s(component))
end
end components
get_scc_count = proc (gs: cvt) returns (int)
return(gs.scc_count)
end get_scc_count
component_id = proc (gs: cvt, vertex: int) returns (int) signals (bad_vertex)
validate_vertex(gs, vertex) resignal bad_vertex
return(gs.component_ids[vertex])
end component_id
is_strongly_connected = proc (gs: cvt, v, w: int) returns (bool) signals (bad_vertex)
validate_vertex(gs, v) resignal bad_vertex
validate_vertex(gs, w) resignal bad_vertex
return(gs.component_ids[v] ~= undefined cand
gs.component_ids[v] = gs.component_ids[w]);
end is_strongly_connected
dfs = proc (gs: rep, dg: digraph, vertex: int)
gs.visited[vertex] := true
gs.preorders[vertex] := gs.preorder_count
gs.preorder_count := gs.preorder_count + 1
array[int]$addh(gs.visited_vertices_stack, vertex)
array[int]$addh(gs.aux_stack, vertex)
for adjacent: int in sequence[int]$elements(digraph$adjacency_list(dg, vertex)) do
if ~gs.visited[adjacent] then
dfs(gs, dg, adjacent)
elseif gs.component_ids[adjacent] = undefined then
while ~array[int]$empty(gs.aux_stack)
cand gs.preorders[array[int]$top(gs.aux_stack)] > gs.preorders[adjacent]
do
array[int]$remh(gs.aux_stack)
end
end
end
if ~array[int]$empty(gs.aux_stack)
cand array[int]$top(gs.aux_stack) = vertex then
array[int]$remh(gs.aux_stack)
while ~array[int]$empty(gs.visited_vertices_stack) do
adjacent: int := array[int]$remh(gs.visited_vertices_stack)
gs.component_ids[adjacent] := gs.scc_count
if adjacent = vertex then break end
end
gs.scc_count := gs.scc_count + 1
end
end dfs
validate_vertex = proc (gs: rep, vertex: int) signals (bad_vertex)
if vertex < 0 cor vertex >= array[bool]$size(gs.visited) then
signal bad_vertex
end
end validate_vertex
end gabow_ssc
start_up = proc ()
po: stream := stream$primary_output()
dg: digraph := digraph$[13:
edge${from: 4, to: 2}, edge${from: 2, to: 3}, edge${from: 3, to: 2},
edge${from: 6, to: 0}, edge${from: 0, to: 1}, edge${from: 2, to: 0},
edge${from: 11, to: 12}, edge${from: 12, to: 9}, edge${from: 9, to: 10},
edge${from: 9, to: 11}, edge${from: 8, to: 9}, edge${from: 10, to: 12},
edge${from: 0, to: 5}, edge${from: 5, to: 4}, edge${from: 3, to: 5},
edge${from: 6, to: 4}, edge${from: 6, to: 9}, edge${from: 7, to: 6},
edge${from: 7, to: 8}, edge${from: 8, to: 7}, edge${from: 5, to: 3},
edge${from: 0, to: 6}
]
stream$putl(po, "Digraph has " || int$unparse(dg.vertex_count) ||
" vertices and " || int$unparse(dg.edge_count) ||
" edges.")
stream$putl(po, "Adjacency lists: ")
for v: int in digraph$vertices(dg) do
stream$putright(po, int$unparse(v) || ":", 3)
for w: int in sequence[int]$elements(digraph$adjacency_list(dg, v)) do
stream$puts(po, " " || int$unparse(w))
end
stream$putl(po, "")
end
stream$putl(po, "")
gs: gabow_ssc := gabow_ssc$create(dg)
stream$putl(po, "It has " || int$unparse(gs.scc_count) ||
" strongly connected components:")
for c: sequence[int] in gabow_ssc$components(gs) do
stream$puts(po, "*")
for v: int in sequence[int]$elements(c) do
stream$puts(po, " " || int$unparse(v))
end
stream$putl(po, "")
end
stream$putl(po, "")
stream$putl(po, "Example connectivity checks:")
for e: edge in sequence[edge]$elements(sequence[edge]$[
edge${from: 0, to: 3}, edge${from: 0, to: 7}, edge${from: 9, to: 12}]) do
stream$puts(po, "Vertices " || int$unparse(e.from) || " and " ||
int$unparse(e.to) || " strongly connected? ")
if gabow_ssc$is_strongly_connected(gs, e.from, e.to) then
stream$putl(po, "yes")
else
stream$putl(po, "no")
end
end
stream$putl(po, "Component ID of vertex 5: " ||
int$unparse(gabow_ssc$component_id(gs, 5)))
stream$putl(po, "Component ID of vertex 8: " ||
int$unparse(gabow_ssc$component_id(gs, 8)))
end start_up- Output:
Digraph has 13 vertices and 22 edges. Adjacency lists: 0: 1 5 6 1: 2: 3 0 3: 2 5 4: 2 5: 4 3 6: 0 4 9 7: 6 8 8: 9 7 9: 10 11 10: 12 11: 12 12: 9 It has 4 strongly connected components: * 1 * 9 10 11 12 * 0 2 3 4 5 6 * 7 8 Example connectivity checks: Vertices 0 and 3 strongly connected? yes Vertices 0 and 7 strongly connected? no Vertices 9 and 12 strongly connected? yes Component ID of vertex 5: 2 Component ID of vertex 8: 3
FreeBASIC
Const NULL As Any Ptr = 0 ' o usar #include "crt.bi"
' Basic Directed Graph class using adjacency lists.
' Vertices are assumed to be integers from 0 to v-1.
' ===== Digraph Implementation =====
Type Edge
dest As Integer
End Type
Type AdjList
edges As Integer
capacity As Integer
list As Edge Ptr
End Type
Type Digraph
v As Integer ' number of vertices
e As Integer ' number of edges
adj As AdjList Ptr ' adjacency lists
End Type
' Creates a new digraph with v vertices
Function CreateDigraph(v As Integer) As Digraph Ptr
If v < 0 Then
Print "Number of vertices must be non-negative"
Return NULL
End If
Dim As Digraph Ptr g = Allocate(Sizeof(Digraph))
g->v = v
g->e = 0
' Create adjacency lists
g->adj = Allocate(v * Sizeof(AdjList))
For i As Integer = 0 To v - 1
g->adj[i].edges = 0
g->adj[i].capacity = 4 ' Initial capacity
g->adj[i].list = Allocate(4 * Sizeof(Edge))
Next
Return g
End Function
' Adds the directed edge v->w to the digraph
Sub AddEdge(g As Digraph Ptr, v As Integer, w As Integer)
' Validate vertices
If v < 0 Or v >= g->v Or w < 0 Or w >= g->v Then
Print "Invalid vertex in AddEdge: " & v & " -> " & w
Return
End If
' Resize if needed
With g->adj[v]
If .edges >= .capacity Then
.capacity *= 2
.list = Reallocate(.list, .capacity * Sizeof(Edge))
End If
.list[.edges].dest = w
.edges += 1
End With
g->e += 1
End Sub
' String representation of the digraph
Sub PrintDigraph(g As Digraph Ptr)
Print g->v & " vertices, " & g->e & " edges"
For v As Integer = 0 To g->v - 1
Print Iif(v < 10, " ", "") & v & ": ";
For i As Integer = 0 To g->adj[v].edges - 1
Print g->adj[v].list[i].dest & " ";
Next
Print
Next
End Sub
' Free memory used by the digraph
Sub FreeDigraph(g As Digraph Ptr)
If g = NULL Then Return
For i As Integer = 0 To g->v - 1
Deallocate(g->adj[i].list)
Next
Deallocate(g->adj)
Deallocate(g)
End Sub
' ===== Stack Implementation =====
Type Stack
items As Integer Ptr
size As Integer
capacity As Integer
End Type
Function CreateStack(initialCapacity As Integer = 10) As Stack
Dim As Stack s
s.capacity = initialCapacity
s.size = 0
s.items = Allocate(s.capacity * Sizeof(Integer))
Return s
End Function
Sub PushStack(s As Stack Ptr, item As Integer)
If s->size >= s->capacity Then
s->capacity *= 2
s->items = Reallocate(s->items, s->capacity * Sizeof(Integer))
End If
s->items[s->size] = item
s->size += 1
End Sub
Function PopStack(s As Stack Ptr) As Integer
If s->size <= 0 Then Return -1
s->size -= 1
Return s->items[s->size]
End Function
Function PeekStack(s As Stack Ptr) As Integer
If s->size <= 0 Then Return -1
Return s->items[s->size - 1]
End Function
Function IsEmptyStack(s As Stack Ptr) As Boolean
Return s->size <= 0
End Function
Sub FreeStack(s As Stack Ptr)
Deallocate(s->items)
s->size = 0
s->capacity = 0
End Sub
' ===== Gabow SCC Implementation =====
Type GabowSCC
marked As Boolean Ptr ' marked[v] = has v been visited?
id As Integer Ptr ' id[v] = id of strong component containing v
preorder As Integer Ptr ' preorder[v] = preorder of v
preCounter As Integer ' preorder number counter
sccCount As Integer ' number of strongly connected components
stack1 As Stack ' stores vertices in order of visitation
stack2 As Stack ' auxiliary stack for finding SCC roots
End Type
' Private method containing 'depth first search' core logic for Gabow's algorithm
Sub DFS(scc As GabowSCC Ptr, g As Digraph Ptr, v As Integer)
Dim As Integer w, i
scc->marked[v] = True
scc->preorder[v] = scc->preCounter
scc->preCounter += 1
PushStack(@scc->stack1, v)
PushStack(@scc->stack2, v)
' Process all adjacent vertices
With g->adj[v]
For i = 0 To .edges - 1
w = .list[i].dest
If Not scc->marked[w] Then
DFS(scc, g, w)
Elseif scc->id[w] = -1 Then
' Pop vertices from stack2 until top has preorder number <= preorder[w]
While Not IsEmptyStack(@scc->stack2) Andalso _
scc->preorder[PeekStack(@scc->stack2)] > scc->preorder[w]
PopStack(@scc->stack2)
Wend
End If
Next
End With
' If v is the root of an SCC
If Not IsEmptyStack(@scc->stack2) Andalso PeekStack(@scc->stack2) = v Then
PopStack(@scc->stack2)
' Pop vertices from stack1 until v is popped; assign them the current SCC id
Do
w = PopStack(@scc->stack1)
scc->id[w] = scc->sccCount
If w = v Then Exit Do
Loop
scc->sccCount += 1
End If
End Sub
' Creates a GabowSCC to compute the strong components of the digraph
Function CreateGabowSCC(g As Digraph Ptr) As GabowSCC Ptr
Dim As Integer i, v
Dim As GabowSCC Ptr scc = Allocate(Sizeof(GabowSCC))
' Allocate and initialize arrays
scc->marked = Allocate(g->v * Sizeof(Boolean))
scc->id = Allocate(g->v * Sizeof(Integer))
scc->preorder = Allocate(g->v * Sizeof(Integer))
' Initialize arrays with default values
For i = 0 To g->v - 1
scc->marked[i] = False
scc->id[i] = -1
scc->preorder[i] = -1
Next
scc->preCounter = 0
scc->sccCount = 0
scc->stack1 = CreateStack(g->v) ' Pre-allocate with expected size
scc->stack2 = CreateStack(g->v) ' Pre-allocate with expected size
' Run DFS from each unvisited vertex
For v = 0 To g->v - 1
If Not scc->marked[v] Then DFS(scc, g, v)
Next
Return scc
End Function
' Returns the number of strong components
Function Count(scc As GabowSCC Ptr) As Integer
Return scc->sccCount
End Function
' Returns whether or not vertices v and w are in the same strong component
Function StronglyConnected(scc As GabowSCC Ptr, v As Integer, w As Integer, vertexCount As Integer) As Boolean
If v < 0 Or v >= vertexCount Or w < 0 Or w >= vertexCount Then Return False
Return scc->id[v] <> -1 Andalso scc->id[v] = scc->id[w]
End Function
' Returns the component id of the strong component containing vertex v
Function GetId(scc As GabowSCC Ptr, v As Integer, vertexCount As Integer) As Integer
If v < 0 Or v >= vertexCount Then Return -1
Return scc->id[v]
End Function
' Free memory used by the GabowSCC
Sub FreeGabowSCC(scc As GabowSCC Ptr)
If scc = NULL Then Return
Deallocate(scc->marked)
Deallocate(scc->id)
Deallocate(scc->preorder)
FreeStack(@scc->stack1)
FreeStack(@scc->stack2)
Deallocate(scc)
End Sub
' ===== Main Program =====
Sub main()
Dim As Integer i, j, m, v, componentId
' Create graph with 13 vertices
Dim As Integer numVertices = 13
Dim As Digraph Ptr g = CreateDigraph(numVertices)
' Define edges
Dim As Integer edges(21, 1) => { _
{4, 2}, {2, 3}, {3, 2}, {6, 0}, {0, 1}, {2, 0}, {11, 12}, _
{12, 9}, {9, 10}, {9, 11}, {8, 9}, {10, 12}, {0, 5}, {5, 4}, _
{3, 5}, {6, 4}, {6, 9}, {7, 6}, {7, 8}, {8, 7}, {5, 3}, {0, 6} }
' Add edges to graph
For i = 0 To 21
AddEdge(g, edges(i, 0), edges(i, 1))
Next
Print "Constructed Digraph:"
PrintDigraph(g)
' Compute SCCs
Dim As GabowSCC Ptr scc = CreateGabowSCC(g)
m = Count(scc)
Print !"\n" & m & " strongly connected components"
' Group vertices by component ID
Type Component
vertices As Integer Ptr
size As Integer
capacity As Integer
End Type
Dim As Component Ptr components = Allocate(m * Sizeof(Component))
' Initialize components with reasonable initial capacity
For i = 0 To m - 1
components[i].size = 0
components[i].capacity = 4
components[i].vertices = Allocate(4 * Sizeof(Integer))
Next
' Add vertices to their components
For v = 0 To g->v - 1
componentId = GetId(scc, v, g->v)
If componentId <> -1 Then
With components[componentId]
' Resize if needed
If .size >= .capacity Then
.capacity *= 2
.vertices = Reallocate(.vertices, .capacity * Sizeof(Integer))
End If
.vertices[.size] = v
.size += 1
End With
Else
Print "Warning: Vertex " & v & " has no SCC ID assigned."
End If
Next
Print !"\nComponents:"
For i = 0 To m - 1
Print "Component " & i & ": ";
For j = 0 To components[i].size - 1
Print components[i].vertices[j] & " ";
Next
Print
Next
' Example usage of strongly_connected and get_id
Print !"\nConnectivity checks:"
Print "Vertices 0 and 3 strongly connected? " & StronglyConnected(scc, 0, 3, g->v)
Print "Vertices 0 and 7 strongly connected? " & StronglyConnected(scc, 0, 7, g->v)
Print "Vertices 9 and 12 strongly connected? " & StronglyConnected(scc, 9, 12, g->v)
Print "ID of vertex 5: " & GetId(scc, 5, g->v)
Print "ID of vertex 8: " & GetId(scc, 8, g->v)
' Free memory
For i = 0 To m - 1
Deallocate(components[i].vertices)
Next
Deallocate(components)
FreeGabowSCC(scc)
FreeDigraph(g)
End Sub
main()
Sleep
- Output:
Same as Wren entry.
Go
package main
import (
"fmt"
"strings"
)
// Digraph represents a directed graph using adjacency lists
type Digraph struct {
v int // number of vertices
e int // number of edges
adj [][]int // adjacency lists
}
// NewDigraph initializes an empty digraph with V vertices
func NewDigraph(v int) (*Digraph, error) {
if v < 0 {
return nil, fmt.Errorf("number of vertices must be non-negative")
}
adj := make([][]int, v)
for i := 0; i < v; i++ {
adj[i] = make([]int, 0)
}
return &Digraph{
v: v,
e: 0,
adj: adj,
}, nil
}
// V returns the number of vertices
func (g *Digraph) V() int {
return g.v
}
// E returns the number of edges
func (g *Digraph) E() int {
return g.e
}
// validateVertex raises an error if v is not a valid vertex
func (g *Digraph) validateVertex(v int) error {
if v < 0 || v >= g.v {
return fmt.Errorf("vertex %d is not between 0 and %d", v, g.v-1)
}
return nil
}
// AddEdge adds the directed edge v->w to the digraph
func (g *Digraph) AddEdge(v, w int) error {
if err := g.validateVertex(v); err != nil {
return err
}
if err := g.validateVertex(w); err != nil {
return err
}
g.adj[v] = append(g.adj[v], w)
g.e++
return nil
}
// Adj returns the list of neighbors adjacent from vertex v
func (g *Digraph) Adj(v int) ([]int, error) {
if err := g.validateVertex(v); err != nil {
return nil, err
}
return g.adj[v], nil
}
// String returns a string representation of the digraph
func (g *Digraph) String() string {
var sb strings.Builder
fmt.Fprintf(&sb, "%d vertices, %d edges\n", g.v, g.e)
for v := 0; v < g.v; v++ {
sb.WriteString(fmt.Sprintf("%d: ", v))
for _, w := range g.adj[v] {
sb.WriteString(fmt.Sprintf("%d ", w))
}
sb.WriteString("\n")
}
return sb.String()
}
// GabowSCC computes strongly connected components (SCCs) in a digraph using Gabow's algorithm
type GabowSCC struct {
marked []bool // marked[v] = has v been visited?
id []int // id[v] = id of strong component containing v
preorder []int // preorder[v] = preorder of v
preCounter int // preorder number counter
sccCount int // number of strongly-connected components
stack1 []int // Stores vertices in order of visitation
stack2 []int // Auxiliary stack for finding SCC roots
}
// NewGabowSCC computes the strong components of the digraph G
func NewGabowSCC(g *Digraph) *GabowSCC {
marked := make([]bool, g.V())
id := make([]int, g.V())
preorder := make([]int, g.V())
// Initialize id array with -1
for i := range id {
id[i] = -1
}
scc := &GabowSCC{
marked: marked,
id: id,
preorder: preorder,
preCounter: 0,
sccCount: 0,
stack1: make([]int, 0),
stack2: make([]int, 0),
}
for v := 0; v < g.V(); v++ {
if !scc.marked[v] {
scc.dfs(g, v)
}
}
return scc
}
// dfs implements depth-first search core logic for Gabow's algorithm
func (scc *GabowSCC) dfs(g *Digraph, v int) {
scc.marked[v] = true
scc.preorder[v] = scc.preCounter
scc.preCounter++
scc.stack1 = append(scc.stack1, v)
scc.stack2 = append(scc.stack2, v)
adj, _ := g.Adj(v)
for _, w := range adj {
if !scc.marked[w] {
scc.dfs(g, w)
} else if scc.id[w] == -1 {
// Pop vertices from stack2 until top has preorder number <= preorder[w]
for len(scc.stack2) > 0 && scc.preorder[scc.stack2[len(scc.stack2)-1]] > scc.preorder[w] {
scc.stack2 = scc.stack2[:len(scc.stack2)-1] // Pop
}
}
}
// If v is the root of an SCC
if len(scc.stack2) > 0 && scc.stack2[len(scc.stack2)-1] == v {
// Pop v from stack2
scc.stack2 = scc.stack2[:len(scc.stack2)-1]
// Pop vertices from stack1 until v is popped; assign them the current SCC id
for {
l := len(scc.stack1)
if l == 0 {
break
}
w := scc.stack1[l-1]
scc.stack1 = scc.stack1[:l-1] // Pop
scc.id[w] = scc.sccCount
if w == v {
break
}
}
scc.sccCount++
}
}
// Count returns the number of strong components
func (scc *GabowSCC) Count() int {
return scc.sccCount
}
// validateVertex raises an error if v is not a valid vertex
func (scc *GabowSCC) validateVertex(v int) error {
if v < 0 || v >= len(scc.marked) {
return fmt.Errorf("vertex %d is not between 0 and %d", v, len(scc.marked)-1)
}
return nil
}
// StronglyConnected returns true if vertices v and w are in the same strong component
func (scc *GabowSCC) StronglyConnected(v, w int) (bool, error) {
if err := scc.validateVertex(v); err != nil {
return false, err
}
if err := scc.validateVertex(w); err != nil {
return false, err
}
return scc.id[v] != -1 && scc.id[v] == scc.id[w], nil
}
// GetID returns the component id of the strong component containing vertex v
func (scc *GabowSCC) GetID(v int) (int, error) {
if err := scc.validateVertex(v); err != nil {
return -1, err
}
return scc.id[v], nil
}
func main() {
// Manually construct the digraph (same as in Python code)
numVertices := 13
g, err := NewDigraph(numVertices)
if err != nil {
fmt.Printf("Error creating digraph: %v\n", err)
return
}
edges := [][2]int{
{4, 2}, {2, 3}, {3, 2}, {6, 0}, {0, 1}, {2, 0}, {11, 12},
{12, 9}, {9, 10}, {9, 11}, {8, 9}, {10, 12}, {0, 5}, {5, 4},
{3, 5}, {6, 4}, {6, 9}, {7, 6}, {7, 8}, {8, 7}, {5, 3}, {0, 6},
}
for _, edge := range edges {
v, w := edge[0], edge[1]
if err := g.AddEdge(v, w); err != nil {
fmt.Printf("Error adding edge %d->%d: %v\n", v, w, err)
return
}
}
fmt.Println("Constructed Digraph:")
fmt.Println(g)
// Compute SCCs
scc := NewGabowSCC(g)
// Print results
m := scc.Count()
fmt.Printf("%d strongly connected components\n", m)
// Group vertices by component ID
components := make([][]int, m)
for i := range components {
components[i] = make([]int, 0)
}
for v := 0; v < g.V(); v++ {
componentID, err := scc.GetID(v)
if err != nil {
fmt.Printf("Error getting ID for vertex %d: %v\n", v, err)
continue
}
if componentID != -1 {
components[componentID] = append(components[componentID], v)
} else {
fmt.Printf("Warning: Vertex %d has no SCC ID assigned.\n", v)
}
}
fmt.Println("\nComponents:")
for i := 0; i < m; i++ {
fmt.Printf("Component %d: ", i)
for _, v := range components[i] {
fmt.Printf("%d ", v)
}
fmt.Println()
}
// Example usage of StronglyConnected and GetID
fmt.Println("\nConnectivity checks:")
connected03, _ := scc.StronglyConnected(0, 3)
fmt.Printf("Vertices 0 and 3 strongly connected? %v\n", connected03)
connected07, _ := scc.StronglyConnected(0, 7)
fmt.Printf("Vertices 0 and 7 strongly connected? %v\n", connected07)
connected912, _ := scc.StronglyConnected(9, 12)
fmt.Printf("Vertices 9 and 12 strongly connected? %v\n", connected912)
id5, _ := scc.GetID(5)
fmt.Printf("ID of vertex 5: %d\n", id5)
id8, _ := scc.GetID(8)
fmt.Printf("ID of vertex 8: %d\n", id8)
}
- Output:
Constructed Digraph: 13 vertices, 22 edges 0: 1 5 6 1: 2: 3 0 3: 2 5 4: 2 5: 4 3 6: 0 4 9 7: 6 8 8: 9 7 9: 10 11 10: 12 11: 12 12: 9 4 strongly connected components Components: Component 0: 1 Component 1: 9 10 11 12 Component 2: 0 2 3 4 5 6 Component 3: 7 8 Connectivity checks: Vertices 0 and 3 strongly connected? true Vertices 0 and 7 strongly connected? false Vertices 9 and 12 strongly connected? true ID of vertex 5: 2 ID of vertex 8: 3
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public final class GabowsAlgorithm {
public static void main(String[] args) {
record Edge(int from, int to) {}
List<Edge> edges = List.of( new Edge(4, 2), new Edge(2, 3), new Edge(3, 2), new Edge(6, 0), new Edge(0, 1),
new Edge(2, 0), new Edge(11, 12), new Edge(12, 9), new Edge(9, 10), new Edge(9, 11), new Edge(8, 9),
new Edge(10, 12), new Edge(0, 5), new Edge(5, 4), new Edge(3, 5), new Edge(6, 4), new Edge(6, 9),
new Edge(7, 6), new Edge(7, 8), new Edge(8, 7), new Edge(5, 3), new Edge(0, 6) );
Digraph digraph = new Digraph(13);
edges.forEach( edge -> digraph.addEdge(edge.from, edge.to) );
System.out.println("Constructed digraph:");
System.out.println(digraph);
GabowSCC gabowSCC = new GabowSCC(digraph);
System.out.println("It has " + gabowSCC.stronglyConnectedComponentCount() + " strongly connected components.");
List<List<Integer>> components = gabowSCC.components();
System.out.println(System.lineSeparator() + "Components:");
IntStream.range(0, components.size()).forEach( i -> {
System.out.println("Component " + i + ": " +
components.get(i).stream().map(String::valueOf).collect(Collectors.joining(" ")));
} );
// Example usage of the isStronglyConnected() and componentID() methods
System.out.println(System.lineSeparator() + "Example connectivity checks:");
System.out.println("Vertices 0 and 3 strongly connected? " + gabowSCC.isStronglyConnected(0, 3));
System.out.println("Vertices 0 and 7 strongly connected? " + gabowSCC.isStronglyConnected(0, 7));
System.out.println("Vertices 9 and 12 strongly connected? " + gabowSCC.isStronglyConnected(9, 12));
System.out.println("Component ID of vertex 5: " + gabowSCC.componentID(5));
System.out.println("Component ID of vertex 8: " + gabowSCC.componentID(8));
}
}
/**
* Determination of the strongly connected components (SCC's) of a directed graph using Gabow's algorithm.
*/
final class GabowSCC {
public GabowSCC(Digraph digraph) {
visited = Stream.generate( () -> false ).limit(digraph.vertexCount()).collect(Collectors.toList());
componentIDs = IntStream.range(0, digraph.vertexCount()).boxed().map( i -> NONE ).collect(Collectors.toList());
preorders = IntStream.range(0, digraph.vertexCount()).boxed().map( i -> NONE ).collect(Collectors.toList());
preorderCount = 0;
sccCount = 0;
visitedVerticesStack = new Stack<Integer>();
auxiliaryStack = new Stack<Integer>();
IntStream.range(0, digraph.vertexCount()).forEach( vertex -> {
if ( ! visited.get(vertex) ) {
depthFirstSearch(digraph, vertex);
}
} );
}
// Return, for each vertex, a list of its strongly connected vertices
public List<List<Integer>> components() {
List<List<Integer>> components = IntStream.range(0, sccCount).boxed()
.map( i -> new ArrayList<Integer>() ).collect(Collectors.toList());
for ( int vertex = 0; vertex < visited.size(); vertex++ ) {
final int componentID = componentID(vertex);
if ( componentID != NONE ) { // This would normally be true
components.get(componentID).addLast(vertex);
} else {
// Could be caused by the digraph edges being changed by the user
throw new AssertionError("Warning: Vertex " + vertex + " has no SCC ID assigned.");
}
}
return components;
}
// Return whether or not vertices 'v' and 'w' are in the same strongly connected component.
public boolean isStronglyConnected(int v, int w) {
validateVertex(v);
validateVertex(w);
// If either vertex was not visited, for example, due to it being in an unconnected graph component,
// its id will be 'NONE', and they cannot be strongly connected unless
// the graph is empty or has isolated vertices which is handled by the return condition below.
return componentIDs.get(v) != NONE && componentIDs.get(v) == componentIDs.get(w);
}
// Return the component ID of the strong component containing 'vertex'.
public int componentID(int vertex) {
validateVertex(vertex);
return componentIDs.get(vertex);
}
public int stronglyConnectedComponentCount() {
return sccCount;
}
private void depthFirstSearch(Digraph digraph, int vertex) {
visited.set(vertex, true);
preorders.set(vertex, preorderCount);
preorderCount += 1;
visitedVerticesStack.push(vertex);
auxiliaryStack.push(vertex);
digraph.adjacencyList(vertex).forEach( w -> {
if ( ! visited.get(w) ) {
depthFirstSearch(digraph, w);
// If 'w' is visited, but not yet assigned to a SCC,
// then 'w' is on the current depth first path,
// or in a SCC which has already been processed in this depth first path,
// and this will be handled by the 'auxiliaryStack'.
} else if ( componentIDs.get(w) == NONE ) {
// Pop vertices from the 'auxiliaryStack' until the top vertex has a preorder <= preorder of 'w'.
// This maintains the invariant that 'auxiliaryStack' contains a path of potential SCC roots.
while ( ! auxiliaryStack.isEmpty() && preorders.get(auxiliaryStack.peek()) > preorders.get(w) ) {
auxiliaryStack.pop();
}
}
} );
// 'vertex' is the root of a SCC,
// if it remains on top of the 'auxiliaryStack' after exploring all of its descendants and back-edges.
if ( ! auxiliaryStack.isEmpty() && auxiliaryStack.peek() == vertex ) {
auxiliaryStack.pop();
// Pop vertices from the 'auxiliartStack' until 'vertex' is popped,
// and assign these vertices the current strongly connected component id.
while ( ! visitedVerticesStack.isEmpty() ) {
final int w = visitedVerticesStack.pop();
componentIDs.set(w, sccCount);
if ( w == vertex ) {
break;
}
}
sccCount += 1;
}
}
private void validateVertex(int vertex) {
final int visitedCount = visited.size();
if ( vertex < 0 || vertex >= visitedCount ) {
throw new AssertionError("Vertex " + vertex + " is not between 0 and " + ( visitedCount - 1 ));
}
}
private List<Boolean> visited; // stores the vertices that have been visited
private List<Integer> componentIDs; // the unique id number of each strongly connected component
private List<Integer> preorders; // stores the preorder of vertices
private int preorderCount; // the number of preorders of vertices
private int sccCount; // the number of strongly connected components
private Stack<Integer> visitedVerticesStack; // stores vertices in the order of their visit
private Stack<Integer> auxiliaryStack; // auxiliary stack for finding SCC roots
private static final int NONE = -1;
}
/**
* Representation of a directed graph, or digraph, using adjacency lists.
* Vertices are identified by integers starting from zero.
*/
final class Digraph {
public Digraph(int aVertexCount) {
if ( aVertexCount < 0 ) {
throw new AssertionError("Number of vertices must be non-negative");
}
vertexCount = aVertexCount;
edgeCount = 0;
adjacencyLists = IntStream.range(0, vertexCount).boxed()
.map( i -> new ArrayList<Integer>() ).collect(Collectors.toList());
}
public void addEdge(int from, int to) {
validateVertex(from);
validateVertex(to);
adjacencyLists.get(from).addLast(to);
edgeCount += 1;
}
public String toString() {
String result = "Digraph has " + vertexCount + " vertices and " + edgeCount + " edges"
+ System.lineSeparator() + "Adjacency lists:" + System.lineSeparator();
for ( int vertex = 0; vertex < vertexCount; vertex++ ) {
result += ( vertex < 10 ? " " : "" ) + vertex + ": "
+ adjacencyLists.get(vertex).stream().map(String::valueOf).sorted().collect(Collectors.joining(" "))
+ System.lineSeparator();
}
return result;
}
public int vertexCount() {
return vertexCount;
}
public int edgeCount() {
return edgeCount;
}
public List<Integer> adjacencyList(int vertex) {
validateVertex(vertex);
return adjacencyLists.get(vertex);
}
private void validateVertex(int vertex) {
if ( vertex < 0 || vertex >= vertexCount ) {
throw new AssertionError("Vertex must be between 0 " + vertexCount + ": " + vertex);
}
}
private int vertexCount;
private int edgeCount;
private List<List<Integer>> adjacencyLists;
}
- Output:
Constructed digraph: Digraph has 13 vertices and 22 edges Adjacency lists: 0: 1 5 6 1: 2: 0 3 3: 2 5 4: 2 5: 3 4 6: 0 4 9 7: 6 8 8: 7 9 9: 10 11 10: 12 11: 12 12: 9 It has 4 strongly connected components. Components: Component 0: 1 Component 1: 9 10 11 12 Component 2: 0 2 3 4 5 6 Component 3: 7 8 Example connectivity checks: Vertices 0 and 3 strongly connected? true Vertices 0 and 7 strongly connected? false Vertices 9 and 12 strongly connected? true Component ID of vertex 5: 2 Component ID of vertex 8: 3
JavaScript
/**
* Basic Directed Graph class using adjacency lists.
* Vertices are assumed to be integers from 0 to V-1.
*/
class Digraph {
#V; // Number of vertices (private)
#E; // Number of edges (private)
#adj; // Adjacency lists (private)
/**
* Initializes an empty digraph with V vertices.
* @param {number} V - The number of vertices.
*/
constructor(V) {
if (V < 0) {
throw new Error("Number of vertices must be non-negative");
}
this.#V = V;
this.#E = 0;
// Use an array of arrays for adjacency lists
this.#adj = Array.from({ length: V }, () => []);
}
/**
* Returns the number of vertices.
* @returns {number}
*/
get V() {
return this.#V;
}
/**
* Returns the number of edges.
* @returns {number}
*/
get E() {
return this.#E;
}
/**
* Throws Error if v is not a valid vertex.
* @param {number} v - The vertex to validate.
* @private
*/
#validateVertex(v) {
if (v < 0 || v >= this.#V) {
throw new Error(`vertex ${v} is not between 0 and ${this.#V - 1}`);
}
}
/**
* Adds the directed edge v->w to the digraph.
* @param {number} v - The source vertex.
* @param {number} w - The target vertex.
*/
addEdge(v, w) {
this.#validateVertex(v);
this.#validateVertex(w);
this.#adj[v].push(w);
this.#E++;
}
/**
* Returns the list of neighbors adjacent from vertex v.
* @param {number} v - The vertex.
* @returns {number[]} - An array of adjacent vertices.
*/
adj(v) {
this.#validateVertex(v);
return this.#adj[v]; // Return a copy if mutation is a concern: [...this.#adj[v]]
}
/**
* String representation of the digraph.
* @returns {string}
*/
toString() {
let s = `${this.#V} vertices, ${this.#E} edges\n`;
for (let v = 0; v < this.#V; v++) {
s += `${v}: ${this.#adj[v].join(' ')}\n`;
}
return s;
}
}
/**
* Computes strongly connected components (SCCs) in a digraph
* using Gabow's algorithm.
*/
class GabowSCC {
#marked; // marked[v] = has v been visited? (boolean array)
#id; // id[v] = id of strong component containing v (number array)
#preorder; // preorder[v] = preorder of v (number array)
#preCounter; // preorder number counter (number)
#sccCount; // number of strongly-connected components (number)
#stack1; // Stores vertices in order of visitation (number array)
#stack2; // Auxiliary stack for finding SCC roots (number array)
#graphV; // Store graph's vertex count for validation
/**
* Computes the strong components of the digraph G.
* @param {Digraph} G - The Digraph object.
*/
constructor(G) {
const V = G.V;
this.#graphV = V;
this.#marked = Array(V).fill(false);
this.#id = Array(V).fill(-1);
this.#preorder = Array(V).fill(-1);
this.#preCounter = 0;
this.#sccCount = 0;
this.#stack1 = [];
this.#stack2 = [];
for (let v = 0; v < V; v++) {
if (!this.#marked[v]) {
this.#dfs(G, v);
}
}
// Optional: Add a check function if needed (would require a TransitiveClosure implementation)
// assert this.#check(G);
}
/**
* Depth First Search core logic for Gabow's algorithm.
* @param {Digraph} G - The graph.
* @param {number} v - The current vertex.
* @private
*/
#dfs(G, v) {
this.#marked[v] = true;
this.#preorder[v] = this.#preCounter++;
this.#stack1.push(v);
this.#stack2.push(v);
for (const w of G.adj(v)) {
if (!this.#marked[w]) {
this.#dfs(G, w);
}
// If w is visited but not yet assigned to an SCC,
// it means w is on the current DFS path (or in an SCC already processed
// in this DFS branch, but stack2 handles this).
else if (this.#id[w] === -1) {
// Pop vertices from stack2 until top has preorder number <= preorder[w]
// This maintains the invariant that stack2 contains a path of potential SCC roots
while (this.#stack2.length > 0 && this.#preorder[this.#stack2[this.#stack2.length - 1]] > this.#preorder[w]) {
this.#stack2.pop();
}
}
}
// If v is the root of an SCC (i.e., it remains on top of stack2 after
// exploring all its descendants and back-edges)
if (this.#stack2.length > 0 && this.#stack2[this.#stack2.length - 1] === v) {
this.#stack2.pop();
// Pop vertices from stack1 until v is popped; assign them the current SCC id
let w;
do {
w = this.#stack1.pop();
if (w === undefined) { // Should not happen in correct execution
throw new Error("Error in Gabow's Algorithm: Stack1 became unexpectedly empty.");
}
this.#id[w] = this.#sccCount;
} while (w !== v);
this.#sccCount++;
}
}
/**
* Returns the number of strong components.
* @returns {number}
*/
count() {
return this.#sccCount;
}
/**
* Throws Error if v is not a valid vertex for the original graph.
* @param {number} v - The vertex to validate.
* @private
*/
#validateVertex(v) {
if (v < 0 || v >= this.#graphV) {
throw new Error(`vertex ${v} is not between 0 and ${this.#graphV - 1}`);
}
}
/**
* Are vertices v and w in the same strong component?
* @param {number} v - one vertex
* @param {number} w - the other vertex
* @returns {boolean} - True if v and w are in the same strong component, False otherwise
*/
stronglyConnected(v, w) {
this.#validateVertex(v);
this.#validateVertex(w);
// If either vertex wasn't visited (e.g., in a disconnected graph part),
// its id will be -1, and they cannot be strongly connected unless
// the graph is empty or has isolated vertices (handled by id comparison).
return this.#id[v] !== -1 && this.#id[v] === this.#id[w];
}
/**
* Returns the component id of the strong component containing vertex v.
* @param {number} v - the vertex
* @returns {number} - The component id (an integer >= 0) or -1 if vertex is invalid/not reached.
*/
getId(v) {
this.#validateVertex(v);
return this.#id[v];
}
// The _check method from Java requires a TransitiveClosure implementation.
// For simplicity, it's omitted here, but could be added if needed.
// #check(G) { ... }
}
// --- Main execution block ---
// --- Manually construct the digraph ---
// Example graph (based on Sedgewick/Wayne algs4 tinyDG.txt)
// 13 vertices, 22 edges
// Edges: 4->2, 2->3, 3->2, 6->0, 0->1, 2->0, 11->12, 12->9, 9->10,
// 9->11, 8->9, 10->12, 0->5, 5->4, 3->5, 6->4, 6->9, 7->6,
// 7->8, 8->7, 5->3, 0->6 (Added 0->6 to connect 0-1 and 0-5-4-2-3 cycles more directly)
const numVertices = 13;
const g = new Digraph(numVertices);
const edges = [
[4, 2], [2, 3], [3, 2], [6, 0], [0, 1], [2, 0], [11, 12],
[12, 9], [9, 10], [9, 11], [8, 9], [10, 12], [0, 5], [5, 4],
[3, 5], [6, 4], [6, 9], [7, 6], [7, 8], [8, 7], [5, 3], [0, 6]
];
for (const [v, w] of edges) {
g.addEdge(v, w);
}
console.log("Constructed Digraph:");
console.log(g.toString());
// --- Compute SCCs ---
const scc = new GabowSCC(g);
// --- Print results ---
const m = scc.count();
console.log(`\n${m} strongly connected components`);
// Group vertices by component ID
const components = Array.from({ length: m }, () => []);
for (let v = 0; v < g.V; v++) {
const componentId = scc.getId(v);
if (componentId !== -1) { // Should always be >= 0 after running constructor
components[componentId].push(v);
} else {
// This case should ideally not happen if all vertices are reachable
// or handled correctly in the init loop. Could represent isolated vertices
// or issues if the graph was modified after SCC computation.
console.warn(`Warning: Vertex ${v} has no SCC ID assigned.`);
}
}
console.log("\nComponents:");
for (let i = 0; i < m; i++) {
console.log(`Component ${i}: ${components[i].join(' ')}`);
}
// --- Example usage of stronglyConnected and getId ---
console.log("\nConnectivity checks:");
console.log(`Vertices 0 and 3 strongly connected? ${scc.stronglyConnected(0, 3)}`); // Should be True
console.log(`Vertices 0 and 7 strongly connected? ${scc.stronglyConnected(0, 7)}`); // Should be False
console.log(`Vertices 9 and 12 strongly connected? ${scc.stronglyConnected(9, 12)}`); // Should be True
console.log(`ID of vertex 5: ${scc.getId(5)}`);
console.log(`ID of vertex 8: ${scc.getId(8)}`);
- Output:
Constructed Digraph: 13 vertices, 22 edges 0: 1 5 6 1: 2: 3 0 3: 2 5 4: 2 5: 4 3 6: 0 4 9 7: 6 8 8: 9 7 9: 10 11 10: 12 11: 12 12: 9 4 strongly connected components Components: Component 0: 1 Component 1: 9 10 11 12 Component 2: 0 2 3 4 5 6 Component 3: 7 8 Connectivity checks: Vertices 0 and 3 strongly connected? true Vertices 0 and 7 strongly connected? false Vertices 9 and 12 strongly connected? true ID of vertex 5: 2 ID of vertex 8: 3
Julia
import Base.string, Base.count
""" Digraph represents a directed graph using adjacency lists
Note that Julia uses 1 based indexing so numbers from 1 not 0
Test output converts back to 0 based for comparable output
"""
mutable struct Digraph
v::Int # number of vertices
e::Int # number of edges
adj::Vector{Vector{Int}} # adjacency lists
end
""" makes an empty digraph with v vertices """
function Digraph(v::Integer)
@assert v >= 0 "number of vertices must be non-negative"
return Digraph(v, 0, [Int[] for _ in 1:v])
end
""" nv returns the number of vertices """
nv(g::Digraph) = g.v
""" ne returns the number of edges """
ne(g::Digraph) = g.e
""" validatevertex raises an error if v is not a valid vertex """
function validatevertex(g::Digraph, v::Integer)
@assert 0 < v <= g.v "Domain error with v $v: required that 0 < v <= $(g.v)"
end
""" addedge! adds the directed edge v->w to the digraph """
function addedge!(g::Digraph, v, w)
validatevertex(g, v)
validatevertex(g, w)
push!(g.adj[v], w)
g.e += 1
end
""" Adj returns the list of neighbors adjacent from vertex v """
function adj(g::Digraph, v::Integer)
validatevertex(g, v)
return g.adj[v]
end
""" returns a string representation of the digraph """
function string(g::Digraph, zerobasedoutput = true)
s = "$(nv(g)) vertices, $(ne(g)) edges\n"
for v in eachindex(g.adj)
s *= "$v: " * join([string(i - zerobasedoutput) for i in g.adj[v]], " ") * "\n"
end
return s
end
""" strongly connected components in a digraph using Gabow's algorithm """
mutable struct GabowSCC
marked::Vector{Bool} # marked[v] = has v been visited?
id::Vector{Int} # id[v] = id of strong component containing v
preorder::Vector{Int} # preorder[v] = preorder of v
precounter::Int # preorder number counter
scc_count::Int # number of strongly-connected components
stack1::Vector{Int} # Stores vertices in order of visitation
stack2::Vector{Int} # Auxiliary stack for finding SCC roots
end
""" Computes the strong components of the digraph G as a GabowSCC """
function GabowSCC(g::Digraph)
marked = falses(nv(g))
id = fill(-1, nv(g)) # Initialize id array with -1
preorder = zeros(Int, nv(g))
scc = GabowSCC(marked, id, preorder, 0, 1, Int[], Int[])
for v in 1:nv(g)
!scc.marked[v] && dfs!(scc, g, v)
end
return scc
end
""" dfs! implements depth-first search core logic for Gabow's algorithm """
function dfs!(scc::GabowSCC, g::Digraph, v::Integer)
scc.marked[v] = true
scc.precounter += 1
scc.preorder[v] = scc.precounter
push!(scc.stack1, v)
push!(scc.stack2, v)
for w in g.adj[v]
if !scc.marked[w]
dfs!(scc, g, w)
elseif scc.id[w] == -1
# Pop vertices from stack2 until top has preorder number <= preorder[w]
while !isempty(scc.stack2) && scc.preorder[scc.stack2[end]] > scc.preorder[w]
pop!(scc.stack2)
end
end
end
# If v at end of stack2 is the root of an SCC
if !isempty(scc.stack2) && scc.stack2[end] == v
pop!(scc.stack2) # remove v from stack2
# Pop vertices from stack1 until v is found; assign them the current SCC id
while !isempty(scc.stack1)
w = pop!(scc.stack1)
scc.id[w] = scc.scc_count
w == v && break
end
scc.scc_count += 1
end
end
""" returns the number of strong components """
count(scc::GabowSCC) = scc.scc_count - 1
""" raises an error if v is not a valid vertex """
function validatevertex(scc::GabowSCC, v::Integer)
len = length(scc.marked)
@assert 0 < v <= len "vertex $v is not between 0 and $len"
end
""" returns true if vertices v and w are in the same strong component """
function stronglyconnected(scc::GabowSCC, v::Integer, w::Integer)
validatevertex(scc, v)
validatevertex(scc, w)
return scc.id[v] != -1 && scc.id[v] == scc.id[w]
end
""" returns the component id of the strong component containing vertex v """
id(scc::GabowSCC, v::Integer) = (validatevertex(scc, v); scc.id[v])
function testgabow()
# Manually construct the digraph (same as in Python code)
numVertices = 13
g = Digraph(numVertices)
edges = [
[4, 2], [2, 3], [3, 2], [6, 0], [0, 1], [2, 0], [11, 12],
[12, 9], [9, 10], [9, 11], [8, 9], [10, 12], [0, 5], [5, 4],
[3, 5], [6, 4], [6, 9], [7, 6], [7, 8], [8, 7], [5, 3], [0, 6],
]
for (v, w) in edges
addedge!(g, v + 1, w + 1)
end
println("Constructed Digraph:\n$(string(g))")
# Compute SCCs
scc = GabowSCC(g)
# Print results
m = count(scc)
println("$m strongly connected components:")
# Group vertices by component ID
components = [Int[] for _ in 1:m]
for v in 1:nv(g)
componentID = id(scc, v)
if componentID != -1
push!(components[componentID], v)
else
println("Warning: Vertex $v has no SCC ID assigned.\n")
end
end
for i in 1:m
println("Component $(i-1): ", join([string(components[i][j] - 1) for j in eachindex(components[i])], " "))
end
# Example usage of stronglyconnected and id
println("\nConnectivity checks:")
for (v, w) in [(0, 3), (0, 7), (9, 12)]
println("Vertices $v and $w strongly connected? ",
stronglyconnected(scc, v + 1, w + 1))
end
println("ID of vertex 5: ", id(scc, 5 + 1) - 1)
println("ID of vertex 8: ", id(scc, 8 + 1) - 1)
end
testgabow()
- Output:
Constructed Digraph: 13 vertices, 22 edges 1: 1 5 6 2: 3: 3 0 4: 2 5 5: 2 6: 4 3 7: 0 4 9 8: 6 8 9: 9 7 10: 10 11 11: 12 12: 12 13: 9 4 strongly connected components: Component 0: 1 Component 1: 9 10 11 12 Component 2: 0 2 3 4 5 6 Component 3: 7 8 Connectivity checks: Vertices 0 and 3 strongly connected? true Vertices 0 and 7 strongly connected? false Vertices 9 and 12 strongly connected? true ID of vertex 5: 2 ID of vertex 8: 3
Phix
// Digraph represents a directed graph using adjacency lists
integer n_v, // number of vertices
n_e // number of edges
sequence adj // adjacency lists
type vertex(integer v)
return v>=1 and v<=n_v
end type
// GabowSCC computes strongly connected components (SCCs) in a digraph using Gabow's algorithm
sequence marked, // marked[v] = has v been visited?
id, // id[v] = id of strong component containing v
preorder, // preorder[v] = preorder of v
stack1, // Stores vertices in order of visitation
stack2 // Auxiliary stack for finding SCC roots
integer preCounter, // preorder number counter
sccCount // number of strongly-connected components
// dfs implements depth-first search core logic for Gabow's algorithm
procedure dfs(integer v)
marked[v] = true
preorder[v] = preCounter
preCounter += 1
stack1 = append(stack1, v)
stack2 = append(stack2, v)
for w in adj[v] do
if not marked[w] then
dfs(w)
elsif id[w] == -1 then
// Pop vertices from stack2 until top has preorder number <= preorder[w]
while length(stack2) > 0 and preorder[stack2[$]] > preorder[w] do
stack2 = stack2[1..$-1] // Pop
end while
end if
end for
// If v is the root of an SCC
if length(stack2) > 0 and stack2[$] == v then
// Pop v from stack2
stack2 = stack2[1..$-1]
sccCount += 1
// Pop vertices from stack1 until v is popped; assign them the current SCC id
while length(stack1) do
integer w := stack1[$]
stack1 = stack1[1..$-1] // Pop
id[w] = sccCount
if w == v then exit end if
end while
end if
end procedure
// StronglyConnected returns true if vertices v and w are in the same strong component
function StronglyConnected(vertex v, w)
return id[v] != -1 and id[v] == id[w]
end function
// Manually construct the digraph (same as in Python code)
n_v = 13 // numVertices
n_e = 0 // no edges yet
adj = repeat({},n_v)
sequence edges := {{5,3},{3,4},{4,3},{7,1},{1,2},{3,1},{12,13},{13,10},{10,11},{10,12},
{9,10},{11,13},{1,6},{6,5},{4,6},{7,5},{7,10},{8,7},{8,9},{9,8},{6,4},{1,7}}
for edge in edges do
integer {v, w} := edge
adj[v] = append(adj[v], w)
n_e += 1
end for
printf(1,"Constructed Digraph:\n")
printf(1,"%d vertices, %d edges\n", {n_v, n_e})
for v=1 to n_v do
printf(1,"%d: %v\n",{v,adj[v]})
end for
// Compute SCCs
marked := repeat(false,n_v)
id := repeat(-1, n_v)
preorder := repeat(0, n_v)
preCounter := 1
sccCount := 0
stack1 := {}
stack2 := {}
for v=1 to n_v do
if not marked[v] then
dfs(v)
end if
end for
// Print results
printf(1,"\n%d strongly connected components\n", sccCount)
// Group vertices by component ID
sequence components := repeat({},sccCount)
for v=1 to n_v do
integer componentID := id[v]
if componentID != -1 then
components[componentID] = append(components[componentID], v)
else
printf(1,"Warning: Vertex %d has no SCC ID assigned.\n", v)
end if
end for
printf(1,"\nComponents:\n")
for i=1 to sccCount do
printf(1,"Component %d: %v\n", {i,components[i]})
end for
// Example usage of StronglyConnected and GetID
printf(1,"\nConnectivity checks:\n")
printf(1,"Vertices 1 and 4 strongly connected? %t\n", StronglyConnected(1,4))
printf(1,"Vertices 1 and 8 strongly connected? %t\n", StronglyConnected(1,8))
printf(1,"Vertices 10 and 13 strongly connected? %t\n", StronglyConnected(10,13))
printf(1,"ID of vertex 6: %d\n", id[6])
printf(1,"ID of vertex 9: %d\n", id[9])
- Output:
(using 1-based indices and ids)
Constructed Digraph:
13 vertices, 22 edges
1: {2,6,7}
2: {}
3: {4,1}
4: {3,6}
5: {3}
6: {5,4}
7: {1,5,10}
8: {7,9}
9: {10,8}
10: {11,12}
11: {13}
12: {13}
13: {10}
4 strongly connected components
Components:
Component 1: {2}
Component 2: {10,11,12,13}
Component 3: {1,3,4,5,6,7}
Component 4: {8,9}
Connectivity checks:
Vertices 1 and 4 strongly connected? true
Vertices 1 and 8 strongly connected? false
Vertices 10 and 13 strongly connected? true
ID of vertex 6: 3
ID of vertex 9: 4
Python
import sys
# Increase recursion depth limit for potentially deep DFS
# Be cautious with this in production, but useful for deep graphs
try:
sys.setrecursionlimit(2000)
except Exception as e:
print(f"Warning: Could not set recursion depth limit: {e}")
class Digraph:
"""
Basic Directed Graph class using adjacency lists.
Vertices are assumed to be integers from 0 to V-1.
"""
def __init__(self, V):
"""Initializes an empty digraph with V vertices."""
if V < 0:
raise ValueError("Number of vertices must be non-negative")
self._V = V
self._E = 0
# Use a list of lists for adjacency lists
self._adj = [[] for _ in range(V)]
def V(self):
"""Returns the number of vertices."""
return self._V
def E(self):
"""Returns the number of edges."""
return self._E
def _validate_vertex(self, v):
"""Raises ValueError if v is not a valid vertex."""
if not (0 <= v < self._V):
raise ValueError(f"vertex {v} is not between 0 and {self._V-1}")
def add_edge(self, v, w):
"""Adds the directed edge v->w to the digraph."""
self._validate_vertex(v)
self._validate_vertex(w)
self._adj[v].append(w)
self._E += 1
def adj(self, v):
"""Returns the list of neighbors adjacent from vertex v."""
self._validate_vertex(v)
return self._adj[v]
def __str__(self):
"""String representation of the digraph."""
s = f"{self._V} vertices, {self._E} edges\n"
for v in range(self._V):
s += f"{v}: {' '.join(map(str, self._adj[v]))}\n"
return s
class GabowSCC:
"""
Computes strongly connected components (SCCs) in a digraph
using Gabow's algorithm.
"""
def __init__(self, G):
"""
Computes the strong components of the digraph G.
:param G: The Digraph object
"""
self._marked = [False] * G.V() # marked[v] = has v been visited?
self._id = [-1] * G.V() # id[v] = id of strong component containing v
self._preorder = [-1] * G.V() # preorder[v] = preorder of v
self._pre_counter = 0 # preorder number counter
self._scc_count = 0 # number of strongly-connected components
self._stack1 = [] # Stores vertices in order of visitation
self._stack2 = [] # Auxiliary stack for finding SCC roots
for v in range(G.V()):
if not self._marked[v]:
self._dfs(G, v)
# Optional: Add a check function if needed (requires TransitiveClosure)
# assert self._check(G)
def _dfs(self, G, v):
"""Depth First Search core logic for Gabow's algorithm."""
self._marked[v] = True
self._preorder[v] = self._pre_counter
self._pre_counter += 1
self._stack1.append(v)
self._stack2.append(v)
for w in G.adj(v):
if not self._marked[w]:
self._dfs(G, w)
# If w is visited but not yet assigned to an SCC,
# it means w is on the current DFS path (or in an SCC already processed
# in this DFS branch, but stack2 handles this).
elif self._id[w] == -1:
# Pop vertices from stack2 until top has preorder number <= preorder[w]
# This maintains the invariant that stack2 contains a path of potential SCC roots
while self._stack2 and self._preorder[self._stack2[-1]] > self._preorder[w]:
self._stack2.pop()
# If v is the root of an SCC (i.e., it remains on top of stack2 after
# exploring all its descendants and back-edges)
if self._stack2 and self._stack2[-1] == v:
self._stack2.pop()
# Pop vertices from stack1 until v is popped; assign them the current SCC id
while True:
w = self._stack1.pop()
self._id[w] = self._scc_count
if w == v:
break
self._scc_count += 1
def count(self):
"""Returns the number of strong components."""
return self._scc_count
def _validate_vertex(self, v):
"""Raises ValueError if v is not a valid vertex."""
V = len(self._marked)
if not (0 <= v < V):
raise ValueError(f"vertex {v} is not between 0 and {V-1}")
def strongly_connected(self, v, w):
"""
Are vertices v and w in the same strong component?
:param v: one vertex
:param w: the other vertex
:return: True if v and w are in the same strong component, False otherwise
"""
self._validate_vertex(v)
self._validate_vertex(w)
# If either vertex wasn't visited (e.g., in a disconnected graph part),
# its id will be -1, and they cannot be strongly connected unless
# the graph is empty or has isolated vertices (handled by id comparison).
return self._id[v] != -1 and self._id[v] == self._id[w]
def get_id(self, v):
"""
Returns the component id of the strong component containing vertex v.
:param v: the vertex
:return: The component id (an integer >= 0) or -1 if vertex is invalid/not reached.
"""
self._validate_vertex(v)
return self._id[v]
# The _check method from Java requires a TransitiveClosure implementation.
# For simplicity, it's omitted here, but could be added if needed.
# def _check(self, G): ...
# --- Main execution block ---
if __name__ == "__main__":
# --- Manually construct the digraph ---
# Example graph (based on Sedgewick/Wayne algs4 tinyDG.txt)
# 13 vertices, 22 edges
# Edges: 4->2, 2->3, 3->2, 6->0, 0->1, 2->0, 11->12, 12->9, 9->10,
# 9->11, 8->9, 10->12, 0->5, 5->4, 3->5, 6->4, 6->9, 7->6,
# 7->8, 8->7, 5->3, 0->6 (Added 0->6 to connect 0-1 and 0-5-4-2-3 cycles more directly)
num_vertices = 13
g = Digraph(num_vertices)
edges = [
(4, 2), (2, 3), (3, 2), (6, 0), (0, 1), (2, 0), (11, 12),
(12, 9), (9, 10), (9, 11), (8, 9), (10, 12), (0, 5), (5, 4),
(3, 5), (6, 4), (6, 9), (7, 6), (7, 8), (8, 7), (5, 3), (0, 6)
]
for v, w in edges:
g.add_edge(v, w)
print("Constructed Digraph:")
print(g)
# --- Compute SCCs ---
scc = GabowSCC(g)
# --- Print results ---
m = scc.count()
print(f"{m} strongly connected components")
# Group vertices by component ID
components = [[] for _ in range(m)]
for v in range(g.V()):
component_id = scc.get_id(v)
if component_id != -1: # Should always be >= 0 after running constructor
components[component_id].append(v)
else:
# This case should ideally not happen if all vertices are reachable
# or handled correctly in the init loop. Could represent isolated vertices
# or issues if the graph was modified after SCC computation.
print(f"Warning: Vertex {v} has no SCC ID assigned.")
print("\nComponents:")
for i in range(m):
print(f"Component {i}: {' '.join(map(str, components[i]))}")
# --- Example usage of strongly_connected and get_id ---
print("\nConnectivity checks:")
print(f"Vertices 0 and 3 strongly connected? {scc.strongly_connected(0, 3)}") # Should be True in the example
print(f"Vertices 0 and 7 strongly connected? {scc.strongly_connected(0, 7)}") # Should be False
print(f"Vertices 9 and 12 strongly connected? {scc.strongly_connected(9, 12)}") # Should be True
print(f"ID of vertex 5: {scc.get_id(5)}")
print(f"ID of vertex 8: {scc.get_id(8)}")
- Output:
Constructed Digraph: 13 vertices, 22 edges 0: 1 5 6 1: 2: 3 0 3: 2 5 4: 2 5: 4 3 6: 0 4 9 7: 6 8 8: 9 7 9: 10 11 10: 12 11: 12 12: 9 4 strongly connected components Components: Component 0: 1 Component 1: 9 10 11 12 Component 2: 0 2 3 4 5 6 Component 3: 7 8 Connectivity checks: Vertices 0 and 3 strongly connected? True Vertices 0 and 7 strongly connected? False Vertices 9 and 12 strongly connected? True ID of vertex 5: 2 ID of vertex 8: 3
Raku
# 20250415 Raku programming solution
my subset Vertex of UInt;
my subset ComponentId of UInt;
class Digraph {
has Int $.vertex-count is readonly;
has Int $.edge-count is rw = 0;
has @.adjacency-lists;
method new(Int $vertex-count where * >= 0) { # Constructor
self.bless( vertex-count => $vertex-count,
adjacency-lists => [ [] xx $vertex-count ] )
}
method add-edge(Vertex $from, Vertex $to) { # Add a directed edge
self!validate-vertex($from);
self!validate-vertex($to);
@!adjacency-lists[$from].push($to);
$!edge-count++;
}
method adjacency-list(Vertex $vertex) { # Get adjacency list for a vertex
self!validate-vertex($vertex);
@!adjacency-lists[$vertex];
}
method !validate-vertex(Vertex $vertex) { # Validate vertex index
if $vertex >= $!vertex-count {
die "Vertex $vertex is not between 0 and {$!vertex-count - 1}";
}
}
method gist { # String representation
return [~] [
"Digraph has $!vertex-count vertices and $!edge-count edges\n",
"Adjacency lists:\n"
].append( gather for ^$!vertex-count -> $vertex {
take sprintf("%2d: ", $vertex);
take @!adjacency-lists[$vertex].sort.Str ~ "\n"
})
}
}
class GabowSCC {
has Bool @.visited;
has Int @.component-ids; # Using Int with -1 as None equivalent
has Int @.preorders; # Using Int with -1 as None equivalent
has Int $.preorder-count is rw = 0;
has Int $.scc-count is rw = 0;
has Vertex @.visited-vertices-stack;
has Vertex @.auxiliary-stack;
method new(Digraph $digraph) { # Constructor
my $n = $digraph.vertex-count;
my $self = self.bless(
visited => False xx $n,
component-ids => (-1) xx $n,
preorders => (-1) xx $n,
visited-vertices-stack => [],
auxiliary-stack => []
);
for ^$n -> $vertex {
$self!depth-first-search($digraph, $vertex) unless $self.visited[$vertex]
}
$self;
}
# Depth-first search for Gabow's algorithm
method !depth-first-search(Digraph $digraph, Vertex $vertex) {
@!visited[$vertex] = True;
@!preorders[$vertex] = $!preorder-count++;
@!visited-vertices-stack.push($vertex);
@!auxiliary-stack.push($vertex);
for $digraph.adjacency-list($vertex).List -> $adjacent {
if !@!visited[$adjacent] {
self!depth-first-search($digraph, $adjacent)
} else {
if @!component-ids[$adjacent] == -1 {
my $adjacent-preorder = @!preorders[$adjacent];
while @!auxiliary-stack && @!preorders[@!auxiliary-stack[*-1]] > $adjacent-preorder {
@!auxiliary-stack.pop;
}
}
}
}
if @!auxiliary-stack && @!auxiliary-stack[*-1] == $vertex {
@!auxiliary-stack.pop;
loop {
my $scc-member = @!visited-vertices-stack.pop // die "Visited stack empty";
@!component-ids[$scc-member] = $!scc-count;
last if $scc-member == $vertex;
}
$!scc-count++;
}
}
method get-component-id(Vertex $vertex) { # Get component ID for a vertex
self!validate-vertex($vertex);
@!component-ids[$vertex] == -1 ?? Nil !! @!component-ids[$vertex];
}
# Check if two vertices are strongly connected
method is-strongly-connected(Vertex $v, Vertex $w) {
self!validate-vertex($v);
self!validate-vertex($w);
@!component-ids[$v] != -1 && @!component-ids[$w] != -1 && @!component-ids[$v] == @!component-ids[$w];
}
method get-components() { # Get all components
my @components = [] xx $!scc-count;
for @!component-ids.kv -> $vertex, $id {
if $id != -1 {
$id < $!scc-count
?? @components[$id].push($vertex)
!! note "Warning: Vertex $vertex has invalid SCC ID $id"
}
}
@components.map: *.sort
}
method !validate-vertex(Vertex $vertex) { # Validate vertex index
given my $n = @!visited.elems {
die "Vertex $vertex is not between 0 and {$n - 1}" if $vertex >= $n
}
}
}
my @edges = [ <4 2>, <2 3>, <3 2>, <6 0>, <0 1>, <2 0>, <11 12>, <12 9>,
<9 10>, <9 11>, <8 9>, <10 12>, <0 5>, <5 4>, <3 5>, <6 4>,
<6 9>, <7 6>, <7 8>, <8 7>, <5 3>, <0 6>
].map: { ( from => .[0], to => .[1] ).Hash };
my $vertex-count = 13;
my $digraph = Digraph.new($vertex-count);
for @edges -> $edge { $digraph.add-edge($edge<from>, $edge<to>) }
print "Constructed digraph:" ~ $digraph.gist;
my $gabow-scc = GabowSCC.new($digraph);
say "It has $gabow-scc.scc-count() strongly connected components.";
my @components = $gabow-scc.get-components();
say "\nComponents:";
for @components.kv -> $i, @component {
say "Component $i: " ~ @component.Str if @component.Bool;
}
say "\nExample connectivity checks:";
for ( <0 3>, <0 7>, <9 12> ) -> ($i,$j) {
say "Vertices $i and $j strongly connected? {$gabow-scc.is-strongly-connected($i, $j)}"
}
say "Component ID of vertex 5: {$gabow-scc.get-component-id(5) // 'None'}";
say "Component ID of vertex 8: {$gabow-scc.get-component-id(8) // 'None'}";
(my $id = $gabow-scc.get-component-id(5)).defined
?? say "Component ID of vertex 5 (explicit handling): $id"
!! say "Vertex 5 has no assigned component ID.";
You may Attempt This Online!
Rust
use std::fmt;
// Use usize for indices and counts, standard in Rust.
type Vertex = usize;
type ComponentId = usize;
// --- Digraph Struct ---
#[derive(Debug, Clone)] // Added Clone for potential use cases, Debug for easy printing
pub struct Digraph {
vertex_count: usize,
edge_count: usize,
adjacency_lists: Vec<Vec<Vertex>>,
}
impl Digraph {
/// Creates a new directed graph with a given number of vertices.
/// Vertices are numbered 0 to vertex_count - 1.
pub fn new(vertex_count: usize) -> Self {
Digraph {
vertex_count,
edge_count: 0,
// Initialize adjacency lists: one empty Vec per vertex
adjacency_lists: vec![Vec::new(); vertex_count],
}
}
/// Adds a directed edge from `from` to `to`.
///
/// # Panics
/// Panics if `from` or `to` vertex indices are out of bounds.
pub fn add_edge(&mut self, from: Vertex, to: Vertex) {
self.validate_vertex(from);
self.validate_vertex(to);
self.adjacency_lists[from].push(to);
self.edge_count += 1;
}
/// Returns the number of vertices in the graph.
pub fn vertex_count(&self) -> usize {
self.vertex_count
}
/// Returns the number of edges in the graph.
pub fn edge_count(&self) -> usize {
self.edge_count
}
/// Returns a slice representing the adjacency list for a given vertex.
///
/// # Panics
/// Panics if the vertex index is out of bounds.
pub fn adjacency_list(&self, vertex: Vertex) -> &[Vertex] {
self.validate_vertex(vertex);
&self.adjacency_lists[vertex]
}
/// Validates if a vertex index is within the allowed range.
/// Panics if the vertex is invalid.
fn validate_vertex(&self, vertex: Vertex) {
if vertex >= self.vertex_count {
panic!(
"Vertex {} is not between 0 and {}",
vertex,
self.vertex_count - 1
);
}
}
}
// Implement Display trait for nice printing
impl fmt::Display for Digraph {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
writeln!(
f,
"Digraph has {} vertices and {} edges",
self.vertex_count, self.edge_count
)?;
writeln!(f, "Adjacency lists:")?;
for vertex in 0..self.vertex_count {
// Format vertex number with padding for alignment
write!(f, "{:>2}: ", vertex)?;
// Clone and sort the list for consistent output like the C++ version
let mut adj_list = self.adjacency_lists[vertex].clone();
adj_list.sort(); // Sorts in place
for &adjacent in &adj_list {
write!(f, "{} ", adjacent)?;
}
writeln!(f)?; // Newline after each vertex's list
}
Ok(())
}
}
// --- GabowSCC Struct ---
pub struct GabowScc {
visited: Vec<bool>,
// Use Option<ComponentId> instead of a sentinel value like -1/u32::MAX
component_ids: Vec<Option<ComponentId>>,
preorders: Vec<Option<usize>>, // Preorder number for each vertex
preorder_count: usize, // Counter for assigning preorder numbers
scc_count: usize, // Number of strongly connected components found
// Use Vec as stacks
visited_vertices_stack: Vec<Vertex>,
auxiliary_stack: Vec<Vertex>,
}
impl GabowScc {
/// Computes the strongly connected components of a digraph using Gabow's algorithm.
pub fn new(digraph: &Digraph) -> Self {
let n = digraph.vertex_count();
let mut scc = GabowScc {
visited: vec![false; n],
component_ids: vec![None; n],
preorders: vec![None; n],
preorder_count: 0,
scc_count: 0,
visited_vertices_stack: Vec::new(),
auxiliary_stack: Vec::new(),
};
for vertex in 0..n {
if !scc.visited[vertex] {
scc.depth_first_search(digraph, vertex);
}
}
scc
}
/// Performs the depth-first search core to Gabow's algorithm.
fn depth_first_search(&mut self, digraph: &Digraph, vertex: Vertex) {
self.visited[vertex] = true;
self.preorders[vertex] = Some(self.preorder_count);
self.preorder_count += 1;
self.visited_vertices_stack.push(vertex);
self.auxiliary_stack.push(vertex);
for &adjacent in digraph.adjacency_list(vertex) {
if !self.visited[adjacent] {
self.depth_first_search(digraph, adjacent);
} else if self.component_ids[adjacent].is_none() {
// Adjacent is visited but not yet assigned to an SCC.
// It must be on the current DFS path or in an already processed SCC
// within this DFS branch. Check the auxiliary stack.
let adjacent_preorder = self
.preorders[adjacent]
.expect("Visited vertex without component ID should have a preorder");
// Pop vertices from auxiliary_stack until top has preorder <= adjacent's preorder
while let Some(&top_vertex) = self.auxiliary_stack.last() {
let top_preorder = self.preorders[top_vertex]
.expect("Vertex on auxiliary stack should have a preorder");
if top_preorder > adjacent_preorder {
self.auxiliary_stack.pop(); // Pop it
} else {
break; // Stop popping
}
}
}
// If adjacent has a component_id, it belongs to a completed SCC, ignore.
}
// Check if 'vertex' is the root of an SCC
// It's the root if it's still on top of the auxiliary stack here.
if let Some(&top_vertex) = self.auxiliary_stack.last() {
if top_vertex == vertex {
self.auxiliary_stack.pop(); // Pop the root 'vertex' itself
// Pop vertices from visited_vertices_stack until 'vertex' is found.
// All these popped vertices form the new SCC.
loop {
let scc_member = self.visited_vertices_stack.pop()
.expect("Visited stack should not be empty when forming SCC");
self.component_ids[scc_member] = Some(self.scc_count);
if scc_member == vertex {
break; // Found the root, SCC is complete
}
}
self.scc_count += 1; // Increment the SCC counter
}
}
}
/// Returns the total number of strongly connected components found.
pub fn scc_count(&self) -> usize {
self.scc_count
}
/// Returns the component ID of the SCC containing `vertex`.
/// Returns `None` if the vertex was unreachable (should not happen in a connected graph analysis).
///
/// # Panics
/// Panics if the vertex index is out of bounds.
pub fn get_component_id(&self, vertex: Vertex) -> Option<ComponentId> {
self.validate_vertex(vertex);
self.component_ids[vertex] // This is already an Option<ComponentId>
}
/// Checks if two vertices `v` and `w` are in the same strongly connected component.
///
/// # Panics
/// Panics if `v` or `w` vertex indices are out of bounds.
pub fn is_strongly_connected(&self, v: Vertex, w: Vertex) -> bool {
self.validate_vertex(v);
self.validate_vertex(w);
// Check if both have IDs and if the IDs are the same
match (self.component_ids[v], self.component_ids[w]) {
(Some(id_v), Some(id_w)) => id_v == id_w,
_ => false, // If either vertex doesn't have a component ID, they aren't connected
}
}
/// Returns a vector where each inner vector contains the vertices belonging to one SCC.
pub fn get_components(&self) -> Vec<Vec<Vertex>> {
let mut components: Vec<Vec<Vertex>> = vec![Vec::new(); self.scc_count];
for vertex in 0..self.component_ids.len() {
if let Some(id) = self.component_ids[vertex] {
// Ensure the ID is valid before pushing (robustness)
if id < self.scc_count {
components[id].push(vertex);
} else {
// This case indicates an internal logic error
eprintln!(
"Warning: Vertex {} has an invalid SCC ID {} assigned (max should be {}).",
vertex, id, self.scc_count - 1
);
}
}
// Vertices with None component_id are ignored (e.g., unreachable)
}
// Optionally sort vertices within each component for consistent output
for component in &mut components {
component.sort();
}
components
}
/// Validates if a vertex index is within the bounds based on internal state size.
/// Panics if the vertex is invalid.
fn validate_vertex(&self, vertex: Vertex) {
let visited_count = self.visited.len(); // Use length of internal vectors
if vertex >= visited_count {
panic!(
"Vertex {} is not between 0 and {}",
vertex,
// Handle edge case of 0 vertices gracefully
if visited_count == 0 { 0 } else { visited_count - 1 }
);
}
}
}
// --- Main Function ---
// Simple struct to define edges for clarity
struct Edge {
from: Vertex,
to: Vertex,
}
fn main() {
let edges = vec![
Edge { from: 4, to: 2 }, Edge { from: 2, to: 3 }, Edge { from: 3, to: 2 },
Edge { from: 6, to: 0 }, Edge { from: 0, to: 1 }, Edge { from: 2, to: 0 },
Edge { from: 11, to: 12 }, Edge { from: 12, to: 9 }, Edge { from: 9, to: 10 },
Edge { from: 9, to: 11 }, Edge { from: 8, to: 9 }, Edge { from: 10, to: 12 },
Edge { from: 0, to: 5 }, Edge { from: 5, to: 4 }, Edge { from: 3, to: 5 },
Edge { from: 6, to: 4 }, Edge { from: 6, to: 9 }, Edge { from: 7, to: 6 },
Edge { from: 7, to: 8 }, Edge { from: 8, to: 7 }, Edge { from: 5, to: 3 },
Edge { from: 0, to: 6 },
];
let vertex_count = 13;
let mut digraph = Digraph::new(vertex_count);
for edge in &edges {
digraph.add_edge(edge.from, edge.to);
}
println!("Constructed digraph:");
println!("{}", digraph); // Uses the Display trait implementation
let gabow_scc = GabowScc::new(&digraph);
println!("It has {} strongly connected components.", gabow_scc.scc_count());
let components = gabow_scc.get_components();
println!("\nComponents:");
for (i, component) in components.iter().enumerate() {
print!("Component {}: ", i);
for &vertex in component {
print!("{} ", vertex);
}
println!();
}
// Example usage of the is_strongly_connected() and get_component_id() methods
println!("\nExample connectivity checks:");
println!("Vertices 0 and 3 strongly connected? {}", gabow_scc.is_strongly_connected(0, 3));
println!("Vertices 0 and 7 strongly connected? {}", gabow_scc.is_strongly_connected(0, 7));
println!("Vertices 9 and 12 strongly connected? {}", gabow_scc.is_strongly_connected(9, 12));
// get_component_id returns Option<usize>, use {:?} for easy printing or match/if let
println!("Component ID of vertex 5: {:?}", gabow_scc.get_component_id(5));
println!("Component ID of vertex 8: {:?}", gabow_scc.get_component_id(8));
// Example of handling the Option explicitly:
match gabow_scc.get_component_id(5) {
Some(id) => println!("Component ID of vertex 5 (explicit handling): {}", id),
None => println!("Vertex 5 has no assigned component ID."),
}
}
- Output:
Constructed digraph: Digraph has 13 vertices and 22 edges Adjacency lists: 0: 1 5 6 1: 2: 0 3 3: 2 5 4: 2 5: 3 4 6: 0 4 9 7: 6 8 8: 7 9 9: 10 11 10: 12 11: 12 12: 9 It has 4 strongly connected components. Components: Component 0: 1 Component 1: 9 10 11 12 Component 2: 0 2 3 4 5 6 Component 3: 7 8 Example connectivity checks: Vertices 0 and 3 strongly connected? true Vertices 0 and 7 strongly connected? false Vertices 9 and 12 strongly connected? true Component ID of vertex 5: Some(2) Component ID of vertex 8: Some(3) Component ID of vertex 5 (explicit handling): 2
Wren
/* Basic Directed Graph class using adjacency lists.
Vertices are assumed to be integers from 0 to _v-1. */
class Digraph {
// Creates a new digraph with v vertices.
construct new(v) {
if (v < 0) Fiber.abort("Number of vertices must be non-negative")
_v = v
_e = 0
// use a list of lists for adjacency lists
_adj = List.filled(v, null)
for (i in 0...v) _adj[i] = []
}
// Returns the number of vertices.
v { _v }
// Returns the number of edges.
e { _e }
// Private method to validate a vertex.
validateVertex_(v) {
if (v < 0 || v >= _v) Fiber.abort("Vertex %(v) is not between 0 and %(_v - 1)")
}
// Adds the directed edge v->w to the digraph.
addEdge(v, w) {
validateVertex_(v)
validateVertex_(w)
_adj[v].add(w)
_e = _e + 1
}
// Returns the list of neighbors adjacent from vertex v.
adj(v) {
validateVertex_(v)
return _adj[v]
}
// String representation of the digraph.
toString {
var s = "%(_v) vertices, %(_e) edges\n"
for (v in 0..._v) {
var sp = v < 10 ? " " : ""
s = s + "%(sp)%(v): %(_adj[v].join(" "))\n"
}
return s
}
}
/* Computes strongly connected components (SCCs) in a digraph
using Gabow's algorithm. */
class GabowSCC {
// Creates a GabowSCC to compute the strong components of the digraph 'g'.
construct new(g) {
_marked = List.filled(g.v, false) // marked[v] = has v been visited?
_id = List.filled(g.v, -1) // id[v] = id of strong component containing v
_preorder = List.filled(g.v, -1) // preorder[v] = preorder of v
_preCounter = 0 // preorder number counter
_sccCount = 0 // number of strongly connected components
_stack1 = [] // stores vertices in order of visitation
_stack2 = [] // auxiliary stack for finding SCC roots
for (v in 0...g.v) if (!_marked[v]) dfs_(g, v)
}
// Private method containing 'depth first search' core logic for Gabow's algorithm.
dfs_(g, v) {
_marked[v] = true
_preorder[v] = _preCounter
_preCounter = _preCounter + 1
_stack1.add(v)
_stack2.add(v)
for (w in g.adj(v)) {
if (!_marked[w]) {
dfs_(g, w)
// If w is visited but not yet assigned to an SCC,
// it means w is on the current DFS path (or in an SCC already processed
// in this DFS branch, but stack2 handles this).
} else if (_id[w] == -1) {
// Pop vertices from stack2 until top has preorder number <= preorder[w].
// This maintains the invariant that stack2 contains a path of potential SCC roots.
while (!_stack2.isEmpty && _preorder[_stack2[-1]] > _preorder[w]) _stack2.removeAt(-1)
}
}
// If v is the root of an SCC (i.e., it remains on top of stack2 after
// exploring all its descendants and back-edges):
if (!_stack2.isEmpty && _stack2[-1] == v) {
_stack2.removeAt(-1)
// Pop vertices from stack1 until v is popped; assign them the current SCC id.
while (!_stack1.isEmpty) {
var w = _stack1.removeAt(-1)
_id[w] = _sccCount
if (w == v) break
}
_sccCount = _sccCount + 1
}
}
// Returns the number of strong components.
count { _sccCount }
// Private method to validate a vertex.
validateVertex_(v) {
var vc = _marked.count
if (v < 0 || v >= vc) Fiber.abort("Vertex %(v) is not between 0 and %(vc - 1)")
}
// Returns whether or not vertices v and w are in the same strong component.
stronglyConnected(v, w) {
validateVertex_(v)
validateVertex_(w)
// If either vertex wasn't visited (e.g., in a disconnected graph part),
// its id will be -1, and they cannot be strongly connected unless
// the graph is empty or has isolated vertices (handled by id comparison).
return _id[v] != -1 && _id[v] == _id[w]
}
// Returns the component id of the strong component containing vertex v.
getId(v) {
validateVertex_(v)
return _id[v]
}
}
var numVertices = 13
var g = Digraph.new(numVertices)
var edges = [
[4, 2], [2, 3], [3, 2], [6, 0], [0, 1], [2, 0], [11, 12],
[12, 9], [9, 10], [9, 11], [8, 9], [10, 12], [0, 5], [5, 4],
[3, 5], [6, 4], [6, 9], [7, 6], [7, 8], [8, 7], [5, 3], [0, 6]
]
for (edge in edges) g.addEdge(edge[0], edge[1])
System.print("Constructed Digraph:")
System.print(g)
// --- Compute SCCs ---
var scc = GabowSCC.new(g)
// --- Print results ---
var m = scc.count
System.print("%(m) strongly connected components")
// Group vertices by component ID.
var components = List.filled(m, null)
for (i in 0...m) components[i] = []
for (v in 0...g.v) {
var componentId = scc.getId(v)
if (componentId != -1) { // should always be >= 0 after running constructor
components[componentId].add(v)
} else {
// This case should ideally not happen if all vertices are reachable
// or handled correctly in the constructor loop. Could represent isolated vertices
// or issues if the graph was modified after SCC computation.
System.print("Warning: Vertex %(v) has no SCC ID assigned.")
}
}
System.print("\nComponents:")
for (i in 0...m) System.print("Component %(i): %(components[i].join(" "))")
// --- Example usage of strongly_connected and get_id ---
System.print("\nConnectivity checks:")
System.print("Vertices 0 and 3 strongly connected? %(scc.stronglyConnected(0, 3))") // should be true
System.print("Vertices 0 and 7 strongly connected? %(scc.stronglyConnected(0, 7))") // should be false
System.print("Vertices 9 and 12 strongly connected? %(scc.stronglyConnected(9, 12))") // should be true
System.print("ID of vertex 5: %(scc.getId(5))")
System.print("ID of vertex 8: %(scc.getId(8))")
- Output:
Constructed Digraph: 13 vertices, 22 edges 0: 1 5 6 1: 2: 3 0 3: 2 5 4: 2 5: 4 3 6: 0 4 9 7: 6 8 8: 9 7 9: 10 11 10: 12 11: 12 12: 9 4 strongly connected components Components: Component 0: 1 Component 1: 9 10 11 12 Component 2: 0 2 3 4 5 6 Component 3: 7 8 Connectivity checks: Vertices 0 and 3 strongly connected? true Vertices 0 and 7 strongly connected? false Vertices 9 and 12 strongly connected? true ID of vertex 5: 2 ID of vertex 8: 3
Zig
const std = @import("std");
/// Representation of a directed graph, or digraph, using adjacency lists.
/// Vertices are identified by integers starting from zero.
const Digraph = struct {
vertex_count: u32,
edge_count: u32,
adjacency_lists: std.ArrayList(std.ArrayList(u32)),
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator, vertex_count: u32) !Digraph {
var adjacency_lists = std.ArrayList(std.ArrayList(u32)).init(allocator);
try adjacency_lists.ensureTotalCapacity(vertex_count);
for (0..vertex_count) |_| {
try adjacency_lists.append(std.ArrayList(u32).init(allocator));
}
return Digraph{
.vertex_count = vertex_count,
.edge_count = 0,
.adjacency_lists = adjacency_lists,
.allocator = allocator,
};
}
pub fn deinit(self: *Digraph) void {
for (self.adjacency_lists.items) |*list| {
list.deinit();
}
self.adjacency_lists.deinit();
}
pub fn addEdge(self: *Digraph, from: u32, to: u32) !void {
self.validateVertex(from);
self.validateVertex(to);
try self.adjacency_lists.items[from].append(to);
self.edge_count += 1;
}
pub fn toString(self: *Digraph, allocator: std.mem.Allocator) ![]u8 {
var result = std.ArrayList(u8).init(allocator);
defer result.deinit();
try std.fmt.format(result.writer(), "Digraph has {d} vertices and {d} edges\nAdjacency lists:\n", .{ self.vertex_count, self.edge_count });
for (0..self.vertex_count) |vertex| {
if (vertex < 10) {
try result.append(' ');
}
try std.fmt.format(result.writer(), "{d}: ", .{vertex});
// Sort the adjacency list
std.sort.insertion(u32, self.adjacency_lists.items[vertex].items, {}, comptime std.sort.asc(u32));
for (self.adjacency_lists.items[vertex].items) |adjacent| {
try std.fmt.format(result.writer(), "{d} ", .{adjacent});
}
try result.append('\n');
}
return result.toOwnedSlice();
}
pub fn getVertexCount(self: Digraph) u32 {
return self.vertex_count;
}
pub fn getEdgeCount(self: Digraph) u32 {
return self.edge_count;
}
pub fn getAdjacencyList(self: Digraph, vertex: u32) ![]const u32 {
self.validateVertex(vertex);
return self.adjacency_lists.items[vertex].items;
}
fn validateVertex(self: Digraph, vertex: u32) void {
if (vertex >= self.vertex_count) {
std.debug.panic("Vertex must be between 0 and {d}: {d}", .{ self.vertex_count - 1, vertex });
}
}
};
const UNDEFINED: u32 = std.math.maxInt(u32);
/// Determination of the strongly connected components (SCC's) of a directed graph using Gabow's algorithm.
const GabowSCC = struct {
visited: []bool,
component_IDs: []u32,
preorders: []u32,
preorder_count: u32,
scc_count: u32,
visited_vertices_stack: std.ArrayList(u32),
auxiliary_stack: std.ArrayList(u32),
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator, digraph: Digraph) !GabowSCC {
const vertex_count = digraph.getVertexCount();
const visited = try allocator.alloc(bool, vertex_count);
@memset(visited, false);
const component_IDs = try allocator.alloc(u32, vertex_count);
@memset(component_IDs, UNDEFINED);
const preorders = try allocator.alloc(u32, vertex_count);
@memset(preorders, UNDEFINED);
var result = GabowSCC{
.visited = visited,
.component_IDs = component_IDs,
.preorders = preorders,
.preorder_count = 0,
.scc_count = 0,
.visited_vertices_stack = std.ArrayList(u32).init(allocator),
.auxiliary_stack = std.ArrayList(u32).init(allocator),
.allocator = allocator,
};
for (0..vertex_count) |vertex| {
if (!result.visited[vertex]) {
try result.depthFirstSearch(digraph, @intCast(vertex));
}
}
return result;
}
pub fn deinit(self: *GabowSCC) void {
self.allocator.free(self.visited);
self.allocator.free(self.component_IDs);
self.allocator.free(self.preorders);
self.visited_vertices_stack.deinit();
self.auxiliary_stack.deinit();
}
// Return, for each vertex, a list of its strongly connected vertices
pub fn getComponents(self: GabowSCC) !std.ArrayList(std.ArrayList(u32)) {
var components = std.ArrayList(std.ArrayList(u32)).init(self.allocator);
try components.ensureTotalCapacity(self.scc_count);
for (0..self.scc_count) |_| {
try components.append(std.ArrayList(u32).init(self.allocator));
}
for (0..self.visited.len) |vertex| {
const component_id = self.getComponentID(@intCast(vertex));
if (component_id != UNDEFINED) {
try components.items[component_id].append(@intCast(vertex));
} else {
std.debug.panic("Warning: Vertex {d} has no SCC ID assigned.", .{vertex});
}
}
return components;
}
// Return whether or not vertices 'v' and 'w' are in the same strongly connected component.
pub fn isStronglyConnected(self: GabowSCC, v: u32, w: u32) bool {
self.validateVertex(v);
self.validateVertex(w);
return self.component_IDs[v] != UNDEFINED and self.component_IDs[v] == self.component_IDs[w];
}
// Return the component ID of the strong component containing 'vertex'.
pub fn getComponentID(self: GabowSCC, vertex: u32) u32 {
self.validateVertex(vertex);
return self.component_IDs[vertex];
}
pub fn getSccCount(self: GabowSCC) u32 {
return self.scc_count;
}
fn depthFirstSearch(self: *GabowSCC, digraph: Digraph, vertex: u32) !void {
self.visited[vertex] = true;
self.preorders[vertex] = self.preorder_count;
self.preorder_count += 1;
try self.visited_vertices_stack.append(vertex);
try self.auxiliary_stack.append(vertex);
const adjacents = try digraph.getAdjacencyList(vertex);
for (adjacents) |adjacent| {
if (!self.visited[adjacent]) {
try self.depthFirstSearch(digraph, adjacent);
} else if (self.component_IDs[adjacent] == UNDEFINED) {
// Pop vertices from the 'auxiliary_stack'
// until the top vertex has a preorder <= preorder of 'adjacent'.
while (self.auxiliary_stack.items.len > 0 and
self.preorders[self.auxiliary_stack.items[self.auxiliary_stack.items.len - 1]] > self.preorders[adjacent]) {
_ = self.auxiliary_stack.pop();
}
}
}
// 'vertex' is the root of a SCC,
// if it remains on top of the 'auxiliary_stack' after exploring all of its descendants and back-edges.
if (self.auxiliary_stack.items.len > 0 and self.auxiliary_stack.items[self.auxiliary_stack.items.len - 1] == vertex) {
_ = self.auxiliary_stack.pop();
// Pop vertices from the 'auxiliary_stack' until 'vertex' is popped,
// and assign these vertices the current strongly connected component id.
while (self.visited_vertices_stack.items.len > 0) {
const adjacent = self.visited_vertices_stack.pop().?; // Use .? to unwrap the optional
self.component_IDs[adjacent] = self.scc_count;
if (adjacent == vertex) {
break;
}
}
self.scc_count += 1;
}
}
fn validateVertex(self: GabowSCC, vertex: u32) void {
const visited_count = self.visited.len;
if (vertex >= visited_count) {
std.debug.panic("Vertex {d} is not between 0 and {d}", .{ vertex, visited_count - 1 });
}
}
};
const Edge = struct {
from: u32,
to: u32,
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const edges = [_]Edge{
.{ .from = 4, .to = 2 }, .{ .from = 2, .to = 3 }, .{ .from = 3, .to = 2 }, .{ .from = 6, .to = 0 },
.{ .from = 0, .to = 1 }, .{ .from = 2, .to = 0 }, .{ .from = 11, .to = 12 }, .{ .from = 12, .to = 9 },
.{ .from = 9, .to = 10 }, .{ .from = 9, .to = 11 }, .{ .from = 8, .to = 9 }, .{ .from = 10, .to = 12 },
.{ .from = 0, .to = 5 }, .{ .from = 5, .to = 4 }, .{ .from = 3, .to = 5 }, .{ .from = 6, .to = 4 },
.{ .from = 6, .to = 9 }, .{ .from = 7, .to = 6 }, .{ .from = 7, .to = 8 }, .{ .from = 8, .to = 7 },
.{ .from = 5, .to = 3 }, .{ .from = 0, .to = 6 },
};
var digraph = try Digraph.init(allocator, 13);
defer digraph.deinit();
for (edges) |edge| {
try digraph.addEdge(edge.from, edge.to);
}
const stdout = std.io.getStdOut().writer();
try stdout.print("Constructed digraph:\n", .{});
const digraph_str = try digraph.toString(allocator);
defer allocator.free(digraph_str);
try stdout.print("{s}\n", .{digraph_str});
var gabow_scc = try GabowSCC.init(allocator, digraph);
defer gabow_scc.deinit();
try stdout.print("It has {d} strongly connected components.\n\n", .{gabow_scc.getSccCount()});
var components = try gabow_scc.getComponents();
defer {
for (components.items) |*component| {
component.deinit();
}
components.deinit();
}
try stdout.print("Components:\n", .{});
for (components.items, 0..) |component, i| {
try stdout.print("Component {d}: ", .{i});
for (component.items) |vertex| {
try stdout.print("{d} ", .{vertex});
}
try stdout.print("\n", .{});
}
try stdout.print("\nExample connectivity checks:\n", .{});
try stdout.print("Vertices 0 and 3 strongly connected? {}\n", .{gabow_scc.isStronglyConnected(0, 3)});
try stdout.print("Vertices 0 and 7 strongly connected? {}\n", .{gabow_scc.isStronglyConnected(0, 7)});
try stdout.print("Vertices 9 and 12 strongly connected? {}\n", .{gabow_scc.isStronglyConnected(9, 12)});
try stdout.print("Component ID of vertex 5: {d}\n", .{gabow_scc.getComponentID(5)});
try stdout.print("Component ID of vertex 8: {d}\n", .{gabow_scc.getComponentID(8)});
}
- Output:
Constructed digraph: Digraph has 13 vertices and 22 edges Adjacency lists: 0: 1 5 6 1: 2: 0 3 3: 2 5 4: 2 5: 3 4 6: 0 4 9 7: 6 8 8: 7 9 9: 10 11 10: 12 11: 12 12: 9 It has 4 strongly connected components. Components: Component 0: 1 Component 1: 9 10 11 12 Component 2: 0 2 3 4 5 6 Component 3: 7 8 Example connectivity checks: Vertices 0 and 3 strongly connected? true Vertices 0 and 7 strongly connected? false Vertices 9 and 12 strongly connected? true Component ID of vertex 5: 2 Component ID of vertex 8: 3