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