I have been working on a library to represent graphs (directed graphs and undirected graphs). I know that there are already many such libraries but I wanted to create my own as a learning exercise.
I have not tested the library extensively so there are likely to be bugs etc. But what I am really interested in is the design of the library - I spent quite a while thinking about the best design for the interface etc.
There is an abstract base class which DiGraph (directed graph) and UDiGraph (undirected graph) inherit from. I have designed as a template so that each Vertex and each Edge can have an associated user supplied object.
Thanks
// Graph.h
#include <map>
#include <set>
#include <stdexcept>
#include <algorithm>
#include <optional>
#ifndef GRAPH_H
#define GRAPH_H
namespace GLib
{
template <class V, class E>
class GraphABC
{
// TYPES/DEFINITIONS
public:
using VertexID = signed int;
protected:
GraphABC(){} // makes class abstract
using EdgeObjectID = unsigned int;
using VertexEdgeMapping = std::multimap<VertexID, EdgeObjectID>;
enum EDGE_OBJECT_CODE {NO_EDGE_OBJECT = -1};
public:
using EdgeIterator = VertexEdgeMapping::const_iterator;
using VertexIterator = typename std::map<VertexID, V>::const_iterator;
//MEMBERS
public:
// vertex member functions
bool vertexExists(VertexID vertex) const
{
return mVertices.count(vertex);
}
V getVertexObject(VertexID vertex) const
{
if (!vertexExists(vertex))
{
throw std::out_of_range("no such vertex");
}
if (!vertexHasObject(vertex))
{
throw std::invalid_argument("vertex has no such object");
}
return mVertices.at(vertex).value();
}
bool vertexHasObject(VertexID vertex) const
{
return mVertices.at(vertex).has_value();
}
VertexIterator verticesBegin() const
{
return mVertices.cbegin();
}
VertexIterator verticesEnd() const
{
return mVertices.cend();
}
GraphABC<V,E>& addVertex(VertexID idForNewVertex, const V& vertexOb)
{
if ( vertexExists(idForNewVertex) )
{
throw std::invalid_argument("ID already exists");
}
mVertices[idForNewVertex] = vertexOb; // create vertex
mEdges.insert(std::pair<VertexID, VertexEdgeMapping>(idForNewVertex, VertexEdgeMapping())); // insert vertex in list of edges (empty by default)
return *this;
}
VertexID addVertex(const V& vertexOb)
{
for(VertexID potentialId = 0; ; ++potentialId)
{
if (mVertices.count(potentialId) == 0)
{
mVertices[potentialId] = vertexOb;
mEdges.insert(std::pair<VertexID, VertexEdgeMapping>(potentialId, VertexEdgeMapping())); // insert vertex in list of edges (empty by default)
return potentialId;
}
}
}
GraphABC<V,E>& addVertex(VertexID idForNewVertex)
{
if (vertexExists(idForNewVertex))
{
throw std::invalid_argument("ID already exists");
}
mVertices[idForNewVertex] = std::nullopt; // no vertex object
mEdges.insert(std::pair<VertexID, VertexEdgeMapping>(idForNewVertex, VertexEdgeMapping())); // insert vertex in list of edges (empty by default)
return *this;
}
bool setVertexObject(VertexID vertex, const V& vertexOb)
{
if (!vertexExists(vertex))
{
throw std::out_of_range("no such vertex");
}
mVertices[vertex] = vertexOb;
return true;
}
bool deleteVertex(VertexID vertexToDelete)
{
if (!vertexExists(vertexToDelete))
{
throw std::out_of_range("no such vertex");
}
mVertices.erase(vertexToDelete);
mEdges.erase(vertexToDelete); // delete all elements in map where key is vector
for ( auto it = mEdges.begin(); it != mEdges.end(); ++it )
{
it->second.erase(vertexToDelete); // loop through elements of mmap and delete any value which is vector
}
removeRedundantEdgeObjects(); // delete unused edges
return true;
}
EdgeIterator edgesOfVertexBegin(VertexID vertex) const
{
if (!vertexExists(vertex))
{
throw std::out_of_range("no such vertex");
}
return mEdges.at(vertex).cbegin();
}
EdgeIterator edgesOfVertexBegin(VertexID originVertex, VertexID destVertex) const
{
if (!vertexExists(originVertex) || !vertexExists(destVertex))
{
throw std::out_of_range("no such vertex");
}
return mEdges.at(originVertex).lower_bound(destVertex);
}
EdgeIterator edgesOfVertexEnd(VertexID vertex) const
{
if (!vertexExists(vertex))
{
throw std::out_of_range("no such vertex");
}
return mEdges.at(vertex).cend();
}
EdgeIterator edgesOfVertexEnd(VertexID originVertex, VertexID destVertex)
{
if (!vertexExists(originVertex) || !vertexExists(destVertex))
{
throw std::out_of_range("no such vertex");
}
return mEdges.at(originVertex).upper_bound(destVertex);
}
bool edgeObjectExists(EdgeObjectID edgeObjectID) const
{
return mEdgeObjects.count(edgeObjectID);
}
E getEdgeObject(EdgeObjectID edgeObjectID) const
{
if (mEdgeObjects.count(edgeObjectID) == 0)
{
throw std::out_of_range("no such edge object");
}
return mEdgeObjects.at(edgeObjectID);
}
void setEdgeObject(EdgeObjectID edgeObjectID, const E& edgeObject)
{
if (mEdgeObjects.count(edgeObjectID) == 0)
{
throw std::out_of_range("no such edge object");
}
mEdgeObjects[edgeObjectID] = edgeObject;
}
// convenience functions
std::set<VertexID> adjacentVertices(VertexID vertex) const
{
if (!vertexExists(vertex))
{
throw std::out_of_range("no such vertex");
}
std::set<VertexID> adjVertices;
for (auto edgeIt = edgesOfVertexBegin(vertex); edgeIt != edgesOfVertexEnd(vertex); ++edgeIt)
{
adjVertices.insert((*edgeIt).first);
}
return adjVertices;
}
std::set<VertexID> adjacentVertices(VertexID vertex, std::function<bool (VertexID)> evalFunc)
{
if (!vertexExists(vertex))
{
throw std::out_of_range("no such vertex");
}
std::set<VertexID> adjVertices;
for (auto edgeIt = edgesOfVertexBegin(vertex); edgeIt != edgesOfVertexEnd(vertex); ++edgeIt)
{
if ( evalFunc( (*edgeIt).first ) )
{
adjVertices.insert((*edgeIt).first);
}
}
return adjVertices;
}
protected:
std::map<VertexID, VertexEdgeMapping> mEdges;
std::map<EdgeObjectID, E> mEdgeObjects;
std::map< VertexID, std::optional<V> > mVertices;
EdgeObjectID addEdgeObject(const E& e)
{
for (EdgeObjectID potentialID = 0; ;++potentialID)
{
if (mEdgeObjects.count(potentialID) == 0)
{
mEdgeObjects[potentialID] = e;
return potentialID;
}
}
}
size_t removeRedundantEdgeObjects() // delete any edge objects which are not used in any edges
{
std::set<EdgeObjectID> currentEdgeObjectIDs, edgeObjectIDsInEdges;
for(auto edgeObjectIt = mEdgeObjects.begin(); edgeObjectIt!= mEdgeObjects.end(); ++edgeObjectIt)
{
currentEdgeObjectIDs.insert((*edgeObjectIt).first);
}
for(typename decltype(mEdges)::iterator it = mEdges.begin(); it != mEdges.end(); ++it)
{
for(VertexEdgeMapping::iterator mappingIt = (*it).second.begin(); mappingIt!=(*it).second.begin(); ++mappingIt)
{
if ((*mappingIt).second == NO_EDGE_OBJECT )
{
continue;
}
edgeObjectIDsInEdges.insert((*mappingIt).second);
}
}
std::set<EdgeObjectID> redundantEdgeObjects;
std::set_difference(currentEdgeObjectIDs.begin(), currentEdgeObjectIDs.end(),
edgeObjectIDsInEdges.begin(), edgeObjectIDsInEdges.end(),
std::inserter(redundantEdgeObjects, redundantEdgeObjects.begin()) );
for(EdgeObjectID redundantEdgeID : redundantEdgeObjects)
{
mEdgeObjects.erase(redundantEdgeID);
}
return redundantEdgeObjects.size();
}
};
template <class V, class E>
class DiGraph : public GraphABC <V, E>
{
public:
using VertexID = typename GraphABC<V,E>::VertexID;
using EdgeObjectID = typename GraphABC<V,E>::EdgeObjectID;
using EdgeIterator = typename GraphABC<V,E>::EdgeIterator;
DiGraph<V,E>& addEdgeFromTo(VertexID vertex_1, VertexID vertex_2, const E& edgeToAdd)
{
if ( !GraphABC<V,E>::vertexExists(vertex_1) || !GraphABC<V,E>::vertexExists(vertex_2) )
{
throw std::out_of_range("vertex does not exist");
}
EdgeObjectID generatedEdgeObjectID = GraphABC<V,E>::addEdgeObject(edgeToAdd);
this->mEdges[vertex_1].insert(std::pair<VertexID, EdgeObjectID> (vertex_2, generatedEdgeObjectID) );
return *this;
}
DiGraph<V,E>& addEdgeFromTo(VertexID vertex_1, VertexID vertex_2, EdgeObjectID edgeIdToUse)
{
if ( !GraphABC<V,E>::vertexExists(vertex_1) || !GraphABC<V,E>::vertexExists(vertex_2))
{
throw std::out_of_range("vertex does not exist");;
}
if (this->mEdgeObjects.count(edgeIdToUse) == 0 )
{
throw std::out_of_range("edge object does not exist");
}
this->mEdges[vertex_1].insert(std::pair<VertexID, EdgeObjectID>(vertex_2, edgeIdToUse));
return *this;
}
DiGraph<V,E>& addEdgeFromTo(VertexID vertex_1, VertexID vertex_2)
{
if ( !GraphABC<V,E>::vertexExists(vertex_1) || !GraphABC<V,E>::vertexExists(vertex_2) )
{
throw std::out_of_range("vertex does not exist");
}
this->mEdges[vertex_1].insert(std::pair<VertexID, EdgeObjectID>(vertex_2, GraphABC<V,E>::NO_EDGE_OBJECT));
return *this;
}
size_t deleteAllEdgesFrom(VertexID vertex)
{
if ( !GraphABC<V,E>::vertexExists(vertex) )
{
return false;
}
size_t deletedEdgeCount = this->mEdges[vertex].size();
this->mEdges[vertex].clear(); // use clear not erase - still need key if vector exists
GraphABC<V,E>::removeRedundantEdgeObjects();
return deletedEdgeCount;
}
size_t deleteAllEdgesFromTo(VertexID vertex_1, VertexID vertex_2)
{
if ( !GraphABC<V,E>::vertexExists(vertex_1) || !GraphABC<V,E>::vertexExists(vertex_2) )
{
return false;
}
size_t deletedEdgeCount = this->mEdges[vertex_1].erase(vertex_2);
GraphABC<V,E>::removeRedundantEdgeObjects();
return deletedEdgeCount;
}
void deleteEdgeFrom(VertexID vertex, EdgeIterator edgeIt)
{
if ( !GraphABC<V,E>::vertexExists(vertex) )
{
throw std::out_of_range("vertex does not exist");;
}
this->mEdges[vertex].erase(edgeIt);
GraphABC<V,E>::removeRedundantEdgeObjects();
}
private:
};
template <class V, class E>
class UDiGraph : public GraphABC<V,E>
{
public:
using VertexID = typename GraphABC<V,E>::VertexID;
using EdgeObjectID = typename GraphABC<V,E>::EdgeObjectID;
using EdgeIterator = typename GraphABC<V,E>::EdgeIterator;
UDiGraph<V,E>& addEdgeBetween(VertexID vertex_1, VertexID vertex_2, const E& edgeToAdd)
{
if ( !GraphABC<V,E>::vertexExists(vertex_1) || !GraphABC<V,E>::vertexExists(vertex_2) )
{
throw std::out_of_range("vertex does not exist");
}
EdgeObjectID generatedEdgeObjectID = GraphABC<V,E>::addEdgeObject(edgeToAdd);
// add mirror edges
this->mEdges[vertex_1].insert(std::pair<VertexID, EdgeObjectID> (vertex_2, generatedEdgeObjectID) );
this->mEdges[vertex_2].insert(std::pair<VertexID, EdgeObjectID>(vertex_1, generatedEdgeObjectID));
return *this;
}
UDiGraph<V,E>& addEdgeBetween(VertexID vertex_1, VertexID vertex_2, EdgeObjectID edgeIdToUse)
{
if ( !GraphABC<V,E>::vertexExists(vertex_1) || !GraphABC<V,E>::vertexExists(vertex_2))
{
throw std::out_of_range("vertex does not exist");;
}
if (this->mEdgeObjects.count(edgeIdToUse) == 0 )
{
throw std::out_of_range("edge object does not exist");
}
this->mEdges[vertex_1].insert(std::pair<VertexID, EdgeObjectID>(vertex_2, edgeIdToUse));
this->mEdges[vertex_2].insert(std::pair<VertexID, EdgeObjectID>(vertex_1, edgeIdToUse));
return *this;
}
UDiGraph<V,E>& addEdgeBetween(VertexID vertex_1, VertexID vertex_2)
{
if ( !GraphABC<V,E>::vertexExists(vertex_1) || !GraphABC<V,E>::vertexExists(vertex_2) )
{
throw std::out_of_range("vertex does not exist");
}
this->mEdges[vertex_1].insert(std::pair<VertexID, EdgeObjectID>(vertex_2, GraphABC<V,E>::NO_EDGE_OBJECT));
this->mEdges[vertex_2].insert(std::pair<VertexID, EdgeObjectID>(vertex_1, GraphABC<V,E>::NO_EDGE_OBJECT));
return *this;
}
void deleteEdgeFrom(VertexID vertex, EdgeIterator edgeIt)
{
if ( !GraphABC<V,E>::vertexExists(vertex) )
{
throw std::out_of_range("vertex does not exist");;;
}
// store vertex details before deleting
VertexID adjVertex = (*edgeIt).first;
EdgeObjectID eObId = (*edgeIt).second;
// delete outward edge
this->mEdges[vertex].erase(edgeIt);
// delete inward edge
for(EdgeIterator adjVertexEdgeIt = GraphABC<V,E>::edgesOfVertexBegin(adjVertex, vertex); adjVertexEdgeIt != GraphABC<V,E>::edgesOfVertexEnd(adjVertex, vertex); ++adjVertexEdgeIt)
{
if ( (*adjVertexEdgeIt).second == eObId ) // delete mirrored edge with same object ID
{
this->mEdges[adjVertex].erase(adjVertexEdgeIt);
GraphABC<V,E>::removeRedundantEdgeObjects();
return;
}
}
throw std::logic_error("could not find corresponding edge to delete");
}
size_t deleteAllEdgesBetween(VertexID vertex_1, VertexID vertex_2)
{
if ( !GraphABC<V,E>::vertexExists(vertex_1) && !GraphABC<V,E>::vertexExists(vertex_2) )
{
throw std::out_of_range("vertex does not exist");
}
this->mEdges[vertex_1].erase(vertex_2);
size_t deletedEdges = this->mEdges[vertex_2].erase(vertex_1);
GraphABC<V,E>::removeRedundantEdgeObjects();
return deletedEdges;
}
private:
};
}
#endif
// main.cpp
#include <iostream>
#include "Graph.h"
using namespace GLib;
int main()
{
// example of directed graph
DiGraph<std::string, std::string> graph;
DiGraph<std::string, std::string>::VertexID A = graph.addVertex("A"); // 0
DiGraph<std::string, std::string>::VertexID B = graph.addVertex("B"); // 1
DiGraph<std::string, std::string>::VertexID C = graph.addVertex("C"); // 2
DiGraph<std::string, std::string>::VertexID D = graph.addVertex("D"); // 3
DiGraph<std::string, std::string>::VertexID E = graph.addVertex("E"); // 4
DiGraph<std::string, std::string>::VertexID F = graph.addVertex("F"); // 5
graph.addEdgeFromTo(A, B, "A to B");
graph.addEdgeFromTo(A, C, "A to C");
graph.addEdgeFromTo(C, D, "C to D");
graph.addEdgeFromTo(C, D, "c to d");
graph.addEdgeFromTo(D, E, "D to E");
graph.addEdgeFromTo(D, F, "D to F");
// print all outward edges of C
for (auto it = graph.edgesOfVertexBegin(C); it!=graph.edgesOfVertexEnd(C); ++it)
{
std::cout << graph.getEdgeObject ( (*it).second ) << std::endl;
}
}