#4622 closed Bugs (fixed)
clear_vertex on a vertex with a self-loop can cause a segmentation fault
| Reported by: | 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)
Change History (15)
by , 12 years ago
| Attachment: | clear_vertex_min_test.cpp added |
|---|
comment:1 by , 12 years ago
| Resolution: | → fixed |
|---|---|
| Status: | new → closed |
comment:2 by , 10 years ago
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 by , 10 years ago
| Resolution: | fixed |
|---|---|
| Status: | closed → reopened |
comment:4 by , 10 years ago
| Resolution: | → fixed |
|---|---|
| Status: | reopened → closed |
comment:5 by , 10 years ago
Have you tested that?
It looks to me as if it will now try to erase the same element from m_edges twice.
comment:7 by , 10 years ago
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 by , 10 years ago
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 by , 10 years ago
I thought that each self-loop appeared twice in the out-edge list, for an undirected graph.
follow-up: 13 comment:10 by , 10 years ago
comment:11 by , 10 years ago
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 by , 10 years ago
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").
(In [65198]) Fixed clearing of vertices with self-loop edges; fixes #4622