Boost C++ Libraries: Ticket #10231: [graph] finish_edge seems never to get called in depth_first_search

attachment set

Wed, 23 Jul 2014 11:19:22 GMT

attachment → finish_edge_bug.cpp

MWE showing that finish_edge never gets called.

Fri, 25 Jul 2014 13:03:32 GMT

Hard-wiring the call to finish_edge actually shows that the logic behind it in depth_first_visit is buggy. In the MWE above, the edge (1,2) gets finished two times, for example.

edwin.carlinet@… — Fri, 15 Aug 2014 09:49:26 GMT

Look like a duplicate of #9770 (ticket). Does the patch given in ticket:9770#comment:1 solve your problem?

Sat, 16 Aug 2014 09:11:31 GMT

Replying to edwin.carlinet@…:

Look like a duplicate of #9770 (ticket). Does the patch given in ticket:9770#comment:1 solve your problem?

It might (partly), but I didn't try (see below for the reason).

First, the main point of this bug is that the code making finish_edge optional to the visitor seems to be broken, at least in my quite old environment (Ubuntu 12.10 and gcc 4.7.2). As far as I can see, the implementation using BOOST_TTI_HAS_MEMBER_FUNCTION(finish_tree_edge) does not work. Testing it in an minimal example showed that it claims there is no finish_tree_edge member function even though there is. So the problem probably actually does not lie in the Graph library itself, but in the TTI library it uses. I had a look into that, but it is quite convoluted macro-code and I gave up on fixing that properly. Should I file a new bug to get the attention of the TTI developers?

Second, I didn't try the patch, because I think the problem lies elsewhere: The call of finish_tree_edge is dislocated. It should be right after the pop of the edge (think of the 'pop' of the edge as 'returning' (in the original recursive implementation) back over the edge). This is solved in this pull request: https://github.com/boostorg/graph/pull/16

Fri, 22 Aug 2014 12:23:44 GMT

I just noticed I should have mentioned: I'm using Ubuntu 12.10 with gcc 4.7.2.

Mon, 25 Aug 2014 08:34:39 GMT

"finish_edge" is meant wherever "finish_tree_edge" is said, of course.

Replying to Alex <alxlaus@…>:

Replying to edwin.carlinet@…:

Look like a duplicate of #9770 (ticket). Does the patch given in ticket:9770#comment:1 solve your problem?

It might (partly), but I didn't try (see below for the reason).

First, the main point of this bug is that the code making finish_edge optional to the visitor seems to be broken, at least in my quite old environment (Ubuntu 12.10 and gcc 4.7.2). As far as I can see, the implementation using BOOST_TTI_HAS_MEMBER_FUNCTION(finish_tree_edge) does not work. Testing it in an minimal example showed that it claims there is no finish_tree_edge member function even though there is. So the problem probably actually does not lie in the Graph library itself, but in the TTI library it uses. I had a look into that, but it is quite convoluted macro-code and I gave up on fixing that properly. Should I file a new bug to get the attention of the TTI developers?

Second, I didn't try the patch, because I think the problem lies elsewhere: The call of finish_tree_edge is dislocated. It should be right after the pop of the edge (think of the 'pop' of the edge as 'returning' (in the original recursive implementation) back over the edge). This is solved in this pull request: https://github.com/boostorg/graph/pull/16

anonymous — Sun, 09 Nov 2014 00:08:53 GMT

I just pushed a fix to develop for this. Can you please check that finish_edge is now getting called correctly?

alxlaus@… — Tue, 11 Nov 2014 10:53:15 GMT

Replying to anonymous:

I just pushed a fix to develop for this. Can you please check that finish_edge is now getting called correctly?

It doesn't. I hard-coded the finish_edge-call to work around that it never gets called at all. Then it outputs the following, which is clearly wrong as the edge (1,2) gets finished twice.

The example graph:
0 --> 1 2
1 --> 2
2 --> 0
finish_edge: (2,0)
finish_edge: (1,2)
finish_edge: (1,2)
finish_edge: (0,2)
finish_edge: (0,1)

Noel Belcourt — Tue, 11 Nov 2014 19:42:40 GMT

I just pushed this test case (slightly modified) to develop. Once we fix where the finish_edge event point is called, we'll update this test to check for correctness, right now we know the output is incorrect.

status changed; resolution set

Noel Belcourt — Sun, 01 May 2016 20:14:16 GMT

status new → closed
resolution → fixed

I just pushed your github PR, the output is now correct:

kbelco$ ./finish_edge_bug

The example graph: 0 --> 1 2 1 --> 2 2 --> 0 finish_edge: (2,0) finish_edge: (1,2) finish_edge: (0,1) finish_edge: (0,2)

We'll have to monitor tests and fix older compilers that can't handle this code. Thanks for the bug report.