summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
file |
latest |
revisions |
annotate |
diff |
comparison |
raw |
help

doc/groups.dox

changeset 432 | 76287c8caa26 |

parent 403 | 0a3ec097a76c |

child 434 | ad483acf1654 |

1.1 --- a/doc/groups.dox Sun Nov 30 19:00:30 2008 +0100 1.2 +++ b/doc/groups.dox Sun Nov 30 19:18:32 2008 +0100 1.3 @@ -60,6 +60,79 @@ 1.4 */ 1.5 1.6 /** 1.7 +@defgroup graph_adaptors Adaptor Classes for graphs 1.8 +@ingroup graphs 1.9 +\brief This group contains several adaptor classes for digraphs and graphs 1.10 + 1.11 +The main parts of LEMON are the different graph structures, generic 1.12 +graph algorithms, graph concepts which couple these, and graph 1.13 +adaptors. While the previous notions are more or less clear, the 1.14 +latter one needs further explanation. Graph adaptors are graph classes 1.15 +which serve for considering graph structures in different ways. 1.16 + 1.17 +A short example makes this much clearer. Suppose that we have an 1.18 +instance \c g of a directed graph type say ListDigraph and an algorithm 1.19 +\code 1.20 +template <typename Digraph> 1.21 +int algorithm(const Digraph&); 1.22 +\endcode 1.23 +is needed to run on the reverse oriented graph. It may be expensive 1.24 +(in time or in memory usage) to copy \c g with the reversed 1.25 +arcs. In this case, an adaptor class is used, which (according 1.26 +to LEMON digraph concepts) works as a digraph. The adaptor uses the 1.27 +original digraph structure and digraph operations when methods of the 1.28 +reversed oriented graph are called. This means that the adaptor have 1.29 +minor memory usage, and do not perform sophisticated algorithmic 1.30 +actions. The purpose of it is to give a tool for the cases when a 1.31 +graph have to be used in a specific alteration. If this alteration is 1.32 +obtained by a usual construction like filtering the arc-set or 1.33 +considering a new orientation, then an adaptor is worthwhile to use. 1.34 +To come back to the reverse oriented graph, in this situation 1.35 +\code 1.36 +template<typename Digraph> class ReverseDigraph; 1.37 +\endcode 1.38 +template class can be used. The code looks as follows 1.39 +\code 1.40 +ListDigraph g; 1.41 +ReverseDigraph<ListGraph> rg(g); 1.42 +int result = algorithm(rg); 1.43 +\endcode 1.44 +After running the algorithm, the original graph \c g is untouched. 1.45 +This techniques gives rise to an elegant code, and based on stable 1.46 +graph adaptors, complex algorithms can be implemented easily. 1.47 + 1.48 +In flow, circulation and bipartite matching problems, the residual 1.49 +graph is of particular importance. Combining an adaptor implementing 1.50 +this, shortest path algorithms and minimum mean cycle algorithms, 1.51 +a range of weighted and cardinality optimization algorithms can be 1.52 +obtained. For other examples, the interested user is referred to the 1.53 +detailed documentation of particular adaptors. 1.54 + 1.55 +The behavior of graph adaptors can be very different. Some of them keep 1.56 +capabilities of the original graph while in other cases this would be 1.57 +meaningless. This means that the concepts that they are models of depend 1.58 +on the graph adaptor, and the wrapped graph(s). 1.59 +If an arc of \c rg is deleted, this is carried out by deleting the 1.60 +corresponding arc of \c g, thus the adaptor modifies the original graph. 1.61 + 1.62 +But for a residual graph, this operation has no sense. 1.63 +Let us stand one more example here to simplify your work. 1.64 +RevGraphAdaptor has constructor 1.65 +\code 1.66 +ReverseDigraph(Digraph& digraph); 1.67 +\endcode 1.68 +This means that in a situation, when a <tt>const ListDigraph&</tt> 1.69 +reference to a graph is given, then it have to be instantiated with 1.70 +<tt>Digraph=const ListDigraph</tt>. 1.71 +\code 1.72 +int algorithm1(const ListDigraph& g) { 1.73 + RevGraphAdaptor<const ListDigraph> rg(g); 1.74 + return algorithm2(rg); 1.75 +} 1.76 +\endcode 1.77 +*/ 1.78 + 1.79 +/** 1.80 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs 1.81 @ingroup graphs 1.82 \brief Graph types between real graphs and graph adaptors.