doc/images/bipartite_partitions.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 15 Mar 2011 19:32:21 +0100
changeset 936 ddd3c0d3d9bf
parent 586 7c12061bd271
child 1045 4e8787627db3
permissions -rw-r--r--
Implement the scaling Price Refinement heuristic in CostScaling (#417)
instead of Early Termination.

These two heuristics are similar, but the newer one is faster
and not only makes it possible to skip some epsilon phases, but
it can improve the performance of the other phases, as well.
     1 %!PS-Adobe-2.0 EPSF-2.0
     2 %%Creator: LEMON, graphToEps()
     3 %%CreationDate: Tue Nov 15 16:51:43 2005
     4 %%BoundingBox: 0 0 842 596
     5 %%EndComments
     6 /lb { setlinewidth setrgbcolor newpath moveto
     7       4 2 roll 1 index 1 index curveto stroke } bind def
     8 /l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
     9 /c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
    10 /sq { newpath 2 index 1 index add 2 index 2 index add moveto
    11       2 index 1 index sub 2 index 2 index add lineto
    12       2 index 1 index sub 2 index 2 index sub lineto
    13       2 index 1 index add 2 index 2 index sub lineto
    14       closepath pop pop pop} bind def
    15 /di { newpath 2 index 1 index add 2 index moveto
    16       2 index             2 index 2 index add lineto
    17       2 index 1 index sub 2 index             lineto
    18       2 index             2 index 2 index sub lineto
    19       closepath pop pop pop} bind def
    20 /nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
    21      setrgbcolor 1.1 div c fill
    22    } bind def
    23 /nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
    24      setrgbcolor 1.1 div sq fill
    25    } bind def
    26 /ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
    27      setrgbcolor 1.1 div di fill
    28    } bind def
    29 /arrl 1 def
    30 /arrw 0.3 def
    31 /lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
    32 /arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
    33        /w exch def /len exch def
    34        newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
    35        len w sub arrl sub dx dy lrl
    36        arrw dy dx neg lrl
    37        dx arrl w add mul dy w 2 div arrw add mul sub
    38        dy arrl w add mul dx w 2 div arrw add mul add rlineto
    39        dx arrl w add mul neg dy w 2 div arrw add mul sub
    40        dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
    41        arrw dy dx neg lrl
    42        len w sub arrl sub neg dx dy lrl
    43        closepath fill } bind def
    44 /cshow { 2 index 2 index moveto dup stringwidth pop
    45          neg 2 div fosi .35 mul neg rmoveto show pop pop} def
    46 
    47 gsave
    48 90 rotate
    49 0 -842 translate
    50 71.6378 15 translate
    51 0.389093 dup scale
    52 90 rotate
    53 1197.47 -613.138 translate
    54 %Edges:
    55 gsave
    56 513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb
    57 513.857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb
    58 393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb
    59 393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb
    60 393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb
    61 869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb
    62 869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 2 lb
    63 -82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 2 lb
    64 -663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 2 lb
    65 -663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 2 lb
    66 -1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 2 lb
    67 -1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 2 lb
    68 -1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 2 lb
    69 -1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 2 lb
    70 -880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 2 lb
    71 -499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 2 lb
    72 -499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 2 lb
    73 -499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 2 lb
    74 79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb
    75 637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb
    76 205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb
    77 399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb
    78 399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 2 lb
    79 -842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 2 lb
    80 -842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 2 lb
    81 -860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 2 lb
    82 -211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 2 lb
    83 -99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 2 lb
    84 -99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 2 lb
    85 120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 2 lb
    86 grestore
    87 %Nodes:
    88 gsave
    89 -274 -131 20 1 0 0 nc
    90 -607.82 -246.651 20 1 0 0 nc
    91 -484.494 328.869 20 0 0 1 nc
    92 108.644 334.741 20 0 0 1 nc
    93 120.389 -129.198 20 0 0 1 nc
    94 -99.8351 99.8351 20 1 0 0 nc
    95 -211.415 -452.194 20 1 0 0 nc
    96 -860.344 -29.3633 20 0 0 1 nc
    97 -842.726 243.715 20 0 0 1 nc
    98 399.34 88.0898 20 1 0 0 nc
    99 205.543 -322.996 20 1 0 0 nc
   100 637.183 -184.989 20 0 0 1 nc
   101 79.2808 -528.539 20 0 0 1 nc
   102 -499.175 -499.175 20 0 0 1 nc
   103 -880.898 -528.539 20 0 0 1 nc
   104 -1177.47 -234.906 20 1 0 0 nc
   105 -1077.63 161.498 20 1 0 0 nc
   106 -663.61 546.157 20 1 0 0 nc
   107 -82.2171 593.138 20 0 0 1 nc
   108 596.074 302.442 20 0 0 1 nc
   109 869.153 52.8539 20 1 0 0 nc
   110 393.468 566.711 20 1 0 0 nc
   111 513.857 -446.322 20 1 0 0 nc
   112 grestore
   113 grestore
   114 showpage