Этюд по реализации ориентированного графа с единичными ребрами, используя PL/pgSQL

Граф был использован для реализации подчинения между сотрудниками, взамен использованного ранее метода «предок-потомок» в таблице отделов.

Опыт оказался успешным, может быть кому-то пригодится и поможет сэкономить время. Я в свое время искал реализации именно на pqSQL, но видимо плохо искал. Пришлось реализовывать самому. Что в общем-то даже к лучшему, задача интересная, всегда приятно что-то сделать своими руками, так, что время потрачено не зря.

Входные данные

В общем случае имеется стандартная таблица «должность сотрудника» c первичным ключом id. Должности имеют иерархию подчинения «начальник-сотрудник». Идея в том, что связи между должностями хранятся в отдельной сущности граф.
Для поиска пути в графе использован алгоритм Дейкстры, общее описание можно посмотреть например — здесь

Выходные данные

• Список подчиненных сотрудников для данного
• Список начальников для данного сотрудника
• Является ли сотрудник подчиненным для данного
• Список подчиненных сотрудников для данного(путь от начальника к сотруднику)

Реализация, используя PL/pgSQL

Хранение графа в виде таблицы ребер

Вершинами являются значения id, целевой таблицы.

CREATE TABLE graph (     vertex integer NOT NULL ,         --id записи в целевой таблице   edge integer NOT NULL ,           --id ребра   vertex_order integer NOT NULL --порядок вершины ( 0 предок, 1 потомок) );

Для генерации id ребра используется последовательность

CREATE SEQUENCE enge_seq OWNED BY graph.edge; 

Заполнение таблицы ребер

Для вставки нового ребра(вершины id0, id1) используется две операции INSERT

--Генерация нового id ребра new_id = nextval('enge_seq');

--Вставка предка INSERT INTO  graph (vertex  , edge , vertex_order  ) VALUES ( id0 , new_id , 0  );

--Вставка потомка INSERT INTO  graph (vertex  , edge , vertex_order  ) VALUES ( id1 , new_id , 1  );

Получение списка подчиненных сотрудников для данного current_id

SELECT    id  FROM    graph WHERE    vertex_order  = 1 AND    edge IN (SELECT edge FROM graph WHERE vertex  = current_id AND vertex_order = 0  );

Получение списка начальников для данного current_id

SELECT    id  FROM    graph WHERE    vertex_order  = 0 AND    edge IN (SELECT edge FROM graph WHERE vertex  = current_id AND vertex_order = 1  );

Генерация матрицы доступности (алгоритм Дейкстры) из заданной вершины start_id

CREATE TEMPORARY TABLE tmp_matrix AS (   SELECT      DISTINCT vertex  ,      FALSE AS label ,     999999 AS distance ,     FALSE AS is_finish    FROM     graph );

UPDATE tmp_matrix  SET label = TRUE , distance = 0  WHERE vertex = current_id ;   current_id = start_id ;  SELECT    distance INTO    current_distance FROM    tmp_matrix WHERE    vertex = current_id;  SELECT    EXISTS (SELECT 1 FROM tmp_matrix WHERE label = FALSE ) INTO   not_visit;

WHILE not_visit  LOOP   FOR v_rec IN     SELECT        *    FROM       tmp_matrix   WHERE      NOT label AND      --Вершина достижима за один шаг      vertex IN ( SELECT                         id                       FROM                        graph                     WHERE                        vertex_order  = 1 AND                        edge IN (SELECT                                       edge                                      FROM                                        graph                                      WHERE                                        vertex  = current_id AND vertex_order = 0  ))   LOOP         --Найдена достижимая вершина     IF v_rec.distance > (current_distance +1)     THEN        UPDATE tmp_matrix SET distance = (current_distance +1) WHERE vertex = v_rec.vertex;     END IF ;         --если закончен обход    IF SELECT          NOT EXISTS          (           SELECT 1 FROM graph WHERE vertex = v_rec.vertex AND vertex_order = 0          )    THEN      UPDATE tmp_matrix SET label = TRUE , is_finish = TRUE WHERE vertex = v_rec.vertex;    END IF ;      END LOOP;      UPDATE tmp_matrix SET label = TRUE WHERE vertex = current_id ;    --Следующая итерация   SELECT      vertex   INTO     current_id    FROM      tmp_matrix    WHERE      NOT label AND     distance < 999999 ;    SELECT      distance   INTO      current_distance   FROM      tmp_matrix    WHERE       vertex = current_id ;    SELECT      EXISTS (SELECT 1 FROM tmp_matrix  WHERE label = FALSE )   INTO    not_visit ;    IF current_id IS NULL    THEN      not_visit = FALSE ;    END IF; END LOOP;

SELECT    vertex ,    label ,     distance ,    is_finish FROM    tmp_matrix  WHERE    distance != 999999 ; 

Является ли сотрудник с check_id подчиненным для данного start_id

Получить матрицу доступности для start_id (см. выше).

IF EXISTS    ( SELECT distance FROM tmp_matrix WHERE vertex = check_id  ) THEN     RETURN TRUE; ELSE    RETURN FALSE; END IF;

Список подчиненных сотрудников для данного(путь от начальника start_id к сотруднику finish_id)

Получить матрицу доступности для start_id (см. выше).

current_id = finish_id ; result[1] = finish_id ;  WHILE current_id != start_id  LOOP   SELECT      par.id    FROM     ( SELECT         id       FROM        graph     WHERE        vertex_order  = 0 AND        edge IN (SELECT                       edge                      FROM                        graph                      WHERE                        vertex  = current_id AND vertex_order = 1  )) par   JOIN  tmp_matrix m ON ( par.id = m.vertex  )   INTO      parent_id   LIMIT 1 ;    SELECT      array_append( result , parent_id )   INTO      result ;   --Следующая итерация current_id = parent_id ;    END LOOP;

В результате в массиве result сформируется путь в виде набора id в обратном порядке. Для удобства просмотра массив можно реверсировать любым способом.