COIN-OR::LEMON - Graph Library

Opened 9 years ago

Last modified 15 months ago

#218 assigned enhancement

Path decomposition subroutine in Preflow.

Reported by: alpar Owned by: kpeter
Priority: major Milestone: LEMON 1.5 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

The title says everything.

See also #217.

Change History (5)

comment:1 Changed 9 years ago by kpeter

  • Owner changed from alpar to kpeter
  • Status changed from new to assigned

comment:2 Changed 9 years ago by kpeter

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 8 years ago by kpeter

  • Milestone set to LEMON 1.3 release

comment:4 Changed 5 years ago by alpar

  • Milestone changed from LEMON 1.3 release to LEMON 1.4 release

comment:5 Changed 15 months ago by alpar

  • Milestone changed from LEMON 1.4 release to LEMON 1.5 release
Note: See TracTickets for help on using tickets.