CSE100
Project #3
Due: 2008-11-13 THURSDAY 11:59:00PM PDT.
Update 11/5/08 by Cynthia Lee:
- Requirements vs. suggestions: I'd like to be more clear about what is absolutely required and what is up to you. Specifically, the data structures under "Your Graph class should contain the following:" are suggestions. It is strongly suggested that you follow the suggestions, both for your own sake, and so we're all talking about the same thing on the webboard (in PA2 there was some confusion on the webborad from people who were doing things that were fine but not required and other students reading discussion of that and thinking it was required). But, strictly speaking, grading will not be based on following the suggestions for the internals of the Graph class. However, the Graph class must have the interface described, namely the things under "Your Graph class must also support the following operations:" and "Graph Algorithms." Although the specifics of the internals should be reasonable and follow algorithms described in class (i.e., could work on a large data file in reasonable time). Hope that clears things up.
Social Networking
We have gathered a small fragment of a social network from the popular
service, NerdBook. In addition to the usual "X and Y are friends"
functionality, NerdBook allows its users to specify how well they get along
with each-other. This works by having each pair of friends to set a
disagreement score. The disagreement score is a non-negative number,
where 0 indicates total agreement, and larger values indicate more
disagreement between the two friends.
This information is encoded in the form of a weighted, undirected graph over
the users of the service. We provide this information to you in the
form of two text files in the public directory:
-
nodes.txt contains the names of the users, one per line
-
edges.txt contains the edges of the graph, one per line, e.g.
0 21 4.973
4 9 0.55
indicates that the first user (index 0, the first row in nodes.txt) shares
an edge with user 21 (22nd row in nodes.txt), and their disagreement score
is 4.973. Similarly, user index 4 shares an edge with user index 9,
with disagreement score 0.55.
Note that these indices are only there to help
with reading the file, and should not appear anywhere in your graph
implementation!
Your program will use this information to construct a graph and solve a few
socially-oriented problems.
Graph Data Structure
The first step is to implement a generic-typed graph class: Graph<E>,
where E is the type of data stored in the vertices. Your Graph class
should contain the following:
-
a Set<E> to contain the vertices of the graph.
- EDIT 2008-11-05:
a Map<E, Collection<WeightedEdge>>, which contains the
adjacency-list representation of the graph's edges. Remember, this
graph is undirected, so each edge (A,B) should appear in the adjacency
lists for both A and B. The choice of collection structure is up to you (just a plain Vector is fine, there are other possibilities).
a Map<E, SortedSet<WeightedEdge>>, which contains the
adjacency-list representation of the graph's edges. Remember, this
graph is undirected, so each edge (A,B) should appear in the adjacency
lists for both A and B.
-
a public inner class WeightedEdge<E>, which contains one
vertex, and the weight of the edge. You should provide setters and
getters for the vertex and weight variables. Your WeightedEdge set
should implement Comparable, and use the natural ordering over weight
for its comparison.
-
(You should make wise, informed decisions about which particular
implementations of the Set, Map or collections interfaces to select for
use in your project. There is no need to write your own
implementation--though remember that TreapSet is among your options!)
Your Graph class must also support the following operations:
-
void addVertex(E v): adds v as a new vertex into the graph. If v
was already in the graph, this should do nothing.
-
void removeVertex(E v): removes the vertex v from the graph, as well as
all of its edges. If v was not in the graph, this should do
nothing.
-
void addEdge(E v1, E v2, double weight): adds an edge between v1 and v2,
with the specified weight. If either of the specified vertices are
not in the graph, throw an IllegalArgumentException. If the edge
is already in the graph, update its weight with the new weight.
-
void removeEdge(E v1, E v2): removes an edge (if one exists) between v1
and v2. If either of the specified vertices are not in the graph,
throw an IllegalArgumentException. If the edge is not in the
graph, do nothing.
-
Collection<E> getVertices(): returns a collection of the vertices
in the graph.
-
Collection<WeightedEdge<E>> getEdges(E v): returns a
collection of the vertices adjacent to v in the graph, along with their
edge-weights.
-
double getEdgeWeight(E v1, E v2): returns the weight of the edge between
v1 and v2. If either of the specified vertices are not in the
graph, throw an IllegalArgumentException. If they are in the
graph, but there is no edge, return Double.POSITIVE_INFINITY.
Graph Algorithms
In addition to the basic graph operations described above, your Graph
structure must also implement the following graph algorithms:
-
LinkedList<E> shortestUnweightedPath(E s, E t): returns the
shortest unweighted path from s to t. This path should start with
s and end with t.
-
LinkedList<E> shortestWeightedPath(E s, E t): returns the shortest
weighted path from s to t in the graph as a vector of nodes.
-
Graph<E> shortestUnweightedPathTree(E s): returns a new graph
containing the unweighted shortest path tree rooted at s.
-
Graph<E> shortestWeightedPathTree(E s): returns a new graph
containing the weighted shortest path tree rooted at s.
-
Graph<E> minimumSpanningTree(): returns a new graph containing the
minimum spanning tree over the original graph.
Application
Having implemented the algorithms described above, you must write a program
which solves the following problems:
-
To prevent spam, NerdBook only allows you to send messages to your
friends. You will design a way to work around this limitation by sending
messages from friend to friend to reach people who are not directly the
sender's friends. You would like to do this in as few steps as possible,
so that the fewest people will be bothered with having to forward the
message. So person X wants to send a message to a person Y using the
smallest number of intermediate people possible. Determine the shortest
sequence of people to transmit the message from X to Y.
For each person X in the graph, print out their shortest sequence to
each other person Y. Your output should look something like:
Samuel Baden -> Alin Bafna
Samuel Baden -> Alin Bafna -> Jim Bellare
Samuel Baden -> Alin Bafna -> Dana Cottrell
...
(the exact edges may be different in the actual graph).
-
A person X wants to interview for a job with person Y. X wants to
get her foot in the door with a personal recommendation, but may not
directly know person Y, and thus wants to find a chain of
recommendations to Y. Find the chain from X to Y with the minimal
cumulative disagreement score. Cumulative disagreement means the
sum of the disagreements scores along the path from X to Y.
Again, for each person X in the graph, print out their minimal
cumulative disagreement score path to each other person Y.
-
NerdBook provides a "People you may know" feature. For a given person X,
return the top five (or up to five, if fewer than five exist) people in
NerdBook who have the smallest cumulative disagreement, but are not
currently friends with X. Order the top five people according to
cumulative disagreement, smallest first (use sorted list or priority
queue).
Print out each person X along with their top five recommended friends.
-
You
want to measure the amount of group cohesion within the
network. Do this by finding a subset of the edges in which all
nodes are connected, and the total amount of disagreement is minimized.
Report the total amount of disagreement.
Your program should operate as follows:
java NerdBook
<message|interview|recommender|cohesion>
where the parameter indicates which of the four problems described above is to
be solved.
Guidelines
-
Work in teams of 2 people.
-
Include a file named README, which contains the names of your team
members, and your benchmarking results and analysis/discussion.
-
Your code must be thoroughly documented with javadoc.
-
Use good OO design and engineering practice. Use exceptions where
appropriate. Design your methods and data structures BEFORE you
start coding.
-
You should have at least two source files:
-
Graph.java: your Graph class implementation
-
NerdBook.java: the driver application
Turning in
When your program is finished, create a tar file including your source
code and class files by running:
tar czvf LASTNAME1.LASTNAME2.tar.gz *.java
*.class README
Then, submit your tar file by running:
turnin -c cs100f -p p3 LASTNAME1.LASTNAME2.tar.gz