rinace Jul 21 2020 at 14:06

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

3 min

3.7K

В статье описаны общие идеи и наброски по реализации ориентированного графа в PostgreSQL.

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

Опыт оказался успешным, может быть кому-то пригодится и поможет сэкономить время. Я в свое время искал реализации именно на 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

Создание временной таблицы tmp_matrix

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

Первоначальное заполнение таблицы tmp_matrix

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 (см. выше).

Заполнить таблицу пути между таблицами start_id и finish_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 в обратном порядке. Для удобства просмотра массив можно реверсировать любым способом.

Tags:

Hubs: