diff -r 18404ec968ca -r 10b6a5b7d4c0 maps.dox --- a/maps.dox Mon Mar 01 02:28:44 2010 +0100 +++ b/maps.dox Mon Mar 01 02:30:00 2010 +0100 @@ -36,18 +36,6 @@ 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 certain range of \e keys to certain \e values. Each map has two typedef's to determine the types of keys and values, like this: @@ -335,6 +323,7 @@ [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. For example, the \ref Dijkstra class stores a @@ -349,6 +338,17 @@ named template parameters. Similarly to the named function parameters, 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 Container; typedef back_insert_iterator InsertIterator; @@ -378,6 +378,56 @@ .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 topological ordering. +We need to know in which order we should put on our clothes. The program will do the following: +
    +
  1. We run the dfs algorithm to all nodes. +
  2. Put every node into a list when processed completely. +
  3. Write out the list in reverse order. +
+ +\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.
+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 BFS and DFS.