Changeset 2216:1e45cdeea3cc in lemon-0.x

Timestamp:

09/14/06 21:11:24 (19 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2946

Message:

The recent progresses on the tutorial due to Mark.

Files:

• demo/Makefile.am (modified) (2 diffs)
• demo/topological_ordering.cc (added)
• doc/Makefile.am (modified) (2 diffs)
• doc/algorithms.dox (modified) (1 diff)
• doc/lemon_file_format.dox (added)
• doc/read_write_bg.dox (added)
• doc/tutorial.dox (modified) (3 diffs)

demo/Makefile.am

@@ -22 +22 @@
         demo/grid_ugraph_demo \
         demo/topology_demo \
+        demo/topological_ordering \
         demo/simann_maxcut_demo \
         demo/disjoint_paths_demo \
@@ -79 +80 @@
 demo_topology_demo_SOURCES = demo/topology_demo.cc
 
+demo_topological_ordering_SOURCES = demo/topological_ordering.cc
+
 demo_simann_maxcut_demo_SOURCES = demo/simann_maxcut_demo.cc
 

doc/Makefile.am

@@ -17 +17 @@
         doc/graphs.dox \
         doc/groups.dox \
+        doc/lemon_file_format.dox \
         doc/license.dox \
         doc/mainpage.dox \
@@ -25 +26 @@
         doc/namespaces.dox \
         doc/quicktour.dox \
+        doc/read_write_bg.dox \
         doc/ugraphs.dox
 

doc/algorithms.dox

@@ +1 @@
+namespace lemon {
 /**
 \page algorithms Algorithms
 
-Place-holder page for algorithms.
+\section algo_bfs_dfs Bfs/Dfs
+Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
+implementations of the well known algorithms. The algorithms are placed most cases in
+separated files named after the algorithm itself but lower case as all other header file names.
+For example the next Bfs class is in the \c lemon/bfs.h.
+
+\subsection Bfs
+The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
+The class has two template parameters: \b GR and \TR.<br>
+GR is the graph the algorithm runs on. It has \ref lemon::ListGraph "ListGraph" as default type.
+TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
+wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
+
+To use the class, declare it!
+\code
+Bfs<ListUGraph>  bfs(gr);
+\endcode
+Note the lack of second template argument because of the default parameter.
+
+It provides a simple but powerful interface to control the execution.
+\code
+int dist = bfs.run(s,t);
+\endcode
+It finds the shortest path from node \c s to node \c t and returns it, or zero
+if there is no path from \c s to \c t.<br>
+If you want the shortest path from a specified node to all other node, just write:
+\code
+bfs.run(s);
+\endcode
+Now the distances and path information are stored in maps which you can access with
+member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
+Or more directly whit other member functions like \c predNode(). Once the algorithm
+is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
+"predNode()" can be called.
+
+For an example let's say we want to print the shortest path of those nodes which
+are in a certain distance.
+\code
+bfs.run(s);
+
+for( ListUGraph::NodeIt  n(gr); n != INVALID; ++n ) {
+  if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
+    std::cout << gr.id(n);
+
+    Node  prev = bfs.prevNode(n);
+    while( prev != INVALID ) {
+      std::cout << "<-" << gr.id(prev);
+      prev = bfs.prevNode(n);
+    }
+    
+    std::cout << std::endl;
+  }
+}
+\endcode
+
+\subsubsection bfs_adv_control Advanced control
+In the previous code we only used \c run(). Now we introduce the way you can directly
+control the execution of the algorithm.
+
+First you have to initialize the variables with \ref lemon::Bfs::init "init()".
+\code
+  bfs.init();
+\endcode
+
+Then you add one or more source nodes to the queue. They will be processed, as they would
+be reached by the algorithm before. And yes - you can add more sources during the execution.
+\code
+  bfs.addSource(node_1);
+  bfs.addSource(node_2);
+  ...
+\endcode
+
+And finally you can start the process with \ref lemon::Bfs::start "start()", or
+you can write your own loop to process the nodes one-by-one.
+
+\todo demo for bfs advanced control
+
+\subsection Dfs
+Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
+to demonstrate Dfs's capabilities.
+
+We will see a program, which solves the problem of <b>topological ordering</b>.
+We need to know in which order we should put on our clothes. The program will do the following:
+<ol>
+<li>We run the dfs algorithm to all nodes.
+<li>Put every node into a list when processed completely.
+<li>Write out the list in reverse order.
+</ol>
+
+\dontinclude topological_ordering.cc
+First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
+will be done through it.
+\skip SerializingWriteMap
+\until };
+The class meets the \ref lemon::WriteMap "WriteMap" concept. In it's \c set() method the only thing
+we need to do is insert the key - that is the node who's processing just finished - into the beginning
+of the list.
+
+First we declare the needed data structures: the graph and a map to store the nodes' label.
+\skip ListGraph
+\until label
+
+Now we build a graph. But keep in mind that it must be DAG because cyclic graphs has no topological
+ordering.
+\skip belt
+\until trousers
+We label them...
+\skip label
+\until trousers
+Then add directed edges which represent the precedences between those items.
+\skip trousers, belt
+\until );
+
+See how easy is to access the internal information of this algorithm trough maps.
+We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
+\skip Dfs
+\until run
+
+And now comes the third part. Write out the list in reverse order. But the list was
+composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
+\skip std
+\until endl
+
+The program is to be found in the \ref demo directory: \ref topological_ordering.cc
 */
+}

doc/tutorial.dox

@@ +1 @@
+namespace lemon {
 /**
 \page Tutorial LEMON Tutorial
@@ -16 +17 @@
     <LI>\ref maps1
   </UL>
-  <LI><A href="#file">Lemon Graph File Format</A>
+  <LI>\ref lemon_file_format
+  <UL>
+    <LI>\ref read_write_bg
+  </UL>
   <LI>\ref algorithms
   <UL>
-    <LI><A href="#bfs_dfs">Bfs/Dfs</A>
-    <LI><A href="#dijkstra">Dijkstra</A>
-    <LI><A href="#kruskal">Kruskal</A>
+    <LI>\ref algo_bfs_dfs
+    <LI>Dijkstra
+    <LI>Kruskal
   </UL>
   <LI>\ref maps2
   <UL>
     <LI>\ref custom_maps
-    <LI><A href="#map_adaptors">Map Adaptors</A>
-    <LI><A href="#special_maps">Special Purpose Maps</a>
+    <LI>Map Adaptors
+    <LI>Special Purpose Maps
   </UL>
-  <LI><A href="#show">Show a graph</A>
-  <LI><A href="#misc">Miscellaneous Tool</A>
+  <LI>Show a graph
+  <LI>Miscellaneous Tool
   <UL>
-    <LI><A href="#lp">LP solver</A>
-    <LI><A href="#simann">Simulated Annealing</A>
+    <LI>LP solver
+    <LI>Simulated Annealing
   </UL>
 </OL>
@@ -43 +47 @@
 sections.
 */
+}