lemon-0.x: demo/sample.lgf@c51b320bc51c

Mercurial lemon-0.x / file revision

demo/sample.lgf

author	kpeter
	Wed, 15 Oct 2008 12:04:11 +0000
changeset 2625	c51b320bc51c
parent 1901	723b2b81d900
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.

     1 @nodeset

     2 label      coordinates_x   coordinates_y

     3 5       796.398 208.035

     4 4       573.002 63.002

     5 3       568.549 401.748

     6 2       277.889 68.476

     7 1       288.248 397.327

     8 0       102.239 257.532

     9 @edgeset

    10                 label      capacity

    11 4       5       6       8

    12 3       5       5       8

    13 2       4       4       5

    14 1       4       3       8

    15 1       3       2       5

    16 0       2       1       10

    17 0       1       0       10

    18 #This is a comment here

    19 @nodes

    20 source 0

    21 target 5

    22 @edges

    23 @attributes

    24 name "Simple Sample Graph"

    25 author "Attila BERNATH"

    26 @end

lemon-0.x

RSS Atom