Changeset 58:10b6a5b7d4c0 in lemon-tutorial for maps.dox

Timestamp:

03/01/10 02:30:00 (14 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Improve Algorithms section (it is still under construction)

File:

• maps.dox (modified) (4 diffs)

maps.dox

@@ -36 +36 @@
 These classes also conform to the map %concepts, thus they can be used
 like standard LEMON maps.
-
-Let us suppose that we have a traffic network stored in a LEMON digraph
-structure with two arc maps \c length and \c speed, which
-denote the physical length of each arc and the maximum (or average)
-speed that can be achieved on the corresponding road-section,
-respectively. If we are interested in the best traveling times,
-the following code can be used.
-
-\code
-  dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
-\endcode
-
 
 Maps play a central role in LEMON. As their name suggests, they map a
@@ -336 +324 @@
 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
 
+
 The basic functionality of the algorithms can be highly extended using
 special purpose map types for their internal data structures.
@@ -350 +339 @@
 they allow specifying any subset of the parameters and in arbitrary order.
 
+Let us suppose that we have a traffic network stored in a LEMON digraph
+structure with two arc maps \c length and \c speed, which
+denote the physical length of each arc and the maximum (or average)
+speed that can be achieved on the corresponding road-section,
+respectively. If we are interested in the best traveling times,
+the following code can be used.
+
+\code
+  dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
+\endcode
+
 \code
   typedef vector<ListDigraph::Node> Container;
@@ -378 +378 @@
     .run(s);
 \endcode
+
+Let us 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 MyOrdererMap
+\until };
+The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
+we need to do is insert the key - that is the node whose processing just finished - into the beginning
+of the list.<br>
+Although we implemented this needed helper class ourselves it was not necessary.
+The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
+what we needed. To be correct it's more general - and it's all in \c LEMON. But
+we wanted to show you, how easy is to add additional functionality.
+
+First we declare the needed data structures: the digraph and a map to store the nodes' label.
+\skip ListDigraph
+\until label
+
+Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
+ordering.
+\skip belt
+\until trousers
+We label them...
+\skip label
+\until trousers
+Then add arcs 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
 
 LEMON also contains visitor based algorithm classes for