doc/images/grid_graph.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 25 Apr 2009 02:12:41 +0200
changeset 623 7c1324b35d89
permissions -rw-r--r--
Modify the interface of Suurballe (#266, #181)

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