doc/images/bipartite_partitions.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: Tue Nov 15 16:51:43 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.6378 15 translate
kpeter@633
    51
0.389093 dup scale
kpeter@633
    52
90 rotate
kpeter@633
    53
1197.47 -613.138 translate
kpeter@633
    54
%Edges:
kpeter@633
    55
gsave
kpeter@633
    56
513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb
kpeter@633
    57
513.857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb
kpeter@633
    58
393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb
kpeter@633
    59
393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb
kpeter@633
    60
393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb
kpeter@633
    61
869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb
kpeter@633
    62
869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 2 lb
kpeter@633
    63
-82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 2 lb
kpeter@633
    64
-663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 2 lb
kpeter@633
    65
-663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 2 lb
kpeter@633
    66
-1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 2 lb
kpeter@633
    67
-1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 2 lb
kpeter@633
    68
-1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 2 lb
kpeter@633
    69
-1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 2 lb
kpeter@633
    70
-880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 2 lb
kpeter@633
    71
-499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 2 lb
kpeter@633
    72
-499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 2 lb
kpeter@633
    73
-499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 2 lb
kpeter@633
    74
79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb
kpeter@633
    75
637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb
kpeter@633
    76
205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb
kpeter@633
    77
399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb
kpeter@633
    78
399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 2 lb
kpeter@633
    79
-842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 2 lb
kpeter@633
    80
-842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 2 lb
kpeter@633
    81
-860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 2 lb
kpeter@633
    82
-211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 2 lb
kpeter@633
    83
-99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 2 lb
kpeter@633
    84
-99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 2 lb
kpeter@633
    85
120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 2 lb
kpeter@633
    86
grestore
kpeter@633
    87
%Nodes:
kpeter@633
    88
gsave
kpeter@633
    89
-274 -131 20 1 0 0 nc
kpeter@633
    90
-607.82 -246.651 20 1 0 0 nc
kpeter@633
    91
-484.494 328.869 20 0 0 1 nc
kpeter@633
    92
108.644 334.741 20 0 0 1 nc
kpeter@633
    93
120.389 -129.198 20 0 0 1 nc
kpeter@633
    94
-99.8351 99.8351 20 1 0 0 nc
kpeter@633
    95
-211.415 -452.194 20 1 0 0 nc
kpeter@633
    96
-860.344 -29.3633 20 0 0 1 nc
kpeter@633
    97
-842.726 243.715 20 0 0 1 nc
kpeter@633
    98
399.34 88.0898 20 1 0 0 nc
kpeter@633
    99
205.543 -322.996 20 1 0 0 nc
kpeter@633
   100
637.183 -184.989 20 0 0 1 nc
kpeter@633
   101
79.2808 -528.539 20 0 0 1 nc
kpeter@633
   102
-499.175 -499.175 20 0 0 1 nc
kpeter@633
   103
-880.898 -528.539 20 0 0 1 nc
kpeter@633
   104
-1177.47 -234.906 20 1 0 0 nc
kpeter@633
   105
-1077.63 161.498 20 1 0 0 nc
kpeter@633
   106
-663.61 546.157 20 1 0 0 nc
kpeter@633
   107
-82.2171 593.138 20 0 0 1 nc
kpeter@633
   108
596.074 302.442 20 0 0 1 nc
kpeter@633
   109
869.153 52.8539 20 1 0 0 nc
kpeter@633
   110
393.468 566.711 20 1 0 0 nc
kpeter@633
   111
513.857 -446.322 20 1 0 0 nc
kpeter@633
   112
grestore
kpeter@633
   113
grestore
kpeter@633
   114
showpage