doc/images/matching.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.
alpar@865
     1
%!PS-Adobe-2.0 EPSF-2.0
alpar@865
     2
%%Creator: LEMON, graphToEps()
alpar@865
     3
%%CreationDate: Sun Mar 14 09:08:34 2010
alpar@865
     4
%%BoundingBox: -353 -264 559 292
alpar@865
     5
%%EndComments
alpar@865
     6
/lb { setlinewidth setrgbcolor newpath moveto
alpar@865
     7
      4 2 roll 1 index 1 index curveto stroke } bind def
alpar@865
     8
/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
alpar@865
     9
/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
alpar@865
    10
/sq { newpath 2 index 1 index add 2 index 2 index add moveto
alpar@865
    11
      2 index 1 index sub 2 index 2 index add lineto
alpar@865
    12
      2 index 1 index sub 2 index 2 index sub lineto
alpar@865
    13
      2 index 1 index add 2 index 2 index sub lineto
alpar@865
    14
      closepath pop pop pop} bind def
alpar@865
    15
/di { newpath 2 index 1 index add 2 index moveto
alpar@865
    16
      2 index             2 index 2 index add lineto
alpar@865
    17
      2 index 1 index sub 2 index             lineto
alpar@865
    18
      2 index             2 index 2 index sub lineto
alpar@865
    19
      closepath pop pop pop} bind def
alpar@865
    20
/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
alpar@865
    21
     setrgbcolor 1.1 div c fill
alpar@865
    22
   } bind def
alpar@865
    23
/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
alpar@865
    24
     setrgbcolor 1.1 div sq fill
alpar@865
    25
   } bind def
alpar@865
    26
/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
alpar@865
    27
     setrgbcolor 1.1 div di fill
alpar@865
    28
   } bind def
alpar@865
    29
/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
alpar@865
    30
  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub
alpar@865
    31
  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto
alpar@865
    32
  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke
alpar@865
    33
  5 index 5 index 5 index c fill
alpar@865
    34
  setrgbcolor 1.1 div c fill
alpar@865
    35
  } bind def
alpar@865
    36
/nmale {
alpar@865
    37
  0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth
alpar@865
    38
  newpath 5 index 5 index moveto
alpar@865
    39
  5 index 4 index 1 mul 1.5 mul add
alpar@865
    40
  5 index 5 index 3 sqrt 1.5 mul mul add
alpar@865
    41
  1 index 1 index lineto
alpar@865
    42
  1 index 1 index 7 index sub moveto
alpar@865
    43
  1 index 1 index lineto
alpar@865
    44
  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto
alpar@865
    45
  stroke
alpar@865
    46
  5 index 5 index 5 index c fill
alpar@865
    47
  setrgbcolor 1.1 div c fill
alpar@865
    48
  } bind def
alpar@865
    49
/arrl 1 def
alpar@865
    50
/arrw 0.3 def
alpar@865
    51
/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
alpar@865
    52
/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
alpar@865
    53
       /w exch def /len exch def
alpar@865
    54
       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
alpar@865
    55
       len w sub arrl sub dx dy lrl
alpar@865
    56
       arrw dy dx neg lrl
alpar@865
    57
       dx arrl w add mul dy w 2 div arrw add mul sub
alpar@865
    58
       dy arrl w add mul dx w 2 div arrw add mul add rlineto
alpar@865
    59
       dx arrl w add mul neg dy w 2 div arrw add mul sub
alpar@865
    60
       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
alpar@865
    61
       arrw dy dx neg lrl
alpar@865
    62
       len w sub arrl sub neg dx dy lrl
alpar@865
    63
       closepath fill } bind def
alpar@865
    64
/cshow { 2 index 2 index moveto dup stringwidth pop
alpar@865
    65
         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
alpar@865
    66
alpar@865
    67
gsave
alpar@865
    68
%Arcs:
alpar@865
    69
gsave
alpar@865
    70
140.321 266.249 -327.729 150.06 0 0 0 4.99223 l
alpar@865
    71
82.1207 -238.726 -245.288 -110.743 0 0 0 4.99223 l
alpar@865
    72
336.635 -229.036 533.603 13.109 0 0 0 4.99223 l
alpar@865
    73
53.8598 -45.8071 -245.288 -110.743 0 0 0 4.99223 l
alpar@865
    74
-75.5617 118.579 -327.729 150.06 0 0 0 4.99223 l
alpar@865
    75
-327.729 150.06 -245.288 -110.743 1 0 0 11.9813 l
alpar@865
    76
533.603 13.109 218.184 -84.2955 0 0 0 4.99223 l
alpar@865
    77
39.87 175.035 141.163 67.2575 0 0 0 4.99223 l
alpar@865
    78
53.8598 -45.8071 -75.5617 118.579 0 0 0 4.99223 l
alpar@865
    79
-102.406 -141.267 82.1207 -238.726 0 0 0 4.99223 l
alpar@865
    80
399.144 166.894 533.603 13.109 1 0 0 11.9813 l
alpar@865
    81
39.87 175.035 140.321 266.249 1 0 0 11.9813 l
alpar@865
    82
399.144 166.894 140.321 266.249 0 0 0 4.99223 l
alpar@865
    83
399.144 166.894 141.163 67.2575 0 0 0 4.99223 l
alpar@865
    84
53.8598 -45.8071 204.765 -173.77 0 0 0 4.99223 l
alpar@865
    85
82.1207 -238.726 204.765 -173.77 0 0 0 4.99223 l
alpar@865
    86
258.227 61.658 399.144 166.894 0 0 0 4.99223 l
alpar@865
    87
53.8598 -45.8071 -102.406 -141.267 1 0 0 11.9813 l
alpar@865
    88
175.073 -37.4477 141.163 67.2575 0 0 0 4.99223 l
alpar@865
    89
258.227 61.658 380 0 0 0 0 4.99223 l
alpar@865
    90
34.6739 40.8267 -75.5617 118.579 1 0 0 11.9813 l
alpar@865
    91
380 0 533.603 13.109 0 0 0 4.99223 l
alpar@865
    92
175.073 -37.4477 380 0 0 0 0 4.99223 l
alpar@865
    93
218.184 -84.2955 204.765 -173.77 0 0 0 4.99223 l
alpar@865
    94
53.8598 -45.8071 34.6739 40.8267 0 0 0 4.99223 l
alpar@865
    95
167.905 -213.988 82.1207 -238.726 1 0 0 11.9813 l
alpar@865
    96
336.635 -229.036 204.765 -173.77 1 0 0 11.9813 l
alpar@865
    97
336.635 -229.036 167.905 -213.988 0 0 0 4.99223 l
alpar@865
    98
329.08 -26.3098 218.184 -84.2955 0 0 0 4.99223 l
alpar@865
    99
39.87 175.035 -75.5617 118.579 0 0 0 4.99223 l
alpar@865
   100
53.8598 -45.8071 175.073 -37.4477 0 0 0 4.99223 l
alpar@865
   101
34.6739 40.8267 141.163 67.2575 0 0 0 4.99223 l
alpar@865
   102
258.227 61.658 141.163 67.2575 1 0 0 11.9813 l
alpar@865
   103
175.073 -37.4477 218.184 -84.2955 1 0 0 11.9813 l
alpar@865
   104
380 0 329.08 -26.3098 1 0 0 11.9813 l
alpar@865
   105
grestore
alpar@865
   106
%Nodes:
alpar@865
   107
gsave
alpar@865
   108
-245.288 -110.743 14.9767 1 1 1 nc
alpar@865
   109
204.765 -173.77 14.9767 1 1 1 nc
alpar@865
   110
-327.729 150.06 14.9767 1 1 1 nc
alpar@865
   111
-75.5617 118.579 14.9767 1 1 1 nc
alpar@865
   112
218.184 -84.2955 14.9767 1 1 1 nc
alpar@865
   113
140.321 266.249 14.9767 1 1 1 nc
alpar@865
   114
141.163 67.2575 14.9767 1 1 1 nc
alpar@865
   115
82.1207 -238.726 14.9767 1 1 1 nc
alpar@865
   116
329.08 -26.3098 14.9767 1 1 1 nc
alpar@865
   117
-102.406 -141.267 14.9767 1 1 1 nc
alpar@865
   118
533.603 13.109 14.9767 1 1 1 nc
alpar@865
   119
167.905 -213.988 14.9767 1 1 1 nc
alpar@865
   120
336.635 -229.036 14.9767 1 1 1 nc
alpar@865
   121
380 0 14.9767 1 1 1 nc
alpar@865
   122
399.144 166.894 14.9767 1 1 1 nc
alpar@865
   123
34.6739 40.8267 14.9767 1 1 1 nc
alpar@865
   124
39.87 175.035 14.9767 1 1 1 nc
alpar@865
   125
175.073 -37.4477 14.9767 1 1 1 nc
alpar@865
   126
53.8598 -45.8071 14.9767 1 1 1 nc
alpar@865
   127
258.227 61.658 14.9767 1 1 1 nc
alpar@865
   128
grestore
alpar@865
   129
grestore
alpar@865
   130
showpage