如何使用 BGL 的 adjacency_list 和标准 unorunordered_set 作为出边列表模板参数

Question

我正在尝试将 boost 的图形库 adjacency_list 与 C++11 unorunordered_set 一起使用。虽然将它用作第二个模板参数（即顶点列表）编译正常，但当尝试将它用作“出边”类型（第一个模板参数）时，我收到以下错误： “"The C++ Standard doesn't provide a hash for this type." 这是有问题的代码：

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

许多 10 倍，安德烈

Answer 1

out-edge 列表确实使用了实现定义的包装器类型。

如果您仔细阅读消息，您会发现您需要 type-erased 迭代器包装器的散列。您需要这些专业（从 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); }
    };
}

注意事项：我只使用内置的 hash_setS 选择器（它使用 boost::unordered_set）。这样你就不会依赖于明确不在 public headers.

中的实现细节

两种口味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;
}

如何使用 BGL 的 adjacency_list 和标准 unorunordered_set 作为出边列表模板参数

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

boost

boost-graph

c++11