COIN-OR::LEMON - Graph Library

Changeset 1530:d99c3c84f797 in lemon-0.x for doc


Ignore:
Timestamp:
07/04/05 15:08:31 (19 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2021
Message:

Doc.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/quicktour.dox

    r1528 r1530  
    4343optimization.
    4444
    45 <ol> <li>The following code fragment shows how to fill a graph with
    46 data. It creates a complete graph on 4 nodes. The type Listgraph is one of the
    47 LEMON graph types: the typedefs in the beginning are for convenience and we
    48 will suppose them later as well. 
     45<ol> <li>The following code shows how to build a graph from scratch
     46and iterate on its nodes and edges.  This example also shows how to
     47give a map on the edges of the graph.  The type Listgraph is one of
     48the LEMON graph types: the typedefs in the beginning are for
     49convenience and we will assume them later as well.
    4950
    50 \dontinclude hello_lemon.cc
    51 \skip ListGraph
    52 \until addEdge
     51\include hello_lemon.cc
    5352
    54 See the whole program in file \ref hello_lemon.cc in \c demo subdir of
     53See the whole program in file \ref hello_lemon.cc in the \c demo subdir of
    5554LEMON package.
    5655
    5756    If you want to read more on the LEMON graph structures and
    5857concepts, read the page about \ref graphs "graphs".
     58
     59
     60<li>LEMON has an own file format for storing graphs, maps on edges/nodes and some other things. Instead of any explanation let us give a
     61short example file in this format: read the detailed description of the LEMON
     62graph file format and input-output routines here: \ref graph-io-page.
     63
     64So here is a file describing a graph of 6 nodes (0 to 5), two nodemaps
     65(called \c coordinates_x and \c coordinates_y), several edges, an edge map
     66called \c capacity and two designated nodes (called \c source and \c target).
     67
     68\include sample.lgf
     69
     70Finally let us give a simple example that reads a graph from a file and writes
     71it to the standard output.
     72
     73\include reader_writer_demo.cc
     74
     75See the whole program in file \ref reader_writer_demo.cc.
    5976
    6077<li> The following code shows how to read a graph from a stream
     
    7491the details about the output routines into files of the DIMACS format.
    7592
    76 <li>DIMACS formats could not give us the flexibility we needed,
    77 so we worked out our own file format. Instead of any explanation let us give a
    78 short example file in this format: read the detailed description of the LEMON
    79 graph file format and input-output routines \ref graph-io-page here.
    80 
    81 So here is a file describing a graph of 10 nodes (0 to 9), two nodemaps
    82 (called \c coordinates_x and \c coordinates_y), several edges, an edge map
    83 called \c length and two designated nodes (called \c source and \c target).
    84 
    85 \todo Maybe a shorter example would be better here.
    86 
    87 \include route.lgf
    88 
    89 Finally let us give a simple example that reads a graph from a file and writes
    90 it to the standard output.
    91 
    92 \include reader_writer_demo.cc
    93 
    94 See the whole program in file \ref reader_writer_demo.cc.
    95 
    96 \todo This is still under construction!
    97 
    9893</ol>
    9994<li> If you want to solve some transportation problems in a network then
     
    10297that solves this is  the \ref lemon::Dijkstra "LEMON Dijkstra class".
    10398The following code is a simple program using the
    104 \ref lemon::Dijkstra "LEMON Dijkstra class" and it also shows how to define a map on the edges (the length
    105 function):
     99\ref lemon::Dijkstra "LEMON Dijkstra class": it calculates the shortest path between node \c s and \c t in a graph \c g.
     100We omit the part reading the graph  \c g and the length map \c len.
    106101
    107102\dontinclude dijkstra_demo.cc
    108103\skip ListGraph
     104\until Graph g
     105...
     106\skip Dijkstra algorithm
    109107\until std::cout << g.id(s)
    110108
    111109See the whole program in \ref dijkstra_demo.cc.
    112110
    113 The first part of the code is self-explanatory: we build the graph and set the
    114 length values of the edges. Then we instantiate a member of the Dijkstra class
    115 and run the Dijkstra algorithm from node \c s. After this we read some of the
    116 results.
    117 You can do much more with the Dijkstra class, for example you can run it step
    118 by step and gain full control of the execution. For a detailed description, see the documentation of the \ref lemon::Dijkstra "LEMON Dijkstra class".
     111Some explanation: after instantiating a member of the Dijkstra class
     112we run the Dijkstra algorithm from node \c s. After this we read some
     113of the results.  You can do much more with the Dijkstra class, for
     114example you can run it step by step and gain full control of the
     115execution. For a detailed description, see the documentation of the
     116\ref lemon::Dijkstra "LEMON Dijkstra class".
    119117
    120118
     
    155153interface. The code together with the comments is self-explanatory.
    156154
    157 \code
    158 
    159   //A default solver is taken
    160   LpDefault lp;
    161   typedef LpDefault::Row Row;
    162   typedef LpDefault::Col Col;
    163  
    164 
    165   //This will be a maximization
    166   lp.max();
    167 
    168   //We add coloumns (variables) to our problem
    169   Col x1 = lp.addCol();
    170   Col x2 = lp.addCol();
    171   Col x3 = lp.addCol();
    172 
    173   //Constraints
    174   lp.addRow(x1+x2+x3 <=100); 
    175   lp.addRow(10*x1+4*x2+5*x3<=600); 
    176   lp.addRow(2*x1+2*x2+6*x3<=300); 
    177   //Nonnegativity of the variables
    178   lp.colLowerBound(x1, 0);
    179   lp.colLowerBound(x2, 0);
    180   lp.colLowerBound(x3, 0);
    181   //Objective function
    182   lp.setObj(10*x1+6*x2+4*x3);
    183  
    184   //Call the routine of the underlying LP solver
    185   lp.solve();
    186 
    187   //Print results
    188   if (lp.primalStatus()==LpSolverBase::OPTIMAL){
    189     printf("Z = %g; x1 = %g; x2 = %g; x3 = %g\n",
    190            lp.primalValue(),
    191            lp.primal(x1), lp.primal(x2), lp.primal(x3));
    192   }
    193   else{
    194     std::cout<<"Optimal solution not found!"<<std::endl;
    195   }
    196 
    197 
    198 \endcode
     155\dontinclude lp_demo.cc
     156\skip A default solver is taken
     157\until End of LEMON style code
    199158
    200159See the whole code in \ref lp_demo.cc.
     
    211170in the memory. We will also omit the typedefs.
    212171
    213 \code
    214   //Define a map on the edges for the variables of the LP problem
    215   typename G::template EdgeMap<LpDefault::Col> x(g);
    216   lp.addColSet(x);
    217  
    218   //Nonnegativity and capacity constraints
    219   for(EdgeIt e(g);e!=INVALID;++e) {
    220     lp.colUpperBound(x[e],cap[e]);
    221     lp.colLowerBound(x[e],0);
    222   }
     172\dontinclude lp_maxflow_demo.cc
     173\skip Define a map on the edges for the variables of the LP problem
     174\until lp.max();
     175\skip Solve with the underlying solver
     176\until lp.solve();
    223177
    224 
    225   //Flow conservation constraints for the nodes (except for 's' and 't')
    226   for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
    227     LpDefault::Expr ex;
    228     for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
    229     for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
    230     lp.addRow(ex==0);
    231   }
    232  
    233   //Objective function: the flow value entering 't'
    234   {
    235     LpDefault::Expr ex;
    236     for(InEdgeIt  e(g,t);e!=INVALID;++e) ex+=x[e];
    237     for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
    238     lp.setObj(ex);
    239   }
    240 
    241   //Maximization
    242   lp.max();
    243 
    244   //Solve with the underlying solver
    245   lp.solve();
    246 
    247 \endcode
    248178
    249179The complete program can be found in file \ref lp_maxflow_demo.cc. After compiling run it in the form:
Note: See TracChangeset for help on using the changeset viewer.