COIN-OR::LEMON - Graph Library

Opened 15 years ago

Last modified 7 years ago

#218 assigned enhancement

Path decomposition subroutine in Preflow.

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


The title says everything.

See also #217.

Change History (5)

comment:1 Changed 15 years ago by Peter Kovacs

Owner: changed from Alpar Juttner to Peter Kovacs
Status: newassigned

comment:2 Changed 15 years ago by Peter Kovacs

I think it should implemented separately from the flow and circulation classes (just like #216) to be able to use with an arbitrary flow (or circulation) that does not have flow cycles.

E.g. we could have a separate class for transforming a flow into a flow without cycles (i.e. without directed cycles consisting of arcs with positive flow value, see also #216, where another "without cycles" notion is also discussed) and this class could also support path decomposition.

However path decomposition can also be useful without trying to eliminate flow cycles, when we do know that the flow doesn't contain cycles. E.g. the first phase of the current Suurballe implementation produces a union of k paths as a flow and the second phase performs a path decomposition on it.

comment:3 Changed 14 years ago by Peter Kovacs

Milestone: LEMON 1.3 release

comment:4 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.3 releaseLEMON 1.4 release

comment:5 Changed 7 years ago by Alpar Juttner

Milestone: LEMON 1.4 releaseLEMON 1.5 release
Note: See TracTickets for help on using tickets.