1.1 --- a/doc/quicktour.dox Mon Jul 04 07:51:57 2005 +0000
1.2 +++ b/doc/quicktour.dox Mon Jul 04 13:08:31 2005 +0000
1.3 @@ -42,21 +42,38 @@
1.4 file format that gives a more flexible way to store data related to network
1.5 optimization.
1.6
1.7 -<ol> <li>The following code fragment shows how to fill a graph with
1.8 -data. It creates a complete graph on 4 nodes. The type Listgraph is one of the
1.9 -LEMON graph types: the typedefs in the beginning are for convenience and we
1.10 -will suppose them later as well.
1.11 +<ol> <li>The following code shows how to build a graph from scratch
1.12 +and iterate on its nodes and edges. This example also shows how to
1.13 +give a map on the edges of the graph. The type Listgraph is one of
1.14 +the LEMON graph types: the typedefs in the beginning are for
1.15 +convenience and we will assume them later as well.
1.16
1.17 -\dontinclude hello_lemon.cc
1.18 -\skip ListGraph
1.19 -\until addEdge
1.20 +\include hello_lemon.cc
1.21
1.22 -See the whole program in file \ref hello_lemon.cc in \c demo subdir of
1.23 +See the whole program in file \ref hello_lemon.cc in the \c demo subdir of
1.24 LEMON package.
1.25
1.26 If you want to read more on the LEMON graph structures and
1.27 concepts, read the page about \ref graphs "graphs".
1.28
1.29 +
1.30 +<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
1.31 +short example file in this format: read the detailed description of the LEMON
1.32 +graph file format and input-output routines here: \ref graph-io-page.
1.33 +
1.34 +So here is a file describing a graph of 6 nodes (0 to 5), two nodemaps
1.35 +(called \c coordinates_x and \c coordinates_y), several edges, an edge map
1.36 +called \c capacity and two designated nodes (called \c source and \c target).
1.37 +
1.38 +\include sample.lgf
1.39 +
1.40 +Finally let us give a simple example that reads a graph from a file and writes
1.41 +it to the standard output.
1.42 +
1.43 +\include reader_writer_demo.cc
1.44 +
1.45 +See the whole program in file \ref reader_writer_demo.cc.
1.46 +
1.47 <li> The following code shows how to read a graph from a stream
1.48 (e.g. a file) in the DIMACS file format (find the documentation of the
1.49 DIMACS file formats on the web).
1.50 @@ -73,49 +90,30 @@
1.51 \ref dimacs.h "Dimacs file format reader". There you will also find
1.52 the details about the output routines into files of the DIMACS format.
1.53
1.54 -<li>DIMACS formats could not give us the flexibility we needed,
1.55 -so we worked out our own file format. Instead of any explanation let us give a
1.56 -short example file in this format: read the detailed description of the LEMON
1.57 -graph file format and input-output routines \ref graph-io-page here.
1.58 -
1.59 -So here is a file describing a graph of 10 nodes (0 to 9), two nodemaps
1.60 -(called \c coordinates_x and \c coordinates_y), several edges, an edge map
1.61 -called \c length and two designated nodes (called \c source and \c target).
1.62 -
1.63 -\todo Maybe a shorter example would be better here.
1.64 -
1.65 -\include route.lgf
1.66 -
1.67 -Finally let us give a simple example that reads a graph from a file and writes
1.68 -it to the standard output.
1.69 -
1.70 -\include reader_writer_demo.cc
1.71 -
1.72 -See the whole program in file \ref reader_writer_demo.cc.
1.73 -
1.74 -\todo This is still under construction!
1.75 -
1.76 </ol>
1.77 <li> If you want to solve some transportation problems in a network then
1.78 you will want to find shortest paths between nodes of a graph. This is
1.79 usually solved using Dijkstra's algorithm. A utility
1.80 that solves this is the \ref lemon::Dijkstra "LEMON Dijkstra class".
1.81 The following code is a simple program using the
1.82 -\ref lemon::Dijkstra "LEMON Dijkstra class" and it also shows how to define a map on the edges (the length
1.83 -function):
1.84 +\ref lemon::Dijkstra "LEMON Dijkstra class": it calculates the shortest path between node \c s and \c t in a graph \c g.
1.85 +We omit the part reading the graph \c g and the length map \c len.
1.86
1.87 \dontinclude dijkstra_demo.cc
1.88 \skip ListGraph
1.89 +\until Graph g
1.90 +...
1.91 +\skip Dijkstra algorithm
1.92 \until std::cout << g.id(s)
1.93
1.94 See the whole program in \ref dijkstra_demo.cc.
1.95
1.96 -The first part of the code is self-explanatory: we build the graph and set the
1.97 -length values of the edges. Then we instantiate a member of the Dijkstra class
1.98 -and run the Dijkstra algorithm from node \c s. After this we read some of the
1.99 -results.
1.100 -You can do much more with the Dijkstra class, for example you can run it step
1.101 -by step and gain full control of the execution. For a detailed description, see the documentation of the \ref lemon::Dijkstra "LEMON Dijkstra class".
1.102 +Some explanation: after instantiating a member of the Dijkstra class
1.103 +we run the Dijkstra algorithm from node \c s. After this we read some
1.104 +of the results. You can do much more with the Dijkstra class, for
1.105 +example you can run it step by step and gain full control of the
1.106 +execution. For a detailed description, see the documentation of the
1.107 +\ref lemon::Dijkstra "LEMON Dijkstra class".
1.108
1.109
1.110 <li> If you want to design a network and want to minimize the total length
1.111 @@ -154,48 +152,9 @@
1.112 <li>The following code shows how to solve an LP problem using the LEMON lp
1.113 interface. The code together with the comments is self-explanatory.
1.114
1.115 -\code
1.116 -
1.117 - //A default solver is taken
1.118 - LpDefault lp;
1.119 - typedef LpDefault::Row Row;
1.120 - typedef LpDefault::Col Col;
1.121 -
1.122 -
1.123 - //This will be a maximization
1.124 - lp.max();
1.125 -
1.126 - //We add coloumns (variables) to our problem
1.127 - Col x1 = lp.addCol();
1.128 - Col x2 = lp.addCol();
1.129 - Col x3 = lp.addCol();
1.130 -
1.131 - //Constraints
1.132 - lp.addRow(x1+x2+x3 <=100);
1.133 - lp.addRow(10*x1+4*x2+5*x3<=600);
1.134 - lp.addRow(2*x1+2*x2+6*x3<=300);
1.135 - //Nonnegativity of the variables
1.136 - lp.colLowerBound(x1, 0);
1.137 - lp.colLowerBound(x2, 0);
1.138 - lp.colLowerBound(x3, 0);
1.139 - //Objective function
1.140 - lp.setObj(10*x1+6*x2+4*x3);
1.141 -
1.142 - //Call the routine of the underlying LP solver
1.143 - lp.solve();
1.144 -
1.145 - //Print results
1.146 - if (lp.primalStatus()==LpSolverBase::OPTIMAL){
1.147 - printf("Z = %g; x1 = %g; x2 = %g; x3 = %g\n",
1.148 - lp.primalValue(),
1.149 - lp.primal(x1), lp.primal(x2), lp.primal(x3));
1.150 - }
1.151 - else{
1.152 - std::cout<<"Optimal solution not found!"<<std::endl;
1.153 - }
1.154 -
1.155 -
1.156 -\endcode
1.157 +\dontinclude lp_demo.cc
1.158 +\skip A default solver is taken
1.159 +\until End of LEMON style code
1.160
1.161 See the whole code in \ref lp_demo.cc.
1.162
1.163 @@ -210,42 +169,13 @@
1.164 the capacity map \c cap, the source node \c s and the target node \c t
1.165 in the memory. We will also omit the typedefs.
1.166
1.167 -\code
1.168 - //Define a map on the edges for the variables of the LP problem
1.169 - typename G::template EdgeMap<LpDefault::Col> x(g);
1.170 - lp.addColSet(x);
1.171 -
1.172 - //Nonnegativity and capacity constraints
1.173 - for(EdgeIt e(g);e!=INVALID;++e) {
1.174 - lp.colUpperBound(x[e],cap[e]);
1.175 - lp.colLowerBound(x[e],0);
1.176 - }
1.177 +\dontinclude lp_maxflow_demo.cc
1.178 +\skip Define a map on the edges for the variables of the LP problem
1.179 +\until lp.max();
1.180 +\skip Solve with the underlying solver
1.181 +\until lp.solve();
1.182
1.183
1.184 - //Flow conservation constraints for the nodes (except for 's' and 't')
1.185 - for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
1.186 - LpDefault::Expr ex;
1.187 - for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e];
1.188 - for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
1.189 - lp.addRow(ex==0);
1.190 - }
1.191 -
1.192 - //Objective function: the flow value entering 't'
1.193 - {
1.194 - LpDefault::Expr ex;
1.195 - for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e];
1.196 - for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
1.197 - lp.setObj(ex);
1.198 - }
1.199 -
1.200 - //Maximization
1.201 - lp.max();
1.202 -
1.203 - //Solve with the underlying solver
1.204 - lp.solve();
1.205 -
1.206 -\endcode
1.207 -
1.208 The complete program can be found in file \ref lp_maxflow_demo.cc. After compiling run it in the form:
1.209
1.210 <tt>./lp_maxflow_demo < sample.lgf</tt>