Peter Larsson Blog

Patron Saint of Lost Yaks

Expand network using CTE without circular reference

by Peter Larsson in  , , ,

Today I come across an interesting approach to a networking algorithm. The question was about how to use recursive to expand a network and still avoid circular reference.
See topic here http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=115290
You can’t do that in a recursive CTE because you can only reference the CTE once in the recursive part. Then I thought about a “recursive csv string”. And I gave it a try.
 
Here is the result.
 
DECLARE @Stations TABLE
      (
            stationID INT,
            name VARCHAR(255)
      )
 
INSERT      @Stations
SELECT      1, 'Glasgow' UNION ALL
SELECT      2, 'Edinburgh' UNION ALL
SELECT      3, 'York' UNION ALL
SELECT      4, 'London' UNION ALL
SELECT      5, 'Aberdeen' UNION ALL
SELECT      6, 'Bjuv'
 
DECLARE @Links TABLE
      (
            fromID INT,
            toID INT
      )
 
INSERT      @Links
SELECT      1, 2 UNION ALL
SELECT      1, 5 UNION ALL
SELECT      1, 3 UNION ALL
SELECT      2, 1 UNION ALL
SELECT      2, 3 UNION ALL
SELECT      3, 1 UNION ALL
SELECT      3, 2 UNION ALL
SELECT      3, 4 UNION ALL
SELECT      4, 3 UNION ALL
SELECT      6, 4 UNION ALL
SELECT      5, 1
 
;WITH paths(stationIDs, pathLength, hopPath, fromID, fromName, toName)
AS (
      SELECT      CAST(stationID AS VARCHAR(MAX)),
            CAST(-1 AS INT),
            CAST(name AS VARCHAR(MAX)),
            stationID,
            CAST(name AS VARCHAR(MAX)),
            CAST(NULL AS VARCHAR(MAX))
      FROM @Stations
 
      UNION ALL
 
      SELECT            p.stationIDs + '/' + CAST(l.toID AS VARCHAR(MAX)),
                  pathLength + 1,
                  p.hopPath + '-' + s.name,
                  l.toID,
                  p.fromName,
                  CAST(s.name AS VARCHAR(MAX))
      FROM        paths AS p
      INNER JOIN @Links AS l ON l.fromID = p.fromID
      INNER JOIN @Stations AS s ON s.stationID = l.toID
      WHERE       '/' + stationIDs + '/' NOT LIKE '%/' + CAST(l.toID AS VARCHAR(MAX)) + '/%'
)
 
SELECT            fromName,
            toName,
            pathLength AS hops,
            hopPath
FROM        paths
WHERE       pathLength >= 0
ORDER BY    fromName,
            toName,
            pathLength
OPTION            (MAXRECURSION 0)
 
If you only want the shortest path between two stations, replace the last SELECT statement with this statement.
 
SELECT            fromName,
            toName,
            hops,
            hopPath
FROM        (
                  SELECT            fromName,
                              toName,
                              pathLength AS hops,
                              hopPath,
                              ROW_NUMBER() OVER (PARTITION BY fromName, toName ORDER BY pathLength) AS recID
                  FROM        paths
                  WHERE       pathLength >= 0
            ) AS d
WHERE       recID = 1
ORDER BY    fromName,
            toName
OPTION            (MAXRECURSION 0)