# Changeset 49:c8c5a2a4ec71 in lemon-tutorial

Ignore:
Timestamp:
02/22/10 02:03:25 (12 years ago)
Branch:
default
Phase:
public
Message:

Port the remaining 0.x tutorial contents from SVN -r 3524

Files:
2 edited

Unmodified
Removed
• ## algorithms.dox

 r46 In addition to the graph structures, the most important parts of LEMON are the various algorithm implementations, which can be used quite flexibly and efficiently. the various algorithms related to graph theory and combinatorial optimization. The library probvides quite flexible and efficient implementations for well-known fundamental algorithms, such as breadth-first search (BFS), depth-first search (DFS), Dijkstra algorithm, Kruskal algorithm and methods for discovering graph properties like connectivity, bipartiteness or Euler property, as well as more complex optimization algorithms for finding maximum flows, minimum cuts, matchings, minimum cost flows and arc-disjoint paths. In this section, we present only some of the most fundamental algorithms. [SEC]sec_graph_search[SEC] Graph Search \todo The following contents are ported from the LEMON 0.x tutorial, thus they have to thouroughly revised, reorganized and reworked. See \ref Bfs, \ref Dfs and \ref graph_properties. 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. 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 \b TR.
GR is the digraph the algorithm runs on. It has \ref lemon::ListDigraph "ListDigraph" 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". To use the class, declare it! \code Bfs  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.
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()".
Or more directly with other member functions like \ref lemon::Bfs::predNode "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( ListGraph::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 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. 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 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 \todo Check the linking of the demo file, the code samples are missing. More algorithms are described in the \ref algorithms2 "second part". [SEC]sec_shortest_paths[SEC] Shortest Paths See \ref Dijkstra and \ref BellmanFord. If you want to solve some transportation problems in a network then you will want to find shortest paths between nodes of a graph. This is usually solved using Dijkstra's algorithm. A utility that solves this is the LEMON Dijkstra class. The following code is a simple program using the LEMON Dijkstra class: it calculates the shortest path between node s and t in a graph g. We omit the part reading the graph g and the length map len.
In LEMON, the algorithms are implemented basically as classes, but for some of them, function-type interfaces are also available for the sake of convenience. For instance, the Dijkstra algorithm is implemented in the \ref Dijkstra template class, but the \ref dijkstra() function is also defined, which can still be used quite flexibly due to named parameters. The original sample code could also use the class interface as follows. \code Dijkstra dijktra(g, length); dijkstra.distMap(dist); dijsktra.init(); dijkstra.addSource(u); dijkstra.start(); \endcode The previous code is obviously longer than the original, but the execution can be controlled to a higher extent. While using the function-type interface, only one source can be added to the algorithm, the class interface makes it possible to specify several root nodes. Moreover, the algorithm can also be executed step-by-step. For instance, the following code can be used instead of \ref dijkstra.start(). \code while (!dijkstra.emptyQueue()) { ListDigraph::Node n = dijkstra.processNextNode(); cout << g.id(n) << ' ' << dijkstra.dist(g) << endl; } \endcode [SEC]sec_max_flow[SEC] Maximum Flows
• ## maps.dox

 r46 \todo This page is under construction. \todo The following contents are ported from the LEMON 0.x tutorial, thus they have to thouroughly revised, reorganized and reworked. The LEMON maps are not only just storage classes, but also they are %concepts of any key--value based data access. Beside the standard digraph maps, LEMON contains several "lightweight" \e map \e adaptor \e classes, which perform various operations on the data of the adapted maps when their access operations are called, but without actually copying or modifying the original storage. 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: \code typedef Arc Key; typedef double Value; \endcode A map can be \e readable (\ref lemon::concepts::ReadMap "ReadMap", for short), \e writable (\ref lemon::concepts::WriteMap "WriteMap") or both (\ref lemon::concepts::ReadWriteMap "ReadWriteMap"). There also exists a special type of ReadWrite map called \ref lemon::concepts::ReferenceMap "reference map". In addition that you can read and write the values of a key, a reference map can also give you a reference to the value belonging to a key, so you have a direct access to the memory address where it is stored. Each digraph structure in LEMON provides two standard map templates called \c ArcMap and \c NodeMap. Both are reference maps and you can easily assign data to the nodes and to the arcs of the digraph. For example if you have a digraph \c g defined as \code ListDigraph g; \endcode and you want to assign a floating point value to each arc, you can do it like this. \code ListDigraph::ArcMap length(g); \endcode Note that you must give the underlying digraph to the constructor. The value of a readable map can be obtained by operator[]. \code d=length[e]; \endcode where \c e is an instance of \c ListDigraph::Arc. (Or anything else that converts to \c ListDigraph::Arc, like  \c ListDigraph::ArcIt or \c ListDigraph::OutArcIt etc.) There are two ways to assign a new value to a key - In case of a reference map operator[] gives you a reference to the value, thus you can use this. \code length[e]=3.5; \endcode - Writable maps have a member function \c set(Key,const Value &) for this purpose. \code length.set(e,3.5); \endcode The first case is more comfortable and if you store complex structures in your map, it might be more efficient. However, there are writable but not reference maps, so if you want to write a generic algorithm, you should insist on the second way. \section how-to-write-your-own-map How to Write Your Own Maps \subsection read-maps Readable Maps Readable maps are very frequently used as the input of an algorithm.  For this purpose the most straightforward way is the use of the default maps provided by LEMON's digraph structures. Very often however, it is more convenient and/or more efficient to write your own readable map. You can find some examples below. In these examples \c Digraph is the type of the particular digraph structure you use. This simple map assigns \f$\pi\f$ to each arc. \code struct MyMap { typedef double Value; typedef Digraph::Arc Key; double operator[](Key e) const { return PI;} }; \endcode An alternative way to define maps is to use \c MapBase \code struct MyMap : public MapBase { Value operator[](Key e) const { return PI;} }; \endcode Here is a bit more complex example. It provides a length function obtained from a base length function shifted by a potential difference. \code class ReducedLengthMap  : public MapBase { const Digraph &g; const Digraph::ArcMap &orig_len; const Digraph::NodeMap &pot; public: Value operator[](Key e) const { return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]); } ReducedLengthMap(const Digraph &_g, const Digraph::ArcMap &_o, const Digraph::NodeMap &_p) : g(_g), orig_len(_o), pot(_p) {}; }; \endcode Then, you can call e.g. Dijkstra algoritm on this map like this: \code ... ReducedLengthMap rm(g,len,pot); Dijkstra dij(g,rm); dij.run(s); ... \endcode In the previous section we discussed digraph topology. That is the skeleton a complex digraph represented data-set needs. But how to assign the data itself to that skeleton?
Here come the \b maps in. \section maps_intro Introduction to maps Maps play a central role in LEMON. As their name suggests, they map a certain range of keys to certain values. In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this: \code typedef Arc Key; typedef double Value; \endcode (Except matrix maps, they have two key types.) To make easy to use them - especially as template parameters - there are map concepts like by digraph classes.
• \ref concepts::ReadMap "ReadMap" - values can be read out with the \c operator[]. \code value_typed_variable = map_instance[key_value]; \endcode
• \ref concepts::WriteMap "WriteMap" - values can be set with the \c set() member function. \code map_instance.set(key_value, value_typed_expression); \endcode
• \ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both readable and writable. It is delivered from them.
• \ref concepts::ReferenceMap "ReferenceMap" - a subclass of ReadWriteMap. It has two additional typedefs Reference and ConstReference and two overloads of \c operator[] to providing you constant or non-constant reference to the value belonging to a key, so you have a direct access to the memory address where it is stored.
• And there are the Matrix version of these maps, where the values are assigned to a pair of keys. The keys can be different types. (\ref concepts::ReadMatrixMap "ReadMatrixMap", \ref concepts::WriteMatrixMap "WriteMatrixMap", \ref concepts::ReadWriteMatrixMap "ReadWriteMatrixMap", \ref concepts::ReferenceMatrixMap "ReferenceMatrixMap")
\section maps_graph Digraphs' maps Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap and ArcMap satisfying the \ref DigraphMap concept. If you want to assign data to nodes, just declare a NodeMap with the corresponding type. As an example, think of a arc-weighted digraph. \code ListDigraph::ArcMap  weight(digraph); \endcode You can see that the map needs the digraph whose arcs will mapped, but nothing more. If the digraph class is extendable or erasable the map will automatically follow the changes you make. If a new node is added a default value is mapped to it. You can define the default value by passing a second argument to the map's constructor. \code ListDigraph::ArcMap  weight(digraph, 13); \endcode But keep in mind that \c VALUE has to have copy constructor. Of course \c VALUE can be a rather complex type. For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)! \dontinclude maps_summary.cc \skip template \until } The task is simple. We need the summary of some kind of data assigned to a digraph's nodes. (Whit a little trick the summary can be calculated only to a sub-digraph without changing this code. See \ref SubDigraph techniques - that's LEMON's true potential.) And the usage is simpler than the declaration suggests. The compiler deduces the template specialization, so the usage is like a simple function call. \skip std \until ; 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. If you want some 'real-life' examples see the next page, where we discuss \ref algorithms (coming soon) and will use maps hardly. Or if you want to know more about maps read these \ref maps2 "advanced map techniques". Here we discuss some advanced map techniques. Like writing your own maps or how to extend/modify a maps functionality with adaptors. \section custom_maps Writing Custom ReadMap \subsection custom_read_maps Readable Maps Readable maps are very frequently used as the input of an algorithm.  For this purpose the most straightforward way is the use of the default maps provided by LEMON's digraph structures. Very often however, it is more convenient and/or more efficient to write your own readable map. You can find some examples below. In these examples \c Digraph is the type of the particular digraph structure you use. This simple map assigns \f$\pi\f$ to each arc. \code struct MyMap { typedef double Value; typedef Digraph::Arc Key; double operator[](const Key &e) const { return PI;} }; \endcode An alternative way to define maps is to use MapBase \code struct MyMap : public MapBase { Value operator[](const Key& e) const { return PI;} }; \endcode Here is a bit more complex example. It provides a length function obtained from a base length function shifted by a potential difference. \code class ReducedLengthMap  : public MapBase { const Digraph &g; const Digraph::ArcMap &orig_len; const Digraph::NodeMap &pot; public: Value operator[](Key e) const { return orig_len[e]-(pot[g.target(e)]-pot[g.source(e)]); } ReducedLengthMap(const Digraph &_g, const Digraph::ArcMap &_o, const Digraph::NodeMap &_p) : g(_g), orig_len(_o), pot(_p) {}; }; \endcode Then, you can call e.g. Dijkstra algoritm on this map like this: \code ... ReducedLengthMap rm(g,len,pot); Dijkstra dij(g,rm); dij.run(s); ... \endcode [SEC]sec_map_concepts[SEC] Map Concepts [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 ef ProcessedMap, which has to be a writable node map of \ref bool value type. The assigned value of each node is set to \ref true when the node is processed, i.e., its actual distance is found. Applying a special map, \ref LoggerBoolMap, the processed order of the nodes can easily be stored in a standard container. Such specific map types can be passed to the algorithms using the technique of named template parameters. Similarly to the named function parameters, they allow specifying any subset of the parameters and in arbitrary order. \code typedef vector Container; typedef back_insert_iterator InsertIterator; typedef LoggerBoolMap ProcessedMap; Dijkstra ::SetProcessedMap ::Create dijktra(g, length); Container container; InsertIterator iterator(container); ProcessedMap processed(iterator); dijkstra.processedMap(processed).run(s); \endcode The function-type interfaces are considerably simpler, but they can be used in almost all practical cases. Surprisingly, even the above example can also be implemented using the \ref dijkstra() function and named parameters, as follows. Note that the function-type interface has the major advantage that temporary objects can be passed as parameters. \code vector process_order; dijkstra(g, length) .processedMap(loggerBoolMap(back_inserter(process_order))) .run(s); \endcode LEMON also contains visitor based algorithm classes for BFS and DFS. Skeleton visitor classes are defined for both BFS and DFS, the concrete implementations can be inherited from them. \code template struct DfsVisitor { void start(const typename GR::Node& node) {} void stop(const typename GR::Node& node) {} void reach(const typename GR::Node& node) {} void leave(const typename GR::Node& node) {} void discover(const typename GR::Arc& arc) {} void examine(const typename GR::Arc& arc) {} void backtrack(const typename GR::Arc& arc) {} }; \endcode In the following example, the \ref discover()} and \code{examine() events are processed and the DFS tree is stored in an arc map. The values of this map indicate whether the corresponding arc reaches a new node or its target node is already reached. \code template struct TreeVisitor : public DfsVisitor { TreeVisitor(typename GR::ArcMap& tree) : _tree(tree) {} void discover(const typename GR::Arc& arc) { _tree[arc] = true; } void examine(const typename GR::Arc& arc) { _tree[arc] = false; } typename GR::ArcMap& _tree; }; \endcode [TRAILER]
Note: See TracChangeset for help on using the changeset viewer.