[graph] finish_edge seems never to get called in depth_first_search

[Alex <alxlaus@…>]

The subject says everything.

Attached is a MWE. It implements a dfs-visitor that should output something each time an edge is finished, but it doesn't.

[Alex <alxlaus@…>]

MWE showing that finish_edge never gets called.

[Alex <alxlaus@…>]

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@…]

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

[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

[Alex <alxlaus@…>]

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

[Alex <alxlaus@…>]

"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]

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

[alxlaus@…]

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]

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.

[Noel Belcourt]

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.