Benchmark questions related to Preflow
There are some efficiency questions about the Preflow
implementation, that require thorough benchmarking.
Elevator
or LinkedElevator
should be used by default?
- The BFS implementation in the
init()
function could be made more efficient using only one vector and three indices (first
, last
, new_level
).
- We should try very large instances and check again whether the current heuristics and the constant 20 factor that is used for them are really optimal or not.
- We should try Goldberg's new idea of partial augmentations. (However it should probably be a new class.)
Change History (5)
Milestone: |
LEMON 1.1 release
|
Description: |
modified (diff)
|
Milestone: |
→ LEMON 1.5 release
|
Another idea to be considered is to store the last outgoing arc for each node, see #431.