A Problem with Generative Recursion

Next: Designing Accumulator-Style Functions Up: The Loss of Knowledge Previous: A Problem with Structural

A Problem with Generative Recursion

Let us revisit the problem of finding a path in a graph from section . Recall that we are given a collection of nodes and connections between nodes, and that we need to determine whether there is a route from a node labeled orig to one called dest. Here we study the slightly simpler version of the problem of simple graphs where each node has exactly one (one-directional) connection to another node.

Consider the example in figure . There are six nodes: A through F, and six connections. To get from A to E, we go through B, C, and E. It is impossible, though, to reach F from A or from any other node (besides F itself).

(define SimpleG 
  '((A B) 
    (B C) 
    (C E) 
    (D E) 
    (E B) 
    (F F)))

Figure: A simple graph

The right part of figure contains a Scheme definition that represents the graph. Each node is represented by a list of two symbols. The first symbol is the label of the node; the second one is the reachable node. Here are the relevant data definitions:

A node is a symbol.

A pair is a list of two nodes:

(cons S (cons T empty)) where S, T are symbols.

A simple-graph is a list of pairs:

(listof pair).

They are straightforward translations of our informal descriptions.

Finding a route in a graph is a problem of generative recursion. We have data definitions, we have (informal) examples, and the header material is standard:

;; route-exists? : node node simple-graph -> boolean
;; to determine whether there is a route from orig to dest in sg 
(define (route-exists? orig dest sg) ...)

What we need are answers to the four basic questions of the recipe for generative recursion:

What is a trivially solvable problem?: The problem is trivial if the nodes orig and dest are the same.
What is a corresponding solution?: Easy: true.
How do we generate new problems?: If orig is not the same as dest, there is only one thing we can do, namely, go to the node to which orig is connected and determine whether a route exists between it and dest.
How do we relate the solutions?: There is no need to do anything after we find the solution to the new problem. If orig's neighbor is connected to dest, then so is orig.

From here we just need to express these answers in Scheme, and we get an algorithm. Figure

contains the complete function, including a function for looking up the neighbor of a node in a simple graph.

;; route-exists? : node node simple-graph -> boolean
;; to determine whether there is a route from orig to dest in sg 
(define (route-exists? orig dest sg) 
  (cond 
    [(symbol=? orig dest) true] 
    [else (route-exists? (neighbor orig sg) dest sg)]))

;; neighbor : node simple-graph -> node
;; to determine the node that is connected to a-node in sg 
(define (neighbor a-node sg) 
  (cond 
    [(empty? sg) (error ``neighbor: impossible'')] 
    [else (cond 
            [(symbol=? (first (first sg)) a-node) 
             (second (first sg))] 
            [else (neighbor a-node (rest ag))])]))

Figure: Finding a route in a simple graph (version 1)

Even a casual look at the function suggests that we have a problem. Although the function is supposed to produce false if there is no route from orig to dest, the function definition doesn't contain false anywhere. Conversely, we need to ask what the function actually does when there is no route between two nodes.

Take another look at figure . In this simple graph there is no route from C to D. The connection that leaves C passes right by D and instead goes to E. So let's look at how route-exists? deals with the inputs 'C and 'D for SimpleG:

  (route-exists? 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)))
= (route-exists? 'E 'D '((A B) (B C) (C E) (D E) (E B) (F F))) 
= (route-exists? 'B 'D '((A B) (B C) (C E) (D E) (E B) (F F))) 
= (route-exists? 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)))

The hand-evaluation confirms that as the function recurs, it calls itself with the exact same arguments again and again. In other words, the evaluation never stops.

Our problem with route-exists? is again a loss of ``knowledge,'' similar to that of relative-2-absolute in the preceding section. Like relative-2-absolute, route-exists? was developed according to the recipe and is independent of its context. That is, it doesn't ``know'' whether some application is the first or the hundredth of a recursive chain. In the case of route-exists? this means, in particular, that the function doesn't ``know'' whether a previous application in the current chain of recursions received the exact same arguments.

The solution follows the pattern of the preceding section. We add a parameter, which we call accu-seen and which represents the accumulated list of origination nodes that the function has encountered, starting with the original application. Its initial value must be empty. As the function checks on a specific orig and moves to its neighbors, orig is added to accu-seen.

Here is a first revision of route-exists?, dubbed route-exists-accu?:

;; route-exists-accu? : node node simple-graph (listof node) -> boolean
;; to determine whether there is a route from orig to dest in sg,  
;; assuming the nodes in accu-seen have already been inspected  
;; and failed to deliver a solution  
(define (route-exists-accu? orig dest sg accu-seen) 
  (cond 
    [(symbol=? orig dest) true] 
    [else (route-exists-accu? (neighbor orig sg) dest sg 
                              (cons orig accu-seen))]))

The addition of the new parameter alone does not solve our problem, but, as the following hand-evaluation shows, provides the foundation for one:

  (route-exists-accu? 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)) empty)
= (route-exists-accu? 'E 'D '((A B) (B C) (C E) (D E) (E B) (F F)) '(C)) 
= (route-exists-accu? 'B 'D '((A B) (B C) (C E) (D E) (E B) (F F)) '(E C)) 
= (route-exists-accu? 'C 'D '((A B) (B C) (C E) (D E) (E B) (F F)) 
                      '(B E C))

In contrast to the original function, the revised function no longer calls itself with the exact same arguments. While the three arguments proper are again the same for the third recursive application, the accumulator argument is different from that of the first application. Instead of empty, it is now '(B E C). The new value represents the fact that during the search of a route from 'C to 'D, the function has inspected 'B, 'E, and 'C as starting points.

All we need to do at this point is exploit the accumulated knowledge in the function definition. Specifically, we determine whether the given orig is already an item on accu-seen. If so, the problem is trivially solvable with false. Figure contains the definition of route-exists2?, which is the revision of route-exists?. The definition refers to contains, our first recursive function (see part ), which determines whether a specific symbol is on a list of symbols.

;; route-exists2? : node node simple-graph -> boolean
;; to determine whether there is a route from orig to dest in sg 
(define (route-exists2? orig dest sg) 
  (local ((define (re-accu? orig dest sg accu-seen) 
            (cond 
              [(symbol=? orig dest) true] 
              [(contains orig accu-seen) false] 
              [else (re-accu? (neighbor orig sg) dest sg (cons orig accu-seen))]))) 
    (re-accu? orig dest sg empty)))

Figure: Finding a route in a simple graph (version 2)

The definition of route-exists2? also eliminates the two minor problems with the first revision. By localizing the definition of the accumulating function, we can ensure that the first call to re-accu? always uses empty as the initial value for accu-seen. And, route-exists2? satisfies the exact same contract and purpose statement as route-exists?.

Still, there is a significant difference between route-exists2? and relative-to-absolute2. Whereas the latter was equivalent to the original function, route-exists2? is an improvement over the route-exists? function. After all, it corrects a fundamental flaw in route-exists?, which completely failed to find an answer for some inputs.

Exercises

Exercise 30.2.1

Complete the definition in figure and test it with the running example. Use the strategy of section to formulate the tests as boolean-valued expressions.

Check with a hand-evaluation that this function computes the proper result for 'A, 'C, and SimpleG. Solution

Exercise 30.2.2

Edit the function in figure so that the locally defined function consumes only those arguments that change during an evaluation. Solution

Exercise 30.2.3

Develop a vector-based representation of simple graphs. Adapt the function in figure so that it works on a vector-based representation of simple graphs. Solution

Exercise 30.2.4

Modify the definitions of find-route and find-route/list in figure so that they produce false, even if they encounter the same starting point twice. Solution

Next: Designing Accumulator-Style Functions Up: The Loss of Knowledge Previous: A Problem with Structural

PLT