🤐 🛡️ 🦊 مقال عن تنفيذ رسم بياني موجه باستخدام حواف الوحدة باستخدام PL / pgSQL 🏂🏻 🈂️ 🖐🏻

تقدم هذه المقالة أفكارًا ومخططات عامة لتنفيذ رسم بياني موجه في PostgreSQL.

تم استخدام الرسم البياني لتنفيذ التبعية بين الموظفين ، بدلاً من طريقة الجد-الطفل المستخدمة سابقًا في جدول القسم.

تبين أن التجربة كانت ناجحة ، فربما تكون مفيدة لشخص ما وتساعد في توفير الوقت. في وقت ما كنت أبحث عن تطبيق على pqSQL ، لكن يبدو أنني كنت أبدو سيئًا. كان علي أن أنفذها بنفسي. الذي ، بشكل عام ، حتى للأفضل ، المهمة مثيرة للاهتمام ، من الجيد دائمًا أن تفعل شيئًا بيديك ، حتى لا يضيع الوقت.

ادخال البيانات

بشكل عام ، هناك جدول قياسي "منصب الموظف" مع معرف المفتاح الأساسي . المناصب لها تسلسل هرمي من تبعية "كبير الموظفين". الفكرة هي أن الروابط بين المنشورات يتم تخزينها في رسم بياني منفصل للكيان .

تم استخدام خوارزمية Dijkstra للعثور على مسار في الرسم البياني ، ويمكن العثور على وصف عام ، على سبيل المثال ، هنا

انتاج |

قائمة الموظفين المرؤوسين لهذا الغرض
قائمة الرؤساء لهذا الموظف
هل الموظف مرؤوس لهذا
قائمة الموظفين المرؤوسين لهذا (المسار من الرئيس إلى الموظف)

التنفيذ باستخدام PL / pgSQL

تخزين الرسم البياني كجدول من الحواف

القمم هي قيم معرف الجدول الهدف.

CREATE TABLE graph
(  
  vertex integer NOT NULL ,         --id    
  edge integer NOT NULL ,           --id 
  vertex_order integer NOT NULL --  ( 0 , 1 )
);

لتوليد معرف الحافة ، استخدم التسلسل

CREATE SEQUENCE enge_seq OWNED BY graph.edge;

ملء طاولة الحافة

يتم استخدام عمليتي INSERT لإدراج حافة جديدة (الرؤوس id0 ، id1 )

--  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  );

الحصول على قائمة الرؤساء للمعرّف الحالي

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

إنشاء مصفوفة الإتاحة (خوارزمية Dijkstra) من 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;

قائمة الموظفين المرؤوسين لهذا واحد (المسار من بداية رئيسه إلى معرف انتهاء الموظف)