LEMON/LEMON-official Changeset - r802:134852d7fb0a

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r802:134852d7fb0a

« 801:2de0fc

803:53bea3 »

r802:134852d7fb0a

Sat, 10 Oct 2009 08:18:46

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Insert citations into the doc (#184) - Add general citations to modules. - Add specific citations for max flow and min cost flow algorithms. - Add citations for the supported LP and MIP solvers. - Extend the main page. - Replace inproceedings entries with the journal versions. - Add a new bibtex entry about network simplex. - Remove unwanted entries.

0 6 0

default

6 files changed with 86 insertions and 93 deletions:

doc/groups.dox

doc/mainpage.dox

doc/min_cost_flow.dox

doc/references.bib

lemon/network_simplex.h

lemon/preflow.h

↑ Collapse diff ↑

doc/groups.dox

Show inline comments

@@ -316,7 +316,8 @@
 		\brief Common graph search algorithms.
 		This group contains the common graph search algorithms, namely
-		\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
 		\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
 		\ref clrs01algorithms.
 		*/
 		/**
@@ -324,7 +325,8 @@
 		@ingroup algs
 		\brief Algorithms for finding shortest paths.
-		This group contains the algorithms for finding shortest paths in digraphs.
 		This group contains the algorithms for finding shortest paths in digraphs
 		\ref clrs01algorithms.
 		 - \ref Dijkstra algorithm for finding shortest paths from a source node
 		   when all arc lengths are non-negative.
@@ -346,7 +348,7 @@
 		\brief Algorithms for finding minimum cost spanning trees and arborescences.
 		This group contains the algorithms for finding minimum cost spanning
 		trees and arborescences.
+		trees and arborescences \ref clrs01algorithms.
 		*/
 		/**
@@ -355,7 +357,7 @@
 		\brief Algorithms for finding maximum flows.
 		This group contains the algorithms for finding maximum flows and
 		feasible circulations.
+		feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
 		The \e maximum \e flow \e problem is to find a flow of maximum value between
 		a single source and a single target. Formally, there is a \f$G=(V,A)\f$
@@ -370,12 +372,16 @@
 		\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 		LEMON contains several algorithms for solving maximum flow problems:
 		- \ref EdmondsKarp Edmonds-Karp algorithm.
 		- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
 		- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
 		- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
 		- \ref EdmondsKarp Edmonds-Karp algorithm
 		  \ref edmondskarp72theoretical.
 		- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
 		  \ref goldberg88newapproach.
 		- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
 		  \ref dinic70algorithm, \ref sleator83dynamic.
 		- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
 		  \ref goldberg88newapproach, \ref sleator83dynamic.
-		In most cases the \ref Preflow "Preflow" algorithm provides the
 		In most cases the \ref Preflow algorithm provides the
 		fastest method for computing a maximum flow. All implementations
 		also provide functions to query the minimum cut, which is the dual
 		problem of maximum flow.
@@ -393,18 +399,22 @@
 		\brief Algorithms for finding minimum cost flows and circulations.
 		This group contains the algorithms for finding minimum cost flows and
 		circulations. For more information about this problem and its dual
 		solution see \ref min_cost_flow "Minimum Cost Flow Problem".
 		circulations \ref amo93networkflows. For more information about this
 		problem and its dual solution, see \ref min_cost_flow
 		"Minimum Cost Flow Problem".
 		LEMON contains several algorithms for this problem.
 		 - \ref NetworkSimplex Primal Network Simplex algorithm with various
 		   pivot strategies.
+		   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
 		 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
-		   cost scaling.
+		   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
 		   \ref bunnagel98efficient.
 		 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
 		   capacity scaling.
 		 - \ref CancelAndTighten The Cancel and Tighten algorithm.
-		 - \ref CycleCanceling Cycle-Canceling algorithms.
+		   capacity scaling \ref edmondskarp72theoretical.
 		 - \ref CancelAndTighten The Cancel and Tighten algorithm
 		   \ref goldberg89cyclecanceling.
 		 - \ref CycleCanceling Cycle-Canceling algorithms
 		   \ref klein67primal, \ref goldberg89cyclecanceling.
 		In general NetworkSimplex is the most efficient implementation,
 		but in special cases other algorithms could be faster.
@@ -534,13 +544,16 @@
 		*/
 		/**
-		@defgroup lp_group Lp and Mip Solvers
+		@defgroup lp_group LP and MIP Solvers
 		@ingroup gen_opt_group
-		\brief Lp and Mip solver interfaces for LEMON.
+		\brief LP and MIP solver interfaces for LEMON.
 		This group contains Lp and Mip solver interfaces for LEMON. The
 		various LP solvers could be used in the same manner with this
-		interface.
+		This group contains LP and MIP solver interfaces for LEMON.
 		Various LP solvers could be used in the same manner with this
 		high-level interface.
 		The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
 		\ref cplex, \ref soplex.
 		*/
 		/**

doc/mainpage.dox

Show inline comments

@@ -21,14 +21,11 @@
 		\section intro Introduction
 		\subsection whatis What is LEMON
 		LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
 		and <b>O</b>ptimization in <b>N</b>etworks.
 		It is a C++ template
 		library aimed at combinatorial optimization tasks which
 		often involve in working
 		with graphs.
 		<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
 		and <b>O</b>ptimization in <b>N</b>etworks</i>.
 		It is a C++ template library providing efficient implementation of common
 		data structures and algorithms with focus on combinatorial optimization
 		problems in graphs and networks.
 		<b>
 		LEMON is an <a class="el" href="http://opensource.org/">open&nbsp;source</a>
@@ -38,7 +35,16 @@
 		\ref license "license terms".
 		</b>
-		\subsection howtoread How to read the documentation
+		The project is maintained by the
 		<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
 		Combinatorial Optimization</a> \ref egres
 		at the Operations Research Department of the
 		<a href="http://www.elte.hu/">E&ouml;tv&ouml;s Lor&aacute;nd University,
 		Budapest</a>, Hungary.
 		LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
 		initiative \ref coinor.
 		\section howtoread How to Read the Documentation
 		If you would like to get to know the library, see
 		<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.

doc/min_cost_flow.dox

Show inline comments

@@ -26,7 +26,7 @@
 		The \e minimum \e cost \e flow \e problem is to find a feasible flow of
 		minimum total cost from a set of supply nodes to a set of demand nodes
 		in a network with capacity constraints (lower and upper bounds)
 		and arc costs.
+		and arc costs \ref amo93networkflows.
 		Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
 		\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and

doc/references.bib

Show inline comments

@@ -150,15 +150,25 @@
 		%%%%% Maximum flow algorithms %%%%%
-		@inproceedings{goldberg86newapproach,
+		@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},
 		  booktitle =    {STOC '86: Proceedings of the Eighteenth Annual ACM
 		                  Symposium on Theory of Computing},
 		  year =         1986,
 		  publisher =    {ACM Press},
 		  address =      {New York, NY},
 		  pages =        {136-146}
 		  journal =      {Journal of the ACM},
 		  year =         1988,
 		  volume =       35,
 		  number =       4,
 		  pages =        {921-940}
+		}
 		@article{dinic70algorithm,
@@ -229,42 +239,18 @@
 		  pages =        {205-220}
+		}
-		@inproceedings{goldberg88cyclecanceling,
+		@article{goldberg89cyclecanceling,
 		  author =       {Andrew V. Goldberg and Robert E. Tarjan},
 		  title =        {Finding minimum-cost circulations by canceling
 		                  negative cycles},
 		  booktitle =    {STOC '88: Proceedings of the Twentieth Annual ACM
 		                  Symposium on Theory of Computing},
 		  year =         1988,
 		  publisher =    {ACM Press},
 		  address =      {New York, NY},
 		  pages =        {388-397}
 		  journal =      {Journal of the ACM},
 		  year =         1989,
 		  volume =       36,
 		  number =       4,
 		  pages =        {873-886}
+		}
 		@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}
+		}
 		@inproceedings{goldberg87approximation,
 		  author =       {Andrew V. Goldberg and Robert E. Tarjan},
 		  title =        {Solving minimum-cost flow problems by successive
 		                  approximation},
 		  booktitle =    {STOC '87: Proceedings of the Nineteenth Annual ACM
 		                  Symposium on Theory of Computing},
 		  year =         1987,
 		  publisher =    {ACM Press},
 		  address =      {New York, NY},
 		  pages =        {7-18}
+		}
 		@article{goldberg90finding,
 		@article{goldberg90approximation,
 		  author =       {Andrew V. Goldberg and Robert E. Tarjan},
 		  title =        {Finding Minimum-Cost Circulations by Successive
 		                  Approximation},
@@ -297,6 +283,13 @@
 		  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
@@ -306,25 +299,3 @@
 		  year =         1991,
 		  month =        sep,
+		}
 		@techreport{lobel96networksimplex,
 		  author =       {Andreas L{\"o}bel},
 		  title =        {Solving large-scale real-world minimum-cost flow
 		                  problems by a network simplex method},
 		  institution =  {Konrad-Zuse-Zentrum fur Informationstechnik Berlin
 		                  ({ZIB})},
 		  address =      {Berlin, Germany},
 		  year =         1996,
 		  number =       {SC 96-7}
+		}
 		@article{frangioni06computational,
 		  author =       {Antonio Frangioni and Antonio Manca},
 		  title =        {A Computational Study of Cost Reoptimization for
 		                  Min-Cost Flow Problems},
 		  journal =      {INFORMS Journal On Computing},
 		  year =         2006,
 		  volume =       18,
 		  number =       1,
 		  pages =        {61-70}
+		}

lemon/network_simplex.h

Show inline comments

@@ -40,7 +40,9 @@
 		  /// for finding a \ref min_cost_flow "minimum cost flow".
 		  ///
 		  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
-		  /// for finding a \ref min_cost_flow "minimum cost flow".
 		  /// for finding a \ref min_cost_flow "minimum cost flow"
 		  /// \ref amo93networkflows, \ref dantzig63linearprog,
 		  /// \ref kellyoneill91netsimplex.
 		  /// This algorithm is a specialized version of the linear programming
 		  /// simplex method directly for the minimum cost flow problem.
 		  /// It is one of the most efficient solution methods.

lemon/preflow.h

Show inline comments

@@ -102,7 +102,8 @@
 		  ///
 		  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
 		  /// \e push-relabel algorithm producing a \ref max_flow
-		  /// "flow of maximum value" in a digraph.
+		  /// "flow of maximum value" in a digraph \ref clrs01algorithms,
 		  /// \ref amo93networkflows, \ref goldberg88newapproach.
 		  /// The preflow algorithms are the fastest known maximum
 		  /// flow algorithms. The current implementation uses a mixture of the
 		  /// \e "highest label" and the \e "bound decrease" heuristics.

0 comments (0 inline)

RhodeCode

Login to your account