In fact, this solution isn't even quite correct modulo the representation
problem you pointed out yet. It fails on some input graphs:
```
(define problem-graph
'((A (B C E))
(B (E))
(C (F))))
```
As for your nesting list problem, I believe it will nest things deeper the
longer the path. The problem is in the interplay between `map` and
`find-paths`. `find-paths` returns a list, by applying its first argument to
each element of its second argument. But `find-paths` produces a list as its
result. What happens when each result in a map is, itself, a list?
If you're still having trouble seeing the source of the problem, try writing
down the type of each argument to and result from the functions `find-paths`,
`find-paths/all`, and `neighbors`. For example, the type of `origin` should be
`symbol`, the type of `path` should be `(listof symbol)`, the type of `G` can
just be `graph` (for simplicity), and the return type of `neighbors` should be
`(listof symbol)`. You're going to run into trouble trying to match a couple of
types that really ought to match.
- Lucas Paul
On Saturday, January 30, 2016 at 9:29:56 PM UTC-7, liweijian wrote:
> HtDP taught us how to check if there exists path(s) from one node to another.
>
> I tried to implement accumulating all the paths between two nodes as:
>
> ```racket
> (define (find-paths origin dest G path)
> (cond
> [(equal? origin dest) (reverse (cons dest path))]
> [else
> (find-paths/all (neighbors origin G) dest G (cons origin path))]))
>
> (define (find-paths/all lons dest G path)
> (cond
> [(empty? lons) '(#f)]
> [else
> (map (λ (n) (find-paths n dest G path)) lons)]))
> ```
>
> However, when I tested it by
>
> ```racket
> (define sample-graph
> '((A (B E))
> (B (E))))
>
> (define (neighbors origination G)
> (cadr (assoc origination G)))
>
> (find-paths 'A 'E sample-graph '())
> ```
>
> The answer is: '(((A B E)) (A E))
>
> In order to get the right answer, I have to write another `flatten` function
> as:
>
> ```racket
> (define (flatten-path lop)
> (cond
> [(empty? lop) empty]
> [(not (list? (caar lop))) (cons (first lop) (flatten-path (rest lop)))]
> [else
> (append (flatten-path (first lop)) (flatten-path (rest lop)))]))
>
> (filter (λ (path) (not (boolean? (car path)))) (flatten-path (find-paths 'A
> 'E sample-graph '())))
> ```
>
> And now it works.
>
> I was wondering if maybe I could improve it?
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
