doc/images/node_biconnected_components.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:26:13 +0100
changeset 872 fa6f37d7a25b
parent 633 7c12061bd271
child 1213 4e8787627db3
permissions -rw-r--r--
Entirely rework CapacityScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster (up to 2-5 times faster on large graphs).
- Handle GEQ supply type (LEQ is not supported).
- Handle negative costs for arcs of finite capacity.
(Note that this algorithm cannot handle arcs of negative cost
and infinite upper bound, thus it returns UNBOUNDED if such
an arc exists.)
- Extend the documentation.
kpeter@633
     1
%!PS-Adobe-2.0 EPSF-2.0
kpeter@633
     2
%%Creator: LEMON, graphToEps()
kpeter@633
     3
%%CreationDate: Fri Nov  4 13:47:12 2005
alpar@634
     4
%%BoundingBox: 0 0 842 596
kpeter@633
     5
%%EndComments
kpeter@633
     6
/lb { setlinewidth setrgbcolor newpath moveto
kpeter@633
     7
      4 2 roll 1 index 1 index curveto stroke } bind def
kpeter@633
     8
/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
kpeter@633
     9
/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
kpeter@633
    10
/sq { newpath 2 index 1 index add 2 index 2 index add moveto
kpeter@633
    11
      2 index 1 index sub 2 index 2 index add lineto
kpeter@633
    12
      2 index 1 index sub 2 index 2 index sub lineto
kpeter@633
    13
      2 index 1 index add 2 index 2 index sub lineto
kpeter@633
    14
      closepath pop pop pop} bind def
kpeter@633
    15
/di { newpath 2 index 1 index add 2 index moveto
kpeter@633
    16
      2 index             2 index 2 index add lineto
kpeter@633
    17
      2 index 1 index sub 2 index             lineto
kpeter@633
    18
      2 index             2 index 2 index sub lineto
kpeter@633
    19
      closepath pop pop pop} bind def
kpeter@633
    20
/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
kpeter@633
    21
     setrgbcolor 1.1 div c fill
kpeter@633
    22
   } bind def
kpeter@633
    23
/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill
kpeter@633
    24
     setrgbcolor 1.1 div sq fill
kpeter@633
    25
   } bind def
kpeter@633
    26
/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill
kpeter@633
    27
     setrgbcolor 1.1 div di fill
kpeter@633
    28
   } bind def
kpeter@633
    29
/arrl 1 def
kpeter@633
    30
/arrw 0.3 def
kpeter@633
    31
/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
kpeter@633
    32
/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
kpeter@633
    33
       /w exch def /len exch def
kpeter@633
    34
       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
kpeter@633
    35
       len w sub arrl sub dx dy lrl
kpeter@633
    36
       arrw dy dx neg lrl
kpeter@633
    37
       dx arrl w add mul dy w 2 div arrw add mul sub
kpeter@633
    38
       dy arrl w add mul dx w 2 div arrw add mul add rlineto
kpeter@633
    39
       dx arrl w add mul neg dy w 2 div arrw add mul sub
kpeter@633
    40
       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
kpeter@633
    41
       arrw dy dx neg lrl
kpeter@633
    42
       len w sub arrl sub neg dx dy lrl
kpeter@633
    43
       closepath fill } bind def
kpeter@633
    44
/cshow { 2 index 2 index moveto dup stringwidth pop
kpeter@633
    45
         neg 2 div fosi .35 mul neg rmoveto show pop pop} def
kpeter@633
    46
kpeter@633
    47
gsave
alpar@634
    48
90 rotate
alpar@634
    49
0 -842 translate
kpeter@633
    50
71.0944 15 translate
kpeter@633
    51
0.434694 dup scale
kpeter@633
    52
90 rotate
kpeter@633
    53
860.856 -588.349 translate
kpeter@633
    54
%Edges:
kpeter@633
    55
gsave
kpeter@633
    56
574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 5 lb
kpeter@633
    57
694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 5 lb
kpeter@633
    58
280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 5 lb
kpeter@633
    59
280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 5 lb
kpeter@633
    60
212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 5 lb
kpeter@633
    61
286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 5 lb
kpeter@633
    62
286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 5 lb
kpeter@633
    63
438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 5 lb
kpeter@633
    64
438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 5 lb
kpeter@633
    65
397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 5 lb
kpeter@633
    66
366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 5 lb
kpeter@633
    67
271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 5 lb
kpeter@633
    68
271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 5 lb
kpeter@633
    69
277.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 5 lb
kpeter@633
    70
-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 5 lb
kpeter@633
    71
-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 5 lb
kpeter@633
    72
-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 5 lb
kpeter@633
    73
-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 5 lb
kpeter@633
    74
906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 5 lb
kpeter@633
    75
906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 5 lb
kpeter@633
    76
986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 5 lb
kpeter@633
    77
-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 5 lb
kpeter@633
    78
422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 5 lb
kpeter@633
    79
422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 5 lb
kpeter@633
    80
422.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 5 lb
kpeter@633
    81
-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 5 lb
kpeter@633
    82
329.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 5 lb
kpeter@633
    83
-67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 5 lb
kpeter@633
    84
762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 5 lb
kpeter@633
    85
762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 5 lb
kpeter@633
    86
526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 5 lb
kpeter@633
    87
730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 5 lb
kpeter@633
    88
415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 5 lb
kpeter@633
    89
-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 5 lb
kpeter@633
    90
-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 5 lb
kpeter@633
    91
-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 5 lb
kpeter@633
    92
-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 5 lb
kpeter@633
    93
-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 5 lb
kpeter@633
    94
-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 5 lb
kpeter@633
    95
-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 5 lb
kpeter@633
    96
-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 5 lb
kpeter@633
    97
116.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 5 lb
kpeter@633
    98
-262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 5 lb
kpeter@633
    99
-262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 5 lb
kpeter@633
   100
-13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 5 lb
kpeter@633
   101
-180.397 245.045 -140.307 344.649 -132.697 451.748 0 1 1 5 lb
kpeter@633
   102
-180.397 245.045 -172.787 352.144 -132.697 451.748 0 1 1 5 lb
kpeter@633
   103
-416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 5 lb
kpeter@633
   104
-416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 5 lb
kpeter@633
   105
-132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 5 lb
kpeter@633
   106
670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 5 lb
kpeter@633
   107
670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 5 lb
kpeter@633
   108
588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 5 lb
kpeter@633
   109
-689.204 -237.261 -612.964 -103.444 -567.302 43.6423 0 0 0 5 lb
kpeter@633
   110
-689.204 -237.261 -643.542 -90.1744 -567.302 43.6423 0 0 0 5 lb
kpeter@633
   111
grestore
kpeter@633
   112
%Nodes:
kpeter@633
   113
gsave
kpeter@633
   114
-567.302 43.6423 20 0 0 1 nc
kpeter@633
   115
-689.204 -237.261 20 0 0 1 nc
kpeter@633
   116
924.667 409.347 20 0 0 1 nc
kpeter@633
   117
588.113 544.499 20 0 0 1 nc
kpeter@633
   118
670.264 274.195 20 1 0 0 nc
kpeter@633
   119
-371.2 568.349 20 0 0 1 nc
kpeter@633
   120
-132.697 451.748 20 1 0 0 nc
kpeter@633
   121
-416.25 345.746 20 0 0 1 nc
kpeter@633
   122
-180.397 245.045 20 1 0 0 nc
kpeter@633
   123
-13.4452 133.743 20 0 0 1 nc
kpeter@633
   124
-262.548 107.243 20 0 0 1 nc
kpeter@633
   125
201.208 38.3422 20 0 0 1 nc
kpeter@633
   126
116.407 -173.66 20 0 0 1 nc
kpeter@633
   127
-26.6953 -19.9585 20 1 0 0 nc
kpeter@633
   128
-539.894 -262.64 20 0 0 1 nc
kpeter@633
   129
-323.543 -433.964 20 0 0 1 nc
kpeter@633
   130
-309.657 -57.9033 20 1 0 0 nc
kpeter@633
   131
-67.9734 -347.42 20 1 0 0 nc
kpeter@633
   132
415.393 -289.516 20 1 0 0 nc
kpeter@633
   133
730.084 -307.139 20 0 0 1 nc
kpeter@633
   134
526.164 32.7279 20 1 0 0 nc
kpeter@633
   135
762.812 -17.6227 20 1 0 0 nc
kpeter@633
   136
-67.9734 319.727 20 0 0 1 nc
kpeter@633
   137
329.797 314.692 20 0 0 1 nc
kpeter@633
   138
-5.03507 561.41 20 0 0 1 nc
kpeter@633
   139
422.945 521.129 20 0 0 1 nc
kpeter@633
   140
-470.779 158.605 20 1 0 0 nc
kpeter@633
   141
986.873 -115.807 20 0 0 1 nc
kpeter@633
   142
906.312 201.403 20 0 0 1 nc
kpeter@633
   143
-767.847 113.289 20 1 0 0 nc
kpeter@633
   144
-579.033 445.603 20 0 0 1 nc
kpeter@633
   145
-840.856 -246.718 20 0 0 1 nc
kpeter@633
   146
206.221 -205.967 20 0 0 1 nc
kpeter@633
   147
277.311 -252.33 20 0 0 1 nc
kpeter@633
   148
271.13 -175.058 20 1 0 0 nc
kpeter@633
   149
366.947 -110.15 20 1 0 0 nc
kpeter@633
   150
397.855 -196.694 20 0 0 1 nc
kpeter@633
   151
438.037 -88.514 20 0 0 1 nc
kpeter@633
   152
286.584 -48.3327 20 1 0 0 nc
kpeter@633
   153
212.403 -23.6057 20 0 0 1 nc
kpeter@633
   154
280.402 10.3938 20 0 0 1 nc
kpeter@633
   155
694.579 115.483 20 0 0 1 nc
kpeter@633
   156
574.035 177.301 20 0 0 1 nc
kpeter@633
   157
grestore
kpeter@633
   158
grestore
kpeter@633
   159
showpage