Graph programming in Scheme

Question

I'm new to Scheme, have been using MIT Scheme for sometime now. I'm trying to understand how to implement popular graph algorithms like the shortest path algorithms, BFS, DFS. Are there any tutorials that could help me out understand the recursion that'd be involved, along with the appropriate data structures? I have tried Googling my way around, but that didn't end up giving me good results.

EDIT: I apologize for not being more specific earlier. My question was pertaining to traversing the whole graph, and not finding the path between a start and goal node. So, given a graph G(V, E), where V is the vertex set and E is the edge set, starting from any node n, what is the path generated so that at the end of this traversal, all nodes are visited.

Most implementations that I found while Googling were the ones with the start and goal node. My version (one of the answers), chooses one vertex, and visits all others.

Take for example, the following graph:-

1 ----> 2           5
       /|          /|
      / |         / |
     /  |        /  |
    /   |       /   |
   /    |      /    | 
  4<----3 <---6     7

This DAG has (4->2), (2->3), (5->6) and (5->7), which I unable to represent in the diagram. :-)

The Path traversed starting from 1 could be:

(1, 2, 3, 4, 5, 6, 7)

Behave

Answer 1

Took some time, but I got it working finally! My output is the sequence in which the nodes would've been visited in the traversal through DFS.

Note that I am still only learning Scheme, and my programming approach might not be the best. If you find something wrong, incorrect or something that can be expressed better, leave a comment!

    (define (dfs graph)
       (define (dfshelper g unvisited stack path)
          (cond
             ((null? unvisited) path)
                ((null? stack)
                   (dfshelper g
                              unvisited 
                              (append (list (caar unvisited)) stack) 
                              path))
                ((memq (car stack) path) (dfshelper g
                                                    unvisited 
                                                    (cdr stack) 
                                                    path))
                (else (dfshelper g
                                 (cdr unvisited) 
                                 (append (car (neighbours (car stack) g)) (cdr stack)) 
                                 (append path (list (car stack)))))))

   (define (neighbours node g)
      (cond
         ((null? g) '())
         ((equal? node (caar g)) (cdar g))
         (else (neighbours node 
                           (cdr g)))))

   (dfshelper graph  graph '() '()))

Sample input could be: (dfs '((1 (2)) (2 (3)) (3 (4)) (4 (2)) (5 (3 6)) (6 ())))

Behave

I'm curious about what you're trying to code up. Specifically, a search algorithm usually involves searching for a goal or target, but it looks like your program does not. Some purpose statements, contracts, and test cases would help a bunch! – Lardon

John, I have added a short summary to my question! Let me know if I am missing something! – Behave

Answer 2

Breadth-first and Depth-first search both occur as examples in How To Design Programs, starting in section 28. I think that this will probably help you most specifically with your question about the uses of recursion in graph processing.

Lardon

The traversal described there has a start and a goal node, and ends if the goal node is found. The problem that I'm facing while implementing a full DFS, is that the "visited" list is not propagated to higher levels of recursion. – Behave

Sure, that's valid. In order to solve that, you'd want a searcher that returns either a valid path or a list of all the nodes visited so far. This would allow you to avoid visiting the same nodes twice. – Lardon

Answer 3

If you represent graphs like this, i.e. as a list of names of nodes and the names of their neighbors:

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

that has the advantage that you can even represent cyclic graphs without resorting to destructive modification of your data structure (set-cdr! etc.), provided you allow multiple entries in the list for each key.

Alternately, you could store not just the names but the full representation of each neighbor in a list, so that you can walk the graph without doing any name lookups:

(define node-name car)
(define node-children cdr)
(define node-first-child cadr)

(node-first-child (node-first-child node1))

To make a cyclic graph this way though, you'd need to use set! or some variant. So the best representation really depends on the application.

Lansing

Thanks gcbenison, your graph representation was helpful! – Behave

Answer 4

How to Design Programs (HtDP) gives one possible implementation without solving with cyclic graph situation although it points out this problem (I have not read HtDP before so I don't know where is that part.):

In the next part, we will study a programming technique that helps us finds routes even in the presence of cycles in a graph.

We can follow wikipedia to make that code work. Here we still use "recursive implementation" (notice this corresponds to iterative implementation in SICP term.)

;; https://htdp.org/2003-09-26/Solutions/find-route4.html
(define (printf . args)
  (newline)
  (for-each 
    display
    args))

#| ---------------------------------------------------------------------------------

   Find Route in Graph: Tests

   find-route : node node graph -> (listof node) or #f
   Purpose: produce a list of nodes, starting with origination 
    and ending destination. The list represent a path from 
    the origination node to the destination node in a-graph.
    If there is no path, the function produces #f. 
|#

;; We need `visited` https://mcmap.net/q/1777036/-finding-a-path-in-a-directed-graph-in-python, i.e. `discovered` https://en.wikipedia.org/wiki/Depth-first_search#Pseudocode
(define (set-minus set-1 set-2)
  (remove (lambda (x) (member x set-2)) set-1))
(define visited '())

(define (find-route origination destination graph)
  (set! visited '())
  (find-route-helper origination destination graph))

(define (find-route-helper origination destination graph)
  (printf "(find-route ~s ~s cyclic-graph)~n" origination destination)
  (cond
    ((eq? origination destination) (list destination))
    (else 
      (if (member origination visited)
        '()
        (begin
          (printf "neighbors of " origination " are " (neighbors origination graph))
          ;; > label v as discovered
          (set! visited (cons origination visited))
          (let ((possible-route 
                  (find-route/list (set-minus (neighbors origination graph) visited) destination graph)))
            (cond
              ((boolean? possible-route) #f)
              (else (cons origination possible-route)))))))))

#| find-route/list : (listof node) node graph -> (listof node) or #f
   Purpose: produce a list of nodes, starting with one node on lo-originations 
    and ending destination. The list represent a path from 
    the node on lo-originations to destination in a-graph.
    If there is no path, the function produces #f.     |#
(define (find-route/list lo-Os D graph)
  (printf "(find-route ~s ~s cyclic-graph)~n" lo-Os D)
  (cond
    ((null? lo-Os) #f)
    (else 
      (let ((next-node (first lo-Os)))
        (if (member next-node visited)
          '()
          ;; > if vertex w is not labeled as discovered then
          (begin
            ;; comment the following out to avoid inserting twice.
            ; (set! visited (cons next-node visited))
            (let ((possible-route (find-route-helper next-node D graph)))
              (cond
                ((boolean? possible-route) (find-route/list (cdr lo-Os) D graph))
                (else possible-route)))))))))

(define (neighbors a-node a-graph)
  (second (assq a-node a-graph)))

#| ---------------------------------------------------------------------------------
   Tests: data followed by expessions |#

(define Graph 
  '((A (B E))
    (B (E F))
    (C (B D))
    (D ())
    (E (C F))
    (F (D G))
    (G ())))

(assert (equal? (list 'A 'B 'E 'F 'G) (find-route 'A 'G Graph)))
(assert (equal? '(c b e f g) (find-route 'C 'G Graph)))
(assert (not (find-route 'G 'C Graph)))

;; Here DFS doesn't ensure to find the shortest path. Here I didn't intend to find that since it is beyond what SDf intends to teach.
(assert (equal? '(a b e) (find-route 'A 'E Graph)))

---

P.S. IMHO DFS_iterative in wikipedia link can use queue to have the same "visit" order as recursive. "it delays checking" to emulate "discovered" behavior when recursion.

Ency