Changeset 1530:d99c3c84f797 in lemon0.x for doc
 Timestamp:
 07/04/05 15:08:31 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2021
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

doc/quicktour.dox
r1528 r1530 43 43 optimization. 44 44 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 46 and iterate on its nodes and edges. This example also shows how to 47 give a map on the edges of the graph. The type Listgraph is one of 48 the LEMON graph types: the typedefs in the beginning are for 49 convenience and we will assume them later as well. 49 50 50 \dontinclude hello_lemon.cc 51 \skip ListGraph 52 \until addEdge 51 \include hello_lemon.cc 53 52 54 See the whole program in file \ref hello_lemon.cc in \c demo subdir of53 See the whole program in file \ref hello_lemon.cc in the \c demo subdir of 55 54 LEMON package. 56 55 57 56 If you want to read more on the LEMON graph structures and 58 57 concepts, 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 61 short example file in this format: read the detailed description of the LEMON 62 graph file format and inputoutput routines here: \ref graphiopage. 63 64 So 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 66 called \c capacity and two designated nodes (called \c source and \c target). 67 68 \include sample.lgf 69 70 Finally let us give a simple example that reads a graph from a file and writes 71 it to the standard output. 72 73 \include reader_writer_demo.cc 74 75 See the whole program in file \ref reader_writer_demo.cc. 59 76 60 77 <li> The following code shows how to read a graph from a stream … … 74 91 the details about the output routines into files of the DIMACS format. 75 92 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 a78 short example file in this format: read the detailed description of the LEMON79 graph file format and inputoutput routines \ref graphiopage here.80 81 So here is a file describing a graph of 10 nodes (0 to 9), two nodemaps82 (called \c coordinates_x and \c coordinates_y), several edges, an edge map83 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.lgf88 89 Finally let us give a simple example that reads a graph from a file and writes90 it to the standard output.91 92 \include reader_writer_demo.cc93 94 See the whole program in file \ref reader_writer_demo.cc.95 96 \todo This is still under construction!97 98 93 </ol> 99 94 <li> If you want to solve some transportation problems in a network then … … 102 97 that solves this is the \ref lemon::Dijkstra "LEMON Dijkstra class". 103 98 The 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 length105 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. 100 We omit the part reading the graph \c g and the length map \c len. 106 101 107 102 \dontinclude dijkstra_demo.cc 108 103 \skip ListGraph 104 \until Graph g 105 ... 106 \skip Dijkstra algorithm 109 107 \until std::cout << g.id(s) 110 108 111 109 See the whole program in \ref dijkstra_demo.cc. 112 110 113 The first part of the code is selfexplanatory: 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".111 Some explanation: after instantiating a member of the Dijkstra class 112 we run the Dijkstra algorithm from node \c s. After this we read some 113 of the results. You can do much more with the Dijkstra class, for 114 example you can run it step by step and gain full control of the 115 execution. For a detailed description, see the documentation of the 116 \ref lemon::Dijkstra "LEMON Dijkstra class". 119 117 120 118 … … 155 153 interface. The code together with the comments is selfexplanatory. 156 154 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 199 158 200 159 See the whole code in \ref lp_demo.cc. … … 211 170 in the memory. We will also omit the typedefs. 212 171 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(); 223 177 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 //Maximization242 lp.max();243 244 //Solve with the underlying solver245 lp.solve();246 247 \endcode248 178 249 179 The 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.