# problem4.txt # Dan R. K. Ports # 6.170 PS4, 2003/03/09 # $Id: problem4.txt,v 1.1 2004/03/09 05:38:02 dan Exp $ REQUIREMENTS No clarification necessary. DESIGN A BipartiteGraph is represented using Node objects. A Node contains a label (any Object) and a color, in addition to HashMaps of the parents and children of the node. The color is represented using a NodeColor class that has only two static instances (NodeColor.WHITE and NodeColor.BLACK). Each HashMap maps the edge label (an Object) to the parent or child Node at the other end of the edge. Two HashMaps mapping node labels to Node objects are maintained, whiteNodes and blackNodes. Each holds only nodes of one color. This representation allows lookup operations to be performed rapidly, generally in constant time. Searching for a node requires searching the whiteNodes and/or blackNodes hash tables, and finding parents or children of a node requires accessing the node's parents/children hash table. Both can be performed in constant time. A single nodes HashMap could be used instead of the separate whiteNodes and blackNodes; this would have simplified the implementation of some operations (e.g. the findNode() private helper function), but would have made whiteNodeIterator() and blackNodeIterator() significantly more complex. It would not have changed any asymptotic runtimes. An alternate implementation might have used a HashMap of edges, rather than maintaining edges as lists of parents and children for each node. This would have made it easy to look up whether a particular edge exists, but would have increased the runtime required to look up the parents or children for a particular node, operations we wished to optimize. TESTING Two sample graphs were created for use in testing. g1 was a copy of the graph from the problem set description; it makes a good test case because it includes several nodes and edges, including edges with the same labels. g2 was a simple graph with two nodes and one edge, with nodes and edges labeled using Integers. The graphs were first constructed (using the constructor and addNode/addEdge methods), then the observer methods were tested on them. The addNode and addEdge methods were further tested on g1, as well as the removeNode and removeEdge methods. All cases of invalid arguments that should throw exceptions were tested. The implementation passed all tests. ANALYSIS The BipartiteGraph class was successfully specified, implemented, and tested. Performance of all methods was satisfactory (though the checkRep call introduces considerable overhead). The interface provided includes a constructor, modifier functions for adding and removing edges, and observer methods that can check whether a node is in the graph, check a node's color, look up a node's parent or child by edge label, or obtain iterators. Iterators were provided for accessing the labels of the set of white nodes, the set of black nodes, the set of children of each node, and the set of parents of each node. These iterators allow efficient access to the lists, and could also be used to build a new collection of the labels. It might be helpful to have a few more methods. Being able to access the set of nodes as a collection rather than an iterator could be useful, and similarly it may be helpful to access the set of both white and black nodes together.