Количество связных компонент графа в SQL

Ты что теперь? Несмотря на то, что я рекомендовал вам написать процедуру хранения на PL/Python, позже я решил написать этот одиночный sql-запрос просто для развлечения. Вот что я сделал. Я использовал RECURSIVE CTE.

WITH RECURSIVE graph_search(node_id, connected_to, path, cycle) AS (
        SELECT node_id, connected_to, ARRAY[node_id], false FROM paths
    UNION 
        SELECT p.node_id, p.connected_to, gs.path || p.node_id, p.node_id=ANY(gs.path)
        FROM graph_search gs JOIN paths p ON gs.connected_to = p.node_id AND NOT gs.cycle
 ),
 paths AS (
    SELECT node_id, connected_to
    FROM (
        SELECT n.node_id, unnest(r.nodes) AS connected_to
        FROM nodes n JOIN roads r ON n.node_id = ANY(r.nodes)
    ) sub
    WHERE node_id <> connected_to
 ) 
SELECT count(DISTINCT component)
FROM (
        SELECT node_id,
               array_agg(DISTINCT reachable_node ORDER BY reachable_node) as component
        FROM (
            SELECT node_id, unnest(path) as reachable_node from graph_search 
        ) sub
        GROUP BY node_id
    UNION ALL /*need to append lonely nodes - they are components for themselves*/
        SELECT node_id, ARRAY[node_id]
        FROM nodes
        WHERE node_id NOT IN (SELECT node_id from paths)
) sub;

• Во-первых, мне нужно другое представление самого графика. Обычный CTE с именем paths создает двухстолбцовую таблицу с парами связанных узлов.
• Затем я просто немного изменил пример из руководства PostgreSQL, так что у меня есть список узлов и всех узлов, достижимых из него.
• Агрегация дает мне компоненты графа.
• В конце я подсчитываю отдельные компоненты.

Решение выше не будет работать, если количество узлов слишком велико.

Наиболее эффективное решение (если у вас достаточно оперативной памяти для чтения всех данных) — это считывание данных в память с помощью таких языков, как C или C++, и выполнение вычислений там.

Но если размер данных слишком велик и у вас нет выбора, то, вероятно, вы можете сделать это следующим образом:

(реализация plpgssql, предполагая, что у нас есть табличные дороги (node1, node2))

CREATE TABLE node AS
  SELECT DISTINCT node1 AS id, node1 AS color
  FROM roads

  CREATE OR REPLACE FUNCTION merge_node()
  RETURNS VOID
AS
$$
DECLARE
left_to_do INT := 1;
counter INT :=1;
row record;
BEGIN
    DROP TABLE IF EXISTS t;
CREATE TEMP TABLE t  (
    node1 INT,
    prev INT,
    next INT
);

    WHILE left_to_do > 0
    LOOP
        WITH joined_table AS (
            SELECT roads.node1,
                   MAX (v1.color) AS prev,
                   MAX (v2.color) AS next
            FROM roads
            JOIN node v1 ON roads.node1 = v1.id
            JOIN node v2 ON roads.node2 = v2.id
            GROUP BY roads.node1
        )
        INSERT INTO t (node1, prev, next)
        SELECT node1,
               prev,
               next
        FROM joined_table
        WHERE prev < next;
        SELECT COUNT(*) INTO left_to_do FROM t;
        UPDATE node color
        SET color = t.next
        FROM t
        WHERE color.id = t.node1;
        DELETE FROM t;
        counter := counter + 1;
    END LOOP;
END;
$$
LANGUAGE plpgsql;

это должно работать лучше, если степень узла низка по сравнению с количеством узлов. протестировал его на графе с 2,4 миллионами узлов и 24 миллионами ребер, и это занимает около 30-60 минут с индексами. (Для сравнения, в С++ требуется 2,5 минуты, большую часть времени он считывает данные из csv/записывает данные в csv)