Various improvements in NetworkSimplex.
- Faster variant of "Altering Candidate List" pivot rule using make_heap
instead of partial_sort.
- Doc improvements.
- Removing unecessary inline keywords.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
20 \page getstart How to start using LEMON
22 In this page we detail how to start using LEMON, from downloading it to
23 your computer, through the steps of installation, to showing a simple
24 "Hello World" type program that already uses LEMON. We assume that you
25 have a basic knowledge of your operating system and \c C++ programming
26 language. The procedure is pretty straightforward, but if you have any
27 difficulties don't hesitate to
28 <a href="mailto:lemon-user@lemon.cs.elte.hu">ask</a>.
31 \section requirementsLEMON Hardware and software requirements
33 In LEMON we use C++ templates heavily, thus compilation takes a
34 considerable amount of time and memory. So some decent box would be
35 advantageous. But otherwise there are no special hardware requirements.
37 You will need a recent C++ compiler. Our primary target is the GNU C++
38 Compiler (g++), from version 3.3 upwards. We also checked the Intel C++
39 Compiler (icc). Microsoft Visual C++ .NET 2003 was also reported to
40 work (but not the earlier versions). If you want to develop with LEMON
41 under Windows you could consider using Cygwin.
43 In this description we will suppose a Linux environment and GNU C++ Compiler.
46 \subsection requirementsLP LP solver requirements
48 The LEMON LP solver interface can use the GLPK (GNU Linear Programming
49 Kit) ,CPLEX (was tested with CPLEX 7.5) and SoPlex solver. If you want
50 to use it you will need at least one of these. See \ref configureFlags
51 how to enable these at compile time.
54 \section downloadLEMON How to download LEMON
56 You can download LEMON from the LEMON web site:
57 <a href="https://lemon.cs.elte.hu/site/products/">
58 https://lemon.cs.elte.hu/site/products/</a> .
59 There you will find released versions in form of <tt>.tar.gz</tt> files.
60 If you want a developer version (for example you want to contribute in
61 developing the library LEMON) then you might want to use our Subversion
62 repository. This case is detailed later, so from now on we suppose that
63 you downloaded a <tt>.tar.gz</tt> file.
66 \section installLEMON How to install LEMON
68 In order to install LEMON you have to do the following steps.
70 Download the tarball (named <tt>lemon-x.y.z.tar.gz</tt> where \c x,\c y
71 and \c z are numbers indicating the version of the library: in our example
72 we will have <tt>lemon-0.3.1.tar.gz</tt>) and issue the following
76 tar xvzf lemon-0.3.1.tar.gz
80 make check #(This is optional, but recommended. It runs a bunch of tests.)
84 These commands install LEMON under \c /usr/local (you will
85 need root privileges to be able to install to that
86 directory). If you want to install it to some other place, then
87 pass the \c --prefix=DIRECTORY flag to <tt>./configure</tt>, for example:
90 ./configure --prefix=/home/username/lemon
93 In what follows we will assume that you were able to install to directory
94 \c /usr/local, otherwise some extra care is to be taken to use the
97 We briefly explain these commands below.
100 tar xvzf lemon-0.3.1.tar.gz
102 This command untars the <tt>tar.gz</tt> file into a directory named <tt>
108 Enters the directory.
113 Does some configuration (creates makefiles etc).
118 This command compiles the non-template part of LEMON into
119 <b>libemon.a</b> file. It also compiles some benchmark and demo
125 This is an optional step: it runs the test programs that we
126 developed for LEMON to check whether the library works properly on
132 This will copy the directory structure to its final destination (e.g. to \c
133 /usr/local) so that your system can access it. This command should
134 be issued as "root", unless you provided a \c --prefix switch to
135 the \c configure to install the library in non-default location.
138 \subsection configureFlags Configure flags
140 You can pass the following flags to <tt>./configure</tt> (see <tt>./configure</tt> --help
146 Enable GLPK support (default). You should specify the prefix too if you
147 installed it to some non-standard location (e.g. your home directory). If
148 GLPK is not found, then GLPK support will be disabled.
151 --with-glpk-includedir=DIR
153 The directory where the GLPK header files are located. This is only useful when
154 the GLPK headers and libraries are not under the same prefix (which is
158 --with-glpk-libdir=DIR
160 The directory where the GLPK libraries are located. This is only useful when
161 the GLPK headers and libraries are not under the same prefix (which is
167 Disable GLPK support.
170 --with-cplex[=PREFIX]
172 Enable CPLEX support (default). You should specify the prefix too if you
173 installed it to some non-standard location (e.g. \c /opt/ilog/cplex75). If
174 CPLEX is not found, then CPLEX support will be disabled.
177 --with-cplex-includedir=DIR
179 The directory where the CPLEX header files are located. This is only useful
180 when the CPLEX headers and libraries are not under the same prefix.
183 --with-cplex-libdir=DIR
185 The directory where the CPLEX libraries are located. This is only useful when
186 the CPLEX headers and libraries are not under the same prefix.
191 Disable CPLEX support.
194 --with-soplex[=PREFIX]
196 Enable SoPlex support (default). You should specify the prefix too if
197 you installed it to some non-standard location. If SoPlex is not
198 found, then SoPlex support will be disabled.
201 --with-soplex-includedir=DIR
203 The directory where the SoPlex header files are located. This is only useful
204 when the SoPlex headers and libraries are not under the same prefix.
207 --with-soplex-libdir=DIR
209 The directory where the SoPlex libraries are located. This is only useful when
210 the SoPlex headers and libraries are not under the same prefix.
215 Disable SoPlex support.
218 \section svnCheckout How to checkout LEMON form our Subversion repository
220 You can obtain the latest version of LEMON from our Subversion repository. To
221 do this issue the following command:
223 svn co https://lemon.cs.elte.hu/svn/lemon/trunk lemon-src
225 Use "lemon" as username, the password is empty.
228 \section svnCompile How to compile the source from the repository
230 You can compile the code from the repository similarly to the packaged
231 version, but you will need to run \c autoreconf \c -vi or
232 <tt>./bootstrap</tt> in some older environment before <tt>./configure</tt>. See \c
233 ./configure \c --help for options. For bootstrapping you will need the
236 - <a href="http://www.gnu.org/software/automake/">automake</a> (1.7 or newer)
237 - <a href="http://www.gnu.org/software/autoconf/">autoconf</a> (2.59 or newer)
238 - <a href="http://www.gnu.org/software/libtool/">libtool</a>
239 - <a href="http://pkgconfig.freedesktop.org/">pkgconfig</a>
241 To generate the documentation, run \c make \c doc. You will need
242 <a href="http://www.doxygen.org/">Doxygen</a> for this.
244 You can pass the \c --enable-doc=full flag to <tt>./configure</tt> to generate the
245 internal documentation too.
247 If you pass the \c --disable-doc flag to <tt>./configure</tt> then the documentation
248 won't be installed, when you run \c make \c install (this speeds things up a
251 \section helloworld My first program using LEMON
253 If you have installed LEMON on your system you can paste the
254 following code segment into a file (you can find it as \c
255 demo/hello_lemon.cc in the LEMON package) to have a first working
256 program that uses library LEMON.
258 \dontinclude hello_lemon.cc
262 First let us briefly explain how this program works.
264 ListGraph is one of LEMON's graph classes. It is based on linked lists,
265 therefore iterating throuh its edges and nodes is fast.
267 After some convenience typedefs we create a graph and add three nodes to it.
268 Then we add edges to it to form a complete graph.
270 Then we iterate through all nodes of the graph. We use a constructor of the
271 node iterator to initialize it to the first node. The operator++ is used to
272 step to the next node. Using operator++ on the iterator pointing to the last
273 node invalidates the iterator i.e. sets its value to
274 \ref lemon::INVALID "INVALID". This is what we exploit in the stop condition.
276 We can also iterate through all edges of the graph very similarly. The
278 \c source member functions can be used to access the endpoints of an edge.
280 If your installation of LEMON into directory \c /usr/local was
281 successful, then it is very easy to compile this program with the
282 following command (the argument <tt>-lemon</tt> tells the compiler
283 that we are using the installed library LEMON):
286 g++ hello_lemon.cc -o hello_lemon -lemon
289 As a result you will get the exacutable \c hello_lemon in
290 this directory that you can run by the command
296 If everything has gone well then the previous code fragment prints
302 Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0)
307 If you want to see more features, go to the
308 \ref quicktour "Quick Tour to LEMON",
309 if you want to see some demo programs then go to our
310 \ref demoprograms "Demo Programs" page!