CPTR 318 Data Structures and Algorithms

Relation Properties

Please read the remarks about programming problems for this course.

Chapter 2 in your textbook cover relations and their properties: reflexivity, symmetry, antisymmetry, and transitivity. Your task is to write individual functions that test whether or not a given binary relation ovre a finite set of integers exhibits these properties.

We will use the std::set and std::pair data types from the C++ standard library. The following C++ typedefs simplify their use:

// Some convenient type names typedef std::set<int> Set; typedef std::pair<int, int> Pair; typedef std::set<std::pair<int, int>> Relation;

Your task is to implement the following functions:

// Returns true if relation rel is reflexive; // otherwise, returns false // s is a set // rel is a binary relation on set s bool is_reflexive(const Set& s, const Relation& rel); // Returns true if relation rel is symmetric; // otherwise, returns false bool is_symmetric(const Relation& rel); // Returns true if relation rel is antisymmetric; // otherwise, returns false bool is_antisymmetric(const Relation& rel); // Returns true if relation rel is transitive; // otherwise, returns false bool is_transitive(const Relation& rel);

The header file relprop.h contains the necessary declarations. You should use the relprop.h file as is within your project and implement those functions in a file named relprop.cpp. You can use the code in RelationProperties.cpp to test your functions. You must ensure that the code you provide in your relprop.cpp file is compatible with both relprop.h and RelationProperties.cpp.

Within your relprop.cpp file you may write helper functions to assist the four functions above.

The supplied read_relation function in RelationProperties.cpp expects a text input stream with the following format:

n
e₁
e₂
e₃
.
.
.
e_n
<r₁,r₂>
<r₃,r₄>
<r₃,r₆>
<r₄,r₈>
.
.
.
<r_k,r_p>

where

n is the number of elements in the set.
e₁, e₂, e₃, ..., e_n are integers that are elements of the set.
<r₁,r₂>, <r₃,r₄>, <r₃,r₆>, ..., <r_k,r_p> are the ordered pairs that define a binary relation on the set; r₁,r₂, r₃, etc. are elements of the set.

You should ensure that the last line in any data files you create is the last ordered pair of the relation (if any); do not include any blank lines at the end of the data file.

For example, the text file

 3
 1
 2
 3
 <1,1>
 <1,2>
 <2,1>
 <1,3>
 <3,3>

processed by the read_relation function creates a Set object consisting of the three elements {1,2,3}, and a Relation object consisting of the ordered pairs {<1,1>,<1,2>,<2,1>,<1,3>,<3,3>}.

The supplied test program reports whether or not the relation exhibits the four properties. The example relation shown above is

not reflexive (it does not contain <2,2>),
not symmetric (<1,3> is in the relation, but <3,1> is not),
not antisymmetric (<1,2> and <2,1> are both in the relation, but 1 ≠ 2), and
not transitive (<2,1> and <1,2> but are both in the relation, but <2,2> is not).

You are encouraged to produce your own relation data files so you can test your function implementations. You are free to modify the testing code if you like, but you may not modify the relprop.h include file!

When you have completed your implementation of the relprop.cpp file please submit only your relprop.cpp file to http://eclass.e.southern.edu. Your relprop.cpp file should not contain any extraneous code that does not implement the functionality of the function prototypes declared in relprop.h. Specifically, your relprop.cpp file should not contain main (the main function is in the file implementing the testing code).