c++ Transitive Relation Function

[ashworcp]

I am having trouble writing my transitive relation function. I have written reflexive, symmetric and anti-symmetric but cannot figure out transitive. I am trying to use this method of testing it:

transitive:
set holds to true
for each pair(e,f) in b
for each pair(f,g) in b
if pair(e,g) is not in b
set holds to false
break
if holds is false
break

I have developed a pair in relation function:

bool pair_is_in_relation(int left, int right, int b[], int sizeOfB)
{
    for(int i=0; i+1<sizeOfB; i+=2) {
        if (b[i]==left && b[i+1]==right)
            return true;
    }
    return false;
}

And my transitive function:

bool transitive(int b[], int sizeOfB) 
{
    bool hold = true; // set hold to true
    for(int i=0; i+1<sizeOfB; i+=2) // for each pair (e,f) in b
	{
        int e = b[i]; // declare e
        int f = b[i+1]; // declare f
		for(int j = 0; j+1 < sizeOfB; j+=2) // for each pair (e,g) in b
		{
			int g = b[j]; // declare g
			if (pair_is_in_relation(g, e, b, sizeOfB) == false) // if pair(e,g) is not in b
			{
				hold = false; // set hold to false
				break;
			}
		}
      }
    if (hold)
        cout << "Transitive - Yes" << endl; 
    else
        cout << "Transitive - No" << endl; 
    return hold;
}

What am I doing wrong?

[SIK]

I see you declare [ f ] but do nothing with it.

What are you suppose to do with [ f ].

[ashworcp]

Now, this is checking to see if (e,f) is in b to go on to the next loop but still is not coming back correct.

bool transitive(int b[], int sizeOfB) 
{
    bool hold = true; // set hold to true
    for(int i = 0; i+1 < sizeOfB; i+=2) // for each pair (e,f) in b
    {
        int e = b[i]; // declare e
        int f = b[i+1]; // declare f
	if(inRelation(f, e, b, sizeOfB))

		for(int j = 0; j+1 < sizeOfB; j+=2) // for each pair (e,g) in b
		{
			int g = b[j]; // declare g
			if (inRelation(g, e, b, sizeOfB) == false) // if pair (e,g) is not in b
			{
				hold = false; // set hold to false
				break;
			}
		}
      }
    if(hold)
        cout << "Transitive - Yes" << endl; 
    else
        cout << "Transitive - No" << endl; 
    return hold;
}

[kev82]

If you add a print statement after line 12 to print out (e,g), I think you will find that it will list pairs that are not in b.

I would loop through them like this:

for(int i=0;i!=sizeOfB;i+=2) {
  int e=b[i], f=b[i+1];
  for(int j=0;j!=sizeOfB;j+=2) {
    if(b[j] != f) continue;
    int g = b[j+1];
    //do stuff
  }
}

[ashworcp]

@Kev82, then call inRelation and set my hold to false if pair (e,g) is not in b?

[kev82]

Why not try it and see? The only way to learn is to do. I also highly recommend you add the print statement to your code, so you can see you're not generating the (e,g) pair correctly.

[SIK]

bool pair_exist(int left, int right, int b[], int sizeOfB)
{
   for (int i=0; i<sizeOfB; i+=2)
   {
      if (left==b[i] && right==b[i+1])  return true;
   }

   return false;
}


bool transitive(int b[], int sizeOfB)
{
   for (int i=0; i<sizeOfB; i+=2)
   {
      int e = b[i];
      int f = b[i+1];
      // we've chosen pair (e, f) from b


      // we now find any (f, g)
      for (int j=0; j<sizeOfB; j+=2)
      {
         if (i == j)       continue;      // avoid choosing same pair
         if (b[j] != f)    continue;      // ignore all pairs not having f for 1st value.

         // we now have a pair (b[j], b[j+1]) where f is the 1st value
         // thus b[j+1] = g
         // therefore we must now see if (e, g) is a pair in b
         if (!pair_exist(e, b[j+1], b, sizeOfB))    return false;
      }
   }
   
   return true;
}


void main()
{
   int b[] = {1, 2,   2, 3,   4, 5,   7, 9,  1, 3};
   

   bool is_transitive = transitive(b, sizeof(b)/sizeof(int));

   cout << is_transitive << endl;
}

I changed the name of function [pair_is_in_relation] to [pair_exist] to be more intuitive with rest of my logic.

Does this answer your question?