Common code for traversing all kinds of graph

create unique index terminal_unq on <the path table>(path[cardinality(path)])

drop function if exists start cascade;
drop function if exists terminal cascade;

create function start(path in text[])
  returns text
  immutable
  language plpgsql
as $body$
begin
  return path[1];
end;
$body$;

create function terminal(path in text[])
  returns text
  immutable
  language plpgsql
as $body$
begin
  return path[cardinality(path)];
end;
$body$;

drop function if exists path_as_text(text[]) cascade;

create function path_as_text(path in text[])
  returns text
  immutable
  language plpgsql
as $body$
begin
  return path::text;
end;
$body$;

drop procedure if exists create_path_table(text, boolean) cascade;

create procedure create_path_table(name in text, temp in boolean)
  language plpgsql
as $body$
declare
  drop_table constant text := '
    drop table if exists ? cascade';

  create_table constant text := '
    create table ?(
      k     serial  primary key,
      path  text[]  not null)';

  create_temp_table constant text := '
    create temporary table ?(
      k     serial  primary key,
      path  text[]  not null)';

  cache_sequence constant text := '
    alter sequence ?_k_seq  cache 100000';
begin
  execute replace(drop_table,     '?', name);
  case temp
    when true then execute replace(create_temp_table, '?', name);
    else           execute replace(create_table,      '?', name);
  end case;
  execute replace(cache_sequence, '?', name);
end;
$body$;

call create_path_table('raw_paths', false);

alter table raw_paths add column repeat_nr int;

drop function if exists raw_paths_trg_f() cascade;
create function raw_paths_trg_f()
  returns trigger
  language plpgsql
as $body$
declare
  max_iteration constant int := (
    select coalesce(max(repeat_nr), null, -1) + 1 from raw_paths);
begin
  update raw_paths set repeat_nr = max_iteration where repeat_nr is null;
  return new;
end;
$body$;

create trigger raw_paths_trg after insert on raw_paths
for each statement
execute function raw_paths_trg_f();

call create_path_table('raw_paths', false);
drop function if exists raw_paths_trg_f() cascade;

call create_path_table('shortest_paths',        false);
call create_path_table('unq_containing_paths',  false);
call create_path_table('temp_paths',            true);
call create_path_table('previous_paths',        true);

create unique index shortest_paths_start_terminal_unq on shortest_paths(start(path), terminal(path));

drop procedure if exists restrict_to_shortest_paths(text, text, boolean) cascade;

-- Restrict the paths from the start node to every other node
-- to just the shortest path to each distinct node.
create procedure restrict_to_shortest_paths(
  in_tab in text, out_tab in text, append in boolean default false)
  language plpgsql
as $body$
declare
  stmt constant text := '
    with
      -- For readability. Define cardinality and end_node as view columns.
      a1(k, cardinality, end_node, path) as (
        select
          k,
          cardinality(path),
          path[cardinality(path)],
          path
        from ?in_tab),

      -- In general, there is more than one path to any end_node. Define the
      -- minumum cardinality for each end_node as a pair of view columns.
      a2(cardinality, end_node) as (
        select
          min(cardinality),
          end_node
        from a1
        group by end_node),

      -- There might still be more than one path to a particular end_node
      -- where each of these has the minimum cardinality. Pick up the path
      -- for each of these following the GROUP BY to allow just one of these
      -- to be picked arbitrarily.
      a3(path, cardinality, end_node) as (
        select
          a1.path,
          cardinality,
          end_node
        from a1 inner join a2 using(cardinality, end_node)),

      -- Pick just one path among the possibly several minimum cardinality paths
      -- to each end_node.
      a4(path, cardinality, end_node) as (
        select
          min(path),
          cardinality,
          end_node
        from a3 group by cardinality, end_node)

    -- Finally, pick up the actual path to each arbitrily selected end_node to which the
    -- path has the minimum cardinality. No need to include the end_node column now because
    -- it is anyway shown as the final node in the path.
    insert into ?out_tab(path)
    select path
    from a4 inner join a1 using(path, cardinality, end_node)';
begin
  case append
    when false then execute 'delete from '||out_tab;
    else            null;
  end case;
  execute replace(replace(stmt, '?in_tab', in_tab), '?out_tab', out_tab);
end;
$body$;

drop procedure if exists restrict_to_longest_paths(text, text, boolean) cascade;

-- Restrict the paths from the start node to every other node
-- to just the longest path to each distinct node.
create procedure restrict_to_longest_paths(
  in_tab in text, out_tab in text, append in boolean default false)
  language plpgsql
as $body$
declare
  stmt constant text := '
    with
      -- For readability. Define cardinality and end_node as view columns.
      a1(k, cardinality, end_node, path) as (
        select
          k,
          cardinality(path),
          path[cardinality(path)],
          path
        from ?in_tab),

      -- In general, there is more than one path to any end_node. Define the
      -- maximum cardinality for each end_node as a pair of view columns.
      a2(cardinality, end_node) as (
        select
          max(cardinality),
          end_node
        from a1
        group by end_node),

      -- There might still be more than one path to a particular end_node
      -- where each of these has the maximum cardinality. Pick up the path
      -- for each of these following the GROUP BY to allow just one of these
      -- to be picked arbitrarily.
      a3(path, cardinality, end_node) as (
        select
          a1.path,
          cardinality,
          end_node
        from a1 inner join a2 using(cardinality, end_node)),

      -- Pick just one path among the possibly several maximum cardinality paths
      -- to each end_node.
      a4(path, cardinality, end_node) as (
        select
          max(path),
          cardinality,
          end_node
        from a3 group by cardinality, end_node)

    -- Finally, pick up the actual path to each arbitrily selected end_node to which the
    -- path has the maximum cardinality. No need to include the end_node column now because
    -- it is anyway shown as the final node in the path.
    insert into ?out_tab(path)
    select path
    from a4 inner join a1 using(path, cardinality, end_node)';
begin
  case append
    when false then execute 'delete from '||out_tab;
    else            null;
  end case;
  execute replace(replace(stmt, '?in_tab', in_tab), '?out_tab', out_tab);
end;
$body$;

drop procedure if exists restrict_to_unq_containing_paths(text, text, boolean) cascade;

-- Filter the input set of paths to set of longest paths
-- that jointly contain all the other paths.
create procedure restrict_to_unq_containing_paths(
  in_tab in text, out_tab in text, append in boolean default false)
  language plpgsql
as $body$
declare
  stmt constant text := '
    with
      -- Cartesian product restricted to give all possible
      -- longer path with shorter path combinations.
      each_path_with_all_shorter_paths as (
        select a1.path as longer_path, a2.path as shorter_path
        from ?in_tab as a1, ?in_tab as a2
        where cardinality(a1.path) > cardinality(a2.path)),

      -- Identify each shorter path that is contained by
      -- its longer path partner.
      contained_paths as (
        select
        shorter_path as contained_path
        from each_path_with_all_shorter_paths
        where longer_path @> shorter_path)

    -- Filter out the contained paths.
    insert into ?out_tab(path)
    select path
    from ?in_tab
    where path not in (
      select contained_path from contained_paths
      )';
begin
  case append
    when false then execute 'delete from '||out_tab;
    else            null;
  end case;
  execute replace(replace(stmt, '?in_tab', in_tab), '?out_tab', out_tab);
end;
$body$;

drop function if exists list_paths(text) cascade;

create function list_paths(tab in text)
  returns table(t text)
  language plpgsql
as $body$
declare
  -- Recall that when you address an array element that falls outside of its bounds,
  -- you get a `NULL` result. And recall that `NULLS FIRST` is the default sorting order.
  stmt constant text := $$
    with a(r, c, p) as (
      select
        row_number() over w,
        cardinality(path),
        path
      from ?
      window w as
        (order by path[1], cardinality(path), path[2], path[3], path[4], path[5], path[6]))

    select
      array_agg(
        lpad(r::text,  6) ||'   '||
        lpad(c::text, 11) ||'   '||
        replace(translate(p::text, '{}', ''), ',', ' > ')
        order by p[1], cardinality(p), p[2], p[3], p[4], p[5], p[6])
    from a
    $$;

  results text[] not null := '{}';
begin
  t := 'path #   cardinality   path'; return next;
  t := '------   -----------   ----'; return next;

  execute replace(stmt, '?', tab)  into results;
  foreach t in array results loop
    return next;
  end loop;
end;
$body$;

drop procedure if exists assert_shortest_paths_same_as_raw_paths() cascade;

create procedure assert_shortest_paths_same_as_raw_paths()
  language plpgsql
as $body$
declare
  n int not null := 999999;
begin
  with
    restricteded_except_raw as (
      select path
      from shortest_paths
      except
      select path
      from raw_paths),

    raw_except_restricted as (
      select path
      from raw_paths
      except
      select path
      from shortest_paths),

    filtered_except_raw_union_raw_except_filtered as (
      select path
      from restricteded_except_raw
      union all
      select path
      from raw_except_restricted)

  select
    count(*) into n
  from filtered_except_raw_union_raw_except_filtered;

  assert n = 0, 'unexpected';
end;
$body$;