Modify

Opened 7 years ago

Closed 5 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: asutton
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@…

comment:1 Changed 7 years ago by jewillco

  • Resolution set to fixed
  • Status changed from new to closed

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

comment:2 Changed 5 years ago by endecotp

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 5 years ago by anonymous

  • Resolution fixed deleted
  • Status changed from closed to reopened

comment:4 Changed 5 years ago by jewillco

  • Resolution set to fixed
  • Status changed from reopened to closed

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

comment:5 Changed 5 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 5 years ago by jewillco

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

comment:7 Changed 5 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 5 years ago by jewillco

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 5 years ago by anonymous

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

comment:10 follow-up: Changed 5 years ago by jewillco

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

comment:11 Changed 5 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 5 years ago by jewillco

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 jewillco

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

Add Comment

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain asutton.
The resolution will be deleted. Next status will be 'reopened'.
Author


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

 
Note: See TracTickets for help on using tickets.