doc/images/grid_ugraph.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@2223
     1
%!PS-Adobe-2.0 EPSF-2.0
deba@2223
     2
%%Title: Grid undirected graph
deba@2223
     3
%%Copyright: (C) 2006 LEMON Project
deba@2223
     4
%%Creator: LEMON, graphToEps()
deba@2223
     5
%%CreationDate: Fri Sep 29 11:55:56 2006
deba@2223
     6
%%BoundingBox: 0 0 596 842
deba@2223
     7
%%DocumentPaperSizes: a4
deba@2223
     8
%%EndComments
deba@2223
     9
/lb { setlinewidth setrgbcolor newpath moveto
deba@2223
    10
      4 2 roll 1 index 1 index curveto stroke } bind def
deba@2223
    11
/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
deba@2223
    12
/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
deba@2223
    13
/sq { newpath 2 index 1 index add 2 index 2 index add moveto
deba@2223
    14
      2 index 1 index sub 2 index 2 index add lineto
deba@2223
    15
      2 index 1 index sub 2 index 2 index sub lineto
deba@2223
    16
      2 index 1 index add 2 index 2 index sub lineto
deba@2223
    17
      closepath pop pop pop} bind def
deba@2223
    18
/di { newpath 2 index 1 index add 2 index moveto
deba@2223
    19
      2 index             2 index 2 index add lineto
deba@2223
    20
      2 index 1 index sub 2 index             lineto
deba@2223
    21
      2 index             2 index 2 index sub lineto
deba@2223
    22
      closepath pop pop pop} bind def
deba@2223
    23
/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
deba@2223
    24
     setrgbcolor 1.1 div c fill
deba@2223
    25
   } bind def
deba@2223
    26
/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
deba@2223
    27
     setrgbcolor 1.1 div sq fill
deba@2223
    28
   } bind def
deba@2223
    29
/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
deba@2223
    30
     setrgbcolor 1.1 div di fill
deba@2223
    31
   } bind def
deba@2223
    32
/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
deba@2223
    33
  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
deba@2223
    34
  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
deba@2223
    35
  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
deba@2223
    36
  5 index 5 index 5 index c fill
deba@2223
    37
  setrgbcolor 1.1 div c fill
deba@2223
    38
  } bind def
deba@2223
    39
/nmale {
deba@2223
    40
  0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
deba@2223
    41
  newpath 5 index 5 index moveto
deba@2223
    42
  5 index 4 index 1 mul 1.5 mul add
deba@2223
    43
  5 index 5 index 3 sqrt 1.5 mul mul add
deba@2223
    44
  1 index 1 index lineto
deba@2223
    45
  1 index 1 index 7 index sub moveto
deba@2223
    46
  1 index 1 index lineto
deba@2223
    47
  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
deba@2223
    48
  stroke
deba@2223
    49
  5 index 5 index 5 index c fill
deba@2223
    50
  setrgbcolor 1.1 div c fill
deba@2223
    51
  } bind def
deba@2223
    52
/arrl 1 def
deba@2223
    53
/arrw 0.3 def
deba@2223
    54
/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
deba@2223
    55
/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
deba@2223
    56
       /w exch def /len exch def
deba@2223
    57
       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
deba@2223
    58
       len w sub arrl sub dx dy lrl
deba@2223
    59
       arrw dy dx neg lrl
deba@2223
    60
       dx arrl w add mul dy w 2 div arrw add mul sub
deba@2223
    61
       dy arrl w add mul dx w 2 div arrw add mul add rlineto
deba@2223
    62
       dx arrl w add mul neg dy w 2 div arrw add mul sub
deba@2223
    63
       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
deba@2223
    64
       arrw dy dx neg lrl
deba@2223
    65
       len w sub arrl sub neg dx dy lrl
deba@2223
    66
       closepath fill } bind def
deba@2223
    67
/cshow { 2 index 2 index moveto dup stringwidth pop
deba@2223
    68
         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
deba@2223
    69
deba@2223
    70
gsave
deba@2223
    71
15 60.1011 translate
deba@2223
    72
7.8206 dup scale
deba@2223
    73
1.14018 1.14018 translate
deba@2223
    74
%Edges:
deba@2223
    75
gsave
deba@2223
    76
70 80 70 90 0 0 0 0.342053 l
deba@2223
    77
70 70 70 80 0 0 0 0.342053 l
deba@2223
    78
70 60 70 70 0 0 0 0.342053 l
deba@2223
    79
70 50 70 60 0 0 0 0.342053 l
deba@2223
    80
70 40 70 50 0 0 0 0.342053 l
deba@2223
    81
70 30 70 40 0 0 0 0.342053 l
deba@2223
    82
70 20 70 30 0 0 0 0.342053 l
deba@2223
    83
70 10 70 20 0 0 0 0.342053 l
deba@2223
    84
70 0 70 10 0 0 0 0.342053 l
deba@2223
    85
60 80 60 90 0 0 0 0.342053 l
deba@2223
    86
60 70 60 80 0 0 0 0.342053 l
deba@2223
    87
60 60 60 70 0 0 0 0.342053 l
deba@2223
    88
60 50 60 60 0 0 0 0.342053 l
deba@2223
    89
60 40 60 50 0 0 0 0.342053 l
deba@2223
    90
60 30 60 40 0 0 0 0.342053 l
deba@2223
    91
60 20 60 30 0 0 0 0.342053 l
deba@2223
    92
60 10 60 20 0 0 0 0.342053 l
deba@2223
    93
60 0 60 10 0 0 0 0.342053 l
deba@2223
    94
50 80 50 90 0 0 0 0.342053 l
deba@2223
    95
50 70 50 80 0 0 0 0.342053 l
deba@2223
    96
50 60 50 70 0 0 0 0.342053 l
deba@2223
    97
50 50 50 60 0 0 0 0.342053 l
deba@2223
    98
50 40 50 50 0 0 0 0.342053 l
deba@2223
    99
50 30 50 40 0 0 0 0.342053 l
deba@2223
   100
50 20 50 30 0 0 0 0.342053 l
deba@2223
   101
50 10 50 20 0 0 0 0.342053 l
deba@2223
   102
50 0 50 10 0 0 0 0.342053 l
deba@2223
   103
40 80 40 90 0 0 0 0.342053 l
deba@2223
   104
40 70 40 80 0 0 0 0.342053 l
deba@2223
   105
40 60 40 70 0 0 0 0.342053 l
deba@2223
   106
40 50 40 60 0 0 0 0.342053 l
deba@2223
   107
40 40 40 50 0 0 0 0.342053 l
deba@2223
   108
40 30 40 40 0 0 0 0.342053 l
deba@2223
   109
40 20 40 30 0 0 0 0.342053 l
deba@2223
   110
40 10 40 20 0 0 0 0.342053 l
deba@2223
   111
40 0 40 10 0 0 0 0.342053 l
deba@2223
   112
30 80 30 90 0 0 0 0.342053 l
deba@2223
   113
30 70 30 80 0 0 0 0.342053 l
deba@2223
   114
30 60 30 70 0 0 0 0.342053 l
deba@2223
   115
30 50 30 60 0 0 0 0.342053 l
deba@2223
   116
30 40 30 50 0 0 0 0.342053 l
deba@2223
   117
30 30 30 40 0 0 0 0.342053 l
deba@2223
   118
30 20 30 30 0 0 0 0.342053 l
deba@2223
   119
30 10 30 20 0 0 0 0.342053 l
deba@2223
   120
30 0 30 10 0 0 0 0.342053 l
deba@2223
   121
20 80 20 90 0 0 0 0.342053 l
deba@2223
   122
20 70 20 80 0 0 0 0.342053 l
deba@2223
   123
20 60 20 70 0 0 0 0.342053 l
deba@2223
   124
20 50 20 60 0 0 0 0.342053 l
deba@2223
   125
20 40 20 50 0 0 0 0.342053 l
deba@2223
   126
20 30 20 40 0 0 0 0.342053 l
deba@2223
   127
20 20 20 30 0 0 0 0.342053 l
deba@2223
   128
20 10 20 20 0 0 0 0.342053 l
deba@2223
   129
20 0 20 10 0 0 0 0.342053 l
deba@2223
   130
10 80 10 90 0 0 0 0.342053 l
deba@2223
   131
10 70 10 80 0 0 0 0.342053 l
deba@2223
   132
10 60 10 70 0 0 0 0.342053 l
deba@2223
   133
10 50 10 60 0 0 0 0.342053 l
deba@2223
   134
10 40 10 50 0 0 0 0.342053 l
deba@2223
   135
10 30 10 40 0 0 0 0.342053 l
deba@2223
   136
10 20 10 30 0 0 0 0.342053 l
deba@2223
   137
10 10 10 20 0 0 0 0.342053 l
deba@2223
   138
10 0 10 10 0 0 0 0.342053 l
deba@2223
   139
0 80 0 90 0 0 0 0.342053 l
deba@2223
   140
0 70 0 80 0 0 0 0.342053 l
deba@2223
   141
0 60 0 70 0 0 0 0.342053 l
deba@2223
   142
0 50 0 60 0 0 0 0.342053 l
deba@2223
   143
0 40 0 50 0 0 0 0.342053 l
deba@2223
   144
0 30 0 40 0 0 0 0.342053 l
deba@2223
   145
0 20 0 30 0 0 0 0.342053 l
deba@2223
   146
0 10 0 20 0 0 0 0.342053 l
deba@2223
   147
0 0 0 10 0 0 0 0.342053 l
deba@2223
   148
60 90 70 90 0 0 0 0.342053 l
deba@2223
   149
60 80 70 80 0 0 0 0.342053 l
deba@2223
   150
60 70 70 70 0 0 0 0.342053 l
deba@2223
   151
60 60 70 60 0 0 0 0.342053 l
deba@2223
   152
60 50 70 50 0 0 0 0.342053 l
deba@2223
   153
60 40 70 40 0 0 0 0.342053 l
deba@2223
   154
60 30 70 30 0 0 0 0.342053 l
deba@2223
   155
60 20 70 20 0 0 0 0.342053 l
deba@2223
   156
60 10 70 10 0 0 0 0.342053 l
deba@2223
   157
60 0 70 0 0 0 0 0.342053 l
deba@2223
   158
50 90 60 90 0 0 0 0.342053 l
deba@2223
   159
50 80 60 80 0 0 0 0.342053 l
deba@2223
   160
50 70 60 70 0 0 0 0.342053 l
deba@2223
   161
50 60 60 60 0 0 0 0.342053 l
deba@2223
   162
50 50 60 50 0 0 0 0.342053 l
deba@2223
   163
50 40 60 40 0 0 0 0.342053 l
deba@2223
   164
50 30 60 30 0 0 0 0.342053 l
deba@2223
   165
50 20 60 20 0 0 0 0.342053 l
deba@2223
   166
50 10 60 10 0 0 0 0.342053 l
deba@2223
   167
50 0 60 0 0 0 0 0.342053 l
deba@2223
   168
40 90 50 90 0 0 0 0.342053 l
deba@2223
   169
40 80 50 80 0 0 0 0.342053 l
deba@2223
   170
40 70 50 70 0 0 0 0.342053 l
deba@2223
   171
40 60 50 60 0 0 0 0.342053 l
deba@2223
   172
40 50 50 50 0 0 0 0.342053 l
deba@2223
   173
40 40 50 40 0 0 0 0.342053 l
deba@2223
   174
40 30 50 30 0 0 0 0.342053 l
deba@2223
   175
40 20 50 20 0 0 0 0.342053 l
deba@2223
   176
40 10 50 10 0 0 0 0.342053 l
deba@2223
   177
40 0 50 0 0 0 0 0.342053 l
deba@2223
   178
30 90 40 90 0 0 0 0.342053 l
deba@2223
   179
30 80 40 80 0 0 0 0.342053 l
deba@2223
   180
30 70 40 70 0 0 0 0.342053 l
deba@2223
   181
30 60 40 60 0 0 0 0.342053 l
deba@2223
   182
30 50 40 50 0 0 0 0.342053 l
deba@2223
   183
30 40 40 40 0 0 0 0.342053 l
deba@2223
   184
30 30 40 30 0 0 0 0.342053 l
deba@2223
   185
30 20 40 20 0 0 0 0.342053 l
deba@2223
   186
30 10 40 10 0 0 0 0.342053 l
deba@2223
   187
30 0 40 0 0 0 0 0.342053 l
deba@2223
   188
20 90 30 90 0 0 0 0.342053 l
deba@2223
   189
20 80 30 80 0 0 0 0.342053 l
deba@2223
   190
20 70 30 70 0 0 0 0.342053 l
deba@2223
   191
20 60 30 60 0 0 0 0.342053 l
deba@2223
   192
20 50 30 50 0 0 0 0.342053 l
deba@2223
   193
20 40 30 40 0 0 0 0.342053 l
deba@2223
   194
20 30 30 30 0 0 0 0.342053 l
deba@2223
   195
20 20 30 20 0 0 0 0.342053 l
deba@2223
   196
20 10 30 10 0 0 0 0.342053 l
deba@2223
   197
20 0 30 0 0 0 0 0.342053 l
deba@2223
   198
10 90 20 90 0 0 0 0.342053 l
deba@2223
   199
10 80 20 80 0 0 0 0.342053 l
deba@2223
   200
10 70 20 70 0 0 0 0.342053 l
deba@2223
   201
10 60 20 60 0 0 0 0.342053 l
deba@2223
   202
10 50 20 50 0 0 0 0.342053 l
deba@2223
   203
10 40 20 40 0 0 0 0.342053 l
deba@2223
   204
10 30 20 30 0 0 0 0.342053 l
deba@2223
   205
10 20 20 20 0 0 0 0.342053 l
deba@2223
   206
10 10 20 10 0 0 0 0.342053 l
deba@2223
   207
10 0 20 0 0 0 0 0.342053 l
deba@2223
   208
0 90 10 90 0 0 0 0.342053 l
deba@2223
   209
0 80 10 80 0 0 0 0.342053 l
deba@2223
   210
0 70 10 70 0 0 0 0.342053 l
deba@2223
   211
0 60 10 60 0 0 0 0.342053 l
deba@2223
   212
0 50 10 50 0 0 0 0.342053 l
deba@2223
   213
0 40 10 40 0 0 0 0.342053 l
deba@2223
   214
0 30 10 30 0 0 0 0.342053 l
deba@2223
   215
0 20 10 20 0 0 0 0.342053 l
deba@2223
   216
0 10 10 10 0 0 0 0.342053 l
deba@2223
   217
0 0 10 0 0 0 0 0.342053 l
deba@2223
   218
grestore
deba@2223
   219
%Nodes:
deba@2223
   220
gsave
deba@2223
   221
70 90 1.14018 1 1 1 nc
deba@2223
   222
70 80 1.14018 1 1 1 nc
deba@2223
   223
70 70 1.14018 1 1 1 nc
deba@2223
   224
70 60 1.14018 1 1 1 nc
deba@2223
   225
70 50 1.14018 1 1 1 nc
deba@2223
   226
70 40 1.14018 1 1 1 nc
deba@2223
   227
70 30 1.14018 1 1 1 nc
deba@2223
   228
70 20 1.14018 1 1 1 nc
deba@2223
   229
70 10 1.14018 1 1 1 nc
deba@2223
   230
70 0 1.14018 1 1 1 nc
deba@2223
   231
60 90 1.14018 1 1 1 nc
deba@2223
   232
60 80 1.14018 1 1 1 nc
deba@2223
   233
60 70 1.14018 1 1 1 nc
deba@2223
   234
60 60 1.14018 1 1 1 nc
deba@2223
   235
60 50 1.14018 1 1 1 nc
deba@2223
   236
60 40 1.14018 1 1 1 nc
deba@2223
   237
60 30 1.14018 1 1 1 nc
deba@2223
   238
60 20 1.14018 1 1 1 nc
deba@2223
   239
60 10 1.14018 1 1 1 nc
deba@2223
   240
60 0 1.14018 1 1 1 nc
deba@2223
   241
50 90 1.14018 1 1 1 nc
deba@2223
   242
50 80 1.14018 1 1 1 nc
deba@2223
   243
50 70 1.14018 1 1 1 nc
deba@2223
   244
50 60 1.14018 1 1 1 nc
deba@2223
   245
50 50 1.14018 1 1 1 nc
deba@2223
   246
50 40 1.14018 1 1 1 nc
deba@2223
   247
50 30 1.14018 1 1 1 nc
deba@2223
   248
50 20 1.14018 1 1 1 nc
deba@2223
   249
50 10 1.14018 1 1 1 nc
deba@2223
   250
50 0 1.14018 1 1 1 nc
deba@2223
   251
40 90 1.14018 1 1 1 nc
deba@2223
   252
40 80 1.14018 1 1 1 nc
deba@2223
   253
40 70 1.14018 1 1 1 nc
deba@2223
   254
40 60 1.14018 1 1 1 nc
deba@2223
   255
40 50 1.14018 1 1 1 nc
deba@2223
   256
40 40 1.14018 1 1 1 nc
deba@2223
   257
40 30 1.14018 1 1 1 nc
deba@2223
   258
40 20 1.14018 1 1 1 nc
deba@2223
   259
40 10 1.14018 1 1 1 nc
deba@2223
   260
40 0 1.14018 1 1 1 nc
deba@2223
   261
30 90 1.14018 1 1 1 nc
deba@2223
   262
30 80 1.14018 1 1 1 nc
deba@2223
   263
30 70 1.14018 1 1 1 nc
deba@2223
   264
30 60 1.14018 1 1 1 nc
deba@2223
   265
30 50 1.14018 1 1 1 nc
deba@2223
   266
30 40 1.14018 1 1 1 nc
deba@2223
   267
30 30 1.14018 1 1 1 nc
deba@2223
   268
30 20 1.14018 1 1 1 nc
deba@2223
   269
30 10 1.14018 1 1 1 nc
deba@2223
   270
30 0 1.14018 1 1 1 nc
deba@2223
   271
20 90 1.14018 1 1 1 nc
deba@2223
   272
20 80 1.14018 1 1 1 nc
deba@2223
   273
20 70 1.14018 1 1 1 nc
deba@2223
   274
20 60 1.14018 1 1 1 nc
deba@2223
   275
20 50 1.14018 1 1 1 nc
deba@2223
   276
20 40 1.14018 1 1 1 nc
deba@2223
   277
20 30 1.14018 1 1 1 nc
deba@2223
   278
20 20 1.14018 1 1 1 nc
deba@2223
   279
20 10 1.14018 1 1 1 nc
deba@2223
   280
20 0 1.14018 1 1 1 nc
deba@2223
   281
10 90 1.14018 1 1 1 nc
deba@2223
   282
10 80 1.14018 1 1 1 nc
deba@2223
   283
10 70 1.14018 1 1 1 nc
deba@2223
   284
10 60 1.14018 1 1 1 nc
deba@2223
   285
10 50 1.14018 1 1 1 nc
deba@2223
   286
10 40 1.14018 1 1 1 nc
deba@2223
   287
10 30 1.14018 1 1 1 nc
deba@2223
   288
10 20 1.14018 1 1 1 nc
deba@2223
   289
10 10 1.14018 1 1 1 nc
deba@2223
   290
10 0 1.14018 1 1 1 nc
deba@2223
   291
0 90 1.14018 1 1 1 nc
deba@2223
   292
0 80 1.14018 1 1 1 nc
deba@2223
   293
0 70 1.14018 1 1 1 nc
deba@2223
   294
0 60 1.14018 1 1 1 nc
deba@2223
   295
0 50 1.14018 1 1 1 nc
deba@2223
   296
0 40 1.14018 1 1 1 nc
deba@2223
   297
0 30 1.14018 1 1 1 nc
deba@2223
   298
0 20 1.14018 1 1 1 nc
deba@2223
   299
0 10 1.14018 1 1 1 nc
deba@2223
   300
0 0 1.14018 1 1 1 nc
deba@2223
   301
grestore
deba@2223
   302
grestore
deba@2223
   303
showpage