COIN-OR::LEMON - Graph Library

Changeset 2216:1e45cdeea3cc in lemon-0.x

09/14/06 21:11:24 (13 years ago)
Alpar Juttner

The recent progresses on the tutorial due to Mark.

3 added
4 edited


  • demo/

    r2195 r2216  
    2222        demo/grid_ugraph_demo \
    2323        demo/topology_demo \
     24        demo/topological_ordering \
    2425        demo/simann_maxcut_demo \
    2526        demo/disjoint_paths_demo \
    7980demo_topology_demo_SOURCES = demo/
     82demo_topological_ordering_SOURCES = demo/
    8184demo_simann_maxcut_demo_SOURCES = demo/
  • doc/

    r2196 r2216  
    1717        doc/graphs.dox \
    1818        doc/groups.dox \
     19        doc/lemon_file_format.dox \
    1920        doc/license.dox \
    2021        doc/mainpage.dox \
    2526        doc/namespaces.dox \
    2627        doc/quicktour.dox \
     28        doc/read_write_bg.dox \
    2729        doc/ugraphs.dox
  • doc/algorithms.dox

    r2196 r2216  
     1namespace lemon {
    23\page algorithms Algorithms
    4 Place-holder page for algorithms.
     5\section algo_bfs_dfs Bfs/Dfs
     6Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
     7implementations of the well known algorithms. The algorithms are placed most cases in
     8separated files named after the algorithm itself but lower case as all other header file names.
     9For example the next Bfs class is in the \c lemon/bfs.h.
     11\subsection Bfs
     12The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
     13The class has two template parameters: \b GR and \TR.<br>
     14GR is the graph the algorithm runs on. It has \ref lemon::ListGraph "ListGraph" as default type.
     15TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
     16wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
     18To use the class, declare it!
     20Bfs<ListUGraph>  bfs(gr);
     22Note the lack of second template argument because of the default parameter.
     24It provides a simple but powerful interface to control the execution.
     26int dist =,t);
     28It finds the shortest path from node \c s to node \c t and returns it, or zero
     29if there is no path from \c s to \c t.<br>
     30If you want the shortest path from a specified node to all other node, just write:
     34Now the distances and path information are stored in maps which you can access with
     35member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
     36Or more directly whit other member functions like \c predNode(). Once the algorithm
     37is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
     38"predNode()" can be called.
     40For an example let's say we want to print the shortest path of those nodes which
     41are in a certain distance.
     45for( ListUGraph::NodeIt  n(gr); n != INVALID; ++n ) {
     46  if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
     47    std::cout <<;
     49    Node  prev = bfs.prevNode(n);
     50    while( prev != INVALID ) {
     51      std::cout << "<-" <<;
     52      prev = bfs.prevNode(n);
     53    }
     55    std::cout << std::endl;
     56  }
     60\subsubsection bfs_adv_control Advanced control
     61In the previous code we only used \c run(). Now we introduce the way you can directly
     62control the execution of the algorithm.
     64First you have to initialize the variables with \ref lemon::Bfs::init "init()".
     66  bfs.init();
     69Then you add one or more source nodes to the queue. They will be processed, as they would
     70be reached by the algorithm before. And yes - you can add more sources during the execution.
     72  bfs.addSource(node_1);
     73  bfs.addSource(node_2);
     74  ...
     77And finally you can start the process with \ref lemon::Bfs::start "start()", or
     78you can write your own loop to process the nodes one-by-one.
     80\todo demo for bfs advanced control
     82\subsection Dfs
     83Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
     84to demonstrate Dfs's capabilities.
     86We will see a program, which solves the problem of <b>topological ordering</b>.
     87We need to know in which order we should put on our clothes. The program will do the following:
     89<li>We run the dfs algorithm to all nodes.
     90<li>Put every node into a list when processed completely.
     91<li>Write out the list in reverse order.
     95First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
     96will be done through it.
     97\skip SerializingWriteMap
     98\until };
     99The class meets the \ref lemon::WriteMap "WriteMap" concept. In it's \c set() method the only thing
     100we need to do is insert the key - that is the node who's processing just finished - into the beginning
     101of the list.
     103First we declare the needed data structures: the graph and a map to store the nodes' label.
     104\skip ListGraph
     105\until label
     107Now we build a graph. But keep in mind that it must be DAG because cyclic graphs has no topological
     109\skip belt
     110\until trousers
     111We label them...
     112\skip label
     113\until trousers
     114Then add directed edges which represent the precedences between those items.
     115\skip trousers, belt
     116\until );
     118See how easy is to access the internal information of this algorithm trough maps.
     119We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
     120\skip Dfs
     121\until run
     123And now comes the third part. Write out the list in reverse order. But the list was
     124composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
     125\skip std
     126\until endl
     128The program is to be found in the \ref demo directory: \ref
  • doc/tutorial.dox

    r2195 r2216  
     1namespace lemon {
    23\page Tutorial LEMON Tutorial
    1617    <LI>\ref maps1
    1718  </UL>
    18   <LI><A href="#file">Lemon Graph File Format</A>
     19  <LI>\ref lemon_file_format
     20  <UL>
     21    <LI>\ref read_write_bg
     22  </UL>
    1923  <LI>\ref algorithms
    2024  <UL>
    21     <LI><A href="#bfs_dfs">Bfs/Dfs</A>
    22     <LI><A href="#dijkstra">Dijkstra</A>
    23     <LI><A href="#kruskal">Kruskal</A>
     25    <LI>\ref algo_bfs_dfs
     26    <LI>Dijkstra
     27    <LI>Kruskal
    2428  </UL>
    2529  <LI>\ref maps2
    2630  <UL>
    2731    <LI>\ref custom_maps
    28     <LI><A href="#map_adaptors">Map Adaptors</A>
    29     <LI><A href="#special_maps">Special Purpose Maps</a>
     32    <LI>Map Adaptors
     33    <LI>Special Purpose Maps
    3034  </UL>
    31   <LI><A href="#show">Show a graph</A>
    32   <LI><A href="#misc">Miscellaneous Tool</A>
     35  <LI>Show a graph
     36  <LI>Miscellaneous Tool
    3337  <UL>
    34     <LI><A href="#lp">LP solver</A>
    35     <LI><A href="#simann">Simulated Annealing</A>
     38    <LI>LP solver
     39    <LI>Simulated Annealing
    3640  </UL>
Note: See TracChangeset for help on using the changeset viewer.