I am trying to answer this question by using a breadth-first search from each node of the graph represented by the tables
mapSolarSystemJumps in the data dump at http://community.eveonline.com/community/toolkit.asp (important parts of schema below) in order to find the node with the lowest average edge count to all points on the subgraph of nodes with security >= 0.45.
I managed to hack together this beauty of T-SQL from various tutorials across the web. Sadly, although I managed to get it to function, I am not confident that it is correct. I've never created quite such a complicated piece of SQL before.
At the same time, I would like some assistance with idiomatic T-SQL - looks like CapWords for identifiers,
usp_ for stored procedures,
BEGIN always on new line. I've tried to take the worst offenders out of the first working version of the code at http://gaming.stackexchange.com/a/103876/9760 - things which I can spot. I was able to reduce the execution time to 4:21 minutes from 7:01 minutes in the process.
My priorities are:
- Correctness vetting or fixed
- Readability / Clarity (eg, idomatic)
- Execution speed
CREATE PROCEDURE dbo.usp_Eve_BFS AS BEGIN SET XACT_ABORT ON BEGIN TRAN SET NOCOUNT ON; CREATE TABLE #Result (Id int NOT NULL PRIMARY KEY, Name nvarchar(100), Average int, Maximum int) INSERT INTO #Result (Id, Name) SELECT solarSystemID, solarSystemName FROM mapSolarSystems WHERE security >= 0.45 DECLARE @StartNode int DECLARE c CURSOR FOR SELECT Id FROM #Result OPEN c FETCH NEXT FROM c INTO @StartNode WHILE @@FETCH_STATUS=0 BEGIN CREATE TABLE #Discovered (Id int NOT NULL PRIMARY KEY, Parent int NULL, Depth int) INSERT INTO #Discovered (Id, parent, depth) VALUES (@StartNode, NULL, 0) WHILE @@ROWCOUNT > 0 BEGIN INSERT INTO #Discovered (Id, Parent, Depth) SELECT toSolarSystemID, MAX(fromSolarSystemID), MIN(Depth) + 1 FROM #Discovered d JOIN mapSolarSystemJumps ON d.Id = fromSolarSystemID JOIN #Result ON (mapSolarSystemJumps.toSolarSystemID = #Result.Id) WHERE toSolarSystemID NOT IN (SELECT Id From #Discovered) AND Depth = ( -- make sure the fromSolarSystemID matches the MIN(depth)! SELECT MIN(Depth) FROM #Discovered d JOIN mapSolarSystemJumps ON d.Id = fromSolarSystemID JOIN #Result ON (mapSolarSystemJumps.toSolarSystemID = #Result.Id) WHERE toSolarSystemID NOT IN (SELECT Id From #Discovered) ) GROUP BY toSolarSystemID END; WITH BacktraceCTE(Id, Depth) AS ( SELECT Id, Depth FROM #Discovered d WHERE d.Id = @StartNode UNION ALL SELECT d.Id, d.Depth FROM #Discovered d JOIN BacktraceCTE cte ON d.Parent = cte.Id ) UPDATE #Result SET Average = a.Average, Maximum = a.Maximum FROM (SELECT AVG(Depth) AS Average, MAX(Depth) AS Maximum FROM BacktraceCTE) AS a WHERE #Result.Id = @StartNode DROP TABLE #Discovered FETCH NEXT FROM c INTO @StartNode END SELECT * FROM #Result ORDER BY Average, Maximum; DROP TABLE #Result COMMIT TRAN RETURN 0 END
The basic shape came from http://hansolav.net/sql/graphs.html#bfs.
mapSolarSystems relevant columns:
regionID int constellationID int solarSystemID int solarSystemName nvarchar(100) security float
mapSolarSystems relevant indexes:
mapSolarSystems_IX_constellation nonclustered located on PRIMARY constellationID mapSolarSystems_IX_region nonclustered located on PRIMARY regionID mapSolarSystems_IX_security nonclustered located on PRIMARY security mapSolarSystems_PK clustered, unique, primary key located on PRIMARY solarSystemID
mapSolarSystemJumps relevant columns:
fromRegionID int fromConstellationID int fromSolarSystemID int toSolarSystemID int toConstellationID int toRegionID int
mapSolarSystemJumps relevant indexes:
mapSolarSystemJumps_IX_fromConstellation nonclustered located on PRIMARY fromConstellationID mapSolarSystemJumps_IX_fromRegion nonclustered located on PRIMARY fromRegionID mapSolarSystemJumps_PK clustered, unique, primary key located on PRIMARY fromSolarSystemID, toSolarSystemID