1.1 --- a/doc/getstart.dox Fri Jun 24 21:02:47 2005 +0000
1.2 +++ b/doc/getstart.dox Fri Jun 24 21:03:08 2005 +0000
1.3 @@ -3,26 +3,46 @@
1.4
1.5 In this page we detail how to start using LEMON, from downloading it to
1.6 your computer, through the steps of installation to showing a simple
1.7 -"Hello World" type program that already uses LEMON. If anything is not
1.8 +"Hello World" type program that already uses LEMON. We assume that you have a
1.9 +basic knowledge of your operating system and \c C++ or \c C
1.10 +programming language. If anything is not
1.11 clear write to our FAQ.
1.12
1.13 \todo Is this FAQ thing a good idea here? Is there such a thing? If
1.14 twice YES then a link comes here.
1.15
1.16 +\section requirementsLEMON Hardware and software requirements
1.17
1.18 +Hardware requirements ...
1.19 +
1.20 +You will also need a C++ compiler. We mostly used the Gnu C++ Compiler (g++),
1.21 +from version 3.0 upwards. We also checked the Intel C compiler
1.22 +(icc). Unfortunately, Visual C++ compiler knows not enough to compile the
1.23 +library, so if you are using Microsoft Windows, then try to compile under
1.24 +Cygwin.
1.25 +
1.26 +Ide kell írni:
1.27 +
1.28 +-Hol fordul (Windows-os fordító nem fordítja, unix/linux alatt gcc hanyas verziója kell)
1.29 +-
1.30 +
1.31 +In this description we will suppose a linux environment and Gnu C Compiler.
1.32
1.33 \section downloadLEMON How to download LEMON
1.34
1.35 You can download LEMON from the LEMON web site:
1.36 http://lemon.cs.elte.hu
1.37 -by following the download link. There you will find the issued distributions in form of \e .ta.gz files. If you want a developer version (for example you want to contribute in developing the library LEMON) then you might want to use our Subversion repository. This case is not detailed here, so from now on we suppose that you downloaded a tar.gz file.
1.38 +by following the download link. There you will find the issued distributions
1.39 +in form of <tt> .tar.gz </tt> files. If you want a developer version (for example you want to contribute in developing the library LEMON) then you might want to use our Subversion repository. This case is not detailed here, so from now on we suppose that you downloaded a tar.gz file.
1.40 +
1.41
1.42
1.43 \section installLEMON How to install LEMON
1.44
1.45 In order to install LEMON you have to do the following
1.46
1.47 -Download the tarball and issue the following commands:
1.48 +Download the tarball (named <tt>lemon-x.y.z.tar.gz</tt> where \c x,\c y and \c z are
1.49 +numbers indicating the version of the library: in our example we will have lemon-0.3.1) and issue the following commands:
1.50
1.51 \code
1.52 tar xvzf lemon-0.3.1.tar.gz
1.53 @@ -33,16 +53,54 @@
1.54 make install
1.55 \endcode
1.56
1.57 -These commands install LEMON under /usr/local. If you want to install it to some other place, then pass the --prefix=DIR flag to ./configure.
1.58 +These commands install LEMON under \c /usr/local (you will probably need \c root
1.59 +privileges to be able to install to that directory). If you want to install it
1.60 +to some other place, then pass the \c --prefix=DIR flag to \c ./configure. In
1.61 +what follows we will assume that you were able to install to directory \c
1.62 +/usr/local, otherwise some extra care is to be taken to use the library.
1.63
1.64 -Ide kell írni:
1.65 -
1.66 --Hol fordul (Windows-os fordító nem fordítja, unix/linux alatt gcc hanyas verziója kell)
1.67 --
1.68 +We briefly explain these commands below.
1.69 +
1.70 +\code
1.71 +tar xvzf lemon-0.3.1.tar.gz
1.72 +\endcode
1.73 +This command untars the <tt>tar.gz</tt> file into a directory named <tt> lemon-0.3.1</tt>.
1.74 +
1.75 +\code
1.76 +cd lemon-0.3.1
1.77 +\endcode
1.78 +Enters the directory.
1.79 +
1.80 +\code
1.81 +./configure
1.82 +\endcode
1.83 +Does some configuration (creates makefiles etc).
1.84 +
1.85 +\code
1.86 +make
1.87 +\endcode
1.88 +This command compiles the <tt> .cc</tt> files of the library package (the
1.89 +implementation of non-template functions and classes and some test and demo
1.90 +programs) and creates the very important <b> libemon.la </b> file. When
1.91 +linking your program that uses LEMON it needs to access this file.
1.92 +
1.93 +\code
1.94 +make check (This is optional, but recomended. It runs a bunch of tests.)
1.95 +\endcode
1.96 +This is an optional step: it runs the test programs that we developed for
1.97 +LEMON to check
1.98 +whether the library works properly on your platform.
1.99 +
1.100 +\code
1.101 +make install
1.102 +\endcode
1.103 +This will copy the directory structure to its final destination (e.g. to \c
1.104 +/usr/local) so that your system can access it.
1.105
1.106 \section helloworld My first program using LEMON
1.107
1.108 -If you have installed LEMON on your system you can paste the following code
1.109 +If you have installed LEMON on your system you
1.110 +can paste the following code
1.111 segment into a file to have a first working program that uses library LEMON.
1.112
1.113 \code
1.114 @@ -54,11 +112,7 @@
1.115 int main()
1.116 {
1.117 typedef ListGraph Graph;
1.118 - typedef Graph::Edge Edge;
1.119 - typedef Graph::InEdgeIt InEdgeIt;
1.120 - typedef Graph::OutEdgeIt OutEdgeIt;
1.121 typedef Graph::EdgeIt EdgeIt;
1.122 - typedef Graph::Node Node;
1.123 typedef Graph::NodeIt NodeIt;
1.124
1.125 Graph g;
1.126 @@ -82,6 +136,7 @@
1.127
1.128 \endcode
1.129
1.130 +First let us briefly explain how this program works.
1.131
1.132 ListGraph is one of LEMON's graph classes. It is based on linked lists,
1.133 therefore iterating throuh its edges and nodes is fast.
1.134 @@ -99,7 +154,22 @@
1.135 \c target and
1.136 \c source member functions can be used to access the endpoints of an edge.
1.137
1.138 -The previous code fragment prints out the following:
1.139 +If you have saved the preceding code into a file named, say, \c hemon.cc and your installation of LEMON into directory \c /usr/local was
1.140 +successful then it is very easy to compile this program with the following
1.141 +command (the argument <tt>-lemon</tt> tells the compiler that we are using the
1.142 +installed library LEMON):
1.143 +\code
1.144 +g++ hemon.cc -o hemon -lemon
1.145 +\endcode
1.146 +
1.147 +As a result you will get the exacutable \c hemon in
1.148 +this directory that you can run by the command
1.149 +\code
1.150 +./hemon
1.151 +\endcode
1.152 +
1.153 +
1.154 +If everything has gone well then the previous code fragment prints out the following:
1.155
1.156 \code
1.157 Nodes: 2 1 0
1.158 @@ -107,6 +177,7 @@
1.159 Edges: (0,2) (1,2) (0,1) (2,1) (1,0) (2,0)
1.160 \endcode
1.161
1.162 +Congratulations!
1.163
1.164 If you want to see more features, go to the \ref quicktour "Quick Tour to
1.165 LEMON", if you want to see see some demo programs then go to our
2.1 --- a/doc/quicktour.dox Fri Jun 24 21:02:47 2005 +0000
2.2 +++ b/doc/quicktour.dox Fri Jun 24 21:03:08 2005 +0000
2.3 @@ -18,14 +18,18 @@
2.4 graph: a very good description can be found in the page
2.5 about \ref graphs "graphs".
2.6
2.7 -You will also want to assign data to the edges or nodes of the graph, for example a length or capacity function defined on the edges. You can do this in LEMON using so called \ref maps "maps". You can define a map on the nodes or on the edges of the graph and the value of the map (the range of the function) can be practically almost of any type. Read more about maps \ref maps-page "here".
2.8 +You will also want to assign data to the edges or nodes of the graph, for
2.9 +example a length or capacity function defined on the edges. You can do this in
2.10 +LEMON using so called \b maps. You can define a map on the nodes or on the edges of the graph and the value of the map (the range of the function) can be practically almost of any type. Read more about maps \ref maps-page "here".
2.11
2.12 Some examples are the following (you will find links next to the code fragments that help to download full demo programs: save them on your computer and compile them according to the description in the page about \ref getsart How to start using LEMON):
2.13
2.14 -- First we give two examples that show how to instantiate a graph. The
2.15 +<ul>
2.16 +<li> First we give two examples that show how to instantiate a graph. The
2.17 first one shows the methods that add nodes and edges, but one will
2.18 usually use the second way which reads a graph from a stream (file).
2.19 --# The following code fragment shows how to fill a graph with data. It creates a complete graph on 4 nodes. The type Listgraph is one of the LEMON graph types: the typedefs in the beginning are for convenience and we will suppose them later as well.
2.20 +<ol>
2.21 +<li>The following code fragment shows how to fill a graph with data. It creates a complete graph on 4 nodes. The type Listgraph is one of the LEMON graph types: the typedefs in the beginning are for convenience and we will suppose them later as well.
2.22 \code
2.23 typedef ListGraph Graph;
2.24 typedef Graph::NodeIt NodeIt;
2.25 @@ -42,9 +46,9 @@
2.26
2.27 See the whole program in file \ref helloworld.cc.
2.28
2.29 -If you want to read more on the LEMON graph structures and concepts, read the page about \ref graphs "graphs".
2.30 + If you want to read more on the LEMON graph structures and concepts, read the page about \ref graphs "graphs".
2.31
2.32 --# The following code shows how to read a graph from a stream (e.g. a file). LEMON supports the DIMACS file format: it can read a graph instance from a file
2.33 +<li> The following code shows how to read a graph from a stream (e.g. a file). LEMON supports the DIMACS file format: it can read a graph instance from a file
2.34 in that format (find the documentation of the DIMACS file format on the web).
2.35 \code
2.36 Graph g;
2.37 @@ -53,8 +57,8 @@
2.38 \endcode
2.39 One can also store network (graph+capacity on the edges) instances and other things in DIMACS format and use these in LEMON: to see the details read the documentation of the \ref dimacs.h "Dimacs file format reader".
2.40
2.41 -
2.42 -- If you want to solve some transportation problems in a network then
2.43 +</ol>
2.44 +<li> If you want to solve some transportation problems in a network then
2.45 you will want to find shortest paths between nodes of a graph. This is
2.46 usually solved using Dijkstra's algorithm. A utility
2.47 that solves this is the \ref lemon::Dijkstra "LEMON Dijkstra class".
2.48 @@ -129,7 +133,7 @@
2.49 by step and gain full control of the execution. For a detailed description, see the documentation of the \ref lemon::Dijkstra "LEMON Dijkstra class".
2.50
2.51
2.52 -- If you want to design a network and want to minimize the total length
2.53 +<li> If you want to design a network and want to minimize the total length
2.54 of wires then you might be looking for a <b>minimum spanning tree</b> in
2.55 an undirected graph. This can be found using the Kruskal algorithm: the
2.56 class \ref lemon::Kruskal "LEMON Kruskal class" does this job for you.
2.57 @@ -137,11 +141,73 @@
2.58
2.59 Ide Zsuzska fog irni!
2.60
2.61 --
2.62 +<li>Many problems in network optimization can be formalized by means of a
2.63 +linear programming problem (LP problem, for short). In our library we decided
2.64 +not to write an LP solver, since such packages are available in the commercial
2.65 +world just as well as in the open source world, and it is also a difficult
2.66 +task to compete these. Instead we decided to develop an interface that makes
2.67 +it easier to use these solvers together with LEMON. So far we have an
2.68 +interface for the commercial LP solver software \b CLPLEX (developed by ILOG)
2.69 +and for the open source solver \b GLPK (a shorthand for Gnu Linear Programming
2.70 +Toolkit).
2.71 +
2.72 +We will show two examples, the first one shows how simple it is to formalize
2.73 +and solve an LP problem in LEMON, while the second one shows how LEMON
2.74 +facilitates solving network optimization problems using LP solvers.
2.75 +
2.76 +<ol>
2.77 +<li>The following code shows how to solve an LP problem using the LEMON lp
2.78 +interface.
2.79
2.80 \code
2.81
2.82 + //A default solver is taken
2.83 + LpDefault lp;
2.84 + typedef LpDefault::Row Row;
2.85 + typedef LpDefault::Col Col;
2.86 +
2.87 +
2.88 + //This will be a maximization
2.89 + lp.max();
2.90 +
2.91 + //We add coloumns (variables) to our problem
2.92 + Col x1 = lp.addCol();
2.93 + Col x2 = lp.addCol();
2.94 + Col x3 = lp.addCol();
2.95 +
2.96 + //Constraints
2.97 + lp.addRow(x1+x2+x3 <=100);
2.98 + lp.addRow(10*x1+4*x2+5*x3<=600);
2.99 + lp.addRow(2*x1+2*x2+6*x3<=300);
2.100 + //Nonnegativity of the variables
2.101 + lp.colLowerBound(x1, 0);
2.102 + lp.colLowerBound(x2, 0);
2.103 + lp.colLowerBound(x3, 0);
2.104 + //Objective function
2.105 + lp.setObj(10*x1+6*x2+4*x3);
2.106 +
2.107 + //Call the routine of the underlying LP solver
2.108 + lp.solve();
2.109 +
2.110 + //Print results
2.111 + if (lp.primalStatus()==LpSolverBase::OPTIMAL){
2.112 + printf("Z = %g; x1 = %g; x2 = %g; x3 = %g\n",
2.113 + lp.primalValue(),
2.114 + lp.primal(x1), lp.primal(x2), lp.primal(x3));
2.115 + }
2.116 + else{
2.117 + std::cout<<"Optimal solution not found!"<<std::endl;
2.118 + }
2.119 +
2.120 +
2.121 \endcode
2.122
2.123 +See the whole code in \ref lp_demo.cc.
2.124 +
2.125 +<li>The second example shows how easy it is to formalize a network
2.126 +optimization problem as an LP problem using the LEMON LP interface.
2.127 +
2.128 +</ol>
2.129 +</ul>
2.130
2.131 */