Equivalence Relation Manager

[Sherwin_4]

Good afternoon,

I have to create a program to only be used as a tool (no main function). Below is the background information related to task:

Your goal for this assignment is to create a tool that manages an equivalence relation that can be changed by the program. The equivalence relation is always over a set of integers {1, 2, 3, …, n} for some n.

This tool is not a complete program. It is intended to be part of a larger program. It must not have a main function.

For this assignment, an equivalence relation has type ER. A module that uses this tool can create an equivalence relation called e by saying

1. ER R = newER(n);
   where n is an integer. Initially, each number is in its own equivalence class; the equivalence classes are {1}, {2}, …, {n}. There are two operations that can be performed.
   equivalent(R, x, y) yields true if x and y are currently in the same equivalence class in equivalence relation R.

1. merge(R, x, y) modifies equivalence relation R by making x and y equivalent. It combines the equivalence class that contains x with the equivalence class that contains y. The merge function does not yield an answer.

You will not store the equivalence classes directly. Instead, you will store them implicitly, using the following ideas. You are required to implement an equivalence manager in this way. You will receive no credit for a module that does not follow this algorithm.

Each equivalence class has a leader, which is one of the members of that equivalence class. You will create a function leader(R, x) that yields the current leader of the equivalence class that contains x in equivalence relation R. Two values are equivalent if they have the same leader.

There is another idea that is similar to a leader, but not exactly the same. Each value has a boss, which is a value in its equivalence class. Let's write boss[x] for x's boss.

If x is the leader of its equivalence class then boss[x] = 0, indicating that x does not have a boss. If x is not the leader then boss[x] ≠ x and boss[x] is closer to the leader. If you look at the values x, boss[x], boss[boss[x]], boss[boss[boss[x]]], … then you will eventually encounter x's leader.

Use an array to store the bosses. Write the following functions.

1. newER(n) returns an array of n+1 integers. Allocate the array in the heap. This array will be used to store the bosses. So, if R has type ER then R[x] is x's boss. (If you prefer, you can call an equivalence relation boss. Then boss[x] is x's boss.)

In C++, arrays start at index 0. You will use indices 1, … n, so you need to allocate n+1 slots. (Index 0 will not be used.)

Initialize the array so that each value is a leader of its own group. That is, boss[x] = 0 for x = 1, …, n.

1. leader(R, x) returns the leader of x in equivalence relation R. To compute x's leader, just follow the bosses up to the leader. You are required to use this function any time you want to find the leader of a value.

2. equivalent(R, x, y) returns true if x and y are currently in the same equivalence class in equivalence relation R. (They are in the same equivalence class if they have the same leader.)

3. merge(R, x, y) merges the equivalence classes of x and y in R as follows. First, it finds the leaders x′ and y′ of x and y. If x′ and y′ are different (so x and y are not already in the same equivalence class) then y′ becomes the new boss of x′. (How can you changes x′'s boss?) So y′ becomes the leader of the combined equivalence class.

4. destroyER(R) deallocates R.

5. showER(R, n) prints the entire contents of array R (of size n) in a readable form for debugging.

Important note. It is crucial that your program never change the boss of a value that is not a leader.

The professor provided the following header (I'm glad he did, gives me a better understanding on how he likes his contracts. I do know he doesn't want any body comments):

// These #ifndef and #define lines make it so that, if this file is
// read more than once by the compiler, its body is skipped on all
// but the first time it is read.

#ifndef EQUIV_H
#define EQUIV_H

// An equivalence relation is an array of integers.
// So ER abbreviates int*.  

typedef int* ER;

// Public functions

ER   newER      (int n);
void destroyER  (ER e);
bool equivalent (ER e, int x, int y);
void merge      (ER e, int x, int y);

// The following is advertised here solely for debugging.  These must
// only be used for debugging.

void showER(ER e, int n);
int  leader(ER e, int x);

#endif

Below is what I have so far. I'm looking to change ER e to R, but not sure if that is possible. Based off of what I provided, am I at least on the right path? https://code.sololearn.com/c5850jWvbHRj/#cpp

// These #ifndef and #define lines make it so that, if this file is
// read more than once by the compiler, its body is skipped on all
// but the first time it is read.

#ifndef EQUIV_H
#define EQUIV_H

// An equivalence relation is an array of integers.
// So ER abbreviates int*.  

typedef int* ER;

// Public functions ///////////////////////////////////////////////////

/*
// ER new ER(int n)
// Returns an array of 'n' + 1 integers
*/

ER newER(int n)
{
    int* R = new int[n];

    for (int index = 1; index < n; index++)
    {
        R[index] = (n + 1); 
    }

    return R; 

}

/*
// destroyER(Er)
// Deallocates R. 
*/ 
void destroyER(ER e)
{
    // Changed ER e to R. 
    delete R;
    int* R = NULL;
    // Is this considered a dangling pointer? 
}

/*
// equivalent(ER e, int x, int y)
// Returns true if x and y are currently in the same equivalence class in equivalence relation R.
*/
bool equivalent (ER e, int x, int y);
{

}

/*
// merge(ER e, int x, int y)
// Merges the equivalnece classes of x and y in R. 
*/
void merge(ER e, int x, int y);
{

}

////////////////////////////////////////////////////////////////////

// The following is advertised here solely for debugging.  These must
// only be used for debugging.

///////////////////////////////////////////////////////////////////

/*
//  showER(ER e, int n)
//  Prints the entire contents of array R (of size n) in a readable form for debugging.
*/
void showER(ER e, int n);
{

}

/*
// leader(ER e, int x)
// Returns the leader of x in equivalence relation R
*/
int leader(ER e, int x);
{

    // I changed ER e to R
    if (R[x] == 0)
    {
        return x;
    }

    else
    {
        return leader(R, R[x])
    }
}

#endif

[Sherwin_4]

Or for the first funtion:

int newER(int n)
{
    int* R = new int[n];
    int temp = 1;

    for (int index = 1; index == n; index++)
    {
        R[index] = (temp); 
        temp++;
    }

    return R;

[AssertNull]

Not the question you asked, but again, if there is no reason to have temp, get rid of it.

int newER(int n)
{
    int* R = new int[n];
    int temp = 1;

    for(int index = 1; index == n; index++)
    {
        R[index] = (temp); 
        temp++;
    }

    return R; 
}

Voilà.

int newER(int n)
{
    int* R = new int[n];

    for(int index = 1; index == n; index++)
    {
        R[index] = index; 
    }

    return R; 
}

Line 3. Above. If I create an array of size n, what are the valid indexes? Are you getting a Seg Fault anywhere? Hint: If you are NOT, that doesn't mean things are OK memory-wise.

Why is this function returning an integer? Aren't you creating and returning an array?

void destroyER(ER e)
{
    // Changed ER e to R. 
    delete R;
    int* R = NULL;
    // Is this considered a dangling pointer? 
}

Changed ER e to R.

1. Why? ER seems like a nice, descriptive name. The function's called deleteER. So delete ER. Names, names, names. If it ain't brike, don't fix it. Unless there's a reason.
2. Does it compile? You ARE compiling and testing this as you go, right?

Or for the first funtion:

The first function you write is the display function. The second function you write is the newER function. The THIRD function you write is a driver/test/main function that creates the array, then displays the array.

You'll be changing around the driver/test/main function a lot as you go, but you'll be printing the array over and over and over again and you'll be re-compiling and re-running this program over and over and over again, throwing everything you can at it to see what works and what fails, testing it over and over and over again. That way bugs get caught early.

Is this considered a dangling pointer?

No, but it's pointless, no pun intended.

As part of this testing over and over and over again, try creating and deleting a large array over and over again, with a counter. If the number printouts get slower and slower, you're probably running out of memory, which means you're either creating the array wrong or deleting it wrong.

[AssertNull]

Okay, I appear to have written some semi-jibberish yesterday. I could have sworn I had a point, but re-reading it, let's just rephrase things and make it a little more clear.

The original...

Why? ER seems like a nice, descriptive name. The function's called deleteER. So delete ER. Names, names, names. If it ain't brike, don't fix it. Unless there's a reason.

Here is the function...

void destroyER(ER e)
{
    // Changed ER e to R. 
    delete R;
    int* R = NULL;
    // Is this considered a dangling pointer? 
}

The point is that that the name in the parameter should match what is in the function. If you are going to change the parameter name to R, then you can change the parameter name to R. Or use e. But whichever you use, make it match.

    void destroyER(ER e)
    {
        delete []e;
    }

or

void destroyER(ER R)
{
    delete []R;
}

Both are fine. Just don't have e at the top and R in the body or vice-versa. Note the brackets in front of e. See this link. You are deleting an array.

http://www.cplusplus.com/reference/new/operator%20delete[]

If you used new with brackets (and you did), you should use delete with brackets. If you used new without brackets, use delete without brackets.

Watch your int versus int*. Keep it consistent. Note ER is typedefed to be int*, so writing ER in your code is equivalent to writing int* as far as types go. If you have a function returning int, make sure that's what you want to have. If it is not, change it. If it is, don't return an ER or int*.

Edit: Not sure the link is working. Google "C++ delete array brackets".

[Sherwin_4]

@ AssertNull first response:

Yea, I found out yesterday evening during his class that the header file can contain the function definitions. At first I thought that the header would be standalone (only containing the function prototypes), and that you would put the definitions in another file, but #include(header name) in that file. The functions I provided earlier are the functions he wants us to define. I have to keep the function names the way that he presented.

[Sherwin_4]

@AssertNull second response

Yea, I didn't know we could do that, I was going off of the examples in class. Also, should I leave the header alone, and put my definitions in another file. The header is really throwing me off. I see the typedef ER basically means int*. I coded the following below.

ER newER(int n)
{
    int* R = new int[n];
    int index;

    for(index = 1; index <= (n+1); index++)
    {
        R[index] = index; 

        cout << index << " ________________"<< R[index] << endl;
    }
    return R; 
}

I put cout << index << " ________________"<< R[index] << endl; here so I can track the ouput. The output is correct, based off of my understanding of him wanting an array that was n+1 in length. Currently I'm returning an address of this array. The function definition states it should return an array n+1 of integers. I believe for memory purposes, the address is what we are looking for. Not 100% sure, but giving it a try.

[Sherwin_4]

Let re work the code in my last respone to this:

int* newER(int n)
{

    int ER [n + 1];

    int *R = ER;

    for(int index = 1; index <= (n+1); index++)
    {
        ER[index] = index; 

        cout << index << " ________________"<< ER[index] << endl;
    }

    return R; 
}

[AssertNull]

Had a big long post written out, but it got lost due to some weird loging problem. Not rewriting the whole thing. Sorry. Highlights are as follows...

1. The array is to be created on the heap. That means using the new[] command.
2. You need indexes 1 through n, which means you need to create n+1 integers, so n+1 should be in the brackets with new.
3. Valid indexes are 1 through n. You are not using 0. You cannot use n+1 as an array index, thus be careful in your loop with test as far as < versus <= and n versus n+1. Make sure your loop goes from 1 through n somehow, but don't access index n+1 since it's unnecessary and you do not have enough memory.
4. ER is an int* type. Do not use ER as a variable name. You should be able to change ER to int* in your code and vice versa and have everything compile fine. If it doesn't, you have a problem somewhere. You should use ER everywhere for int* when it represents an integer array, or you should do it nowhere, but having ER in parts of the function and int* elsewhere is confusing (note that there are potential exceptions to this rule, but I don't see any of those exceptions in this particular program since all int* represent Equivalence Relation integer arrays in this program. The typedef is defined for the human reader to see ER and think "Ah, an Equivalency Relation array". This is for humans. The compiler could not care less.
5. cout is fine in this function, but remember to take it out later. I'll reiterate that you should write showER ASAP since you have to write it anyway and it will help you in your debugging. IMO once you write showER, you'll be able to call it and remove the cout statements in the other functions.

I see the typedef ER basically means int*.

Correct. See point 4. See code below for improvements corresponding to the points above. I have retained your cout statement, but consider point 5.

ER newER(int n)
{
    ER R = new int[n + 1];
    for(int index = 1; index <= n; index++)
    {
        R[index] = index; 
        cout << index << " ________________"<< R[index] << endl;
    }
    return R; 
}

Note that you do not see int* anywhere. You see ER instead, but only as a type, not a variable name. Thus ER is the type and R is the variable name everywhere. My personal preference would be to name it er instead of R, but R is acceptable. What you CAN'T do is name your variable ER or use ER anywhere where you would use a variable name.

[AssertNull]

This code won't work, and that's after I cleaned up the ER problem and the n versus n+1 problems (based on your code, but cleaned up a little to follow your intent).

int* newER(int n)
{
    int R[n + 1]; // bad.  Needs to be created on the HEAP using new[]
    for(int index = 1; index <= n; index++)
    {
        R[index] = index; 
        cout << index << " ________________"<< R[index] << endl;
    }

    return R; 
}

It will print out just fine, but it you compile it, you get this warning, assuming you have the appropriate compiler flags on.

warning: address of local variable 'R' returned [-Wreturn-local-addr]

What it means is that memory can be used within that function only. If you try to use that array later, it will be a matter of dumb luck if the memory hasn't been de-allocated or written over (why, when, and how that happens, and when you might get away with it and when you won't is beyond your current level, so don't worry about that now).

Hence the requirement to create the array using the heap using new[]. In other words, DO use my function in my last post and DO NOT use my function in this post (which was based on your function).

[Sherwin_4]

Understood. I decided to leave out the header file completely, and just focus on a file that only contains the function definitions. I'll use NoMachine to run all three files together, since I'm unable to do that via SOL Cpp site. Below is my current draft of what I came up with. I'm looking for examples on how to do the equivalent funtion, then the merge fuction. I believe the other functions are good to go.

#include "equiv.h"
#include <iostream>
#include <cstdio>
using namespace std;

/*
// int* newER(int n)
// Returns an array of n+1 integers.
*/
int* newER(int n)
{
    int *R = new int[n + 1];

    for(int index = 1; index <= n; index++)
    {
        R[index] = 0; 
    }
    return R;  
}

/*
// int leader(int* R, int x)
// Returns the leader of x in equivalence relation R.
*/
int leader(int* R, int x)
{

    if (R[x] == 0)
    {
        return x;
    }

    else
    {
        return leader(R, R[x])
    }
}

/*
// bool equivalent(int* R, int x, int y)
// Returns true if x and y are currently in 
// the same equivalence class in equivalence relation R.
*/
bool equivalent(int* R, int x, int y)
{
    for(int index = 0; index < "pending" ; index++)
    {
        if( (R[index] = x) == (R[index] = y))
        {
            return true;
        }
    }
    return false; 
}

/*
// void merge(int* R, int x, int y)
// Merges the equivalence classes of x and y in R.
*/
void merge(int* R, int x, int y)
{

}

/*
// void destroyR(int* R)
// Deallocates R.
*/
void destroyER(int* R)
{
    delete R;
}

/*
// void showER(int* R, int n)
// Prints the entire contents of array R (of size n). 
*/
void showER(int* R, int n)
{
    for (int index = 1; index <= n; index++)
    { 
        cout << index << " " << R[index] << endl;
    }
}

[AssertNull]

if( (R[index] = x) == (R[index] = y))

I'm either not understanding what the equivalent function does or this is way off. You are changing the R array in this function by using the = operator. Thus R will be different after the function than it was before. Do you want that? I can't imagine that you do.

I can't figure out your logic either in this function. You say your other functions are good to go, so use them. If my understanding of this project is correct, x and y are in the same equivalence class if and only if x and y have the same leader. If your other functions are truly good to go, perhaps call the leader function from the equivalent function?

[AssertNull]

I went through your spec a little more closely and I'm a little confused. The array you are storing is the ""Boss" array, correct? It's a little unclear whether a leader (let's say 2 is a leader) should store 0 or store itself (2). Any element that is NOT a leader should neither store itself nor strore 0. That's easy enough to comprehend. But what does the leader store (itself or 0)? I'm seeing evidence of both in the spec.

I'm also not seeing a few helper functions that I would expect to see. In particular, it's easy enough to traverse from the middle of an equivalency to the front element, but how do you get from the middle or the front to the tail/back? In other words if I have a set {1,2,3,4} where 1 is the leader, 1 is the boss of 2, 2 is the boss of 3, and 3 is the boss of 4, how do I get from, say, 2 to 4?

This is quite doable, but just consider that concept when you have to merge {1,2,3,4} and {5,6,7,8} and you are given, say, x = 2 and y = 6. You need to find the leader of 6 and change that leader's boss to 4. Easy enough to find 6's leader (you have a function for that called leader), but how do you find 2's tail (ie 4)? Are you supposed to write a tail function?

My guess is that this assignment is a preview of a concept called a Linked List. In this case it is a Singlly Linked List. The "boss" of an element is the element ahead of that element in line (synonym for "line" is "list" in this case), so an element can see the element in front of it only and go to it. It cannot see behind it and go that way. That would be a Doubly Linked List. The front element either has no boss or is its own boss and hence knows there is no one in front of it.

Anyway, you might want to google those terms and see what I mean.

And, again, how do you go backwards to the tail because you need to be able to do that in order to print one list or merge two lists, yes?

That's what you have to figure out. Pencil and paper.

[Sherwin_4]

Understood. I was looking over the equivalent function, below is what I came up with:

/*
// bool equivalent(int* R, int x, int y)
// Returns true if x and y are currently in 
// the same equivalence class in equivalence relation R.
*/
bool equivalent(int* R, int x, int y)
{
    bool testOf_x = false, testOf_y = false;

    for(int index = 0; index < R[n-1]; index++)
    {
        if(R[index] == x)
        {
            testOf_x = true;
        }

        else if(R[index] == y)
        {
            testOf_y = true;
        }
        else if(testOf_x && testOf_y)
        {
            return true;
        }
    }
}

Do you believe I can impove on this function draft?

v/r

[Sherwin_4]

Actually the above is not the right direction. What do you think of this:

/*
// bool equivalent(int* R, int x, int y)
// Returns true if x and y are currently in 
// the same equivalence class in equivalence relation R.
*/
bool equivalent(int* R, int x, int y)
{
    if (leader(int* R, int x) == leader(int* R, int y)
    {
        return true;
    }

}

[AssertNull]

if (leader(int* R, int x) == leader(int* R, int y)

You're compiling as you're going along, right? That's not going to compile.

Leave the types out...

if (leader(R, x) == leader(R, y)

And match the parentheses...

if (leader(R, x) == leader(R, y))

See if that works better.

And I see a return true in the function. But no return false anywhere. Does this function always return true?

[Sherwin_4]

I'll definitely include the return false, thank you.

[Sherwin_4]

Now I'm running into the issue of multiple definitions in code::blocks, but I think that comes down to how I'm linking the files (I'll figure that out). What do you think of this merge function:

/*
// void merge(int* R, int x, int y)
// Merges the equivalence classes of x and y in R.
*/
void merge(int* R, int x, int y)
{
    if(!equivalent(R, x, y))
    {
        int xLeader = leader(R,x), yLeader = leader(R, y);

        R[xLeader] = yLeader;
    }
}

[AssertNull]

That appears to be about what your professor had in mind as opposed to how I envisioned it a few posts ago.

Learning how to link things correctly is generally a skill you learn when you go farther along, but in a project like this, it's pretty basic and Code Blocks will generally figure it out correctly for you (assuming you do not provide a Makefile and let it create one) if you let it, so it could be an actual coding error.

[Sherwin_4]

Copy that, I'm on it.