doc/images/bipartite_partitions.eps
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:45:15 +0100
changeset 811 fe80a8145653
parent 586 7c12061bd271
child 1045 4e8787627db3
permissions -rw-r--r--
Small implementation improvements in MCF algorithms (#180)

- Handle max() as infinite value (not only infinity()).
- Better GEQ handling in CapacityScaling.
- Skip the unnecessary saturating operations in the first phase in
CapacityScaling.
- Use vector<char> instead of vector<bool> and vector<int> if it is
possible and it proved to be usually faster.
     1 %!PS-Adobe-2.0 EPSF-2.0
     2 %%Creator: LEMON, graphToEps()
     3 %%CreationDate: Tue Nov 15 16:51:43 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.6378 15 translate
    51 0.389093 dup scale
    52 90 rotate
    53 1197.47 -613.138 translate
    54 %Edges:
    55 gsave
    56 513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb
    57 513.857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb
    58 393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb
    59 393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb
    60 393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb
    61 869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb
    62 869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 2 lb
    63 -82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 2 lb
    64 -663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 2 lb
    65 -663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 2 lb
    66 -1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 2 lb
    67 -1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 2 lb
    68 -1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 2 lb
    69 -1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 2 lb
    70 -880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 2 lb
    71 -499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 2 lb
    72 -499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 2 lb
    73 -499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 2 lb
    74 79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb
    75 637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb
    76 205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb
    77 399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb
    78 399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 2 lb
    79 -842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 2 lb
    80 -842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 2 lb
    81 -860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 2 lb
    82 -211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 2 lb
    83 -99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 2 lb
    84 -99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 2 lb
    85 120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 2 lb
    86 grestore
    87 %Nodes:
    88 gsave
    89 -274 -131 20 1 0 0 nc
    90 -607.82 -246.651 20 1 0 0 nc
    91 -484.494 328.869 20 0 0 1 nc
    92 108.644 334.741 20 0 0 1 nc
    93 120.389 -129.198 20 0 0 1 nc
    94 -99.8351 99.8351 20 1 0 0 nc
    95 -211.415 -452.194 20 1 0 0 nc
    96 -860.344 -29.3633 20 0 0 1 nc
    97 -842.726 243.715 20 0 0 1 nc
    98 399.34 88.0898 20 1 0 0 nc
    99 205.543 -322.996 20 1 0 0 nc
   100 637.183 -184.989 20 0 0 1 nc
   101 79.2808 -528.539 20 0 0 1 nc
   102 -499.175 -499.175 20 0 0 1 nc
   103 -880.898 -528.539 20 0 0 1 nc
   104 -1177.47 -234.906 20 1 0 0 nc
   105 -1077.63 161.498 20 1 0 0 nc
   106 -663.61 546.157 20 1 0 0 nc
   107 -82.2171 593.138 20 0 0 1 nc
   108 596.074 302.442 20 0 0 1 nc
   109 869.153 52.8539 20 1 0 0 nc
   110 393.468 566.711 20 1 0 0 nc
   111 513.857 -446.322 20 1 0 0 nc
   112 grestore
   113 grestore
   114 showpage