Opened 15 years ago
Last modified 8 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: |
Description
The title says everything.
See also #217.
Change History (5)
comment:1 Changed 15 years ago by
| Owner: | changed from Alpar Juttner to Peter Kovacs |
|---|---|
| Status: | new → assigned |
comment:2 Changed 15 years ago by
comment:3 Changed 14 years ago by
| Milestone: | → LEMON 1.3 release |
|---|
comment:4 Changed 11 years ago by
| Milestone: | LEMON 1.3 release → LEMON 1.4 release |
|---|
comment:5 Changed 8 years ago by
| Milestone: | LEMON 1.4 release → LEMON 1.5 release |
|---|
Note: See
TracTickets for help on using
tickets.
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.