CS 2360
Fall 1995
Homework Assignment 4 
Due no later than 8:00am, Monday, October 30, 1995

"She's dead!...Wrapped in plastic!"  With those immortal words began the 
two-year search for Laura Palmer's killer.  That search would lead FBI 
Special Agent Dale Cooper to the Pacific Northwest town of Twin Peaks, 
home of fragrant pines, mighty fine cherry pie, and a great cup of 
coffee.  But beneath that idyllic facade, Agent Cooper would find an 
intricately woven web of relationships between some pretty bizarre 
characters: a dwarf who spoke backwards, a headdress-wearing teen who 
liked to bang his head against the wall, a really tall guy from outer 
space, a woman and her pet log, and a psychopath named Bob, to mention 
just a few.

As you might have surmised from the "Twin Peaks Who's Who" in "People" 
magazine we showed you last week, Agent Cooper could have used some help 
in keeping track of how everyone was related to everyone else in Twin 
Peaks.  Your assignment is to write a LISP program which searches for 
the relationship, however distant, between any two inhabitants of Twin 
Peaks.  The top-level function that Cooper will use is to be called 
"show-relationship", and this function will take three arguments.  The 
first two arguments are the names of two people who may be somehow 
related.  The third argument should be an expression which evaluates to 
an association list representing the information contained in the "Twin 
Peaks Who's Who" network.  In fact, we're feeling so generous these days 
that we're giving you the exact data structure we want you to use.  Here 
it is, ready to go (it's actually just a subset of the "Who's Who", and 
we've added a little bit of information):

(defun *database* () '(
                     (pete_martell      (wife catherine_martell))

                     (catherine_martell (husband pete_martell)
                                        (brother andrew_packard)
                                        (works_with fred_truax)
                                        (sleeps_with benjamin_horne))

                     (fred_truax        (works_with catherine_martell))

                     (benjamin_horne    (sleeps_with catherine_martell)
                                        (brother jerry_horne)
                                        (wife sylvia_horne)
                                        (son johnny_horne)
                                        (daughter audrey_horne))

                     (sylvia_horne      (husband benjamin_horne)
                                        (son johnny_horne)
                                        (daughter audrey_horne))

                     (johnny_horne      (father benjamin_horne)
                                        (mother sylvia_horne)
                                        (sister audrey_horne))

                     (audrey_horne      (father benjamin_horne)
                                        (mother sylvia_horne)
                                        (brother johnny_horne))

                     (jerry_horne       (brother benjamin_horne))

                     (andrew_packard    (sister catherine_martell)
                                        (married josie_packard))

                     (josie_packard     (married andrew_packard)
                                        (sleeps_with sheriff_truman))

                     (sheriff_truman    (sleeps_with josie_packard)
                                        (works_with deputy_andy)
                                        (works_with lucy_moran)
                                        (works_with deputy_hawk)
                                        (works_with mayor_milford))

                     (deputy_andy       (works_with sheriff_truman)
                                        (sleeps_with lucy_moran)
                                        (works_with lucy_moran))

                     (lucy_moran        (sleeps_with deputy_andy)
                                        (works_with deputy_andy)
                                        (works_with sheriff_truman)
                                        (works_with deputy_hawk))

                     (deputy_hawk       (works_with sheriff_truman)
                                        (works_with lucy_moran))


                   )
      )

For example,

  (show-relationship 'pete_martell 'fred_truax (*database*))

should return something like

  (PETE_MARTELL WIFE CATHERINE_MARTELL WORKS_WITH FRED_TRUAX)

If no relationship can be found, simply return NIL.  If more than one 
chain of relations can be found, then just return the first one found.

To implement this, use a depth-first search algorithm.  You've already 
had some exposure to depth-first search:  it's the same as a preorder 
traversal.  However, there are a few wrinkles which make this problem 
more complex than just plain old vanilla preorder traversal.  First, 
this data structure isn't a tree.  That is, this data structure has 
cycles, which means you have to figure out how to keep your program from 
searching around and around through the same cycle.  Second, it won't be 
enough to just return T when you find a relationship between two Twin 
Peaks inhabitants--you'll have to return a list of the labels on the 
"nodes" and "links" joining the two inhabitants.  While that's not all 
too difficult, it is a bit different from what you've been asked to do 
so far.

Make sure that your program is the pinnacle of good design, good 
documentation, and good abstraction.  When it comes to grading this 
thing, there's going to be more emphasis on how well we understand what 
you were trying to do than there will be on how well the program works.



-- 


Kurt Eiselt
Assistant Dean, Student Services
College of Computing
Georgia Institute of Technology
Atlanta, GA 30332-0280

http://www.cc.gatech.edu/aimosaic/faculty/eiselt.html