COIN-OR::LEMON - Graph Library

Opened 15 years ago

Closed 14 years ago

#181 closed enhancement (done)

Support multiple targets for Suurballe

Reported by: Alpar Juttner Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id: 80ec623f529f

Description (last modified by Peter Kovacs)

The concept is that

run(s,t,k);

would do just as it does now, but in addition to it, there would be a function

init(s);

performing a full Dijkstra and computing reduced arc costs, which could be then followed by several

start(t,k);

execution, each of them would reverse the arcs on the shortest s-t path found by init(s) and execute partial Dijkstra to t only k-1 times.

It could speed up the use cases when k arc-disjoint s-t paths are needed for a lot of t nodes (e.g. all t!=s nodes).

Change History (11)

comment:1 Changed 15 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Peter Kovacs

comment:2 Changed 15 years ago by Alpar Juttner

Summary: Support multiple target for SuurballSupport multiple targets for Suurball

comment:3 Changed 15 years ago by Peter Kovacs

Description: modified (diff)
Status: newassigned
Summary: Support multiple targets for SuurballSupport multiple targets for Suurballe

comment:4 Changed 15 years ago by Peter Kovacs

Description: modified (diff)

comment:5 Changed 15 years ago by Peter Kovacs

Note that the current implementation is a specialization of the Successive Shortest Path algorithm for the Minimum Cost Flow problem.

In fact, Suurballe and Suurballe-Tarjan algorithms only solves this problem for the case of k=2, however with a much better theoretical time complexity (due to a more sophisticated method). It would be nice to implement these algorithms and compare the efficiency to the current implementation for k=2.

comment:6 Changed 15 years ago by Peter Kovacs

Currently there are findFlow() and findPaths() functions instead of start().

comment:7 Changed 15 years ago by Peter Kovacs

Priority: minormajor

comment:8 Changed 14 years ago by Peter Kovacs

There are two problems that have to solved for this improvement:

  1. The potentials (node distances) have to be "saved" after the first full Dijkstra, and they have to be reverted to this state at the beginning of each start() call. (And the flow have to be set to zero on all arcs.)
  2. The proposed interface conflicts with the current one: we already has an init(s) function, but it does not call Dijkstra. Now
      init(s);
      findFlow(t,k);
      findPaths();
    
    is said to be equivalent to run(s,t,k), so it runs s-t Dijkstra k times (and no full Dijkstra).

comment:9 in reply to:  8 Changed 14 years ago by Peter Kovacs

Replying to kpeter:

  1. The proposed interface conflicts with the current one: we already has an init(s) function...

A possible solution is to use different names. In #323, [9a7e4e606f83] is proposed with an implementation.

comment:10 Changed 14 years ago by Peter Kovacs

Milestone: LEMON 1.2 release

comment:11 Changed 14 years ago by Peter Kovacs

Resolution: done
Status: assignedclosed

[9a7e4e606f83] went to the main branch, this ticket can be closed.

Note: See TracTickets for help on using tickets.