COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/quicktour.dox @ 1522:321661278137

Last change on this file since 1522:321661278137 was 1522:321661278137, checked in by athos, 14 years ago

Some corrections to graph_io.dox (mainly language corrections). Improvements on quicktour.

File size: 11.6 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\code
48
49  typedef ListGraph Graph;
50  typedef Graph::NodeIt NodeIt;
51
52  Graph g;
53 
54  for (int i = 0; i < 3; i++)
55    g.addNode();
56 
57  for (NodeIt i(g); i!=INVALID; ++i)
58    for (NodeIt j(g); j!=INVALID; ++j)
59      if (i != j) g.addEdge(i, j);
60
61\endcode
62
63See the whole program in file \ref helloworld.cc.
64
65    If you want to read more on the LEMON graph structures and concepts, read the page about \ref graphs "graphs".
66
67<li> The following code shows how to read a graph from a stream (e.g. a file)
68in the DIMACS file format (find the documentation of the DIMACS file formats on the web).
69
70\code
71Graph g;
72std::ifstream f("graph.dim");
73readDimacs(f, g);
74\endcode
75
76One can also store network (graph+capacity on the edges) instances and other
77things (minimum cost flow instances etc.) in DIMACS format and use these in LEMON: to see the details read the
78documentation of the \ref dimacs.h "Dimacs file format reader". There you will
79also find the details about the output routines into files of the DIMACS
80format.
81
82<li>We needed much greater flexibility than the DIMACS formats could give us,
83so we worked out our own file format. Instead of any explanation let us give a
84short example file in this format: read the detailed description of the LEMON
85graph file format and input-output routines \ref graph-io-page here.
86
87So here is a file describing a graph of 10 nodes (0 to 9), two nodemaps
88(called \c coordinates_x and \c coordinates_y), several edges, an edge map
89called \c length and two designated nodes (called \c source and \c target).
90
91\todo Maybe another example would be better here.
92
93\code
94@nodeset
95id      coordinates_x   coordinates_y   
969       447.907 578.328
978       79.2573 909.464
987       878.677 960.04 
996       11.5504 938.413
1005       327.398 815.035
1014       427.002 954.002
1023       148.549 753.748
1032       903.889 326.476
1041       408.248 577.327
1050       189.239 92.5316
106@edgeset
107                length 
1082       3       901.074
1098       5       270.85 
1106       9       601.553
1115       9       285.022
1129       4       408.091
1133       0       719.712
1147       5       612.836
1150       4       933.353
1165       0       778.871
1175       5       0       
1187       1       664.049
1195       5       0       
1200       9       560.464
1214       8       352.36 
1224       9       399.625
1234       1       402.171
1241       2       591.688
1253       8       182.376
1264       5       180.254
1273       1       345.283
1285       4       184.511
1296       2       1112.45
1300       1       556.624
131@nodes
132source  1       
133target  8       
134@end
135\endcode
136
137Finally let us give a simple example that reads a graph from a file and writes
138it to another.
139
140\todo This is to be done!
141
142</ol>
143<li> If you want to solve some transportation problems in a network then
144you will want to find shortest paths between nodes of a graph. This is
145usually solved using Dijkstra's algorithm. A utility
146that solves this is  the \ref lemon::Dijkstra "LEMON Dijkstra class".
147The following code is a simple program using the
148\ref lemon::Dijkstra "LEMON Dijkstra class" and it also shows how to define a map on the edges (the length
149function):
150
151\code
152
153    typedef ListGraph Graph;
154    typedef Graph::Node Node;
155    typedef Graph::Edge Edge;
156    typedef Graph::EdgeMap<int> LengthMap;
157
158    Graph g;
159
160    //An example from Ahuja's book
161
162    Node s=g.addNode();
163    Node v2=g.addNode();
164    Node v3=g.addNode();
165    Node v4=g.addNode();
166    Node v5=g.addNode();
167    Node t=g.addNode();
168
169    Edge s_v2=g.addEdge(s, v2);
170    Edge s_v3=g.addEdge(s, v3);
171    Edge v2_v4=g.addEdge(v2, v4);
172    Edge v2_v5=g.addEdge(v2, v5);
173    Edge v3_v5=g.addEdge(v3, v5);
174    Edge v4_t=g.addEdge(v4, t);
175    Edge v5_t=g.addEdge(v5, t);
176 
177    LengthMap len(g);
178
179    len.set(s_v2, 10);
180    len.set(s_v3, 10);
181    len.set(v2_v4, 5);
182    len.set(v2_v5, 8);
183    len.set(v3_v5, 5);
184    len.set(v4_t, 8);
185    len.set(v5_t, 8);
186
187    std::cout << "The id of s is " << g.id(s)<< std::endl;
188    std::cout <<"The id of t is " << g.id(t)<<"."<<std::endl;
189
190    std::cout << "Dijkstra algorithm test..." << std::endl;
191
192    Dijkstra<Graph, LengthMap> dijkstra_test(g,len);
193   
194    dijkstra_test.run(s);
195
196   
197    std::cout << "The distance of node t from node s: " << dijkstra_test.dist(t)<<std::endl;
198
199    std::cout << "The shortest path from s to t goes through the following nodes" <<std::endl;
200 std::cout << " (the first one is t, the last one is s): "<<std::endl;
201
202    for (Node v=t;v != s; v=dijkstra_test.predNode(v)){
203        std::cout << g.id(v) << "<-";
204    }
205    std::cout << g.id(s) << std::endl; 
206\endcode
207
208See the whole program in \ref dijkstra_demo.cc.
209
210The first part of the code is self-explanatory: we build the graph and set the
211length values of the edges. Then we instantiate a member of the Dijkstra class
212and run the Dijkstra algorithm from node \c s. After this we read some of the
213results.
214You can do much more with the Dijkstra class, for example you can run it step
215by step and gain full control of the execution. For a detailed description, see the documentation of the \ref lemon::Dijkstra "LEMON Dijkstra class".
216
217
218<li> If you want to design a network and want to minimize the total length
219of wires then you might be looking for a <b>minimum spanning tree</b> in
220an undirected graph. This can be found using the Kruskal algorithm: the
221class \ref lemon::Kruskal "LEMON Kruskal class" does this job for you.
222The following code fragment shows an example:
223
224Ide Zsuzska fog irni!
225
226<li>Many problems in network optimization can be formalized by means
227of a linear programming problem (LP problem, for short). In our
228library we decided not to write an LP solver, since such packages are
229available in the commercial world just as well as in the open source
230world, and it is also a difficult task to compete these. Instead we
231decided to develop an interface that makes it easier to use these
232solvers together with LEMON. The advantage of this approach is
233twofold. Firstly our C++ interface is more comfortable than the
234solvers' native interface. Secondly, changing the underlying solver in
235a certain software using LEMON's LP interface needs zero effort. So,
236for example, one may try his idea using a free solver, demonstrate its
237usability for a customer and if it works well, but the performance
238should be improved, then one may decide to purchase and use a better
239commercial solver.
240
241So far we have an
242interface for the commercial LP solver software \b CLPLEX (developed by ILOG)
243and for the open source solver \b GLPK (a shorthand for Gnu Linear Programming
244Toolkit).
245
246We will show two examples, the first one shows how simple it is to formalize
247and solve an LP problem in LEMON, while the second one shows how LEMON
248facilitates solving network optimization problems using LP solvers.
249
250<ol>
251<li>The following code shows how to solve an LP problem using the LEMON lp
252interface. The code together with the comments is self-explanatory.
253
254\code
255
256  //A default solver is taken
257  LpDefault lp;
258  typedef LpDefault::Row Row;
259  typedef LpDefault::Col Col;
260 
261
262  //This will be a maximization
263  lp.max();
264
265  //We add coloumns (variables) to our problem
266  Col x1 = lp.addCol();
267  Col x2 = lp.addCol();
268  Col x3 = lp.addCol();
269
270  //Constraints
271  lp.addRow(x1+x2+x3 <=100); 
272  lp.addRow(10*x1+4*x2+5*x3<=600); 
273  lp.addRow(2*x1+2*x2+6*x3<=300); 
274  //Nonnegativity of the variables
275  lp.colLowerBound(x1, 0);
276  lp.colLowerBound(x2, 0);
277  lp.colLowerBound(x3, 0);
278  //Objective function
279  lp.setObj(10*x1+6*x2+4*x3);
280 
281  //Call the routine of the underlying LP solver
282  lp.solve();
283
284  //Print results
285  if (lp.primalStatus()==LpSolverBase::OPTIMAL){
286    printf("Z = %g; x1 = %g; x2 = %g; x3 = %g\n",
287           lp.primalValue(),
288           lp.primal(x1), lp.primal(x2), lp.primal(x3));
289  }
290  else{
291    std::cout<<"Optimal solution not found!"<<std::endl;
292  }
293
294
295\endcode
296
297See the whole code in \ref lp_demo.cc.
298
299<li>The second example shows how easy it is to formalize a max-flow
300problem as an LP problem using the LEMON LP interface: we are looking
301for a real valued function defined on the edges of the digraph
302satisfying the nonnegativity-, the capacity constraints and the
303flow-conservation constraints and giving the largest flow value
304between to designated nodes.
305
306In the following code we suppose that we already have the graph \c g,
307the capacity map \c cap, the source node \c s and the target node \c t
308in the memory. We will also omit the typedefs.
309
310\code
311  //Define a map on the edges for the variables of the LP problem
312  typename G::template EdgeMap<LpDefault::Col> x(g);
313  lp.addColSet(x);
314 
315  //Nonnegativity and capacity constraints
316  for(EdgeIt e(g);e!=INVALID;++e) {
317    lp.colUpperBound(x[e],cap[e]);
318    lp.colLowerBound(x[e],0);
319  }
320
321
322  //Flow conservation constraints for the nodes (except for 's' and 't')
323  for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
324    LpDefault::Expr ex;
325    for(InEdgeIt  e(g,n);e!=INVALID;++e) ex+=x[e];
326    for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
327    lp.addRow(ex==0);
328  }
329 
330  //Objective function: the flow value entering 't'
331  {
332    LpDefault::Expr ex;
333    for(InEdgeIt  e(g,t);e!=INVALID;++e) ex+=x[e];
334    for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
335    lp.setObj(ex);
336  }
337
338  //Maximization
339  lp.max();
340
341  //Solve with the underlying solver
342  lp.solve();
343
344\endcode
345
346The complete program can be found in file \ref lp_maxflow_demo.cc. After compiling run it in the form:
347
348<tt>./lp_maxflow_demo < ?????????.lgf</tt>
349
350where ?????????.lgf is a file in the lemon format containing a maxflow instance (designated "source", "target" nodes and "capacity" map on the edges).
351
352
353
354</ol>
355</ul>
356
357*/
Note: See TracBrowser for help on using the repository browser.