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