Graph library including minimum spanning tree using Kruskal's Algorithm

Question

I've only ever made small programs. So, I've tried to make something large but easily reusable/extendable. Posted below are the beginnings of a graph library I've written up.

One particular point I'd like to ask about is my use of the class HashMap. I wanted to be able to hash easily and by memory address. This approach gives me a lot of flexibility, but it also feels hacky. I'd like to get a sense from people if this approach seems too strange, or if it is acceptable.

Anyway, it's sort of a lot of code. You're obviously not obligated to look at all (or any!) of it. Any comments, even if on a small segment of the code, are appreciated.

The files are: hashMap.h > disjointSets.h > graph.h > minSpanTree.h, with dependencies in that order.

hashMap.h

#ifndef HASHMAP_H
#define 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;
};
#endif

graph.h:

#ifndef GRAPH_H
#define GRAPH_H

#include <iostream>
#include <vector>
#include "hashMap.h"

using namespace std;

class Vertex
{
public:
    Vertex(float val): _val (val), _id (0) {}
    Vertex(int id): _val (0), _id (id) {} 
    Vertex(int id, float val): _val (val), _id (id) {}
    ~Vertex(){}

    int id() const { return _id; }
    int val() const { return _val; }

private:
    float _val;
    int _id;
};

class Edge
{
public:
    Edge(Vertex *to, Vertex *from): _to (to), _from (from), _weight (1.){}
    Edge(Vertex *to, Vertex *from, float w): _to (to), _from (from), _weight (w){}
    ~Edge(){}

    void show()
    { 
        cout << (*_to).id() << " <-(" << _weight; 
        cout << ")- " << (*_from).id() << endl; 
    }

    Vertex &to() const { return *_to; }
    Vertex &from() const { return *_from; }
    float weight() const { return _weight; }

private:
    Vertex *_to;
    Vertex *_from;
    float _weight;
};

class Graph
{
public:
    Graph(int numVertices)
    {
        _numVertices = 0;
        for(int i=0; i < numVertices; i++)
        {
            _vertices.push_back( Vertex(_numVertices) ); 
            ++_numVertices;
        }
    }

    ~Graph(){}

    vector<Vertex*> adj(Vertex &v){ return _adjHashMap[v]; }
    vector<Vertex> &vertices(){ return _vertices; }
    vector<Edge> &edges(){ return _edges; }

    void connectTo(Vertex &v, Vertex &u, float weight)
    { //TODO: if isConnectedTo, don't connect!
        Vertex *uptr = &u;
        Vertex *vptr = &v;
        _adjHashMap[v].push_back(uptr);

        Edge newEdge(uptr, vptr, weight);
        _edges.push_back(newEdge);
    }

    void connectTo(Vertex &v, Vertex &u){ connectTo(v, u, 1.); }

    bool isConnectedTo(Vertex &v, Vertex &u)
    {
        vector<Vertex* > adj = _adjHashMap[v];
        for(Vertex *vptr : adj)
            if (vptr == &u) return true;
        return false; 
    }

private:
    vector<Vertex> _vertices;
    vector<Edge> _edges;
    HashMap<Vertex, vector<Vertex*> > _adjHashMap;
    int _numVertices;
};
#endif

disjoint.h:

#ifndef DISJOINT_H
#define DISJOINT

#include "hashMap.h"

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

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

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

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

    void link(T &setA, T &setB)
    {
        if (_rankOf[setA] < _rankOf[setB])
            _parentOf[setA] = &setB;
        else
        {
            _parentOf[setB] = &setA;
            if (_rankOf[setB] == _rankOf[setA])
                ++(_rankOf[setB]);
        }
    } 

    int numSets(){ return _numSets; }

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

minSpanTree.h:

#ifndef MST_H
#define MST_H

#include <algorithm>
#include "graph.h"
#include "disjoint.h"

using namespace std;

struct weight_less_than
{
   inline bool operator() (const Edge& a, const Edge &b)
   {
       return a.weight() < b.weight();
  }
};

vector<Edge> kruskal(Graph &g)
{
    vector<Edge> mst;
    vector<Edge> &es = g.edges();
    std::sort( es.begin(), es.end(), weight_less_than()); 
    vector<Vertex> &vs = g.vertices();
    DisjointSets<Vertex> sets;

    for (Vertex &v : vs)
        sets.makeSet(v);
    for (Edge &e : es)
    {
        Vertex &to = e.to();
        Vertex &from = e.from();
        if (&(sets.findSet(to)) != &(sets.findSet(from)))
        {
            sets.unify(to, from);
            mst.push_back(e);
        }
    }
    return mst;
}
#endif

One thing I quite like about how the code turned out was that the implementation of Kruskal's algorithm seems very readable, and very close to pseudo-code (at least for me - maybe I've become too familiar with it).

Any feedback appreciated.

Answer 1

hashMap.h

#ifndef HASHMAP_H
#define 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;
};
#endif

First of all, since your class doesn't provide much more than std::unordered_map, I would advise to dispense with it and use the standard container directly.

The only added-value is the keyed -> long conversion. About that: don't use C-style casting, C++ offers more obvious ways to do it, like in this case static_cast. Moreover, I don't understand why you don't use a map<keyed, val> in the first place; and if the compatibility requirement is convertibility to long, it is enough to have an operator[](const long& item), it'll make the conversion for you.

graph.h:

#ifndef GRAPH_H
#define GRAPH_H

#include <iostream>
#include <vector>
#include "hashMap.h"

using namespace std;

class Vertex
{
public:
    Vertex(float val): _val (val), _id (0) {}
    Vertex(int id): _val (0), _id (id) {} 
    Vertex(int id, float val): _val (val), _id (id) {}
    ~Vertex(){}

    int id() const { return _id; }
    int val() const { return _val; }

private:
    float _val;
    int _id;
};

I'm not a fan of 20-line classes that could be summed up to std::pair<int, float> and actually offer way fewer functionalities (operator< being maybe the most obvious one). If you stick to it, consider a more modern style (and don't mess with the order of initialization):

// constructors calling constructors
    Vertex(int id, float val): _val (val), _id (id) {}
    Vertex(float val): Vertex(0, val) {}
    Vertex(int id): Vertex(id, 0) {} 
// or, default member values
    Vertex(int id, float val): _val (val), _id (id) {}
    Vertex(float val): _val(val) {}
    Vertex(int id): _id(id) {} 
private:
    float _val = 0;
    int _id = 0;

You must also tread very carefully with your constructors, because how the compiler will choose between Vertex(float) and Vertex(int) is a very delicate matter and could surprise you. And what if the client uses a custom class convertible to both int and float?

You could also consider having a simple struct and use aggregate initialization

struct Vertex { int id=0; float val=0; };
Vertex v{1, 3.14};

C++20 will offer designators, so you would then write:

Vertex v{.id = 1, .val = 3.14};

A last point to make: use nicer names for your variables. id is better than _id, val than _val and value than val.

class Edge
{
public:
    Edge(Vertex *to, Vertex *from): _to (to), _from (from), _weight (1.){}
    Edge(Vertex *to, Vertex *from, float w): _to (to), _from (from), _weight (w){}
    ~Edge(){}

    void show()
    { 
        cout << (*_to).id() << " <-(" << _weight; 
        cout << ")- " << (*_from).id() << endl; 
    }

    Vertex &to() const { return *_to; }
    Vertex &from() const { return *_from; }
    float weight() const { return _weight; }

private:
    Vertex *_to;
    Vertex *_from;
    float _weight;
};

Same here: constructors, names, etc. Providing an operator<< is also more idiomatic than show methods

class Graph
{
public:
    Graph(int numVertices)
    {
        _numVertices = 0;

Frankly, using numVertices and _numVertices in the same function is like running with a sharp knife in your pocket. I hope you like pain.

        for(int i=0; i < numVertices; i++)
        {
            _vertices.push_back( Vertex(_numVertices) ); 
            ++_numVertices;
        }

Use standard algorithm to be more explicit. You can fill a container with std::fill or, if it follows a regular by-one increment, std::iota:

vertices(num_vertices);
std::iota(vertices.begin(), vertices.end(), 0);

Let's go on:

    }

    ~Graph(){}

    vector<Vertex*> adj(Vertex &v){ return _adjHashMap[v]; }

names, again: what does adj mean? adjacent vertices? adjacency map?

    vector<Vertex> &vertices(){ return _vertices; }
    vector<Edge> &edges(){ return _edges; }

    void connectTo(Vertex &v, Vertex &u, float weight)

v, u? Come on! canonical names would be src and dest, or lhs and rhs. That the letter 'u' comes before the letter 'v' is all the more confusing

    { //TODO: if isConnectedTo, don't connect!
        Vertex *uptr = &u;
        Vertex *vptr = &v;

You can use &src and &dest directly, no need to create more variables here

        _adjHashMap[v].push_back(uptr);

        Edge newEdge(uptr, vptr, weight);
        _edges.push_back(newEdge);
    }

    void connectTo(Vertex &v, Vertex &u){ connectTo(v, u, 1.); }

Consider having only one connectTo signature with a default weight value.

    bool isConnectedTo(Vertex &v, Vertex &u)
    {
        vector<Vertex* > adj = _adjHashMap[v];
        for(Vertex *vptr : adj)
            if (vptr == &u) return true;
        return false; 
    }

Again, using standard algorithms is more explicit:

        const auto& adjacent_vertices = adjacency_map[src];
        const auto found = std::find(adjacent_vertices.begin(), adjacent_vertices.end(), dest);
        return found != adjacent_vertices.end();

Moving on

private:
    vector<Vertex> _vertices;
    vector<Edge> _edges;
    HashMap<Vertex, vector<Vertex*> > _adjHashMap;
    int _numVertices;
};
#endif

disjoint.h:

#ifndef DISJOINT_H
#define DISJOINT

#include "hashMap.h"

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

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

I would rather make the parent of elem a nullptr, as it is more idiomatic

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

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

    void link(T &setA, T &setB)
    {
        if (_rankOf[setA] < _rankOf[setB])
            _parentOf[setA] = &setB;
        else
        {
            _parentOf[setB] = &setA;
            if (_rankOf[setB] == _rankOf[setA])
                ++(_rankOf[setB]);
        }
    } 

    int numSets(){ return _numSets; }

I do agree with you that this part of your code is very good and clear. Moreover it's cleverly optimized to make the tree flatter and more balanced.

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

minSpanTree.h:

#ifndef MST_H
#define MST_H

#include <algorithm>
#include "graph.h"
#include "disjoint.h"

using namespace std;

struct weight_less_than
{
   inline bool operator() (const Edge& a, const Edge &b)
   {
       return a.weight() < b.weight();
  }
};

Don't bother to create struct for that. Use a lambda directly inside your algorithm call (see below)

vector<Edge> kruskal(Graph &g)
{
    vector<Edge> mst;
    vector<Edge> &es = g.edges();
    std::sort( es.begin(), es.end(), weight_less_than()); 

so, as I said, use lambdas:

std::sort(es.begin(), es.end(), [](const auto& lhs, const auto& rhs) {
    return lhs.weight < rhs.weight;
});

Let's go on:

    vector<Vertex> &vs = g.vertices();
    DisjointSets<Vertex> sets;

    for (Vertex &v : vs)

There is this constness problem all along your code; I've moved on too fast to underline it everywhere. But I've seen it in the other review: const should be the default!

        sets.makeSet(v);
    for (Edge &e : es)
    {
        Vertex &to = e.to();
        Vertex &from = e.from();
        if (&(sets.findSet(to)) != &(sets.findSet(from)))
        {
            sets.unify(to, from);
            mst.push_back(e);
        }
    }
    return mst;
}
#endif

Answer 2

I see a number of things that may help you improve your program.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Know when to use it and when not to (as when writing include headers).

Don't use std::endl if you don't really need it

The difference betweeen std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

Use const where practical

The underlying Graph is not and should not be altered by the kruskal algorithm. For that reason, I would advise changing the signature of the function to this:

std::vector<Edge> kruskal(const Graph &g)

This has a ripple effect through the interface, which will help sharpen your thinking about which things really need to be modified, and which don't.

Let the compiler create default destructor

The compiler will create a destructor by default which is essentially identical to what you've got, so you can simply omit both the declaraton and implementation from your code. Same thing with empty constructors. They add nothing but clutter. If you wish to explicitly use the default, write this:

HashMap() = default;

Think carefully about object ownership

The kruskal routine returns a collection of Edges which each, in turn, refer to a pair of Vertex. What happens if those objects are all out of scope when the collection is accessed? (Hint: boom!!!) Instead, because the collection assumes some invariants (such as the fact that each Edge points to two Vertex objects that are both valid and still exist), the class should be responsible for making sure that invariant always holds true. It shouldn't, for example, be possible for a Vertex to be deleted without all the corresponding Edges to also be deleted. That would make this a much more robust class design. One method to address this might be to use smart pointers rather than raw pointers.

Provide test code

This has more to do with getting useful reviews than necessarily about your code, but showing an example of how you expect your code to be used is very useful to both reviewers, and to yourself, to clarify that how you'd like to write the code is actually how the code is structured. Here's what I used to test your code:

#include "minSpanTree.h"

int main() {
    Graph g(5);
    g.connectTo(g.vertices()[0], g.vertices()[4], 1);
    g.connectTo(g.vertices()[0], g.vertices()[1], 3);
    g.connectTo(g.vertices()[1], g.vertices()[4], 4);
    g.connectTo(g.vertices()[1], g.vertices()[2], 5);
    g.connectTo(g.vertices()[2], g.vertices()[3], 2);
    g.connectTo(g.vertices()[2], g.vertices()[4], 6);
    g.connectTo(g.vertices()[3], g.vertices()[4], 7);
    g.show();
    auto m{kruskal(g)};
    g.show(m);
}

The show command was one I added, but I don't think the connectTo calls are very nice -- there is a lot of opportunity for error there.