COIN-OR::LEMON - Graph Library

1 edited


  • doc/groups.dox

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