0
\$\begingroup\$

I tried to implement union find (disjoint set data structure) algorithm in C++. There I used unordered_map data structure. Is there a better way of doing this using any other data structure.

While finding the root I have used the following way.

int root(int i){
        if(i != parent[i]) parent[i] = root(parent[i]);
        return parent[i];
    }

Also, I can implement it as

int root(int i){
        while (i != parent[i]){
            parent[i] = parent[parent[i]]);
            i = parent[i];
        }
        return i;
    }

It seems like both are same other than the (recursive and iterative) approach for me. Which is better here!

The following is my implementation.

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;

class Disjoinset{

    private:

    unordered_map<int, int> parent, rank;
    // find the root
    int root(int i){
        if(i != parent[i]) parent[i] = root(parent[i]);
        return parent[i];
    }

    public:

    // initialize the parent map
    void makeSet(int i){
        parent[i] = i;
    }
    // check for the connectivity
    bool is_connected(int p, int q){
        return root(p) == root(q);
    }
    // make union of two sets
    void Union(int p, int q){

        int proot = root(p);
        int qroot = root(q);

        if(proot == qroot) return;

        if(rank[proot] > rank[qroot]) {
            parent[qroot] = proot;
        }
        else{
            parent[proot] = qroot;
            if(rank[proot] == rank[qroot]) rank[qroot]++;
        }
    }
};

Driver code

int main(){
    vector<int> arr = {1,2,9,8,6,5,7};
    Disjoinset dis; // create a disjoint set object
    for(int x: arr){
        dis.makeSet(x); // make the set
    }
    dis.Union(1,9); // create connections
    dis.Union(6,5);
    dis.Union(7,9);
    cout <<  dis.is_connected(1,7) << endl; // check the connectivity.
    cout <<  dis.is_connected(1,6) << endl;
    return 0;
}

Thereafter I tried to use generics and I came up with following. Can someone help me on this as I am new to C++. Is my implementation is correct or are there any better approach.

#include<iostream>
#include<unordered_map>
#include<vector>
#include<string>
using namespace std;

template<class T>
class Disjoinset{

    private:

    unordered_map< T, T> parent; 
    unordered_map< T, int>rank;
    // find the root
    T root(T i){
        if(i != parent[i]) parent[i] = root(parent[i]);
        return parent[i];
    }

    public:

    // initialize the parent map
    void makeSet(T i){
        parent[i] = i;
    }
    // check for the connectivity
    bool is_connected(T p, T q){
        return root(p) == root(q);
    }
    // make union of two sets
    void Union(T p, T q){

        T proot = root(p);
        T qroot = root(q);

        if(proot == qroot) return;

        if(rank[proot] > rank[qroot]) {
            parent[qroot] = proot;
        }
        else{
            parent[proot] = qroot;
            if(rank[proot] == rank[qroot]) rank[qroot]++;
        }
    }
};


int main(){
    vector<string> arr = {"amal", "nimal", "kamal", "bimal", "saman"};
    Disjoinset <string>dis; // create a disjoint set object
    for(string x: arr){
        dis.makeSet(x); // make the set
    }
    dis.Union("amal", "kamal"); // create connections
    dis.Union("kamal", "nimal");
    cout <<  dis.is_connected("amal", "nimal") << endl; // check the connectivity.
    cout <<  dis.is_connected("bimal", "amal") << endl;
    return 0;
}

Thank you for every answer.

\$\endgroup\$
4
  • \$\begingroup\$ Did you test it? Does it produce the correct output? \$\endgroup\$
    – Mast
    Commented May 28, 2020 at 19:40
  • \$\begingroup\$ @Mast Did you find anything wrong here? \$\endgroup\$ Commented May 28, 2020 at 20:11
  • \$\begingroup\$ Without a specification what, e.g. int root(int i) is to accomplish, who is to tell if it works as intended, is coded justifiably? (I see the single line comments in the larger code blocks. I'm, old, trying to be patient. And attentive. Failing time and again…) \$\endgroup\$
    – greybeard
    Commented May 29, 2020 at 4:29
  • \$\begingroup\$ @greybeard sorry for that. Thanks for the advice. \$\endgroup\$ Commented May 29, 2020 at 6:23

2 Answers 2

2
\$\begingroup\$

Overall, that looks good to me. A few nitpicks, however, follow:

Advice 1

#include<iostream>
#include<unordered_map>
#include<vector>
#include<string>

I would put a space between e and <. Also, I would sort the rows alphabetically, so that we get:

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

Advice 2: One template per file

I would extract away the main and put the entire disjoint set template into its own file; call it DisjointSet.hpp to begin with.

Advice 3: Protect your header files from multiple inclusion

I would most definitely put the header guards in DisjointSet.hpp so that it looks like this:

#ifndef COM_STACKEXCHANGE_RUSIRU_UTIL_HPP
#define COM_STACKEXCHANGE_RUSIRU_UTIL_HPP
.
. Your funky DisjointSet.hpp code here. :-)
.
#endif // COM_STACKEXCHANGE_RUSIRU_UTIL_HPP

Advice 4: "Package" your code into namespaces

I have a habit of putting my data structures into relevant namespaces in order to avoid name collisions with other people's code:

namespace com::stackexchange::rusiru::util {
    template<class T>
    class DisjointSet {
        ...
    };
}

Advice 5: Remove minor noise

unordered_map< T, T> parent; 
unordered_map< T, int>rank;

I would write:

unordered_map<T, T> parent;
unordered_map<T, int> rank;

Note the placement of spaces!

Advice 6: Arbitrary method naming scheme

Essentially, you have makeSet, is_connected, Union. That's three different method naming schemes right there; choose one and stick to it. For example, makeSet, isConnected, union.

Advice 7: Printing booleans to stdout:

You can do cout << std::boolalpha << ...; in order to print true/false.

Advice 8: Don't pollute your namespace

Generally speaking, using namespace std; is not what you may see in professional C++ code. Consider using individual uses such as:

using std::cout;
using std::endl;

Putting all together

Overall, I had this in mind:

DisjointSet.hpp

#ifndef COM_STACKEXCHANGE_RUSIRU_UTIL_HPP
#define COM_STACKEXCHANGE_RUSIRU_UTIL_HPP

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

namespace com::stackexchange::rusiru::util {

    using std::boolalpha;
    using std::cout;
    using std::endl;
    using std::string;
    using std::unordered_map;
    using std::vector;

    template<typename T>
    class DisjointSet {

    private:

        unordered_map<T, T> parent;
        unordered_map<T, int> rank;

        // find the root
        T root(T i) {
            if (i != parent[i]) parent[i] = root(parent[i]);
            return parent[i];
        }

    public:

        // initialize the parent map
        void makeSet(T i) {
            parent[i] = i;
        }
        // check for the connectivity
        bool isConnected(T p, T q) {
            return root(p) == root(q);
        }
        // make union of two sets
        void union(T p, T q) {

            T proot = root(p);
            T qroot = root(q);

            if (proot == qroot) return;

            if (rank[proot] > rank[qroot]) {
                parent[qroot] = proot;
            }
            else {
                parent[proot] = qroot;
                if (rank[proot] == rank[qroot]) rank[qroot]++;
            }
        }
    };
}

#endif // COM_STACKEXCHANGE_RUSIRU_UTIL_HPP

main.cpp

#include "DisjointSet.hpp"
#include <iostream>
#include <string>
#include <vector>

using std::boolalpha;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using com::stackexchange::rusiru::util::DisjointSet;

int main() {
    vector<string> arr = { "amal", "nimal", "kamal", "bimal", "saman" };
    DisjointSet<string> dis; // create a disjoint set object

    for (const string x : arr) {
        dis.makeSet(x); // make the set
    }

    dis.union("amal", "kamal"); // create connections
    dis.union("kamal", "nimal");

    cout << boolalpha << dis.isConnected("amal", "nimal") << endl; // check the connectivity.
    cout << dis.isConnected("bimal", "amal") << endl;
    return 0;
}
\$\endgroup\$
4
  • \$\begingroup\$ Thank you very much for your detailed advises. Those are really helpful. \$\endgroup\$ Commented May 28, 2020 at 12:39
  • \$\begingroup\$ Nothing about using namespace std;? \$\endgroup\$
    – pacmaninbw
    Commented May 28, 2020 at 15:49
  • \$\begingroup\$ @pacmaninbw Mitigated. \$\endgroup\$
    – coderodde
    Commented May 28, 2020 at 17:16
  • 1
    \$\begingroup\$ I wouldnt recommend sorting the inclusions alphabetically, since you sometimes need to worry which one goes first. You also sometimes want to separate standard ones from custom ones. \$\endgroup\$
    – pacukluka
    Commented May 29, 2020 at 9:06
1
\$\begingroup\$

There is no need for unordered maps, especially not for two of them. Also, since you are dealing with indices and counts, you should make them std::size_t, not int or generic. The datatype for storing parent-rank-tuples should look like this:

std::vector<std::tuple<std::size_t, std::size_t>> data;

Performance will be a good deal better because vector is faster than unordered map and in addition to that, there's only one lookup required to get both parent and rank, like this:

auto [parent, rank] = data[i];

or like this:

std::tie(parent, rank) = data[i];

If you want the union-find datastucture to work on arbitrary objects instead of indices, create a generic wrapper class that translates objects to indices and then invokes the non-generic version. This way, the unordered_map lookup is done only once for each argument, even if the non-generic version subsequently performs several recursions.

\$\endgroup\$
3
  • \$\begingroup\$ P Thanks. What did you mean by " vector is faster than unordered map". Better if you can you explain it . \$\endgroup\$ Commented May 29, 2020 at 10:55
  • \$\begingroup\$ @rusiruthushara - std::vector is an array and std::unordered_map is a hash table. A hash table is built upon an array but with key hashing and collision handling on top, so it is obviously slower than a plain array. The disadvantage of an array is that the keys must be integers between zero and the size of the array. A hash table can handle arbitrary indices, including strings and objects. \$\endgroup\$
    – Rainer P.
    Commented May 29, 2020 at 12:04
  • \$\begingroup\$ Thanks for the information. \$\endgroup\$ Commented May 29, 2020 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.