Generic Graph Library

Question

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.

• Alex Reinking: 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.
• Yuushi: @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.
• Alex Reinking: 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...
• Agostino: 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.
• Yuushi: @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.

Answer 1

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.

• Yuushi: 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.