COIN-OR::LEMON - Graph Library

Changeset 416:76287c8caa26 in lemon-1.2 for doc

11/30/08 19:18:32 (16 years ago)
Balazs Dezso <deba@…>

Reorganication of graph adaptors and doc improvements (#67)

  • Moving to one file, lemon/adaptors.h
  • Renamings
  • Doc cleanings
1 edited


  • doc/groups.dox

    r388 r416  
    5959<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
     63@defgroup graph_adaptors Adaptor Classes for graphs
     64@ingroup graphs
     65\brief This group contains several adaptor classes for digraphs and graphs
     67The main parts of LEMON are the different graph structures, generic
     68graph algorithms, graph concepts which couple these, and graph
     69adaptors. While the previous notions are more or less clear, the
     70latter one needs further explanation. Graph adaptors are graph classes
     71which serve for considering graph structures in different ways.
     73A short example makes this much clearer.  Suppose that we have an
     74instance \c g of a directed graph type say ListDigraph and an algorithm
     76template <typename Digraph>
     77int algorithm(const Digraph&);
     79is needed to run on the reverse oriented graph.  It may be expensive
     80(in time or in memory usage) to copy \c g with the reversed
     81arcs.  In this case, an adaptor class is used, which (according
     82to LEMON digraph concepts) works as a digraph.  The adaptor uses the
     83original digraph structure and digraph operations when methods of the
     84reversed oriented graph are called.  This means that the adaptor have
     85minor memory usage, and do not perform sophisticated algorithmic
     86actions.  The purpose of it is to give a tool for the cases when a
     87graph have to be used in a specific alteration.  If this alteration is
     88obtained by a usual construction like filtering the arc-set or
     89considering a new orientation, then an adaptor is worthwhile to use.
     90To come back to the reverse oriented graph, in this situation
     92template<typename Digraph> class ReverseDigraph;
     94template class can be used. The code looks as follows
     96ListDigraph g;
     97ReverseDigraph<ListGraph> rg(g);
     98int result = algorithm(rg);
     100After running the algorithm, the original graph \c g is untouched.
     101This techniques gives rise to an elegant code, and based on stable
     102graph adaptors, complex algorithms can be implemented easily.
     104In flow, circulation and bipartite matching problems, the residual
     105graph is of particular importance. Combining an adaptor implementing
     106this, shortest path algorithms and minimum mean cycle algorithms,
     107a range of weighted and cardinality optimization algorithms can be
     108obtained. For other examples, the interested user is referred to the
     109detailed documentation of particular adaptors.
     111The behavior of graph adaptors can be very different. Some of them keep
     112capabilities of the original graph while in other cases this would be
     113meaningless. This means that the concepts that they are models of depend
     114on the graph adaptor, and the wrapped graph(s).
     115If an arc of \c rg is deleted, this is carried out by deleting the
     116corresponding arc of \c g, thus the adaptor modifies the original graph.
     118But for a residual graph, this operation has no sense.
     119Let us stand one more example here to simplify your work.
     120RevGraphAdaptor has constructor
     122ReverseDigraph(Digraph& digraph);
     124This means that in a situation, when a <tt>const ListDigraph&</tt>
     125reference to a graph is given, then it have to be instantiated with
     126<tt>Digraph=const ListDigraph</tt>.
     128int algorithm1(const ListDigraph& g) {
     129  RevGraphAdaptor<const ListDigraph> rg(g);
     130  return algorithm2(rg);
Note: See TracChangeset for help on using the changeset viewer.