SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 SQL Server 2005 Forums
 Transact-SQL (2005)
 recursion / expanding networks
 New Topic  Reply to Topic
 Printer Friendly
Next Page
Author Previous Topic Topic Next Topic
Page: of 3

mike123
Flowing Fount of Yak Knowledge

1462 Posts

Posted - 09/13/2007 :  02:40:21  Show Profile  Reply with Quote
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.

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

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


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

SwePeso
Patron Saint of Lost Yaks

Sweden
30117 Posts

Posted - 09/13/2007 :  04:20:48  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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"

Edited by - SwePeso on 09/13/2007 04:52:38
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30117 Posts

Posted - 09/13/2007 :  04:54:10  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

Sweden
30117 Posts

Posted - 09/13/2007 :  05:33:10  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

Sweden
30117 Posts

Posted - 09/13/2007 :  06:33:22  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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"

Edited by - SwePeso on 09/13/2007 07:27:28
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30117 Posts

Posted - 09/13/2007 :  06:44:21  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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
Flowing Fount of Yak Knowledge

1462 Posts

Posted - 09/13/2007 :  15:25:03  Show Profile  Reply with Quote
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

Sweden
30117 Posts

Posted - 09/13/2007 :  15:29:35  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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
Flowing Fount of Yak Knowledge

1462 Posts

Posted - 09/13/2007 :  15:35:03  Show Profile  Reply with Quote
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

Sweden
30117 Posts

Posted - 09/13/2007 :  15:50:18  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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
Flowing Fount of Yak Knowledge

1462 Posts

Posted - 09/13/2007 :  16:46:52  Show Profile  Reply with Quote
sent via sqlteam!, thank you
Go to Top of Page

mike123
Flowing Fount of Yak Knowledge

1462 Posts

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

cheers,
mike123

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

SwePeso
Patron Saint of Lost Yaks

Sweden
30117 Posts

Posted - 09/15/2007 :  02:56:34  Show Profile  Visit SwePeso's Homepage  Reply with Quote
I got it. It's weekend right now



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

mike123
Flowing Fount of Yak Knowledge

1462 Posts

Posted - 09/15/2007 :  05:05:48  Show Profile  Reply with Quote
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

Sweden
30117 Posts

Posted - 09/15/2007 :  17:53:12  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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

Sweden
30117 Posts

Posted - 09/15/2007 :  17:57:22  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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"

Edited by - SwePeso on 09/15/2007 18:29:36
Go to Top of Page

mike123
Flowing Fount of Yak Knowledge

1462 Posts

Posted - 09/15/2007 :  20:15:00  Show Profile  Reply with Quote
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

Sweden
30117 Posts

Posted - 09/16/2007 :  05:17:52  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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
Flowing Fount of Yak Knowledge

1462 Posts

Posted - 09/16/2007 :  16:00:43  Show Profile  Reply with Quote
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

Edited by - mike123 on 09/16/2007 22:58:25
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30117 Posts

Posted - 09/17/2007 :  01:02:42  Show Profile  Visit SwePeso's Homepage  Reply with Quote
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
Flowing Fount of Yak Knowledge

1462 Posts

Posted - 09/17/2007 :  01:25:38  Show Profile  Reply with Quote
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
Page: of 3 Previous Topic Topic Next Topic  
Next Page
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.27 seconds. Powered By: Snitz Forums 2000