doc/images/grid_graph.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
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