On Jul 19, 2005, at 4:14 AM, Feldman, Yulik wrote:

<excerpt><fontfamily><param>Arial</param><x-tad-bigger>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:</x-tad-bigger></fontfamily>

<fontfamily><param>Arial</param><x-tad-bigger> </x-tad-bigger></fontfamily>[snip]

<fontfamily><param>Arial</param><x-tad-bigger>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).

</x-tad-bigger></fontfamily></excerpt>

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. 


<excerpt><fontfamily><param>Arial</param><x-tad-bigger> 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)?</x-tad-bigger></fontfamily>

</excerpt>

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.


<excerpt><fontfamily><param>Arial</param><x-tad-bigger>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).

</x-tad-bigger></fontfamily></excerpt>

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.


<excerpt><fontfamily><param>Arial</param><x-tad-bigger>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).</x-tad-bigger></fontfamily>

</excerpt>

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