CS 2102 - Dterm 09

Homework 1 - Scheme Review: Data Definitions

Due: Friday, March 20 at 5pm


This assignment is to be done individually.

Assignment Goals

The Assignment

In this assignment, you will write (Scheme) data definitions and functions that model a graph: 

    B<----->A<-----------C
    |       ^           /
    v       |          /    
    D------>E         /    
    ^       |        /    
    |       |       /
    |       |      /
    F       |     /
     \      |    /
       \    |   /
         \  |  /
            v
            G
A graph consists of a set of nodes N and a set of edges E. In the graph pictured above, N={A, B, C, D, E, F, G} and E={(A, B) (B, A) (B, D) (C, A) (C, G) (D, E) (E, A) (E, G) (F, D) (F, 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 DrScheme, design the data definitions to represent a graph. A graph will be represented by a list of nodes, where a node contains the name of the node, its location, and a list of the names of its neighbors. (The neighbors of node C in the pictured graph are A and G. Node G has no neighbors.) Provide examples of data and templates for your data definitions.

  2. Provide data definitions for an edge, and a list of edges. An edge needs to record just the names of the two nodes belonging to the edge (not the entire information about the nodes in each edge). Provide examples of data and templates for your data definitions.

  3. Design the function find-edges that extracts from a list of node the list of all edges in that graph.

  4. Design the function draw-node that draws a 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 consumes two nodes and draws an edge between the nodes as a red line between the locations of its two endpoints.

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

  7. Design a function draw-edges that draws all edges in a given list of edges nodes. (Sorry for the typo. The function draw-edges should consume a list of nodes.)

  8. Write the function draw-graph that will draw the whole graph given a list of nodes.

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.