RhodeCode

%!PS-Adobe-2.0 EPSF-2.0

%%Creator: LEMON, graphToEps()

%%CreationDate: Sun Mar 14 09:08:34 2010

%%BoundingBox: -353 -264 559 292

%%EndComments

/lb { setlinewidth setrgbcolor newpath moveto

      4 2 roll 1 index 1 index curveto stroke } bind def

/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def

/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def

/sq { newpath 2 index 1 index add 2 index 2 index add moveto

      2 index 1 index sub 2 index 2 index add lineto

      2 index 1 index sub 2 index 2 index sub lineto

      2 index 1 index add 2 index 2 index sub lineto

      closepath pop pop pop} bind def

/di { newpath 2 index 1 index add 2 index moveto

      2 index             2 index 2 index add lineto

      2 index 1 index sub 2 index             lineto

      2 index             2 index 2 index sub lineto

      closepath pop pop pop} bind def

/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill

     setrgbcolor 1.1 div c fill

   } bind def

/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill

     setrgbcolor 1.1 div sq fill

   } bind def

/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill

     setrgbcolor 1.1 div di fill

   } bind def

/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth

  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub

  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto

  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke

  5 index 5 index 5 index c fill

  setrgbcolor 1.1 div c fill

  } bind def

/nmale {

  0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth

  newpath 5 index 5 index moveto

  5 index 4 index 1 mul 1.5 mul add

  5 index 5 index 3 sqrt 1.5 mul mul add

  1 index 1 index lineto

  1 index 1 index 7 index sub moveto

  1 index 1 index lineto

  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto

  stroke

  5 index 5 index 5 index c fill

  setrgbcolor 1.1 div c fill

  } bind def

/arrl 1 def

/arrw 0.3 def

/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def

/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def

       /w exch def /len exch def

       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto

       len w sub arrl sub dx dy lrl

       arrw dy dx neg lrl

       dx arrl w add mul dy w 2 div arrw add mul sub

       dy arrl w add mul dx w 2 div arrw add mul add rlineto

       dx arrl w add mul neg dy w 2 div arrw add mul sub

       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto

       arrw dy dx neg lrl

       len w sub arrl sub neg dx dy lrl

       closepath fill } bind def

/cshow { 2 index 2 index moveto dup stringwidth pop

         neg 2 div fosi .35 mul neg rmoveto show pop pop} def

gsave

%Arcs:

gsave

140.321 266.249 -327.729 150.06 0 0 0 4.99223 l

82.1207 -238.726 -245.288 -110.743 0 0 0 4.99223 l

336.635 -229.036 533.603 13.109 0 0 0 4.99223 l

53.8598 -45.8071 -245.288 -110.743 0 0 0 4.99223 l

-75.5617 118.579 -327.729 150.06 0 0 0 4.99223 l

-327.729 150.06 -245.288 -110.743 1 0 0 11.9813 l

533.603 13.109 218.184 -84.2955 0 0 0 4.99223 l

39.87 175.035 141.163 67.2575 0 0 0 4.99223 l

53.8598 -45.8071 -75.5617 118.579 0 0 0 4.99223 l

-102.406 -141.267 82.1207 -238.726 0 0 0 4.99223 l

399.144 166.894 533.603 13.109 1 0 0 11.9813 l

39.87 175.035 140.321 266.249 1 0 0 11.9813 l

399.144 166.894 140.321 266.249 0 0 0 4.99223 l

399.144 166.894 141.163 67.2575 0 0 0 4.99223 l

53.8598 -45.8071 204.765 -173.77 0 0 0 4.99223 l

82.1207 -238.726 204.765 -173.77 0 0 0 4.99223 l

258.227 61.658 399.144 166.894 0 0 0 4.99223 l

53.8598 -45.8071 -102.406 -141.267 1 0 0 11.9813 l

175.073 -37.4477 141.163 67.2575 0 0 0 4.99223 l

258.227 61.658 380 0 0 0 0 4.99223 l

34.6739 40.8267 -75.5617 118.579 1 0 0 11.9813 l

380 0 533.603 13.109 0 0 0 4.99223 l

175.073 -37.4477 380 0 0 0 0 4.99223 l

218.184 -84.2955 204.765 -173.77 0 0 0 4.99223 l

53.8598 -45.8071 34.6739 40.8267 0 0 0 4.99223 l

167.905 -213.988 82.1207 -238.726 1 0 0 11.9813 l

336.635 -229.036 204.765 -173.77 1 0 0 11.9813 l

336.635 -229.036 167.905 -213.988 0 0 0 4.99223 l

329.08 -26.3098 218.184 -84.2955 0 0 0 4.99223 l

39.87 175.035 -75.5617 118.579 0 0 0 4.99223 l

53.8598 -45.8071 175.073 -37.4477 0 0 0 4.99223 l

34.6739 40.8267 141.163 67.2575 0 0 0 4.99223 l

258.227 61.658 141.163 67.2575 1 0 0 11.9813 l

175.073 -37.4477 218.184 -84.2955 1 0 0 11.9813 l

380 0 329.08 -26.3098 1 0 0 11.9813 l

grestore

%Nodes:

gsave

-245.288 -110.743 14.9767 1 1 1 nc

204.765 -173.77 14.9767 1 1 1 nc

-327.729 150.06 14.9767 1 1 1 nc

-75.5617 118.579 14.9767 1 1 1 nc

218.184 -84.2955 14.9767 1 1 1 nc

140.321 266.249 14.9767 1 1 1 nc

141.163 67.2575 14.9767 1 1 1 nc

82.1207 -238.726 14.9767 1 1 1 nc

329.08 -26.3098 14.9767 1 1 1 nc

-102.406 -141.267 14.9767 1 1 1 nc

533.603 13.109 14.9767 1 1 1 nc

167.905 -213.988 14.9767 1 1 1 nc

336.635 -229.036 14.9767 1 1 1 nc

380 0 14.9767 1 1 1 nc

399.144 166.894 14.9767 1 1 1 nc

34.6739 40.8267 14.9767 1 1 1 nc

39.87 175.035 14.9767 1 1 1 nc

175.073 -37.4477 14.9767 1 1 1 nc

53.8598 -45.8071 14.9767 1 1 1 nc

258.227 61.658 14.9767 1 1 1 nc

grestore

grestore

showpage

%!PS-Adobe-2.0 EPSF-2.0

%%Creator: LEMON, graphToEps()

%%CreationDate: Fri Oct 19 18:32:32 2007

%%BoundingBox: 0 0 596 842

%%DocumentPaperSizes: a4

%%EndComments

/lb { setlinewidth setrgbcolor newpath moveto

      4 2 roll 1 index 1 index curveto stroke } bind def

/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def

/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def

/sq { newpath 2 index 1 index add 2 index 2 index add moveto

      2 index 1 index sub 2 index 2 index add lineto

      2 index 1 index sub 2 index 2 index sub lineto

      2 index 1 index add 2 index 2 index sub lineto

      closepath pop pop pop} bind def

/di { newpath 2 index 1 index add 2 index moveto

      2 index             2 index 2 index add lineto

      2 index 1 index sub 2 index             lineto

      2 index             2 index 2 index sub lineto

      closepath pop pop pop} bind def

/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill

     setrgbcolor 1.1 div c fill

   } bind def

/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill

     setrgbcolor 1.1 div sq fill

   } bind def

/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill

     setrgbcolor 1.1 div di fill

   } bind def

/nfemale { 0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth

  newpath 5 index 5 index moveto 5 index 5 index 5 index 3.01 mul sub

  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto

  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke

  5 index 5 index 5 index c fill

  setrgbcolor 1.1 div c fill

  } bind def

/nmale {

  0 0 0 setrgbcolor 3 index 0.0909091 1.5 mul mul setlinewidth

  newpath 5 index 5 index moveto

  5 index 4 index 1 mul 1.5 mul add

  5 index 5 index 3 sqrt 1.5 mul mul add

  1 index 1 index lineto

  1 index 1 index 7 index sub moveto

  1 index 1 index lineto

  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto

  stroke

  5 index 5 index 5 index c fill

  setrgbcolor 1.1 div c fill

  } bind def

/arrl 1 def

/arrw 0.3 def

/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def

/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def

       /w exch def /len exch def

       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto

       len w sub arrl sub dx dy lrl

       arrw dy dx neg lrl

       dx arrl w add mul dy w 2 div arrw add mul sub

       dy arrl w add mul dx w 2 div arrw add mul add rlineto

       dx arrl w add mul neg dy w 2 div arrw add mul sub

       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto

       arrw dy dx neg lrl

       len w sub arrl sub neg dx dy lrl

       closepath fill } bind def

/cshow { 2 index 2 index moveto dup stringwidth pop

         neg 2 div fosi .35 mul neg rmoveto show pop pop} def

gsave

15 138.307 translate

12.7843 dup scale

90 rotate

0.608112 -43.6081 translate

%Edges:

gsave

9 31 9.5 30.5 10 30 0 0 0 0.091217 lb

9 31 5.5 34.5 2 38 0 0 0 0.091217 lb

9 31 25.5 16 42 1 0 0 0 0.091217 lb

3 40 23 20.5 43 1 0 0 0 0.091217 lb

3 40 22.5 20.5 42 1 0 0 0 0.091217 lb

3 40 2.5 40.5 2 41 0 0 0 0.091217 lb

13 25 10.5 24.5 8 24 0 0 0 0.091217 lb

13 25 12 27 11 29 0 0 0 0.091217 lb

3 4 2.5 3 2 2 0 0 0 0.091217 lb

3 4 4.5 3 6 2 0 0 0 0.091217 lb

6 25 7 24.5 8 24 0 0 0 0.091217 lb

6 25 6 24.5 6 24 0 0 0 0.091217 lb

34 2 33.5 2 33 2 0 0 0 0.091217 lb

34 2 35 2 36 2 0 0 0 0.091217 lb

6 8 16 9 26 10 0 0 0 0.091217 lb

6 8 6 10.5 6 13 0 0 0 0.091217 lb

6 8 6 7.5 6 7 0 0 0 0.091217 lb

26 10 27.5 8.5 29 7 0 0 0 0.091217 lb

26 10 27.5 9 29 8 0 0 0 0.091217 lb

10 30 10.5 29.5 11 29 0 0 0 0.091217 lb

8 24 7 23.5 6 23 0 0 0 0.091217 lb

8 24 8 24.5 8 25 0 0 0 0.091217 lb

33 2 32.5 2 32 2 0 0 0 0.091217 lb

29 7 17.5 7 6 7 0 0 0 0.091217 lb

2 2 1.5 22 1 42 0 0 0 0.091217 lb

2 2 3.5 2 5 2 0 0 0 0.091217 lb

21 15 13.5 14.5 6 14 0 0 0 0.091217 lb

21 15 21 15.5 21 16 0 0 0 0.091217 lb

1 42 0.5 42.5 0 43 0 0 0 0.091217 lb

1 42 1.5 41.5 2 41 0 0 0 0.091217 lb

6 15 6 15.5 6 16 0 0 0 0.091217 lb

6 15 6 14.5 6 14 0 0 0 0.091217 lb

43 1 22 0.5 1 0 0 0 0 0.091217 lb

31 2 18.5 2 6 2 0 0 0 0.091217 lb

31 2 31.5 2 32 2 0 0 0 0.091217 lb

6 24 6 23.5 6 23 0 0 0 0.091217 lb

6 16 6 16.5 6 17 0 0 0 0.091217 lb

6 23 6 20 6 17 0 0 0 0.091217 lb

6 2 5.5 2 5 2 0 0 0 0.091217 lb

6 2 6 4.5 6 7 0 0 0 0.091217 lb

0 43 0.5 21.5 1 0 0 0 0 0.091217 lb

1 1 19.5 1.5 38 2 0 0 0 0.091217 lb

1 1 1 0.5 1 0 0 0 0 0.091217 lb

2 38 5.5 31.5 9 25 0 0 0 0.091217 lb

25 13 15.5 13 6 13 0 0 0 0.091217 lb

25 13 15.5 13.5 6 14 0 0 0 0.091217 lb

8 25 8.5 25 9 25 0 0 0 0.091217 lb

11 29 24.5 15.5 38 2 0 0 0 0.091217 lb

6 17 11.5 18 17 19 0 0 0 0.091217 lb

16 23 26.5 12.5 37 2 0 0 0 0.091217 lb

16 23 18.5 19.5 21 16 0 0 0 0.091217 lb

36 2 36.5 2 37 2 0 0 0 0.091217 lb

36 2 32.5 5 29 8 0 0 0 0.091217 lb

6 13 6 13.5 6 14 0 0 0 0.091217 lb

37 2 37.5 2 38 2 0 0 0 0.091217 lb

21 16 19 17.5 17 19 0 0 0 0.091217 lb

grestore

%Nodes:

gsave

29 8 0.304556 1 1 1 nc

2 41 0.304556 1 1 1 nc

6 7 0.304556 1 1 1 nc

5 2 0.304556 1 1 1 nc

17 19 0.304556 1 1 1 nc

21 16 0.304556 1 1 1 nc

1 0 0.304556 1 1 1 nc

9 25 0.304556 1 1 1 nc

6 14 0.304556 1 1 1 nc

42 1 0.304556 1 1 1 nc

38 2 0.304556 1 1 1 nc

37 2 0.304556 1 1 1 nc

6 13 0.304556 1 1 1 nc

36 2 0.304556 1 1 1 nc

16 23 0.304556 1 1 1 nc

6 17 0.304556 1 1 1 nc

11 29 0.304556 1 1 1 nc

8 25 0.304556 1 1 1 nc

32 2 0.304556 1 1 1 nc

25 13 0.304556 1 1 1 nc

2 38 0.304556 1 1 1 nc

1 1 0.304556 1 1 1 nc

0 43 0.304556 1 1 1 nc

6 2 0.304556 1 1 1 nc

6 23 0.304556 1 1 1 nc

6 16 0.304556 1 1 1 nc

6 24 0.304556 1 1 1 nc

31 2 0.304556 1 1 1 nc

43 1 0.304556 1 1 1 nc

6 15 0.304556 1 1 1 nc

1 42 0.304556 1 1 1 nc

21 15 0.304556 1 1 1 nc

2 2 0.304556 1 1 1 nc

29 7 0.304556 1 1 1 nc

33 2 0.304556 1 1 1 nc

8 24 0.304556 1 1 1 nc

10 30 0.304556 1 1 1 nc

26 10 0.304556 1 1 1 nc

6 8 0.304556 1 1 1 nc

34 2 0.304556 1 1 1 nc

6 25 0.304556 1 1 1 nc

3 4 0.304556 1 1 1 nc

13 25 0.304556 1 1 1 nc

3 40 0.304556 1 1 1 nc

9 31 0.304556 1 1 1 nc

grestore

grestore

showpage

%%%%% Defining LEMON %%%%%

@misc{lemon,

  key =          {LEMON},

  title =        {{LEMON} -- {L}ibrary for {E}fficient {M}odeling and

                  {O}ptimization in {N}etworks},

  howpublished = {\url{http://lemon.cs.elte.hu/}},

  year =         2009

}

@misc{egres,

  key =          {EGRES},

  title =        {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on

                  {C}ombinatorial {O}ptimization},

  url =          {http://www.cs.elte.hu/egres/}

}

@misc{coinor,

  key =          {COIN-OR},

  title =        {{COIN-OR} -- {C}omputational {I}nfrastructure for

                  {O}perations {R}esearch},

  url =          {http://www.coin-or.org/}

}

%%%%% Other libraries %%%%%%

@misc{boost,

  key =          {Boost},

  title =        {{B}oost {C++} {L}ibraries},

  url =          {http://www.boost.org/}

}

@book{bglbook,

  author =       {Jeremy G. Siek and Lee-Quan Lee and Andrew

                  Lumsdaine},

  title =        {The Boost Graph Library: User Guide and Reference

                  Manual},

  publisher =    {Addison-Wesley},

  year =         2002

}

@misc{leda,

  key =          {LEDA},

  title =        {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and

                  {A}lgorithms},

  url =          {http://www.algorithmic-solutions.com/}

}

@book{ledabook,

  author =       {Kurt Mehlhorn and Stefan N{\"a}her},

  title =        {{LEDA}: {A} platform for combinatorial and geometric

                  computing},

  isbn =         {0-521-56329-1},

  publisher =    {Cambridge University Press},

  address =      {New York, NY, USA},

  year =         1999

}

%%%%% Tools that LEMON depends on %%%%%

@misc{cmake,

  key =          {CMake},

  title =        {{CMake} -- {C}ross {P}latform {M}ake},

  url =          {http://www.cmake.org/}

}

@misc{doxygen,

  key =          {Doxygen},

  title =        {{Doxygen} -- {S}ource code documentation generator

                  tool},

  url =          {http://www.doxygen.org/}

}

%%%%% LP/MIP libraries %%%%%

@misc{glpk,

  key =          {GLPK},

  title =        {{GLPK} -- {GNU} {L}inear {P}rogramming {K}it},

  url =          {http://www.gnu.org/software/glpk/}

}

@misc{clp,

  key =          {Clp},

  title =        {{Clp} -- {Coin-Or} {L}inear {P}rogramming},

  url =          {http://projects.coin-or.org/Clp/}

}

@misc{cbc,

  key =          {Cbc},

  title =        {{Cbc} -- {Coin-Or} {B}ranch and {C}ut},

  url =          {http://projects.coin-or.org/Cbc/}

}

@misc{cplex,

  key =          {CPLEX},

  title =        {{ILOG} {CPLEX}},

  url =          {http://www.ilog.com/}

}

@misc{soplex,

  key =          {SoPlex},

  title =        {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented

                  {S}implex},

  url =          {http://soplex.zib.de/}

}

%%%%% General books %%%%%

@book{amo93networkflows,

  author =       {Ravindra K. Ahuja and Thomas L. Magnanti and James

                  B. Orlin},

  title =        {Network Flows: Theory, Algorithms, and Applications},

  publisher =    {Prentice-Hall, Inc.},

  year =         1993,

  month =        feb,

  isbn =         {978-0136175490}

}

@book{schrijver03combinatorial,

  author =       {Alexander Schrijver},

  title =        {Combinatorial Optimization: Polyhedra and Efficiency},

  publisher =    {Springer-Verlag},

  year =         2003,

  isbn =         {978-3540443896}

}

@book{clrs01algorithms,

  author =       {Thomas H. Cormen and Charles E. Leiserson and Ronald

                  L. Rivest and Clifford Stein},

  title =        {Introduction to Algorithms},

  publisher =    {The MIT Press},

  year =         2001,

  edition =      {2nd}

}

@book{stroustrup00cpp,

  author =       {Bjarne Stroustrup},

  title =        {The C++ Programming Language},

  edition =      {3rd},

  publisher =    {Addison-Wesley Professional},

  isbn =         0201700735,

  month =        {February},

  year =         2000

}

%%%%% Maximum flow algorithms %%%%%

@article{edmondskarp72theoretical,

  author =       {Jack Edmonds and Richard M. Karp},

  title =        {Theoretical improvements in algorithmic efficiency

                  for network flow problems},

  journal =      {Journal of the ACM},

  year =         1972,

  volume =       19,

  number =       2,

  pages =        {248-264}

}

@article{goldberg88newapproach,

  author =       {Andrew V. Goldberg and Robert E. Tarjan},

  title =        {A new approach to the maximum flow problem},

  journal =      {Journal of the ACM},

  year =         1988,

  volume =       35,

  number =       4,

  pages =        {921-940}

}

@article{dinic70algorithm,

  author =       {E. A. Dinic},

  title =        {Algorithm for solution of a problem of maximum flow

                  in a network with power estimation},

  journal =      {Soviet Math. Doklady},

  year =         1970,

  volume =       11,

  pages =        {1277-1280}

}

@article{goldberg08partial,

  author =       {Andrew V. Goldberg},

  title =        {The Partial Augment-Relabel Algorithm for the

                  Maximum Flow Problem},

  journal =      {16th Annual European Symposium on Algorithms},

  year =         2008,

  pages =        {466-477}

}

@article{sleator83dynamic,

  author =       {Daniel D. Sleator and Robert E. Tarjan},

  title =        {A data structure for dynamic trees},

  journal =      {Journal of Computer and System Sciences},

  year =         1983,

  volume =       26,

  number =       3,

  pages =        {362-391}

}

%%%%% Minimum mean cycle algorithms %%%%%

@article{karp78characterization,

  author =       {Richard M. Karp},

  title =        {A characterization of the minimum cycle mean in a

                  digraph},

  journal =      {Discrete Math.},

  year =         1978,

  volume =       23,

  pages =        {309-311}

}

@article{dasdan98minmeancycle,

  author =       {Ali Dasdan and Rajesh K. Gupta},

  title =        {Faster Maximum and Minimum Mean Cycle Alogrithms for

                  System Performance Analysis},

  journal =      {IEEE Transactions on Computer-Aided Design of

                  Integrated Circuits and Systems},

  year =         1998,

  volume =       17,

  number =       10,

  pages =        {889-899}

}

%%%%% Minimum cost flow algorithms %%%%%

@article{klein67primal,

  author =       {Morton Klein},

  title =        {A primal method for minimal cost flows with

                  applications to the assignment and transportation

                  problems},

  journal =      {Management Science},

  year =         1967,

  volume =       14,

  pages =        {205-220}

}

@article{goldberg89cyclecanceling,

  author =       {Andrew V. Goldberg and Robert E. Tarjan},

  title =        {Finding minimum-cost circulations by canceling

                  negative cycles},

  journal =      {Journal of the ACM},

  year =         1989,

  volume =       36,

  number =       4,

  pages =        {873-886}

}

@article{goldberg90approximation,

  author =       {Andrew V. Goldberg and Robert E. Tarjan},

  title =        {Finding Minimum-Cost Circulations by Successive

                  Approximation},

  journal =      {Mathematics of Operations Research},

  year =         1990,

  volume =       15,

  number =       3,

  pages =        {430-466}

}

@article{goldberg97efficient,

  author =       {Andrew V. Goldberg},

  title =        {An Efficient Implementation of a Scaling

                  Minimum-Cost Flow Algorithm},

  journal =      {Journal of Algorithms},

  year =         1997,

  volume =       22,

  number =       1,

  pages =        {1-29}

}

@article{bunnagel98efficient,

  author =       {Ursula B{\"u}nnagel and Bernhard Korte and Jens

                  Vygen},

  title =        {Efficient implementation of the {G}oldberg-{T}arjan

                  minimum-cost flow algorithm},

  journal =      {Optimization Methods and Software},

  year =         1998,

  volume =       10,

  pages =        {157-174}

}

@book{dantzig63linearprog,

  author =       {George B. Dantzig},

  title =        {Linear Programming and Extensions},

  publisher =    {Princeton University Press},

  year =         1963

}

@mastersthesis{kellyoneill91netsimplex,

  author =       {Damian J. Kelly and Garrett M. O'Neill},

  title =        {The Minimum Cost Flow Problem and The Network

                  Simplex Method},

  school =       {University College},

  address =      {Dublin, Ireland},

  year =         1991,

  month =        sep,

}

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2010

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BELLMAN_FORD_H

#define LEMON_BELLMAN_FORD_H

/// \ingroup shortest_path

/// \file

/// \brief Bellman-Ford algorithm.

#include <lemon/list_graph.h>

#include <lemon/bits/path_dump.h>

#include <lemon/core.h>

#include <lemon/error.h>

#include <lemon/maps.h>

#include <lemon/tolerance.h>

#include <lemon/path.h>

#include <limits>

namespace lemon {

  /// \brief Default operation traits for the BellmanFord algorithm class.

  ///

  /// This operation traits class defines all computational operations

  /// and constants that are used in the Bellman-Ford algorithm.

  /// The default implementation is based on the \c numeric_limits class.

  /// If the numeric type does not have infinity value, then the maximum

  /// value is used as extremal infinity value.

  ///

  /// \see BellmanFordToleranceOperationTraits

  template <

    typename V,

    bool has_inf = std::numeric_limits<V>::has_infinity>

  struct BellmanFordDefaultOperationTraits {

    /// \brief Value type for the algorithm.

    typedef V Value;

    /// \brief Gives back the zero value of the type.

    static Value zero() {

      return static_cast<Value>(0);

    }

    /// \brief Gives back the positive infinity value of the type.

    static Value infinity() {

      return std::numeric_limits<Value>::infinity();

    }

    /// \brief Gives back the sum of the given two elements.

    static Value plus(const Value& left, const Value& right) {

      return left + right;

    }

    /// \brief Gives back \c true only if the first value is less than

    /// the second.

    static bool less(const Value& left, const Value& right) {

      return left < right;

    }

  };

  template <typename V>

  struct BellmanFordDefaultOperationTraits<V, false> {

    typedef V Value;

    static Value zero() {

      return static_cast<Value>(0);

    }

    static Value infinity() {

      return std::numeric_limits<Value>::max();

    }

    static Value plus(const Value& left, const Value& right) {

      if (left == infinity() || right == infinity()) return infinity();

      return left + right;

    }

    static bool less(const Value& left, const Value& right) {

      return left < right;

    }

  };

  /// \brief Operation traits for the BellmanFord algorithm class

  /// using tolerance.

  ///

  /// This operation traits class defines all computational operations

  /// and constants that are used in the Bellman-Ford algorithm.

  /// The only difference between this implementation and

  /// \ref BellmanFordDefaultOperationTraits is that this class uses

  /// the \ref Tolerance "tolerance technique" in its \ref less()

  /// function.

  ///

  /// \tparam V The value type.

  /// \tparam eps The epsilon value for the \ref less() function.

  /// By default, it is the epsilon value used by \ref Tolerance

  /// "Tolerance<V>".

  ///

  /// \see BellmanFordDefaultOperationTraits

#ifdef DOXYGEN

  template <typename V, V eps>

#else

  template <

    typename V,

    V eps = Tolerance<V>::def_epsilon>

#endif

  struct BellmanFordToleranceOperationTraits {

    /// \brief Value type for the algorithm.

    typedef V Value;

    /// \brief Gives back the zero value of the type.

    static Value zero() {

      return static_cast<Value>(0);

    }

    /// \brief Gives back the positive infinity value of the type.

    static Value infinity() {

      return std::numeric_limits<Value>::infinity();

    }

    /// \brief Gives back the sum of the given two elements.

    static Value plus(const Value& left, const Value& right) {

      return left + right;

    }

    /// \brief Gives back \c true only if the first value is less than

    /// the second.

    static bool less(const Value& left, const Value& right) {

      return left + eps < right;

    }

  };

  /// \brief Default traits class of BellmanFord class.

  ///

  /// Default traits class of BellmanFord class.

  /// \param GR The type of the digraph.

  /// \param LEN The type of the length map.

  template<typename GR, typename LEN>

  struct BellmanFordDefaultTraits {

    /// The type of the digraph the algorithm runs on.

    typedef GR Digraph;

    /// \brief The type of the map that stores the arc lengths.

    ///

    /// The type of the map that stores the arc lengths.

    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

    typedef LEN LengthMap;

    /// The type of the arc lengths.

    typedef typename LEN::Value Value;

    /// \brief Operation traits for Bellman-Ford algorithm.

    ///

    /// It defines the used operations and the infinity value for the

    /// given \c Value type.

    /// \see BellmanFordDefaultOperationTraits,

    /// BellmanFordToleranceOperationTraits

    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;

    /// \brief The type of the map that stores the last arcs of the

    /// shortest paths.

    ///

    /// The type of the map that stores the last

    /// arcs of the shortest paths.

    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;

    /// \brief Instantiates a \c PredMap.

    ///

    /// This function instantiates a \ref PredMap.

    /// \param g is the digraph to which we would like to define the

    /// \ref PredMap.

    static PredMap *createPredMap(const GR& g) {

      return new PredMap(g);

    }

    /// \brief The type of the map that stores the distances of the nodes.

    ///

    /// The type of the map that stores the distances of the nodes.

    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename GR::template NodeMap<typename LEN::Value> DistMap;

    /// \brief Instantiates a \c DistMap.

    ///

    /// This function instantiates a \ref DistMap.

    /// \param g is the digraph to which we would like to define the

    /// \ref DistMap.

    static DistMap *createDistMap(const GR& g) {

      return new DistMap(g);

    }

  };

  /// \brief %BellmanFord algorithm class.

  ///

  /// \ingroup shortest_path

  /// This class provides an efficient implementation of the Bellman-Ford

  /// algorithm. The maximum time complexity of the algorithm is

  /// <tt>O(ne)</tt>.

  ///

  /// The Bellman-Ford algorithm solves the single-source shortest path

  /// problem when the arcs can have negative lengths, but the digraph

  /// should not contain directed cycles with negative total length.

  /// If all arc costs are non-negative, consider to use the Dijkstra

  /// algorithm instead, since it is more efficient.

  ///

  /// The arc lengths are passed to the algorithm using a

  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any

  /// kind of length. The type of the length values is determined by the

  /// \ref concepts::ReadMap::Value "Value" type of the length map.

  ///

  /// There is also a \ref bellmanFord() "function-type interface" for the

  /// Bellman-Ford algorithm, which is convenient in the simplier cases and

  /// it can be used easier.

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// The default type is \ref ListDigraph.

  /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies

  /// the lengths of the arcs. The default map type is

  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

  /// \tparam TR The traits class that defines various types used by the

  /// algorithm. By default, it is \ref BellmanFordDefaultTraits

  /// "BellmanFordDefaultTraits<GR, LEN>".

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template <typename GR=ListDigraph,

            typename LEN=typename GR::template ArcMap<int>,

            typename TR=BellmanFordDefaultTraits<GR,LEN> >

#endif

  class BellmanFord {

  public:

    ///The type of the underlying digraph.

    typedef typename TR::Digraph Digraph;

    /// \brief The type of the arc lengths.

    typedef typename TR::LengthMap::Value Value;

    /// \brief The type of the map that stores the arc lengths.

    typedef typename TR::LengthMap LengthMap;

    /// \brief The type of the map that stores the last

    /// arcs of the shortest paths.

    typedef typename TR::PredMap PredMap;

    /// \brief The type of the map that stores the distances of the nodes.

    typedef typename TR::DistMap DistMap;

    /// The type of the paths.

    typedef PredMapPath<Digraph, PredMap> Path;

    ///\brief The \ref BellmanFordDefaultOperationTraits

    /// "operation traits class" of the algorithm.

    typedef typename TR::OperationTraits OperationTraits;

    ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.

    typedef TR Traits;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    // Pointer to the underlying digraph.

    const Digraph *_gr;

    // Pointer to the length map

    const LengthMap *_length;

    // Pointer to the map of predecessors arcs.

    PredMap *_pred;

    // Indicates if _pred is locally allocated (true) or not.

    bool _local_pred;

    // Pointer to the map of distances.

    DistMap *_dist;

    // Indicates if _dist is locally allocated (true) or not.

    bool _local_dist;

    typedef typename Digraph::template NodeMap<bool> MaskMap;

    MaskMap *_mask;

    std::vector<Node> _process;

    // Creates the maps if necessary.

    void create_maps() {

      if(!_pred) {

        _local_pred = true;

        _pred = Traits::createPredMap(*_gr);

      }

      if(!_dist) {

        _local_dist = true;

        _dist = Traits::createDistMap(*_gr);

      }

      if(!_mask) {

        _mask = new MaskMap(*_gr);

      }

    }

  public :

    typedef BellmanFord Create;

    /// \name Named Template Parameters

    ///@{

    template <class T>

    struct SetPredMapTraits : public Traits {

      typedef T PredMap;

      static PredMap *createPredMap(const Digraph&) {

        LEMON_ASSERT(false, "PredMap is not initialized");

        return 0; // ignore warnings

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c PredMap type.

    ///

    /// \ref named-templ-param "Named parameter" for setting

    /// \c PredMap type.

    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

    struct SetPredMap

      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {

      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;

    };

    template <class T>

    struct SetDistMapTraits : public Traits {

      typedef T DistMap;

      static DistMap *createDistMap(const Digraph&) {

        LEMON_ASSERT(false, "DistMap is not initialized");

        return 0; // ignore warnings

      }

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c DistMap type.

    ///

    /// \ref named-templ-param "Named parameter" for setting

    /// \c DistMap type.

    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

    struct SetDistMap

      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {

      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;

    };

    template <class T>

    struct SetOperationTraitsTraits : public Traits {

      typedef T OperationTraits;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    /// \c OperationTraits type.

    ///

    /// \ref named-templ-param "Named parameter" for setting

    /// \c OperationTraits type.

    /// For more information, see \ref BellmanFordDefaultOperationTraits.

    template <class T>

    struct SetOperationTraits

      : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {

      typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >

      Create;

    };

    ///@}

  protected:

    BellmanFord() {}

  public:

    /// \brief Constructor.

    ///

    /// Constructor.

    /// \param g The digraph the algorithm runs on.

    /// \param length The length map used by the algorithm.

    BellmanFord(const Digraph& g, const LengthMap& length) :

      _gr(&g), _length(&length),

      _pred(0), _local_pred(false),

      _dist(0), _local_dist(false), _mask(0) {}

    ///Destructor.

    ~BellmanFord() {

      if(_local_pred) delete _pred;

      if(_local_dist) delete _dist;

      if(_mask) delete _mask;

    }

    /// \brief Sets the length map.

    ///

    /// Sets the length map.

    /// \return <tt>(*this)</tt>

    BellmanFord &lengthMap(const LengthMap &map) {

      _length = ↦

      return *this;

    }

    /// \brief Sets the map that stores the predecessor arcs.

    ///

    /// Sets the map that stores the predecessor arcs.

    /// If you don't use this function before calling \ref run()

    /// or \ref init(), an instance will be allocated automatically.

    /// The destructor deallocates this automatically allocated map,

    /// of course.

    /// \return <tt>(*this)</tt>

    BellmanFord &predMap(PredMap &map) {

      if(_local_pred) {

        delete _pred;

        _local_pred=false;

      }

      _pred = ↦

      return *this;

    }

    /// \brief Sets the map that stores the distances of the nodes.

    ///

    /// Sets the map that stores the distances of the nodes calculated

    /// by the algorithm.

    /// If you don't use this function before calling \ref run()

    /// or \ref init(), an instance will be allocated automatically.

    /// The destructor deallocates this automatically allocated map,

    /// of course.

    /// \return <tt>(*this)</tt>

    BellmanFord &distMap(DistMap &map) {

      if(_local_dist) {

        delete _dist;

        _local_dist=false;

      }

      _dist = ↦

      return *this;

    }

    /// \name Execution Control

    /// The simplest way to execute the Bellman-Ford algorithm is to use

    /// one of the member functions called \ref run().\n

    /// If you need better control on the execution, you have to call

    /// \ref init() first, then you can add several source nodes

    /// with \ref addSource(). Finally the actual path computation can be

    /// performed with \ref start(), \ref checkedStart() or

    /// \ref limitedStart().

    ///@{

    /// \brief Initializes the internal data structures.

    ///

    /// Initializes the internal data structures. The optional parameter

    /// is the initial distance of each node.

    void init(const Value value = OperationTraits::infinity()) {

      create_maps();

      for (NodeIt it(*_gr); it != INVALID; ++it) {

        _pred->set(it, INVALID);

        _dist->set(it, value);

      }

      _process.clear();

      if (OperationTraits::less(value, OperationTraits::infinity())) {

        for (NodeIt it(*_gr); it != INVALID; ++it) {

          _process.push_back(it);

          _mask->set(it, true);

        }

      } else {