Question

Your goal for this assignment is to create a tool that manages an equivalence relation that can be changed in a specific way by the program while the program runs. The assignment will involve creating two files, equiv.h and equiv.cpp.

For this assignment, the equivalence relation is always over a set of integers {1, 2, 3, …, n} for some positive integer n.

This tool is not a complete program. It is intended to be part of a larger program. File equiv.cpp must not contain a 'main' function.

Equiv.h will contain function prototypes, but it must not contain any full function definitions. (There must be no function bodies.) Equiv.cpp must contain line

  #include "equiv.h"

before any function definitions.

Interface

The interface tells exactly what this module provides for other modules to use. Other modules must not use anything that is not described here. Briefly, the interface includes a type, ER, which is the type of an equivalence relation, and the following functions.

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

Additionally, there is one function that is solely for debugging.

  void showER(const ER R, const int n);

There is one more function that is part of the implementation but not part of the interface. You can use it for debugging, though.

  int  leader(ER R, const int x);

A module that uses this tool can create an equivalence relation called R by saying

  ER R = newER(n);

where n is a positive 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.

1. equivalent(R, x, y) returns a boolean value: true if x and y are currently in the same equivalence class in equivalence relation R, and false otherwise.

2. 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 return an answer.

Example

For example, suppose that n = 7. The following shows a sequence of operations and shows the equivalence classes after each merge operation.

Step	Result
ER R = newER(7)	R = {1} {2} {3} {4} {5} {6} {7}
merge(R, 1, 5)	R = {1, 5} {2} {3} {4} {6} {7}
merge(R, 2, 7)	R = {1, 5} {2, 7} {3} {4} {6}
equivalent(R, 1, 5)	yields true
equivalent(R, 1, 7)	yields false
merge(R, 5, 7)	R = {1, 2, 5, 7} {3} {4} {6}
equivalent(R, 2, 5)	yields true
equivalent(R, 2, 3) yields false	yields false
merge(R, 2, 3)	R = {1, 2, 3, 5, 7} {4} {6}
equivalent(R, 3, 7)	yields true
equivalent(R, 4, 7)	yields false
merge(R, 4, 6)	R = {1, 2, 3, 5, 7} {4, 6}
merge(R, 2, 3)	R = {1, 2, 3, 5, 7} {4, 6}

As you can see from the last step, it is allowed to merge two values that are already equivalent. That should cause no change.

An Algorithm for Managing an Equivalence Relation

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.

1. 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 returns the current leader of the equivalence class that contains x in equivalence relation R.

   Two values are equivalent if they have the same leader.

2. 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. For the purposes of describing the idea, let's write boss[x] for x's boss.

   1. If x is the leader of its equivalence class then boss[x] = 0, indicating that x has no boss.

   2. If x is not the leader of its equivalence class then boss[x] ≠ 0 and boss[x] is closer to the leader, in the following sense. If you look at the values x, boss[x], boss[boss[x]], boss[boss[boss[x]]], … then you will eventually encounter x's leader (just before you encounter 0).

Details on the algorithm

Use an array to store the bosses. Declaration

  typedef int* ER;

defines type ER to be the same as int*. Write the following functions.

1. newER(n) returns an equivalence relation as an array of n+1 integers. Allocate the array in the heap. This array will be used to store the bosses. If R has type ER then R[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 equivalence class. That is, R[x] = 0 for x = 1, …, n.

2. 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. Here is a sketch of a loop that finds the leader of x.

     y = x
     while(boss[y] != 0)
       y = boss[y]
     return y
   

   You can use a loop or recursion the leader function. Any function that wants to compute a leader must use the leader function to do that.

3. equivalent(R, x, y) returns true if x and y have the same leader in R. Notice that is not the same as saying that they have the same boss.

4. 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′ and y′ becomes the leader of the combined equivalence class.

5. destroyER(R) deallocates R.

6. showER(R, n) prints the entire contents of array R (of size n) in a readable form for debugging. Be sure that showER shows both k and k's boss, for each k.

   Do not try to be too fancy here. Do not try to show the equivalence classes. ShowER is a debugging tool, and it should show the bosses.

Important Note.
It is crucial for your merge function never to change the boss of a nonleader. If you are not sure that x is a leader, do not change R[x].  Pay attention to this! In the past, many students have ignored this requirement. Needless to say, their modules did not work and their scores were low.

Additional Requirements

It is important for you to follow the algorithms and design described here. Do not make up your own algorithm. Implement exactly the functions that are indicated. Keep the parameter order as shown here. If you change the parameter order, your module will not compile correctly with my tester. Do not add extra responsibilities to functions.

The definition of ER must only be in equiv.h. Do not duplicate that definition in equiv.cpp.

A Refinement Plan

Development plan
2. Create a file called equiv.cpp. Copy and paste the module-template into it. Edit the file. Add your name and the assignment number. If you will use tabs, say how far apart the tab stops are. Add line #include "equiv.h"
3. Write a comment telling what this module will provide when it is finished. Equiv.cpp is not an application. It just provides a tool. Say that it is an equivalence relation manager and give an outline of the interface.
4. Create a file called equiv.h. Copy the following into equiv.h, then edit it to add your name. // CSCI 2530 // Assignment: 3 // Author: *** // File: equiv.h // Tab stops: none // 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 function prototypes ER newER (const int n); void destroyER (ER R); bool equivalent (ER R, const int x, const int y); void merge (ER R, const int x, const int y); // The following is advertised here solely for debugging. These must // only be used for debugging. void showER(const ER R, const int n); int leader(ER R, const int x); #endif Note. In the types of equivalent and leader, parameter R is not marked const, even though it seems to make sense to do that. The reason is that improvements that can be done for extra credit need to make changes to R, even in equivalent and leader.
5. In equiv.cpp, write a heading and contract, then fill in the body, of the 'newER' function. Notice that newER(n) returns an equivalence relation that can handle set {1, 2, …, n}. Say that. Don't say that it returns an array. Where possible, express things in conceptual terms rather than in physical terms.
6. In equiv.cpp, write a contract, then an implementation, of the 'showER' function. Pay attention to what showER is supposed to do.
7. Create file test1.cpp for partial testing of equiv.cpp. Add a main function to test1.cpp and make main create a new ER object (using newER) and use showER to show what it looks like. Testequiv.cpp should contain #include "equiv.h" to allow it to use what is described in equiv.h. Compile test1.cpp and equiv.cpp together as follows. g++ -Wall -o test1 test1.cpp equiv.cpp Then run test1 by ./test1
8. In equiv.cpp, write a heading and contract, then an implementation, of the 'leader' function. Modify test1.cpp so that it tests leader by showing showing the leader of each value in the ER object that it creates. Note that, at this point, each number will be its own leader. Run test1.cpp.
9. In equiv.cpp, write a heading and contract, then an implementation, of the 'merge' function. Modify test1.cpp by making it merge just a few values, then show what the equivalence relation looks like using showER. Does it look right?
10. In equiv.cpp, write a contract, then an implementation, of the 'equivalent' function. Now you have enough to use the automated tester. Run it. If there are errors, fix them. You can read testequiv.cpp to see what it is doing, but only change equiv.cpp to fix errors; changing the tester will not help since I will not use your modified tester when I grade your submission.
11. In equiv.cpp, write a contract, then an implementation, of the 'destroyER' function.

Answer 1

#include <cstdio>

#include <cstdlib>
#include "equi.h"
using namespace std;

const int maxEdges = 1000;
typedef int vertexNum;
typedef int edgeNum;
typedef int (*QSORT_COMPARE_TYPE)(const void *, const void *);

struct Edge
{
    int vert1;
    int vert2;
    int wght;

    Edge()
    {
        vert1 = 0;
        vert2 = 0;
        wght = 0;
    }
};

struct Graph
{
    int totalVertices;
    int totalEdges;
    Edge* edgeArray;
    int arrSize;

    Graph(int nv)
    {
        totalVertices = nv;
        totalEdges = 0;
        arrSize = maxEdges;
        edgeArray = new Edge[arrSize];
    }
};

void insertEdge(int x, int y, int z, Graph& g)

{
    Edge newEdge;
    newEdge.vert1 = x;
    newEdge.vert2 = y;
    newEdge.wght = z;
    if(g.totalEdges < maxEdges)
    {
        g.edgeArray[g.totalEdges] = newEdge;
        g.totalEdges ++;
    }
    return;
}

void readGraph(Graph& g)
{
    int x,y,z;
    while(true)
    {
        scanf("%i", &x);
        if(x == 0)
        {
            break;
        }
        scanf("%i", &y);
        scanf("%i", &z);
        insertEdge(x,y,z, g);
    }
    return;
}

void writeGraph(const Graph& g)
{
    printf("\nThere are %i vertices and %i edges\n", g.totalVertices,
           g.totalEdges);
    printf(" Vertices    Weight\n");
    for(int n = 0; n< g.totalEdges; n++)
    {
        printf(" %i %i         %i\n", g.edgeArray[n].vert1, g.edgeArray[n].vert2,
               g.edgeArray[n].wght);
    }
    return;
}
// Function compareEdges returns a negative or positive number
// if 'A' is smaller or larger than 'B' respectively.
int compareEdges(const Edge *A, const Edge *B)
{
    return A->wght - B->wght;
}

// Function sortEdges sorts the array of edges in graph G by weight
// in ascending order.

void sortEdges(Graph& g)
{
    qsort((void *)g.edgeArray, g.totalEdges, sizeof(Edge),
          (QSORT_COMPARE_TYPE)compareEdges);
    return;
}

//Function minimalSpanningTree returns the minimal spanning tree graph of 'g'.
Graph minimalSpanningTree(Graph& g)
{
    sortEdges(g);
    Graph *k = new Graph(g.totalVertices);
    ER kTracker = newER(g.totalVertices);
    for(int n = 0; n < g.totalEdges; n++)
    {
        if (!equivalent(kTracker, g.edgeArray[n].vert1, g.edgeArray[n].vert2))
        {
            insertEdge(g.edgeArray[n].vert1, g.edgeArray[n].vert2,
                       g.edgeArray[n].wght, *k);
            merge(kTracker, g.edgeArray[n].vert1, g.edgeArray[n].vert2);
        }
    }
    return *k;
}

// Function totalWeight returns the combined weight of each edge
// in the graph 'g'.

int totalWeight(const Graph& g)
{
    int totalWeight =0;
    for(int n = 0; n<= g.totalEdges; n++)
    {
        totalWeight = totalWeight + g.edgeArray[n].wght;
    }
    return totalWeight;
}

int main()
{
    int nv =0;
    scanf("%i", &nv);
    Graph* g = new Graph(nv);
    readGraph(*g);
    printf("Input Graph:\n");
    writeGraph(*g);
    Graph k = minimalSpanningTree(*g);
    printf("Minimal spanning tree:\n");
    writeGraph(k);
    printf("\nThe total weight of the spanning tree is %i\n ", totalWeight(k));

    return 0;
}
---------------------------------------------------------------------------------------------------------
//Equiv.cpp

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

// Function newER returns an equivalence relation of size 'n' over {1, ..., n}
// where each value is initially the sole member of it's equivalence class.

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

// Function "leader" returns the leader of n in equivalence relation R.

int leader(ER R, int n)
{

    if (R[n] == n)
    {
        return n;
    }
    else
    {
        R[n] = leader(R, R[n]);
        return R[n];
    }
}

// Function equivalent returns true if x and y are currently in
// the same equivalence class in equivalence relation R, and
// returns false if they are not in the same class.

bool equivalent(ER R, int x, int y)
{
    if (leader(R, x) == leader(R, y))
    {
        return true;
    }
    return false;
}

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

void merge(ER R, int x, int y)
{
    if (!equivalent(R, x, y))
    {
        R[leader(R, x)] = leader(R, y);
    }
}

//Function destroyER deletes the Equivalent Relation R and frees memory.

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

// Function showER writes the contents of the Equivalent Relation 'R'
// to the standard output.

void showER(ER R, int n)
{
    printf("\nx Boss\n");
    for (int index = 1; index <= n; index++)
    {
        printf("%i %i \n", index, R[index]);
    }
}

-----------------------------------------------------------------------------------------------------------
//Equiv.h
#ifndef EQUIV_H
#define EQUIV_H

typedef int *ER;

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

void showER(const ER R, const int n);
int leader(ER R, const int x);

#endif