diff -r c914e7ec2b7b -r d99c3c84f797 doc/quicktour.dox --- a/doc/quicktour.dox Mon Jul 04 07:51:57 2005 +0000 +++ b/doc/quicktour.dox Mon Jul 04 13:08:31 2005 +0000 @@ -42,21 +42,38 @@ file format that gives a more flexible way to store data related to network optimization. -
  1. 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. +
    1. The following code shows how to build a graph from scratch +and iterate on its nodes and edges. This example also shows how to +give a map on the edges of the graph. The type Listgraph is one of +the LEMON graph types: the typedefs in the beginning are for +convenience and we will assume them later as well. -\dontinclude hello_lemon.cc -\skip ListGraph -\until addEdge +\include hello_lemon.cc -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". + +
    2. 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. +
    3. 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). @@ -73,49 +90,30 @@ \ref dimacs.h "Dimacs file format reader". There you will also find the details about the output routines into files of the DIMACS format. -
    4. 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! -
  2. 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 -function): +\ref lemon::Dijkstra "LEMON Dijkstra class": it calculates the shortest path between node \c s and \c t in a graph \c g. +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 -length values of the edges. Then we instantiate a member of the Dijkstra class -and run the Dijkstra algorithm from node \c s. After this we read some of the -results. -You can do much more with the Dijkstra class, for example you can run it step -by step and gain full control of the execution. For a detailed description, see the documentation of the \ref lemon::Dijkstra "LEMON Dijkstra class". +Some explanation: after instantiating a member of the Dijkstra class +we run the Dijkstra algorithm from node \c s. After this we read some +of the results. You can do much more with the Dijkstra class, for +example you can run it step by step and gain full control of the +execution. For a detailed description, see the documentation of the +\ref lemon::Dijkstra "LEMON Dijkstra class".
  3. If you want to design a network and want to minimize the total length @@ -154,48 +152,9 @@
  4. 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 - - //A default solver is taken - 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!"< x(g); - lp.addColSet(x); - - //Nonnegativity and capacity constraints - for(EdgeIt e(g);e!=INVALID;++e) { - lp.colUpperBound(x[e],cap[e]); - lp.colLowerBound(x[e],0); - } +\dontinclude lp_maxflow_demo.cc +\skip Define a map on the edges for the variables of the LP problem +\until lp.max(); +\skip Solve with the underlying solver +\until lp.solve(); - //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: ./lp_maxflow_demo < sample.lgf