Expanding Networks

In the example in the preceding section, each item had only one superior. In a network, an item can have more than one superior. The following data, for example, 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

A common problem you can have with this data is finding all routes between a given pair of cities:

Itineraries
----------------------------------
Seattle, Chicago, New York
Seattle, Denver, Chicago, New York

A few changes to the example in the preceding section can accomplish this:

• 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, don't expand cities that appear in the current itinerary.

These changes are illustrated in the following example (not from pubs):

create proc 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 itinerary = city
                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

In this example, when @level is greater than 0, the process 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 adding the current city (INSERT #list VALUES(@current, @level)).
2. Whenever the goal city is reached (@current = @dest), this example 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's already in the current itinerary.

If the flights table in the preceding example 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