Program 2

Program 2

A directed graph (also called a "digraph") contains a set of nodes connected by "arcs" or "edges", usually drawn as arrows. The graph is called "directed" because these edges have directionality: they go from one node to another. (In contrast, in an undirected graph the edges between nodes can be thought of as bidirectional, like highways between cities.)

For example, here's a simple digraph: 

          DET ------------> NOUN
            \                 ^
             \                |
              \              /
               \            /
                --> ADJ ----
                    / ^
                    |_|
That is, we have nodes named DET, ADJ, and NOUN, and we have four edges: one from DET to NOUN, one from DET to ADJ, one from ADJ to NOUN, and one from ADJ to itself.

In this assignment, you'll see two different ways to represent digraphs, and your job will be to write the same functionality using the two representations. Specifically, you should do the following:

  1. Complete the missing parts of the functions in program2a.lisp. The file examples.txt shows you examples of how the functions should behave. A good first step would be to draw +graph1+ on paper.

  2. Once program2a.lisp is complete and correct, you should be able to load "examples.lisp" and get the same output as in examples.txt. Turn in (i) a hardcopy listing of program2a.lisp, and (ii) a dribble showing the result of (load "examples").

  3. Now complete the missing parts of the functions in program2b.lisp. Note that in principle there is no reason that all or even most of the function bodies might not be identical to what you wrote in program2a. This illustrates how breaking a problem into the right pieces can make life easier: changing representations doesn't necessarily mean changing every single function in a program!

  4. You should turn in the hardcopy and dribble exactly as for program2a.

My own assessment is that this assignment is harder than the usual exercise set, but easier than the last programming assignment, but I could be wrong. So make sure you get started early!!

Solutions: 2a, 2b