Guided Practice 8.4

In the adjacency-list representation of graphs, a graph is represented as a list of node-information items, where each node-information item consists of the node and the list of successors of that node. Here's a data definition and an example:

;; A Graph is a ListOfNodeInfo
;; A NodeInfo is a (list Node ListOfNode)
;; WHERE: If the graph is 
;; '((n_1 (n_11 n_12..))
;;   (n_2 (n_21 n_22 ...))
;;   ...),
;; then:
;; there are no repetitions among the n_i
;; AND for each i, there are no repetitions among n_i1, n_i2, etc.
;; AND every node that occurs as an n_ij is also listed among the n_i.
;; INTERPRETATION: the ni are the nodes in the graph, and n_i1, n_i2,
;; etc., are the successors of n_i


(define graph1
  '((a (c))
    (b (a c))
    (c ())))
;; represents the same graph that used to be represented as
;;   (list
;;     (make-edge 'a 'c)
;;     (make-edge 'b 'a)
;;     (make-edge 'b 'c))

What is the least amount that needs to be done to convert 08-3-reachability.rkt to use this representation?

Hint: This is easy.


Last modified: Sun Oct 19 17:45:45 Eastern Daylight Time 2014