Expanding Networks

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:

1. 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)).
   
   
2. 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).
   
   
3. 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