Generic Graph Library

I've been working on a generic graph library for a while now, in a bit of an off and on fashion. I realise that boost::graph exists, but it is a complex library that allows the user a huge amount of customisation. I have gone for a different approach; I constrain the library user much more, but this (hopefully) makes usage simpler.

There are a few goals I have with this library:

-
Relative simplicity of interface and use, mimicking the STL where possible.

-
Decent error messages using a combination of traits and static_assert, where possible.

-
Insertion and lookup speed. Memory usage is much less of a concern.

A few design considerations up front (I'm happy for these to be criticised):

-
Usage of std::map and std::set over their unordered counterparts. This places a smaller burden on the user, in that they don't have to supply a hashing function or specialise std::hash for their given type.

-
Graphs are segmented by two categories: whether they are directed or undirected, and whether they are weighted or unweighted (that is, if the edges have a weight or not).

-
As many algorithms as possible should be free functions to increase reusability.

The parts I've picked out for review correspond to unweighted graphs.


graph_traits.hpp

#ifndef GRAPH_TRAITS_SGL_HPP_ 
#define GRAPH_TRAITS_SGL_HPP_ 

namespace simplegl 
{
namespace graph
{

template 
struct is_weighted;

template 
struct is_directed;

} // end namespace graph
} // end namespace sgl

#endif // GRAPH_TRAITS_SGL_HPP_

graph_base.hpp

```
// Note: This is an internal header file, and shouldn't be imported directly.

#ifndef GRAPH_BASE_SGL_HPP_
#define GRAPH_BASE_SGL_HPP_

#include
#include
#include
#include
#include
#include
#include
#include
#include

#include "boost/optional.hpp"

namespace simplegl
{
namespace graph
{
namespace detail
{
//Base to utilize for unweighted graphs
template
struct graph_base
{
using allocator = Allocator;
using refer

Subtypes names

First of all, I would make sure that the type names in your classes match those in the standard library classes. We can see that some of them differ:

• allocator should be allocator_type.

• base_container should be container_type.

Subtypes correctness

You have something really strange in graph_base:

• using value_type = std::pair;

• using reference = typename allocator::reference;

Since you often pass std::allocator as the Allocator template parameter, that means that in your class, reference_type != value_type& (and it seems that the problem is propagated in the children types). I think that this is never the case in the standard library and I would totally expect value_type& and reference to be equivalent.

You don't seem to be using value_type directly, so I will assume that this is an error that you didn't spot.

From the other typedefs, I also assume that you are interested in exposing Type to the user of your class and that you don't want it to know that much how your class resembles a mapping type. Therefore, you should change graph_base::value_type to:

using value_type = Type;

Allocators

In graph_base again, this line lind of smells:

using base_container = std::map;

It seems that you are feeding a std::allocator to std::map (when you ) which is supposed to allocate std::pair instances, not Type instances. It should be:

using base_container = std::map>>;

Towards a solution?

One way to prevent all this allocator stuff would be to take containers as template parameters, like std::queue and let it handle all the allocator-related problems:

template ,
          typename Container = std::map>
struct graph_base
{
    // std::map-related types
    using container_type = Container;
    using key_type       = typename container_type::key_type;     
    using mapped_type    = typename container_type::mapped_type;

    // std::set-related types
    using value_type      = Type;
    using allocator_type  = typename Mapped::allocator_type;
    using reference       = typename allocator_type::reference;
    using const_reference = typename allocator_type::const_reference;
    using size_type       = typename allocator_type::size_type;
    using difference_type = typename allocator_type::difference_type;
    using pointer         = typename allocator_type::pointer;
    using const_pointer   = typename allocator_type::const_pointer;

    // ...
};

Note that I removed the types key_compare and value_compare: they weren't used and they prevent users from using an std::unordered_map for Container since std::unordered_map only cares about hasing and equality; it does not care about ordering relations.

Also, from a user perspective, I think that functions taking a key_type should rather take a value_type instead (as redefined in "Subtypes correctness"): they probably want to use "values of the graph", not "instance of the key type of the hidden underlying map". That would make more sense.

Exception safety

Your method insert_edge in undirected_graph does not seem to provide a strong exception guarantee. It may insert one of the edges and not then throw without removing the edge. You should rewrite your code to have the commit-or-rollback guarantee:

bool insert_edge(const Type& from, const Type& to) 
{
    // check whether you can safely insert both
    bool a = /* something non-destructive */ ;
    bool b = /* something non-destructive */ ;

    // if there is a problem, throw
    if(a != b) {
        throw invariant_exception(
            "Undirected graph invariant broken - directed edge found");
    }

    // if there is no problem, commit
    base_type::insert_edge(from, to);
    base_type::insert_edge(to, from);
    return a; 
}

There may be the same problem in remove_edge.

StackExchange Code Review Q#55402, answer score: 6