Re: [Boost-users] performance issue with graph edge removal

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-07-22 13:36:30

On Jul 19, 2005, at 4:14 AM, Feldman, Yulik wrote:
> Our project has recently run into severe performance issue with 
> remove_edge() function of Boost graph. In our particular case, we use 
> adjacency list specialized as:
>  [snip]
> What is actually interesting about this situation, is that I see no 
> way to remove all edges (let’s say we need to remove all edges) with 
> any Boost function and with any adjacency list specialization in O(E) 
> complexity, not necessarily the one we’re currently using. The O(E/V) 
> complexity of the remove_edge() comes from the fact that there is a 
> need to remove the edge from in/out edge lists of the vertices 
> connected by the edge. Even though I know I will not need any of these 
> lists after all edges are removed, remove_edge() doesn’t know that, so 
> it is doing the “extra” work of updating the lists one-by-one. 
> Moreover, in case of edge lists such as vector/list/multiset, i.e. 
> containers that allow parallel edges in the graph, the search is 
> linear in the size of containers (resulting in O(E/V) complexity of 
> the operation).

I was going to suggest remove_edge_if(), but I see that its 
implementation is no more efficient that just calling remove_edge() a 
bunch of times.

>  The question is what can be done, in any way, to do this “simple” 
> operation of removing all edges of the graph in “more reasonable” 
> complexity O(E) instead of O(E * E/V)?

Well, there's the clear() method, which will remove all edges and all 
vertices in the graph. There's no reason we can't implement a 
"clear_all_edges" function that removes all edges.

> If I would be free to change Boost’s graph implementation, one 
> possible solution could be to store in each edge two iterators 
> pointing to the position of this edge in the corresponding in/out edge 
> lists. This would allow removal of the edge from “list” container in 
> O(1). However, it doesn’t seem to be possible to do with current Boost 
> implementation. Still, even if it would be possible, the memory 
> consumption would increase due to the storage of the two iterators (at 
> least two additional extra pointers per edge).

If one uses remove_edge_if(), we can get it down to one extra iterator 
per edge, because remove_edge_if() already has one of the iterators. 
We'd then need to store only the iterator to the in-edge.

> Is there a way to remove all edges in O(E) complexity? Do I miss 
> something, or there is an inherent performance issue in current Boost 
> graph implementation with regard to the edge removal? Even if the 
> current situation is by design due to memory consumption trade offs, I 
> wish the graph implementation would be flexible enough to let the user 
> control performance/memory balance, instead of requiring the 
> performance hit. Or, at least, to provide an atomic function for 
> removal of all edges of the graph, which can be easily implemented to 
> work fast and without incurring any memory overhead with all 
> underlying in/out edge container implementations (just clear all 
> edge-related containers).

Yes, we can definitely provide a clear_all_edges() function. We can't 
change the default trade-off that favors smaller memory consumption 
over efficiency of edge removal, but we might be able to devise a way 
to tell adjacency_list to favor insert/removal performance over memory 
consumption.

        Doug