COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1530:d99c3c84f797 in lemon-0.x


Ignore:
Timestamp:
07/04/05 15:08:31 (20 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2021
Message:

Doc.

Files:
7 edited

Legend:

Unmodified
Added
Removed

  • demo/dijkstra_demo.cc

    r1528 r1530  
    4545    len.set(v5_t, 8);
    4646
     47    std::cout << "This program is a simple demo of the LEMON Dijkstra class."<<std::endl;
     48    std::cout << "We calculate the shortest path from node s to node t in a graph."<<std::endl;
     49    std::cout <<std::endl;
     50
     51
    4752    std::cout << "The id of s is " << g.id(s)<< ", the id of t is " << g.id(t)<<"."<<std::endl;
    4853

  • demo/hello_lemon.cc

    r1526 r1530  
    66  typedef lemon::ListGraph Graph;
    77  typedef Graph::EdgeIt EdgeIt;
     8  typedef Graph::Edge Edge;
    89  typedef Graph::NodeIt NodeIt;
     10  typedef Graph::Node Node;
     11  typedef Graph::EdgeMap<int> LengthMap;
    912  using lemon::INVALID;
    1013
    1114  Graph g;
    1215 
    13   for (int i = 0; i < 3; i++)
    14     g.addNode();
     16  Node s=g.addNode();
     17  Node v2=g.addNode();
     18  Node v3=g.addNode();
     19  Node v4=g.addNode();
     20  Node v5=g.addNode();
     21  Node t=g.addNode();
     22
     23  Edge s_v2=g.addEdge(s, v2);
     24  Edge s_v3=g.addEdge(s, v3);
     25  Edge v2_v4=g.addEdge(v2, v4);
     26  Edge v2_v5=g.addEdge(v2, v5);
     27  Edge v3_v5=g.addEdge(v3, v5);
     28  Edge v4_t=g.addEdge(v4, t);
     29  Edge v5_t=g.addEdge(v5, t);
    1530 
    16   for (NodeIt i(g); i!=INVALID; ++i)
    17     for (NodeIt j(g); j!=INVALID; ++j)
    18       if (i != j) g.addEdge(i, j);
     31  LengthMap length(g);
     32
     33  length.set(s_v2, 10);
     34  length.set(s_v3, 10);
     35  length.set(v2_v4, 5);
     36  length.set(v2_v5, 8);
     37  length.set(v3_v5, 5);
     38  length.set(v4_t, 8);
     39  length.set(v5_t, 8);
    1940
    2041  std::cout << "Hello World!" << std::endl;
    … …  
    3253    std::cout << " (" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")";
    3354  std::cout << std::endl;
     55  std::cout <<  std::endl;
     56
     57  std::cout << "There is a map on the edges (length)!" << std::endl;
     58  std::cout <<  std::endl;
     59  for (EdgeIt i(g); i!=INVALID; ++i)
     60    std::cout << "length(" << g.id(g.source(i)) << "," << g.id(g.target(i)) << ")="<<length[i]<<std::endl;
     61
     62  std::cout << std::endl;
     63
    3464}

  • demo/lp_demo.cc

    r1513 r1530  
    2424 //The following example is taken from the documentation of the GLPK library.
    2525 //See it in the GLPK reference manual and among the GLPK sample files (sample.c)
     26
     27  //A default solver is taken
    2628  LpDefault lp;
    2729  typedef LpDefault::Row Row;
    … …  
    3739  Col x3 = lp.addCol();
    3840
    39   //One solution
    40   //   Row p = lp.addRow();
    41   //   Row q = lp.addRow();
    42   //   Row r = lp.addRow();
    43   //   lp.setRow(p,x1+x2+x3 <=100); 
    44   //   lp.setRow(q,10*x1+4*x2+5*x3<=600); 
    45   //   lp.setRow(r,2*x1+2*x2+6*x3<=300); 
    46 
    47   //A more elegant one
    4841  //Constraints
    4942  lp.addRow(x1+x2+x3 <=100); 
    … …  
    7063  }
    7164
     65  //End of LEMON style code
    7266
    7367  //Here comes the same problem written in C using GLPK API routines

  • demo/reader_writer_demo.cc

    r1528 r1530  
    1616    SmartGraph::EdgeMap<int> cap(graph);
    1717    reader.readEdgeMap("capacity",cap);
    18 //     reader.readNode("source",s).readNode("target",t)
    19 //       .readEdgeMap("capacity",cap).run();
    2018    reader.run();
    2119
    … …  
    3129    writer.run();
    3230     
    33 //     LemonReader reader(std::cin);
    34 
    35 //     NodeSetReader<SmartGraph> nodeset(reader, graph);
    36 //     SmartGraph::NodeMap<int> cost(graph);
    37 //     nodeset.readMap("cost", cost);
    38 //     SmartGraph::NodeMap<char> mmap(graph);
    39 //     nodeset.readMap("mmap", mmap);
    40 
    41 //     EdgeSetReader<SmartGraph> edgeset(reader, graph, nodeset);
    42 //     SmartGraph::EdgeMap<std::string> description(graph);
    43 //     edgeset.readMap<QuotedStringReader>("description", description);
    44 
    45 //     NodeReader<SmartGraph> nodes(reader, nodeset);
    46 //     SmartGraph::Node source;
    47 //     nodes.readNode("source", source);
    48 //     SmartGraph::Node target;
    49 //     nodes.readNode("target", target);
    50 
    51 //     AttributeReader<> attribute(reader, "gui");
    52 //     std::string author;
    53 //     attribute.readAttribute<LineReader>("author", author);
    54 //     int count;
    55 //     attribute.readAttribute("count", count);
    56 
    57 //     PrintReader print(reader);
    58 
    59 //     reader.run();
    60 
    61 
    62 //     for (SmartGraph::NodeIt it(graph); it != INVALID; ++it) {
    63 //       std::cout << cost[it] << ' ' << mmap[it] << std::endl;
    64 //     }
    65 
    66 //     for (SmartGraph::EdgeIt it(graph); it != INVALID; ++it) {
    67 //       std::cout << description[it] << std::endl;
    68 //     }
    69 
    70 //     std::cout << "author: " << author << std::endl;
    71 //     std::cout << "count: " << count << std::endl;
    72 
    73 //     std::cout << "source cost: " << cost[source] << std::endl;
    74 //     std::cout << "target cost: " << cost[target] << std::endl;
    75 
    76 //     std::cout.flush();
    7731  } catch (DataFormatError& error) {
    7832    std::cerr << error.what() << std::endl;

  • demo/route.lgf

    r1435 r1530  
    12120       189.239 92.5316
    1313@edgeset
    14                 length 
    15 2       3       901.074
    16 8       5       270.85 
    17 6       9       601.553
    18 5       9       285.022
    19 9       4       408.091
    20 3       0       719.712
    21 7       5       612.836
    22 0       4       933.353
    23 5       0       778.871
    24 5       5       0       
    25 7       1       664.049
    26 5       5       0       
    27 0       9       560.464
    28 4       8       352.36 
    29 4       9       399.625
    30 4       1       402.171
    31 1       2       591.688
    32 3       8       182.376
    33 4       5       180.254
    34 3       1       345.283
    35 5       4       184.511
    36 6       2       1112.45
    37 0       1       556.624
     14                length  id     
     152       3       901.074 0       
     168       5       270.85  1       
     176       9       601.553 2       
     185       9       285.022 3       
     199       4       408.091 4       
     203       0       719.712 5       
     217       5       612.836 6       
     220       4       933.353 7       
     235       0       778.871 8       
     245       5       0       9       
     257       1       664.049 10     
     265       5       0       11     
     270       9       560.464 12     
     284       8       352.36  13     
     294       9       399.625 14     
     304       1       402.171 15     
     311       2       591.688 16     
     323       8       182.376 17     
     334       5       180.254 18     
     343       1       345.283 19     
     355       4       184.511 20     
     366       2       1112.45 21     
     370       1       556.624 22     
    3838@nodes
    3939source  1       
    4040target  8       
     41@edges
     42@attributes
    4143@end

  • demo/sample.lgf

    r1528 r1530  
    1 @nodeset 
    2 id     
    3 5       
    4 4       
    5 3       
    6 2       
    7 1       
    8 0       
    9 @edgeset 
    10                 id      capacity       
    11 4       5       6       8       
    12 3       5       5       8       
    13 2       4       4       5       
    14 1       4       3       8       
    15 1       3       2       5       
    16 0       2       1       10     
    17 0       1       0       10     
    18 @nodes 
     1@nodeset
     2id      coordinates_x   coordinates_y
     35       796.398 208.035
     44       573.002 63.002
     53       568.549 401.748
     62       277.889 68.476
     71       288.248 397.327
     80       102.239 257.532
     9@edgeset
     10                id      capacity
     114       5       6       8
     123       5       5       8
     132       4       4       5
     141       4       3       8
     151       3       2       5
     160       2       1       10
     170       1       0       10
     18@nodes
    1919source 0
    2020target 5

  • doc/quicktour.dox

    r1528 r1530  
    4343optimization.
    4444
    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
     46and iterate on its nodes and edges.  This example also shows how to
     47give a map on the edges of the graph.  The type Listgraph is one of
     48the LEMON graph types: the typedefs in the beginning are for
     49convenience and we will assume them later as well.
    4950
    50 \dontinclude hello_lemon.cc
    51 \skip ListGraph
    52 \until addEdge
     51\include hello_lemon.cc
    5352
    54 See the whole program in file \ref hello_lemon.cc in \c demo subdir of
     53See the whole program in file \ref hello_lemon.cc in the \c demo subdir of
    5554LEMON package.
    5655
    5756    If you want to read more on the LEMON graph structures and
    5857concepts, 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
     61short example file in this format: read the detailed description of the LEMON
     62graph file format and input-output routines here: \ref graph-io-page.
     63
     64So 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
     66called \c capacity and two designated nodes (called \c source and \c target).
     67
     68\include sample.lgf
     69
     70Finally let us give a simple example that reads a graph from a file and writes
     71it to the standard output.
     72
     73\include reader_writer_demo.cc
     74
     75See the whole program in file \ref reader_writer_demo.cc.
    5976
    6077<li> The following code shows how to read a graph from a stream
    … …  
    7491the details about the output routines into files of the DIMACS format.
    7592
    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 a
    78 short example file in this format: read the detailed description of the LEMON
    79 graph file format and input-output routines \ref graph-io-page here.
    80 
    81 So here is a file describing a graph of 10 nodes (0 to 9), two nodemaps
    82 (called \c coordinates_x and \c coordinates_y), several edges, an edge map
    83 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.lgf
    88 
    89 Finally let us give a simple example that reads a graph from a file and writes
    90 it to the standard output.
    91 
    92 \include reader_writer_demo.cc
    93 
    94 See the whole program in file \ref reader_writer_demo.cc.
    95 
    96 \todo This is still under construction!
    97 
    9893</ol>
    9994<li> If you want to solve some transportation problems in a network then
    … …  
    10297that solves this is  the \ref lemon::Dijkstra "LEMON Dijkstra class".
    10398The 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 length
    105 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.
     100We omit the part reading the graph  \c g and the length map \c len.
    106101
    107102\dontinclude dijkstra_demo.cc
    108103\skip ListGraph
     104\until Graph g
     105...
     106\skip Dijkstra algorithm
    109107\until std::cout << g.id(s)
    110108
    111109See the whole program in \ref dijkstra_demo.cc.
    112110
    113 The first part of the code is self-explanatory: 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".
     111Some explanation: after instantiating a member of the Dijkstra class
     112we run the Dijkstra algorithm from node \c s. After this we read some
     113of the results.  You can do much more with the Dijkstra class, for
     114example you can run it step by step and gain full control of the
     115execution. For a detailed description, see the documentation of the
     116\ref lemon::Dijkstra "LEMON Dijkstra class".
    119117
    120118
    … …  
    155153interface. The code together with the comments is self-explanatory.
    156154
    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
    199158
    200159See the whole code in \ref lp_demo.cc.
    … …  
    211170in the memory. We will also omit the typedefs.
    212171
    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();
    223177
    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   //Maximization
    242   lp.max();
    243 
    244   //Solve with the underlying solver
    245   lp.solve();
    246 
    247 \endcode
    248178
    249179The 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.