lemon-0.x: comparison doc/quicktour.dox

equal deleted inserted replaced

-:403f8709498b
+:f18f7b06179c
 (file): this will also be shown. LEMON supports the DIMACS file formats to
 store network optimization problems, but more importantly we also have our own
 file format that gives a more flexible way to store data related to network
 optimization.
-<ol> <li>The following code fragment shows how to fill a graph with
+<ol> <li>The following code shows how to build a graph from scratch
-data. It creates a complete graph on 4 nodes. The type Listgraph is one of the
+and iterate on its nodes and edges.  This example also shows how to
-LEMON graph types: the typedefs in the beginning are for convenience and we
+give a map on the edges of the graph.  The type Listgraph is one of
-will suppose them later as well.
+the LEMON graph types: the typedefs in the beginning are for
+convenience and we will assume them later as well.
-\dontinclude hello_lemon.cc
+\include hello_lemon.cc
-\skip ListGraph
-\until addEdge
-See the whole program in file \ref hello_lemon.cc in \c demo subdir of
+See the whole program in file \ref hello_lemon.cc in the \c demo subdir of
 LEMON package.
 If you want to read more on the LEMON graph structures and
 concepts, read the page about \ref graphs "graphs".
+<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
+short example file in this format: read the detailed description of the LEMON
+graph file format and input-output routines here: \ref graph-io-page.
+So here is a file describing a graph of 6 nodes (0 to 5), two nodemaps
+(called \c coordinates_x and \c coordinates_y), several edges, an edge map
+called \c capacity and two designated nodes (called \c source and \c target).
+\include sample.lgf
+Finally let us give a simple example that reads a graph from a file and writes
+it to the standard output.
+\include reader_writer_demo.cc
+See the whole program in file \ref reader_writer_demo.cc.
 <li> The following code shows how to read a graph from a stream
 (e.g. a file) in the DIMACS file format (find the documentation of the
 DIMACS file formats on the web).
 other things (minimum cost flow instances etc.) in DIMACS format and
 use these in LEMON: to see the details read the documentation of the
 \ref dimacs.h "Dimacs file format reader". There you will also find
 the details about the output routines into files of the DIMACS format.
-<li>DIMACS formats could not give us the flexibility we needed,
-so we worked out our own file format. Instead of any explanation let us give a
-short example file in this format: read the detailed description of the LEMON
-graph file format and input-output routines \ref graph-io-page here.
-So here is a file describing a graph of 10 nodes (0 to 9), two nodemaps
-(called \c coordinates_x and \c coordinates_y), several edges, an edge map
-called \c length and two designated nodes (called \c source and \c target).
-\todo Maybe a shorter example would be better here.
-\include route.lgf
-Finally let us give a simple example that reads a graph from a file and writes
-it to the standard output.
-\include reader_writer_demo.cc
-See the whole program in file \ref reader_writer_demo.cc.
-\todo This is still under construction!
 </ol>
 <li> If you want to solve some transportation problems in a network then
 you will want to find shortest paths between nodes of a graph. This is
 usually solved using Dijkstra's algorithm. A utility
 that solves this is  the \ref lemon::Dijkstra "LEMON Dijkstra class".
 The following code is a simple program using the
-\ref lemon::Dijkstra "LEMON Dijkstra class" and it also shows how to define a map on the edges (the length
+\ref lemon::Dijkstra "LEMON Dijkstra class": it calculates the shortest path between node \c s and \c t in a graph \c g.
-function):
+We omit the part reading the graph  \c g and the length map \c len.
 \dontinclude dijkstra_demo.cc
 \skip ListGraph
+\until Graph g
+...
+\skip Dijkstra algorithm
 \until std::cout << g.id(s)
 See the whole program in \ref dijkstra_demo.cc.
-The first part of the code is self-explanatory: we build the graph and set the
+Some explanation: after instantiating a member of the Dijkstra class
-length values of the edges. Then we instantiate a member of the Dijkstra class
+we run the Dijkstra algorithm from node \c s. After this we read some
-and run the Dijkstra algorithm from node \c s. After this we read some of the
+of the results.  You can do much more with the Dijkstra class, for
-results.
+example you can run it step by step and gain full control of the
-You can do much more with the Dijkstra class, for example you can run it step
+execution. For a detailed description, see the documentation of the
-by step and gain full control of the execution. For a detailed description, see the documentation of the \ref lemon::Dijkstra "LEMON Dijkstra class".
+\ref lemon::Dijkstra "LEMON Dijkstra class".
 <li> If you want to design a network and want to minimize the total length
 of wires then you might be looking for a <b>minimum spanning tree</b> in
 an undirected graph. This can be found using the Kruskal algorithm: the
 <ol>
 <li>The following code shows how to solve an LP problem using the LEMON lp
 interface. The code together with the comments is self-explanatory.
-\code
+\dontinclude lp_demo.cc
+\skip A default solver is taken
-//A default solver is taken
+\until End of LEMON style code
-LpDefault lp;
-typedef LpDefault::Row Row;
-typedef LpDefault::Col Col;
-//This will be a maximization
-lp.max();
-//We add coloumns (variables) to our problem
-Col x1 = lp.addCol();
-Col x2 = lp.addCol();
-Col x3 = lp.addCol();
-//Constraints
-lp.addRow(x1+x2+x3 <=100);
-lp.addRow(10*x1+4*x2+5*x3<=600);
-lp.addRow(2*x1+2*x2+6*x3<=300);
-//Nonnegativity of the variables
-lp.colLowerBound(x1, 0);
-lp.colLowerBound(x2, 0);
-lp.colLowerBound(x3, 0);
-//Objective function
-lp.setObj(10*x1+6*x2+4*x3);
-//Call the routine of the underlying LP solver
-lp.solve();
-//Print results
-if (lp.primalStatus()==LpSolverBase::OPTIMAL){
-printf("Z = %g; x1 = %g; x2 = %g; x3 = %g\n",
-	   lp.primalValue(),
-	   lp.primal(x1), lp.primal(x2), lp.primal(x3));
-}
-else{
-std::cout<<"Optimal solution not found!"<<std::endl;
-}
-\endcode
 See the whole code in \ref lp_demo.cc.
 <li>The second example shows how easy it is to formalize a max-flow
 problem as an LP problem using the LEMON LP interface: we are looking
 In the following code we suppose that we already have the graph \c g,
 the capacity map \c cap, the source node \c s and the target node \c t
 in the memory. We will also omit the typedefs.
-\code
+\dontinclude lp_maxflow_demo.cc
-//Define a map on the edges for the variables of the LP problem
+\skip Define a map on the edges for the variables of the LP problem
-typename G::template EdgeMap<LpDefault::Col> x(g);
+\until lp.max();
-lp.addColSet(x);
+\skip Solve with the underlying solver
+\until lp.solve();
-//Nonnegativity and capacity constraints
-for(EdgeIt e(g);e!=INVALID;++e) {
-lp.colUpperBound(x[e],cap[e]);
-lp.colLowerBound(x[e],0);
-}
-//Flow conservation constraints for the nodes (except for 's' and 't')
-for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
-LpDefault::Expr ex;
-for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
-for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
-lp.addRow(ex==0);
-}
-//Objective function: the flow value entering 't'
-{
-LpDefault::Expr ex;
-for(InEdgeIt  e(g,t);e!=INVALID;++e) ex+=x[e];
-for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
-lp.setObj(ex);
-}
-//Maximization
-lp.max();
-//Solve with the underlying solver
-lp.solve();
-\endcode
 The complete program can be found in file \ref lp_maxflow_demo.cc. After compiling run it in the form:
 <tt>./lp_maxflow_demo < sample.lgf</tt>

changeset 1533	43c7b3085212
parent 1528	1aa71600000c
child 1534	b86aad11f842