COIN-OR::LEMON - Graph Library

Changeset 1514:c9b9bc63db4e in lemon-0.x


Ignore:
Timestamp:
06/24/05 23:03:08 (19 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1998
Message:

Improved getsart.dox and quicktour.dox

Location:
doc
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/getstart.dox

    r1511 r1514  
    44In this page we detail how to start using LEMON, from downloading it to
    55your computer, through the steps of installation to showing a simple
    6 "Hello World" type program that already uses LEMON. If anything is not
     6"Hello World" type program that already uses LEMON. We assume that you have a
     7basic knowledge of your operating system and \c C++ or \c C
     8programming language. If anything is not
    79clear write to our FAQ.
    810
     
    1012twice YES then a link comes here.
    1113
     14\section requirementsLEMON Hardware and software requirements
    1215
     16Hardware requirements ...
     17
     18You will also need a C++ compiler. We mostly used the Gnu C++ Compiler (g++),
     19from version 3.0 upwards. We also checked the Intel C compiler
     20(icc). Unfortunately, Visual C++ compiler knows not enough to compile the
     21library, so if you are using Microsoft Windows, then try to compile under
     22Cygwin.
     23
     24Ide kell írni:
     25 
     26-Hol fordul (Windows-os fordító nem fordítja, unix/linux alatt gcc hanyas verziója kell)
     27-
     28
     29In this description we will suppose a linux environment and Gnu C Compiler.
    1330
    1431\section downloadLEMON How to download LEMON
     
    1633You can download LEMON from the LEMON web site:
    1734http://lemon.cs.elte.hu
    18 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.
     35by following the download link. There you will find the issued distributions
     36in 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.
     37
    1938
    2039
     
    2342In order to install LEMON you have to do the following
    2443
    25 Download the tarball and issue the following commands:
     44Download the tarball (named <tt>lemon-x.y.z.tar.gz</tt> where \c x,\c y and \c z are
     45numbers indicating the version of the library: in our example we will have lemon-0.3.1) and issue the following commands:
    2646
    2747\code
     
    3454\endcode
    3555
    36 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.
     56These commands install LEMON under \c /usr/local (you will probably need \c root
     57privileges to be able to install to that directory). If you want to install it
     58to some other place, then pass the \c --prefix=DIR flag to \c ./configure. In
     59what follows we will assume that you were able to install to directory \c
     60/usr/local, otherwise some extra care is to be taken to use the library.
    3761
    38 Ide kell írni:
    39  
    40 -Hol fordul (Windows-os fordító nem fordítja, unix/linux alatt gcc hanyas verziója kell)
    41 -
     62We briefly explain these commands below.
     63
     64\code
     65tar xvzf lemon-0.3.1.tar.gz
     66\endcode
     67This command untars the <tt>tar.gz</tt> file into a directory named <tt> lemon-0.3.1</tt>.
     68
     69\code
     70cd lemon-0.3.1
     71\endcode
     72Enters the directory.
     73
     74\code
     75./configure
     76\endcode
     77Does some configuration (creates makefiles etc).
     78
     79\code
     80make
     81\endcode
     82This command compiles the <tt> .cc</tt> files of the library package (the
     83implementation of non-template functions and classes and some test and demo
     84programs) and creates the very important <b> libemon.la </b> file. When
     85linking your program that uses LEMON it needs to access this file.
     86
     87\code
     88make check (This is optional, but recomended. It runs a bunch of tests.)
     89\endcode
     90This is an optional step: it runs the test programs that we developed for
     91LEMON to check
     92whether the library works properly on your platform.
     93
     94\code
     95make install
     96\endcode
     97This will copy the directory structure to its final destination (e.g. to \c
     98/usr/local) so that your system can access it.
    4299
    43100\section helloworld My first program using LEMON
    44101
    45 If you have installed LEMON on your system you can paste the following code
     102If you have installed LEMON on your system you
     103can paste the following code
    46104segment into a file to have a first working program that uses library LEMON.
    47105
     
    55113{
    56114  typedef ListGraph Graph;
    57   typedef Graph::Edge Edge;
    58   typedef Graph::InEdgeIt InEdgeIt;
    59   typedef Graph::OutEdgeIt OutEdgeIt;
    60115  typedef Graph::EdgeIt EdgeIt;
    61   typedef Graph::Node Node;
    62116  typedef Graph::NodeIt NodeIt;
    63117
     
    83137\endcode
    84138
     139First let us briefly explain how this program works.
    85140
    86141ListGraph is one of LEMON's graph classes. It is based on linked lists,
     
    100155\c source member functions can be used to access the endpoints of an edge.
    101156
    102 The previous code fragment prints out the following:
     157If 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
     158successful then it is very easy to compile this program with the following
     159command (the argument <tt>-lemon</tt> tells the compiler that we are using the
     160installed library LEMON):
     161\code
     162g++ hemon.cc -o hemon -lemon
     163\endcode
     164
     165As a result you will get the exacutable \c hemon in
     166this directory that you can run by the command
     167\code
     168./hemon
     169\endcode
     170
     171
     172If everything has gone well then the previous code fragment prints out the following:
    103173
    104174\code
     
    108178\endcode
    109179
     180Congratulations!
    110181
    111182If you want to see more features, go to the \ref quicktour "Quick Tour to
  • doc/quicktour.dox

    r1511 r1514  
    1919about \ref graphs "graphs".
    2020
    21 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".
     21You will also want to assign data to the edges or nodes of the graph, for
     22example a length or capacity function defined on the edges. You can do this in
     23LEMON 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".
    2224
    2325Some 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):
    2426
    25 - First we give two examples that show how to instantiate a graph. The
     27<ul>
     28<li> First we give two examples that show how to instantiate a graph. The
    2629first one shows the methods that add nodes and edges, but one will
    2730usually use the second way which reads a graph from a stream (file).
    28 -# 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.
     31<ol>
     32<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.
    2933 \code
    3034  typedef ListGraph Graph;
     
    4347See the whole program in file \ref helloworld.cc.
    4448
    45 If you want to read more on the LEMON graph structures and concepts, read the page about \ref graphs "graphs".
    46 
    47 -# 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
     49    If you want to read more on the LEMON graph structures and concepts, read the page about \ref graphs "graphs".
     50
     51<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
    4852in that format (find the documentation of the DIMACS file format on the web).
    4953\code
     
    5458One 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".
    5559
    56 
    57 - If you want to solve some transportation problems in a network then
     60</ol>
     61<li> If you want to solve some transportation problems in a network then
    5862you will want to find shortest paths between nodes of a graph. This is
    5963usually solved using Dijkstra's algorithm. A utility
     
    130134
    131135
    132 - If you want to design a network and want to minimize the total length
     136<li> If you want to design a network and want to minimize the total length
    133137of wires then you might be looking for a <b>minimum spanning tree</b> in
    134138an undirected graph. This can be found using the Kruskal algorithm: the
     
    138142Ide Zsuzska fog irni!
    139143
    140 -
     144<li>Many problems in network optimization can be formalized by means of a
     145linear programming problem (LP problem, for short). In our library we decided
     146not to write an LP solver, since such packages are available in the commercial
     147world just as well as in the open source world, and it is also a difficult
     148task to compete these. Instead we decided to develop an interface that makes
     149it easier to use these solvers together with LEMON. So far we have an
     150interface for the commercial LP solver software \b CLPLEX (developed by ILOG)
     151and for the open source solver \b GLPK (a shorthand for Gnu Linear Programming
     152Toolkit).
     153
     154We will show two examples, the first one shows how simple it is to formalize
     155and solve an LP problem in LEMON, while the second one shows how LEMON
     156facilitates solving network optimization problems using LP solvers.
     157
     158<ol>
     159<li>The following code shows how to solve an LP problem using the LEMON lp
     160interface.
    141161
    142162\code
    143163
     164  //A default solver is taken
     165  LpDefault lp;
     166  typedef LpDefault::Row Row;
     167  typedef LpDefault::Col Col;
     168 
     169
     170  //This will be a maximization
     171  lp.max();
     172
     173  //We add coloumns (variables) to our problem
     174  Col x1 = lp.addCol();
     175  Col x2 = lp.addCol();
     176  Col x3 = lp.addCol();
     177
     178  //Constraints
     179  lp.addRow(x1+x2+x3 <=100); 
     180  lp.addRow(10*x1+4*x2+5*x3<=600); 
     181  lp.addRow(2*x1+2*x2+6*x3<=300); 
     182  //Nonnegativity of the variables
     183  lp.colLowerBound(x1, 0);
     184  lp.colLowerBound(x2, 0);
     185  lp.colLowerBound(x3, 0);
     186  //Objective function
     187  lp.setObj(10*x1+6*x2+4*x3);
     188 
     189  //Call the routine of the underlying LP solver
     190  lp.solve();
     191
     192  //Print results
     193  if (lp.primalStatus()==LpSolverBase::OPTIMAL){
     194    printf("Z = %g; x1 = %g; x2 = %g; x3 = %g\n",
     195           lp.primalValue(),
     196           lp.primal(x1), lp.primal(x2), lp.primal(x3));
     197  }
     198  else{
     199    std::cout<<"Optimal solution not found!"<<std::endl;
     200  }
     201
     202
    144203\endcode
    145204
     205See the whole code in \ref lp_demo.cc.
     206
     207<li>The second example shows how easy it is to formalize a network
     208optimization problem as an LP problem using the LEMON LP interface.
     209
     210</ol>
     211</ul>
    146212
    147213*/
Note: See TracChangeset for help on using the changeset viewer.