CS 2360 Assignment 4: Due Midnight Feb 13

The Simpson's Problem

For this program, you need to solve "the Simpson's problem" which I have been talking about in class. Below, there is a database of "facts" about the relationships in the Simpon's TV show. You should use these facts and a depth first search to construct your solution. You should try to make your solution as modular as possible, and use abstract data types where appropriate.

Requirements

Your program must have a function which creates an edge called edge-construct which takes two character names and a relationship as input and constructs an edge data structure from this input.
Your program must have a function called edge-print which will print the relationship of an edge out on the terminal. It should print a sentence about the relationship. It does not matter what this function returns.
Your program must have a function that implements a recursive depth first search of the graph. (Note, this is going to really be implemented using several functions to support this function.) This function should be called tv-show-relation and should take two characters and a list of edges as arguments and return a list of edges that connects the two characters or nil if no such connection exists.
Obviously, you want to have some nice abstractions to manipulate edges and edge-lists but these are for you to design.

Database

The following piece of code may be useful for your testing (although it is by no means complete): (setq simpsons-db (list (edge-construct 'lisa 'homer 'father) (edge-construct 'marge 'homer 'husband) (edge-construct 'homer 'marge 'wife) (edge-construct 'homer 'abraham 'father) (edge-construct 'bart 'homer 'father) (edge-construct 'homer 'bart 'son) (edge-construct 'homer 'lisa 'daughter) (edge-construct 'homer 'maggie 'daughter) (edge-construct 'marge 'bart 'son) (edge-construct 'marge 'lisa 'daughter) (edge-construct 'marge 'maggie 'daughter) (edge-construct 'lisa 'bart 'brother) (edge-construct 'bart 'lisa 'sister) (edge-construct 'maggie 'homer 'father) (edge-construct 'lisa 'marge 'mother) (edge-construct 'bart 'marge 'mother) (edge-construct 'maggie 'marge 'mother) (edge-construct 'snoball 'bart 'owner) (edge-construct 'bart 'snoball 'pet) (edge-construct 'santas-little-helper 'bart 'owner) (edge-construct 'flanders 'homer 'neighbor) (edge-construct 'flanders 'marge 'neighbor) (edge-construct 'homer 'flanders 'neighbor) (edge-construct 'marge 'flanders 'neighbor) (edge-construct 'homer 'mo 'bartender) (edge-construct 'homer 'barney 'drinking-buddy) (edge-construct 'barney 'homer 'drinking-buddy) (edge-construct 'smithers 'mr-burns 'boss) (edge-construct 'mr-burns 'smithers 'assistant) (edge-construct 'mr-burns 'homer 'employee) (edge-construct 'homer 'mr-burns 'boss) (edge-construct 'marge 'thelma 'sister) (edge-construct 'thelma 'marge 'sister) (edge-construct 'bart 'krusty 'hero) (edge-construct 'bart 'sideshow-bob 'enemy) (edge-construct 'sideshow-bob 'thelma 'wife) (edge-construct 'thelma 'sideshow-bob 'husband) (edge-construct 'milhouse 'bart 'friend) (edge-construct 'bart 'milhouse 'friend) ))

Assumptions

You may assume the following:

We will not provide two edges between the same two nodes. (i.e. we will not say that marge is both homer's wife and homer's lover)
You may not assume we will not provide cycles in the graph. (See the above.) It is very useful in a program of this type to have both marge being the wife of homer and homer being the husband of marge.
You may assume that symbols will always be the type of the data entered for the edges, and that EQUAL should be used to compare the names.

Grading

This program will consist of 70% programming practice and 30% programming style.
The 70% of your program that is practice is going to be broken down like this:
- 10 % each for the required edge functions mentioned above
- 30 % does your solution handle the simple cases of relationships
- 10 % does your dfs solution correctly realize when connections are not present
- 10 % does your dfs solution correctly detect cycles
The 30% programming style will be up to the judgement of the TAs having seen all the programs in their section. However, so main points are:
- Is the program reasonably well documented (i.e. comments, function names, variable names)
- Is the program's DFS code readable/understandable?
- Does the program contain an abstraction for the edge data structure?
- Does the program contain an abstraction for the edge list? (This will not be as important as the edge, but can be useful.)

Back To The CS2360 Home Page

Ian Smith (iansmith@cc.gatech.edu)