2

我创建了一个标记图：

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
Item, Link > UnGraph;

我的标签是uint64_t，我想在图表上拥有自己的 ID。

如果我添加一个节点，一切都很好，我只有带有我的标签的节点。

m_g.add_vertex(nodeId, Item(nodeId));

我想检查一个标签是否在我的图表中：

auto BUnGraph::exists( nid source ) const -> bool
{
    if( m_g.vertex(source) == BUnGraph::null_vertex() )
        return false;
    else
        return true;
}

但是方法：

vertex(source)

给我错误的结果，并返回一个默认构造的 vertex_descriptor 当节点不在图中而不是 null_vertex() 取决于标签...

我已经隔离了 boost 中的方法：

labeled_graph.hpp
    /** @name Find Labeled Vertex */
    //@{
    // Tag dispatch for sequential maps (i.e., vectors).
    template <typename Container, typename Graph, typename Label>
    typename graph_traits<Graph>::vertex_descriptor
    find_labeled_vertex(Container const& c, Graph const&, Label const& l,
                        random_access_container_tag)
    { return l < c.size() ? c[l] : graph_traits<Graph>::null_vertex(); }

并检查了内部地图。如果我在图中添加一个节点，map.size() == 42。而不是 1 ！如果我添加 5 个节点 size() == 248。

根据 id，地图大小等于：最大标签值 * 2 + 2 所以任何低于 map.size() 的标签号都会给出错误的结果。

这是怎么回事 ？

编辑：我在我的图表中放了一个像 60000000 这样的标签，只有一个节点。我的电脑内存不足...

4

1 回答 1

3

我找到了负责此的行：

/**
 * Choose the default map instance. If Label is an unsigned integral type
 * the we can use a vector to store the information.
 */
template <typename Label, typename Vertex>
struct choose_default_map {
    typedef typename mpl::if_<
        is_unsigned<Label>,
        std::vector<Vertex>,
        std::map<Label, Vertex> // TODO: Should use unordered_map?
    >::type type;
};

如果类型是无符号的，那么 uint8_t, 16, 32, 64 它将使用向量。我找不到这种行为的好用例。这是非常危险的。

所以，我找到的唯一解决方案是从现在开始使用int64_t而不是 uint64_t。

于 2012-12-07T15:10:46.563 回答