CS 2360
Fall 1998
Homework Assignment 5
Due no later than 8:00am, Monday, November 2, 1998
We mentioned today in class that the weekly news journal "Newsweek"
had employed relational networks to explain complicated, multi-
character relationships such as those that exist between the all
the folks involved in that Monica Lewinsky thing (hmm, that's
not a good name...I'll give it more thought). But being the computer
science (or computer engineering) geek that you are, you've never
even touched a copy of "Newsweek", preferring to ponder the letters
from incarcerated readers that you find in the back of the infrequent
issue of "2600".
In my never-ending mission to educate my students in all aspects
of popular culture, I've decided to give you the opportunity to learn
about this complex world of political and romantic intrigue by
building an information retrieval system for the domain of
"President Clinton's Hobby" (that's better).
We've already encoded some of the basic knowledge for this database
system, as shown below. It's not complete, and we may add to it before
the due date, so you'll want to make sure your code relies as little
as possible on specific details in the database.
Your task is to construct, in Common LISP, three functions which
will comprise the backbone for this system. But let's get back to
the database, which actually consists of three parts. The first part
is a relational network (encoded as a big association list) in which
each node is a brief description of a person in "Bill's Wacky
World of Presidential HiJinks" (?). Each description is indexed by a
node number and contains two types information. One information type
consists of attributes of that person (e.g., name, political orientation,
etc.), while the other type consists of relationships between that person and
others in this relational network. Here's what this first part looks like:
(defvar *database*
'(
(node001
(name bill_clinton)
(politics liberal)
(occupation president_of_the_united_states)
(hillary_clinton married-to) ;;is married to hillary
(monica_lewinsky friend-of) ;;is a friend of monica
(kenneth_starr investigated-by) ;;has been investigated by kenneth
(vernon_jordan friend-of) ;;is a friend of vernon
(betty_currie employs)) ;;employs betty
(node002
(kenneth_starr investigated-by)
(vernon_jordan friend-of)
(bill_clinton married-to)
(politics liberal)
(occupation other_president_of_the_united_states)
(name hillary_clinton))
(node003
(occupation attorney)
(name vernon_jordan)
(politics liberal)
(hillary_clinton friend-of)
(monica_lewinsky helped)
(bill_clinton friend-of)
(kenneth_starr subpoenaed-by))
(node004
(bill_clinton friend-of)
(linda_tripp friend-of)
(william_ginsburg represented-by)
(vernon_jordan helped-by)
(kenneth_starr subpoenaed-by)
(politics liberal)
(occupation unemployed)
(name monica_lewinsky))
(node005
(bill_clinton investigated)
(monica_lewinsky subpoenaed)
(william_ginsburg negotiated-with)
(vernon_jordan subpoenaed)
(hillary_clinton investigated)
(linda_tripp informed-by)
(betty_currie subpoenaed)
(name kenneth_starr)
(occupation special_prosecutor)
(politics conservative))
(node006
(occupation civil_servant)
(politics conservative)
(name linda_tripp)
(monica_lewinsky friend-of)
(kenneth_starr informed))
(node007
(politics unknown)
(occupation personal_secretary)
(name betty_currie)
(bill_clinton employed-by)
(kenneth_starr subpoenaed-by))
(node008
(monica_lewinsky represents)
(kenneth_starr negotiated-with)
(occupation attorney)
(name william_ginsburg)
(politics unknown))
))
The implementation of this network leaves much to be desired. For
example, we're used to seeing ([relation] [node]) when describing
relationships between nodes, but above we see ([node] [relation]).
Don't try to fix the database; the organization may not be
convenient, but it's what you must work with. If this were the
"real world" there might be lots of other folks who depend on
the network looking just like it does. So don't change it.
Furthermore, don't "pre-process" a copy of the network and
turn it into something else that you like better every time
you call one of the new functions that you're going to construct.
That could be extremely time-consuming if this network were huge.
Just deal with the network as it is.
The second component of the database is another a-list, but
this one contains all the names of relationships which may exist
between any two persons in the presidential soap opera. Associated
with each of the relationships which may lead from person A
to person B is the corresponding relationship which must lead
from person B to person A. For example, the relationship
"subpoenaed" leads from node005 ("kenneth_starr") to node004
("monica_lewinsky"), so there must be a "subpoenaed-by" relationship
leading from node004 ("monica_lewinsky") to node005 ("kenneth_starr").
In other words, Kenneth Starr subpoenaed Monica Lewinsky, so Monica
Lewinsky was subpoenaed by Kenneth Starr. Here's how that information
looks:
(defvar *relations* '((married-to married-to)
(friend-of friend-of)
(helped helped-by)
(helped-by helped)
(employs employed-by)
(employed-by employs)
(...you add a pair here...)
(...and the reverse of the pair here...)
...keep doing that until done...
))
The third and final component of the database is yet another a-list
that maps the names of people to their corresponding node numbers:
(defvar *names*
'((bill_clinton node001)
(vernon_jordan node003)
(betty_currie node007)
:
:
))
One LISP program you'll have to write is one which searches for a
relationship, however distant, between any two people in this
scandal. The top-level function here will be called "find-relationship",
and this function takes five arguments. The first two arguments are the
names of two characters who may be somehow related. The third argument is
the relational network, the fourth argument is the a-list of relationships,
and the fifth argument is the a-list of names and corresponding node identifiers.
For example,
(find-relationship
'monica_lewinsky 'betty-currie *database* *relations* *names*)
should return something like
(MONICA_LEWINSKY SUBPOENAED-BY KENNETH_STARR SUBPOENAED BETTY_CURRIE)
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 function, use a depth-first search algorithm.
As impeachment draws near, you'll undoubtedly want to add new people to
the database, so you'll have to construct the appropriate function, which
you'll call "add-person". This function will take four arguments: the
properly constructed "node" to be added to the network, the relational
network, the a-list of relations, and the a-list of names and nodes.
This function will return an enormous two-element list. The first element
of the list will be the updated relational network with the new node added in
somewhere (the order of the people in the network doesn't matter) and with the
appropriate links to the new node inserted in the correct neighboring nodes
(your function will have to construct these from the information passed to it;
the order of the links within a character's node doesn't matter either). The
second element of the two-element list that will be returned is an updated
name/node list. For example, let's assume the existence of a test node:
(defconstant *test-node*
'(node016
(name lucianne_goldberg)
(occupation literary_agent)
(politics conservative)
(linda_tripp represents)))
Then a call to "add-person" like this:
(add-character *test-node* *database* *relations* *names*)
would return this updated network:
(
(
(node016
(name lucianne_goldberg)
(occupation literary_agent)
(politics conservative)
(linda_tripp represents))
(node001
(name bill_clinton)
(politics liberal)
(occupation president_of_the_united_states)
(hillary_clinton married-to)
(monica_lewinsky friend-of)
(kenneth_starr investigated-by)
(vernon_jordan friend-of)
(betty_currie employs))
(node002
(kenneth_starr investigated-by)
(vernon_jordan friend-of)
(bill_clinton married-to)
(politics liberal)
(occupation other_president_of_the_united_states)
(name hillary_clinton))
(node003
(occupation attorney)
(name vernon_jordan)
(politics liberal)
(hillary_clinton friend-of)
(monica_lewinsky helped)
(bill_clinton friend-of)
(kenneth_starr subpoenaed-by))
(node004
(bill_clinton friend-of)
(linda_tripp friend-of)
(william_ginsburg represented-by)
(vernon_jordan helped-by)
(kenneth_starr subpoenaed-by)
(politics liberal)
(occupation unemployed)
(name monica_lewinsky))
(node005
(bill_clinton investigated)
(monica_lewinsky subpoenaed)
(william_ginsburg negotiated-with)
(vernon_jordan subpoenaed)
(hillary_clinton investigated)
(linda_tripp informed-by)
(betty_currie subpoenaed)
(name kenneth_starr)
(occupation special_prosecutor)
(politics conservative))
(node006
(occupation civil_servant)
(politics conservative)
(name linda_tripp)
(monica_lewinsky friend-of)
(kenneth_starr informed)
(lucianne_goldberg represented-by)) ;; this was added
(node007
(politics unknown)
(occupation personal_secretary)
(name betty_currie)
(bill_clinton employed-by)
(kenneth_starr subpoenaed-by))
(node008
(monica_lewinsky represents)
(kenneth_starr negotiated-with)
(occupation attorney)
(name william_ginsburg)
(politics unknown))
)
(
(lucianne_goldberg node016) ;; this was added
(bill_clinton node001)
(vernon_jordan node003)
(betty_currie node007)
:
:
)
)
Similarly, we might want to delete people from the database as necessary.
Thus, if we wanted to delete the president's secretary, Betty Currie,
we'd invoke the "delete-person" function you're going to write. This
function also takes four arguments: the name of the person to be deleted,
the network, the relations, and the name/node list. This function returns a
two-element list. The first element is the relational network with the
designated person's node deleted. Also missing from that network will be
any links from other nodes to the deleted person. The second element is the
updated name/node a-list with the name/node pair for the deleted person
now missing.
The hard part in these latter two functions is dealing with the links
from the related nodes to the node being added or deleted. These
"backlinks" will either have to be constructed from given information
and inserted in the right places (when using "add-person") or
located from given information and deleted (when using "delete-
person"). A simple way to delete all backlinks in the example
above would be to do a more-or-less linear search through *database*
and remove any link that ended with the person being deleted. Don't do
that. One of the goals of this assignment is to give you experience in
tearing apart and putting together complex list structures in just the
right places, so use the information passed to the add and delete
functions to locate the right places to add stuff and the right things
to be deleted.
If you find inconsistencies in the various parts of the database,
post to the newsgroup. It's likely that we'll have to make some fixes.
Also, there will probably be a few things I just plain forgot in this
problem description so stay flexible. Specifications will possibly change
in small ways, just like in the real world. Check the newsgroup
frequently for updates. Make sure that your program is the pinnacle of
good design, good documentation, and good abstraction. Employing that
good abstraction will make it easier for you to adapt to specification
changes as they come up. You're still constrained by the functional
programming paradigm, but so long as you stay within the boundaries
of that paradigm feel free to use any predefined LISP functions that
you've already encountered in lectures or homework (you can even use
the "real" versions of functions that you've had to construct on your
own until now).
Copyright 1998 by Kurt Eiselt. All rights reserved.
Last revised: October 28, 1998