[Boost-bugs] [Boost C++ Libraries] #13198: breadth_first_visit crashes on graphs when VertexLists is vecS

Subject: [Boost-bugs] [Boost C++ Libraries] #13198: breadth_first_visit crashes on graphs when VertexLists is vecS
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2017-09-07 17:04:06

#13198: breadth_first_visit crashes on graphs when VertexLists is vecS
------------------------------+-------------------------------
 Reporter:  hong@…            |      Owner:  Jeremiah Willcock
     Type:  Bugs              |     Status:  new
Milestone:  To Be Determined  |  Component:  graph
  Version:  Boost 1.63.0      |   Severity:  Problem
 Keywords:                    |
------------------------------+-------------------------------
 breadth_first_search crashes if VertexLists is vecS. A minimal example is
 as follows:

 {{{
 #!div style="font-size: 80%"
 Code highlighting:
   {{{#!cpp
 #include <iostream>
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/breadth_first_search.hpp>

 typedef boost::adjacency_list<boost::vecS, boost::vecS,
 boost::undirectedS,
                               boost::property<boost::vertex_color_t,
 boost::default_color_type>> GraphType;

 int main()
 {
     using namespace boost;

     GraphType g;

     auto a = add_vertex(g);
     auto b = add_vertex(g);
     auto c = add_vertex(g);
     add_edge(a, b, g);
     add_edge(b, c, g);
     add_edge(c, a, g);

     typedef boost::property_map<GraphType, boost::vertex_color_t>::type
 color_map_t;
     color_map_t colorMap; //Create a color map
     boost::breadth_first_visit(g, *boost::vertices(g).first,
 boost::color_map(colorMap));

     GraphType::vertex_iterator it, itEnd;
     for (boost::tie(it, itEnd) = boost::vertices(g); it != itEnd; it++)
     {
         std::cout << "Color of node " << *it << " is " << colorMap[*it] <<
 std::endl;
     }
 }
   }}}

 The backtrace:

 {{{
 #0  0x0000555555556d70 in
 std::vector<boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS,
 boost::vecS, boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>, boost::vecS, boost::vecS,
 boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>::config::stored_vertex,
 std::allocator<boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS,
 boost::vecS, boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>, boost::vecS, boost::vecS,
 boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>::config::stored_vertex> >::operator[]
 (this=0x18, __n=0) at /usr/include/c++/6/bits/stl_vector.h:781
 #1  0x0000555555556674 in
 boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS,
 boost::vecS, boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS,
 boost::vecS, boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>*, boost::default_color_type,
 boost::default_color_type&, boost::vertex_color_t>::operator[]
 (this=0x7fffffffcb60, v=0) at
 /usr/include/boost/graph/detail/adjacency_list.hpp:2510
 #2  0x0000555555558451 in
 boost::put<boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS,
 boost::vecS, boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS,
 boost::vecS, boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>*, boost::default_color_type,
 boost::default_color_type&, boost::vertex_color_t>,
 boost::default_color_type&, unsigned long, boost::default_color_type>
 (pa=..., k=0,
     v=@0x7fffffffcbcc: boost::gray_color) at
 /usr/include/boost/property_map/property_map.hpp:309
 #3  0x00005555555577b6 in
 boost::breadth_first_visit<boost::adjacency_list<boost::vecS, boost::vecS,
 boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>, boost::queue<unsigned long,
 std::deque<unsigned long, std::allocator<unsigned long> > >,
 boost::bfs_visitor<boost::null_visitor>,
 boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS,
 boost::vecS, boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS,
 boost::vecS, boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>*, boost::default_color_type,
 boost::default_color_type&, boost::vertex_color_t>, unsigned long*> (
     g=..., sources_begin=0x7fffffffcd28, sources_end=0x7fffffffcd30,
 Q=..., vis=..., color=...)
     at /usr/include/boost/graph/breadth_first_search.hpp:75
 #4  0x0000555555556c6b in
 boost::breadth_first_visit<boost::adjacency_list<boost::vecS, boost::vecS,
 boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>, boost::queue<unsigned long,
 std::deque<unsigned long, std::allocator<unsigned long> > >,
 boost::bfs_visitor<boost::null_visitor>,
 boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS,
 boost::vecS, boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS,
 boost::vecS, boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>*, boost::default_color_type,
 boost::default_color_type&, boost::vertex_color_t> > (g=..., s=0,
     Q=..., vis=..., color=...) at
 /usr/include/boost/graph/breadth_first_search.hpp:104
 #5  0x00005555555564a0 in
 boost::breadth_first_visit<boost::adjacency_list<boost::vecS, boost::vecS,
 boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>,
 boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS,
 boost::vecS, boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS,
 boost::vecS, boost::undirectedS, boost::property<boost::vertex_color_t,
 boost::default_color_type, boost::no_property>, boost::no_property,
 boost::no_property, boost::listS>*, boost::default_color_type,
 boost::default_color_type&, boost::vertex_color_t>, boost::vertex_color_t,
 boost::no_property> (g=..., s=0, params=...) at
 /usr/include/boost/graph/breadth_first_search.hpp:370
 #6  0x0000555555555cce in main () at test.cpp:24
 }}}

 Changing `vecS` to `listS` resolves the issue, but I don't think anywhere
 in the doc mentions that `vecS` cannot be used.

-- 
Ticket URL: <https://svn.boost.org/trac10/boost/ticket/13198>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.