source: lemon-tutorial/adaptors.dox @ 53:0f695eac7e07

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2010
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

namespace lemon {
/**
[PAGE]sec_graph_adaptors[PAGE] Graph Adaptors

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) {
  ReverseDigraph<const ListDigraph> rg(g);
  return algorithm2(rg);
}
\endcode

\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.
In the following image, a \ref SubDigraph adaptor is applied to an
underlying digraph structure to obtain a suitable subgraph.

\image html adaptors1.png
\image latex adaptors1.eps "SubDigraph adaptor" width=\textwidth

\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
example.

\code
  ListDigraph g;
  ListDigraph::NodeMap<bool> filter_map(g);
  // construct the graph and fill the filter map

  {
    StaticDigraph tmp_graph;
    ListDigraph::NodeMap<StaticDigraph::Node> node_ref(g);
    digraphCopy(filterNodes(g, filter_map), tmp_graph)
      .nodeRef(node_ref).run();

    // use tmp_graph
  }
\endcode

\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

Sine the adaptor classes conform to the \ref graph_concepts "graph concepts",
we can even apply an adaptor to another one.
The following image illustrates a situation when a \ref SubDigraph and an
\ref Undirector adaptor is applied to a digraph.

\image html adaptors2.png
\image latex adaptors2.eps "Arc disjoint paths" width=\textwidth

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
  typedef SplitNodes<ListDigraph> SplitGraph;
  SplitGraph sg(g);
  SplitGraph::CombinedArcMap<NodeCostMap, ArcCostMap>
    combined_cost(node_cost, arc_cost);
  SplitGraph::NodeMap<double> dist(sg);
  dijkstra(sg, combined_cost).distMap(dist).run(sg.outNode(u));
\endcode

\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.
For example, in the following digraph, four arc disjoint paths can be found
from the node on the left to the node on the right.

\image html splitnodes1.png
\image latex splitnodes1.eps "Arc disjoint paths" width=\textwidth

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.
For example, in the above digraph, there are only three node disjoint paths.

\image html splitnodes2.png
\image latex splitnodes2.eps "Node disjoint paths" width=\textwidth

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]
*/
}