Index: algorithms.dox =================================================================== --- algorithms.dox (revision 46) +++ algorithms.dox (revision 49) @@ -24,6 +24,12 @@ 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. @@ -32,9 +38,184 @@ [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 Index: maps.dox =================================================================== --- maps.dox (revision 46) +++ maps.dox (revision 49) @@ -23,4 +23,299 @@ \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 @@ -39,5 +334,82 @@ [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]