doc/images/edge_biconnected_components.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 15 Mar 2011 19:32:21 +0100
changeset 1047 ddd3c0d3d9bf
parent 633 7c12061bd271
child 1213 4e8787627db3
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: Fri Nov  4 13:47:12 2005
     4 %%BoundingBox: 0 0 842 596
     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 /arrl 1 def
    30 /arrw 0.3 def
    31 /lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
    32 /arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
    33        /w exch def /len exch def
    34        newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
    35        len w sub arrl sub dx dy lrl
    36        arrw dy dx neg lrl
    37        dx arrl w add mul dy w 2 div arrw add mul sub
    38        dy arrl w add mul dx w 2 div arrw add mul add rlineto
    39        dx arrl w add mul neg dy w 2 div arrw add mul sub
    40        dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
    41        arrw dy dx neg lrl
    42        len w sub arrl sub neg dx dy lrl
    43        closepath fill } bind def
    44 /cshow { 2 index 2 index moveto dup stringwidth pop
    45          neg 2 div fosi .35 mul neg rmoveto show pop pop} def
    46 
    47 gsave
    48 90 rotate
    49 0 -842 translate
    50 71.0944 15 translate
    51 0.434694 dup scale
    52 90 rotate
    53 860.856 -588.349 translate
    54 %Edges:
    55 gsave
    56 574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 2 lb
    57 694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 2 lb
    58 280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 2 lb
    59 280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 2 lb
    60 212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 2 lb
    61 286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 2 lb
    62 286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 2 lb
    63 438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 2 lb
    64 438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 2 lb
    65 397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 2 lb
    66 366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 2 lb
    67 271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 2 lb
    68 271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 2 lb
    69 277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 2 lb
    70 -840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 2 lb
    71 -579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 2 lb
    72 -579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 2 lb
    73 -767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 2 lb
    74 906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 2 lb
    75 906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 2 lb
    76 986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 2 lb
    77 -470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 2 lb
    78 422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 2 lb
    79 422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 2 lb
    80 422.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 2 lb
    81 -5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 2 lb
    82 329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 2 lb
    83 -67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 2 lb
    84 762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 2 lb
    85 762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 2 lb
    86 526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 2 lb
    87 730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 2 lb
    88 415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 2 lb
    89 -67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 2 lb
    90 -67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 2 lb
    91 -309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 2 lb
    92 -323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 2 lb
    93 -26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 2 lb
    94 -26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 2 lb
    95 -26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 2 lb
    96 -26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 2 lb
    97 116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 2 lb
    98 -262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 2 lb
    99 -262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 2 lb
   100 -13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 2 lb
   101 -180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 1 2 lb
   102 -180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 1 2 lb
   103 -416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 2 lb
   104 -416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 2 lb
   105 -132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 2 lb
   106 670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 2 lb
   107 670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 2 lb
   108 588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 2 lb
   109 -689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 1 2 lb
   110 -689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 1 2 lb
   111 grestore
   112 %Nodes:
   113 gsave
   114 -567.302 43.6423 20 0 0 0 nc
   115 -689.204 -237.261 20 0 0 0 nc
   116 924.667 409.347 20 0 0 1 nc
   117 588.113 544.499 20 0 0 1 nc
   118 670.264 274.195 20 0 0 1 nc
   119 -371.2 568.349 20 1 1 0 nc
   120 -132.697 451.748 20 1 1 0 nc
   121 -416.25 345.746 20 1 1 0 nc
   122 -180.397 245.045 20 1 1 0 nc
   123 -13.4452 133.743 20 1 1 0 nc
   124 -262.548 107.243 20 1 1 0 nc
   125 201.208 38.3422 20 1 1 0 nc
   126 116.407 -173.66 20 1 1 0 nc
   127 -26.6953 -19.9585 20 1 1 0 nc
   128 -539.894 -262.64 20 0 0.5 0 nc
   129 -323.543 -433.964 20 0 0.5 0 nc
   130 -309.657 -57.9033 20 0 0.5 0 nc
   131 -67.9734 -347.42 20 0 0.5 0 nc
   132 415.393 -289.516 20 0.5 0 0 nc
   133 730.084 -307.139 20 0.5 0 0 nc
   134 526.164 32.7279 20 0.5 0 0 nc
   135 762.812 -17.6227 20 0.5 0 0 nc
   136 -67.9734 319.727 20 0.5 0 0 nc
   137 329.797 314.692 20 0.5 0 0 nc
   138 -5.03507 561.41 20 0.5 0 0 nc
   139 422.945 521.129 20 0.5 0 0 nc
   140 -470.779 158.605 20 0 1 1 nc
   141 986.873 -115.807 20 0.5 0 0 nc
   142 906.312 201.403 20 0.5 0 0 nc
   143 -767.847 113.289 20 0 1 1 nc
   144 -579.033 445.603 20 0 1 1 nc
   145 -840.856 -246.718 20 1 0 1 nc
   146 206.221 -205.967 20 0 0 0.5 nc
   147 277.311 -252.33 20 0 0 0.5 nc
   148 271.13 -175.058 20 0 0 0.5 nc
   149 366.947 -110.15 20 0 0 0.5 nc
   150 397.855 -196.694 20 0 0 0.5 nc
   151 438.037 -88.514 20 0 0 0.5 nc
   152 286.584 -48.3327 20 0 0 0.5 nc
   153 212.403 -23.6057 20 0 0 0.5 nc
   154 280.402 10.3938 20 0 0 0.5 nc
   155 694.579 115.483 20 1 0 0 nc
   156 574.035 177.301 20 0 1 0 nc
   157 grestore
   158 grestore
   159 showpage