doc/images/grid_graph.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 15 Mar 2011 19:32:21 +0100
changeset 936 ddd3c0d3d9bf
permissions -rw-r--r--
Implement the scaling Price Refinement heuristic in CostScaling (#417)
instead of Early Termination.

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