CS 2102 - Bterm 08

Homework 1 - Accumulator-Style Functions; Data Definitions

Due: Sunday, November 2 at 11:59pm

For this assignment only, we will provide in advance the grade sheet we'll use when grading this assignment. Where the grade sheet refers to "template" in problems 2 -11, this means you structured your function using information from the appropriate template (you don't have to provide the template definition for each problem, just use the appropriate template when writing your function).

Assignment Goals

• To review accumulator-style functions in DrScheme
• To review data definitions in DrScheme

The Assignment

    B<----->A<-----------C
    |       ^           /
    v       |          /    
    D------>E         /    
    ^       |        /    
    |       |       /
    |       |      /
    F       |     /
     \      |    /
       \    |   /
         \  |  /
            v
            G

There is no ordering of the list of nodes or the list of edges. Each edge has a source and a target, and so the edge from A to B is different from the edge from B to A, though it is possible that both exist, as shown.

Note that each node has a name (typically just one letter) and we will record its location (a posn), so we can later draw the graph on a Canvas. Use a string (not a symbol) for the name.

Use check-expect from testing.ss to test your functions. You are not required to provide test cases for functions that produce images.

Problems

1. In Scheme, design the data to represent a list of nodes in a graph and a list of edges connecting the nodes. Each edge needs to record just the names of the two nodes belonging to the edge (not the entire information about the nodes). Provide examples of data and templates for your data definitions.

2. Design the function neighbors that for a given node and a list of edges produces a list of all neighbors of the given node. For example, neighbors of the node C above are nodes A and G. (Note that C is not a neighbor of G, however).

   Follow the design recipe precisely. It is sufficient to produce the names of the nodes; the function does not need to produce the entire information about each neighbor.

3. Define the function neighbors2 that solves the same problem, but uses accumulator-style programming.

4. Design the function draw-node that draws the node at its location as a small red circle with its letter label overlayed on top. The image.ss teachpack contains functions to create circle and text images and functions to overlay one image on top of another.

5. Design the function draw-edge that draws the given edge as a red line between the locations of its two endpoints. Think carefully about what information this function will need to accomplish its task.

6. Create a simple line drawing, and represent it as a list of edges and a list of nodes. Now design a function draw-edges that draws all edges in a given list of edges.

7. Write a function draw-nodes that draws all nodes in a list of nodes.

8. Write the function draw-graph that will draw the whole graph.

9. Your boss tells you that she would like to record for each node of the graph a list of the names of its neighbors. Design a data definition for node2 that includes all the information contained in your original node definition, plus the information about the node's neighbors.

10. Design the function find-edges that extracts from a list of node2 data the list of all edges in that graph.

11. Design the function draw-graph2 that will draw the graph that uses the node2 data definition.

What to Turn In

Using web-based turnin, turn in a single file hw1.scm containing all code and documentation for this assignment. Your name and wpi login name should appear in a comment at the top of the file.