CODEWITHSUNDEEP
schemeracket
rnso
rnso

Reputation: 24535

Finding path between 2 points in Racket

I have following list of connections: 

(define routelist
  (list
      (list'a 'b)
      (list'a 'c)
      (list'b 'e)
      (list'b 'f)
      (list'b 'c)
      (list'a 'd)
      (list'e 'f)
      (list'f 'g)))

Routes between 'a and 'g are to be found. This page shows a solution in Prolog: http://www.anselm.edu/homepage/mmalita/culpro/graf1.html

I could manage following solution, though it is iterative: 

(define (mainpath routelist start end (outl '()))
  (if (equal? start end)
      (println "Same start and end points.")
  (for ((item routelist)) 
    (when (equal? start (list-ref item 0))
          (set! outl (cons start outl))
          (if (equal? end (list-ref item 1))
              (begin 
                ; PATH FOUND:
                (set! outl (cons end outl))
                (println (reverse outl)))
              (begin 
                (mainpath (rest routelist) (list-ref item 1) end outl)
                (set! outl (rest outl))))))))

(mainpath routelist 'a 'g)

Output: 

'(a b e f g)
'(a b f g)

How can a functional solution be achieved in Racket?

Upvotes: 1

Views: 1207

Answers (2)

wangjiezhe
wangjiezhe

Reputation: 121

Use DFS algorithm will be ok.

(define (mainpath routelist start end)
  (letrec ([next-nodes (λ (node)
                        (for/list ([al routelist]
                                   #:when (eq? node (first al)))
                                  (second al)))]
           [path (λ (node vlist)
                   (let ([new-list (cons node vlist)])
                     (when (eq? node end)
                       (println (reverse new-list)))
                     (for ([next (next-nodes node)]
                           #:unless (memq next vlist))
                          (path next new-list))))])
    (path start '())))

Upvotes: 1

Renzo
Renzo

Reputation: 27424

Here is a very simple solution:

(define (mainpath routelist start end)
  (define (neighbors node)
    (map second (filter (lambda (x) (eq? (first x) node)) routelist)))
  (define (visit node visited)
    (when (not (member node visited))
      (when (eq? node end)
        (println (reverse (cons node visited))))
      (let ((new-visited (cons node visited)))
        (map (lambda (x) (visit x new-visited)) (neighbors node)))))
  (visit start '())
  "No more paths")

This recursive function, that can manage also graphs with loops, keeps a list of nodes already visited along the current path and stops when it has visited all the nodes reachable from the start node. When the current node is the end node, the current path is printed.

Upvotes: 2

Related Questions