Русский
Русский
English
Статистика
Реклама

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

В статье описаны общие идеи по реализации ориентированного графа в 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   graphWHERE   vertex_order  = 1 AND   edge IN (SELECT edge FROM graph WHERE vertex  = current_id AND vertex_order = 0  );


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


SELECT   id FROM   graphWHERE   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_matrixAS(  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   distanceINTO   current_distanceFROM   tmp_matrixWHERE   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_finishFROM   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 в обратном порядке. Для удобства просмотра массив можно реверсировать любым способом.
Источник: habr.com
К списку статей
Опубликовано: 21.07.2020 14:09:04
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Postgresql

Графы

Graphs

Pgsql

Категории

Последние комментарии

© 2006-2022, personeltest.ru