recursiongraphscheme

Graph recursive walk in Scheme


I have an undirected graph which nodes are numbered from 0 to 5. Adjacencies are given with a vector of lists #((1 2) (0 3) (0) (1) (5) (4))), thus node 0 is connected to nodes 1 and 2, node 1 is connected to nodes 0 and 3 and so on.

I want to walk using a DFS recursive algorithm:

Function walk(vector: vadj, integer: x, list: acc)
  If x is not in acc then
    append x to acc
    Foreach successor y of x
      walk(vadj, y, acc)
    EndForeach
  EndIf
EndFunction

With Scheme, I try:

(define (walk vadj x acc)
  (unless (member x acc)
    (set! acc (append acc (list x)))
    (let loop ((lst (vector-ref vadj x)))
      (unless (null? lst)
        (walk vadj (car lst) acc)
        (loop (cdr lst))))))

(let ((adj #((1 2) (0 3) (0) (1) (5) (4)))
      (res '()))
  (walk adj 0 res)
  (newline)(display res))

I get an empty list as a result, the result should be '(0 1 3 2). I suspect acc is sometimes redefined by successive walk environments.


Solution

  • Warning : I never used Scheme before to write that answer

    The algorithm supposes the parameter acc is an input-output parameter, but it seems in scheme the parameters can only be input parameters (I don't see in docs how to specify the parameter direction)

    So a way is to return acc and assign it (or res) on the calls of walk to simulate the input-output:

    (define (walk vadj x acc)
      (unless (member x acc)
        (set! acc (append acc (list x)))
        (let loop ((lst (vector-ref vadj x)))
          (unless (null? lst)
            (set! acc (walk vadj (car lst) acc))
            (loop (cdr lst)))))
      acc)
    
    (let ((adj #((1 2) (0 3) (0) (1) (5) (4)))
          (res '()))
      (set! res (walk adj 0 res))
      (newline)(display res)
    )
    

    and the execution prints (0 1 3 2)

    Or of course simplify replacing :

      (set! res (walk adj 0 res))
      (newline)(display res)
    

    by :

      (newline)(display (walk adj 0 res))