Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

 All Forums
 SQL Server 2005 Forums
 Transact-SQL (2005)
 recursion / expanding networks

Author  Topic 

mike123
Master Smack Fu Yak Hacker

1462 Posts

Posted - 2007-09-13 : 02:40:21
Hi,

I'm attemping to create a query that shows how users are connected to other users thru their friends list. (Degrees of seperation) I'm not sure what the best approach is, and I have seen some pretty advanced stuff in these threads.


What I need brought back is each invididual user in the connection. For example if I was looking at user "bob"

Bob is connected to you via Bill -> Jennifer -> Max -> Lisa

If anyone can point me in the direction of what to do it would be greatly appreciated!


thanks for any help!! :)

mike123

The simple table structure of "tblFriends"



CREATE TABLE [dbo].[tblFriends](
[UserID] [int] NOT NULL,
[FriendID] [int] NOT NULL,

[dateAdded] [smalldatetime] )



Some references below:

I found this thread and did some reading on "expanding networks",it seems to be most exact description of what I am looking for, but there doesnt seem to be any code.

[url]http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=32729[/url]

This stuff below gets pretty complicated, but looks very interesting! I've attempted to install all the functions on my box, but as of right now the queries are taking a huge amount of time, I'm still checking my integration etc... (One query I stopped after 16 minutes execution) I have about 500k rows in this "tblFriends" table


[url]http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=72097[/url]

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-09-13 : 04:20:48
You should have read the complete thread (http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=72097).
-- Prepare sample data
DECLARE @Contacts TABLE (pFrom VARCHAR(2), pTo VARCHAR(2))

INSERT @Contacts
SELECT 'A', 'B' UNION ALL
SELECT 'B', 'D' UNION ALL
SELECT 'C', 'A' UNION ALL
SELECT 'C', 'E' UNION ALL
SELECT 'G', 'C' UNION ALL
SELECT 'B', 'G' UNION ALL
SELECT 'F', 'D' UNION ALL
SELECT 'E', 'F'
/*
A - B
/ / \
C - G D
\ /
E - F
*/

-- Initialize search parameters

DECLARE @StartNode VARCHAR(2),
@EndNode VARCHAR(2),
@Iteration INT,
@LastRowID INT

SELECT @StartNode = 'e',
@EndNode = 'g',
@Iteration = 0,
@LastRowID = 0

-- Create staging tables
DECLARE @Tracks TABLE (oldTrack INT, newTrack INT, pFrom VARCHAR(2), pTo VARCHAR(2))
DECLARE @Stage TABLE (Iteration INT, Track INT, pFrom VARCHAR(2), pTo VARCHAR(2), RowID INT IDENTITY(1, 1))

-- Insert starting points
INSERT @Stage
(
Iteration,
Track,
pFrom,
pTo
)
SELECT 0,
ROW_NUMBER() OVER (ORDER BY pFrom),
pFrom,
pTo
FROM (
SELECT pFrom,
pTo
FROM @Contacts
WHERE pFrom = @StartNode

UNION ALL

SELECT pTo,
pFrom
FROM @Contacts
WHERE pTo = @StartNode
) AS x

INSERT @Stage
(
Iteration,
Track,
pFrom,
pTo
)
SELECT -1,
Track,
pFrom,
pFrom
FROM @Stage
WHERE Iteration = 0

WHILE SCOPE_IDENTITY() > @LastRowID
BEGIN
SELECT @Iteration = @Iteration + 1,
@LastRowID = SCOPE_IDENTITY()

DELETE FROM @Tracks

INSERT @Tracks
(
oldTrack,
newTrack,
pFrom,
pTo
)
SELECT p.Track AS oldTrack,
p.Track + ROW_NUMBER() OVER (PARTITION BY p.Track ORDER BY c.pTo) - 1 AS newTrack,
c.pFrom,
c.pTo
FROM (
SELECT pFrom,
pTo
FROM @Contacts

UNION ALL

SELECT pTo,
pFrom
FROM @Contacts
) AS c
INNER JOIN (
SELECT Track,
pTo
FROM @Stage
WHERE Iteration = @Iteration - 1
) AS p ON p.pTo = c.pFrom
WHERE c.pFrom <> @EndNode
AND NOT EXISTS (SELECT * FROM @Stage AS s WHERE s.pFrom = c.pTo)

INSERT @Stage
(
Iteration,
Track,
pFrom,
pTo
)
SELECT @Iteration,
oldTrack,
pFrom,
pTo
FROM @Tracks
WHERE oldTrack = newTrack


INSERT @Stage
(
Iteration,
Track,
pFrom,
pTo
)
SELECT s.Iteration,
t.newTrack,
s.pFrom,
s.pTo
FROM @Tracks AS t
INNER JOIN @Stage AS s ON s.Track = t.oldTrack
WHERE t.oldTrack <> t.newTrack
AND s.Iteration < @Iteration

UNION ALL

SELECT @Iteration,
newTrack,
pFrom,
pTo
FROM @Tracks
WHERE oldTrack <> newTrack
END

-- Show the expected output
SELECT ROW_NUMBER() OVER (ORDER BY LEN(Path), Track) AS Track,
REPLACE(Path, '#', ' -> ') AS Path
FROM (
SELECT DISTINCT s1.Track,
STUFF((SELECT TOP 100 PERCENT '#' + s2.pTo FROM @Stage AS s2 WHERE s2.Track = s1.Track ORDER BY s2.Iteration FOR XML PATH('')), 1, 1, '') AS Path
FROM @Stage AS s1
) AS u
ORDER BY LEN(Path),
Track


E 12°55'05.25"
N 56°04'39.16"
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-09-13 : 04:54:10
Output from above sample code is
Track	Path
----- ---------------------
1 E -> C -> G
2 E -> F -> D -> B -> G
3 E -> C -> A -> B -> G



E 12°55'05.25"
N 56°04'39.16"
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-09-13 : 05:33:10
Or do you only want one path, the shortest?



E 12°55'05.25"
N 56°04'39.16"
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-09-13 : 06:33:22
This solution is fast even for 500,000 members
CREATE PROCEDURE dbo.uspDijkstraResolve
(
@FromNodeName VARCHAR(10),
@ToNodeName VARCHAR(10),
@ReturnAsResultset TINYINT = 0
)
AS

SET NOCOUNT ON

-- Initialize variables
DECLARE @FromNodeID INT,
@ToNodeID INT,
@NodeID INT,
@Cost INT,
@PathID INT

-- Create staging table for all nodes
CREATE TABLE #Nodes
(
NodeID INT IDENTITY (1, 1) PRIMARY KEY CLUSTERED,
NodeName VARCHAR(20),
Cost INT,
PathID INT,
Calculated TINYINT
)

-- Stage all nodes
INSERT #Nodes
(
NodeName,
Calculated
)
SELECT pFrom,
0
FROM tblFriends

UNION

SELECT pTo,
0
FROM tblFriends

--Check to see if FromNode exists
SELECT @FromNodeID = NodeID,
@NodeID = NodeID
FROM #Nodes
WHERE NodeName = @FromNodeName

IF @FromNodeID IS NULL
BEGIN
SET @FromNodeName = ISNULL(@FromNodeName, '')

RAISERROR ('From nodename ''%s'' can not be found.', 16, 1, @FromNodeName)
RETURN
END

--Check to see if ToNode exists
SELECT @ToNodeID = NodeID
FROM #Nodes
WHERE NodeName = @ToNodeName

IF @ToNodeID IS NULL
BEGIN
SET @ToNodeName = ISNULL(@ToNodeName, '')

RAISERROR ('To nodename ''%s'' can not be found.', 16, 1, @ToNodeName)
RETURN
END

-- Create staging table for all paths
CREATE TABLE #Paths
(
PathID INT IDENTITY (1, 1) PRIMARY KEY CLUSTERED,
FromNodeID INT,
ToNodeID INT,
Cost INT
)

-- Stage all paths
INSERT #Paths
(
FromNodeID,
ToNodeID,
Cost
)
SELECT nFrom.NodeID,
nTo.NodeID,
c.Cost
FROM (
SELECT pFrom,
pTo,
1 AS Cost
FROM tblFriends

UNION

SELECT pTo,
pFrom,
1
FROM tblFriends
) AS c
INNER JOIN #Nodes AS nFrom ON nFrom.NodeName = c.pFrom
INNER JOIN #Nodes AS nTo ON nTo.NodeName = c.pTo

UPDATE #Nodes
SET Cost = 0
WHERE NodeID = @FromNodeID

WHILE @NodeID IS NOT NULL
BEGIN
UPDATE ToNodes
SET ToNodes.Cost = CASE
WHEN ToNodes.Cost IS NULL THEN FromNodes.Cost + Paths.Cost
WHEN FromNodes.Cost + Paths.Cost < ToNodes.Cost THEN FromNodes.Cost + Paths.Cost
ELSE ToNodes.Cost
END,
ToNodes.PathID = Paths.PathID
FROM #Nodes AS FromNodes
INNER JOIN #Paths AS Paths ON Paths.FromNodeID = FromNodes.NodeID
INNER JOIN #Nodes AS ToNodes ON ToNodes.NodeID = Paths.ToNodeID
WHERE FromNodes.NodeID = @NodeID
AND (ToNodes.Cost IS NULL OR FromNodes.Cost + Paths.Cost < ToNodes.Cost)
AND ToNodes.Calculated = 0

UPDATE FromNodes
SET FromNodes.Calculated = 1
FROM #Nodes AS FromNodes
WHERE FromNodes.NodeID = @NodeID

SET @NodeID = NULL

SELECT TOP 1 @NodeID = Nodes.NodeID
FROM #Nodes AS Nodes
WHERE Nodes.Calculated = 0
AND Nodes.Cost IS NOT NULL
ORDER BY Nodes.Cost
END

CREATE TABLE #Map
(
RowID INT IDENTITY(-1, -1),
FromNodeName VARCHAR(10),
ToNodeName VARCHAR(10),
Cost INT
)

IF EXISTS (SELECT * FROM #Nodes WHERE NodeID = @ToNodeID AND Cost IS NULL)
BEGIN
SELECT FromNodeName,
ToNodeName,
Cost
FROM #Map

RETURN
END

WHILE @FromNodeID <> @ToNodeID
BEGIN
SELECT @FromNodeName = FromNodes.NodeName,
@ToNodeName = ToNodes.NodeName,
@Cost = ToNodes.Cost,
@PathID = ToNodes.PathID
FROM #Nodes AS ToNodes
INNER JOIN #Paths AS Paths ON Paths.PathID = ToNodes.PathID
INNER JOIN #Nodes AS FromNodes ON FromNodes.NodeID = Paths.FromNodeID
WHERE ToNodes.NodeID = @ToNodeID

INSERT #Map
(
FromNodeName,
ToNodeName,
Cost
)
SELECT @FromNodeName,
@ToNodeName,
@Cost

SELECT @ToNodeID = Paths.FromNodeID
FROM #Paths AS Paths
WHERE Paths.PathID = @PathID
END

INSERT #Map
(
FromNodeName,
ToNodeName,
Cost
)
SELECT FromNodeName,
FromNodeName,
0
FROM #Map
WHERE RowID = SCOPE_IDENTITY()

IF @ReturnAsResultset = 1
SELECT FromNodeName,
ToNodeName,
Cost
FROM #Map
WHERE RowID > SCOPE_IDENTITY()
ORDER BY RowID
ELSE
SELECT REPLACE(STUFF( (
SELECT TOP 100 PERCENT
CHAR(7) + m.ToNodeName
FROM #Map AS m
ORDER BY m.RowID
FOR XML PATH('')
)
, 1, 6, '')
, '#x07;', ' -> ') AS Path

E 12°55'05.25"
N 56°04'39.16"
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-09-13 : 06:44:21
If you have noticed, I also have added a "cost", which can be translated as "how well do they know eachother".

For example

1) Family (low cost)
2) Classmate (middle cost)
3) Know of (high cost)



E 12°55'05.25"
N 56°04'39.16"
Go to Top of Page

mike123
Master Smack Fu Yak Hacker

1462 Posts

Posted - 2007-09-13 : 15:25:03
quote:
Originally posted by Peso

Or do you only want one path, the shortest?



Either all the paths, or just the shortest path are both great solutions for me. I am assuming that performance is going to be very similar.

Thanks! :)
mike123
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-09-13 : 15:29:35
No, all paths will be sending your server to a crawl. Because ALL paths are calculated.
Try the solution posted 09/13/2007 : 06:33:22 and post back what you think.



E 12°55'05.25"
N 56°04'39.16"
Go to Top of Page

mike123
Master Smack Fu Yak Hacker

1462 Posts

Posted - 2007-09-13 : 15:35:03
Hi Peso,

I am attempting to integrate your suggestions on the following SPROC. I have come up with the following modifications, since I am working with INT columns rather than what was posted.

I've let this code run against my table and I just stopped it after 12 minutes. You said this should run fast, and I'm sure its probably an error on my end, but I'm not sure what types of results to expect. There are about 500k rows in the friends table.

Does anything stick out on this SPROC as completely wrong ?

1.) Basically I changed all the VarChar columns to INT's
2.) I changed the parameters to a more appropriate name for this installation.
3.) I changed the pFrom to friendID and pTo to userID

Thanks very much for your help!! I am very excited at the possibility of getting this running smoothly




ALTER PROCEDURE dbo.uspDijkstraResolve
(
@FromNode_userID INT,
@ToNode_userID INT,
@ReturnAsResultset TINYINT = 0
)
AS

SET NOCOUNT ON

-- Initialize variables
DECLARE @FromNodeID INT,
@ToNodeID INT,
@NodeID INT,
@Cost INT,
@PathID INT

-- Create staging table for all nodes
CREATE TABLE #Nodes
(
NodeID INT IDENTITY (1, 1) PRIMARY KEY CLUSTERED,
NodeName INT,
Cost INT,
PathID INT,
Calculated TINYINT
)

-- Stage all nodes
INSERT #Nodes
(
NodeName,
Calculated
)
SELECT friendID,
0
FROM tblFriends

UNION

SELECT userID,
0
FROM tblFriends

--Check to see if FromNode exists
SELECT @FromNodeID = NodeID,
@NodeID = NodeID
FROM #Nodes
WHERE NodeName = @FromNode_userID

IF @FromNodeID IS NULL
BEGIN
--SET @FromNode_userID = ISNULL(@FromNode_userID, '')
SET @FromNode_userID = ISNULL(@FromNode_userID, 0)

RAISERROR ('From nodename ''%s'' can not be found.', 16, 1, @FromNode_userID)
RETURN
END

--Check to see if ToNode exists
SELECT @ToNodeID = NodeID
FROM #Nodes
WHERE NodeName = @ToNode_userID

IF @ToNodeID IS NULL
BEGIN
--SET @ToNode_userID = ISNULL(@ToNode_userID, '')
SET @ToNode_userID = ISNULL(@ToNode_userID, 0)

RAISERROR ('To nodename ''%s'' can not be found.', 16, 1, @ToNode_userID)
RETURN
END

-- Create staging table for all paths
CREATE TABLE #Paths
(
PathID INT IDENTITY (1, 1) PRIMARY KEY CLUSTERED,
FromNodeID INT,
ToNodeID INT,
Cost INT
)

-- Stage all paths
INSERT #Paths
(
FromNodeID,
ToNodeID,
Cost
)
SELECT nFrom.NodeID,
nTo.NodeID,
c.Cost
FROM (
SELECT friendID,
userID,
1 AS Cost
FROM tblFriends

UNION

SELECT userID,
friendID,
1
FROM tblFriends
) AS c
INNER JOIN #Nodes AS nFrom ON nFrom.NodeName = c.friendID
INNER JOIN #Nodes AS nTo ON nTo.NodeName = c.userID

UPDATE #Nodes
SET Cost = 0
WHERE NodeID = @FromNodeID

WHILE @NodeID IS NOT NULL
BEGIN
UPDATE ToNodes
SET ToNodes.Cost = CASE
WHEN ToNodes.Cost IS NULL THEN FromNodes.Cost + Paths.Cost
WHEN FromNodes.Cost + Paths.Cost < ToNodes.Cost THEN FromNodes.Cost + Paths.Cost
ELSE ToNodes.Cost
END,
ToNodes.PathID = Paths.PathID
FROM #Nodes AS FromNodes
INNER JOIN #Paths AS Paths ON Paths.FromNodeID = FromNodes.NodeID
INNER JOIN #Nodes AS ToNodes ON ToNodes.NodeID = Paths.ToNodeID
WHERE FromNodes.NodeID = @NodeID
AND (ToNodes.Cost IS NULL OR FromNodes.Cost + Paths.Cost < ToNodes.Cost)
AND ToNodes.Calculated = 0

UPDATE FromNodes
SET FromNodes.Calculated = 1
FROM #Nodes AS FromNodes
WHERE FromNodes.NodeID = @NodeID

SET @NodeID = NULL

SELECT TOP 1 @NodeID = Nodes.NodeID
FROM #Nodes AS Nodes
WHERE Nodes.Calculated = 0
AND Nodes.Cost IS NOT NULL
ORDER BY Nodes.Cost
END

CREATE TABLE #Map
(
RowID INT IDENTITY(-1, -1),
FromNodeName INT,
ToNodeName INT,
Cost INT
)

IF EXISTS (SELECT * FROM #Nodes WHERE NodeID = @ToNodeID AND Cost IS NULL)
BEGIN
SELECT FromNodeName,
ToNodeName,
Cost
FROM #Map

RETURN
END

WHILE @FromNodeID <> @ToNodeID
BEGIN
SELECT @FromNode_userID = FromNodes.NodeName,
@ToNode_userID = ToNodes.NodeName,
@Cost = ToNodes.Cost,
@PathID = ToNodes.PathID
FROM #Nodes AS ToNodes
INNER JOIN #Paths AS Paths ON Paths.PathID = ToNodes.PathID
INNER JOIN #Nodes AS FromNodes ON FromNodes.NodeID = Paths.FromNodeID
WHERE ToNodes.NodeID = @ToNodeID

INSERT #Map
(
FromNodeName,
ToNodeName,
Cost
)
SELECT @FromNode_userID,
@ToNode_userID,
@Cost

SELECT @ToNodeID = Paths.FromNodeID
FROM #Paths AS Paths
WHERE Paths.PathID = @PathID
END

INSERT #Map
(
FromNodeName,
ToNodeName,
Cost
)
SELECT FromNodeName,
FromNodeName,
0
FROM #Map
WHERE RowID = SCOPE_IDENTITY()

IF @ReturnAsResultset = 1
SELECT FromNodeName,
ToNodeName,
Cost
FROM #Map
WHERE RowID > SCOPE_IDENTITY()
ORDER BY RowID
ELSE
SELECT REPLACE(STUFF( (
SELECT TOP 100 PERCENT
CHAR(7) + m.ToNodeName
FROM #Map AS m
ORDER BY m.RowID
FOR XML PATH('')
)
, 1, 6, '')
, '#x07;', ' -> ') AS Path


Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-09-13 : 15:50:18
Export the tblFriends table (only relevant columns as userid and friendid).
Zip the CSV file and mail it to me.




E 12°55'05.25"
N 56°04'39.16"
Go to Top of Page

mike123
Master Smack Fu Yak Hacker

1462 Posts

Posted - 2007-09-13 : 16:46:52
sent via sqlteam!, thank you
Go to Top of Page

mike123
Master Smack Fu Yak Hacker

1462 Posts

Posted - 2007-09-14 : 17:50:25
I have hosted a CSV of the friends table here, in case sqlteam mail didnt get thru. Thanks again very much appreciated !! :)

cheers,
mike123

[url]http://www.mediafire.com/?8mddstxmbx0[/url]
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-09-15 : 02:56:34
I got it. It's weekend right now



E 12°55'05.25"
N 56°04'39.16"
Go to Top of Page

mike123
Master Smack Fu Yak Hacker

1462 Posts

Posted - 2007-09-15 : 05:05:48
quote:
Originally posted by Peso

I got it. It's weekend right now



Have a great weekend my friend !

cheers,
mike123
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-09-15 : 17:53:12
1) Make a UNIQUE index over {userID, friendID}.
2) Add an IDENTITY column PathID with an UNIQUE CLUSTERED index.



E 12°55'05.25"
N 56°04'39.16"
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-09-15 : 17:57:22
[code]CREATE PROCEDURE dbo.uspDijkstraResolve
(
@FromID INT,
@ToID INT,
@ReturnAsResultset TINYINT = 0
)
AS

SET NOCOUNT ON

-- Initialize variables
DECLARE @NodeID INT,
@Cost INT,
@PathID INT

-- Create staging table for all nodes
CREATE TABLE #Nodes
(
NodeID INT PRIMARY KEY CLUSTERED,
Cost INT,
PathID INT,
Calculated TINYINT
)

-- Stage all nodes
INSERT #Nodes
(
NodeID,
Calculated
)
SELECT DISTINCT userID,
0
FROM tblFriends

--Check to see if FromNode exists
IF NOT EXISTS (SELECT * FROM #Nodes WHERE NodeID = @FromID)
BEGIN
RAISERROR ('FromID ''%d'' can not be found.', 16, 1, @FromID)
RETURN
END

--Check to see if ToNode exists
IF NOT EXISTS (SELECT * FROM #Nodes WHERE NodeID = @ToID)
BEGIN
RAISERROR ('To nodename ''%d'' can not be found.', 16, 1, @ToID)
RETURN
END

UPDATE #Nodes
SET Cost = 0
WHERE NodeID = @FromID

SET @NodeID = @FromID

WHILE @NodeID IS NOT NULL
BEGIN
UPDATE ToNodes
SET ToNodes.Cost = CASE
WHEN ToNodes.Cost IS NULL THEN FromNodes.Cost + 1
WHEN FromNodes.Cost + 1 < ToNodes.Cost THEN FromNodes.Cost + 1
ELSE ToNodes.Cost
END,
ToNodes.PathID = Paths.PathID
FROM #Nodes AS FromNodes
INNER JOIN tblFriends AS Paths ON Paths.userID = FromNodes.NodeID
INNER JOIN #Nodes AS ToNodes ON ToNodes.NodeID = Paths.friendID
WHERE FromNodes.NodeID = @NodeID
AND (ToNodes.Cost IS NULL OR FromNodes.Cost + 1 < ToNodes.Cost)
AND ToNodes.Calculated = 0

UPDATE FromNodes
SET FromNodes.Calculated = 1
FROM #Nodes AS FromNodes
WHERE FromNodes.NodeID = @NodeID

SET @NodeID = NULL

SELECT TOP 1 @NodeID = Nodes.NodeID
FROM #Nodes AS Nodes
WHERE Nodes.Calculated = 0
AND Nodes.Cost IS NOT NULL
ORDER BY Nodes.Cost

IF @NodeID = @ToID
SET @NodeID = NULL
END

CREATE TABLE #Map
(
RowID INT IDENTITY(1, 1),
FromNodeID INT,
ToNodeID INT
)

IF EXISTS (SELECT * FROM #Nodes WHERE NodeID = @ToID AND Cost IS NULL)
BEGIN
SELECT FromNodeID,
ToNodeID
FROM #Map

RETURN
END

WHILE @FromID <> @ToID
BEGIN
SELECT @PathID = ToNodes.PathID
FROM #Nodes AS ToNodes
INNER JOIN tblFriends AS Paths ON Paths.PathID = ToNodes.PathID
INNER JOIN #Nodes AS FromNodes ON FromNodes.NodeID = Paths.userID
WHERE ToNodes.NodeID = @ToID

INSERT #Map
(
FromNodeID,
ToNodeID
)
SELECT @ToID,
@FromID

SELECT @FromID = @ToID,
@ToID = Paths.userID
FROM tblFriends AS Paths
WHERE Paths.PathID = @PathID
END

IF @ReturnAsResultset = 1
SELECT FromNodeID,
ToNodeID
FROM #Map
WHERE RowID > 1
ORDER BY RowID DESC
ELSE
SELECT REPLACE(STUFF( (
SELECT TOP 100 PERCENT
CHAR(7) + CONVERT(VARCHAR, m.FromNodeID)
FROM #Map AS m
ORDER BY m.RowID DESC
FOR XML PATH('')
)
, 1, 6, '')
, '& # x 0 7 ;', ' -> ') AS Path -- No spaces between "& # x 0 7 ;" I only posted them that way because of forum filtering[/code]
E 12°55'05.25"
N 56°04'39.16"
Go to Top of Page

mike123
Master Smack Fu Yak Hacker

1462 Posts

Posted - 2007-09-15 : 20:15:00
Hi Peso,

I've tried to debug this myself, but currently unable to figure out exactly how to modify this.
I don't want to get it working incorrectly either. Any idea what this error might be ?

The line is in bold below.


Thank you very very much!! :)
mike123


Server: Msg 207, Level 16, State 1, Procedure uspDijkstraResolve, Line 123
Invalid column name 'PathID'.


quote:
Originally posted by Peso

CREATE PROCEDURE dbo.uspDijkstraResolve
(
@FromID INT,
@ToID INT,
@ReturnAsResultset TINYINT = 0
)
AS

SET NOCOUNT ON

-- Initialize variables
DECLARE @NodeID INT,
@Cost INT,
@PathID INT

-- Create staging table for all nodes
CREATE TABLE #Nodes
(
NodeID INT PRIMARY KEY CLUSTERED,
Cost INT,
PathID INT,
Calculated TINYINT
)

-- Stage all nodes
INSERT #Nodes
(
NodeID,
Calculated
)
SELECT DISTINCT userID,
0
FROM tblFriends

--Check to see if FromNode exists
IF NOT EXISTS (SELECT * FROM #Nodes WHERE NodeID = @FromID)
BEGIN
RAISERROR ('FromID ''%d'' can not be found.', 16, 1, @FromID)
RETURN
END

--Check to see if ToNode exists
IF NOT EXISTS (SELECT * FROM #Nodes WHERE NodeID = @ToID)
BEGIN
RAISERROR ('To nodename ''%d'' can not be found.', 16, 1, @ToID)
RETURN
END

UPDATE #Nodes
SET Cost = 0
WHERE NodeID = @FromID

SET @NodeID = @FromID

WHILE @NodeID IS NOT NULL
BEGIN
UPDATE ToNodes
SET ToNodes.Cost = CASE
WHEN ToNodes.Cost IS NULL THEN FromNodes.Cost + 1
WHEN FromNodes.Cost + 1 < ToNodes.Cost THEN FromNodes.Cost + 1
ELSE ToNodes.Cost
END,
ToNodes.PathID = Paths.PathID
FROM #Nodes AS FromNodes
INNER JOIN tblFriends AS Paths ON Paths.userID = FromNodes.NodeID
INNER JOIN #Nodes AS ToNodes ON ToNodes.NodeID = Paths.friendID
WHERE FromNodes.NodeID = @NodeID
AND (ToNodes.Cost IS NULL OR FromNodes.Cost + 1 < ToNodes.Cost)
AND ToNodes.Calculated = 0

UPDATE FromNodes
SET FromNodes.Calculated = 1
FROM #Nodes AS FromNodes
WHERE FromNodes.NodeID = @NodeID

SET @NodeID = NULL

SELECT TOP 1 @NodeID = Nodes.NodeID
FROM #Nodes AS Nodes
WHERE Nodes.Calculated = 0
AND Nodes.Cost IS NOT NULL
ORDER BY Nodes.Cost

IF @NodeID = @ToID
SET @NodeID = NULL
END

CREATE TABLE #Map
(
RowID INT IDENTITY(1, 1),
FromNodeID INT,
ToNodeID INT
)

IF EXISTS (SELECT * FROM #Nodes WHERE NodeID = @ToID AND Cost IS NULL)
BEGIN
SELECT FromNodeID,
ToNodeID
FROM #Map

RETURN
END

WHILE @FromID <> @ToID
BEGIN
SELECT @PathID = ToNodes.PathID
FROM #Nodes AS ToNodes
INNER JOIN tblFriends AS Paths ON Paths.PathID = ToNodes.PathID
INNER JOIN #Nodes AS FromNodes ON FromNodes.NodeID = Paths.userID
WHERE ToNodes.NodeID = @ToID

INSERT #Map
(
FromNodeID,
ToNodeID
)
SELECT @ToID,
@FromID

SELECT @FromID = @ToID,
@ToID = Paths.userID
FROM tblFriends AS Paths
WHERE Paths.PathID = @PathID
END

IF @ReturnAsResultset = 1
SELECT FromNodeID,
ToNodeID
FROM #Map
WHERE RowID > 1
ORDER BY RowID DESC
ELSE
SELECT REPLACE(STUFF( (
SELECT TOP 100 PERCENT
CHAR(7) + CONVERT(VARCHAR, m.FromNodeID)
FROM #Map AS m
ORDER BY m.RowID DESC
FOR XML PATH('')
)
, 1, 6, '')
, '& # x 0 7 ;', ' -> ') AS Path -- No spaces between "& # x 0 7 ;" I only posted them that way because of forum filtering

E 12°55'05.25"
N 56°04'39.16"


Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-09-16 : 05:17:52
You table tblFriens do need a PathID column, preferrably the IDENTITY column of that table. It has to be unique.




E 12°55'05.25"
N 56°04'39.16"
Go to Top of Page

mike123
Master Smack Fu Yak Hacker

1462 Posts

Posted - 2007-09-16 : 16:00:43
Hi Peso,

Ok, I just added an IDENTITY column, and got it working. I am guessing I should probably tune the indexes now?

Also I wondering what the best way to fix this error I am getting when I run against 2 nodes that don't connect. For example


Server: Msg 50000, Level 16, State 1, Procedure uspDijkstraResolve, Line 45
To nodename '500' can not be found.


Also I am wondering how difficult it would be to bring back the results in multiple rows (one for each step) Reason being is that I would like to do a JOIN and bring back the users name as well.

Your thoughts and help much appreciated!

Thanks very much :)
mike123
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2007-09-17 : 01:02:42
1) There is an option fot that! Change the default third parameter to 1 instead of missing/null/non-1.
2) If two nodes can't connect you get an empty resultset back.
3) The error you get is that the person/node you start with, can't be found at all.



E 12°55'05.25"
N 56°04'39.16"
Go to Top of Page

mike123
Master Smack Fu Yak Hacker

1462 Posts

Posted - 2007-09-17 : 01:25:38
Hey Peso,

1.) I didnt realize that, works perfectly will attempt the JOIN modification now :)

2/3.) By design, not all users have entries in "tblFriends", so I believe that I might be encountering this error by design. I'll see if I can prevent this situation from executing in the web tier, otherwise maybe I will have to integrate it with the main "Users" table ? I'll do more testing first.

4.) I have 500k rows, I just executed a search and it took 3 minutes and 33 seconds, and it brought back 5 degrees of relations. What type of performance do you think I should be expecting ? I'm guessing some index adjustment needs to be made now that I added a new IDENTITY column.

5.) Do you think there are any optimizations I can do inside the query to make any decent difference ? Mainly I am thinking of stripping functionality that I wont use ( the weight part, multiple return type options) but I'm not sure how significant of a difference that would make.


Thanks once again for your continued support!

mike123
Go to Top of Page
  Previous Page&nsp;  Next Page

- Advertisement -