Subject: [boost] [graph] depth_first_visit_impl
From: Michael Marcin (mike.marcin_at_[hidden])
Date: 2015-06-24 00:22:27
I was doing some work with depth_first_search and came across some
issues that seem surprising with the implementation.
First vis.finish_edge doesn't seem to ever get called on msvc.
Second changing the code to call finish_edge directly instead of through
the call_finish_edge machinery seems to result in incorrect edges being
finished.
Third the implementation of depth_first_visit_impl pushes into a
std::vector stack even for vertices with no out_edges. If I have a graph
with a large number of vertices but few or no edges this seems bad. This
seems to force a dependency on optional as well. Finally the loop as
written should probably be a do..while since the stack will never be
empty on the first test.
I attached a patch that addresses the second and third issues.
The tests continue to pass for me with this change.