doc/images/grid_graph.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 656 e6927fe719e6
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

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