Boost logo

Boost Users :

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


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at