Graph recursive walk in Scheme

Question

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.

Answer 1

As bruno notes in his answer, Scheme uses pass-by-value semantics; changing what a variable is set to doesn't change it in the caller. The usual approach to accumulator arguments is to return a possibly modified copy, and have the caller capture that for further use.

Also, in a loop, (append accumulator-list (list some-value)) is an anti-pattern; because append is a O(N) operation, it can easily turn an O(N) algorithm into an O(N²) one for example or otherwise dramatically increase runtime. The usual approach is to cons new elements onto the head of an accumulator list, and reverse it at the very end to get the desired order. Usually the top-level function defines an internal function to do all the real work and does that reversal when it calls it; this can also allow you to not have to pass an initial accumulator value (The empty list most times) to the top level function, making things cleaner.

There's also a trend among Schemers to avoid using set! if an alternative that doesn't involve it can be used - writing in more of a functional style rather than imperative. Not always feasible, but in this case, your algorithm lends itself well to using a fold higher-ordered function to iterate over the lists of adjacencies, adding new ones to an accumulator as it goes. In Scheme, fold is typically provided by the SRFI-1 list library that most non-toy Scheme implementations support (R6RS Schemes have a fold-left in the (rnrs lists (6)) library that can be used instead (Though the arguments it passes to its function are reversed from the usual so the below code will need some tweaking)).

So I'd write your walk function like so:

;;; Exact import spec and even use of import will depend on your
;;; scheme implementation; this is for generic R7RS with a SRFI-1 library
;;; available.
(import (scheme base) (scheme write) (srfi 1))

(define (walk vadj x)
  (define (helper x seen)
    (if (member x seen)
        seen
        (fold helper (cons x seen) (vector-ref vadj x))))
  (reverse! (helper x '())))

(display (walk #((1 2) (0 3) (0) (1) (5) (4)) 0)) ; (0 1 3 2)
(newline)

Answer 2

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