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