Boost C++ Libraries: Ticket #11723: Memory leak (and assertion failed) in r_c_shortest_paths.hpp https://svn.boost.org/trac10/ticket/11723 <p> In the following 2-years old thread, a memory leak was experienced when using r_c_shortest_paths of the boost graph library. Jeremiah Willcock added a bunch of assertions to the code, to help identify the problem. </p> <p> <a class="ext-link" href="https://groups.google.com/forum/#!topic/boost-list/W1muJiw85pA"><span class="icon">​</span>https://groups.google.com/forum/#!topic/boost-list/W1muJiw85pA</a> </p> <p> I think I now have a reproducible version of this, which I believe might be a bug. Here is the gist: </p> <p> <a class="ext-link" href="https://gist.github.com/alberto-santini/32c19530dcefb784d0f2"><span class="icon">​</span>https://gist.github.com/alberto-santini/32c19530dcefb784d0f2</a> </p> <p> It contains: </p> <blockquote> <p> 1) graph.txt which contains a dump of the graph that exposes the problem 2) boost_bug.cpp which is the code used to build the graph from file and do the labelling 3) terminal_output.txt which contains the command used to compile and what happens when running the code </p> </blockquote> <p> It has been tested on Mac OS X 10.11 with GCC 5.2 and Boost 1.58. The programme doesn't necessary trigger the assertion at each run. There are runs in which it completes successfully, runs in which it segfaults without triggering any assertion and times in which it's aborted by the failed assertion. </p> <p> The failed assertion is: </p> <p> Assertion failed: (p_cur_label-&gt;b_is_valid), function r_c_shortest_paths_dispatch, file /usr/local/include/boost/graph/r_c_shortest_paths.hpp, line 472. </p> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/11723 Trac 1.4.3 a.santini@… Tue, 13 Oct 2015 15:19:49 GMT attachment set https://svn.boost.org/trac10/ticket/11723 https://svn.boost.org/trac10/ticket/11723 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">boost_bug.cpp</span> </li> </ul> <p> boost_bug.cpp </p> Ticket a.santini@… Tue, 13 Oct 2015 15:20:09 GMT attachment set https://svn.boost.org/trac10/ticket/11723 https://svn.boost.org/trac10/ticket/11723 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">graph.txt</span> </li> </ul> <p> graph.txt </p> Ticket a.santini@… Tue, 20 Oct 2015 09:34:36 GMT <link>https://svn.boost.org/trac10/ticket/11723#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/11723#comment:1</guid> <description> <p> I am not sure this can help, but I added some debugging output. Here are my findings. The assertion fails when reconstructing pareto-optimal paths by walking back through pareto-optimal labels. Output: </p> <pre class="wiki">Walking back a pareto-optimal path: 4163 3567 Assertion failed: (p_cur_label-&gt;b_is_valid) </pre><p> Ok, so what is the parent of this label 3567, that causes the assertion to fail? </p> <pre class="wiki">New label 3567 is feasible and extends 3454 </pre><p> Ah-ah! And why is this label 3454 not valid? </p> <pre class="wiki">Deleting dominated label: 3454 (dominated by 17903) </pre><p> So, apparently a dominated label made it into a pareto-optimal path?! </p> </description> <category>Ticket</category> </item> <item> <author>a.santini@…</author> <pubDate>Thu, 19 Nov 2015 13:22:06 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/11723#comment:2 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/11723#comment:2</guid> <description> <p> More insights (in case anyone will ever take care of this). I think the problem is the following: when a label L residing at a vertex V is dominated by a new label L', all unprocessed labels which have L as predecessor will now point to a deallocated L. I believe they should, instead, be rebased so to have L' as their predecessor. </p> <p> It's not clear to me if such a situation (a label that has been extended is now dominated) is pathological or not. </p> <p> See the modified r_c_shortest_paths.hpp <a class="ext-link" href="https://gist.github.com/alberto-santini/13b497601967ee72bd1d"><span class="icon">​</span>here</a> (grep for the parts nearby "\tWARNING"). This files prints to std::cerr some debug info. </p> </description> <category>Ticket</category> </item> <item> <dc:creator>anonymous</dc:creator> <pubDate>Fri, 20 Nov 2015 07:55:14 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/11723#comment:3 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/11723#comment:3</guid> <description> <p> To reply to my previous comment: it's not by itself pathological that label L is dominated; the problem is that all extensions of L' should dominate all extensions of L... therefore no extension of L should make it into the final pareto-optimal set of paths. </p> <p> I will now try to understand whether this situation is due to a bad dominance criterion on my side (am I not honouring some requirement/precondition of the dominance operator? I have to say the related documentation *could* be better) or not. </p> </description> <category>Ticket</category> </item> <item> <author>mateusz.polnik@…</author> <pubDate>Sun, 29 Jul 2018 16:56:30 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/11723#comment:4 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/11723#comment:4</guid> <description> <p> Hi Jeremiah, </p> <p> I created a pull request to the <a class="ext-link" href="https://github.com/boostorg/graph"><span class="icon">​</span>GitHub</a> repository that fixes a memory leak in the algorithm for shortest paths with resource constraints. </p> <p> Could you advise me what if there is anything I could do to have the pull request approved and merged in? </p> <p> <a class="ext-link" href="https://github.com/boostorg/graph/pull/93"><span class="icon">​</span>Link</a>to the pull request. </p> </description> <category>Ticket</category> </item> </channel> </rss>