doc/images/bipartite_partitions.eps
author kpeter
Sun, 05 Oct 2008 13:36:43 +0000
changeset 2619 30fb4d68b0e8
permissions -rw-r--r--
Improve network simplex algorithm

- Remove "Limited Search" and "Combined" pivot rules.
- Add a new pivot rule "Altering Candidate List".
- Make the edge selection faster in every pivot rule.
- Set the default rule to "Block Search".
- Doc improvements.

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