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 pubs):

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 several 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. Whenever the goal city is reached (@current = @dest), the procedure displays the path (SELECT itinerary = city FROM #list) and doesn’t 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, you can stop expanding the current route if the current cost far exceeds the cost of the best route:

IF (SELECT SUM(cost) FROM #list) > @lowest_cost

    CONTINUE

If the flights table also 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