1.1 --- a/maps.dox Mon Mar 01 02:28:44 2010 +0100
1.2 +++ b/maps.dox Mon Mar 01 02:30:00 2010 +0100
1.3 @@ -36,18 +36,6 @@
1.4 These classes also conform to the map %concepts, thus they can be used
1.5 like standard LEMON maps.
1.6
1.7 -Let us suppose that we have a traffic network stored in a LEMON digraph
1.8 -structure with two arc maps \c length and \c speed, which
1.9 -denote the physical length of each arc and the maximum (or average)
1.10 -speed that can be achieved on the corresponding road-section,
1.11 -respectively. If we are interested in the best traveling times,
1.12 -the following code can be used.
1.13 -
1.14 -\code
1.15 - dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
1.16 -\endcode
1.17 -
1.18 -
1.19 Maps play a central role in LEMON. As their name suggests, they map a
1.20 certain range of \e keys to certain \e values. Each map has two
1.21 <tt>typedef</tt>'s to determine the types of keys and values, like this:
1.22 @@ -335,6 +323,7 @@
1.23
1.24 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
1.25
1.26 +
1.27 The basic functionality of the algorithms can be highly extended using
1.28 special purpose map types for their internal data structures.
1.29 For example, the \ref Dijkstra class stores a
1.30 @@ -349,6 +338,17 @@
1.31 named template parameters. Similarly to the named function parameters,
1.32 they allow specifying any subset of the parameters and in arbitrary order.
1.33
1.34 +Let us suppose that we have a traffic network stored in a LEMON digraph
1.35 +structure with two arc maps \c length and \c speed, which
1.36 +denote the physical length of each arc and the maximum (or average)
1.37 +speed that can be achieved on the corresponding road-section,
1.38 +respectively. If we are interested in the best traveling times,
1.39 +the following code can be used.
1.40 +
1.41 +\code
1.42 + dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
1.43 +\endcode
1.44 +
1.45 \code
1.46 typedef vector<ListDigraph::Node> Container;
1.47 typedef back_insert_iterator<Container> InsertIterator;
1.48 @@ -378,6 +378,56 @@
1.49 .run(s);
1.50 \endcode
1.51
1.52 +Let us see a bit more complex example to demonstrate Dfs's capabilities.
1.53 +
1.54 +We will see a program, which solves the problem of <b>topological ordering</b>.
1.55 +We need to know in which order we should put on our clothes. The program will do the following:
1.56 +<ol>
1.57 +<li>We run the dfs algorithm to all nodes.
1.58 +<li>Put every node into a list when processed completely.
1.59 +<li>Write out the list in reverse order.
1.60 +</ol>
1.61 +
1.62 +\dontinclude topological_ordering.cc
1.63 +First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
1.64 +will be done through it.
1.65 +\skip MyOrdererMap
1.66 +\until };
1.67 +The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
1.68 +we need to do is insert the key - that is the node whose processing just finished - into the beginning
1.69 +of the list.<br>
1.70 +Although we implemented this needed helper class ourselves it was not necessary.
1.71 +The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
1.72 +what we needed. To be correct it's more general - and it's all in \c LEMON. But
1.73 +we wanted to show you, how easy is to add additional functionality.
1.74 +
1.75 +First we declare the needed data structures: the digraph and a map to store the nodes' label.
1.76 +\skip ListDigraph
1.77 +\until label
1.78 +
1.79 +Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
1.80 +ordering.
1.81 +\skip belt
1.82 +\until trousers
1.83 +We label them...
1.84 +\skip label
1.85 +\until trousers
1.86 +Then add arcs which represent the precedences between those items.
1.87 +\skip trousers, belt
1.88 +\until );
1.89 +
1.90 +See how easy is to access the internal information of this algorithm trough maps.
1.91 +We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
1.92 +\skip Dfs
1.93 +\until run
1.94 +
1.95 +And now comes the third part. Write out the list in reverse order. But the list was
1.96 +composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
1.97 +\skip std
1.98 +\until endl
1.99 +
1.100 +The program is to be found in the \ref demo directory: \ref topological_ordering.cc
1.101 +
1.102 LEMON also contains visitor based algorithm classes for
1.103 BFS and DFS.
1.104