Re: [boost] GGCL and removal of many edges

From: Asger Alstrup Nielsen (alstrup_at_[hidden])
Date: 2000-09-28 04:15:08

[Removing many edges from a directed graph efficiently]
> The best solution I see at present is to add the following function:
> 
> remove_edge_if(predicate, graph);

That should suit me fine.

Allow me to explain the broader problem: What I need to do is to reduce
a sparse, directed graph to a smaller graph.

Each edge has a criteria whether it should be included in the reduced
graph or not, and first I have to remove all the superflous edges. This
step can only be done in O(n^2) at present, and the above would
hopefully reduce this to (close to) linear time.

After removal of the edges, I have an unconnected graph left. The
topology is such that I have a starting node, and the next step is to
reduce the graph to the connected component that includes the starting
node.
I do this with a depth first search, and then remove all nodes that have
a discovery time that is later than the finishing time of the starting
node.

My profiling in my graphs show that this second step actually takes
twice the time of the first step. This is probably caused by the fact
that the graph is typically reduced to a graph with a size of 10%
compared to the original graph.

I've managed to work around this by changing my algorithm such that I
can get by with just tagging the unconnected nodes rather than deleting
them, and then handle them correctly in a later step.

However, maybe you have an idea of how to improve/use the interface such
that operations such as these can be done efficiently?

I speculate that it would be faster to construct a new graph with only
the needed bits rather than reduce the big graph, but I fail to see how
this can elegantly be expressed with the available operations.

Thank you,

Asger Alstrup