[Lemon-user] How to make a graph algorithm fast when I need to work on subgraph (i.e. with some edges removed)

[Zenna Tavares]

I have implemented the bottleneck shortest path algorithm in lemon.
The algorithm needs to remove (or at least hide) edges in an iterative
manner.  This has caused me severe performance problems, which I hope
someone may be able to help me with.  The problem is that I need to
perform the algorithm several thousand times on the same original
graph, but inside the algorithm, edges must be removed.  I implemented
this the algorithm in two forms and used gprof to assess performance.

1. I made a copy of the graph to use a 'fresh' one for each execution
of the algorithm
    Problem 1: It took an extremely long time to copy the graph each time
    Problem 2: When copied, the ids ( graph.id() ) of the nodes and
edges were completely changed causing incorrect results (as my
implementation works with these ids).

2. Implemented as a static graph and used the adaptors to hide edges
and unhide for the next iteration
    Problem: The algorithm to find connected components now takes an
extremely long time (offsetting any savings made from not having to
copy the graph)

The graph has around two million nodes and thirty million edges.

Anyone have any suggestions?

Thanks

Zenna