CS 2360
Winter 1998
Homework Assignment 5
Due no later than 8:00am, Monday, February 16, 1998
You've had your nose buried in your textbooks since the beginning
of the quarter, so you no doubt have missed most of the news,
but as we pointed out last week there's a bit of a scandal developing
in Washington D.C. right now. It seems that our president might have
been relating just a little bit too much with one particular intern,
and maybe he hasn't been all that truthful in talking about that
relationship, or maybe it's all an enormous but well-orchestrated
political smear campaign. Who knows?
Well, *you* might, if you had a handy-dandy information retrieval
system that could tell you who is related to whom, and how, in this
ever-growing and complex world of political and romantic intrigue.
In my never-ending mission to educate my students in all aspects
of popular culture, I've decided to let you learn by doing. In
this case, what you'll be doing is building some of that aforementioned
handy-dandy information retrieval system.
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 four 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 majors groups of information. One
information group contains attributes of that person (e.g., name,
political orientation, etc.), while the other group contains
relationships between that person and others in this relational
network. Here's what this first part looks like:
(defvar *database*
'(
(node001
(attributes
(name bill_clinton)
(politics liberal)
(occupation president_of_the_united_states))
(relations
(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
(relations
(kenneth_starr investigated-by)
(vernon_jordan friend-of)
(bill_clinton married-to))
(attributes
(politics liberal)
(occupation other_president_of_the_united_states)
(name hillary_clinton)))
(node003
(attributes
(occupation attorney)
(name vernon_jordan)
(politics liberal))
(relations
(hillary_clinton friend-of)
(monica_lewinsky helped)
(bill_clinton friend-of)
(kenneth_starr subpoenaed-by)))
(node004
(relations
(bill_clinton friend-of)
(linda_tripp friend-of)
(william_ginsburg represented-by)
(vernon_jordan helped-by)
(kenneth_starr subpoenaed-by))
(attributes
(politics liberal)
(occupation unemployed)
(name monica_lewinsky)))
(node005
(relations
(bill_clinton investigated)
(monica_lewinsky subpoenaed)
(william_ginsburg negotiated-with)
(vernon_jordan subpoenaed)
(hillary_clinton investigated)
(linda_tripp informed-by)
(betty_currie subpoenaed))
(attributes
(name kenneth_starr)
(occupation special_prosecutor)
(politics conservative)))
(node006
(attributes
(occupation civil_servant)
(politics conservative)
(name linda_tripp))
(relations
(monica_lewinsky friend-of)
(kenneth_starr informed)))
(node007
(attributes
(politics unknown)
(occupation personal_secretary)
(name betty_currie))
(relations
(bill_clinton employed-by)
(kenneth_starr subpoenaed-by)))
(node008
(relations
(monica_lewinsky represents)
(kenneth_starr negotiated-with))
(attributes
(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 next component of the database is just a list of the legal
names of attributes that a character may have. Thus, these labels
don't name relationships between people, they merely name
possibly useful or interesting features of a given person:
(defvar *attributes* '(occupation politics name))
This list, like all the others described here, could shrink
or grow, so you don't want to write code that's dependent on
the list looking just like this.
The third 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 fourth 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 six 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 list of attributes, the
fifth argument is the a-list of relationships, and the sixth argument is
the a-list of names and corresponding node identifiers.
For example,
(find-relationship
'monica_lewinsky 'betty-currie *database* *attributes* *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, 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
people -- you'll have to return a list of the names of the people
and the relationships that connect them.
As the scandal unfolds, 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 five arguments: the
properly constructed "node" to be added to the network, the relational
network, the list of attributes, 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
(attributes
(name lucianne_goldberg)
(occupation literary_agent)
(politics conservative))
(relations
(linda_starr represents))))
Then a call to "add-person" like this:
(add-character *test-node* *database* *attributes* *relations* *names*)
would return this updated network:
(
(
(node016
(attributes
(name lucianne_goldberg)
(occupation literary_agent)
(politics conservative))
(relations
(linda_tripp represents))))
(node001
(attributes
(name bill_clinton)
(politics liberal)
(occupation president_of_the_united_states))
(relations
(hillary_clinton married-to)
(monica_lewinsky friend-of)
(kenneth_starr investigated-by)
(vernon_jordan friend-of)
(betty_currie employs)))
(node002
(relations
(kenneth_starr investigated-by)
(vernon_jordan friend-of)
(bill_clinton married-to))
(attributes
(politics liberal)
(occupation other_president_of_the_united_states)
(name hillary_clinton)))
(node003
(attributes
(occupation attorney)
(name vernon_jordan)
(politics liberal))
(relations
(hillary_clinton friend-of)
(monica_lewinsky helped)
(bill_clinton friend-of)
(kenneth_starr subpoenaed-by)))
(node004
(relations
(bill_clinton friend-of)
(linda_tripp friend-of)
(william_ginsburg represented-by)
(vernon_jordan helped-by)
(kenneth_starr subpoenaed-by))
(attributes
(politics liberal)
(occupation unemployed)
(name monica_lewinsky)))
(node005
(relations
(bill_clinton investigated)
(monica_lewinsky subpoenaed)
(william_ginsburg negotiated-with)
(vernon_jordan subpoenaed)
(hillary_clinton investigated)
(linda_tripp informed-by)
(betty_currie subpoenaed))
(attributes
(name kenneth_starr)
(occupation special_prosecutor)
(politics conservative)))
(node006
(attributes
(occupation civil_servant)
(politics conservative)
(name linda_tripp))
(relations
(lucianne_goldberg represented-by) ;; this was added
(monica_lewinsky friend-of)
(kenneth_starr informed)))
(node007
(attributes
(politics unknown)
(occupation personal_secretary)
(name betty_currie))
(relations
(bill_clinton employed-by)
(kenneth_starr subpoenaed-by)))
(node008
(relations
(monica_lewinsky represents)
(kenneth_starr negotiated-with))
(attributes
(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 five arguments: the name of the person to be deleted,
the network, the attributes, 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.
Copyright 1998 by Kurt Eiselt. All rights reserved.
Last revised: February 11, 1998