Changeset 39:31a1a79019bb in lemon-tutorial

Timestamp:

02/21/10 15:07:59 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Fully rework and extend the adaptors section

Files:

• adaptors.dox (modified) (4 diffs)
• toc.txt (modified) (1 diff)

adaptors.dox

@@ -21 +21 @@
 [PAGE]sec_graph_adaptors[PAGE] Graph Adaptors
 
-\todo Clarify this section.
-
-Alteration of standard containers need a very limited number of
-operations, these together satisfy the everyday requirements.
-In the case of graph structures, different operations are needed which do
-not alter the physical graph, but gives another view. If some nodes or
-arcs have to be hidden or the reverse oriented graph have to be used, then
-this is the case. It also may happen that in a flow implementation
-the residual graph can be accessed by another algorithm, or a node-set
-is to be shrunk for another algorithm.
-LEMON also provides a variety of graphs for these requirements called
-\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
-in conjunction with other graph representations.
-
-The main parts of LEMON are the different graph structures, generic
-graph algorithms, graph concepts, which couple them, and graph
-adaptors. While the previous notions are more or less clear, the
-latter one needs further explanation. Graph adaptors are graph classes
-which serve for considering graph structures in different ways.
-
-A short example makes this much clearer.  Suppose that we have an
-instance \c g of a directed graph type, say ListDigraph and an algorithm
-\code
-template <typename Digraph>
-int algorithm(const Digraph&);
-\endcode
-is needed to run on the reverse oriented graph.  It may be expensive
-(in time or in memory usage) to copy \c g with the reversed
-arcs.  In this case, an adaptor class is used, which (according
-to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
-The adaptor uses the original digraph structure and digraph operations when
-methods of the reversed oriented graph are called.  This means that the adaptor
-have minor memory usage, and do not perform sophisticated algorithmic
-actions.  The purpose of it is to give a tool for the cases when a
-graph have to be used in a specific alteration.  If this alteration is
-obtained by a usual construction like filtering the node or the arc set or
-considering a new orientation, then an adaptor is worthwhile to use.
-To come back to the reverse oriented graph, in this situation
-\code
-template<typename Digraph> class ReverseDigraph;
-\endcode
-template class can be used. The code looks as follows
-\code
-ListDigraph g;
-ReverseDigraph<ListDigraph> rg(g);
-int result = algorithm(rg);
-\endcode
-During running the algorithm, the original digraph \c g is untouched.
-This techniques give rise to an elegant code, and based on stable
-graph adaptors, complex algorithms can be implemented easily.
-
-In flow, circulation and matching problems, the residual
-graph is of particular importance. Combining an adaptor implementing
-this with shortest path algorithms or minimum mean cycle algorithms,
-a range of weighted and cardinality optimization algorithms can be
-obtained. For other examples, the interested user is referred to the
-detailed documentation of particular adaptors.
-
-The behavior of graph adaptors can be very different. Some of them keep
-capabilities of the original graph while in other cases this would be
-meaningless. This means that the concepts that they meet depend
-on the graph adaptor, and the wrapped graph.
-For example, if an arc of a reversed digraph is deleted, this is carried
-out by deleting the corresponding arc of the original digraph, thus the
-adaptor modifies the original digraph.
-However in case of a residual digraph, this operation has no sense.
-
-Let us stand one more example here to simplify your work.
-ReverseDigraph has constructor
-\code
-ReverseDigraph(Digraph& digraph);
-\endcode
-This means that in a situation, when a <tt>const %ListDigraph&</tt>
-reference to a graph is given, then it have to be instantiated with
-<tt>Digraph=const %ListDigraph</tt>.
+In typical algorithms and applications related to graphs and networks,
+we usually encounter situations in which a specific alteration of a graph
+has to be considered.
+If some nodes or arcs have to be hidden (maybe temporarily) or the reverse
+oriented graph has to be used, then this is the case.
+However, actually modifing physical storage of the graph or
+making a copy of the graph structure along with the required maps
+could be rather expensive (in time or in memory usage) compared to the
+operations that should be performed on the altered graph.
+In such cases, the LEMON \e graph \e adaptor \e classes could be used.
+
+
+[SEC]sec_reverse_digraph[SEC] Reverse Oriented Digraph
+
+Let us suppose that we have an instance \c g of a directed graph type, say
+\ref ListDigraph and an algorithm
+\code
+  template <typename Digraph>
+  int algorithm(const Digraph&);
+\endcode
+is needed to run on the reverse oriented digraph.
+In this situation, a certain adaptor class
+\code
+  template <typename Digraph>
+  class ReverseDigraph;
+\endcode
+can be used.
+
+The graph adaptors are special classes that serve for considering other graph
+structures in different ways. They can be used exactly the same as "real"
+graphs, i.e. they conform to the \ref graph_concepts "graph concepts", thus all
+generic algorithms can be performed on them. However, the adaptor classes
+cannot be used alone but only in conjunction with actual graph representations.
+They do not alter the physical graph storage, they just give another view of it.
+When the methods of the adaptors are called, they use the underlying
+graph structures and their operations, thus these classes have only negligible
+memory usage and do not perform sophisticated algorithmic actions.
+
+This technique yields convenient tools that help writing compact and elegant
+code, and makes it possible to easily implement complex algorithms based on
+well tested standard components.
+
+For solving the problem introduced above, we could use the follwing code.
+
+\code
+  ListDigraph g;
+  ReverseDigraph<ListDigraph> rg(g);
+  int result = algorithm(rg);
+\endcode
+
+Note that the original digraph \c g remains untouched during the whole
+procedure.
+
+LEMON also provides simple "creator functions" for the adaptor
+classes to make their usage even simpler.
+For example, \ref reverseDigraph() returns an instance of \ref ReverseDigraph,
+thus the above code can be written like this.
+
+\code
+  ListDigraph g;
+  int result = algorithm(reverseDigraph(g));
+\endcode
+
+Another essential feature of the adaptors is that their \c Node and \c Arc
+types convert to the original item types.
+Therefore, the maps of the original graph can be used in connection with
+the adaptor.
+
+In the following code, Dijksta's algorithm is run on the reverse oriented
+graph but using the original node and arc maps.
+
+\code
+  ListDigraph g;
+  ListDigraph::ArcMap length(g);
+  ListDigraph::NodeMap dist(g);
+
+  ListDigraph::Node s = g.addNode();
+  // add more nodes and arcs
+
+  dijkstra(reverseDigraph(g), length).distMap(dist).run(s);
+\endcode
+
+In the above examples, we used \ref ReverseDigraph in such a way that the
+underlying digraph was not changed. However, the adaptor class can even be
+used for modifying the original graph structure.
+It allows adding and deleting arcs or nodes, and these operations are carried
+out by calling suitable functions of the underlying digraph (if it supports
+them).
+
+For this, \ref ReverseDigraph "ReverseDigraph<GR>" has a constructor of the
+following form.
+\code
+  ReverseDigraph(GR& gr);
+\endcode
+
+This means that in a situation, when the modification of the original graph
+has to be avoided (e.g. it is given as a const reference), then the adaptor
+class has to be instantiated with \c GR set to be \c const type
+(e.g. <tt>GR = const %ListDigraph</tt>), as in the following example.
+
 \code
 int algorithm1(const ListDigraph& g) {
@@ -103 +128 @@
 \endcode
 
-<hr>
-
-The LEMON graph adaptor classes serve for considering graphs in
-different ways. The adaptors can be used exactly the same as "real"
-graphs (i.e., they conform to the graph concepts), thus all generic
-algorithms can be performed on them. However, the adaptor classes use
-the underlying graph structures and operations when their methods are
-called, thus they have only negligible memory usage and do not perform
-sophisticated algorithmic actions. This technique yields convenient and
-elegant tools for the cases when a graph has to be used in a specific
-alteration, but copying it would be too expensive (in time or in memory
-usage) compared to the algorithm that should be executed on it. The
-following example shows how the \ref ReverseDigraph adaptor can be used
-to run Dijksta's algorithm on the reverse oriented graph. Note that the
-maps of the original graph can be used in connection with the adaptor,
-since the node and arc types of the adaptors convert to the original
-item types.
-
-\code
-dijkstra(reverseDigraph(g), length).distMap(dist).run(s);
-\endcode
-
-Using \ref ReverseDigraph could be as efficient as working with the
-original graph, but not all adaptors can be so fast, of course. For
-example, the subgraph adaptors have to access filter maps for the nodes
-and/or the arcs, thus their iterators are significantly slower than the
-original iterators. LEMON also provides some more complex adaptors, for
-instance, \ref SplitNodes, which can be used for splitting each node in
-a directed graph and \ref ResidualDigraph for modeling the residual
-network for flow and matching problems.
-
-Therefore, in cases when rather complex algorithms have to be used
-on a subgraph (e.g. when the nodes and arcs have to be traversed several
-times), it could worth copying the altered graph into an efficient structure
-and run the algorithm on it.
+\note Modification capabilities are not supported for all adaptors.
+E.g. for \ref ResidualDigraph (see \ref sec_other_adaptors "later"),
+this makes no sense.
+
+As a more complex example, let us see how \ref ReverseDigraph can be used
+together with a graph search algorithm to decide whether a directed graph is
+strongly connected or not.
+We exploit the fact the a digraph is strongly connected if and only if
+for an arbitrarily selected node \c u, each other node is reachable from
+\c u (along a directed path) and \c u is reachable from each node.
+The latter condition is the same that each node is reachable from \c u
+in the reversed digraph.
+
+\code
+  template <typename Digraph>
+  bool stronglyConnected(const Digraph& g) {
+    typedef typename Digraph::NodeIt NodeIt;
+    NodeIt u(g);
+    if (u == INVALID) return true;
+
+    // Run BFS on the original digraph
+    Bfs<Digraph> bfs(g);
+    bfs.run(u);
+    for (NodeIt n(g); n != INVALID; ++n) {
+      if (!bfs.reached(n)) return false;
+    }
+
+    // Run BFS on the reverse oriented digraph
+    typedef ReverseDigraph<const Digraph> RDigraph;
+    RDigraph rg(g);
+    Bfs<RDigraph> rbfs(rg);
+    rbfs.run(u);
+    for (NodeIt n(g); n != INVALID; ++n) {
+      if (!rbfs.reached(n)) return false;
+    }
+
+    return true;
+  }
+\endcode
+
+Note that we have to use the adaptor with '<tt>const Digraph</tt>' type, since
+\c g is a \c const reference to the original graph structure.
+The \ref stronglyConnected() function provided in LEMON has a quite
+similar implementation.
+
+
+[SEC]sec_subgraphs[SEC] Subgraph Adaptorts
+
+Another typical requirement is the use of certain subgraphs of a graph,
+or in other words, hiding nodes and/or arcs from a graph.
+LEMON provides several convenient adaptors for these purposes.
+
+\ref FilterArcs can be used when some arcs have to be hidden from a digraph.
+A \e filter \e map has to be given to the constructor, which assign \c bool
+values to the arcs specifying whether they have to be shown or not in the
+subgraph structure.
+Suppose we have a \ref ListDigraph structure \c g.
+Then we can construct a subgraph in which some arcs (\c a1, \c a2 etc.)
+are hidden as follows.
+
+\code
+  ListDigraph::ArcMap filter(g, true);
+  filter[a1] = false;
+  filter[a2] = false;
+  // ...
+  FilterArcs<ListDigraph> subgraph(g, filter);
+\endcode
+
+The following more complex code runs Dijkstra's algorithm on a digraph
+that is obtained from another digraph by hiding all arcs having negative
+lengths.
+
+\code
+  ListDigraph::ArcMap<int> length(g);
+  ListDigraph::NodeMap<int> dist(g);
+
+  dijkstra(filterArcs( g, lessMap(length, constMap<ListDigraph::Arc>(0)) ),
+           length).distMap(dist).run(s);
+\endcode
+
+Note the extensive use of map adaptors and creator functions, which makes
+the code really compact and elegant.
+
+\note Implicit maps and graphs (e.g. created using functions) can only be
+used with the function-type interfaces of the algorithms, since they store
+only references for the used structures.
+
+\ref FilterEdges can be used for hiding edges from an undirected graph (like
+\ref FilterArcs is used for digraphs). \ref FilterNodes serves for filtering
+nodes along with the incident arcs or edges in a directed or undirected graph.
+If both arcs/edges and nodes have to be hidden, then you could use
+\ref SubDigraph or \ref SubGraph adaptors.
+
+\code
+  ListGraph ug;
+  ListGraph::NodeMap<bool> node_filter(ug);
+  ListGraph::EdgeMap<bool> edge_filter(ug);
+  
+  SubGraph<ListGraph> sg(ug, node_filter, edge_filter);
+\endcode
+
+As you see, we needed two filter maps in this case: one for the nodes and
+another for the edges. If a node is hidden, then all of its incident edges
+are also considered to be hidden independently of their own filter values.
+
+The subgraph adaptors also make it possible to modify the filter values
+even after the construction of the adaptor class, thus the corresponding
+graph items can be hidden or shown on the fly.
+The adaptors store references to the filter maps, thus the map values can be
+set directly and even by using the \c enable(), \c disable() and \c status()
+functions.
+
+\code
+  ListDigraph g;
+  ListDigraph::Node x = g.addNode();
+  ListDigraph::Node y = g.addNode();
+  ListDigraph::Node z = g.addNode();
+  
+  ListDigraph::NodeMap<bool> filter(g, true);
+  FilterNodes<ListDigraph> subgraph(g, filter);
+  std::cout << countNodes(subgraph) << ", ";
+
+  filter[x] = false;
+  std::cout << countNodes(subgraph) << ", ";
+
+  subgraph.enable(x);
+  subgraph.disable(y);
+  subgraph.status(z, !subgraph.status(z));
+  std::cout << countNodes(subgraph) << std::endl;
+\endcode
+
+The above example prints out this line.
+\code
+  3, 2, 1
+\endcode
+
+Similarly to \ref ReverseDigraph, the subgraph adaptors also allow the
+modification of the underlying graph structures unless the graph template
+parameter is set to be \c const type.
+Moreover the item types of the original graphs and the subgraphs are
+convertible to each other.
+
+The iterators of the subgraph adaptors use the iterators of the original
+graph structures in such a way that each item with \c false filter value
+is skipped. If both the node and arc sets are filtered, then the arc iterators
+check for each arc the status of its end nodes in addition to its own assigned
+filter value. If the arc or one of its end nodes is hidden, then the arc
+is left out and the next arc is considered.
+(It is the same for edges in undirected graphs.)
+Therefore, the iterators of these adaptors are significantly slower than the
+original iterators.
+
+Using adaptors, these efficiency aspects should be kept in mind.
+For example, if rather complex algorithms have to be performed on a
+subgraph (e.g. the nodes and arcs need to be traversed several times),
+then it could worth copying the altered graph into an efficient
+structure (e.g. \ref StaticDigraph) and run the algorithm on it.
 Note that the adaptor classes can also be used for doing this easily,
 without having to copy the graph manually, as shown in the following
@@ -148 +295 @@
 
   {
-    SmartDigraph temp_graph;
-    ListDigraph::NodeMap<SmartDigraph::Node> node_ref(g);
-    digraphCopy(filterNodes(g, filter_map), temp_graph)
+    StaticDigraph tmp_graph;
+    ListDigraph::NodeMap<StaticDigraph::Node> node_ref(g);
+    digraphCopy(filterNodes(g, filter_map), tmp_graph)
       .nodeRef(node_ref).run();
 
-    // use temp_graph
+    // use tmp_graph
   }
 \endcode
 
-<hr>
-
-Another interesting adaptor in LEMON is \ref SplitNodes.
-It can be used for splitting each node into an in-node and an out-node
-in a directed graph. Formally, the adaptor replaces each node
-u in the graph with two nodes, namely node u<sub>in</sub> and node
-u<sub>out</sub>. Each arc (u,c) in the original graph will correspond to an
-arc (u<sub>out</sub>,v<sub>in</sub>). The adaptor also adds an
-additional bind arc (u<sub>in</sub>,u<sub>out</sub>) for each node u
-of the original digraph.
-
-The aim of this class is to assign costs to the nodes when using
-algorithms which would otherwise consider arc costs only.
-For example, let us suppose that we have a directed graph with costs
-given for both the nodes and the arcs.
-Then Dijkstra's algorithm can be used in connection with \ref SplitNodes
-as follows.
+\note Using \ref ReverseDigraph could be as efficient as working with the
+original graph, but most of the adaptors cannot be so fast, of course. 
+
+
+[SEC]sec_other_adaptors[SEC] Other Graph Adaptors
+
+Two other practical adaptors are \ref Undirector and \ref Orienter.
+\ref Undirector makes an undirected graph from a digraph disregarding the
+orientations of the arcs. More precisely, an arc of the original digraph
+is considered as an edge (and two arcs, as well) in the adaptor.
+\ref Orienter can be used for the reverse alteration, it assigns a certain
+orientation to each edge of an undirected graph to form a directed graph.
+A \c bool edge map of the underlying graph must be given to the constructor
+of the class, which define the direction of the arcs in the created adaptor
+(with respect to the inherent orientation of the original edges).
+
+\code
+  ListGraph graph;
+  ListGraph::EdgeMap<bool> dir_map(graph, true);
+  Orienter<ListGraph> directed_graph(graph, dir_map);
+\endcode
+
+LEMON also provides some more complex adaptors, for
+instance, \ref SplitNodes, which can be used for splitting each node of a
+directed graph into an in-node and an out-node.
+Formally, the adaptor replaces each node u in the graph with two nodes,
+namely u<sub>in</sub> and u<sub>out</sub>. Each arc (u,v) of the original
+graph will correspond to an arc (u<sub>out</sub>,v<sub>in</sub>).
+The adaptor also adds an additional bind arc (u<sub>in</sub>,u<sub>out</sub>)
+for each node u of the original digraph.
+
+The aim of this class is to assign costs or capacities to the nodes when using
+algorithms which would otherwise consider arc costs or capacities only.
+For example, let us suppose that we have a digraph \c g with costs assigned to
+both the nodes and the arcs. Then Dijkstra's algorithm can be used in
+connection with \ref SplitNodes as follows.
 
 \code
@@ -184 +350 @@
 \endcode
 
-Note that this problem can be solved more efficiently with
-map adaptors.
-
-These techniques help writing compact and elegant code, and makes it possible
-to easily implement complex algorithms based on well tested standard components.
-For instance, in flow and matching problems the residual graph is of
-particular importance.
-Combining \ref ResidualDigraph adaptor with various algorithms, a
-range of weighted and cardinality optimization methods can be obtained
-directly.
+\note This problem can also be solved using map adaptors to create
+an implicit arc map that assigns for each arc the sum of its cost
+and the cost of its target node. This map can be used with the original
+graph more efficiently than using the above solution.
+
+Another nice application is the problem of finding disjoint paths in
+a digraph.
+The maximum number of \e edge \e disjoint paths from a source node to
+a sink node in a digraph can be easily computed using a maximum flow
+algorithm with all arc capacities set to 1.
+On the other hand, \e node \e disjoint paths cannot be found directly
+using a standard algorithm.
+However, \ref SplitNodes adaptor makes it really simple.
+If a maximum flow computation is performed on this adaptor, then the
+bottleneck of the flow (i.e. the minimum cut) will be formed by bind arcs,
+thus the found flow will correspond to the union of some node disjoint
+paths in terms of the original digraph.
+
+In flow, circulation and matching problems, the residual network is of
+particular importance, which is implemented in \ref ResidualDigraph.
+Combining this adaptor with various algorithms, a range of weighted and
+cardinality optimization methods can be implemented easily.
+
+To construct a residual network, a digraph structure, a flow map and a
+capacity map have to be given to the constructor of the adaptor as shown
+in the following code.
+
+\code
+  ListDigraph g;
+  ListDigraph::ArcMap<int> flow(g);
+  ListDigraph::ArcMap<int> capacity(g);
+
+  ResidualDigraph<ListDigraph> res_graph(g, capacity, flow); 
+\endcode
+
+\note In fact, this class is implemented using two other adaptors:
+\ref Undirector and \ref FilterArcs.
 
 [TRAILER]

toc.txt

@@ -23 +23 @@
 **_algs_with_maps
 * sec_graph_adaptors
+** sec_reverse_digraph
+** sec_subgraphs
+** sec_other_adaptors
 * sec_lp
 * sec_lgf