13
\$\begingroup\$

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 <typename Graph>
struct is_weighted;

template <typename Graph>
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 <cstdint>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <map>
#include <set>
#include <type_traits>
#include <utility>

#include "boost/optional.hpp"

namespace simplegl
{
namespace graph
{
namespace detail
{
//Base to utilize for unweighted graphs
template <typename Type, typename Compare, typename Allocator>
struct graph_base
{
    using allocator       = Allocator;
    using reference       = typename allocator::reference;
    using const_reference = typename allocator::const_reference;
    using size_type       = typename allocator::size_type;
    using difference_type = typename allocator::difference_type;
    using pointer         = typename allocator::pointer;
    using const_pointer   = typename allocator::const_pointer;

    using key_type       = Type;                                                    
    using mapped_type    = std::set<Type, Compare, Allocator>;
    using value_type     = std::pair<const key_type, mapped_type>;
    using key_compare    = Compare;
    using value_compare  = Compare;
    using base_container = std::map<key_type, mapped_type, key_compare, allocator>;

    using const_iterator         = typename base_container::const_iterator;
    using const_reverse_iterator = typename base_container::const_reverse_iterator;
    using mapped_const_iterator  = typename mapped_type::const_iterator;

    base_container backing_map;
    size_type      num_nodes;
    std::uint64_t  num_edges;

    graph_base()
        : num_nodes(0),
          num_edges(0)
    { }

protected:

    //Disallow usage through a derived pointer, that is, we don't want something
    //like: graph_base<T>* graph = new undirected_graph<T>(). However, we do
    //want to publically inherit member functions from graph_base.
    //The above polymorphic usage will be a compilation error with a protected
    //destructor.
    ~graph_base() { }


public:

    //Convenience constructor to initialize the nodes of a graph.
    template <typename InputIterator>
    graph_base(InputIterator first, InputIterator last)
    {
        for(InputIterator it = first; it != last; ++it) {
            insert_node(*it);
        }
    }

    template <typename T>
    graph_base(std::initializer_list<T> init)
    {
        static_assert(std::is_convertible<T, key_type>::value, 
            "Initializer list type must be convertible to Node Type");
        for(auto it = init.begin(); it != init.end(); ++it) {
            insert_node(*it);
        }
    }

    // Number of nodes contained in the graph, |V|
    size_type node_size() const
    {
        return num_nodes;
    }

    // Number of edges in the graph, |E|
    std::uint64_t edge_size() const
    {
        return num_edges;
    }

    // True iff the graph contains at least 1 node
    bool empty() const
    {
        return backing_map.empty();
    }

    //Inserts a completely disconnected node into the graph.
    bool insert_node(const key_type& node)
    {
        auto it = backing_map.find(node);
        if(it == backing_map.end()) {
            backing_map.insert(std::make_pair(node, mapped_type{})); 
            ++num_nodes;
            return true;
        }
        return false;
    }

    bool insert_node(key_type&& node)
    {
        auto n = std::move(node);
        auto it = backing_map.find(n);
        if(it == backing_map.end()) {
            backing_map.insert(std::make_pair(std::move(n), mapped_type{}));
            ++num_nodes;
            return true;
        }
        return false;
    }

    // Returns true if the given node exists in the graph,
    // false otherwise.
    bool exists_node(const key_type& node) const 
    {
        return backing_map.find(node) != backing_map.end();
    }

    //Inserts an edge between from and to, ie, E = E + (from, to)
    //where E is the edge set of the graph.
    bool insert_edge(const key_type& from, const key_type& to)
    {
        auto from_in_nodes = backing_map.find(from);
        auto to_in_nodes = backing_map.find(to);
        auto end = backing_map.end();

        if(from_in_nodes != end && to_in_nodes != end) {
            mapped_type& adj_nodes = from_in_nodes->second;
            adj_nodes.insert(to);
            ++num_edges;
            return true;
        }
        return false;
    }

    template <typename T> 
    bool insert_edge(const key_type& from, T&& to)
    {
        static_assert(std::is_convertible<T, key_type>::value,
            "Edge type must be explicity convertible to Node type");

        auto from_in_nodes = backing_map.find(from);
        auto to_in_nodes = backing_map.find(to);
        auto end = backing_map.end();

        if(from_in_nodes != end && to_in_nodes != end) {
            mapped_type& adj_nodes = from_in_nodes->second;
            adj_nodes.insert(std::forward<T>(to));
            ++num_edges;
            return true;
        }
        return false;
    }


    template <typename Iterator>
    void insert_edges(const key_type& from, Iterator begin, Iterator end)
    {
        auto from_it = backing_map.find(from);
        if(from_it != backing_map.end()) {
            for(auto it = begin; it != end; ++it) {
                if(backing_map.find(*it) != backing_map.end()) {
                    mapped_type& adj_nodes = from_it->second;
                    adj_nodes.insert(*it);
                    ++num_edges;
                }
            }
        }
    }

    //Returns true if an edge exists between (from, to), or
    //false otherwise
    bool exists_edge(const key_type& from, const key_type& to) const
    {
        auto mp_it = backing_map.find(from);
        if(mp_it != backing_map.end()) {
            auto it = (mp_it->second).find(to);
            return it != mp_it->second.end();
        }
        return false;
    }

    //Removes the edge (from, to).
    bool remove_edge(const key_type& from, const key_type& to)
    {
        auto it = backing_map.find(from);
        if(it != backing_map.end()) {
            mapped_type& adj_nodes = it->second;
            if(adj_nodes.count(to)) {
                adj_nodes.erase(to);
                --num_edges;
                return true;
            }
        }    
        return false;
    }

    template <typename Func, typename... Args>
    auto update_node(key_type&& node, Func f, Args&&... args)
        -> boost::optional<decltype(f(node, args...))>
    {
        using result_type = decltype(f(node, args...));

        auto it = backing_map.find(node);
        if(it != backing_map.end()) {
            auto update(it->first);
            auto result = f(update, std::forward<Args>(args)...);
            mapped_type adj_nodes;
            std::swap(adj_nodes, it->second);
            backing_map.erase(it);
            backing_map.insert(std::make_pair(update, std::move(adj_nodes)));

            const auto& adjacent = backing_map.find(update)->second;
            for(auto n = adjacent.begin(); n != adjacent.end(); ++n) {
                mapped_type& m = backing_map.find(*n)->second;
                auto contains = m.find(node);
                if(contains != m.end()) {
                    m.erase(contains);
                    m.insert(update);
                }
            }
            return boost::optional<result_type>(result);
        }
        return boost::optional<result_type>();
    }

    // Returns a const_iterator that can be used to iterator
    // over all nodes contained within the graph.
    const_iterator begin() const
    {
        return backing_map.begin();
    }

    const_iterator end() const
    {
        return backing_map.end();
    }

    const_reverse_iterator rbegin() const
    {
        return backing_map.rbegin();
    }

    const_reverse_iterator rend() const
    {
        return backing_map.rend();
    }

    const_iterator find_node(const key_type& node) const
    {
        return backing_map.find(node);
    }

    //Calculates the outdegree of a given node, that is,
    //the number of nodes it is adjacent to.
    size_type outdegree(const key_type& node) const
    {
        auto it = backing_map.find(node);
        const mapped_type& s = it->second;
        return s.size();
    }

    //Returns a pair of iterators, pointing to the beginning
    //of the set of adjacent nodes and the end of the set of adjacent
    //nodes respectively.
    std::pair<mapped_const_iterator, mapped_const_iterator> 
    adjacent_nodes(const key_type& node) const
    {
        auto it = backing_map.find(node);
        if(it == backing_map.end()) {
            const mapped_type& begin_s = (backing_map.begin())->second;
            return std::make_pair(begin_s.begin(), begin_s.begin());
        }
        return std::make_pair((it->second).begin(), (it->second).end());
    }
}; //end struct graph_base

} //end namespace detail
} //end namespace graph
} //end namespace simplegl

#endif //GRAPH_BASE_SGL_HPP_

undirected_graph.hpp

#ifndef UNDIRECTED_GRAPH_SGL_HPP_
#define UNDIRECTED_GRAPH_SGL_HPP_

#include <functional>
#include <iterator>
#include <limits>
#include <map>
#include <memory>
#include <set>
#include <utility>

#include "graph/graph_traits.hpp"
#include "graph/invariant_exception.hpp"
#include "graph/structure/detail/graph_base.hpp"

namespace simplegl
{
namespace graph
{

//Class defining an undirected, unweighted graph
template <typename Type, 
          typename Compare = std::less<Type>,
          typename Allocator = std::allocator<Type>>
class undirected_graph
    : public detail::graph_base<Type, Compare, Allocator>
{
private:

    using base_type = detail::graph_base<Type, Compare, Allocator>;

public:

    using allocator = Allocator;

    using key_type        = typename base_type::key_type; 
    using mapped_type     = typename base_type::mapped_type;
    using value_type      = typename base_type::value_type;
    using key_compare     = typename base_type::key_compare;
    using value_compare   = typename base_type::value_compare;
    using reference       = typename base_type::reference;
    using const_reference = typename base_type::const_reference;
    using pointer         = typename base_type::pointer;
    using const_pointer   = typename base_type::const_pointer;

    using const_iterator           = typename base_type::const_iterator;
    using const_reverse_iterator   = typename base_type::const_reverse_iterator;
    using const_adjacency_iterator = typename base_type::mapped_const_iterator;
    using size_type                = typename base_type::size_type;
    using difference_type          = typename base_type::difference_type;

    using node_type = key_type;

    undirected_graph()
        : base_type()
    { }

    //Convenience constructor to initialize an undirected_graph utilizing
    //any kind of input iterator. 
    template <typename InputIterator>
    undirected_graph(InputIterator first, InputIterator last) 
        : base_type(first, last)
    { }

    template <typename T>
    undirected_graph(std::initializer_list<T> init)
        : base_type(init)
    { }

    //Inserts an edge between from and to, ie, E = E + (from, to).
    //Since this is an undirected graph, an edge is also inserted
    //between to and from. Thus the number of edges in the graph
    //is greater by 2 after insert edge has run.
    bool insert_edge(const Type& from, const Type& to) 
    {
        bool a = base_type::insert_edge(from, to);
        bool b = base_type::insert_edge(to, from);
        if(a != b) {
            throw invariant_exception(
                "Undirected graph invariant broken - directed edge found");
        }
        return a; 
    }

    //Removes the edge (from, to). Because this is an undirected graph,
    //also removes the edge (to, from).
    bool remove_edge(const Type& from, const Type& to) 
    {
        bool a = base_type::remove_edge(from, to);
        bool b = base_type::remove_edge(to, from);
        if(a != b) {
            throw invariant_exception(
                "Undirected graph invariant broken - directed edge found");
        }
        return a;
    }

    //Calculates the indegree of a given node. Since our
    //graph is undirected, every edge adds to both indegree
    //and outdegree, thus indegree(node) == outdegree(node)
    size_type indegree(const Type& node) const
    {
        return base_type::outdegree(node);
    }

    //Removes a given node and any edges associated with it.
    //Returns: the number of edges removed
    size_type remove_node(const Type& node)
    {
        auto node_it = base_type::backing_map.find(node);
        size_type edges_removed = 0;

        //Not in our node set, do nothing.
        if(node_it == base_type::backing_map.end()) {

        }
        //0 indegree, and since it is an undirected_graph, 0 outdegree.
        //Thus it can be directly removed from the map, and we know it
        //will have no edges to remove.
        else if(indegree(node) == 0) {
            edges_removed = node_it->second.size();
            base_type::backing_map.erase(node_it);
            --base_type::num_nodes;
        }
        //General case. Walk through the edge set, removing each
        //edge as we go.
        else {
            mapped_type& edge_set = node_it->second;
            for(auto it = edge_set.begin(); it != edge_set.end(); ++it) {
                remove_edge(node_it->first, *it);
            }
        }

        return edges_removed;
    }

}; //end class undirected_graph

template <typename T, typename Compare, typename Allocator>
struct is_directed<undirected_graph<T, Compare, Allocator>>
  : std::false_type
{ };

template <typename T, typename Compare, typename Allocator>
struct is_weighted<undirected_graph<T, Compare, Allocator>>
  : std::false_type
{ };

} //end namespace graph
} //end namespace simplegl

#endif //UNDIRECTED_GRAPH_SGL_HPP_

directed_graph.hpp

#ifndef DIRECTED_GRAPH_SGL_HPP_ 
#define DIRECTED_GRAPH_SGL_HPP_

#include <cassert>
#include <iterator>
#include <map>
#include <memory>
#include <type_traits>

#include "graph/graph_traits.hpp"
#include "graph/structure/detail/graph_base.hpp"

namespace simplegl
{
namespace graph
{
//Class defining a directed, unweighted graph
template <typename Type, 
          typename Compare = std::less<Type>, 
          typename Allocator = std::allocator<Type>>
class directed_graph
    : public detail::graph_base<Type, Compare, Allocator>
{
private:

    using base_type = detail::graph_base<Type, Compare, Allocator>;

public:

    using allocator = Allocator;

    using key_type        = typename base_type::key_type; 
    using mapped_type     = typename base_type::mapped_type;
    using value_type      = typename base_type::value_type;
    using key_compare     = typename base_type::key_compare;
    using value_compare   = typename base_type::value_compare;
    using reference       = typename base_type::reference;
    using const_reference = typename base_type::const_reference;
    using pointer         = typename base_type::pointer;
    using const_pointer   = typename base_type::const_pointer;

    using const_iterator           = typename base_type::const_iterator;
    using const_reverse_iterator   = typename base_type::const_reverse_iterator;
    using const_adjacency_iterator = typename base_type::mapped_const_iterator;
    using size_type                = typename base_type::size_type;
    using difference_type          = typename base_type::difference_type;

    using node_type = key_type;

private:

    std::map<Type, size_type> indegree_cache;

public:

    directed_graph()
        : base_type()
    { }


    template <typename InputIterator>
    directed_graph(InputIterator first, InputIterator last)
    {
        for(InputIterator it = first; it != last; ++it) {
            insert_node(*it);
        }
    }

    //Inserts a completely disconnected node into the graph.
    //Thus, the node is added to the keys only. It will only
    //be added to backing_map only when an edge is added between
    //it and another node. Also creates a value in indegree cache for this node.
    bool insert_node(const Type& node)
    {
        bool inserted = base_type::insert_node(node);
        if(inserted) { 
            indegree_cache[node]; 
        }
        return inserted;
    }

    //Inserts an edge between from and to, ie, E = E + (from, to).
    bool insert_edge(const Type& from, const Type& to)
    {
        bool inserted = base_type::insert_edge(from, to);
        if(inserted) {
            ++indegree_cache[to];
        }
        return inserted;
    }

    //Removes the edge (from, to)
    bool remove_edge(const Type& from, const Type& to)
    {
        bool removed = base_type::remove_edge(from, to);
        if(removed) {
            auto old = indegree_cache[to];
            --indegree_cache[to];
            // Make sure nothing overflows
            assert(assert(old - 1) < old);
        }
        return removed;
    }

    size_type indegree(const Type& node) const
    {
        auto it = indegree_cache.find(node);
        if(it == indegree_cache.end()) {
            return 0;
        }
        return it->second;
    }

    //Removes a given node and any edges associated with it.
    //Unfortunately for a directed_graph, this is a relatively
    //expensive operation, depending on indegree. In the best
    //case, it has 0 indegree, hence we can simply remove the
    //node and all the out edges from it, which is an O(log V)
    //operation. However, in the general case, we don't have a list
    //of which nodes have in edges to the given node, 
    //hence it becomes an O(V log E) operation.
    //
    //Returns: the number of edges removed
    size_type remove_node(const Type& node)
    {
        auto node_it = base_type::backing_map.find(node);
        size_type edges_removed = 0;

        //Not in our node set, do nothing.
        if(node_it == base_type::backing_map.end()) {

        }
        //0 indegree, hence directly remove it from the map, subtracting
        //the edges removed from num_edges and the node removed
        //from num_node. This is a bit of a leaky abstraction
        //unfortunately.
        else if(!indegree(node)) {
            edges_removed = node_it->second.size();
            base_type::backing_map.erase(node_it);
            --base_type::num_nodes;
            base_type::num_edges -= edges_removed;
        }
        //General case, must search every node in the map to see if
        //the node we want to remove is in its edge set. 
        else {
            for(auto it = base_type::backing_map.begin(); 
                     it != base_type::backing_map.end();
                     ++it) {

                if(it == node_it) {
                    continue;
                }

                edges_removed += it->second.erase(node_it->first);
            }

            edges_removed += node_it->second.size();
            base_type::backing_map.erase(node_it);
            --base_type::num_nodes;
            base_type::num_edges -= edges_removed;
        }

        return edges_removed;
    }

}; //end class directed_graph

// Trait specializations
template <typename T, typename Compare, typename Allocator>
struct is_directed<directed_graph<T, Compare, Allocator>>
  : std::true_type
{ };

template <typename T, typename Compare, typename Allocator>
struct is_weighted<directed_graph<T, Compare, Allocator>>
  : std::false_type
{ };

} //end namespace graph
} //end namespace simplegl

#endif //DIRECTED_GRAPH_SGL_HPP_

And that's just about my character limit. In another post I'll throw up some of the generic algorithm code for review as well.

\$\endgroup\$
  • \$\begingroup\$ What is the intended use of this library? Is performance (for scientific computing, say) a major concern? Hash maps kill cache-locality, although since your graph classes are mutable, they'd be hard to replace by arrays. \$\endgroup\$ – Alex Reinking Jun 27 '14 at 4:01
  • \$\begingroup\$ @AlexReinking It isn't meant to be a super high performance library. The intended use is as a (relatively) simple to use, "get up and running" graph library. Sure, maps kill cache locality, but creating functional-style immutable graph structures in C++ is a fairly tall order. \$\endgroup\$ – Yuushi Jun 27 '14 at 4:04
  • \$\begingroup\$ Well, if that's the case, then I don't have much to criticize. Also, creating functional graph structures in a functional language is a pretty tall order! ;) Look up "Tying the Knot" sometime... \$\endgroup\$ – Alex Reinking Jun 27 '14 at 4:09
  • \$\begingroup\$ It would be nice to have a look at the refactored code. If you released this library, could you put a link to the repo? Thanks. \$\endgroup\$ – Agostino Apr 2 '15 at 23:15
  • \$\begingroup\$ @Agostino I've got a repo at bitbucket.org/yuushi/sgl. The graph code sits under graph (there's a few other bits and pieces sitting around in the repo as well). I actually haven't touched it for a little while as I've been busy at work, but you're welcome to have a look regardless. \$\endgroup\$ – Yuushi Apr 3 '15 at 4:18
6
\$\begingroup\$

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<const key_type, mapped_type>;
  • using reference = typename allocator::reference;

Since you often pass std::allocator<Type> 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<key_type, mapped_type, key_compare, allocator>;

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

using base_container = std::map<key_type, mapped_type, key_compare, std::allocator<std::pair<const key_type, mapped_type>>>;

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 Type,
          typename Mapped = std::set<Type>,
          typename Container = std::map<Type, Mapped>>
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.

\$\endgroup\$
  • \$\begingroup\$ All good points. I'm not so fussed about base_container naming as that doesn't get "hoisted out" of graph_base (which is internal and not supposed to be used directly anyway). I do actually use key_compare in some of the algorithms. The allocator type was definitely a big oversight, thanks for pointing that out. \$\endgroup\$ – Yuushi Jun 30 '14 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.