COIN-OR::LEMON - Graph Library

Changeset 1528:1aa71600000c in lemon-0.x


Ignore:
Timestamp:
07/01/05 18:10:46 (19 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2016
Message:

Graph input-output demo, some documentation.

Files:
2 added
4 edited

Legend:

Unmodified
Added
Removed
  • demo/Makefile.am

    r1526 r1528  
    77        dim_to_dot \
    88        dijkstra_demo \
     9        reader_writer_demo \
    910        dim_to_lgf \
    1011        graph_to_eps_demo \
     
    2728dijkstra_demo_SOURCES = dijkstra_demo.cc
    2829
     30reader_writer_demo_SOURCES = reader_writer_demo.cc
     31
    2932dim_to_lgf_SOURCES = dim_to_lgf.cc
    3033
  • demo/dijkstra_demo.cc

    r1526 r1528  
    4949    std::cout << "Dijkstra algorithm test..." << std::endl;
    5050
    51 //     GraphWriter<ListGraph> writer(std::cout, g);
    52 //     writer.writeEdgeMap("capacity", len);
    53 //     writer.writeNode("source", s);
    54 //     writer.writeNode("target", t);
    55 //     writer.run();
    5651
    5752    Dijkstra<Graph, LengthMap> dijkstra_test(g,len);
  • doc/getstart.dox

    r1520 r1528  
    2828
    2929You can download LEMON from the LEMON web site:
    30 http://lemon.cs.elte.hu/dowload.html.
     30http://lemon.cs.elte.hu/download.html.
    3131There you will find released versions in form of <tt>.tar.gz</tt> files.
    3232If you want a developer version (for example you want to contribute in
     
    3939\section installLEMON How to install LEMON
    4040
    41 In order to install LEMON you have to do the following
     41In order to install LEMON you have to do the following steps.
    4242
    4343Download the tarball (named <tt>lemon-x.y.z.tar.gz</tt> where \c x,\c y
     
    5151./configure
    5252make
    53 make check   #(This is optional, but recomended. It runs a bunch of tests.)
     53make check   #(This is optional, but recommended. It runs a bunch of tests.)
    5454make install
    5555\endverbatim
     
    5858need root privileges to be able to install to that
    5959directory). If you want to install it to some other place, then
    60 pass the \c --prefix=DIR flag to \c ./configure. In what follows
    61 we will assume that you were able to install to directory
     60pass the \c --prefix=DIRECTORY flag to \c ./configure, for example:
     61
     62\verbatim
     63./configure --prefix=/home/user1/lemon
     64\endverbatim
     65
     66In what follows we will assume that you were able to install to directory
    6267\c /usr/local, otherwise some extra care is to be taken to use the
    6368library.
  • doc/quicktour.dox

    r1526 r1528  
    2323LEMON 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".
    2424
    25 Some 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):
     25In this quick tour we want to show you some facilities LEMON library can provide through examples (simple demo programs). The examples will only show part of the functionality, but links will always be given to reach complete details.
     26You 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 getstart "How to start using LEMON".
     27
     28Have fun!
    2629
    2730<ul> <li> The first thing to discuss is the way one can create data structures
     
    8083called \c length and two designated nodes (called \c source and \c target).
    8184
    82 \todo Maybe another example would be better here.
    83 
    84 \code
    85 @nodeset
    86 id      coordinates_x   coordinates_y   
    87 9       447.907 578.328
    88 8       79.2573 909.464
    89 7       878.677 960.04 
    90 6       11.5504 938.413
    91 5       327.398 815.035
    92 4       427.002 954.002
    93 3       148.549 753.748
    94 2       903.889 326.476
    95 1       408.248 577.327
    96 0       189.239 92.5316
    97 @edgeset
    98                 length 
    99 2       3       901.074
    100 8       5       270.85 
    101 6       9       601.553
    102 5       9       285.022
    103 9       4       408.091
    104 3       0       719.712
    105 7       5       612.836
    106 0       4       933.353
    107 5       0       778.871
    108 5       5       0       
    109 7       1       664.049
    110 5       5       0       
    111 0       9       560.464
    112 4       8       352.36 
    113 4       9       399.625
    114 4       1       402.171
    115 1       2       591.688
    116 3       8       182.376
    117 4       5       180.254
    118 3       1       345.283
    119 5       4       184.511
    120 6       2       1112.45
    121 0       1       556.624
    122 @nodes
    123 source  1       
    124 target  8       
    125 @end
    126 \endcode
     85\todo Maybe a shorter example would be better here.
     86
     87\include route.lgf
    12788
    12889Finally let us give a simple example that reads a graph from a file and writes
    129 it to another.
    130 
    131 \todo This is to be done!
     90it to the standard output.
     91
     92\include reader_writer_demo.cc
     93
     94See the whole program in file \ref reader_writer_demo.cc.
     95
     96\todo This is still under construction!
    13297
    13398</ol>
     
    140105function):
    141106
    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
     107\dontinclude dijkstra_demo.cc
     108\skip ListGraph
     109\until std::cout << g.id(s)
    198110
    199111See the whole program in \ref dijkstra_demo.cc.
     
    210122of wires then you might be looking for a <b>minimum spanning tree</b> in
    211123an undirected graph. This can be found using the Kruskal algorithm: the
    212 class \ref lemon::Kruskal "LEMON Kruskal class" does this job for you.
     124function \ref lemon::kruskal "LEMON Kruskal ..." does this job for you.
    213125The following code fragment shows an example:
    214126
     
    337249The complete program can be found in file \ref lp_maxflow_demo.cc. After compiling run it in the form:
    338250
    339 <tt>./lp_maxflow_demo < ?????????.lgf</tt>
    340 
    341 where ?????????.lgf is a file in the lemon format containing a maxflow instance (designated "source", "target" nodes and "capacity" map on the edges).
     251<tt>./lp_maxflow_demo < sample.lgf</tt>
     252
     253where sample.lgf is a file in the lemon format containing a maxflow instance (designated "source", "target" nodes and "capacity" map on the edges).
    342254
    343255
Note: See TracChangeset for help on using the changeset viewer.