# Using HashMaps to track parent and rank of graph nodes

I often find myself in the following position: I have created a class in some file, and would like to add a new data member to that class without changing the original class definition. Now, you cannot actually add a new data member to a class without changing the class definition. So instead, I'd like to "simulate" (in some sense) a new data member.

What do I mean by this? In an implementation of the disjoint sets data structure, objects in the disjoint sets have two properties - they have a "rank" (which is an integer) and they have a "parent" (which is another object of the same class). In Kruskal's algorithm, such a disjoint union data structure is used to represent disjoint sets of vertices. It makes no sense to break abstraction barriers, jump into the implementation of "vertex", and place a vertex pointer called "Vertex *parent" and an integer "rank" in each the class definition of Vertex. Instead, I need some other way to access the rank/parent of a Vertex in O(1) time. How should I do this? Is there a canonical way? Do I use a hash table? How does one hash a vertex?

I suspect I can be more helpful in asking my question if I include my attempt at an implementation to get over this problem. I implemented a "hash map" that uses the address of the object as a key.

This is the implementation of "HashMap", which will key objects by their address and store a pointer to something of class val. This file is what my question focuses on.

File hashMap.h:

#include <unordered_map>

template <class keyed, class val>
class HashMap
{
public:
HashMap(){}
~HashMap(){}

long keyOf(keyed &item){ return (long) &item; }

val* &operator[](keyed &item)
{
long key = keyOf(item);
return _uomap[key];
}

private:
std::unordered_map<long, val*> _uomap;
};


This is a file that includes an implementation of the DisjointSets data structure. It isn't very important - I've included it just for concreteness. Notice that "_rankOf" and "_parentOf" will, in a certain sense, "simulate" data members T.rank and T.parent which may not already appear in the implementation of whatever is used for T.

File disjoint.h:

#include "hashMap.h"

template <class T>
class DisjointSets
{
public:
DisjointSets(){}
~DisjointSets(){}

void makeSet(T &elem)
{
int elemRank = 0;
_parentOf[elem] = &elem;
_rankOf[elem] = &elemRank;
++_numSets;
}

T &findSet(T &elem)
{
if (_parentOf[elem] != &elem)
_parentOf[elem] = &findSet(*_parentOf[elem]);
return (*_parentOf[elem]);
}

void unify(T &elemA, T &elemB)
{
--_numSets;
}

{
if (*_rankOf[setA] < *_rankOf[setB])
_parentOf[setA] = &setB;
else
{
_parentOf[setB] = &setA;
if (*_rankOf[setB] == *_rankOf[setA])
++(*_rankOf[setB]);
}
}

private:
HashMap<T, T> _parentOf;
HashMap<T, int> _rankOf;
int _numSets = 0;
};


In a separate file, you might want to actually use the disjoint data structure to do something. Here is an example of such a file. Note that Vertex doesn't have a rank data member or a parent data member.

File vertex.cc:

#include "disjoint.h"
#include <iostream>

using namespace std;

class Vertex
{
public:
Vertex(int val): _val (val){}
~Vertex(){}

int valOf(){ return _val; }

private:
int _val = 0;
};

int main()
{
//Have fun with Kruskal's algorithm or whatever
DisjointSets<Vertex> sets;
Vertex a(1);
Vertex b(2);

sets.makeSet(a);
sets.makeSet(b);
//etc.
return 1;
}


This gets the job done, but I really don't like it. It seems very hacky. I have to use the address as a hash, which doesn't seem safe. I have to use pointers as the stored value of the HashMap, which isn't quite like a real data member.

Any advice is appreciated. Alternatively, if this whole approach is bad, please let me know what the better alternative is. I've been told that I shouldn't find myself in a position where I want to add a new data member without changing the original class definition - I feel I've given a good example here of where this is necessary.

• Adding new features to existing classes in C++ is typically done by aggregation or inheritance. It's not clear to me why neither of these mechanisms is used, and not clear to me what actual problem you're trying to solve. – Edward Oct 7 '18 at 16:41