test/preflow_graph.dim
author kpeter
Wed, 15 Oct 2008 12:04:11 +0000
changeset 2625 c51b320bc51c
parent 887 ec6a528dafd2
permissions -rw-r--r--
Major improvement in the cost scaling algorithm

- Add a new variant that use the partial augment-relabel method.
- Use this method instead of push-relabel by default.
- Use the "Early Termination" heuristic instead of "Price Refinement".

Using the new method and heuristic the algorithm proved to be
2-2.5 times faster on all input files.
jacint@887
     1
p max 10 17
jacint@887
     2
n 2 s
jacint@887
     3
n 9 t
jacint@887
     4
a 1 2 20
jacint@887
     5
a 1 3 0
jacint@887
     6
a 2 2 3
jacint@887
     7
a 2 3 8
jacint@887
     8
a 2 4 8
jacint@887
     9
a 3 6 5
jacint@887
    10
a 4 3 5
jacint@887
    11
a 4 6 5
jacint@887
    12
a 4 7 5
jacint@887
    13
a 5 4 3
jacint@887
    14
a 6 8 3
jacint@887
    15
a 6 7 10
jacint@887
    16
a 6 9 10
jacint@887
    17
a 7 9 8
jacint@887
    18
a 9 10 20
jacint@887
    19
a 9 2 5
jacint@887
    20
a 10 6 5