All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
Classes | Files | Functions
Adaptor Classes for Graphs
Graph Structures

Detailed Description

This group contains several useful adaptor classes for digraphs and graphs.

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 g of a directed graph type, say ListDigraph and an algorithm

template <typename Digraph>
int algorithm(const Digraph&);

is needed to run on the reverse oriented graph. It may be expensive (in time or in memory usage) to copy g with the reversed arcs. In this case, an adaptor class is used, which (according to LEMON 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

template<typename Digraph> class ReverseDigraph;

template class can be used. The code looks as follows

ListDigraph g;
ReverseDigraph<ListDigraph> rg(g);
int result = algorithm(rg);

During running the algorithm, the original digraph 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

ReverseDigraph(Digraph& digraph);

This means that in a situation, when a const ListDigraph& reference to a graph is given, then it have to be instantiated with Digraph=const ListDigraph.

int algorithm1(const ListDigraph& g) {
ReverseDigraph<const ListDigraph> rg(g);
return algorithm2(rg);
}

Classes

class  ReverseDigraph< DGR >
 Adaptor class for reversing the orientation of the arcs in a digraph. More...
 
class  SubDigraph< DGR, NF, AF >
 Adaptor class for hiding nodes and arcs in a digraph. More...
 
class  SubGraph< GR, NF, EF >
 Adaptor class for hiding nodes and edges in an undirected graph. More...
 
class  FilterNodes< GR, NF >
 Adaptor class for hiding nodes in a digraph or a graph. More...
 
class  FilterArcs< DGR, AF >
 Adaptor class for hiding arcs in a digraph. More...
 
class  FilterEdges< GR, EF >
 Adaptor class for hiding edges in a graph. More...
 
class  Undirector< DGR >
 Adaptor class for viewing a digraph as an undirected graph. More...
 
class  Orienter< GR, DM >
 Adaptor class for orienting the edges of a graph to get a digraph. More...
 
class  ResidualDigraph< DGR, CM, FM, TL >
 Adaptor class for composing the residual digraph for directed flow and circulation problems. More...
 
class  SplitNodes< DGR >
 Adaptor class for splitting the nodes of a digraph. More...
 
class  Undirector< DGR >::CombinedArcMap< FW, BK >
 Arc map combined from two original arc maps. More...
 
class  ResidualDigraph< DGR, CM, FM, TL >::ResidualCapacity
 Residual capacity map. More...
 
class  SplitNodes< DGR >::CombinedArcMap< AM, NM >
 Arc map combined from an arc map and a node map of the original digraph. More...
 
class  SplitNodes< DGR >::CombinedNodeMap< IN, OUT >
 Node map combined from two original node maps. More...
 

Files

file  adaptors.h
 Adaptor classes for digraphs and graphs.
 

Functions

template<typename DGR >
ReverseDigraph< const DGR > reverseDigraph (const DGR &digraph)
 Returns a read-only ReverseDigraph adaptor.
 
template<typename DGR , typename NF , typename AF >
SubDigraph< const DGR, NF, AF > subDigraph (const DGR &digraph, NF &node_filter, AF &arc_filter)
 Returns a read-only SubDigraph adaptor.
 
template<typename GR , typename NF , typename EF >
SubGraph< const GR, NF, EF > subGraph (const GR &graph, NF &node_filter, EF &edge_filter)
 Returns a read-only SubGraph adaptor.
 
template<typename GR , typename NF >
FilterNodes< const GR, NF > filterNodes (const GR &graph, NF &node_filter)
 Returns a read-only FilterNodes adaptor.
 
template<typename DGR , typename AF >
FilterArcs< const DGR, AF > filterArcs (const DGR &digraph, AF &arc_filter)
 Returns a read-only FilterArcs adaptor.
 
template<typename GR , typename EF >
FilterEdges< const GR, EF > filterEdges (const GR &graph, EF &edge_filter)
 Returns a read-only FilterEdges adaptor.
 
template<typename DGR >
Undirector< const DGR > undirector (const DGR &digraph)
 Returns a read-only Undirector adaptor.
 
template<typename GR , typename DM >
Orienter< const GR, DM > orienter (const GR &graph, DM &direction)
 Returns a read-only Orienter adaptor.
 
template<typename DGR , typename CM , typename FM >
ResidualDigraph< DGR, CM, FM > residualDigraph (const DGR &digraph, const CM &capacity_map, FM &flow_map)
 Returns a (read-only) Residual adaptor.
 
template<typename DGR >
SplitNodes< DGR > splitNodes (const DGR &digraph)
 Returns a (read-only) SplitNodes adaptor.
 

Function Documentation

ReverseDigraph< const DGR > reverseDigraph ( const DGR &  digraph)
related

This function just returns a read-only ReverseDigraph adaptor.

SubDigraph< const DGR, NF, AF > subDigraph ( const DGR &  digraph,
NF &  node_filter,
AF &  arc_filter 
)
related

This function just returns a read-only SubDigraph adaptor.

SubGraph< const GR, NF, EF > subGraph ( const GR &  graph,
NF &  node_filter,
EF &  edge_filter 
)
related

This function just returns a read-only SubGraph adaptor.

FilterNodes< const GR, NF > filterNodes ( const GR &  graph,
NF &  node_filter 
)
related

This function just returns a read-only FilterNodes adaptor.

FilterArcs< const DGR, AF > filterArcs ( const DGR &  digraph,
AF &  arc_filter 
)
related

This function just returns a read-only FilterArcs adaptor.

FilterEdges< const GR, EF > filterEdges ( const GR &  graph,
EF &  edge_filter 
)
related

This function just returns a read-only FilterEdges adaptor.

Undirector< const DGR > undirector ( const DGR &  digraph)
related

This function just returns a read-only Undirector adaptor.

Orienter< const GR, DM > orienter ( const GR &  graph,
DM &  direction 
)
related

This function just returns a read-only Orienter adaptor.

ResidualDigraph< DGR, CM, FM > residualDigraph ( const DGR &  digraph,
const CM &  capacity_map,
FM &  flow_map 
)
related

This function just returns a (read-only) ResidualDigraph adaptor.

SplitNodes< DGR > splitNodes ( const DGR &  digraph)
related

This function just returns a (read-only) SplitNodes adaptor.