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.
-
- 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.
+
- 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".
+
+
- 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.
+
- 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.
-
- 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!
-
- 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".
- If you want to design a network and want to minimize the total length
@@ -154,48 +152,9 @@
- 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