doc/images/planar.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@2501
     1
%!PS-Adobe-2.0 EPSF-2.0
deba@2501
     2
%%Creator: LEMON, graphToEps()
deba@2501
     3
%%CreationDate: Fri Oct 19 18:32:32 2007
deba@2501
     4
%%BoundingBox: 0 0 596 842
deba@2501
     5
%%DocumentPaperSizes: a4
deba@2501
     6
%%EndComments
deba@2501
     7
/lb { setlinewidth setrgbcolor newpath moveto
deba@2501
     8
      4 2 roll 1 index 1 index curveto stroke } bind def
deba@2501
     9
/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
deba@2501
    10
/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
deba@2501
    11
/sq { newpath 2 index 1 index add 2 index 2 index add moveto
deba@2501
    12
      2 index 1 index sub 2 index 2 index add lineto
deba@2501
    13
      2 index 1 index sub 2 index 2 index sub lineto
deba@2501
    14
      2 index 1 index add 2 index 2 index sub lineto
deba@2501
    15
      closepath pop pop pop} bind def
deba@2501
    16
/di { newpath 2 index 1 index add 2 index moveto
deba@2501
    17
      2 index             2 index 2 index add lineto
deba@2501
    18
      2 index 1 index sub 2 index             lineto
deba@2501
    19
      2 index             2 index 2 index sub lineto
deba@2501
    20
      closepath pop pop pop} bind def
deba@2501
    21
/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
deba@2501
    22
     setrgbcolor 1.1 div c fill
deba@2501
    23
   } bind def
deba@2501
    24
/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
deba@2501
    25
     setrgbcolor 1.1 div sq fill
deba@2501
    26
   } bind def
deba@2501
    27
/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
deba@2501
    28
     setrgbcolor 1.1 div di fill
deba@2501
    29
   } bind def
deba@2501
    30
/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
deba@2501
    31
  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
deba@2501
    32
  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
deba@2501
    33
  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
deba@2501
    34
  5 index 5 index 5 index c fill
deba@2501
    35
  setrgbcolor 1.1 div c fill
deba@2501
    36
  } bind def
deba@2501
    37
/nmale {
deba@2501
    38
  0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
deba@2501
    39
  newpath 5 index 5 index moveto
deba@2501
    40
  5 index 4 index 1 mul 1.5 mul add
deba@2501
    41
  5 index 5 index 3 sqrt 1.5 mul mul add
deba@2501
    42
  1 index 1 index lineto
deba@2501
    43
  1 index 1 index 7 index sub moveto
deba@2501
    44
  1 index 1 index lineto
deba@2501
    45
  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
deba@2501
    46
  stroke
deba@2501
    47
  5 index 5 index 5 index c fill
deba@2501
    48
  setrgbcolor 1.1 div c fill
deba@2501
    49
  } bind def
deba@2501
    50
/arrl 1 def
deba@2501
    51
/arrw 0.3 def
deba@2501
    52
/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
deba@2501
    53
/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
deba@2501
    54
       /w exch def /len exch def
deba@2501
    55
       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
deba@2501
    56
       len w sub arrl sub dx dy lrl
deba@2501
    57
       arrw dy dx neg lrl
deba@2501
    58
       dx arrl w add mul dy w 2 div arrw add mul sub
deba@2501
    59
       dy arrl w add mul dx w 2 div arrw add mul add rlineto
deba@2501
    60
       dx arrl w add mul neg dy w 2 div arrw add mul sub
deba@2501
    61
       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
deba@2501
    62
       arrw dy dx neg lrl
deba@2501
    63
       len w sub arrl sub neg dx dy lrl
deba@2501
    64
       closepath fill } bind def
deba@2501
    65
/cshow { 2 index 2 index moveto dup stringwidth pop
deba@2501
    66
         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
deba@2501
    67
deba@2501
    68
gsave
deba@2501
    69
15 138.307 translate
deba@2501
    70
12.7843 dup scale
deba@2501
    71
90 rotate
deba@2501
    72
0.608112 -43.6081 translate
deba@2501
    73
%Edges:
deba@2501
    74
gsave
deba@2501
    75
9 31 9.5 30.5 10 30 0 0 0 0.091217 lb
deba@2501
    76
9 31 5.5 34.5 2 38 0 0 0 0.091217 lb
deba@2501
    77
9 31 25.5 16 42 1 0 0 0 0.091217 lb
deba@2501
    78
3 40 23 20.5 43 1 0 0 0 0.091217 lb
deba@2501
    79
3 40 22.5 20.5 42 1 0 0 0 0.091217 lb
deba@2501
    80
3 40 2.5 40.5 2 41 0 0 0 0.091217 lb
deba@2501
    81
13 25 10.5 24.5 8 24 0 0 0 0.091217 lb
deba@2501
    82
13 25 12 27 11 29 0 0 0 0.091217 lb
deba@2501
    83
3 4 2.5 3 2 2 0 0 0 0.091217 lb
deba@2501
    84
3 4 4.5 3 6 2 0 0 0 0.091217 lb
deba@2501
    85
6 25 7 24.5 8 24 0 0 0 0.091217 lb
deba@2501
    86
6 25 6 24.5 6 24 0 0 0 0.091217 lb
deba@2501
    87
34 2 33.5 2 33 2 0 0 0 0.091217 lb
deba@2501
    88
34 2 35 2 36 2 0 0 0 0.091217 lb
deba@2501
    89
6 8 16 9 26 10 0 0 0 0.091217 lb
deba@2501
    90
6 8 6 10.5 6 13 0 0 0 0.091217 lb
deba@2501
    91
6 8 6 7.5 6 7 0 0 0 0.091217 lb
deba@2501
    92
26 10 27.5 8.5 29 7 0 0 0 0.091217 lb
deba@2501
    93
26 10 27.5 9 29 8 0 0 0 0.091217 lb
deba@2501
    94
10 30 10.5 29.5 11 29 0 0 0 0.091217 lb
deba@2501
    95
8 24 7 23.5 6 23 0 0 0 0.091217 lb
deba@2501
    96
8 24 8 24.5 8 25 0 0 0 0.091217 lb
deba@2501
    97
33 2 32.5 2 32 2 0 0 0 0.091217 lb
deba@2501
    98
29 7 17.5 7 6 7 0 0 0 0.091217 lb
deba@2501
    99
2 2 1.5 22 1 42 0 0 0 0.091217 lb
deba@2501
   100
2 2 3.5 2 5 2 0 0 0 0.091217 lb
deba@2501
   101
21 15 13.5 14.5 6 14 0 0 0 0.091217 lb
deba@2501
   102
21 15 21 15.5 21 16 0 0 0 0.091217 lb
deba@2501
   103
1 42 0.5 42.5 0 43 0 0 0 0.091217 lb
deba@2501
   104
1 42 1.5 41.5 2 41 0 0 0 0.091217 lb
deba@2501
   105
6 15 6 15.5 6 16 0 0 0 0.091217 lb
deba@2501
   106
6 15 6 14.5 6 14 0 0 0 0.091217 lb
deba@2501
   107
43 1 22 0.5 1 0 0 0 0 0.091217 lb
deba@2501
   108
31 2 18.5 2 6 2 0 0 0 0.091217 lb
deba@2501
   109
31 2 31.5 2 32 2 0 0 0 0.091217 lb
deba@2501
   110
6 24 6 23.5 6 23 0 0 0 0.091217 lb
deba@2501
   111
6 16 6 16.5 6 17 0 0 0 0.091217 lb
deba@2501
   112
6 23 6 20 6 17 0 0 0 0.091217 lb
deba@2501
   113
6 2 5.5 2 5 2 0 0 0 0.091217 lb
deba@2501
   114
6 2 6 4.5 6 7 0 0 0 0.091217 lb
deba@2501
   115
0 43 0.5 21.5 1 0 0 0 0 0.091217 lb
deba@2501
   116
1 1 19.5 1.5 38 2 0 0 0 0.091217 lb
deba@2501
   117
1 1 1 0.5 1 0 0 0 0 0.091217 lb
deba@2501
   118
2 38 5.5 31.5 9 25 0 0 0 0.091217 lb
deba@2501
   119
25 13 15.5 13 6 13 0 0 0 0.091217 lb
deba@2501
   120
25 13 15.5 13.5 6 14 0 0 0 0.091217 lb
deba@2501
   121
8 25 8.5 25 9 25 0 0 0 0.091217 lb
deba@2501
   122
11 29 24.5 15.5 38 2 0 0 0 0.091217 lb
deba@2501
   123
6 17 11.5 18 17 19 0 0 0 0.091217 lb
deba@2501
   124
16 23 26.5 12.5 37 2 0 0 0 0.091217 lb
deba@2501
   125
16 23 18.5 19.5 21 16 0 0 0 0.091217 lb
deba@2501
   126
36 2 36.5 2 37 2 0 0 0 0.091217 lb
deba@2501
   127
36 2 32.5 5 29 8 0 0 0 0.091217 lb
deba@2501
   128
6 13 6 13.5 6 14 0 0 0 0.091217 lb
deba@2501
   129
37 2 37.5 2 38 2 0 0 0 0.091217 lb
deba@2501
   130
21 16 19 17.5 17 19 0 0 0 0.091217 lb
deba@2501
   131
grestore
deba@2501
   132
%Nodes:
deba@2501
   133
gsave
deba@2501
   134
29 8 0.304556 1 1 1 nc
deba@2501
   135
2 41 0.304556 1 1 1 nc
deba@2501
   136
6 7 0.304556 1 1 1 nc
deba@2501
   137
5 2 0.304556 1 1 1 nc
deba@2501
   138
17 19 0.304556 1 1 1 nc
deba@2501
   139
21 16 0.304556 1 1 1 nc
deba@2501
   140
1 0 0.304556 1 1 1 nc
deba@2501
   141
9 25 0.304556 1 1 1 nc
deba@2501
   142
6 14 0.304556 1 1 1 nc
deba@2501
   143
42 1 0.304556 1 1 1 nc
deba@2501
   144
38 2 0.304556 1 1 1 nc
deba@2501
   145
37 2 0.304556 1 1 1 nc
deba@2501
   146
6 13 0.304556 1 1 1 nc
deba@2501
   147
36 2 0.304556 1 1 1 nc
deba@2501
   148
16 23 0.304556 1 1 1 nc
deba@2501
   149
6 17 0.304556 1 1 1 nc
deba@2501
   150
11 29 0.304556 1 1 1 nc
deba@2501
   151
8 25 0.304556 1 1 1 nc
deba@2501
   152
32 2 0.304556 1 1 1 nc
deba@2501
   153
25 13 0.304556 1 1 1 nc
deba@2501
   154
2 38 0.304556 1 1 1 nc
deba@2501
   155
1 1 0.304556 1 1 1 nc
deba@2501
   156
0 43 0.304556 1 1 1 nc
deba@2501
   157
6 2 0.304556 1 1 1 nc
deba@2501
   158
6 23 0.304556 1 1 1 nc
deba@2501
   159
6 16 0.304556 1 1 1 nc
deba@2501
   160
6 24 0.304556 1 1 1 nc
deba@2501
   161
31 2 0.304556 1 1 1 nc
deba@2501
   162
43 1 0.304556 1 1 1 nc
deba@2501
   163
6 15 0.304556 1 1 1 nc
deba@2501
   164
1 42 0.304556 1 1 1 nc
deba@2501
   165
21 15 0.304556 1 1 1 nc
deba@2501
   166
2 2 0.304556 1 1 1 nc
deba@2501
   167
29 7 0.304556 1 1 1 nc
deba@2501
   168
33 2 0.304556 1 1 1 nc
deba@2501
   169
8 24 0.304556 1 1 1 nc
deba@2501
   170
10 30 0.304556 1 1 1 nc
deba@2501
   171
26 10 0.304556 1 1 1 nc
deba@2501
   172
6 8 0.304556 1 1 1 nc
deba@2501
   173
34 2 0.304556 1 1 1 nc
deba@2501
   174
6 25 0.304556 1 1 1 nc
deba@2501
   175
3 4 0.304556 1 1 1 nc
deba@2501
   176
13 25 0.304556 1 1 1 nc
deba@2501
   177
3 40 0.304556 1 1 1 nc
deba@2501
   178
9 31 0.304556 1 1 1 nc
deba@2501
   179
grestore
deba@2501
   180
grestore
deba@2501
   181
showpage