Library to represent graphs

Question

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;
    }
}

Answer 1

Prefer = default over {}

When you have to explicitly define a constructor (or other special member function) but it shouldn't do anything, prefer = default over {}. See this post for more information why.

Don't use .count() if you only want to know if something exists

count() tries to count all matches, which might take more effort than just checking if there is any match. For a std::map, this might not matter, but for a std::multimap it does. But to avoid any doubt, prefer using find(), or if you can use C++20, use contains().

Consider returning vertices by const reference

If V is a potentially large and/or non-copyable object, returning by value can be problematic. Consider returning by const reference.

Inconsistent and useless return types

It's weird to have two overloads over addVertex(), one returns a VertexID, the other returns a reference to *this. Instead of having addVertex(const V&), consider adding a function that returns an unused VertexID, which can then be used as input for the other overload of addVertex().

Why do setVertexObject() and deleteVertex() return a bool, when they always return true? Either I expect errors to cause false to be returned instead of exceptions being thrown, or the function should return void.

Inconsistent use of at()

Sometimes you use at(), other times you use []. Using at() will cause an exception being thrown if the key cannot be found. If you are checking if vertexExists() anyway, then at() is redundant. Conversely, you can just do:

const V& getVertexObject(VertexID vertex) const
{
    return mVertices.at(vertex).value();
}

And at() and value() will throw expections if the vertex ID does not exist or there is no value for that ID, so you don't need to explicitly check for that yourself.

Use -> where appropriate

Instead of (*foo).bar, write the more idiomatic foo->bar.

Use range-for where appropriate

Instead of manually looping with iterators, use range-based for loops where possible. This simplifies your code and leaves less chance for errors. For example:

for (auto& it: mEdges)
{
    it.second.erase(vertexToDelete);
}

It becomes even nicer for maps if you use structured bindings:

for (auto& [vertexID, edgeMapping]: mEdges)
{
    edgeMapping.erase(vertexToDelete);
}

Also consider making your graph class be usable in range-for loops, by renaming verticesBegin() and verticesEnd() to begin() and end(). Even better, add a member function edgesOfVertex() that returns a const reference to an element of mEdges, so that you can write:

for (auto& [vertexID, edgeID]: graph.edgesOfVertex(C))
{
    std::cout << graph.getEdgeObject(edgeID) << '\n';
}

Make use of emplace()

Instead of insert(), consider using emplace() to simplify your code. Instead of:

mEdges.insert(std::pair<VertexID, VertexEdgeMapping>(idForNewVertex, VertexEdgeMapping()));

You can write:

mEdges.emplace(idForNewVertex, VertexEdgeMapping());

Of course you could also just have written:

mEdges[idForNewVertex] = {};

Faster way of finding a free VertexID

In addVertex(const V&), you are linearly searching through mVertices to find an unused ID. If you have never deleted any IDs, this is an \$O(V)\$ operation, where \$V\$ is the number of vertices. However, since it's OK to have holes in the range of used vertex IDs, you can simply look for the highest vertex ID present, and just add one to that:

if (mVertices.empty())
{
    potentialID = 0;
}
else
{
    potentialID = (mVertices.end() - 1)->first + 1;
}

Of course you might need to worry about what happens when the ID becomes so large that it doesn't fit in a signed int anymore, in which case you might want to have a fallback to linearly scan for available IDs again.

And this only works when using std::map, as that keeps the elements sorted. Which brings me to:

Consider using std::unordered_map

Most operations don't require that vertices and edges are sorted by their ID. Consider using std::unordered_maps instead, as they have \$O(1)\$ lookups instead of the \$O(\log N)\$ lookup time of std::map.

Do you need so many maps?

You have three maps; one that stores the vertex objects, one that stores edge objects, and one that stores the adjacency information. You have VertexIDs, which are indeed helpful to distinguish vertices, but then you also have EdgeObjectIDs, and those seem redundant to me: edges can already be uniquely identified by two vertex IDs. For undirected graphs, you can use the rule that given two vertex IDs, the unique edge ID is always formed by the lower vertex ID first, then the higher vertex ID.

Consider creating a struct Vertex to pack the vertex object and the set of edges it has:

struct Vertex {
    std::optional<V> object;
    std::map<VertexID, E> edges;
};

Now you need only a single member variable to hold the whole graph:

std::map<VertexID, Vertex> mVertices;