Question

This problem should be solved using the DrRacket software in the Racket/Scheme language.

Consider two techniques for representing a graph as Scheme lists. We can represent a directed graph as a list of edges. We call this representation an el-graph (i.e. edge-list graph). An edge is itself a list of length two such that the first element is a symbol denoting the source of the edge and the second element is a symbol denoting the target of the edge. Note that an edge is a list (not just a pair). For example, the following is a graph: '((x y) (y z) (x z)). We can also represent a graph similar to an adjacency matrix. We call this representation an x-graph (i.e. matrix-graph). In this case, a graph is a list of adjacencies where an adjacency is a list of length two such that the first element is a node (a symbol) and the second element is a list of the targets of that node. For example, the following is a graph: '((x (y z)) (y (z)) (z ())).

- Write function (el-graph->x-graph g), that accepts an el-graph g and returns an x-graph of g.

- Write function (x-graph->el-graph g), that accepts an x-graph g and returns an el-graph of g.

Answer 1

(define (el-graph->x-graph g)
   (cond ((null? g) '())
       ; case to handle (z ())
       ((null? (cadar g)) '())
       ; case to handle (y (z))
       ((null? (cdadar g)) (cons (list (caar g) (caadar g)) (el-graph->x-graph (cdr g))))
       ; case to handle (x (y z))
       (else (cons (list (caar g) (caadar g)) (el-graph->x-graph (cons (list (caar g) (cdadar g)) (cdr g)))))
   )
)

; (el-graph->x-graph '((x (y z)) (y (z)) (z ())))