/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * 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

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

\code

int algorithm1(const ListDigraph& g) {

  ReverseDigraph<const ListDigraph> rg(g);

  return algorithm2(rg);

}

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

  {

    SmartDigraph temp_graph;

    ListDigraph::NodeMap<SmartDigraph::Node> node_ref(g);

    digraphCopy(filterNodes(g, filter_map), temp_graph)

      .nodeRef(node_ref).run();

    // use temp_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.

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

[TRAILER]

*/

}