# Thinking outside the box

Patron Saint of Lost Yaks
posts - 203, comments - 734, trackbacks - 4

## Expand network using CTE without circular reference

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'

(
fromID INT,
toID INT
)

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)

Print | posted on Thursday, November 27, 2008 4:00 PM | Filed Under [ Optimization SQL Server 2008 Algorithms SQL Server 2005 ]

Comments have been closed on this topic.