Understanding Properties of Relations with C++

I’m going to attempt to explain relations and their different properties. This was a project in my discrete math class that I believe can help anyone to understand what relations are. Before I explain the code, here are the basic properties of relations with examples. In each example R is the given relation.

Reflexive – R is reflexive if every element relates to itself. {(1,1) (2,2)(3,3)}

Irreflexive – R is irreflexive if every element does not relate to itself. {(1,2) (1,3) (2,1) (2,3) (3,1) (3,2)}

Symmetric – R is symmetric if a relates to b (a->b), then b relates to a (b->a). {(1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2)}

Antisymmetric
– R is antisymmetric if a relates to b (a->b), and b relates to a (b->a), then a must equal b (a = b). {(3,2) (3,3)}
– is antisymmetric
  – is not antisymmetric

Asymmetric – if a relates to b (a->b), then b does not relate to a (b!->a). {(1,2) (3,1) (3,2)}

Transitive
– if a relates to b (a->b), and b relates to c (b->c), then a relates to c (a->c).
– is transitive
– is not transitive

Now that we understand the properties we can talk about the code. The code takes in one argument from the command line that is the file with the Relation. The file needs to contain the relation in a matrix form like the examples above with the first number the size of the matrix. Here is an example:

The file above would be the following relation: {(1,2) (2,3)}. There are spaces to separate each cell of the matrix. After given a relation the program will output which properties hold and which ones don’t. We can study the source code to see how to test for each condition. I do not claim this program to be the most efficient way to determine the different relation properties. Please leave in the comments any questions or ideas that you might have.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
/***************************************************************************
* Program:
*    Relations as Connection Matrices
* Author:
*    Don Page
* Summary:
*    Represents relations as connection (zero-one) matrices, and provides
*    functionality for testing properties of relations.
*
***************************************************************************/


#include <cmath>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <assert.h>
using namespace std;

class Relation
{
private:
bool** mMatrix;
int mSize;

void init()
{
mMatrix = new bool*[mSize];
for (int i = 0; i < mSize; i++)
{
mMatrix[i] = new bool[mSize];
}
}

public:
Relation(int size)
{
mSize = size;
init();
}

Relation& operator=(const Relation& rtSide)
{
if (this == &rtSide)
{
return *this;
}
else
{
mSize = rtSide.mSize;
for (int i = 0; i < mSize; i++)
{
delete [] mMatrix[i];
}
delete [] mMatrix;
init();
for (int x = 0; x < mSize; x++)
{
for (int y = 0; y < mSize; y++)
{
mMatrix[x][y] = rtSide[x][y];
}
}
}
return *this;
}

Relation(const Relation& relation)
{
mSize = relation.getConnectionMatrixSize();
init();
*this = relation;
}

~Relation()
{
for (int i = 0; i < mSize; i++)
{
delete [] mMatrix[i];
}
delete [] mMatrix;
}

bool isReflexive();
bool isIrreflexive();
bool isNonreflexive();
bool isSymmetric();
bool isAntisymmetric();
bool isAsymmetric();
bool isTransitive();
void describe();

int getConnectionMatrixSize() const
{
return mSize;
}

bool* operator[](int row) const
{
return mMatrix[row];
}

bool operator==(const Relation& relation)
{
int size = relation.getConnectionMatrixSize();
if (mSize != size)
{
return false;
}
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (mMatrix[i][j] != relation[i][j])
{
return false;
}
}
}
return true;
}

/****************************************************************************
* Returns product of 2 square matrices. Algorithm used from Rosen's Discrete
* Mathematics and Its Applications p.253
***************************************************************************/

Relation operator * (const Relation& relation)
{
// assume multiplying square matrices
assert(mSize == relation.getConnectionMatrixSize());
Relation product(mSize);
for (int i = 0; i < mSize; i++)
{
for (int j = 0; j < mSize; j++)
{
product.mMatrix[i][j] = 0;
for (int k = 0; k < mSize; k++)
{
product.mMatrix[i][j] = product.mMatrix[i][j] ||
(mMatrix[i][k] && relation.mMatrix[k][j]);
}
}
}

return product;
}

/****************************************************************************
* Matrix A is less than Matrix B iff there is a 1 in B everywhere there
* is a 1 in A
***************************************************************************/

bool operator <= (const Relation& relation)
{
for (int i = 0; i < mSize; i++)
{
for (int j = 0; j < mSize; j++)
{
if (mMatrix[i][j] && !relation.mMatrix[i][j])
return false;
}
}
return true;
}

};

ostream& operator<<(ostream& os, const Relation& relation)
{
int n = relation.getConnectionMatrixSize();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
os << relation[i][j] << " ";
}
os << endl;
}
return os;
}

istream& operator>>(istream& is, Relation& relation)
{
int n = relation.getConnectionMatrixSize();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
is >> relation[i][j];
}
}
return is;
}

/****************************************************************************
* Relation Member Functions
***************************************************************************/

/****************************************************************************
*  R is Reflexive if M[i][i] = 1 for all i
***************************************************************************/

bool Relation::isReflexive()
{
for (int i = 0; i < mSize; i++)
{
if (!mMatrix[i][i])
return false;
}
return true;
}

/****************************************************************************
*  R is Irreflexive if M[i][i] = 0 for all i
***************************************************************************/

bool Relation::isIrreflexive()
{
for (int i = 0; i < mSize; i++)
{
if (mMatrix[i][i])
return false;
}
return true;
}

/****************************************************************************
*  R is Nonreflexive if R is either not reflexive or not irreflexive. There
* is a more efficient way to test for nonreflexive, but for learning purposes
* I chose this inefficient way.
***************************************************************************/

bool Relation::isNonreflexive()
{
return (!(isReflexive() || isIrreflexive()));
}

/****************************************************************************
*  R is Symmetric if for each M[i][j] = 1 , M[j][i] = 1 for all i,j
***************************************************************************/

bool Relation::isSymmetric()
{
for (int x = 0; x < mSize; x++)
{
for (int y = 0; y < mSize; y++)
{
if (mMatrix[x][y] && !mMatrix[y][x])
return false;
}
}
return true;
}

/****************************************************************************
*  R is AntiSymmetric if for each M[i][j] = 1 and M[j][i] = 1, then i = j
*  for all i,j
***************************************************************************/

bool Relation::isAntisymmetric()
{
for (int x = 0; x < mSize; x++)
{
for (int y = 0; y < mSize; y++)
{
if (mMatrix[x][y] && mMatrix[y][x] && (x != y))
return false;
}
}
return true;
}

/****************************************************************************
*  R is Asymmetric if M[i][j] = 1, then M[j][i] != 1 for all i,j
***************************************************************************/

bool Relation::isAsymmetric()
{
for (int x = 0; x < mSize; x++)
{
for (int y = 0; y < mSize; y++)
{
if (mMatrix[x][y] && mMatrix[y][x])
return false;
}
}
return true;
}

/****************************************************************************
*  R is Transitive if R^2 <= R. Another way to test if a relation is
*  transitive would be if M[i][j] = 1, and M[j][k] = 1, then M[i][k] = 1.
*  This would require 3 nested for loops.
***************************************************************************/

bool Relation::isTransitive()
{
Relation relation = *this;
Relation product = relation * relation;
return (product <= relation);
}

/****************************************************************************
*  Describes the matrix after testing
*  Reflextivity, Irreflextivity, NonReflextivity, Symmetry, AntiSymmetry,
*  Asymmetry, and Transitivity
***************************************************************************/

void Relation::describe()
{
cout << "\nThe relation represented by the " << mSize << "x" << mSize << " matrix\n";
cout << *this << "is\n";
cout << (isReflexive() ? "" : "NOT ") << "Reflexive\n";
cout << (isIrreflexive() ? "" : "NOT ") << "Irreflexive\n";
cout << (isNonreflexive() ? "" : "NOT ") << "Nonreflexive\n";
cout << (isSymmetric() ? "" : "NOT ") << "Symmetric\n";
cout << (isAntisymmetric() ? "" : "NOT ") << "Antisymmetric\n";
cout << (isAsymmetric() ? "" : "NOT ") << "Asymmetric \n";
cout << (isTransitive() ? "" : "NOT ") << "Transitive.\n";
}

int main(int argc, char* argv[])
{
for (int i = 1; i < argc; i++)
{
string file = argv[i];
ifstream inFile(file.c_str());

if (inFile.is_open())
{
int size;
inFile >> size;
Relation relation(size);
inFile >> relation;
inFile.close();
relation.describe();
}
else
{
cout << "Unable to open " + file;
}
}

return 0;
}