strongly_connected_components

Network functions > strongly_connected_components

syntax

• strongly_connected_components(from_node_rel, to_node_rel)

description

The strongly_connected_components function identifies strongly connected components in a directed graph. A strongly connected component (SCC) is a maximal subgraph where every node is reachable from every other node following the direction of the edges.

The function takes two attributes defining the directed edges of the graph:

• from_node_rel: for each edge, the source node
• to_node_rel: for each edge, the target node

The function uses Tarjan's algorithm to efficiently compute the SCCs in a single pass through the graph.

applies to

• attribute from_node_rel with domain E (edges) and values unit V (nodes), UInt32 value type
• attribute to_node_rel with domain E (edges) and values unit V (nodes), UInt32 value type

conditions

1. Both arguments must have the same domain unit (the edge domain E).
2. Both arguments must have the same values unit (the node domain V).
3. Node indices must be valid (within the range of V) or null.

result

The function returns a new unit P representing the set of strongly connected components, with the following subitems:

subitem	description
part_rel	attribute V->P mapping each node to its strongly connected component
PartLink	unit F representing edges between different SCCs
PartLink/from_rel	attribute F->P indicating the source SCC of each inter-component edge
PartLink/to_rel	attribute F->P indicating the target SCC of each inter-component edge

performance

aspect	indication
time complexity	O(V + E) where V = number of nodes, E = number of edges
memory	O(V + E) for internal data structures
parallelization	single-threaded (iterative Tarjan's algorithm)

This is an efficient linear-time algorithm. For very large graphs (millions of nodes/edges), memory usage scales linearly.

since version

14.0

example

unit<uint32> Node: nrofrows = 6;
unit<uint32> Edge: nrofrows = 8
{
   attribute<Node> from_node: [0, 1, 2, 3, 3, 4, 5, 5];
   attribute<Node> to_node:   [1, 2, 0, 2, 4, 5, 4, 3];
}

unit<uint32> SCC := strongly_connected_components(Edge/from_node, Edge/to_node);
// Results in 3 SCCs:
// - SCC 0: nodes {0, 1, 2} (cycle)
// - SCC 1: nodes {3, 4, 5} (cycle) 
// - SCC 2: isolated if any

see also

• connected_parts - for undirected graph connectivity
• Network functions

GeoDMS ©Object Vision BV. Source code distributed under GNU GPL-3. Documentation distributed under CC BY-SA 4.0.