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