Modify

Ticket #4622 (closed Bugs: fixed)

Opened 4 years ago

Last modified 10 months ago

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

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

Change History

Changed 4 years ago by dtrebbien@…

comment:1 Changed 4 years ago by jewillco

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

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

comment:2 Changed 2 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 2 years ago by anonymous

  • Status changed from closed to reopened
  • Resolution fixed deleted

comment:4 Changed 2 years ago by jewillco

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

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

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

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

comment:7 Changed 2 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 2 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 2 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: ↓ 13 Changed 2 years ago by jewillco

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

comment:11 Changed 2 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 2 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 10 months 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 10 months ago by jewillco

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

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
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.