Changeset 49:c8c5a2a4ec71 in lemon-tutorial

Timestamp:

02/22/10 02:03:25 (14 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

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

Files:

• algorithms.dox (modified) (2 diffs)
• maps.dox (modified) (2 diffs)

algorithms.dox

@@ -24 +24 @@
 
 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 +38 @@
 [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.<br>
+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<GR>".
+
+To use the class, declare it!
+\code
+Bfs<ListGraph>  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.<br>
+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()".<br>
+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 <b>topological ordering</b>.
+We need to know in which order we should put on our clothes. The program will do the following:
+<ol>
+<li>We run the dfs algorithm to all nodes.
+<li>Put every node into a list when processed completely.
+<li>Write out the list in reverse order.
+</ol>
+
+\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.<br>
+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.
+
+<hr>
+ 
+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<ListDigraph> 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

@@ -23 +23 @@
 \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
+<tt>typedef</tt>'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<double> length(g);
+\endcode
+Note that you must give the underlying digraph to the constructor.
+
+The value of a readable map can be obtained by <tt>operator[]</tt>.
+\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 <em>reference map</em> <tt>operator[]</tt>
+gives you a reference to the
+value, thus you can use this.
+\code
+  length[e]=3.5;
+\endcode
+- <em>Writable maps</em> 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<Digraph::Arc,double>
+{
+  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<Digraph::Arc,double>
+{
+  const Digraph &g;
+  const Digraph::ArcMap<double> &orig_len;
+  const Digraph::NodeMap<double> &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<Digraph,ReducedLengthMap> 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?<br>
+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 <i>keys</i> to certain <i>values</i>.
+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 <i>map concepts</i> like by digraph classes.
+<ul>
+<li>\ref concepts::ReadMap "ReadMap" - values can be read out with the \c operator[].
+\code value_typed_variable = map_instance[key_value]; \endcode
+</li>
+<li>\ref concepts::WriteMap "WriteMap" - values can be set with the \c set() member function.
+\code map_instance.set(key_value, value_typed_expression); \endcode
+</li>
+<li>\ref concepts::ReadWriteMap "ReadWriteMap" - it's just a shortcut to indicate that the map is both
+readable and writable. It is delivered from them.
+</li>
+<li>\ref concepts::ReferenceMap "ReferenceMap" - a subclass of ReadWriteMap. It has two additional typedefs
+<i>Reference</i> and <i>ConstReference</i> 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.
+</li>
+<li>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")
+</li>
+</ul>
+
+\section maps_graph Digraphs' maps
+Every \ref MappableDigraphComponent "mappable" digraph class has two public templates: NodeMap<VALUE> and ArcMap<VALUE>
+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<int>  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<int>  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<Digraph::Arc,double>
+{
+  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<Digraph::Arc,double>
+{
+  const Digraph &g;
+  const Digraph::ArcMap<double> &orig_len;
+  const Digraph::NodeMap<double> &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<Digraph,ReducedLengthMap> dij(g,rm);
+  dij.run(s);
+  ...
+\endcode
+
+
 [SEC]sec_map_concepts[SEC] Map Concepts
 
@@ -39 +334 @@
 [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<ListDigraph::Node> Container;
+  typedef back_insert_iterator<Container> InsertIterator;
+  typedef LoggerBoolMap<InsertIterator> ProcessedMap;
+  Dijkstra<ListDigraph>
+    ::SetProcessedMap<ProcessedMap>
+    ::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<ListDigraph::Node> 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 <typename GR>
+  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 <typename GR>
+  struct TreeVisitor : public DfsVisitor<GR> {
+    TreeVisitor(typename GR::ArcMap<bool>& 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<bool>& _tree;
+  };
+\endcode
+
 
 [TRAILER]