Boost C++ Libraries: Ticket #746: max flow with lower bounds (capacities)

maestrodd — Mon, 09 Oct 2006 16:17:49 GMT

Logged In: YES
user_id=520483
Hi Jens,
please try to elaborate a little more on what you are doing
and what you want to do.
Cheers,
Stephan

jens- — Mon, 09 Oct 2006 18:07:30 GMT

Logged In: YES
user_id=1615116
Hi Stephan,
to be more precise:
I had given a graph with upper capacities and wanted to
get the maxflow value. therefore I used the
boost::adjacency_list, created the residual graph and set
its residual_capacity and capacity properties as expected
by the algorithm. This is the input for the
push_relabel_max_flow.hpp and then I got the flow values
by capacity - residualcapacity. Works fine!
Now I have to include lower capacities and I would like to
know if it's possible to use these somehow directly in the
implemented algorithm.
Up to now I use a transformation, which adds dummy edges
to the residual graph so that afterwards the lower
capacities are eliminated. But this makes the graph bigger
(more edges). Is there a possibility to use the
push_relabel_max_flow.hpp without adding edges, just by
using the property map?
yours
Jens

jens- — Tue, 10 Oct 2006 14:09:53 GMT

Logged In: YES
user_id=1615116
A paper in which the transformation from a max flow
problem with lower capacities (bounds) to one with lower
capacity (bound) zero is described in:
http://etd.uwaterloo.ca/etd/cquimber2006.pdf
If one finds a solution without adding edges, as done in
the paper, please tell me!

jens- — Tue, 10 Oct 2006 14:17:54 GMT

Logged In: YES
user_id=1615116
mistake in Link, correction:
http://etd.uwaterloo.ca/etd/cquimper2006.pdf

status, summary changed

jens- — Sun, 22 Oct 2006 14:24:12 GMT

status assigned → closed
summary max flow with lower capacities → max flow with lower bounds (capacities)

Logged In: YES
user_id=1615116
1. capacity == bound
2. Inttroducing lower bounds:
As described in
R.K. Ahuja, T.L. Magnanti and J.B. Orlin
"Network flows: Theory, Algorithms, and Applications "
there are implementations of the max flow algorithm that
work with only residual capacities! (see chapter 6,
p.191ff)
So it is easy to introduce lower bounds on the edges and
to solve the max flow problem more efficiently than by
using dummy edges as done by Berge.
My question: Is there a possibility to have such an
implementation in the boost library. For future works this
semms really interesting to me.

owner, status, description changed; severity set

Dave Abrahams — Fri, 06 Jul 2007 12:28:42 GMT

owner changed from nobody to Douglas Gregor
status assigned → new
description modified (diff)
severity → Showstopper

owner changed

Marshall Clow — Thu, 12 Jul 2007 15:18:16 GMT

owner changed from Douglas Gregor to doug_gregor

Assigned to "doug_gregor" instead of nonexistent user "dgregor"

owner changed

Douglas Gregor — Tue, 29 Apr 2008 18:32:33 GMT

owner changed from doug_gregor to Douglas Gregor

severity changed

Jeremiah Willcock — Mon, 30 Nov 2009 02:23:38 GMT

severity Showstopper → Not Applicable

milestone set

Jeremiah Willcock — Wed, 08 Dec 2010 19:44:29 GMT

milestone → To Be Determined