C++/Discrete Structures 2 Read a matrix from a file into a two dimensional array

Question

C++/Discrete Structures 2 Read a matrix from a file into a two dimensional array and ignore curly brackets and commas. The file is in the format of {{row}, {row}, ....} Then I want to find the reflexive closure, symmetrix closure, and using Warshall's alogirthm find the transitive closure. Put that all into one matrix and cout the matrix just as I was given it(Format of {{row}, {row}, {row}, {row}....}). The input file will look like this

input.txt:

So I want to ignore the letters, the curly brackets, and the commas. Then just the numbers read into a two dimensional array to create an easily accessible 5x5 matrix.

Explanation / Answer

The reflexive closure of a binary relation R on a set X is the smallest reflexive relation on X that contains R. For example, if X is a set of distinct numbers and x R y means "x is less than y", then the reflexive closure of R is the relation "x is less than or equal to y".

Symmetric closure:

The symmetric closure of a binary relation R on a set X is the smallest symmetric relation on X that contains R. For example, if X is a set of airports and xRy means "there is a direct flight from airport x to airport y", then the symmetric closure of R is the relation "there is a direct flight either from x to y or from y to x". Or, if X is the set of humans (alive or dead) and R is the relation 'parent of', then the symmetric closure of R is the relation "x is a parent or a child of y".

Let MRMR denotes the matrix representation of R. Take W0=MR,W0=MR, We have

W0=MR=1001011001101001W0=MR=(1001011001101001) and n=4n=4 (As MRMR is a 4×44×4 matrix)

We compute W4W4 by using warshall's algorithm.

For k=1. In column 1 of W0W0, ‘1’ is at position 1, 4. Hence p1=1,p2=4p1=1,p2=4.

In row 1 of W0W0 ‘1’ is at position 1, 4. Hence q1=1,q2=4q1=1,q2=4.

Therefore, to obtain W1W1, we put ‘1’ at the position:

{(p1,q1),(p1,q2),(p2,q1),(p2,q2)=(1,1),(1,4),(4,1),(44)}{(p1,q1),(p1,q2),(p2,q1),(p2,q2)=(1,1),(1,4),(4,1),(44)}. Thus,

W1=1010000001101111W1=[1001001110110001]

For k=2. In column 2 of W1W1, ‘1’ is at position 2, 3. Hence p1=2,p2=3p1=2,p2=3.

In row 2 of W1W1 ‘1’ is at position 2, 3. Hence q1=2,q2=3q1=2,q2=3.

Therefore, to obtain W2W2, we put ‘1’ at the position:

{(p1,q1),(p1,q2),(p2,q1),(p2,q2)=(2,2),(2,3),(3,2),(3,3)}{(p1,q1),(p1,q2),(p2,q1),(p2,q2)=(2,2),(2,3),(3,2),(3,3)}. Thus,

W2=1010000001101111W2=[1001001110110001]

For k=3. In column 3 of W2W2, ‘1’ is at position 2, 3. Hence p1=2,p2=3p1=2,p2=3.

In row 3 of W2W2 ‘1’ is at position 2, 3. Hence q1=2,q2=3q1=2,q2=3.

Therefore, to obtain W3W3, we put ‘1’ at the position:

{(p1,q1),(p1,q2),(p2,q1),(p2,q2)=(2,2),(2,3),(3,2),(3,3)}{(p1,q1),(p1,q2),(p2,q1),(p2,q2)=(2,2),(2,3),(3,2),(3,3)}. Thus,

W3=1010000001101111W3=[1001001110110001]

For k=4. In column 4 of W3W3, ‘1’ is at position 1, 4. Hence p1=1,p2=4p1=1,p2=4.

In row 4 of W3W3 ‘1’ is at position 1, 4. Hence q1=1,q2=4q1=1,q2=4.

Therefore, to obtain W3W3, we put ‘1’ at the position:

{(p1,q1),(p1,q2),(p2,q1),(p2,q2)=(1,1),(1,4),(4,1),(44)}{(p1,q1),(p1,q2),(p2,q1),(p2,q2)=(1,1),(1,4),(4,1),(44)}. Thus,

W4=1010000001101111W4=[1001001110110001]

Thus, the transitive clousure of R is given as

R= {(1, 1), (1, 4), (2, 2), (2, 3), (3, 2), (3, 3), (4, 1), (4, 4)}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.