Handout P5

Quick links:

• Starter code
• Problem Set Submission

• Purpose
• Logistics
• Problem 1: Abstraction Functions and Representation Invariants in Graph (15 points)
• Problem 2: Reasoning About ADTs (15 points)
• Problem 3: Creating and Analyzing Object Models (30 points)
  • 3.1: Graph Models
  • 3.2: Mail Folders
  • 3.3: Network Links
  • 3.4: Diagramming Tool
• Problem 4: Diagramming MapQuick (20 points)
• Problem 5: Graph-Building (20 points)
• Q & A
• Change Log

Purpose

Abstract reasoning is important throughout all stages of developing a software system. Thus this problem set starts off with some development of your ability to reason abstractly about the properties of the code you write.

Object models are one method for visualizing a design, which can help you to spot design flaws. In this problem set, you will get experience working with object models, and then you will analyze the MapQuick problem using object models.

Finally, you will think ahead about MapQuick's graph-building algorithm.

Logistics

This problem set involves drawing several object models. Microsoft Visio (Windows only) and Dia (Athena, Solaris and Linux only) are programs which can be used for drawing such models and are available for your use. See the tools handout for details.

You are not, however, required to use computerized drawing packages for your diagrams; if you prefer, you may draw your models by hand and submit those diagrams hard-copy-only. If you do so, be sure to note this with the rest of your electronic turnin, and make your diagrams neat and easy to read.

For electronic submissions, use plain text for written solutions and PDF format for diagrams. We will not accept Visio or Dia files. Recall that distill (in the acro locker) converts PostScript files to PDF. Recall also that your Manifest file must list all files that you wish to submit. Any files not listed will not be considered for grading.

You may submit diagram PDF files either in one file per problem, named problem3.pdf, for instance, or you may submit them in separate files for each part, with an appropriate filename such as problem3.2a.pdf. Either way, note the location of each diagram in your plain text file.

Problem 1: Abstraction Functions and Representation Invariants in Graph (15 points)

In Problem Set 3, you specified and implemented a generic graph abstraction. Now write an abstraction function and a representation invariant for your graph ADT. Ensure that your overview and specfields correspond to a graph abstraction and not your implementation. If this is not the case first correct your graph specification. Make these changes directly in your ps3/Graph.java file. It should be listed in your Manifest file as ../ps3/Graph.java.

Using the abstraction function and representation invariant, answer the following questions in problem1.txt.

1. Argue that your implementation of Graph preserves its representation invariant.

2. Is it possible for two concrete states of your implementation of Graph to represent the same abstract state? If so, give an example; if not, briefly explain why this is impossible.

Problem 2: Reasoning About ADTs (15 points)

Consider the abstract data type outlined in IntegerSet.java.

1. Copy IntegerSet.java to ~/6.170/ps5/ and provide an implementation of this type (using the provided fields). Include an abstraction function and representation invariant. Your implementation of size should run in constant time. If you use private methods as part of your implementation, provide specifications for them as well. If you use loops, provide loop invariants and decrementing functions. You should naturally also implement your representation invariant as a checkRep method.
2. Explain carefully why the implementation preserves the representation invariant.
3. Explain carefully why the implementation satisfies the specification.

Place answers to parts (b) and (c) in problem2.txt.

Problem 3: Creating and Analyzing Object Models (30 points)

The exercises of this first part are intended to help you become familiar with the basic notions of object models, and to develop your understanding of how to pick appropriate abstractions for modeling a particular problem. Place your written solutions in problem3.txt. You will consider some rather abstract models for graphs and apply them to some concrete problems. All models you construct for this problem should be problem object models, not code object models.

3.1: Graph Models

Here are four object models that describe graphs.

Graph 1:

This model has a single domain, Node, representing the nodes of the graph, and a single relation adj that maps each node to the nodes it is adjacent to.

Graph 2:

This model has a second domain, Link, that represents the links between nodes; there is a single relation nodes that associates a link with the nodes it connect.

Graph 3:

This model is a variant that replaces the single relation with two relations.

Graph 4:

This model adds a domain, End, that represents the ends of a link. There are two relations, source and target, that map a link respectively to its source and target ends, and a relation node that associates an end with the node that it sits on.

These four models are not equivalent; they allow different kinds of graph to be described.

1. Which models can describe directed graphs?

2. Which models can accommodate multigraphs (graphs in which there may be more than one arc between a pair of nodes)?

3. Which models can accommodate hypergraphs (graphs in which an arc may connect more than two nodes)?

3.2: Mail Folders

Suppose you want to model how an email client stores messages in folders. The folder structure can be viewed as a graph, with an edge from a folder or message to the folder that contains it.

1. Construct an object model for this problem using Folders and Messages as domains.
2. Which of the following three constraints can be expressed graphically in your object model without introducing any new domains? For those that can, elaborate your model accordingly. You need not redraw your model, but you should label the addition with the number of the constraint. For those that can't be represented indicate whether it is a limitation of your choice of model (i.e. it could be expressed by sufficient restructuring of the model) or if the constraint cannot be expressed graphically at all. Explain.
   1. A message may belong to at most one folder.
   2. A folder that contains other folders may not itself contain messages.
   3. A folder may not contain itself.

   Now consider a classification where Folder and Message are both subdomains of Email Object, where email objects in turn can be stored in folders.

3. Construct an object model for the problem using this classification.
4. Explain which, if any, of the above constraints can no longer be expressed using this revised model.

3.3: Network Links

Suppose you want to model the topology of a network in which there are host machines with undirected links among hosts, and that an important concern is the bandwidth of the links.

1. Construct a minimal object model in these steps:
   1. Pick one of the four graph models as a starting point. You should select the least complex model that provides only notions you'll need, and no extraneous ones.
   2. Rename the sets and relations so that they are appropriate to this problem.
   3. Introduce new elements (that is, sets and relations) into the model to express the notion that links have bandwidth.

2. Which of the following constraints can be expressed graphically in an object model? For those that can, elaborate the model accordingly. You need not redraw your model, but you should label the addition with the number of the constraint.
   1. Every machine is on at least one link.
   2. There is at most one link between a given pair of machines.
   3. The bandwidth of a link does not change over time.

3.4: Diagramming Tool

Suppose you are designing a new diagramming tool, and you want to model the kinds of diagram that are to be produced. Diagrams are constructed from components, namely boxes and arrows, which can optionally be labelled. An arrow must be connected to a box at each end, and can be labelled in the middle and at each end. Components can be grouped; groups may carry labels and can themselves be grouped.

1. Construct a minimal object model in these steps:
   1. Pick one of the four graph models as a starting point. You should select the least complex model that provides only notions you ll need, and no extraneous ones.
   2. Rename the sets and relations so that they are appropriate to this problem.
   3. Introduce new elements (that is, sets and relations) into the model to express the notion that diagram components may have labels and may be grouped. Hint: consider classifying diagram parts into those that can be labelled and those that can be grouped.

2. Which of the following constraints can be expressed graphically in an object model? For those that can, elaborate the model accordingly.
   1. A component may belong to at most one group.
   2. Two components may not share the same label.
   3. Component within the same group may not share the same label.
   4. One can create new groups, but cannot change which components belong to an existing group.

Problem 4: Diagramming MapQuick (20 points)

Develop a Problem Object Model for MapQuick. You must use the following domains in your model: Length, Angle, Location, Path, Street, Number, Zip-code, Address, and Name. You may add other domains as you see fit. Be careful not to develop a Code Object Model; the goal is to understand the abstract problem domain.

For each of the domains (those provided and those you add) and each of the relations among them, write a textual description describing its role in the model. Your model should also include textual descriptions of constraints that cannot be expressed graphically. Submit your written solution in problem4.txt.

Problem 5: Graph-Building (20 points)

In Problem Set 6, you will build a graph-based representation of the streets in the MapQuick database.

Consider the following pseudo-code to build such a graph from a collection of StreetSegments:

for each segment s in the collection of segments
  s_r <- reverse of s
  add s to the set of nodes
  add s_r to the set of nodes
 
for each segment s in the set of nodes
  for each segment s' in the set of nodes
    if s.p2 = s'.p1
      add an edge from s to s'
    else if s.p1 = s'.p2
      add an edge from s' to s

Note: We are ignoring the issue of one-way streets. Thus, we are assuming that all street segments in the database allow bidirectional travel and are therefore placing both a segment and its reverse in the set of nodes.

Unfortunately, this algorithm requires quadratic time in the number of segments. For MapQuick, this is unacceptable due to the large number of segments in the database.

Give a more efficient algorithm to build the graph. Your algorithm should run in time O(n*outDegree) where n is the number of segments and outDegree is the maximum number of segments a single segment connects to. Describe your algorithm in problem5.txt and argue that it meets the specified time bound.

Feel free to use pseudo-code and to introduce auxiliary data structures or helper procedures as necessary.

Q & A

This section will list clarifications and answers to common questions about problem sets.

Saturday, March 17, 2001

Q: Do we need to write a checkRep() method for Graph?

A: You're not required to for PS5, but you'll want to have it for PS6. So we suggest you write it now while the AF/RI are still fresh in your memory, but you won't be graded on it for this pset.

Change Log

This section details the changes made since the handout was posted to the website. You may use the version number at the bottom of your hardcopy to determine what has changed since you printed this handout.

revision 1.34:	Updated Problem 1b to clarify that we're talking about two concrete states of your implementation. Also added Q & A section.
revision 1.32:	Stated explicitly that Problem 3 refers to problem object models, not code object models.
revision 1.31:	Changed ps3/Graph.java turnin method. See Problem 1. Moved IntegerSet.java out to its own file. Created a starter Manifest file. Also added point distributions.