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

[Alpár Jüttner]

Dear Zenna,

Could you please define the exact algorithmic problem you are dealing
with?

Are you looking for a path between to given points (or one points to
each other points?) for which the cost of the cheapest edge of the path
is the highest?

Regards,
Alpár


On Fri, 2010-10-08 at 17:33 +0100, Zenna Tavares wrote:
> 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
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user