COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/quicktour.dox @ 1526:8c14aa8f27a2

Last change on this file since 1526:8c14aa8f27a2 was 1526:8c14aa8f27a2, checked in by athos, 14 years ago

Mainly doc review.

File size: 11.5 KB
Line 
1/**
2
3\page quicktour Quick Tour to LEMON
4
5Let us first answer the question <b>"What do I want to use LEMON for?"
6</b>.
7LEMON is a C++ library, so you can use it if you want to write C++
8programs. What kind of tasks does the library LEMON help to solve?
9It helps to write programs that solve optimization problems that arise
10frequently when <b>designing and testing certain networks</b>, for example
11in telecommunication, computer networks, and other areas that I cannot
12think of now. A very natural way of modelling these networks is by means
13of a <b> graph</b> (we will always mean a directed graph by that and say
14<b> undirected graph </b> otherwise).
15So if you want to write a program that works with
16graphs then you might find it useful to use our library LEMON. LEMON
17defines various graph concepts depending on what you want to do with the
18graph: a very good description can be found in the page
19about \ref graphs "graphs".
20
21You will also want to assign data to the edges or nodes of the graph, for
22example a length or capacity function defined on the edges. You can do this in
23LEMON using so called \b maps. You can define a map on the nodes or on the edges of the graph and the value of the map (the range of the function) can be practically almost of any type. Read more about maps \ref maps-page "here".
24
25Some examples are the following (you will find links next to the code fragments that help to download full demo programs: save them on your computer and compile them according to the description in the page about \ref getsart How to start using LEMON):
26
27<ul> <li> The first thing to discuss is the way one can create data structures
28like graphs and maps in a program using LEMON.
29//There are more graph types
30//implemented in LEMON and you can implement your own graph type just as well:
31//read more about this in the already mentioned page on \ref graphs "graphs".
32
33First we show how to add nodes and edges to a graph manually. We will also
34define a map on the edges of the graph. After this we show the way one can
35read a graph (and perhaps maps on it) from a stream (e.g. a file). Of course
36we also have routines that write a graph (and perhaps maps) to a stream
37(file): this will also be shown. LEMON supports the DIMACS file formats to
38store network optimization problems, but more importantly we also have our own
39file format that gives a more flexible way to store data related to network
40optimization.
41
42<ol> <li>The following code fragment shows how to fill a graph with
43data. It creates a complete graph on 4 nodes. The type Listgraph is one of the
44LEMON graph types: the typedefs in the beginning are for convenience and we
45will suppose them later as well. 
46
47\dontinclude hello_lemon.cc
48\skip ListGraph
49\until addEdge
50
51See the whole program in file \ref hello_lemon.cc in \c demo subdir of
52LEMON package.
53
54    If you want to read more on the LEMON graph structures and
55concepts, read the page about \ref graphs "graphs".
56
57<li> The following code shows how to read a graph from a stream
58(e.g. a file) in the DIMACS file format (find the documentation of the
59DIMACS file formats on the web).
60
61\code
62Graph g;
63std::ifstream f("graph.dim");
64readDimacs(f, g);
65\endcode
66
67One can also store network (graph+capacity on the edges) instances and
68other things (minimum cost flow instances etc.) in DIMACS format and
69use these in LEMON: to see the details read the documentation of the
70\ref dimacs.h "Dimacs file format reader". There you will also find
71the details about the output routines into files of the DIMACS format.
72
73<li>DIMACS formats could not give us the flexibility we needed,
74so we worked out our own file format. Instead of any explanation let us give a
75short example file in this format: read the detailed description of the LEMON
76graph file format and input-output routines \ref graph-io-page here.
77
78So here is a file describing a graph of 10 nodes (0 to 9), two nodemaps
79(called \c coordinates_x and \c coordinates_y), several edges, an edge map
80called \c length and two designated nodes (called \c source and \c target).
81
82\todo Maybe another example would be better here.
83
84\code
85@nodeset
86id      coordinates_x   coordinates_y   
879       447.907 578.328
888       79.2573 909.464
897       878.677 960.04 
906       11.5504 938.413
915       327.398 815.035
924       427.002 954.002
933       148.549 753.748
942       903.889 326.476
951       408.248 577.327
960       189.239 92.5316
97@edgeset
98                length 
992       3       901.074
1008       5       270.85 
1016       9       601.553
1025       9       285.022
1039       4       408.091
1043       0       719.712
1057       5       612.836
1060       4       933.353
1075       0       778.871
1085       5       0       
1097       1       664.049
1105       5       0       
1110       9       560.464
1124       8       352.36 
1134       9       399.625
1144       1       402.171
1151       2       591.688
1163       8       182.376
1174       5       180.254
1183       1       345.283
1195       4       184.511
1206       2       1112.45
1210       1       556.624
122@nodes
123source  1       
124target  8       
125@end
126\endcode
127
128Finally let us give a simple example that reads a graph from a file and writes
129it to another.
130
131\todo This is to be done!
132
133</ol>
134<li> If you want to solve some transportation problems in a network then
135you will want to find shortest paths between nodes of a graph. This is
136usually solved using Dijkstra's algorithm. A utility
137that solves this is  the \ref lemon::Dijkstra "LEMON Dijkstra class".
138The following code is a simple program using the
139\ref lemon::Dijkstra "LEMON Dijkstra class" and it also shows how to define a map on the edges (the length
140function):
141
142\code
143
144    typedef ListGraph Graph;
145    typedef Graph::Node Node;
146    typedef Graph::Edge Edge;
147    typedef Graph::EdgeMap<int> LengthMap;
148
149    Graph g;
150
151    //An example from Ahuja's book
152
153    Node s=g.addNode();
154    Node v2=g.addNode();
155    Node v3=g.addNode();
156    Node v4=g.addNode();
157    Node v5=g.addNode();
158    Node t=g.addNode();
159
160    Edge s_v2=g.addEdge(s, v2);
161    Edge s_v3=g.addEdge(s, v3);
162    Edge v2_v4=g.addEdge(v2, v4);
163    Edge v2_v5=g.addEdge(v2, v5);
164    Edge v3_v5=g.addEdge(v3, v5);
165    Edge v4_t=g.addEdge(v4, t);
166    Edge v5_t=g.addEdge(v5, t);
167 
168    LengthMap len(g);
169
170    len.set(s_v2, 10);
171    len.set(s_v3, 10);
172    len.set(v2_v4, 5);
173    len.set(v2_v5, 8);
174    len.set(v3_v5, 5);
175    len.set(v4_t, 8);
176    len.set(v5_t, 8);
177
178    std::cout << "The id of s is " << g.id(s)<< std::endl;
179    std::cout <<"The id of t is " << g.id(t)<<"."<<std::endl;
180
181    std::cout << "Dijkstra algorithm test..." << std::endl;
182
183    Dijkstra<Graph, LengthMap> dijkstra_test(g,len);
184   
185    dijkstra_test.run(s);
186
187   
188    std::cout << "The distance of node t from node s: " << dijkstra_test.dist(t)<<std::endl;
189
190    std::cout << "The shortest path from s to t goes through the following nodes" <<std::endl;
191 std::cout << " (the first one is t, the last one is s): "<<std::endl;
192
193    for (Node v=t;v != s; v=dijkstra_test.predNode(v)){
194        std::cout << g.id(v) << "<-";
195    }
196    std::cout << g.id(s) << std::endl; 
197\endcode
198
199See the whole program in \ref dijkstra_demo.cc.
200
201The first part of the code is self-explanatory: we build the graph and set the
202length values of the edges. Then we instantiate a member of the Dijkstra class
203and run the Dijkstra algorithm from node \c s. After this we read some of the
204results.
205You can do much more with the Dijkstra class, for example you can run it step
206by step and gain full control of the execution. For a detailed description, see the documentation of the \ref lemon::Dijkstra "LEMON Dijkstra class".
207
208
209<li> If you want to design a network and want to minimize the total length
210of wires then you might be looking for a <b>minimum spanning tree</b> in
211an undirected graph. This can be found using the Kruskal algorithm: the
212class \ref lemon::Kruskal "LEMON Kruskal class" does this job for you.
213The following code fragment shows an example:
214
215Ide Zsuzska fog irni!
216
217<li>Many problems in network optimization can be formalized by means
218of a linear programming problem (LP problem, for short). In our
219library we decided not to write an LP solver, since such packages are
220available in the commercial world just as well as in the open source
221world, and it is also a difficult task to compete these. Instead we
222decided to develop an interface that makes it easier to use these
223solvers together with LEMON. The advantage of this approach is
224twofold. Firstly our C++ interface is more comfortable than the
225solvers' native interface. Secondly, changing the underlying solver in
226a certain software using LEMON's LP interface needs zero effort. So,
227for example, one may try his idea using a free solver, demonstrate its
228usability for a customer and if it works well, but the performance
229should be improved, then one may decide to purchase and use a better
230commercial solver.
231
232So far we have an
233interface for the commercial LP solver software \b CPLEX (developed by ILOG)
234and for the open source solver \b GLPK (a shorthand for Gnu Linear Programming
235Toolkit).
236
237We will show two examples, the first one shows how simple it is to formalize
238and solve an LP problem in LEMON, while the second one shows how LEMON
239facilitates solving network optimization problems using LP solvers.
240
241<ol>
242<li>The following code shows how to solve an LP problem using the LEMON lp
243interface. The code together with the comments is self-explanatory.
244
245\code
246
247  //A default solver is taken
248  LpDefault lp;
249  typedef LpDefault::Row Row;
250  typedef LpDefault::Col Col;
251 
252
253  //This will be a maximization
254  lp.max();
255
256  //We add coloumns (variables) to our problem
257  Col x1 = lp.addCol();
258  Col x2 = lp.addCol();
259  Col x3 = lp.addCol();
260
261  //Constraints
262  lp.addRow(x1+x2+x3 <=100); 
263  lp.addRow(10*x1+4*x2+5*x3<=600); 
264  lp.addRow(2*x1+2*x2+6*x3<=300); 
265  //Nonnegativity of the variables
266  lp.colLowerBound(x1, 0);
267  lp.colLowerBound(x2, 0);
268  lp.colLowerBound(x3, 0);
269  //Objective function
270  lp.setObj(10*x1+6*x2+4*x3);
271 
272  //Call the routine of the underlying LP solver
273  lp.solve();
274
275  //Print results
276  if (lp.primalStatus()==LpSolverBase::OPTIMAL){
277    printf("Z = %g; x1 = %g; x2 = %g; x3 = %g\n",
278           lp.primalValue(),
279           lp.primal(x1), lp.primal(x2), lp.primal(x3));
280  }
281  else{
282    std::cout<<"Optimal solution not found!"<<std::endl;
283  }
284
285
286\endcode
287
288See the whole code in \ref lp_demo.cc.
289
290<li>The second example shows how easy it is to formalize a max-flow
291problem as an LP problem using the LEMON LP interface: we are looking
292for a real valued function defined on the edges of the digraph
293satisfying the nonnegativity-, the capacity constraints and the
294flow-conservation constraints and giving the largest flow value
295between to designated nodes.
296
297In the following code we suppose that we already have the graph \c g,
298the capacity map \c cap, the source node \c s and the target node \c t
299in the memory. We will also omit the typedefs.
300
301\code
302  //Define a map on the edges for the variables of the LP problem
303  typename G::template EdgeMap<LpDefault::Col> x(g);
304  lp.addColSet(x);
305 
306  //Nonnegativity and capacity constraints
307  for(EdgeIt e(g);e!=INVALID;++e) {
308    lp.colUpperBound(x[e],cap[e]);
309    lp.colLowerBound(x[e],0);
310  }
311
312
313  //Flow conservation constraints for the nodes (except for 's' and 't')
314  for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
315    LpDefault::Expr ex;
316    for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
317    for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
318    lp.addRow(ex==0);
319  }
320 
321  //Objective function: the flow value entering 't'
322  {
323    LpDefault::Expr ex;
324    for(InEdgeIt  e(g,t);e!=INVALID;++e) ex+=x[e];
325    for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
326    lp.setObj(ex);
327  }
328
329  //Maximization
330  lp.max();
331
332  //Solve with the underlying solver
333  lp.solve();
334
335\endcode
336
337The complete program can be found in file \ref lp_maxflow_demo.cc. After compiling run it in the form:
338
339<tt>./lp_maxflow_demo < ?????????.lgf</tt>
340
341where ?????????.lgf is a file in the lemon format containing a maxflow instance (designated "source", "target" nodes and "capacity" map on the edges).
342
343
344
345</ol>
346</ul>
347
348*/
Note: See TracBrowser for help on using the repository browser.