GGCL and removal of many edges

From: jsiek_at_[hidden]
Date: 2000-09-26 11:11:42

Forwarded bug report/feature request for the graph library.

Asger Alstrup Nielsen writes:
 > Dear Jeremy,
 > 
 > I'm a fond user of the GGCL, and I follow your integration of the code
 > into Boost with great interest. However, I've ran into a problem: How
 > can I efficiently remove many edges from a graph?
 > 
 > It seems that code like this won't work:
 > 
 > 	Graph::edge_iterator e1, e2;
 > 	for (boost::tie(e1, e2) = edges(g); e1 != e2; ++e1) {
 > 		if ([criteria]) {
 > 			// Remove this edge!
 > 			remove_edge(g, *e1);
 > 		}
 > 	}
 > 
 > The only alternative I can find is to use an O(n^2) algorithm like this:
 > 
 > 	bool done = false;
 > 	while (!done) {
 > 		Graph::edge_iterator e1, e2;
 > 		for (boost::tie(e1, e2) = edges(g); e1 != e2; ++e1) {
 > 			if ([criteria]) {
 > 				// Remove this edge!
 > 				remove_edge(g, *e1);
 > 				done = false;
 > 				break;
 > 			}
 > 		}
 > 		done = true;
 > 	}
 > 
 > Any ideas?
 > 
 > I suppose a similar problem appears with nodes.
 > 
 > Ideally, I would like to be able to use the STL algorithm remove_if for
 > this job.
 > 
 > I use an older version of GGCL because I use VC++. I don't believe you
 > have addressed this problem in the later versions, but please correct me
 > if I'm wrong.
 > 
 > Thank you,
 > 
 > Asger Alstrup Nielsen
 >