In a network, an item can have more than one superior. For example, the following data is a representation of airline flights among a number of cities:
Departure Destination ---------------------------------- ---------------------------------- Chicago New York Chicago Milwaukee Denver Chicago Seattle Chicago Seattle Denver Seattle San Francisco
With this data, finding all routes between a given pair of cities is a common problem:
Itineraries ---------------------------------- Seattle, Chicago, New York Seattle, Denver, Chicago, New York
To solve this problem, you can make these changes to the example in Expanding Hierarchies:
- Two additional input parameters are required: the goal city and the depth-of-search limit.
- The current itinerary is saved in another temporary table and displayed only when a goal is reached.
- To avoid expanding around a cycle in the network, do not expand cities that appear in the current itinerary.
These changes are shown in this example (not from the pubs database):
CREATE PROCEDURE route (@current char(20), @dest char(20), @maxlevel int = 5) AS SET NOCOUNT ON DECLARE @level int CREATE TABLE #stack (city char(20), level int) CREATE TABLE #list (city char(20), level int) INSERT #stack VALUES (@current, 1) SELECT @level = 1 WHILE @level > 0 BEGIN IF EXISTS (SELECT * FROM #stack WHERE level = @level) BEGIN SELECT @current = city FROM #stack WHERE level = @level DELETE FROM #stack WHERE level = @level AND city = @current DELETE FROM #list WHERE level >= @level IF EXISTS (SELECT * FROM #list WHERE city = @current) CONTINUE INSERT #list VALUES(@current, @level) IF(@current = @dest) BEGIN SELECT city AS itinerary FROM #list CONTINUE END INSERT #stack SELECT destination, @level + 1 FROM flights WHERE departure = @current AND @level < @maxlevel IF @@rowcount > 0 SELECT @level = @level + 1 END ELSE SELECT @level = @level - 1 END -- WHILE
In this example, when @level is greater than 0, the procedure follows these steps:
- The current city is added to #list by clearing anything at the current level or below (DELETE FROM #list WHERE level > = @level), and then by adding the current city (INSERT #list VALUES(@current, @level)).
- When the goal city is reached (@current = @dest), the procedure displays the path (SELECT itinerary = city FROM #list) and does not expand the path any further (CONTINUE).
- The depth of search is limited by adding a condition (@level < @maxlevel) to the INSERT statement that adds cities to the stack.
The IF EXISTS statement at the beginning of the WHILE loop skips the current city if it is already in the current itinerary.
If the flights table also contains cost information, the lowest cost route can be found by saving the current itinerary if its total cost is less than the best cost so far:
SELECT @cost = sum(cost) FROM #list IF @cost < @lowest_cost BEGIN @lowest_cost = @cost TRUNCATE TABLE #best_route INSERT #best_route SELECT * FROM #list END
For greater efficiency, stop expanding the current route if the current cost exceeds the cost of the best route:
IF (SELECT SUM(cost) FROM #list) > @lowest_cost CONTINUE
If the flights table includes a departure and arrival time, you can add an IF statement to expand only the routes that have a departure time at least one hour after the arrival time of the current route:
IF ((SELECT SUM(cost) FROM #list) > @lowest_cost) AND datediff(hh, departuretime, @arrivaltime) > 1) CONTINUE