[Graph] Labeled graph bug

Hello, 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: m_g.add_vertex(nodeId, Item(nodeId)); Everything is fine, but there is a bug with find_labeled_vertex. I want to check if a label is in my graph: *auto BUnGraph::exists( nid source ) const -> bool* *{* * if( m_g.vertex(source) == UnGraph::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(). I have isolated the method. 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(); }* I have 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. *So any label number inferior to map.size() will give false results ...* What's going on ? Thank you.

I have 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.
So any label number inferior to map.size() will give false results ...
What's going on ?
It looks like a broken assumption in the design of labeled_graph (which is mostly experimental), that any use of integral labels would be in the range [0, num_vertices(g)). When you insert a new label, it is automatically resizing the container to accommodate your new label. You may be better off not using labeled_graph. Andrew

I figure it out when I tried to put a label= 600000000, my computer ran out of memory. I changed from uint64_t to int64_t. Now it is properly working. Cheers, /** * 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;}; On Fri, Dec 7, 2012 at 3:52 PM, Andrew Sutton <asutton.list@gmail.com>wrote:
I have 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.
So any label number inferior to map.size() will give false results ...
What's going on ?
It looks like a broken assumption in the design of labeled_graph (which is mostly experimental), that any use of integral labels would be in the range [0, num_vertices(g)). When you insert a new label, it is automatically resizing the container to accommodate your new label.
You may be better off not using labeled_graph.
Andrew _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (2)
-
Andrew Sutton
-
Kikohs xxx