Tarjan's strongly connected components algorithm implemented in PL/pgSQL

tarjan.sql

CREATE OR REPLACE FUNCTION tarjan(from_nodes int4range[], to_nodes int[])
RETURNS SETOF int[]
LANGUAGE plpgsql
AS
$$
--
-- https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
--
DECLARE
current_index integer := 0;
index int[];
lowlink int[];
on_stack bool[];
stack int[] := ARRAY[]::int[];
call_stack int[] := ARRAY[]::int[];
edge int;
node int;
next_node int;
next_edge int;
scc int[];
BEGIN
FOR node IN 1..cardinality(from_nodes)
LOOP
  IF index[node] IS NULL THEN
    call_stack := call_stack || node || NULL::int;
    <<recurse>>
    LOOP
      node := call_stack[cardinality(call_stack)-1];
      next_edge := call_stack[cardinality(call_stack)];
      call_stack := call_stack[:cardinality(call_stack)-2];
      IF next_edge IS NULL THEN
        index[node] := current_index;
        lowlink[node] := current_index;
        current_index := current_index + 1;
        stack := stack || node;
        on_stack[node] := TRUE;
      END IF;
      IF NOT from_nodes[node] = 'empty' THEN
        FOR edge IN COALESCE(next_edge,lower(from_nodes[node]))..(upper(from_nodes[node])-1)
        LOOP
          next_node := to_nodes[edge];
          IF index[next_node] IS NULL THEN
            call_stack := call_stack
              || node || (edge+1)
              || next_node || NULL::int;
            CONTINUE recurse;
          ELSIF on_stack[next_node] THEN
            lowlink[node] := LEAST(lowlink[node], index[next_node]);
          END IF;
        END LOOP;
      END IF;
      IF index[node] = lowlink[node] THEN
        scc := ARRAY[]::int[];
        LOOP
          next_node := stack[cardinality(stack)];
          stack := stack[:cardinality(stack)-1];
          on_stack[next_node] := FALSE;
          scc := scc || next_node;
          IF next_node = node THEN
            EXIT;
          END IF;
        END LOOP;
        RETURN NEXT scc;
      END IF;
      IF cardinality(call_stack) = 0 THEN
        EXIT;
      ELSE
        next_node := node;
        node := call_stack[cardinality(call_stack)-1];
        lowlink[node] := LEAST(lowlink[node], lowlink[next_node]);
      END IF;
    END LOOP;
  END IF;
END LOOP;
RETURN;
END
$$;

/*
Example from https://pypi.org/project/tarjan/

>>> tarjan({1:[2],2:[1,5],3:[4],4:[3,5],5:[6],6:[7],7:[8],8:[6,9],9:[]})
[[9], [8, 7, 6], [5], [2, 1], [4, 3]]

Same example using the PL/pgSQL tarjan() function:
*/

SELECT tarjan(
  from_nodes := '{"[1,1]","[2,3]","[4,4]","[5,6]","[7,7]","[8,8]","[9,9]","[10,11]",empty}'::int4range[],
  to_nodes := '{2,1,5,4,3,5,6,7,8,6,9}'::int[]
);

/*
 tarjan
---------
 {9}
 {8,7,6}
 {5}
 {2,1}
 {4,3}
(5 rows)
*/