How to perform graph traversal along multiple paths

Question

Problem Introduction

I have a list of graph edges with fromNodes, toNodes, and the edge properties (edgeType and edgeLength) in a SQL table.

My goal is to find all yellow edges and then build paths through the graph consisting of all connected blue edges (starting with each yellow edge).

I implemented the following for this discussion:

STEP 1 So first I want to find all yellow edges, that's easy:

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

Now we have all of the yellow edges 1,4,6,9,15

STEP 2 Find all the blue edges, okay no problem

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

STEP 3 Find all blue edges that lead to yellow edges and perform a left join, adding both yellow edges and blue edges to a column of arrays called 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

Step 4 Now find all blue edges that connect to the blue edges we identified previously and add these to the path (Make sure that new edges have not been previously traversed as part of this path (to avoid circular paths)

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

STEP 5 Repeat step 4 until some condition is met i(e perform x iterations, or you have reached the end of each path).

Okay so here is where I am stuck. I've looked into a few potential options, Recursive CTE, recursive function call, function call in a while loop, or maybe just repeating this query in a while loop.

I'm not sure which of these if any would allow me to do what I want:

The recursive CTE I'm not sure would work since it relies on union and it seems to not be possible to implement with left join. I did find some tree traversal examples, but in each case it was limited to starting with a single edge, I'm assuming that is a limitation of that method since union expands the number of rows not the number of columns. I need a method that allows me to traverse multiple edges like what I've started to do here. When I eventually get this working I will port this to our actual database which probably has 100,000-1,000,000 of these edges
The functional call options seem tricky because it seems like you can't pass a table to a function (but you can pass a table like thing or something but still I haven't been able to figure that out)
I like the idea of just repeating this query in a while loop but I haven't been able to find understandable documentation on how to do a while loop in a PostgreSQL query. I haven't been able to implement even a basic while loop in a query on SQL fiddle.

Here's the fiddle link to the example up to step 4:

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

Or else you can find the example code below. I've been stuck on this for a bit now and would really appreciate some help.

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

user_8060017 · Answer

A recursive cte should provide you the expected result.

The non-recursive term select all the yellow edges.
The recursive term appends the blue edges to the yellow edges in an iterative way.
LEFT JOIN is not needed in the recursive term, INNER JOIN is ok because the recursive term adds some new rows to the existing ones comming from the non-recursive term and the previous iterations of the recursive term.
In the WHERE clause of the recursive term, NOT l.EdgePathArray @> array[g.EdgeID] is mandatory in order to avoid infinite loops.

The recursive cte provides too many rows due to the new rows created at every iteration. The self join on the recursive cte result allows to select the relevant rows only, ie the rows whose EdgePathArray is not a sub part of another row's EdgePathArray.

Here is the sql code :

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

Here is the test result.

See the manual for all the details about recursive cte.

How to perform graph traversal along multiple paths

Problem Introduction

1 Answers