1.1 --- a/algorithms.dox Mon Feb 22 02:00:51 2010 +0100
1.2 +++ b/algorithms.dox Mon Feb 22 02:03:25 2010 +0100
1.3 @@ -23,20 +23,201 @@
1.4 \todo This page is under construction.
1.5
1.6 In addition to the graph structures, the most important parts of LEMON are
1.7 -the various algorithm implementations, which can be used quite flexibly and
1.8 -efficiently.
1.9 +the various algorithms related to graph theory and combinatorial optimization.
1.10 +The library probvides quite flexible and efficient implementations
1.11 +for well-known fundamental algorithms, such as breadth-first
1.12 +search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm
1.13 +and methods for discovering graph properties like connectivity, bipartiteness
1.14 +or Euler property, as well as more complex optimization algorithms for finding
1.15 +maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint
1.16 +paths.
1.17
1.18 In this section, we present only some of the most fundamental algorithms.
1.19 For a complete overview, see the \ref algs module of the reference manual.
1.20
1.21 [SEC]sec_graph_search[SEC] Graph Search
1.22
1.23 +\todo The following contents are ported from the LEMON 0.x tutorial,
1.24 +thus they have to thouroughly revised, reorganized and reworked.
1.25 +
1.26 See \ref Bfs, \ref Dfs and \ref graph_properties.
1.27
1.28 +Both \ref lemon::Bfs "Bfs" and \ref lemon::Dfs "Dfs" are highly adaptable and efficient
1.29 +implementations of the well known algorithms. The algorithms are placed most cases in
1.30 +separated files named after the algorithm itself but lower case as all other header file names.
1.31 +For example the next Bfs class is in the \c lemon/bfs.h.
1.32 +
1.33 +The algorithm is implemented in the \ref lemon::Bfs "Bfs" template class - rather than as function.
1.34 +The class has two template parameters: \b GR and \b TR.<br>
1.35 +GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" as default type.
1.36 +TR is a Traits class commonly used to easy the parametrization of templates. In most cases you
1.37 +wont need to modify the default type \ref lemon::BfsDefaultTraits "BfsDefaultTraits<GR>".
1.38 +
1.39 +To use the class, declare it!
1.40 +\code
1.41 +Bfs<ListGraph> bfs(gr);
1.42 +\endcode
1.43 +Note the lack of second template argument because of the default parameter.
1.44 +
1.45 +It provides a simple but powerful interface to control the execution.
1.46 +\code
1.47 +int dist = bfs.run(s,t);
1.48 +\endcode
1.49 +It finds the shortest path from node \c s to node \c t and returns it, or zero
1.50 +if there is no path from \c s to \c t.<br>
1.51 +If you want the shortest path from a specified node to all other node, just write:
1.52 +\code
1.53 +bfs.run(s);
1.54 +\endcode
1.55 +Now the distances and path information are stored in maps which you can access with
1.56 +member functions like \ref lemon::Bfs::distMap "distMap()" or \ref lemon::Bfs::predMap "predMap()".<br>
1.57 +Or more directly with other member functions like \ref lemon::Bfs::predNode "predNode()". Once the algorithm
1.58 +is finished (or to be precise reached that node) \ref lemon::Bfs::dist "dist()" or \ref lemon::Bfs::predNode
1.59 +"predNode()" can be called.
1.60 +
1.61 +For an example let's say we want to print the shortest path of those nodes which
1.62 +are in a certain distance.
1.63 +\code
1.64 +bfs.run(s);
1.65 +
1.66 +for( ListGraph::NodeIt n(gr); n != INVALID; ++n ) {
1.67 + if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
1.68 + std::cout << gr.id(n);
1.69 +
1.70 + Node prev = bfs.prevNode(n);
1.71 + while( prev != INVALID ) {
1.72 + std::cout << "<-" << gr.id(prev);
1.73 + prev = bfs.prevNode(n);
1.74 + }
1.75 +
1.76 + std::cout << std::endl;
1.77 + }
1.78 +}
1.79 +\endcode
1.80 +
1.81 +In the previous code we only used \c run(). Now we introduce the way you can directly
1.82 +control the execution of the algorithm.
1.83 +
1.84 +First you have to initialize the variables with \ref lemon::Bfs::init "init()".
1.85 +\code
1.86 + bfs.init();
1.87 +\endcode
1.88 +
1.89 +Then you add one or more source nodes to the queue. They will be processed, as they would
1.90 +be reached by the algorithm before. And yes - you can add more sources during the execution.
1.91 +\code
1.92 + bfs.addSource(node_1);
1.93 + bfs.addSource(node_2);
1.94 + ...
1.95 +\endcode
1.96 +
1.97 +And finally you can start the process with \ref lemon::Bfs::start "start()", or
1.98 +you can write your own loop to process the nodes one-by-one.
1.99 +
1.100 +
1.101 +Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example
1.102 +to demonstrate Dfs's capabilities.
1.103 +
1.104 +We will see a program, which solves the problem of <b>topological ordering</b>.
1.105 +We need to know in which order we should put on our clothes. The program will do the following:
1.106 +<ol>
1.107 +<li>We run the dfs algorithm to all nodes.
1.108 +<li>Put every node into a list when processed completely.
1.109 +<li>Write out the list in reverse order.
1.110 +</ol>
1.111 +
1.112 +\dontinclude topological_ordering.cc
1.113 +First of all we will need an own \ref lemon::Dfs::ProcessedMap "ProcessedMap". The ordering
1.114 +will be done through it.
1.115 +\skip MyOrdererMap
1.116 +\until };
1.117 +The class meets the \ref concepts::WriteMap "WriteMap" concept. In it's \c set() method the only thing
1.118 +we need to do is insert the key - that is the node whose processing just finished - into the beginning
1.119 +of the list.<br>
1.120 +Although we implemented this needed helper class ourselves it was not necessary.
1.121 +The \ref lemon::FrontInserterBoolMap "FrontInserterBoolMap" class does exactly
1.122 +what we needed. To be correct it's more general - and it's all in \c LEMON. But
1.123 +we wanted to show you, how easy is to add additional functionality.
1.124 +
1.125 +First we declare the needed data structures: the digraph and a map to store the nodes' label.
1.126 +\skip ListDigraph
1.127 +\until label
1.128 +
1.129 +Now we build a digraph. But keep in mind that it must be DAG because cyclic digraphs has no topological
1.130 +ordering.
1.131 +\skip belt
1.132 +\until trousers
1.133 +We label them...
1.134 +\skip label
1.135 +\until trousers
1.136 +Then add arcs which represent the precedences between those items.
1.137 +\skip trousers, belt
1.138 +\until );
1.139 +
1.140 +See how easy is to access the internal information of this algorithm trough maps.
1.141 +We only need to set our own map as the class's \ref lemon::Dfs::ProcessedMap "ProcessedMap".
1.142 +\skip Dfs
1.143 +\until run
1.144 +
1.145 +And now comes the third part. Write out the list in reverse order. But the list was
1.146 +composed in reverse way (with \c push_front() instead of \c push_back() so we just iterate it.
1.147 +\skip std
1.148 +\until endl
1.149 +
1.150 +The program is to be found in the \ref demo directory: \ref topological_ordering.cc
1.151 +
1.152 +\todo Check the linking of the demo file, the code samples are missing.
1.153 +
1.154 +More algorithms are described in the \ref algorithms2 "second part".
1.155 +
1.156 +
1.157 [SEC]sec_shortest_paths[SEC] Shortest Paths
1.158
1.159 See \ref Dijkstra and \ref BellmanFord.
1.160
1.161 +
1.162 +If you want to solve some transportation problems in a network then you
1.163 +will want to find shortest paths between nodes of a graph. This is
1.164 +usually solved using Dijkstra's algorithm. A utility that solves this is
1.165 +the LEMON Dijkstra class. The following code is a simple program using
1.166 +the LEMON Dijkstra class: it calculates the shortest path between node s
1.167 +and t in a graph g. We omit the part reading the graph g and the length
1.168 +map len.
1.169 +
1.170 +<hr>
1.171 +
1.172 +In LEMON, the algorithms are implemented basically as classes, but
1.173 +for some of them, function-type interfaces are also available
1.174 +for the sake of convenience.
1.175 +For instance, the Dijkstra algorithm is implemented in the \ref Dijkstra
1.176 +template class, but the \ref dijkstra() function is also defined,
1.177 +which can still be used quite flexibly due to named parameters.
1.178 +
1.179 +The original sample code could also use the class interface as follows.
1.180 +
1.181 +\code
1.182 + Dijkstra<ListDigraph> dijktra(g, length);
1.183 + dijkstra.distMap(dist);
1.184 + dijsktra.init();
1.185 + dijkstra.addSource(u);
1.186 + dijkstra.start();
1.187 +\endcode
1.188 +
1.189 +The previous code is obviously longer than the original, but the
1.190 +execution can be controlled to a higher extent. While using the function-type
1.191 +interface, only one source can be added to the algorithm, the class
1.192 +interface makes it possible to specify several root nodes.
1.193 +Moreover, the algorithm can also be executed step-by-step. For instance,
1.194 +the following code can be used instead of \ref dijkstra.start().
1.195 +
1.196 +\code
1.197 + while (!dijkstra.emptyQueue()) {
1.198 + ListDigraph::Node n = dijkstra.processNextNode();
1.199 + cout << g.id(n) << ' ' << dijkstra.dist(g) << endl;
1.200 + }
1.201 +\endcode
1.202 +
1.203 +
1.204 [SEC]sec_max_flow[SEC] Maximum Flows
1.205
1.206 See \ref Preflow.
2.1 --- a/maps.dox Mon Feb 22 02:00:51 2010 +0100
2.2 +++ b/maps.dox Mon Feb 22 02:03:25 2010 +0100
2.3 @@ -22,6 +22,301 @@
2.4
2.5 \todo This page is under construction.
2.6
2.7 +\todo The following contents are ported from the LEMON 0.x tutorial,
2.8 +thus they have to thouroughly revised, reorganized and reworked.
2.9 +
2.10 +The LEMON maps are not only just storage classes, but also
2.11 +they are %concepts of any key--value based data access.
2.12 +Beside the standard digraph maps, LEMON contains several "lightweight"
2.13 +\e map \e adaptor \e classes, which perform various operations on the
2.14 +data of the adapted maps when their access operations are called,
2.15 +but without actually copying or modifying the original storage.
2.16 +These classes also conform to the map %concepts, thus they can be used
2.17 +like standard LEMON maps.
2.18 +
2.19 +Let us suppose that we have a traffic network stored in a LEMON digraph
2.20 +structure with two arc maps \c length and \c speed, which
2.21 +denote the physical length of each arc and the maximum (or average)
2.22 +speed that can be achieved on the corresponding road-section,
2.23 +respectively. If we are interested in the best traveling times,
2.24 +the following code can be used.
2.25 +
2.26 +\code
2.27 + dijkstra(g, divMap(length, speed)).distMap(dist).run(s);
2.28 +\endcode
2.29 +
2.30 +
2.31 +Maps play a central role in LEMON. As their name suggests, they map a
2.32 +certain range of \e keys to certain \e values. Each map has two
2.33 +<tt>typedef</tt>'s to determine the types of keys and values, like this:
2.34 +
2.35 +\code
2.36 + typedef Arc Key;
2.37 + typedef double Value;
2.38 +\endcode
2.39 +
2.40 +A map can be
2.41 +\e readable (\ref lemon::concepts::ReadMap "ReadMap", for short),
2.42 +\e writable (\ref lemon::concepts::WriteMap "WriteMap") or both
2.43 +(\ref lemon::concepts::ReadWriteMap "ReadWriteMap").
2.44 +There also exists a special type of
2.45 +ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map".
2.46 +In addition that you can
2.47 +read and write the values of a key, a reference map
2.48 +can also give you a reference to the
2.49 +value belonging to a key, so you have a direct access to the memory address
2.50 +where it is stored.
2.51 +
2.52 +Each digraph structure in LEMON provides two standard map templates called
2.53 +\c ArcMap and \c NodeMap. Both are reference maps and you can easily
2.54 +assign data to the nodes and to the arcs of the digraph. For example if you
2.55 +have a digraph \c g defined as
2.56 +\code
2.57 + ListDigraph g;
2.58 +\endcode
2.59 +and you want to assign a floating point value to each arc, you can do
2.60 +it like this.
2.61 +\code
2.62 + ListDigraph::ArcMap<double> length(g);
2.63 +\endcode
2.64 +Note that you must give the underlying digraph to the constructor.
2.65 +
2.66 +The value of a readable map can be obtained by <tt>operator[]</tt>.
2.67 +\code
2.68 + d=length[e];
2.69 +\endcode
2.70 +where \c e is an instance of \c ListDigraph::Arc.
2.71 +(Or anything else
2.72 +that converts to \c ListDigraph::Arc, like \c ListDigraph::ArcIt or
2.73 +\c ListDigraph::OutArcIt etc.)
2.74 +
2.75 +There are two ways to assign a new value to a key
2.76 +
2.77 +- In case of a <em>reference map</em> <tt>operator[]</tt>
2.78 +gives you a reference to the
2.79 +value, thus you can use this.
2.80 +\code
2.81 + length[e]=3.5;
2.82 +\endcode
2.83 +- <em>Writable maps</em> have
2.84 +a member function \c set(Key,const Value &)
2.85 +for this purpose.
2.86 +\code
2.87 + length.set(e,3.5);
2.88 +\endcode
2.89 +
2.90 +The first case is more comfortable and if you store complex structures in your
2.91 +map, it might be more efficient. However, there are writable but
2.92 +not reference maps, so if you want to write a generic algorithm, you should
2.93 +insist on the second way.
2.94 +
2.95 +\section how-to-write-your-own-map How to Write Your Own Maps
2.96 +
2.97 +\subsection read-maps Readable Maps
2.98 +
2.99 +Readable maps are very frequently used as the input of an
2.100 +algorithm. For this purpose the most straightforward way is the use of the
2.101 +default maps provided by LEMON's digraph structures.
2.102 +Very often however, it is more
2.103 +convenient and/or more efficient to write your own readable map.
2.104 +
2.105 +You can find some examples below. In these examples \c Digraph is the
2.106 +type of the particular digraph structure you use.
2.107 +
2.108 +
2.109 +This simple map assigns \f$\pi\f$ to each arc.
2.110 +
2.111 +\code
2.112 +struct MyMap
2.113 +{
2.114 + typedef double Value;
2.115 + typedef Digraph::Arc Key;
2.116 + double operator[](Key e) const { return PI;}
2.117 +};
2.118 +\endcode
2.119 +
2.120 +An alternative way to define maps is to use \c MapBase
2.121 +
2.122 +\code
2.123 +struct MyMap : public MapBase<Digraph::Arc,double>
2.124 +{
2.125 + Value operator[](Key e) const { return PI;}
2.126 +};
2.127 +\endcode
2.128 +
2.129 +Here is a bit more complex example.
2.130 +It provides a length function obtained
2.131 +from a base length function shifted by a potential difference.
2.132 +
2.133 +\code
2.134 +class ReducedLengthMap : public MapBase<Digraph::Arc,double>
2.135 +{
2.136 + const Digraph &g;
2.137 + const Digraph::ArcMap<double> &orig_len;
2.138 + const Digraph::NodeMap<double> &pot;
2.139 +
2.140 +public:
2.141 + Value operator[](Key e) const {
2.142 + return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
2.143 + }
2.144 +
2.145 + ReducedLengthMap(const Digraph &_g,
2.146 + const Digraph::ArcMap &_o,
2.147 + const Digraph::NodeMap &_p)
2.148 + : g(_g), orig_len(_o), pot(_p) {};
2.149 +};
2.150 +\endcode
2.151 +
2.152 +Then, you can call e.g. Dijkstra algoritm on this map like this:
2.153 +\code
2.154 + ...
2.155 + ReducedLengthMap rm(g,len,pot);
2.156 + Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
2.157 + dij.run(s);
2.158 + ...
2.159 +\endcode
2.160 +
2.161 +
2.162 +In the previous section we discussed digraph topology. That is the skeleton a complex
2.163 +digraph represented data-set needs. But how to assign the data itself to that skeleton?<br>
2.164 +Here come the \b maps in.
2.165 +
2.166 +\section maps_intro Introduction to maps
2.167 +Maps play a central role in LEMON. As their name suggests, they map a certain range of <i>keys</i> to certain <i>values</i>.
2.168 +In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this:
2.169 +\code
2.170 + typedef Arc Key;
2.171 + typedef double Value;
2.172 +\endcode
2.173 +(Except matrix maps, they have two key types.)
2.174 +
2.175 +To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by digraph classes.
2.176 +<ul>
2.177 +<li>\ref concepts::ReadMap "ReadMap" - values can be read out with the \c operator[].
2.178 +\code value_typed_variable = map_instance[key_value]; \endcode
2.179 +</li>
2.180 +<li>\ref concepts::WriteMap "WriteMap" - values can be set with the \c set() member function.
2.181 +\code map_instance.set(key_value, value_typed_expression); \endcode
2.182 +</li>
2.183 +<li>\ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both
2.184 +readable and writable. It is delivered from them.
2.185 +</li>
2.186 +<li>\ref concepts::ReferenceMap "ReferenceMap" - a subclass of ReadWriteMap. It has two additional typedefs
2.187 +<i>Reference</i> and <i>ConstReference</i> and two overloads of \c operator[] to
2.188 +providing you constant or non-constant reference to the value belonging to a key,
2.189 +so you have a direct access to the memory address where it is stored.
2.190 +</li>
2.191 +<li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys.
2.192 +The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap",
2.193 +\ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap",
2.194 +\ref concepts::ReferenceMatrixMap "ReferenceMatrixMap")
2.195 +</li>
2.196 +</ul>
2.197 +
2.198 +\section maps_graph Digraphs' maps
2.199 +Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE>
2.200 +satisfying the \ref DigraphMap concept.
2.201 +If you want to assign data to nodes, just declare a NodeMap with the corresponding
2.202 +type. As an example, think of a arc-weighted digraph.
2.203 +\code ListDigraph::ArcMap<int> weight(digraph); \endcode
2.204 +You can see that the map needs the digraph whose arcs will mapped, but nothing more.
2.205 +
2.206 +If the digraph class is extendable or erasable the map will automatically follow
2.207 +the changes you make. If a new node is added a default value is mapped to it.
2.208 +You can define the default value by passing a second argument to the map's constructor.
2.209 +\code ListDigraph::ArcMap<int> weight(digraph, 13); \endcode
2.210 +But keep in mind that \c VALUE has to have copy constructor.
2.211 +
2.212 +Of course \c VALUE can be a rather complex type.
2.213 +
2.214 +For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)!
2.215 +\dontinclude maps_summary.cc
2.216 +\skip template
2.217 +\until }
2.218 +The task is simple. We need the summary of some kind of data assigned to a digraph's nodes.
2.219 +(Whit a little trick the summary can be calculated only to a sub-digraph without changing
2.220 +this code. See \ref SubDigraph techniques - that's LEMON's true potential.)
2.221 +
2.222 +And the usage is simpler than the declaration suggests. The compiler deduces the
2.223 +template specialization, so the usage is like a simple function call.
2.224 +\skip std
2.225 +\until ;
2.226 +
2.227 +Most of the time you will probably use digraph maps, but keep in mind, that in LEMON maps are more general and can be used widely.
2.228 +
2.229 +If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
2.230 +(coming soon) and will use maps hardly.
2.231 +Or if you want to know more about maps read these \ref maps2 "advanced map techniques".
2.232 +
2.233 +Here we discuss some advanced map techniques. Like writing your own maps or how to
2.234 +extend/modify a maps functionality with adaptors.
2.235 +
2.236 +\section custom_maps Writing Custom ReadMap
2.237 +\subsection custom_read_maps Readable Maps
2.238 +
2.239 +Readable maps are very frequently used as the input of an
2.240 +algorithm. For this purpose the most straightforward way is the use of the
2.241 +default maps provided by LEMON's digraph structures.
2.242 +Very often however, it is more
2.243 +convenient and/or more efficient to write your own readable map.
2.244 +
2.245 +You can find some examples below. In these examples \c Digraph is the
2.246 +type of the particular digraph structure you use.
2.247 +
2.248 +
2.249 +This simple map assigns \f$\pi\f$ to each arc.
2.250 +
2.251 +\code
2.252 +struct MyMap
2.253 +{
2.254 + typedef double Value;
2.255 + typedef Digraph::Arc Key;
2.256 + double operator[](const Key &e) const { return PI;}
2.257 +};
2.258 +\endcode
2.259 +
2.260 +An alternative way to define maps is to use MapBase
2.261 +
2.262 +\code
2.263 +struct MyMap : public MapBase<Digraph::Arc,double>
2.264 +{
2.265 + Value operator[](const Key& e) const { return PI;}
2.266 +};
2.267 +\endcode
2.268 +
2.269 +Here is a bit more complex example.
2.270 +It provides a length function obtained
2.271 +from a base length function shifted by a potential difference.
2.272 +
2.273 +\code
2.274 +class ReducedLengthMap : public MapBase<Digraph::Arc,double>
2.275 +{
2.276 + const Digraph &g;
2.277 + const Digraph::ArcMap<double> &orig_len;
2.278 + const Digraph::NodeMap<double> &pot;
2.279 +
2.280 +public:
2.281 + Value operator[](Key e) const {
2.282 + return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]);
2.283 + }
2.284 +
2.285 + ReducedLengthMap(const Digraph &_g,
2.286 + const Digraph::ArcMap &_o,
2.287 + const Digraph::NodeMap &_p)
2.288 + : g(_g), orig_len(_o), pot(_p) {};
2.289 +};
2.290 +\endcode
2.291 +
2.292 +Then, you can call e.g. Dijkstra algoritm on this map like this:
2.293 +\code
2.294 + ...
2.295 + ReducedLengthMap rm(g,len,pot);
2.296 + Dijkstra<Digraph,ReducedLengthMap> dij(g,rm);
2.297 + dij.run(s);
2.298 + ...
2.299 +\endcode
2.300 +
2.301 +
2.302 [SEC]sec_map_concepts[SEC] Map Concepts
2.303
2.304 ...
2.305 @@ -38,7 +333,84 @@
2.306
2.307 [SEC]sec_algs_with_maps[SEC] Using Algorithms with Special Maps
2.308
2.309 -...
2.310 +The basic functionality of the algorithms can be highly extended using
2.311 +special purpose map types for their internal data structures.
2.312 +For example, the \ref Dijkstra class stores a
2.313 +ef ProcessedMap,
2.314 +which has to be a writable node map of \ref bool value type.
2.315 +The assigned value of each node is set to \ref true when the node is
2.316 +processed, i.e., its actual distance is found.
2.317 +Applying a special map, \ref LoggerBoolMap, the processed order of
2.318 +the nodes can easily be stored in a standard container.
2.319 +
2.320 +Such specific map types can be passed to the algorithms using the technique of
2.321 +named template parameters. Similarly to the named function parameters,
2.322 +they allow specifying any subset of the parameters and in arbitrary order.
2.323 +
2.324 +\code
2.325 + typedef vector<ListDigraph::Node> Container;
2.326 + typedef back_insert_iterator<Container> InsertIterator;
2.327 + typedef LoggerBoolMap<InsertIterator> ProcessedMap;
2.328 + Dijkstra<ListDigraph>
2.329 + ::SetProcessedMap<ProcessedMap>
2.330 + ::Create dijktra(g, length);
2.331 +
2.332 + Container container;
2.333 + InsertIterator iterator(container);
2.334 + ProcessedMap processed(iterator);
2.335 +
2.336 + dijkstra.processedMap(processed).run(s);
2.337 +\endcode
2.338 +
2.339 +The function-type interfaces are considerably simpler, but they can be
2.340 +used in almost all practical cases. Surprisingly, even the above example
2.341 +can also be implemented using the \ref dijkstra() function and
2.342 +named parameters, as follows.
2.343 +Note that the function-type interface has the major advantage
2.344 +that temporary objects can be passed as parameters.
2.345 +
2.346 +\code
2.347 + vector<ListDigraph::Node> process_order;
2.348 + dijkstra(g, length)
2.349 + .processedMap(loggerBoolMap(back_inserter(process_order)))
2.350 + .run(s);
2.351 +\endcode
2.352 +
2.353 +LEMON also contains visitor based algorithm classes for
2.354 +BFS and DFS.
2.355 +
2.356 +Skeleton visitor classes are defined for both BFS and DFS, the concrete
2.357 +implementations can be inherited from them.
2.358 +\code
2.359 + template <typename GR>
2.360 + struct DfsVisitor {
2.361 + void start(const typename GR::Node& node) {}
2.362 + void stop(const typename GR::Node& node) {}
2.363 + void reach(const typename GR::Node& node) {}
2.364 + void leave(const typename GR::Node& node) {}
2.365 + void discover(const typename GR::Arc& arc) {}
2.366 + void examine(const typename GR::Arc& arc) {}
2.367 + void backtrack(const typename GR::Arc& arc) {}
2.368 + };
2.369 +\endcode
2.370 +
2.371 +In the following example, the \ref discover()} and \code{examine()
2.372 +events are processed and the DFS tree is stored in an arc map.
2.373 +The values of this map indicate whether the corresponding arc
2.374 +reaches a new node or its target node is already reached.
2.375 +\code
2.376 + template <typename GR>
2.377 + struct TreeVisitor : public DfsVisitor<GR> {
2.378 + TreeVisitor(typename GR::ArcMap<bool>& tree)
2.379 + : _tree(tree) {}
2.380 + void discover(const typename GR::Arc& arc)
2.381 + { _tree[arc] = true; }
2.382 + void examine(const typename GR::Arc& arc)
2.383 + { _tree[arc] = false; }
2.384 + typename GR::ArcMap<bool>& _tree;
2.385 + };
2.386 +\endcode
2.387 +
2.388
2.389 [TRAILER]
2.390 */