CS246 [Winter 2010] Assignment 4. 

Version 0.3, 09 Feb 2010

Version 0.4, 15 Feb 2010

Version 0.5, 29 Feb 2010 (See note added below on the “p” command, at the end of this document)

 

Beware: Expect some changes to occur in this assignment.  Further changes are not expected.

 

Binary relations as an abstraction

You are to create software to manipulate binary relations such as

love:  { (Bob, Jane), (Jane, Fred) }

This relation, call it the “love” relation, can be read as: Bob loves Jane and Jane loves Fred.  This relation is a set of two pairs, the first pair is Bob and Jane and the second pair is Jane and Fred.  Pairs are ordered (so even if Bob loves Jane, Jane may not love Bob).  Relations are unordered sets, so the “love” relation can also be written equivalently as

{ (Jane, Fred), (Bob, Jane) }

Since a relation is a set, a relation, such as “love”, cannot contain more than one copy of the same pair.

 

You will implement a data abstraction, which is the concept of a binary relation, which can also be thought of as a table, e.g.,

 

love:

SOURCE

TARGET

Bob

Jane

Jane

Fred

 

To keep things simple, we sometimes write a relation such as “love” as simply:

love:

  Bob  Jane

  Jane  Fred

 

Here is another relation, the “like” relation

like:

  Bob  George

  Bob  Jane

In general, a binary relation contains zero or more pairs.  For this assignment, each item in the pair, such as Bob or George, is a string of characters.

 

The operations on binary relations include union (+), subtraction (-) and composition.  For example, for the “love” and “like” relations (see above), the union of “like” and “love”, written as like + love, is as follows:

like+love:

  Bob  Jane

  Jane Fred

  Bob George

 

Relations can be subtracted, so the relation written as like-love contains all those pairs in like but not in love:

like-love:

  Bob George

We can interpret this to mean that Bob likes George but he does not love him.

 

Another operation is called composition (or join), e.g., like*love.  If person p likes someone and that someone loves q then the pair p q is in the relation like*love as shown here.

like*love:

  Bob Fred

We can interpret this to mean that Bob likes someone who loves Fred.  (That someone is Jane in this example.)

 

We will sometimes call a binary relation simply a relation.

 

Implementation of binrel class

Write a C++ class called binrel that supports operations such as +, - and * on binary relations. Each object of the class represents a binary relation.  Within each object that represents a relation is a C++ vector of pairs of strings, one pair of strings for each pair in the represented relation.  The size of the vector gives the cardinality (number of pairs) of the represented relation.  All relations are initially be empty. 

 

The interface to the binrel class should be in the file binrel.h and its implementation should be in the file binrel.cpp.

 

This class should include the following public members:

void nullify ();                            // Make the binary relation have no pairs

bool isNull () const;                       // See if the binary relation has no pairs

void output();                              // Output in simple format

binrel& operator =(const binrel& rtSide);   // Assignment

binrel operator +(const binrel& rtSide);    // Union

binrel operator -(const binrel& rtSide);    // Subtraction

binrel operator *(const binrel& rtSide);    // Composition (binary join)

// There will be more functions here.

 

Implementation of the calculator

Your main program is used to manipulate relations.  It reads commands from the keyboard and produces output on the console.  One command is to create or “declare” a relation (initially empty) with a name such as love.   The main program  maintains a C++ vector of structs, whose two parts are the relation name and the relation’s value.  The value is an instance of the binrel class.

 

You program should make simple checks such as verifying that a relation is declared before it is used, reporting errors on the cerr stream.  All error messages should begin with the word ERROR.

 

The help command

The calculator outputs help information when you give it the ‘h’ command.  There is a function in help.cpp that prints out the list of commands.  You should study those files as they list commands that the calculator is to carry out.   Your main program should #include help.h.  Beware that the files help.h and help.cpp might change a bit.

 

Example calculator session

 

Below is an example interaction between a user and the relation calculator.

The parts in bold are typed by the user.

The parts in italics are data output by the program.

The other parts are prompts written by the program.

 

Welcome to binary relation calculator.  Type 'h' for help.

Command: d

Declare.  Give rel: love

Command: i

Insert pair.  Give rel src trg: love Bob Jane

Command: o

Output.  Give rel: love

Bob   Jane

Command: i

Insert pair.  Give rel src trg: love Jane Fred

Command: o

Output.  Give rel: love

Bob   Jane

Jane  Fred

Command: d

Declare.  Give rel: like

Command: i

Insert pair.  Give rel src trg: like Bob George

Command: i

Insert pair.  Give rel src trg: like Bob Jane

Command: o

Output.  Give rel: like

Bob   George

Bob   Jane

Command: +

Union.  Give relx rely relz: likeOrLove like love

  ERROR: No such rel 'likeOrLove'

Command: d

Declare.  Give rel: likeOrLove

Command: +

Union.  Give relx rely relz: likeOrLove like love

Command: o

Output.  Give rel: likeOrLove

Bob   George

Bob   Jane

Jane  Fred

Command: q

Quitting.

 

Nondeterminacy.  Relations are unordered sets of pairs.  (The strings in a pair are ordered, but the pairs in a relation are not ordered.)  So the order in which pairs are output for a given relation is, at least in principle, immaterial.  You may want to keep the pairs in order of age, i.e., so that those that added to the relation longest ago are generally output earliest, but this is not required.

Related files.  You will be given a compiled (master) solution to this assignment.  You can run this under a student account to see if your solution gives the same answers.  Your output  (except when there are user errors) from your program should be the same, character for character, as the master solution.  You can get this master solution on your student account using the Unix commands:

curl http://plg.uwaterloo.ca/~holt/cs/246/2010/asgn04/relcalcdir/masterrelcalc > masterrelcalc

chmod 700 masterrelcalc

You will be given the makefile and the header files which can be accessed in a similar way.   You should write you program so the makefile works on it.

See this URL for files available to you (some in that directory have purposely been make non-viewable by you.)  See also files script.* which

you can use for testing.

            http://plg.uwaterloo.ca/~holt/cs/246/2010/asgn04/relcalcdir

 

The assignment.  This assignment has two parts as follows:

Part 4a.  Implement relcalc as described above.

Part 4b.  Make your program so that if it is given a –q (quiet) flag, as in relcalc -q, then the calculator writes no prompts. such as “Command:” to the user.  But if requested by the h command, the help file is still printed.

 

Inconsistency.  As pointed out by a student, the “script.rel” file uses an extra command, the “p” (for print) that

is implemented in the distributed solution, but is not documented.  This command takes a string (not containing white space) and prints it, somewhat like a simplified version of the shell “echo” command.  The file “script.rel” uses this “p” command.  You have a choice.  You can either ignore the “p” command, removing the lines that use it from “script.rel”.  Or you can implement the “p” command, including documenting it in “help.cpp”, for a bonus of 2 points.