Boost C++ Libraries: Ticket #13198: breadth_first_visit crashes on graphs where VertexLists is vecS

Boost C++ Libraries: Ticket #13198: breadth_first_visit crashes on graphs where VertexLists is vecS https://svn.boost.org/trac10/ticket/13198 <p> breadth_first_search crashes if <a class="missing wiki">VertexLists</a> is vecS. A minimal example is as follows: </p> <div class="wikipage" style="font-size: 80%"><p> Code highlighting: </p> <div class="wiki-code"><div class="code"><pre><span class="cp">#include</span> <span class="cpf"><iostream></span><span class="cp"></span> <span class="cp">#include</span> <span class="cpf"><boost/graph/adjacency_list.hpp></span><span class="cp"></span> <span class="cp">#include</span> <span class="cpf"><boost/graph/breadth_first_search.hpp></span><span class="cp"></span> <span class="k">typedef</span> <span class="n">boost</span><span class="o">::</span><span class="n">adjacency_list</span><span class="o"><</span><span class="n">boost</span><span class="o">::</span><span class="n">vecS</span><span class="p">,</span> <span class="n">boost</span><span class="o">::</span><span class="n">vecS</span><span class="p">,</span> <span class="n">boost</span><span class="o">::</span><span class="n">undirectedS</span><span class="p">,</span> <span class="n">boost</span><span class="o">::</span><span class="n">property</span><span class="o"><</span><span class="n">boost</span><span class="o">::</span><span class="n">vertex_color_t</span><span class="p">,</span> <span class="n">boost</span><span class="o">::</span><span class="n">default_color_type</span><span class="o">>></span> <span class="n">GraphType</span><span class="p">;</span> <span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span> <span class="k">using</span> <span class="k">namespace</span> <span class="n">boost</span><span class="p">;</span> <span class="n">GraphType</span> <span class="n">g</span><span class="p">;</span> <span class="k">auto</span> <span class="n">a</span> <span class="o">=</span> <span class="n">add_vertex</span><span class="p">(</span><span class="n">g</span><span class="p">);</span> <span class="k">auto</span> <span class="n">b</span> <span class="o">=</span> <span class="n">add_vertex</span><span class="p">(</span><span class="n">g</span><span class="p">);</span> <span class="k">auto</span> <span class="n">c</span> <span class="o">=</span> <span class="n">add_vertex</span><span class="p">(</span><span class="n">g</span><span class="p">);</span> <span class="n">add_edge</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">g</span><span class="p">);</span> <span class="n">add_edge</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">,</span> <span class="n">g</span><span class="p">);</span> <span class="n">add_edge</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">g</span><span class="p">);</span> <span class="k">typedef</span> <span class="n">boost</span><span class="o">::</span><span class="n">property_map</span><span class="o"><</span><span class="n">GraphType</span><span class="p">,</span> <span class="n">boost</span><span class="o">::</span><span class="n">vertex_color_t</span><span class="o">>::</span><span class="n">type</span> <span class="n">color_map_t</span><span class="p">;</span> <span class="n">color_map_t</span> <span class="n">colorMap</span><span class="p">;</span> <span class="c1">//Create a color map</span> <span class="n">boost</span><span class="o">::</span><span class="n">breadth_first_visit</span><span class="p">(</span><span class="n">g</span><span class="p">,</span> <span class="o">*</span><span class="n">boost</span><span class="o">::</span><span class="n">vertices</span><span class="p">(</span><span class="n">g</span><span class="p">).</span><span class="n">first</span><span class="p">,</span> <span class="n">boost</span><span class="o">::</span><span class="n">color_map</span><span class="p">(</span><span class="n">colorMap</span><span class="p">));</span> <span class="n">GraphType</span><span class="o">::</span><span class="n">vertex_iterator</span> <span class="n">it</span><span class="p">,</span> <span class="n">itEnd</span><span class="p">;</span> <span class="k">for</span> <span class="p">(</span><span class="n">boost</span><span class="o">::</span><span class="n">tie</span><span class="p">(</span><span class="n">it</span><span class="p">,</span> <span class="n">itEnd</span><span class="p">)</span> <span class="o">=</span> <span class="n">boost</span><span class="o">::</span><span class="n">vertices</span><span class="p">(</span><span class="n">g</span><span class="p">);</span> <span class="n">it</span> <span class="o">!=</span> <span class="n">itEnd</span><span class="p">;</span> <span class="n">it</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="n">std</span><span class="o">::</span><span class="n">cout</span> <span class="o"><<</span> <span class="s">"Color of node "</span> <span class="o"><<</span> <span class="o">*</span><span class="n">it</span> <span class="o"><<</span> <span class="s">" is "</span> <span class="o"><<</span> <span class="n">colorMap</span><span class="p">[</span><span class="o">*</span><span class="n">it</span><span class="p">]</span> <span class="o"><<</span> <span class="n">std</span><span class="o">::</span><span class="n">endl</span><span class="p">;</span> <span class="p">}</span> <span class="p">}</span> </pre></div></div><p> The backtrace: </p> <pre class="wiki">#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 </pre><p> Changing <code>vecS</code> to <code>listS</code> resolves the issue, but I don't think anywhere in the doc mentions that <code>vecS</code> cannot be used. </p> </div> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/13198 Trac 1.4.3 anonymous Thu, 07 Sep 2017 17:04:29 GMT summary changed https://svn.boost.org/trac10/ticket/13198#comment:1 https://svn.boost.org/trac10/ticket/13198#comment:1 <ul> <li><strong>summary</strong> <span class="trac-field-old">breadth_first_visit crashes on graphs when VertexLists is vecS</span> → <span class="trac-field-new">breadth_first_visit crashes on graphs where VertexLists is vecS</span> </li> </ul> Ticket