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.