[Boost-users] [BGL] Custom edge-removing visitor.

From: Blowhorn (Kili2x_at_[hidden])
Date: 2004-01-16 20:05:00

Hello, all.

     I'm working on an algorithm that takes a graph and two path iterators (begin and past-the-end) as input, and removes "cross edges" (is that the right term in this case?) from the graph until the path described by the iterators is the only simple path between those two vertices.

     The implementation I have so far consists of a function template and three visitor class templates built on top of the boost::depth_first_visit function template.  I'm still improving on it (too many out-edges from the path itself are being removed), but for now the function works as it should.

     Now, the graph reference passed to the operator() member function in the boost::base_visitor class template (from which I inherited) must be a constant reference, so I can't pass it to the boost::remove_edge function.  Furthermore, looking at the source code included in <boost/graph/depth_first_search.hpp> (both 1.30.2 and CVS versions), the edge passed to vis.forward_or_cross_edge cannot be removed without invalidating the out_edge_iterator used in the depth-first traversal.

     I've worked around the first issue by keeping a non-constant reference to the graph as a member of my custom visitor class and passing that reference to boost::remove_edge, and I'm using the boost::on_finish_vertex event filter instead of boost::on_forward_or_cross_edge (adjusting the code as appropritate) in order to overcome the second issue.

     The workarounds look rather kludgey in code, so removing the const modifier and/or adding an extra iterator to store the current edge while incrementing the traversing iterator might enable me to come up with a more elegant solution.  Would such changes to <boost/graph/depth_first_search.hpp> break compatibility with older code?  Or are there other particular issues in play?

     BTW, Is this the appropriate list for seeking such help?  

                                        TIA!
                                        Cromwell Enage

__________________________________________________________________
New! Unlimited Netscape Internet Service.
Only $9.95 a month -- Sign up today at http://isp.netscape.com/register
Act now to get a personalized email address!

Netscape. Just the Net You Need.