Блог

Главная - Вопросы по программированию - Как выполнить обход графа по нескольким путям

Как выполнить обход графа по нескольким путям

#sql #postgresql

#sql #postgresql

Вопрос:

Введение в проблему

У меня есть список ребер графа с fromNodes, toNodes и свойствами ребра (EdgeType и edgeLength) в таблице SQL.

Моя цель — найти все желтые ребра, а затем построить пути по графу, состоящему из всех соединенных синих ребер (начиная с каждого желтого ребра).

Я реализовал следующее для этого обсуждения:

Примерный график

ШАГ 1 Итак, сначала я хочу найти все желтые края, это легко:

 WITH 
  YellowEdges AS
  (SELECT EdgeId, FromNodeID, ToNodeID,EdgeType,EdgeLength,array_append(GraphNetwork.EDGES,GraphNetwork.EdgeId) AS EdgePathArray
     FROM GraphNetwork
  WHERE EdgeType = 3
  )
  
SELECT * 
FROM YellowEdge

Теперь у нас есть все желтые ребра 1,4,6,9,15
Запрос, чтобы найти все желтые края

ШАГ 2 Найдите все синие края, хорошо, никаких проблем

 WITH
  YellowEdges AS
  (SELECT EdgeId, FromNodeID, ToNodeID,EdgeType,EdgeLength,array_append(GraphNetwork.EDGES,GraphNetwork.EdgeId) AS EdgePathArray
     FROM GraphNetwork
  WHERE EdgeType = 3
  ),
  BlueEdges AS 
  (SELECT *
  FROM GraphNetwork
  WHERE EdgeType = 2
  )

SELECT *
FROM BlueEdges

Синие Края

ШАГ 3 Найдите все синие ребра, которые ведут к желтым ребрам, и выполните соединение по левому краю, добавив как желтые, так и синие ребра в столбец массивов, называемый edge path array

 WITH
  YellowEdges AS
  (SELECT EdgeId, FromNodeID, ToNodeID,EdgeType,EdgeLength,array_append(GraphNetwork.EDGES,GraphNetwork.EdgeId) AS EdgePathArray
     FROM GraphNetwork
  WHERE EdgeType = 3
  ),
  BlueEdges AS 
  (SELECT *
  FROM GraphNetwork
  WHERE EdgeType = 2
  ),
  EdgePathTable AS
  (SELECT *
  FROM (
    SELECT BlueEdges.EdgeId, BlueEdges.FromNodeID, BlueEdges.ToNodeID,BlueEdges.EdgeType,BlueEdges.EdgeLength,array_append(YellowEdges.EdgePathArray,BlueEdges.EdgeId) AS EdgePathArray
    FROM YellowEdges
    LEFT JOIN BlueEdges
    ON YellowEdges.EdgeId <> BlueEdges.EdgeId 
    AND YellowEdges.FromNodeID = BlueEdges.ToNodeID 
       ) AS unnamedTable
  )
  
SELECT * 
FROM EdgePathTable

Первая итерация по пути

Шаг 4 Теперь найдите все синие ребра, которые соединяются с синими ребрами, которые мы определили ранее, и добавьте их к контуру (убедитесь, что новые ребра ранее не были пройдены как часть этого пути (чтобы избежать круговых путей)

 WITH
  YellowEdges AS
  (SELECT EdgeId, FromNodeID, ToNodeID,EdgeType,EdgeLength,array_append(GraphNetwork.EDGES,GraphNetwork.EdgeId) AS EdgePathArray
     FROM GraphNetwork
  WHERE EdgeType = 3
  ),
  BlueEdges AS 
  (SELECT *
  FROM GraphNetwork
  WHERE EdgeType = 2
  ),
  EdgePathTable AS
  (SELECT *
  FROM (
    SELECT BlueEdges.EdgeId, BlueEdges.FromNodeID, BlueEdges.ToNodeID,BlueEdges.EdgeType,BlueEdges.EdgeLength,array_append(YellowEdges.EdgePathArray,BlueEdges.EdgeId) AS EdgePathArray
    FROM YellowEdges
    LEFT JOIN BlueEdges
    ON YellowEdges.EdgeId <> BlueEdges.EdgeId 
    AND YellowEdges.FromNodeID = BlueEdges.ToNodeID 
       ) AS unnamedTable
  )

SELECT *
FROM (SELECT EdgePathTable_iteration2.EdgeId, EdgePathTable_iteration2.FromNodeID, EdgePathTable_iteration2.ToNodeID,EdgePathTable_iteration2.EdgeType,EdgePathTable_iteration2.EdgeLength,array_append(EdgePathTable.EdgePathArray,EdgePathTable_iteration2.EdgeId) AS EdgePathArray
FROM EdgePathTable
LEFT JOIN BlueEdges AS EdgePathTable_iteration2
ON EdgePathTable_iteration2.EdgeId <> any(EdgePathTable.EdgePathArray) 
AND EdgePathTable.FromNodeID = EdgePathTable_iteration2.ToNodeID) AS EdgePathTable

Добавьте следующий набор синих краев

ШАГ 5 Повторяйте шаг 4, пока не будет выполнено какое-либо условие i (e выполните x итераций, или вы достигли конца каждого пути).

Хорошо, вот где я застрял. Я рассмотрел несколько потенциальных вариантов: рекурсивный CTE, рекурсивный вызов функции, вызов функции в цикле while или, может быть, просто повторение этого запроса в цикле while.

Я не уверен, какой из них, если таковые имеются, позволит мне делать то, что я хочу:

  1. Рекурсивный CTE, в котором я не уверен, будет работать, поскольку он основан на объединении, и, похоже, его невозможно реализовать с помощью left join. Я нашел несколько примеров обхода дерева, но в каждом случае он был ограничен началом с одного ребра, я предполагаю, что это ограничение этого метода, поскольку объединение увеличивает количество строк, а не количество столбцов. Мне нужен метод, который позволяет мне пересекать несколько ребер, как то, что я начал делать здесь. Когда я в конечном итоге заработаю, я перенесу это в нашу фактическую базу данных, которая, вероятно, имеет 100 000-1 000 000 таких ребер
  2. Функциональные параметры вызова кажутся сложными, потому что кажется, что вы не можете передать таблицу функции (но вы можете передать табличную вещь или что-то в этом роде, но я все еще не смог этого понять)
  3. Мне нравится идея просто повторить этот запрос в цикле while, но я не смог найти понятную документацию о том, как выполнить цикл while в запросе PostgreSQL. Я не смог реализовать даже базовый цикл while в запросе на SQL fiddle.

Вот ссылка на скрипку к примеру до шага 4:

http://sqlfiddle.com /#!17/2a341d/1

Или вы можете найти пример кода ниже. Я немного застрял на этом и был бы очень признателен за помощь.

 CREATE TABLE GraphNetwork 
(
    EdgeId INT primary key,
    FromNodeID INT,  
    ToNodeID INT,
    EdgeType INT,
    EdgeLength INT,
    EDGES INT[]
);

INSERT INTO GraphNetwork (EdgeId, FromNodeID, ToNodeID, EdgeType, EdgeLength)
VALUES
    (1,2,1,3,10),
    (2,3,2,2,50),
    (3,4,3,2,40),
    (4,5,4,3,15),
    (5,5,16,2,60),
    (6,4,5,3,20),
    (7,3,4,2,80),
    (8,2,3,2,25),
    (9,7,6,3,5),
    (10,8,7,2,20),
    (11,9,8,2,35),
    (12,7,9,2,10),
    (13,10,9,2,10),
    (14,11,10,1,15),
    (15,13,12,3,25),
    (16,14,13,2,25),
    (17,15,14,1,30)
;
 
 WITH YellowEdges AS
(
    SELECT 
        EdgeId, FromNodeID, ToNodeID, EdgeType, EdgeLength,
        array_append(GraphNetwork.EDGES, GraphNetwork.EdgeId) AS EdgePathArray
    FROM 
        GraphNetwork
    WHERE 
        EdgeType = 3
),
BlueEdges AS 
(
    SELECT *
    FROM GraphNetwork
    WHERE EdgeType = 2
),
EdgePathTable AS
( 
    SELECT *
    FROM 
        (SELECT 
             BlueEdges.EdgeId, BlueEdges.FromNodeID, BlueEdges.ToNodeID,
             BlueEdges.EdgeType, BlueEdges.EdgeLength,
             array_append(YellowEdges.EdgePathArray, BlueEdges.EdgeId) AS EdgePathArray
         FROM 
             YellowEdges
         LEFT JOIN 
             BlueEdges ON YellowEdges.EdgeId <> BlueEdges.EdgeId 
                       AND YellowEdges.FromNodeID = BlueEdges.ToNodeID 
        ) AS unnamedTable
)
SELECT *
FROM 
    (SELECT 
         EdgePathTable_iteration2.EdgeId, 
         EdgePathTable_iteration2.FromNodeID, 
         EdgePathTable_iteration2.ToNodeID,
         EdgePathTable_iteration2.EdgeType,
         EdgePathTable_iteration2.EdgeLength,
         array_append(EdgePathTable.EdgePathArray, EdgePathTable_iteration2.EdgeId) AS EdgePathArray
     FROM 
         EdgePathTable
     LEFT JOIN 
         BlueEdges AS EdgePathTable_iteration2 ON EdgePathTable_iteration2.EdgeId <> ANY(EdgePathTable.EdgePathArray) 

                                               AND EdgePathTable.FromNodeID = EdgePathTable_iteration2.ToNodeID) AS EdgePathTable

Ответ №1:

A recursive cte должен предоставить вам ожидаемый результат.

  • Нерекурсивный термин выделяет все желтые ребра.
  • Рекурсивный термин итеративно добавляет синие края к желтым краям.
  • LEFT JOIN не требуется в рекурсивном термине, INNER JOIN это нормально, потому что рекурсивный термин добавляет несколько новых строк к существующим, исходящим из нерекурсивного термина и предыдущих итераций рекурсивного термина.
  • В WHERE предложении рекурсивного термина NOT l.EdgePathArray @> array[g.EdgeID] является обязательным, чтобы избежать бесконечных циклов.

recursive cte Предоставляет слишком много строк из-за новых строк, создаваемых на каждой итерации. Самосоединение в рекурсивном результате cte позволяет выбирать только соответствующие строки, то есть строки, которые EdgePathArray не являются составной частью EdgePathArray другой строки.

Вот код sql :

 WITH RECURSIVE list (EdgeId, FromNodeID, ToNodeID, EdgeType, EdgeLength, EdgePathArray) AS
(
SELECT EdgeId, FromNodeID, ToNodeID, EdgeType, EdgeLength, array[EdgeId] AS EdgePathArray
  FROM GraphNetwork
  WHERE EdgeType = 3
UNION ALL
SELECT g.EdgeId, g.FromNodeID, g.ToNodeID, g.EdgeType, g.EdgeLength, l.EdgePathArray || g.EdgeId
  FROM list AS l
 INNER JOIN GraphNetwork AS g
    ON g.ToNodeID = l.FromNodeID
 WHERE g.EdgeType = 2
   AND NOT l.EdgePathArray @> array[g.EdgeID]
)
SELECT c.*
  FROM list AS c
  LEFT JOIN list AS f
   ON f.EdgePathArray @> c.EdgePathArray
  AND f.EdgePathArray <> c.EdgePathArray
 WHERE f.EdgePathArray IS NULL
 ORDER BY c.EdgePathArray

Вот результат теста.

Все подробности о рекурсивном cte см. в руководстве.

Метки: