Adaptor Classes for Graphs
[Graph Structures]


Detailed Description

The main parts of LEMON are the different graph structures, generic graph algorithms, graph concepts which couple these, 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 g of a directed graph type say ListGraph and an algorithm

 template<typename Graph> int algorithm(const Graph&); 
is needed to run on the reversed oriented graph. It may be expensive (in time or in memory usage) to copy g with the reversed orientation. In this case, an adaptor class is used, which (according to LEMON graph concepts) works as a graph. The adaptor uses the original graph structure and graph 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 edge-set or considering a new orientation, then an adaptor is worthwhile to use. To come back to the reversed oriented graph, in this situation
 template<typename Graph> class RevGraphAdaptor; 
template class can be used. The code looks as follows
   ListGraph g;
   RevGraphAdaptor<ListGraph> rgw(g);
   int result=algorithm(rgw);
After running the algorithm, the original graph g is untouched. This techniques gives rise to an elegant code, and based on stable graph adaptors, complex algorithms can be implemented easily.

In flow, circulation and bipartite matching problems, the residual graph is of particular importance. Combining an adaptor implementing this, shortest path algorithms and 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 are models of depend on the graph adaptor, and the wrapped graph(s). If an edge of rgw is deleted, this is carried out by deleting the corresponding edge of g, thus the adaptor modifies the original graph. But for a residual graph, this operation has no sense. Let us stand one more example here to simplify your work. RevGraphAdaptor has constructor

   RevGraphAdaptor(Graph& _g);
This means that in a situation, when a const ListGraph& reference to a graph is given, then it have to be instantiated with Graph=const ListGraph.
   int algorithm1(const ListGraph& g) {
   RevGraphAdaptor<const ListGraph> rgw(g);
   return algorithm2(rgw);
   }


Files

file  graph_adaptor.h
 Several graph adaptors.

Classes

class  GraphAdaptorBase
 Base type for the Graph Adaptors

Base type for the Graph Adaptors. More...

class  RevGraphAdaptor
 A graph adaptor which reverses the orientation of the edges. More...
class  SubGraphAdaptor
 A graph adaptor for hiding nodes and edges from a graph. More...
class  NodeSubGraphAdaptor
 An adaptor for hiding nodes from a graph. More...
class  UGraphAdaptor
 An undirected graph is made from a directed graph by an adaptor

Undocumented, untested!!! If somebody knows nice demo application, let's polulate it. More...

class  ResGraphAdaptor
class  ErasingFirstGraphAdaptor

Variables

const CapacityMap & lemon::_capacity
 An adaptor for composing a subgraph of a bidirected graph made from a directed one.

An adaptor for composing a subgraph of a bidirected graph made from a directed one. An adaptor for composing bidirected graph from a directed one. / / /.


Variable Documentation

const CapacityMap& _capacity
 

Warning:
Graph adaptors are in even more experimental state than the other parts of the lib. Use them at you own risk.
Let $ G=(V, A) $ be a directed graph and for each directed edge $ e\in A $, let $ \bar e $ denote the edge obtained by / reversing its orientation. We are given moreover two bool valued / maps on the edge-set, /$ forward\_filter $, and $ backward\_filter $. / SubBidirGraphAdaptor implements the graph structure with node-set /$ V $ and edge-set /$ \{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\} $. / The purpose of writing + instead of union is because parallel / edges can arise. (Similarly, antiparallel edges also can arise). / In other words, a subgraph of the bidirected graph obtained, which / is given by orienting the edges of the original graph in both directions. / As the oppositely directed edges are logically different, / the maps are able to attach different values for them. / / An example for such a construction is RevGraphAdaptor where the / forward_filter is everywhere false and the backward_filter is / everywhere true. We note that for sake of efficiency, / RevGraphAdaptor is implemented in a different way. / But BidirGraphAdaptor is obtained from / SubBidirGraphAdaptor by considering everywhere true / valued maps both for forward_filter and backward_filter. / / The most important application of SubBidirGraphAdaptor / is ResGraphAdaptor, which stands for the residual graph in directed / flow and circulation problems. / As adaptors usually, the SubBidirGraphAdaptor implements the / above mentioned graph structure without its physical storage, / that is the whole stuff is stored in constant memory. template<typename _Graph, typename ForwardFilterMap, typename BackwardFilterMap> class SubBidirGraphAdaptor : public IterableGraphExtender< SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > { public: typedef _Graph Graph; typedef IterableGraphExtender< SubBidirGraphAdaptorBase< _Graph, ForwardFilterMap, BackwardFilterMap> > Parent; protected: SubBidirGraphAdaptor() { } public: SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter, BackwardFilterMap& _backward_filter) { setGraph(_graph); setForwardFilterMap(_forward_filter); setBackwardFilterMap(_backward_filter); } };

/

Warning:
Graph adaptors are in even more experimental state /than the other /parts of the lib. Use them at you own risk. / / An adaptor for composing bidirected graph from a directed one. / A bidirected graph is composed over the directed one without physical / storage. As the oppositely directed edges are logically different ones / the maps are able to attach different values for them. template<typename Graph> class BidirGraphAdaptor : public SubBidirGraphAdaptor< Graph, ConstMap<typename Graph::Edge, bool>, ConstMap<typename Graph::Edge, bool> > { public: typedef SubBidirGraphAdaptor< Graph, ConstMap<typename Graph::Edge, bool>, ConstMap<typename Graph::Edge, bool> > Parent; protected: ConstMap<typename Graph::Edge, bool> cm;
BidirGraphAdaptor() : Parent(), cm(true) { Parent::setForwardFilterMap(cm); Parent::setBackwardFilterMap(cm); } public: BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) { Parent::setGraph(_graph); Parent::setForwardFilterMap(cm); Parent::setBackwardFilterMap(cm); }

int edgeNum() const { return 2*this->graph->edgeNum(); } };

template<typename Graph, typename Number, typename CapacityMap, typename FlowMap> class ResForwardFilter { const Graph* graph; const CapacityMap* capacity; const FlowMap* flow; public: ResForwardFilter(/*const Graph& _graph,


Generated on Fri Feb 3 18:40:00 2006 for LEMON by  doxygen 1.4.6