How to use BGL’s adjacency_list with standard unorunordered_set as the out edges list template parameter

Question

I’m trying to use boost’s graph library adjacency_list with C++11 unorunordered_set. While using it as the second template argument (i.e. the vertex list) compiles fine, when trying to use it as the “out edges” types (the first template parameter) I get the following error: “"The C++ Standard doesn't provide a hash for this type." Here is the code at question:

#include <unordered_set>
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>

struct NodeProperty{
    std::string FirstName;
    std::string LastName;
};

namespace std{
    template<>
    struct hash<NodeProperty>
    {
        std::hash<std::string> hasher;
        size_t operator()(const NodeProperty& key) const
        {
            return hasher(key.FirstName) ^ hasher(key.LastName);
        }
    };
}
namespace boost {
    struct std_unorunordered_setS{};

    template <class ValueType>
    struct container_gen<std_unorunordered_setS, ValueType> {
        typedef std::unordered_set<ValueType> type;
    };

    template <>
    struct parallel_edge_traits<std_unorunordered_setS> {
        typedef disallow_parallel_edge_tag type;
    };
}

using namespace boost;

int main(int, char*[])
{
    typedef adjacency_list< std_unorunordered_setS, std_unorunordered_setS, bidirectionalS,
        NodeProperty > Graph;

    typedef graph_traits<Graph>::vertex_descriptor Vertex;
}

Many 10x, Andrey

Answer 1

The out-edge list does use a implementation defined wrapper types.

If you read the message well, you can see you need the hash of something of a type-erased iterator wrapper. You need these specializations (stolen from detail/adjacency_list.hpp):

namespace std {

    template <typename V> struct hash<boost::detail::stored_edge<V> > {
        std::size_t operator()(const boost::detail::stored_edge<V> &e) const { return hash<V>()(e.m_target); }
    };

    template <typename V, typename P> struct hash<boost::detail::stored_edge_property<V, P> > {
        std::size_t operator()(const boost::detail::stored_edge_property<V, P> &e) const { return hash<V>()(e.m_target); }
    };

    template <typename V, typename I, typename P> struct hash<boost::detail::stored_edge_iter<V, I, P> > {
        std::size_t operator()(const boost::detail::stored_edge_iter<V, I, P> &e) const { return hash<V>()(e.m_target); }
    };
}

CAVEAT: I'd just use the hash_setS selector that is built in (which uses boost::unordered_set). That way you won't depend on implementation details that are expressly not in the public headers.

Both flavours Live On Coliru

#include <unordered_set>
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>

struct NodeProperty {
    std::string FirstName;
    std::string LastName;
};

namespace std {
    template <> struct hash<NodeProperty> {
        std::hash<std::string> hasher;
        size_t operator()(const NodeProperty &key) const { return hasher(key.FirstName) ^ hasher(key.LastName); }
    };
}

namespace std {
    template <typename V> struct hash<boost::detail::stored_edge<V> > {
        std::size_t operator()(const boost::detail::stored_edge<V> &e) const { return hash<V>()(e.m_target); }
    };

    template <typename V, typename P> struct hash<boost::detail::stored_edge_property<V, P> > {
        std::size_t operator()(const boost::detail::stored_edge_property<V, P> &e) const { return hash<V>()(e.m_target); }
    };

    template <typename V, typename I, typename P> struct hash<boost::detail::stored_edge_iter<V, I, P> > {
        std::size_t operator()(const boost::detail::stored_edge_iter<V, I, P> &e) const { return hash<V>()(e.m_target); }
    };
}

namespace boost {
    struct std_unordered_setS {};

    template <class ValueType> struct container_gen<std_unordered_setS, ValueType> {
        typedef std::unordered_set<ValueType> type;
    };

    template <> struct parallel_edge_traits<std_unordered_setS> { typedef disallow_parallel_edge_tag type; };
}

using namespace boost;

int main() {
#ifdef USE_STD
    typedef adjacency_list<std_unordered_setS, std_unordered_setS, bidirectionalS, NodeProperty> Graph;
#else
    typedef adjacency_list<hash_setS, hash_setS, bidirectionalS, NodeProperty> Graph;
#endif

    // typedef graph_traits<Graph>::vertex_descriptor Vertex;
}