Modify

Opened 7 years ago

Closed 6 years ago

Last modified 4 years ago

#4622 closed Bugs (fixed)

clear_vertex on a vertex with a self-loop can cause a segmentation fault

Reported by: dtrebbien@… Owned by: Andrew Sutton
Milestone: To Be Determined Component: graph
Version: Boost Development Trunk Severity: Problem
Keywords: Cc: dtrebbien@…

Description

Attached is a minimal test case that raises a segmentation fault. When line 23, add_edge(5, 5, g);, is commented out, then the fault no longer occurs.

I am currently at trunk revision 65192.

Attachments (1)

clear_vertex_min_test.cpp (872 bytes) - added by dtrebbien@… 7 years ago.

Download all attachments as: .zip

Change History (15)

Changed 7 years ago by dtrebbien@…

Attachment: clear_vertex_min_test.cpp added

comment:1 Changed 7 years ago by Jeremiah Willcock

Resolution: fixed
Status: newclosed

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

comment:2 Changed 6 years ago by Phil Endecott

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...

comment:3 Changed 6 years ago by anonymous

Resolution: fixed
Status: closedreopened

comment:4 Changed 6 years ago by Jeremiah Willcock

Resolution: fixed
Status: reopenedclosed

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

comment:5 Changed 6 years ago by anonymous

Have you tested that?

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

comment:6 Changed 6 years ago by Jeremiah Willcock

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

comment:7 Changed 6 years ago by anonymous

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.

comment:8 Changed 6 years ago by Jeremiah Willcock

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).

comment:9 Changed 6 years ago by anonymous

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

comment:10 Changed 6 years ago by Jeremiah Willcock

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

comment:11 Changed 6 years ago by anonymous

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?

comment:12 Changed 6 years ago by Jeremiah Willcock

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").

comment:13 in reply to:  10 Changed 4 years ago by i@…

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.

comment:14 Changed 4 years ago by Jeremiah Willcock

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

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain Andrew Sutton.
The resolution will be deleted.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.