[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]

Assume you want to solve the following problem (please confirm it is
indeed the problem you want to solve).

        For a given undirected graph G=(N,E) and cost function c:E->R,
        the bottleneck cost of a path is the cost of its minimum cost
        edge (b(p):=min{c(e): e in p}).
        
        For a given pair s,t of nodes we are looking for an s-t path p
        having the maximum bottleneck cost b(p).
        
In order to solve this, find a maximum cost spanning tree (e.g. by
kruskal()+ a negMap adaptor). This spanning tree determines a unique
path between s and t. It is easy to see that this path is a maximum
bottleneck path between s and t.

Regards,
Alpar


On Fri, 2010-10-08 at 19:05 +0100, Zenna Tavares wrote:
> I am not sure how you could solve this using a minimum spanning tree,
> so I would love to hear.  The alternative method suggested in that
> paper as well as in responses in the stack overflow forum, is to use
> dijkstra's algorithm, but make the priority queue return the node with
> the maximum height, as opposed to the shortest path.  The alleged
> advantage of the BSP algorithm over this is that the BSP algorithm is
> linear in complexity, which is good.  I think the problems I am facing
> are more with the lemon library than algorithmic (although I will
> happily change the algorithm if need be).
> 
> On 8 October 2010 18:06, Alpár Jüttner <alpar at cs.elte.hu> wrote:
> > On Fri, 2010-10-08 at 17:49 +0100, Zenna Tavares wrote:
> >> The algorith is called the Bottleneck shortest path, a good overview
> >> of it can be found in
> >> http://www.zib.de/Publications/Reports/ZR-06-22.pdf
> >
> > From the definition of the problem on the first page of the above paper,
> > I believe that for undirected graph a simple max cost spanning tree
> > (found by e.g. kruskal()) will give you the Bottleneck shortest path to
> > each destinations and once. The kruskal() implementation runs very fast
> > even on huge graphs.
> >
> > My problem is that the paper suggests something much more complex.
> >
> > Do I misunderstand something?
> >
> > Regards,
> > Alpar
> >
> >
> >>
> >> I implemented this algorithm to solve the problem I posted on
> >> stackoverflow http://stackoverflow.com/questions/3544083/shortest-path-on-a-graph-where-distances-change-dynamically-maximum-energy-path
> >> .  The goal is to find, between two nodes in the graph (maxima on a
> >> landscape), of all paths connecting these two points, what is the
> >> least energy edge in the best path connecting them; where the best
> >> path is one which reduces least in energy.
> >>
> >> Sorry if that sounds a bit convoluted, but basically if A to B are two
> >> local maxima on a landscape, then the best path(s) is the one which
> >> goes down the landscape the least to get from A to B.  Of that best
> >> path what is the lowest point, i.e. the bottleneck.
> >>
> >> Zenna
> >>
> >> On 8 October 2010 17:40, Alpár Jüttner <alpar at cs.elte.hu> wrote:
> >> > 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
> >> >
> >> >
> >> >
> >
> >
> >