1.1 --- a/demo/dijkstra_demo.cc Mon Jul 04 07:51:57 2005 +0000
1.2 +++ b/demo/dijkstra_demo.cc Mon Jul 04 13:08:31 2005 +0000
1.3 @@ -44,6 +44,11 @@
1.4 len.set(v4_t, 8);
1.5 len.set(v5_t, 8);
1.6
1.7 + std::cout << "This program is a simple demo of the LEMON Dijkstra class."<<std::endl;
1.8 + std::cout << "We calculate the shortest path from node s to node t in a graph."<<std::endl;
1.9 + std::cout <<std::endl;
1.10 +
1.11 +
1.12 std::cout << "The id of s is " << g.id(s)<< ", the id of t is " << g.id(t)<<"."<<std::endl;
1.13
1.14 std::cout << "Dijkstra algorithm test..." << std::endl;
2.1 --- a/demo/hello_lemon.cc Mon Jul 04 07:51:57 2005 +0000
2.2 +++ b/demo/hello_lemon.cc Mon Jul 04 13:08:31 2005 +0000
2.3 @@ -5,17 +5,38 @@
2.4 {
2.5 typedef lemon::ListGraph Graph;
2.6 typedef Graph::EdgeIt EdgeIt;
2.7 + typedef Graph::Edge Edge;
2.8 typedef Graph::NodeIt NodeIt;
2.9 + typedef Graph::Node Node;
2.10 + typedef Graph::EdgeMap<int> LengthMap;
2.11 using lemon::INVALID;
2.12
2.13 Graph g;
2.14
2.15 - for (int i = 0; i < 3; i++)
2.16 - g.addNode();
2.17 + Node s=g.addNode();
2.18 + Node v2=g.addNode();
2.19 + Node v3=g.addNode();
2.20 + Node v4=g.addNode();
2.21 + Node v5=g.addNode();
2.22 + Node t=g.addNode();
2.23 +
2.24 + Edge s_v2=g.addEdge(s, v2);
2.25 + Edge s_v3=g.addEdge(s, v3);
2.26 + Edge v2_v4=g.addEdge(v2, v4);
2.27 + Edge v2_v5=g.addEdge(v2, v5);
2.28 + Edge v3_v5=g.addEdge(v3, v5);
2.29 + Edge v4_t=g.addEdge(v4, t);
2.30 + Edge v5_t=g.addEdge(v5, t);
2.31
2.32 - for (NodeIt i(g); i!=INVALID; ++i)
2.33 - for (NodeIt j(g); j!=INVALID; ++j)
2.34 - if (i != j) g.addEdge(i, j);
2.35 + LengthMap length(g);
2.36 +
2.37 + length.set(s_v2, 10);
2.38 + length.set(s_v3, 10);
2.39 + length.set(v2_v4, 5);
2.40 + length.set(v2_v5, 8);
2.41 + length.set(v3_v5, 5);
2.42 + length.set(v4_t, 8);
2.43 + length.set(v5_t, 8);
2.44
2.45 std::cout << "Hello World!" << std::endl;
2.46 std::cout << std::endl;
2.47 @@ -31,4 +52,13 @@
2.48 for (EdgeIt i(g); i!=INVALID; ++i)
2.49 std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
2.50 std::cout << std::endl;
2.51 + std::cout << std::endl;
2.52 +
2.53 + std::cout << "There is a map on the edges (length)!" << std::endl;
2.54 + std::cout << std::endl;
2.55 + for (EdgeIt i(g); i!=INVALID; ++i)
2.56 + std::cout << "length(" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")="<<length[i]<<std::endl;
2.57 +
2.58 + std::cout << std::endl;
2.59 +
2.60 }
3.1 --- a/demo/lp_demo.cc Mon Jul 04 07:51:57 2005 +0000
3.2 +++ b/demo/lp_demo.cc Mon Jul 04 13:08:31 2005 +0000
3.3 @@ -23,6 +23,8 @@
3.4 {
3.5 //The following example is taken from the documentation of the GLPK library.
3.6 //See it in the GLPK reference manual and among the GLPK sample files (sample.c)
3.7 +
3.8 + //A default solver is taken
3.9 LpDefault lp;
3.10 typedef LpDefault::Row Row;
3.11 typedef LpDefault::Col Col;
3.12 @@ -36,15 +38,6 @@
3.13 Col x2 = lp.addCol();
3.14 Col x3 = lp.addCol();
3.15
3.16 - //One solution
3.17 - // Row p = lp.addRow();
3.18 - // Row q = lp.addRow();
3.19 - // Row r = lp.addRow();
3.20 - // lp.setRow(p,x1+x2+x3 <=100);
3.21 - // lp.setRow(q,10*x1+4*x2+5*x3<=600);
3.22 - // lp.setRow(r,2*x1+2*x2+6*x3<=300);
3.23 -
3.24 - //A more elegant one
3.25 //Constraints
3.26 lp.addRow(x1+x2+x3 <=100);
3.27 lp.addRow(10*x1+4*x2+5*x3<=600);
3.28 @@ -69,6 +62,7 @@
3.29 std::cout<<"Optimal solution not found!"<<std::endl;
3.30 }
3.31
3.32 + //End of LEMON style code
3.33
3.34 //Here comes the same problem written in C using GLPK API routines
3.35
4.1 --- a/demo/reader_writer_demo.cc Mon Jul 04 07:51:57 2005 +0000
4.2 +++ b/demo/reader_writer_demo.cc Mon Jul 04 13:08:31 2005 +0000
4.3 @@ -15,8 +15,6 @@
4.4 GraphReader<SmartGraph> reader(filename,graph);
4.5 SmartGraph::EdgeMap<int> cap(graph);
4.6 reader.readEdgeMap("capacity",cap);
4.7 -// reader.readNode("source",s).readNode("target",t)
4.8 -// .readEdgeMap("capacity",cap).run();
4.9 reader.run();
4.10
4.11 std::cout << "Hello! We have read a graph from file " << filename<<
4.12 @@ -30,50 +28,6 @@
4.13 // writer.writeNode("target", t);
4.14 writer.run();
4.15
4.16 -// LemonReader reader(std::cin);
4.17 -
4.18 -// NodeSetReader<SmartGraph> nodeset(reader, graph);
4.19 -// SmartGraph::NodeMap<int> cost(graph);
4.20 -// nodeset.readMap("cost", cost);
4.21 -// SmartGraph::NodeMap<char> mmap(graph);
4.22 -// nodeset.readMap("mmap", mmap);
4.23 -
4.24 -// EdgeSetReader<SmartGraph> edgeset(reader, graph, nodeset);
4.25 -// SmartGraph::EdgeMap<std::string> description(graph);
4.26 -// edgeset.readMap<QuotedStringReader>("description", description);
4.27 -
4.28 -// NodeReader<SmartGraph> nodes(reader, nodeset);
4.29 -// SmartGraph::Node source;
4.30 -// nodes.readNode("source", source);
4.31 -// SmartGraph::Node target;
4.32 -// nodes.readNode("target", target);
4.33 -
4.34 -// AttributeReader<> attribute(reader, "gui");
4.35 -// std::string author;
4.36 -// attribute.readAttribute<LineReader>("author", author);
4.37 -// int count;
4.38 -// attribute.readAttribute("count", count);
4.39 -
4.40 -// PrintReader print(reader);
4.41 -
4.42 -// reader.run();
4.43 -
4.44 -
4.45 -// for (SmartGraph::NodeIt it(graph); it != INVALID; ++it) {
4.46 -// std::cout << cost[it] << ' ' << mmap[it] << std::endl;
4.47 -// }
4.48 -
4.49 -// for (SmartGraph::EdgeIt it(graph); it != INVALID; ++it) {
4.50 -// std::cout << description[it] << std::endl;
4.51 -// }
4.52 -
4.53 -// std::cout << "author: " << author << std::endl;
4.54 -// std::cout << "count: " << count << std::endl;
4.55 -
4.56 -// std::cout << "source cost: " << cost[source] << std::endl;
4.57 -// std::cout << "target cost: " << cost[target] << std::endl;
4.58 -
4.59 -// std::cout.flush();
4.60 } catch (DataFormatError& error) {
4.61 std::cerr << error.what() << std::endl;
4.62 }
5.1 --- a/demo/route.lgf Mon Jul 04 07:51:57 2005 +0000
5.2 +++ b/demo/route.lgf Mon Jul 04 13:08:31 2005 +0000
5.3 @@ -11,31 +11,33 @@
5.4 1 408.248 577.327
5.5 0 189.239 92.5316
5.6 @edgeset
5.7 - length
5.8 -2 3 901.074
5.9 -8 5 270.85
5.10 -6 9 601.553
5.11 -5 9 285.022
5.12 -9 4 408.091
5.13 -3 0 719.712
5.14 -7 5 612.836
5.15 -0 4 933.353
5.16 -5 0 778.871
5.17 -5 5 0
5.18 -7 1 664.049
5.19 -5 5 0
5.20 -0 9 560.464
5.21 -4 8 352.36
5.22 -4 9 399.625
5.23 -4 1 402.171
5.24 -1 2 591.688
5.25 -3 8 182.376
5.26 -4 5 180.254
5.27 -3 1 345.283
5.28 -5 4 184.511
5.29 -6 2 1112.45
5.30 -0 1 556.624
5.31 + length id
5.32 +2 3 901.074 0
5.33 +8 5 270.85 1
5.34 +6 9 601.553 2
5.35 +5 9 285.022 3
5.36 +9 4 408.091 4
5.37 +3 0 719.712 5
5.38 +7 5 612.836 6
5.39 +0 4 933.353 7
5.40 +5 0 778.871 8
5.41 +5 5 0 9
5.42 +7 1 664.049 10
5.43 +5 5 0 11
5.44 +0 9 560.464 12
5.45 +4 8 352.36 13
5.46 +4 9 399.625 14
5.47 +4 1 402.171 15
5.48 +1 2 591.688 16
5.49 +3 8 182.376 17
5.50 +4 5 180.254 18
5.51 +3 1 345.283 19
5.52 +5 4 184.511 20
5.53 +6 2 1112.45 21
5.54 +0 1 556.624 22
5.55 @nodes
5.56 source 1
5.57 target 8
5.58 +@edges
5.59 +@attributes
5.60 @end
6.1 --- a/demo/sample.lgf Mon Jul 04 07:51:57 2005 +0000
6.2 +++ b/demo/sample.lgf Mon Jul 04 13:08:31 2005 +0000
6.3 @@ -1,21 +1,21 @@
6.4 -@nodeset
6.5 -id
6.6 -5
6.7 -4
6.8 -3
6.9 -2
6.10 -1
6.11 -0
6.12 -@edgeset
6.13 - id capacity
6.14 -4 5 6 8
6.15 -3 5 5 8
6.16 -2 4 4 5
6.17 -1 4 3 8
6.18 -1 3 2 5
6.19 -0 2 1 10
6.20 -0 1 0 10
6.21 -@nodes
6.22 +@nodeset
6.23 +id coordinates_x coordinates_y
6.24 +5 796.398 208.035
6.25 +4 573.002 63.002
6.26 +3 568.549 401.748
6.27 +2 277.889 68.476
6.28 +1 288.248 397.327
6.29 +0 102.239 257.532
6.30 +@edgeset
6.31 + id capacity
6.32 +4 5 6 8
6.33 +3 5 5 8
6.34 +2 4 4 5
6.35 +1 4 3 8
6.36 +1 3 2 5
6.37 +0 2 1 10
6.38 +0 1 0 10
6.39 +@nodes
6.40 source 0
6.41 target 5
6.42 @edges
7.1 --- a/doc/quicktour.dox Mon Jul 04 07:51:57 2005 +0000
7.2 +++ b/doc/quicktour.dox Mon Jul 04 13:08:31 2005 +0000
7.3 @@ -42,21 +42,38 @@
7.4 file format that gives a more flexible way to store data related to network
7.5 optimization.
7.6
7.7 -<ol> <li>The following code fragment shows how to fill a graph with
7.8 -data. It creates a complete graph on 4 nodes. The type Listgraph is one of the
7.9 -LEMON graph types: the typedefs in the beginning are for convenience and we
7.10 -will suppose them later as well.
7.11 +<ol> <li>The following code shows how to build a graph from scratch
7.12 +and iterate on its nodes and edges. This example also shows how to
7.13 +give a map on the edges of the graph. The type Listgraph is one of
7.14 +the LEMON graph types: the typedefs in the beginning are for
7.15 +convenience and we will assume them later as well.
7.16
7.17 -\dontinclude hello_lemon.cc
7.18 -\skip ListGraph
7.19 -\until addEdge
7.20 +\include hello_lemon.cc
7.21
7.22 -See the whole program in file \ref hello_lemon.cc in \c demo subdir of
7.23 +See the whole program in file \ref hello_lemon.cc in the \c demo subdir of
7.24 LEMON package.
7.25
7.26 If you want to read more on the LEMON graph structures and
7.27 concepts, read the page about \ref graphs "graphs".
7.28
7.29 +
7.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
7.31 +short example file in this format: read the detailed description of the LEMON
7.32 +graph file format and input-output routines here: \ref graph-io-page.
7.33 +
7.34 +So here is a file describing a graph of 6 nodes (0 to 5), two nodemaps
7.35 +(called \c coordinates_x and \c coordinates_y), several edges, an edge map
7.36 +called \c capacity and two designated nodes (called \c source and \c target).
7.37 +
7.38 +\include sample.lgf
7.39 +
7.40 +Finally let us give a simple example that reads a graph from a file and writes
7.41 +it to the standard output.
7.42 +
7.43 +\include reader_writer_demo.cc
7.44 +
7.45 +See the whole program in file \ref reader_writer_demo.cc.
7.46 +
7.47 <li> The following code shows how to read a graph from a stream
7.48 (e.g. a file) in the DIMACS file format (find the documentation of the
7.49 DIMACS file formats on the web).
7.50 @@ -73,49 +90,30 @@
7.51 \ref dimacs.h "Dimacs file format reader". There you will also find
7.52 the details about the output routines into files of the DIMACS format.
7.53
7.54 -<li>DIMACS formats could not give us the flexibility we needed,
7.55 -so we worked out our own file format. Instead of any explanation let us give a
7.56 -short example file in this format: read the detailed description of the LEMON
7.57 -graph file format and input-output routines \ref graph-io-page here.
7.58 -
7.59 -So here is a file describing a graph of 10 nodes (0 to 9), two nodemaps
7.60 -(called \c coordinates_x and \c coordinates_y), several edges, an edge map
7.61 -called \c length and two designated nodes (called \c source and \c target).
7.62 -
7.63 -\todo Maybe a shorter example would be better here.
7.64 -
7.65 -\include route.lgf
7.66 -
7.67 -Finally let us give a simple example that reads a graph from a file and writes
7.68 -it to the standard output.
7.69 -
7.70 -\include reader_writer_demo.cc
7.71 -
7.72 -See the whole program in file \ref reader_writer_demo.cc.
7.73 -
7.74 -\todo This is still under construction!
7.75 -
7.76 </ol>
7.77 <li> If you want to solve some transportation problems in a network then
7.78 you will want to find shortest paths between nodes of a graph. This is
7.79 usually solved using Dijkstra's algorithm. A utility
7.80 that solves this is the \ref lemon::Dijkstra "LEMON Dijkstra class".
7.81 The following code is a simple program using the
7.82 -\ref lemon::Dijkstra "LEMON Dijkstra class" and it also shows how to define a map on the edges (the length
7.83 -function):
7.84 +\ref lemon::Dijkstra "LEMON Dijkstra class": it calculates the shortest path between node \c s and \c t in a graph \c g.
7.85 +We omit the part reading the graph \c g and the length map \c len.
7.86
7.87 \dontinclude dijkstra_demo.cc
7.88 \skip ListGraph
7.89 +\until Graph g
7.90 +...
7.91 +\skip Dijkstra algorithm
7.92 \until std::cout << g.id(s)
7.93
7.94 See the whole program in \ref dijkstra_demo.cc.
7.95
7.96 -The first part of the code is self-explanatory: we build the graph and set the
7.97 -length values of the edges. Then we instantiate a member of the Dijkstra class
7.98 -and run the Dijkstra algorithm from node \c s. After this we read some of the
7.99 -results.
7.100 -You can do much more with the Dijkstra class, for example you can run it step
7.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".
7.102 +Some explanation: after instantiating a member of the Dijkstra class
7.103 +we run the Dijkstra algorithm from node \c s. After this we read some
7.104 +of the results. You can do much more with the Dijkstra class, for
7.105 +example you can run it step by step and gain full control of the
7.106 +execution. For a detailed description, see the documentation of the
7.107 +\ref lemon::Dijkstra "LEMON Dijkstra class".
7.108
7.109
7.110 <li> If you want to design a network and want to minimize the total length
7.111 @@ -154,48 +152,9 @@
7.112 <li>The following code shows how to solve an LP problem using the LEMON lp
7.113 interface. The code together with the comments is self-explanatory.
7.114
7.115 -\code
7.116 -
7.117 - //A default solver is taken
7.118 - LpDefault lp;
7.119 - typedef LpDefault::Row Row;
7.120 - typedef LpDefault::Col Col;
7.121 -
7.122 -
7.123 - //This will be a maximization
7.124 - lp.max();
7.125 -
7.126 - //We add coloumns (variables) to our problem
7.127 - Col x1 = lp.addCol();
7.128 - Col x2 = lp.addCol();
7.129 - Col x3 = lp.addCol();
7.130 -
7.131 - //Constraints
7.132 - lp.addRow(x1+x2+x3 <=100);
7.133 - lp.addRow(10*x1+4*x2+5*x3<=600);
7.134 - lp.addRow(2*x1+2*x2+6*x3<=300);
7.135 - //Nonnegativity of the variables
7.136 - lp.colLowerBound(x1, 0);
7.137 - lp.colLowerBound(x2, 0);
7.138 - lp.colLowerBound(x3, 0);
7.139 - //Objective function
7.140 - lp.setObj(10*x1+6*x2+4*x3);
7.141 -
7.142 - //Call the routine of the underlying LP solver
7.143 - lp.solve();
7.144 -
7.145 - //Print results
7.146 - if (lp.primalStatus()==LpSolverBase::OPTIMAL){
7.147 - printf("Z = %g; x1 = %g; x2 = %g; x3 = %g\n",
7.148 - lp.primalValue(),
7.149 - lp.primal(x1), lp.primal(x2), lp.primal(x3));
7.150 - }
7.151 - else{
7.152 - std::cout<<"Optimal solution not found!"<<std::endl;
7.153 - }
7.154 -
7.155 -
7.156 -\endcode
7.157 +\dontinclude lp_demo.cc
7.158 +\skip A default solver is taken
7.159 +\until End of LEMON style code
7.160
7.161 See the whole code in \ref lp_demo.cc.
7.162
7.163 @@ -210,42 +169,13 @@
7.164 the capacity map \c cap, the source node \c s and the target node \c t
7.165 in the memory. We will also omit the typedefs.
7.166
7.167 -\code
7.168 - //Define a map on the edges for the variables of the LP problem
7.169 - typename G::template EdgeMap<LpDefault::Col> x(g);
7.170 - lp.addColSet(x);
7.171 -
7.172 - //Nonnegativity and capacity constraints
7.173 - for(EdgeIt e(g);e!=INVALID;++e) {
7.174 - lp.colUpperBound(x[e],cap[e]);
7.175 - lp.colLowerBound(x[e],0);
7.176 - }
7.177 +\dontinclude lp_maxflow_demo.cc
7.178 +\skip Define a map on the edges for the variables of the LP problem
7.179 +\until lp.max();
7.180 +\skip Solve with the underlying solver
7.181 +\until lp.solve();
7.182
7.183
7.184 - //Flow conservation constraints for the nodes (except for 's' and 't')
7.185 - for(NodeIt n(g);n!=INVALID;++n) if(n!=s&&n!=t) {
7.186 - LpDefault::Expr ex;
7.187 - for(InEdgeIt e(g,n);e!=INVALID;++e) ex+=x[e];
7.188 - for(OutEdgeIt e(g,n);e!=INVALID;++e) ex-=x[e];
7.189 - lp.addRow(ex==0);
7.190 - }
7.191 -
7.192 - //Objective function: the flow value entering 't'
7.193 - {
7.194 - LpDefault::Expr ex;
7.195 - for(InEdgeIt e(g,t);e!=INVALID;++e) ex+=x[e];
7.196 - for(OutEdgeIt e(g,t);e!=INVALID;++e) ex-=x[e];
7.197 - lp.setObj(ex);
7.198 - }
7.199 -
7.200 - //Maximization
7.201 - lp.max();
7.202 -
7.203 - //Solve with the underlying solver
7.204 - lp.solve();
7.205 -
7.206 -\endcode
7.207 -
7.208 The complete program can be found in file \ref lp_maxflow_demo.cc. After compiling run it in the form:
7.209
7.210 <tt>./lp_maxflow_demo < sample.lgf</tt>