On Jan 19, 2016, at 3:41 AM, pvt <liweijian.h...@gmail.com> wrote:
> I just read the chapter of graph traversing from HtDP's website:
>
> http://www.ccs.neu.edu/home/matthias/HtDP2e/part_five.html#%28part._fsm._sec~3atraverse-graph1%29
>
> The implementation of graph traversing is the calling sequence of:
> `find-path` -> `find-path/list` -> `find-path` -> ...
>
> I must say this is the best DFS algorithm implementation I've ever found.
>
> I was wondering if maybe we could implement the topological sorting algorithm
> in this HtDP-y way? Or maybe is that not necessary?
>
> I found an elegant implementation in which the core function `visit` call
> itself:
> https://github.com/carl-eastlund/mischief/blob/master/mischief/sort.rkt
Thanks for the entertaining question.
If you go to Wikipedia, you find a graph and several suggested topological
sorts.
You also find a natural description of an algorithm for DAGs:
-- find vertices w/o incoming edges
-- list those
-- remove them from the graph
-- repeat until graph is empty
This clearly suggests a generative recursion. If you represent graphs as list
of list of nodes plus outgoing connections, you can see that you reverse the
algorithm and of course you get a reversed topological sorted list back. You
can use reverse or you can throw in an accumulator and get the result directly.
This is how a person thinks who has absorbed HtDP completely.
;; A Directed Graph
;; Graph = [Listof [NEListof Node]]
;; Node = N
;; constraint: every non-first node on any list must start some other list
;; interpretation:
;; each list represents the source node and
;; to which destination nodes it connects
(define the-graph
'((5 11)
(11 2 9 10)
(2)
(7 11 8)
(8 9)
(9)
(3 8 10)
(10)))
;; -----------------------------------------------------------------------------
;; Graph -> [Listof Node]
;; generative recursion with accumulator
;; remove nodes without outgoing edges and accumulate tho
(check-member-of (topological-sort the-graph)
'(5 7 3 11 8 2 9 10) ; (visual left-to-right, top-to-bottom)
'(3 5 7 8 11 2 9 10) ; (smallest-numbered available vertex
first)
'(5 7 3 8 11 10 9 2) ; (fewest edges first)
'(7 5 11 3 10 8 9 2) ; (largest-numbered available vertex
first)
'(5 7 11 2 3 8 9 10) ; (attempting top-to-bottom,
left-to-right)
'(3 7 5 8 11 10 9 2) ; the one that we actually find
'(3 7 8 5 11 10 2 9)) ; (arbitrary]
(define (topological-sort G0)
(local (;; Graph [Listof Node] -> [Listof Node]
;; accumulator: done are topologically sorted nodes between G and G0
(define (topological-sort G done)
(cond
[(empty? G) done]
[else
(local ((define next (no-out-going-edges G))
(define G-next (foldr remove-node G next)))
(topological-sort G-next (append next done)))])))
(topological-sort G0 '())))
;; -----------------------------------------------------------------------------
;; Graph -> [Listof Node]
;; find vertices w/o outgoing edges
(check-expect (no-out-going-edges the-graph) '(2 9 10))
(define (no-out-going-edges G)
(map first (filter (lambda (c) (empty? (rest c))) G)))
;; -----------------------------------------------------------------------------
;; Node Graph -> Graph
;; remove the node from this graph
(define the-graph-without-9
'((5 11)
(11 2 10)
(2)
(7 11 8)
(8)
(3 8 10)
(10)))
(check-expect (remove-node 9 the-graph) the-graph-without-9)
(define (remove-node n G)
(local (;; [Listof Node] -> [Listof Node]
(define (remove-connectivity c)
(remove-all n c)))
(filter cons? (map remove-connectivity G))))
EXERCISE Design a function is-sorted-topologically?. It consumes a list of
nodes and a (directed acyclic) graph. Its result is #true if the given list is
sorted topologically. Otherwise it produces #false.
Once you have designed the function, use it to simplify the test case for
topological sort. []
--
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.
