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 ;; EXAMPLE: (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