CODEWITHSUNDEEP
c++boostboost-graph
Kirell
Kirell

Reputation: 9798

Boost labeled graph, wrong internal map size

I have created a labeled graph:

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

My labels are uint64_t, I want to have my own ids on the graph.

If I add a node, everything is fine, I only have the nodes with my labels.

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

I want to check if a label is in my graph:

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

But the method:

vertex(source)

gives me false results, and returns me a default constructed vertex_descriptor when a node is not in the graph instead of a null_vertex() depending on the label ...

I have isolated the method in 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(); }

and checked the internal map. If I add a single node in the graph, map.size() == 42. Instead of 1 ! If I add 5 nodes size() == 248.

Depending on the id, the map size is equal to: max label value * 2 + 2 So any label number inferior to map.size() will give false results.

What's going on ?

EDIT: I put a label like 60000000, in my graph, only one node. My computer ran out of memory ...

Upvotes: 2

Views: 539

Answers (1)

Kirell
Kirell

Reputation: 9798

I found the line responsible for this:

/**
 * 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;
};

If the type is unsigned, so uint8_t, 16, 32, 64 it will use a vector. I cannot find a good use case for this behavior. It is very dangerous.

So, the only solution I found is to use from now on int64_t instead of uint64_t.

Upvotes: 3

Related Questions