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
    Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources

Articles

Forums

Blogs

Contact Us

About the Site