Boost C++ Libraries: Ticket #4622: clear_vertex on a vertex with a self-loop can cause a segmentation fault

attachment set

dtrebbien@… — Thu, 02 Sep 2010 15:25:05 GMT

attachment → clear_vertex_min_test.cpp

status changed; resolution set

Jeremiah Willcock — Thu, 02 Sep 2010 18:24:21 GMT

status new → closed
resolution → fixed

(In [65198]) Fixed clearing of vertices with self-loop edges; fixes #4622

Phil Endecott — Thu, 10 May 2012 22:20:16 GMT

The fixed version still seems wrong. Consider a vertex in an undirected graph with only self-loops. The current code will do nothing inside the loop, and then clear the out_edge_list. The problem is that m_edges has not been updated to remove these edges. When I subsequently iterate over all the edges in the graph, I still find these edges (and then crash).

This is the first time that I've ever used Boost.Graph so it's possible that I'm misunderstanding something...

status changed; resolution deleted

anonymous — Fri, 11 May 2012 14:36:13 GMT

status closed → reopened
resolution fixed

status changed; resolution set

Jeremiah Willcock — Fri, 11 May 2012 19:37:57 GMT

status reopened → closed
resolution → fixed

(In [78425]) Fixed handling of self-loops; fixes #4622

anonymous — Fri, 11 May 2012 20:54:32 GMT

Have you tested that?

It looks to me as if it will now try to erase the same element from m_edges twice.

Jeremiah Willcock — Fri, 11 May 2012 21:03:22 GMT

(In [78428]) Trying to fix undirected clear_vertex() again; refs #4622

anonymous — Sat, 12 May 2012 13:48:26 GMT

Please try to convince me that the new code is correct. It's not obvious to me why it would now call m_edges.erase() only once per self-loop edge.

Jeremiah Willcock — Sat, 12 May 2012 18:51:52 GMT

As long as each self-loop appears in the out-edge list exactly once, it will be deleted exactly once since that is what the loop that deletes from m_edges does (and the loop doesn't do anything else anymore).

anonymous — Sat, 12 May 2012 19:27:57 GMT

I thought that each self-loop appeared twice in the out-edge list, for an undirected graph.

Jeremiah Willcock — Sat, 12 May 2012 20:10:16 GMT

(In [78439]) Fixed bugs in remove_edge and clear_vertex for undirected graphs; refs #4622

anonymous — Sat, 12 May 2012 22:14:46 GMT

It would be great to get some sort of explanation either here or in the commit message.

Do you believe that the old remove_edge was also wrong, or was that change needed only because of how you have now implemented clear_vertex?

Jeremiah Willcock — Sat, 12 May 2012 22:40:32 GMT

The old remove_edge was wrong in general; compiling libs/graph/test/graph.cpp with -D_GLIBCXX_DEBUG and adding in some self-loops led to dereferencing of singular iterators before clear_vertex was called at all. The patch to clear_vertex is a rewrite changing it to a brute-force version ("while any adjacent edges exist, remove the first one").

i@… — Fri, 21 Jun 2013 12:10:15 GMT

Replying to jewillco:

(In [78439]) Fixed bugs in remove_edge and clear_vertex for undirected graphs; refs #4622

This introduced a regression for me. What is the added BOOST_ASSERT in remove_edge_and_property good for? Especially considering the condition right after it.

Jeremiah Willcock — Fri, 21 Jun 2013 20:06:47 GMT

(In [84869]) Removed assertion to enable removal of non-existent edges, as suggested by comment to #4622; refs #4622