doc/images/planar.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 15 Mar 2011 19:32:21 +0100
changeset 1047 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 %%Creator: LEMON, graphToEps()
     3 %%CreationDate: Fri Oct 19 18:32:32 2007
     4 %%BoundingBox: 0 0 596 842
     5 %%DocumentPaperSizes: a4
     6 %%EndComments
     7 /lb { setlinewidth setrgbcolor newpath moveto
     8       4 2 roll 1 index 1 index curveto stroke } bind def
     9 /l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
    10 /c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
    11 /sq { newpath 2 index 1 index add 2 index 2 index add moveto
    12       2 index 1 index sub 2 index 2 index add lineto
    13       2 index 1 index sub 2 index 2 index sub lineto
    14       2 index 1 index add 2 index 2 index sub lineto
    15       closepath pop pop pop} bind def
    16 /di { newpath 2 index 1 index add 2 index moveto
    17       2 index             2 index 2 index add lineto
    18       2 index 1 index sub 2 index             lineto
    19       2 index             2 index 2 index sub lineto
    20       closepath pop pop pop} bind def
    21 /nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
    22      setrgbcolor 1.1 div c fill
    23    } bind def
    24 /nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
    25      setrgbcolor 1.1 div sq fill
    26    } bind def
    27 /ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
    28      setrgbcolor 1.1 div di fill
    29    } bind def
    30 /nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
    31   newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
    32   lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
    33   5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
    34   5 index 5 index 5 index c fill
    35   setrgbcolor 1.1 div c fill
    36   } bind def
    37 /nmale {
    38   0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
    39   newpath 5 index 5 index moveto
    40   5 index 4 index 1 mul 1.5 mul add
    41   5 index 5 index 3 sqrt 1.5 mul mul add
    42   1 index 1 index lineto
    43   1 index 1 index 7 index sub moveto
    44   1 index 1 index lineto
    45   exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
    46   stroke
    47   5 index 5 index 5 index c fill
    48   setrgbcolor 1.1 div c fill
    49   } bind def
    50 /arrl 1 def
    51 /arrw 0.3 def
    52 /lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
    53 /arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
    54        /w exch def /len exch def
    55        newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
    56        len w sub arrl sub dx dy lrl
    57        arrw dy dx neg lrl
    58        dx arrl w add mul dy w 2 div arrw add mul sub
    59        dy arrl w add mul dx w 2 div arrw add mul add rlineto
    60        dx arrl w add mul neg dy w 2 div arrw add mul sub
    61        dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
    62        arrw dy dx neg lrl
    63        len w sub arrl sub neg dx dy lrl
    64        closepath fill } bind def
    65 /cshow { 2 index 2 index moveto dup stringwidth pop
    66          neg 2 div fosi .35 mul neg rmoveto show pop pop} def
    67 
    68 gsave
    69 15 138.307 translate
    70 12.7843 dup scale
    71 90 rotate
    72 0.608112 -43.6081 translate
    73 %Edges:
    74 gsave
    75 9 31 9.5 30.5 10 30 0 0 0 0.091217 lb
    76 9 31 5.5 34.5 2 38 0 0 0 0.091217 lb
    77 9 31 25.5 16 42 1 0 0 0 0.091217 lb
    78 3 40 23 20.5 43 1 0 0 0 0.091217 lb
    79 3 40 22.5 20.5 42 1 0 0 0 0.091217 lb
    80 3 40 2.5 40.5 2 41 0 0 0 0.091217 lb
    81 13 25 10.5 24.5 8 24 0 0 0 0.091217 lb
    82 13 25 12 27 11 29 0 0 0 0.091217 lb
    83 3 4 2.5 3 2 2 0 0 0 0.091217 lb
    84 3 4 4.5 3 6 2 0 0 0 0.091217 lb
    85 6 25 7 24.5 8 24 0 0 0 0.091217 lb
    86 6 25 6 24.5 6 24 0 0 0 0.091217 lb
    87 34 2 33.5 2 33 2 0 0 0 0.091217 lb
    88 34 2 35 2 36 2 0 0 0 0.091217 lb
    89 6 8 16 9 26 10 0 0 0 0.091217 lb
    90 6 8 6 10.5 6 13 0 0 0 0.091217 lb
    91 6 8 6 7.5 6 7 0 0 0 0.091217 lb
    92 26 10 27.5 8.5 29 7 0 0 0 0.091217 lb
    93 26 10 27.5 9 29 8 0 0 0 0.091217 lb
    94 10 30 10.5 29.5 11 29 0 0 0 0.091217 lb
    95 8 24 7 23.5 6 23 0 0 0 0.091217 lb
    96 8 24 8 24.5 8 25 0 0 0 0.091217 lb
    97 33 2 32.5 2 32 2 0 0 0 0.091217 lb
    98 29 7 17.5 7 6 7 0 0 0 0.091217 lb
    99 2 2 1.5 22 1 42 0 0 0 0.091217 lb
   100 2 2 3.5 2 5 2 0 0 0 0.091217 lb
   101 21 15 13.5 14.5 6 14 0 0 0 0.091217 lb
   102 21 15 21 15.5 21 16 0 0 0 0.091217 lb
   103 1 42 0.5 42.5 0 43 0 0 0 0.091217 lb
   104 1 42 1.5 41.5 2 41 0 0 0 0.091217 lb
   105 6 15 6 15.5 6 16 0 0 0 0.091217 lb
   106 6 15 6 14.5 6 14 0 0 0 0.091217 lb
   107 43 1 22 0.5 1 0 0 0 0 0.091217 lb
   108 31 2 18.5 2 6 2 0 0 0 0.091217 lb
   109 31 2 31.5 2 32 2 0 0 0 0.091217 lb
   110 6 24 6 23.5 6 23 0 0 0 0.091217 lb
   111 6 16 6 16.5 6 17 0 0 0 0.091217 lb
   112 6 23 6 20 6 17 0 0 0 0.091217 lb
   113 6 2 5.5 2 5 2 0 0 0 0.091217 lb
   114 6 2 6 4.5 6 7 0 0 0 0.091217 lb
   115 0 43 0.5 21.5 1 0 0 0 0 0.091217 lb
   116 1 1 19.5 1.5 38 2 0 0 0 0.091217 lb
   117 1 1 1 0.5 1 0 0 0 0 0.091217 lb
   118 2 38 5.5 31.5 9 25 0 0 0 0.091217 lb
   119 25 13 15.5 13 6 13 0 0 0 0.091217 lb
   120 25 13 15.5 13.5 6 14 0 0 0 0.091217 lb
   121 8 25 8.5 25 9 25 0 0 0 0.091217 lb
   122 11 29 24.5 15.5 38 2 0 0 0 0.091217 lb
   123 6 17 11.5 18 17 19 0 0 0 0.091217 lb
   124 16 23 26.5 12.5 37 2 0 0 0 0.091217 lb
   125 16 23 18.5 19.5 21 16 0 0 0 0.091217 lb
   126 36 2 36.5 2 37 2 0 0 0 0.091217 lb
   127 36 2 32.5 5 29 8 0 0 0 0.091217 lb
   128 6 13 6 13.5 6 14 0 0 0 0.091217 lb
   129 37 2 37.5 2 38 2 0 0 0 0.091217 lb
   130 21 16 19 17.5 17 19 0 0 0 0.091217 lb
   131 grestore
   132 %Nodes:
   133 gsave
   134 29 8 0.304556 1 1 1 nc
   135 2 41 0.304556 1 1 1 nc
   136 6 7 0.304556 1 1 1 nc
   137 5 2 0.304556 1 1 1 nc
   138 17 19 0.304556 1 1 1 nc
   139 21 16 0.304556 1 1 1 nc
   140 1 0 0.304556 1 1 1 nc
   141 9 25 0.304556 1 1 1 nc
   142 6 14 0.304556 1 1 1 nc
   143 42 1 0.304556 1 1 1 nc
   144 38 2 0.304556 1 1 1 nc
   145 37 2 0.304556 1 1 1 nc
   146 6 13 0.304556 1 1 1 nc
   147 36 2 0.304556 1 1 1 nc
   148 16 23 0.304556 1 1 1 nc
   149 6 17 0.304556 1 1 1 nc
   150 11 29 0.304556 1 1 1 nc
   151 8 25 0.304556 1 1 1 nc
   152 32 2 0.304556 1 1 1 nc
   153 25 13 0.304556 1 1 1 nc
   154 2 38 0.304556 1 1 1 nc
   155 1 1 0.304556 1 1 1 nc
   156 0 43 0.304556 1 1 1 nc
   157 6 2 0.304556 1 1 1 nc
   158 6 23 0.304556 1 1 1 nc
   159 6 16 0.304556 1 1 1 nc
   160 6 24 0.304556 1 1 1 nc
   161 31 2 0.304556 1 1 1 nc
   162 43 1 0.304556 1 1 1 nc
   163 6 15 0.304556 1 1 1 nc
   164 1 42 0.304556 1 1 1 nc
   165 21 15 0.304556 1 1 1 nc
   166 2 2 0.304556 1 1 1 nc
   167 29 7 0.304556 1 1 1 nc
   168 33 2 0.304556 1 1 1 nc
   169 8 24 0.304556 1 1 1 nc
   170 10 30 0.304556 1 1 1 nc
   171 26 10 0.304556 1 1 1 nc
   172 6 8 0.304556 1 1 1 nc
   173 34 2 0.304556 1 1 1 nc
   174 6 25 0.304556 1 1 1 nc
   175 3 4 0.304556 1 1 1 nc
   176 13 25 0.304556 1 1 1 nc
   177 3 40 0.304556 1 1 1 nc
   178 9 31 0.304556 1 1 1 nc
   179 grestore
   180 grestore
   181 showpage