doc/images/strongly_connected_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 10 def
kpeter@633
    30
/arrw 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
77.1122 15 translate
kpeter@633
    51
0.585745 dup scale
kpeter@633
    52
90 rotate
kpeter@633
    53
695.963 -397.916 translate
kpeter@633
    54
%Edges:
kpeter@633
    55
gsave
kpeter@633
    56
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
    57
218.178 27.2723 moveto
kpeter@633
    58
192.373 -40.1551 188.622 -49.9556 169.228 -100.631 curveto stroke
kpeter@633
    59
newpath 164.939 -111.838 moveto 165.492 -99.2013 lineto 172.964 -102.061 lineto closepath fill
kpeter@633
    60
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
    61
44.8044 15.5841 moveto
kpeter@633
    62
119.293 20.6059 129.775 21.3125 186.25 25.1199 curveto stroke
kpeter@633
    63
newpath 198.223 25.927 moveto 186.519 21.1289 lineto 185.981 29.1108 lineto closepath fill
kpeter@633
    64
2 setlinewidth 1 0 0 setrgbcolor newpath
kpeter@633
    65
218.178 27.2723 moveto
kpeter@633
    66
285.395 -87.4449 290.763 -96.6058 348.102 -194.464 curveto stroke
kpeter@633
    67
newpath 354.169 -204.818 moveto 344.651 -196.487 lineto 351.554 -192.442 lineto closepath fill
kpeter@633
    68
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
    69
157.79 -130.517 moveto
kpeter@633
    70
108.71 -67.0521 102.27 -58.7243 64.3804 -9.72954 curveto stroke
kpeter@633
    71
newpath 57.0394 -0.236898 moveto 67.5446 -7.28254 lineto 61.2162 -12.1765 lineto closepath fill
kpeter@633
    72
2 setlinewidth 1 0 0 setrgbcolor newpath
kpeter@633
    73
-105.193 -261.035 moveto
kpeter@633
    74
-35.6576 -132.801 -30.5923 -123.459 29.5506 -12.5464 curveto stroke
kpeter@633
    75
newpath 35.2708 -1.99743 moveto 33.0669 -14.4531 lineto 26.0343 -10.6397 lineto closepath fill
kpeter@633
    76
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
    77
-465.576 -42.8564 moveto
kpeter@633
    78
-559.078 -25.5413 -569.47 -23.6169 -644.498 -9.72286 curveto stroke
kpeter@633
    79
newpath -656.297 -7.5378 moveto -643.77 -5.78973 lineto -645.226 -13.656 lineto closepath fill
kpeter@633
    80
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
    81
-574.666 -153.893 moveto
kpeter@633
    82
-528.842 -107.252 -521.515 -99.794 -488.002 -65.683 curveto stroke
kpeter@633
    83
newpath -479.592 -57.123 moveto -485.149 -68.4863 lineto -490.856 -62.8797 lineto closepath fill
kpeter@633
    84
2 setlinewidth 1 0 0 setrgbcolor newpath
kpeter@633
    85
-490.901 120.777 moveto
kpeter@633
    86
-480.122 51.1328 -478.519 40.7713 -470.47 -11.2329 curveto stroke
kpeter@633
    87
newpath -468.635 -23.0917 moveto -474.423 -11.8447 lineto -466.517 -10.6212 lineto closepath fill
kpeter@633
    88
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
    89
-675.963 -3.89604 moveto
kpeter@633
    90
-632.116 -68.8235 -626.228 -77.5422 -592.575 -127.374 curveto stroke
kpeter@633
    91
newpath -585.859 -137.319 moveto -595.89 -129.612 lineto -589.26 -125.135 lineto closepath fill
kpeter@633
    92
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
    93
-490.901 120.777 moveto
kpeter@633
    94
-435.445 215.844 -430.107 224.995 -384.3 303.522 curveto stroke
kpeter@633
    95
newpath -378.253 313.887 moveto -380.845 301.507 lineto -387.755 305.537 lineto closepath fill
kpeter@633
    96
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
    97
-266.879 114.933 moveto
kpeter@633
    98
-367.067 117.547 -377.642 117.822 -458.912 119.943 curveto stroke
kpeter@633
    99
newpath -470.908 120.255 moveto -458.807 123.941 lineto -459.016 115.944 lineto closepath fill
kpeter@633
   100
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
   101
-368.176 331.163 moveto
kpeter@633
   102
-322.511 233.685 -318.018 224.095 -280.454 143.911 curveto stroke
kpeter@633
   103
newpath -275.364 133.044 moveto -284.076 142.214 lineto -276.832 145.608 lineto closepath fill
kpeter@633
   104
2 setlinewidth 1 0 0 setrgbcolor newpath
kpeter@633
   105
-266.879 114.933 moveto
kpeter@633
   106
-224.004 235.52 -220.448 245.52 -184.094 347.765 curveto stroke
kpeter@633
   107
newpath -180.074 359.072 moveto -180.325 346.425 lineto -187.863 349.105 lineto closepath fill
kpeter@633
   108
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
   109
-251.294 -335.059 moveto
kpeter@633
   110
-189.25 -303.624 -179.902 -298.887 -133.738 -275.498 curveto stroke
kpeter@633
   111
newpath -123.034 -270.074 moveto -131.93 -279.066 lineto -135.546 -271.93 lineto closepath fill
kpeter@633
   112
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
   113
-389.604 -136.361 moveto
kpeter@633
   114
-327.15 -226.083 -321.098 -234.777 -269.576 -308.795 curveto stroke
kpeter@633
   115
newpath -262.72 -318.644 moveto -272.859 -311.081 lineto -266.293 -306.51 lineto closepath fill
kpeter@633
   116
2 setlinewidth 1 0 0 setrgbcolor newpath
kpeter@633
   117
5.84406 175.322 moveto
kpeter@633
   118
-76.0754 267.926 -83.1051 275.873 -152.172 353.948 curveto stroke
kpeter@633
   119
newpath -160.122 362.936 moveto -149.176 356.598 lineto -155.168 351.298 lineto closepath fill
kpeter@633
   120
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
   121
169.478 311.683 moveto
kpeter@633
   122
96.8003 251.119 88.6819 244.353 30.4273 195.808 curveto stroke
kpeter@633
   123
newpath 21.2086 188.126 moveto 27.8666 198.881 lineto 32.988 192.735 lineto closepath fill
kpeter@633
   124
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
   125
342.851 111.037 moveto
kpeter@633
   126
263.766 202.563 256.831 210.589 190.4 287.47 curveto stroke
kpeter@633
   127
newpath 182.554 296.55 moveto 193.427 290.085 lineto 187.373 284.855 lineto closepath fill
kpeter@633
   128
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
   129
5.84406 175.322 moveto
kpeter@633
   130
163.16 145.314 173.605 143.321 311.418 117.033 curveto stroke
kpeter@633
   131
newpath 323.205 114.784 moveto 310.668 113.104 lineto 312.167 120.962 lineto closepath fill
kpeter@633
   132
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
   133
342.851 111.037 moveto
kpeter@633
   134
497.255 2.58683 505.964 -3.53033 643.932 -100.436 curveto stroke
kpeter@633
   135
newpath 653.752 -107.334 moveto 641.633 -103.71 lineto 646.231 -97.163 lineto closepath fill
kpeter@633
   136
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
   137
364.28 -222.074 moveto
kpeter@633
   138
354.298 -66.9063 353.616 -56.2971 344.905 79.1029 curveto stroke
kpeter@633
   139
newpath 344.135 91.0781 moveto 348.897 79.3597 lineto 340.914 78.8461 lineto closepath fill
kpeter@633
   140
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
   141
670.118 -118.829 moveto
kpeter@633
   142
528.037 -166.793 517.967 -170.192 394.599 -211.839 curveto stroke
kpeter@633
   143
newpath 383.229 -215.677 moveto 393.32 -208.049 lineto 395.878 -215.629 lineto closepath fill
kpeter@633
   144
2 setlinewidth 1 0 0 setrgbcolor newpath
kpeter@633
   145
-105.193 -261.035 moveto
kpeter@633
   146
118.401 -242.479 129.015 -241.598 332.39 -224.721 curveto stroke
kpeter@633
   147
newpath 344.348 -223.728 moveto 332.72 -228.707 lineto 332.059 -220.734 lineto closepath fill
kpeter@633
   148
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
   149
-105.193 -261.035 moveto
kpeter@633
   150
-160.867 -161.176 -166.028 -151.918 -212.336 -68.858 curveto stroke
kpeter@633
   151
newpath -218.179 -58.3769 moveto -208.842 -66.9102 lineto -215.829 -70.8058 lineto closepath fill
kpeter@633
   152
2 setlinewidth 0 0 1 setrgbcolor newpath
kpeter@633
   153
-227.918 -40.9084 moveto
kpeter@633
   154
-298.35 -82.4884 -307.42 -87.8432 -362.048 -120.093 curveto stroke
kpeter@633
   155
newpath -372.381 -126.193 moveto -364.081 -116.648 lineto -360.014 -123.537 lineto closepath fill
kpeter@633
   156
grestore
kpeter@633
   157
%Nodes:
kpeter@633
   158
gsave
kpeter@633
   159
-389.604 -136.361 20 0 1 0 nc
kpeter@633
   160
-227.918 -40.9084 20 0 1 0 nc
kpeter@633
   161
-105.193 -261.035 20 0 1 0 nc
kpeter@633
   162
364.28 -222.074 20 1 1 0 nc
kpeter@633
   163
670.118 -118.829 20 1 1 0 nc
kpeter@633
   164
342.851 111.037 20 1 1 0 nc
kpeter@633
   165
5.84406 175.322 20 1 1 0 nc
kpeter@633
   166
169.478 311.683 20 1 1 0 nc
kpeter@633
   167
-173.374 377.916 20 1 0 1 nc
kpeter@633
   168
-251.294 -335.059 20 0 1 0 nc
kpeter@633
   169
-266.879 114.933 20 0 0 0 nc
kpeter@633
   170
-368.176 331.163 20 0 0 0 nc
kpeter@633
   171
-490.901 120.777 20 0 0 0 nc
kpeter@633
   172
-574.666 -153.893 20 1 0 0 nc
kpeter@633
   173
-675.963 -3.89604 20 1 0 0 nc
kpeter@633
   174
-465.576 -42.8564 20 1 0 0 nc
kpeter@633
   175
44.8044 15.5841 20 0 0 1 nc
kpeter@633
   176
157.79 -130.517 20 0 0 1 nc
kpeter@633
   177
218.178 27.2723 20 0 0 1 nc
kpeter@633
   178
grestore
kpeter@633
   179
grestore
kpeter@633
   180
showpage