SQL Recursive CTE Graph Traversal

Question

I have a table that contains small groups of related nodes. I would like to be able to identify all the nodes that are related.

-- Example of some small related nodes.
--         (14)   (5) (8)    (10) (3)
--         /        \   \      \  /
--  (11)-(2)       (12)-(9)    (7)
--         \        /          /  \
--         (4)    (6)        (1)  (13) 

DECLARE @Graph TABLE  (
    A SmallInt NOT NULL,
    B SmallInt NOT NULL
)

INSERT INTO @Graph (A, B)
VALUES 
    (11,  2), ( 2, 14), ( 2,  4), ( 5, 12),
    ( 6, 12), ( 12, 9), ( 8,  9), (10,  7),
    ( 1,  7), ( 7, 13), ( 7,  3);

Desired Result

1, 13
2, 14
3, 13
4, 14
5, 12
6, 12
7, 13
8, 12
9, 12
10, 13
11, 14
12, 12
13, 13
14, 14

CTE That gets close to the correct answer, but not quite.

WITH Src AS (
    SELECT A, B FROM @Graph
)
, Recurse (A, B) AS (
    SELECT A, B FROM Src
    UNION ALL
    SELECT S.A, R.B FROM Src S INNER JOIN Recurse R ON S.B = R.A 
)
, List AS (
    SELECT A, B FROM Recurse 
    UNION SELECT A, A FROM Src
    UNION SELECT B, B FROM Src
)
SELECT A, MAX(B) B FROM List GROUP BY A ORDER BY 1, 2;

Query Result

1, 13
2, 14
3, 3 <- Wrong result
4, 4 <- Wrong result
5, 12
6, 12
7, 13
8, 9 <- Wrong result
9, 9 <- Wrong result
10, 13
11, 14
12, 12
13, 13
14, 14

I decided to use the MAX node number to relate the nodes together, but some other method would be acceptable.

This is a lot harder than it seems in SQL Server. Please read https://stackoverflow.com/questions/35254260/how-to-find-all-connected-subgraphs-of-an-undirected-graph and https://stackoverflow.com/questions/50619401/how-to-group-hierarchical-relationships-together-in-sql-server — EzLo, Sep 24 '19 at 13:29
SQL Server 2017+ also implemented support for Graphs, with special nodes and edge tables. Unfortunately I'm not experienced with it, but might be worth a read. https://learn.microsoft.com/en-us/sql/relational-databases/graphs/sql-graph-architecture?view=sql-server-2017 — EzLo, Sep 24 '19 at 13:34
Your problem isn't clear enough : (12,12),(13,13),(14,14),(5,12), .... shouldn't be in the output as related (of course relating to your description of the problem). Also I think what you're modeling and what you actually want/have isn't the same. The model you drew isn't reflected by your `@Graph` table. Either a node is a structure having one integer (like the model) and then you have to model the relationship between nodes or a node is a structure having two integers and one of them could an element in multiple nodes then you have redesign your problem. — Fourat, Sep 24 '19 at 13:49
The model above is a list of nodes. The table @Graph contains relationships (edges) between the nodes. I want a list of the nodes that are related. Using the desired result I can group all the nodes that are related by the 2nd value in the result. (12, 12) would mean that node 12 is in the group identified as 12, along with nodes 5, 6, 8, 9. Perhaps it would have been more clear if I had stated I would like a list of related nodes (5, 6, 8, 9, 12), (2, 4, 11, 14), & (1, 3, 7, 10, 13). I decided to use the MAX node number to relate the nodes together, but some other method would be acceptable. — Brian Bates, Sep 24 '19 at 14:19

score 2 · Answer 1 · answered Sep 24 '19 at 14:56

EzLo has to get credit for leading me to another post (How to find all connected subgraphs of an undirected graph) that allowed me to compose the correct answer.

DECLARE @Graph TABLE  (
    A SmallInt NOT NULL,
    B SmallInt NOT NULL
)

INSERT INTO @Graph (A, B)
VALUES 
    (11,  2), ( 2, 14), ( 2,  4), ( 5, 12),
    ( 6, 12), ( 12, 9), ( 8,  9), (10,  7),
    ( 1,  7), ( 7, 13), ( 7,  3);


WITH CTE_Idents AS (
    SELECT A AS Ident FROM @Graph
    UNION SELECT B AS Ident FROM @Graph
)
, CTE_Pairs AS (
    SELECT A AS Ident1, B AS Ident2 FROM @Graph WHERE A <> B
    UNION SELECT B AS Ident1, A AS Ident2 FROM @Graph WHERE A <> B
)
, CTE_Recursive AS (
    SELECT
        CTE_Idents.Ident AS AnchorIdent,
        Ident1,
        Ident2,
        CAST(',' + CAST(Ident1 AS VARCHAR(2)) + ',' + CAST(Ident2 AS VARCHAR(2)) + ',' AS varchar(8000)) AS IdentPath
    FROM 
            CTE_Pairs
        INNER JOIN 
            CTE_Idents 
                ON CTE_Idents.Ident = CTE_Pairs.Ident1

    UNION ALL

    SELECT 
        CTE_Recursive.AnchorIdent, 
        CTE_Pairs.Ident1, 
        CTE_Pairs.Ident2, 
        CAST(CTE_Recursive.IdentPath + CAST(CTE_Pairs.Ident2 AS VARCHAR(2)) + ',' AS varchar(8000)) AS IdentPath
    FROM
            CTE_Pairs
        INNER JOIN 
            CTE_Recursive 
                ON CTE_Recursive.Ident2 = CTE_Pairs.Ident1
    WHERE
        CTE_Recursive.IdentPath NOT LIKE CAST('%,' + CAST(CTE_Pairs.Ident2 AS VARCHAR(2)) + ',%' AS varchar(8000))
)
, CTE_RecursionResult AS (
    SELECT AnchorIdent, Ident1, Ident2 FROM CTE_Recursive
)
, CTE_CleanResult AS (
    SELECT AnchorIdent, Ident1 AS Ident FROM CTE_RecursionResult
    UNION SELECT AnchorIdent, Ident2 AS Ident FROM CTE_RecursionResult
)
SELECT AnchorIdent, MAX(Ident) AS Ident FROM CTE_CleanResult GROUP BY AnchorIdent ORDER BY AnchorIdent

SQL Recursive CTE Graph Traversal

Desired Result

CTE That gets close to the correct answer, but not quite.

Query Result

1 Answers1