Boost C++ Libraries: Ticket #11960: boost::transitive_closure dies on small graph with only 100,000 vertices
https://svn.boost.org/trac10/ticket/11960
<p>
Here's a trivial program that dies with a SIGKILL inside of boost::transitive_closure. I suspect it tries to allocate an absurd amount of memory.
</p>
en-usBoost C++ Libraries/htdocs/site/boost.png
https://svn.boost.org/trac10/ticket/11960
Trac 1.4.3Joshua Pritikin <jpritikin@…>Sat, 06 Feb 2016 03:03:29 GMTattachment set
https://svn.boost.org/trac10/ticket/11960
https://svn.boost.org/trac10/ticket/11960
<ul>
<li><strong>attachment</strong>
→ <span class="trac-field-new">death.cpp</span>
</li>
</ul>
<p>
cpp source code to reproduce bug
</p>
TicketJoshua Pritikin <jpritikin@…>Sat, 06 Feb 2016 03:25:27 GMT
<link>https://svn.boost.org/trac10/ticket/11960#comment:1 </link>
<guid isPermaLink="false">https://svn.boost.org/trac10/ticket/11960#comment:1</guid>
<description>
<p>
I traced it to transitive_closure.hpp:178,
</p>
<pre class="wiki"> std::vector<std::vector<cg_vertex> > successors(CG_vec.size(),
std::vector<cg_vertex>
(chains.size(), inf));
</pre><p>
Both vec.size() and chains.size() are 100,000 and sizeof(inf) is 8 so that's .. 76 terabytes? There must be a more space efficient way to implement this algorithm?
</p>
</description>
<category>Ticket</category>
</item>
<item>
<dc:creator>Steven Watanabe</dc:creator>
<pubDate>Sat, 13 Feb 2016 21:17:56 GMT</pubDate>
<title>component changed; owner set
https://svn.boost.org/trac10/ticket/11960#comment:2
https://svn.boost.org/trac10/ticket/11960#comment:2
<ul>
<li><strong>owner</strong>
set to <span class="trac-author">Jeremiah Willcock</span>
</li>
<li><strong>component</strong>
<span class="trac-field-old">None</span> → <span class="trac-field-new">graph</span>
</li>
</ul>
Ticket