COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1401:9588dcef6793 in lemon-0.x


Ignore:
Timestamp:
05/04/05 15:07:10 (20 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1863
Message:

wrapper -> adaptor

Files:
7 edited
5 moved

Legend:

Unmodified
Added
Removed

  • doc/Makefile.am

    r1400 r1401  
    99        demoprograms.dox graphs.dox undir_graphs.dox named-param.dox \
    1010        maps.dox coding_style.dox groups.dox namespaces.dox license.dox \
    11         developers_interface.dox graph_io.dox dirs.dox gwrappers.dox
     11        developers_interface.dox graph_io.dox dirs.dox graph-adaptors.dox
    1212
    1313

  • doc/graph-adaptors.dox

    r1252 r1401  
    11/**
    2    @defgroup gwrappers Wrapper Classes for Graphs
    3    \brief This group contains several wrapper classes for graphs
     2   @defgroup graph_adaptors Adaptor Classes for Graphs
     3   \brief This group contains several adaptor classes for graphs
    44   @ingroup graphs
    55   
    66   The main parts of LEMON are the different graph structures,
    77   generic graph algorithms, graph concepts which couple these, and
    8    graph wrappers. While the previous notions are more or less clear, the
     8   graph adaptors. While the previous notions are more or less clear, the
    99   latter one needs further explanation.
    10    Graph wrappers are graph classes which serve for considering graph
     10   Graph adaptors are graph classes which serve for considering graph
    1111   structures in different ways.
    1212
    … …  
    1919   It may be expensive (in time or in memory usage) to copy
    2020   \c g with the reversed orientation.
    21    In this case, a wrapper class is used, which
     21   In this case, an adaptor class is used, which
    2222   (according to LEMON graph concepts) works as a graph.
    23    The wrapper uses
     23   The adaptor uses
    2424   the original graph structure and graph operations when methods of the
    2525   reversed oriented graph are called.
    26    This means that the wrapper have minor memory usage,
     26   This means that the adaptor have minor memory usage,
    2727   and do not perform sophisticated algorithmic actions.
    2828   The purpose of it is to give a tool for the cases when
    … …  
    3030   If this alteration is obtained by a usual construction
    3131   like filtering the edge-set or considering a new orientation, then
    32    a wrapper is worthwhile to use.
     32   an adaptor is worthwhile to use.
    3333   To come back to the reversed oriented graph, in this situation
    34    \code template<typename Graph> class RevGraphWrapper; \endcode
     34   \code template<typename Graph> class RevGraphAdaptor; \endcode
    3535   template class can be used.
    3636   The code looks as follows
    3737   \code
    3838   ListGraph g;
    39    RevGraphWrapper<ListGraph> rgw(g);
     39   RevGraphAdaptor<ListGraph> rgw(g);
    4040   int result=algorithm(rgw);
    4141   \endcode
    … …  
    4343   is untouched.
    4444   This techniques gives rise to an elegant code, and
    45    based on stable graph wrappers, complex algorithms can be
     45   based on stable graph adaptors, complex algorithms can be
    4646   implemented easily.
    4747
    4848   In flow, circulation and bipartite matching problems, the residual
    49    graph is of particular importance. Combining a wrapper implementing
     49   graph is of particular importance. Combining an adaptor implementing
    5050   this, shortest path algorithms and minimum mean cycle algorithms,
    5151   a range of weighted and cardinality optimization algorithms can be
    … …  
    5353   For other examples,
    5454   the interested user is referred to the detailed documentation of
    55    particular wrappers.
     55   particular adaptors.
    5656
    57    The behavior of graph wrappers can be very different. Some of them keep
     57   The behavior of graph adaptors can be very different. Some of them keep
    5858   capabilities of the original graph while in other cases this would be
    5959   meaningless. This means that the concepts that they are models of depend
    60    on the graph wrapper, and the wrapped graph(s).
     60   on the graph adaptor, and the wrapped graph(s).
    6161   If an edge of \c rgw is deleted, this is carried out by
    62    deleting the corresponding edge of \c g, thus the wrapper modifies the
     62   deleting the corresponding edge of \c g, thus the adaptor modifies the
    6363   original graph.
    6464   But for a residual
    6565   graph, this operation has no sense.
    6666   Let us stand one more example here to simplify your work.
    67    RevGraphWrapper has constructor
     67   RevGraphAdaptor has constructor
    6868   \code
    69    RevGraphWrapper(Graph& _g);
     69   RevGraphAdaptor(Graph& _g);
    7070   \endcode
    7171   This means that in a situation,
    … …  
    7474   \code
    7575   int algorithm1(const ListGraph& g) {
    76    RevGraphWrapper<const ListGraph> rgw(g);
     76   RevGraphAdaptor<const ListGraph> rgw(g);
    7777   return algorithm2(rgw);
    7878   }

  • doc/groups.dox

    r1329 r1401  
    3232is to be shrunk for an other algorithm.
    3333LEMON also provides a variety of graphs for these requirements called
    34 \ref gwrappers "graph wrappers". Wrappers cannot be used alone but only
     34\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
    3535in conjunction with other graph representation.
    3636

  • src/demo/Makefile.am

    r1387 r1401  
    22LDADD = $(top_builddir)/src/lemon/libemon.la
    33
    4 EXTRA_DIST = sub_graph_wrapper_demo.dim
     4EXTRA_DIST = sub_graph_adaptor_demo.dim
    55
    66noinst_PROGRAMS = \
    … …  
    99        graph_to_eps_demo \
    1010        min_route \
    11         sub_graph_wrapper_demo
     11        sub_graph_adaptor_demo
    1212
    1313if HAVE_GLPK
    … …  
    2828min_route_SOURCES = min_route.cc
    2929
    30 sub_graph_wrapper_demo_SOURCES = \
    31         sub_graph_wrapper_demo.cc \
     30sub_graph_adaptor_demo_SOURCES = \
     31        sub_graph_adaptor_demo.cc \
    3232        tight_edge_filter_map.h
    3333

  • src/demo/sub_graph_adaptor_demo.cc

    r986 r1401  
    22
    33// Use a DIMACS max flow file as stdin.
    4 // sub_graph_wrapper_demo < dimacs_max_flow_file
     4// sub_graph_adaptor_demo < dimacs_max_flow_file
    55// This program computes a maximum number of edge-disjoint shortest paths
    66// between s and t.
    … …  
    1212#include <lemon/dijkstra.h>
    1313#include <lemon/maps.h>
    14 #include <lemon/graph_wrapper.h>
     14#include <lemon/graph_adaptor.h>
    1515#include <lemon/dimacs.h>
    1616#include <lemon/preflow.h>
    … …  
    5858//  ConstMap<Node, bool> const_true_map(true);
    5959  // This graph contains exaclty the tight edges.
    60 // typedef SubGraphWrapper<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW;
    61   typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
     60// typedef SubGraphAdaptor<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW;
     61  typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
    6262  SubGW gw(g, tight_edge_filter);
    6363

  • src/lemon/Makefile.am

    r1386 r1401  
    3030        fib_heap.h \
    3131        full_graph.h \
    32         graph_wrapper.h \
     32        graph_adaptor.h \
    3333        graph_utils.h \
    3434        graph_to_eps.h \

  • src/lemon/bits/undir_graph_extender.h

    r1359 r1401  
    3939
    4040    protected:
    41       // FIXME: Marci use opposite logic in his graph wrappers. It would
     41      // FIXME: Marci use opposite logic in his graph adaptors. It would
    4242      // be reasonable to syncronize...
    4343      bool forward;

  • src/lemon/graph_adaptor.h

    r1383 r1401  
    11/* -*- C++ -*-
    2  * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
     2 * src/lemon/graph_adaptor.h - Part of LEMON, a generic C++ optimization library
    33 *
    44 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    … …  
    1515 */
    1616
    17 #ifndef LEMON_GRAPH_WRAPPER_H
    18 #define LEMON_GRAPH_WRAPPER_H
    19 
    20 ///\ingroup gwrappers
     17#ifndef LEMON_GRAPH_ADAPTOR_H
     18#define LEMON_GRAPH_ADAPTOR_H
     19
     20///\ingroup graph_adaptors
    2121///\file
    22 ///\brief Several graph wrappers.
     22///\brief Several graph adaptors.
    2323///
    24 ///This file contains several useful graph wrapper functions.
     24///This file contains several useful graph adaptor functions.
    2525///
    2626///\author Marton Makai
    … …  
    3434namespace lemon {
    3535
    36   // Graph wrappers
     36  // Graph adaptors
    3737
    3838  /*!
    39     \addtogroup gwrappers
     39    \addtogroup graph_adaptors
    4040    @{
    4141   */
    4242
    4343  /*!
    44     Base type for the Graph Wrappers
     44    Base type for the Graph Adaptors
    4545   
    46     \warning Graph wrappers are in even more experimental state than the other
     46    \warning Graph adaptors are in even more experimental state than the other
    4747    parts of the lib. Use them at you own risk.
    4848   
    49     This is the base type for most of LEMON graph wrappers.
    50     This class implements a trivial graph wrapper i.e. it only wraps the
     49    This is the base type for most of LEMON graph adaptors.
     50    This class implements a trivial graph adaptor i.e. it only wraps the
    5151    functions and types of the graph. The purpose of this class is to
    52     make easier implementing graph wrappers. E.g. if a wrapper is
     52    make easier implementing graph adaptors. E.g. if an adaptor is
    5353    considered which differs from the wrapped graph only in some of its
    54     functions or types, then it can be derived from GraphWrapper, and only the
     54    functions or types, then it can be derived from GraphAdaptor, and only the
    5555    differences should be implemented.
    5656 
    … …  
    5858  */
    5959  template<typename _Graph>
    60   class GraphWrapperBase {
     60  class GraphAdaptorBase {
    6161  public:
    6262    typedef _Graph Graph;
    … …  
    6767  protected:
    6868    Graph* graph;
    69     GraphWrapperBase() : graph(0) { }
     69    GraphAdaptorBase() : graph(0) { }
    7070    void setGraph(Graph& _graph) { graph=&_graph; }
    7171
    7272  public:
    73     GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
     73    GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
    7474 
    7575    typedef typename Graph::Node Node;
    … …  
    113113    public:
    114114      typedef typename _Graph::template NodeMap<_Value> Parent;
    115       NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
    116       NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
     115      NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
     116      NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
    117117      : Parent(*gw.graph, value) { }
    118118    };
    … …  
    122122    public:
    123123      typedef typename _Graph::template EdgeMap<_Value> Parent;
    124       EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
    125       EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
     124      EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
     125      EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
    126126      : Parent(*gw.graph, value) { }
    127127    };
    … …  
    130130
    131131  template <typename _Graph>
    132   class GraphWrapper :
    133     public IterableGraphExtender<GraphWrapperBase<_Graph> > {
     132  class GraphAdaptor :
     133    public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
    134134  public:
    135135    typedef _Graph Graph;
    136     typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
    137   protected:
    138     GraphWrapper() : Parent() { }
    139 
    140   public:
    141     GraphWrapper(Graph& _graph) { setGraph(_graph); }
     136    typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
     137  protected:
     138    GraphAdaptor() : Parent() { }
     139
     140  public:
     141    GraphAdaptor(Graph& _graph) { setGraph(_graph); }
    142142  };
    143143
    144144  template <typename _Graph>
    145   class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
     145  class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
    146146  public:
    147147    typedef _Graph Graph;
    148     typedef GraphWrapperBase<_Graph> Parent;
    149   protected:
    150     RevGraphWrapperBase() : Parent() { }
     148    typedef GraphAdaptorBase<_Graph> Parent;
     149  protected:
     150    RevGraphAdaptorBase() : Parent() { }
    151151  public:
    152152    typedef typename Parent::Node Node;
    … …  
    166166   
    167167
    168   /// A graph wrapper which reverses the orientation of the edges.
    169 
    170   ///\warning Graph wrappers are in even more experimental state than the other
     168  /// A graph adaptor which reverses the orientation of the edges.
     169
     170  ///\warning Graph adaptors are in even more experimental state than the other
    171171  ///parts of the lib. Use them at you own risk.
    172172  ///
    … …  
    180180  /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
    181181  /// reversing its orientation.
    182   /// Then RevGraphWrapper implements the graph structure with node-set
     182  /// Then RevGraphAdaptor implements the graph structure with node-set
    183183  /// \f$V\f$ and edge-set
    184184  /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
    … …  
    186186  /// such an instance can be constructed.
    187187  /// \code
    188   /// RevGraphWrapper<ListGraph> gw(g);
     188  /// RevGraphAdaptor<ListGraph> gw(g);
    189189  /// \endcode
    190190  ///\author Marton Makai
    191191  template<typename _Graph>
    192   class RevGraphWrapper :
    193     public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
     192  class RevGraphAdaptor :
     193    public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
    194194  public:
    195195    typedef _Graph Graph;
    196196    typedef IterableGraphExtender<
    197       RevGraphWrapperBase<_Graph> > Parent;
    198   protected:
    199     RevGraphWrapper() { }
    200   public:
    201     RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
     197      RevGraphAdaptorBase<_Graph> > Parent;
     198  protected:
     199    RevGraphAdaptor() { }
     200  public:
     201    RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
    202202  };
    203203
    204204 
    205205  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
    206   class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
     206  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
    207207  public:
    208208    typedef _Graph Graph;
    209     typedef GraphWrapperBase<_Graph> Parent;
     209    typedef GraphAdaptorBase<_Graph> Parent;
    210210  protected:
    211211    NodeFilterMap* node_filter_map;
    212212    EdgeFilterMap* edge_filter_map;
    213     SubGraphWrapperBase() : Parent(),
     213    SubGraphAdaptorBase() : Parent(),
    214214                            node_filter_map(0), edge_filter_map(0) { }
    215215
    … …  
    222222
    223223  public:
    224 //     SubGraphWrapperBase(Graph& _graph,
     224//     SubGraphAdaptorBase(Graph& _graph,
    225225//                      NodeFilterMap& _node_filter_map,
    226226//                      EdgeFilterMap& _edge_filter_map) :
    … …  
    315315  };
    316316
    317   /*! \brief A graph wrapper for hiding nodes and edges from a graph.
     317  /*! \brief A graph adaptor for hiding nodes and edges from a graph.
    318318   
    319   \warning Graph wrappers are in even more experimental state than the other
     319  \warning Graph adaptors are in even more experimental state than the other
    320320  parts of the lib. Use them at you own risk.
    321321 
    322   SubGraphWrapper shows the graph with filtered node-set and
     322  SubGraphAdaptor shows the graph with filtered node-set and
    323323  edge-set.
    324324  Let \f$G=(V, A)\f$ be a directed graph
    … …  
    327327  Let moreover \f$b_V\f$ and
    328328  \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
    329   SubGraphWrapper<...>::NodeIt iterates
     329  SubGraphAdaptor<...>::NodeIt iterates
    330330  on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
    331   SubGraphWrapper<...>::EdgeIt iterates
     331  SubGraphAdaptor<...>::EdgeIt iterates
    332332  on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
    333   SubGraphWrapper<...>::OutEdgeIt and SubGraphWrapper<...>::InEdgeIt iterates
     333  SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
    334334  only on edges leaving and entering a specific node which have true value.
    335335
    … …  
    351351  Graph::EdgeMap<bool> em(g, true);
    352352  em.set(e, false);
    353   typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
     353  typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
    354354  SubGW gw(g, nm, em);
    355355  for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
    … …  
    366366  \c Graph::Node that is why \c g.id(n) can be applied.
    367367
    368   For other examples see also the documentation of NodeSubGraphWrapper and
    369   EdgeSubGraphWrapper.
     368  For other examples see also the documentation of NodeSubGraphAdaptor and
     369  EdgeSubGraphAdaptor.
    370370
    371371  \author Marton Makai
    … …  
    373373  template<typename _Graph, typename NodeFilterMap,
    374374           typename EdgeFilterMap>
    375   class SubGraphWrapper :
     375  class SubGraphAdaptor :
    376376    public IterableGraphExtender<
    377     SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
     377    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
    378378  public:
    379379    typedef _Graph Graph;
    380380    typedef IterableGraphExtender<
    381       SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
    382   protected:
    383     SubGraphWrapper() { }
    384   public:
    385     SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
     381      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
     382  protected:
     383    SubGraphAdaptor() { }
     384  public:
     385    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
    386386                    EdgeFilterMap& _edge_filter_map) {
    387387      setGraph(_graph);
    … …  
    393393
    394394
    395   /*! \brief A wrapper for hiding nodes from a graph.
    396 
    397   \warning Graph wrappers are in even more experimental state than the other
     395  /*! \brief An adaptor for hiding nodes from a graph.
     396
     397  \warning Graph adaptors are in even more experimental state than the other
    398398  parts of the lib. Use them at you own risk.
    399399 
    400   A wrapper for hiding nodes from a graph.
    401   This wrapper specializes SubGraphWrapper in the way that only the node-set
     400  An adaptor for hiding nodes from a graph.
     401  This adaptor specializes SubGraphAdaptor in the way that only the node-set
    402402  can be filtered. Note that this does not mean of considering induced
    403403  subgraph, the edge-iterators consider the original edge-set.
    … …  
    405405  */
    406406  template<typename Graph, typename NodeFilterMap>
    407   class NodeSubGraphWrapper :
    408     public SubGraphWrapper<Graph, NodeFilterMap,
     407  class NodeSubGraphAdaptor :
     408    public SubGraphAdaptor<Graph, NodeFilterMap,
    409409                           ConstMap<typename Graph::Edge,bool> > {
    410410  public:
    411     typedef SubGraphWrapper<Graph, NodeFilterMap,
     411    typedef SubGraphAdaptor<Graph, NodeFilterMap,
    412412                            ConstMap<typename Graph::Edge,bool> > Parent;
    413413  protected:
    414414    ConstMap<typename Graph::Edge, bool> const_true_map;
    415415  public:
    416     NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
     416    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
    417417      Parent(), const_true_map(true) {
    418418      Parent::setGraph(_graph);
    … …  
    423423
    424424
    425   /*! \brief A wrapper for hiding edges from a graph.
    426 
    427   \warning Graph wrappers are in even more experimental state than the other
     425  /*! \brief An adaptor for hiding edges from a graph.
     426
     427  \warning Graph adaptors are in even more experimental state than the other
    428428  parts of the lib. Use them at you own risk.
    429429 
    430   A wrapper for hiding edges from a graph.
    431   This wrapper specializes SubGraphWrapper in the way that only the edge-set
    432   can be filtered. The usefulness of this wrapper is demonstrated in the
     430  An adaptor for hiding edges from a graph.
     431  This adaptor specializes SubGraphAdaptor in the way that only the edge-set
     432  can be filtered. The usefulness of this adaptor is demonstrated in the
    433433  problem of searching a maximum number of edge-disjoint shortest paths
    434434  between
    … …  
    499499  TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
    500500 
    501   typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
     501  typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
    502502  SubGW gw(g, tight_edge_filter);
    503503  \endcode
    … …  
    550550  */
    551551  template<typename Graph, typename EdgeFilterMap>
    552   class EdgeSubGraphWrapper :
    553     public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
     552  class EdgeSubGraphAdaptor :
     553    public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
    554554                           EdgeFilterMap> {
    555555  public:
    556     typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
     556    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
    557557                            EdgeFilterMap> Parent;
    558558  protected:
    559559    ConstMap<typename Graph::Node, bool> const_true_map;
    560560  public:
    561     EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
     561    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
    562562      Parent(), const_true_map(true) {
    563563      Parent::setGraph(_graph);
    … …  
    568568
    569569  template <typename _Graph>
    570   class UndirGraphWrapperBase :
    571     public UndirGraphExtender<GraphWrapperBase<_Graph> > {
     570  class UndirGraphAdaptorBase :
     571    public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
    572572  public:
    573573    typedef _Graph Graph;
    574     typedef UndirGraphExtender<GraphWrapperBase<_Graph> > Parent;
    575   protected:
    576     UndirGraphWrapperBase() : Parent() { }
     574    typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
     575  protected:
     576    UndirGraphAdaptorBase() : Parent() { }
    577577  public:
    578578    typedef typename Parent::UndirEdge UndirEdge;
    … …  
    585585    class EdgeMap {
    586586    protected:
    587       const UndirGraphWrapperBase<_Graph>* g;
     587      const UndirGraphAdaptorBase<_Graph>* g;
    588588      template <typename TT> friend class EdgeMap;
    589589      typename _Graph::template EdgeMap<T> forward_map, backward_map;
    … …  
    592592      typedef Edge Key;
    593593     
    594       EdgeMap(const UndirGraphWrapperBase<_Graph>& _g) : g(&_g),
     594      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
    595595        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
    596596
    597       EdgeMap(const UndirGraphWrapperBase<_Graph>& _g, T a) : g(&_g),
     597      EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
    598598        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
    599599     
    … …  
    621621      typedef UndirEdge Key;
    622622     
    623       UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g) :
     623      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
    624624        map(*(g.graph)) { }
    625625
    626       UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g, T a) :
     626      UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
    627627        map(*(g.graph), a) { }
    628628     
    … …  
    638638  };
    639639
    640   /// \brief An undirected graph is made from a directed graph by a wrapper
     640  /// \brief An undirected graph is made from a directed graph by an adaptor
    641641  ///
    642642  /// Undocumented, untested!!!
    … …  
    645645  /// \author Marton Makai
    646646  template<typename _Graph>
    647   class UndirGraphWrapper :
     647  class UndirGraphAdaptor :
    648648    public IterableUndirGraphExtender<
    649     UndirGraphWrapperBase<_Graph> > {
     649    UndirGraphAdaptorBase<_Graph> > {
    650650  public:
    651651    typedef _Graph Graph;
    652652    typedef IterableUndirGraphExtender<
    653       UndirGraphWrapperBase<_Graph> > Parent;
    654   protected:
    655     UndirGraphWrapper() { }
    656   public:
    657     UndirGraphWrapper(_Graph& _graph) {
     653      UndirGraphAdaptorBase<_Graph> > Parent;
     654  protected:
     655    UndirGraphAdaptor() { }
     656  public:
     657    UndirGraphAdaptor(_Graph& _graph) {
    658658      setGraph(_graph);
    659659    }
    … …  
    663663  template <typename _Graph,
    664664            typename ForwardFilterMap, typename BackwardFilterMap>
    665   class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
     665  class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
    666666  public:
    667667    typedef _Graph Graph;
    668     typedef GraphWrapperBase<_Graph> Parent;
     668    typedef GraphAdaptorBase<_Graph> Parent;
    669669  protected:
    670670    ForwardFilterMap* forward_filter;
    671671    BackwardFilterMap* backward_filter;
    672     SubBidirGraphWrapperBase() : Parent(),
     672    SubBidirGraphAdaptorBase() : Parent(),
    673673                                 forward_filter(0), backward_filter(0) { }
    674674
    … …  
    681681
    682682  public:
    683 //     SubGraphWrapperBase(Graph& _graph,
     683//     SubGraphAdaptorBase(Graph& _graph,
    684684//                      NodeFilterMap& _node_filter_map,
    685685//                      EdgeFilterMap& _edge_filter_map) :
    … …  
    691691    typedef typename _Graph::Edge GraphEdge;
    692692    template <typename T> class EdgeMap;
    693     /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
     693    /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
    694694    /// _Graph::Edge. It contains an extra bool flag which is true
    695695    /// if and only if the
    696696    /// edge is the backward version of the original edge.
    697697    class Edge : public _Graph::Edge {
    698       friend class SubBidirGraphWrapperBase<
     698      friend class SubBidirGraphAdaptorBase<
    699699        Graph, ForwardFilterMap, BackwardFilterMap>;
    700700      template<typename T> friend class EdgeMap;
    … …  
    850850
    851851    template <typename T>
    852     /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
     852    /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
    853853    /// _Graph::EdgeMap one for the forward edges and
    854854    /// one for the backward edges.
    … …  
    860860      typedef Edge Key;
    861861
    862       EdgeMap(const SubBidirGraphWrapperBase<_Graph,
     862      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
    863863              ForwardFilterMap, BackwardFilterMap>& g) :
    864864        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
    865865
    866       EdgeMap(const SubBidirGraphWrapperBase<_Graph,
     866      EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
    867867              ForwardFilterMap, BackwardFilterMap>& g, T a) :
    868868        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
    … …  
    900900
    901901
    902   ///\brief A wrapper for composing a subgraph of a
     902  ///\brief An adaptor for composing a subgraph of a
    903903  /// bidirected graph made from a directed one.
    904904  ///
    905   /// A wrapper for composing a subgraph of a
     905  /// An adaptor for composing a subgraph of a
    906906  /// bidirected graph made from a directed one.
    907907  ///
    908   ///\warning Graph wrappers are in even more experimental state than the other
     908  ///\warning Graph adaptors are in even more experimental state than the other
    909909  ///parts of the lib. Use them at you own risk.
    910910  ///
    … …  
    914914  /// maps on the edge-set,
    915915  /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
    916   /// SubBidirGraphWrapper implements the graph structure with node-set
     916  /// SubBidirGraphAdaptor implements the graph structure with node-set
    917917  /// \f$V\f$ and edge-set
    918918  /// \f$\{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}\}\f$.
    … …  
    924924  /// the maps are able to attach different values for them.
    925925  ///
    926   /// An example for such a construction is \c RevGraphWrapper where the
     926  /// An example for such a construction is \c RevGraphAdaptor where the
    927927  /// forward_filter is everywhere false and the backward_filter is
    928928  /// everywhere true. We note that for sake of efficiency,
    929   /// \c RevGraphWrapper is implemented in a different way.
    930   /// But BidirGraphWrapper is obtained from
    931   /// SubBidirGraphWrapper by considering everywhere true
     929  /// \c RevGraphAdaptor is implemented in a different way.
     930  /// But BidirGraphAdaptor is obtained from
     931  /// SubBidirGraphAdaptor by considering everywhere true
    932932  /// valued maps both for forward_filter and backward_filter.
    933933  ///
    934   /// The most important application of SubBidirGraphWrapper
    935   /// is ResGraphWrapper, which stands for the residual graph in directed
     934  /// The most important application of SubBidirGraphAdaptor
     935  /// is ResGraphAdaptor, which stands for the residual graph in directed
    936936  /// flow and circulation problems.
    937   /// As wrappers usually, the SubBidirGraphWrapper implements the
     937  /// As adaptors usually, the SubBidirGraphAdaptor implements the
    938938  /// above mentioned graph structure without its physical storage,
    939939  /// that is the whole stuff is stored in constant memory.
    940940  template<typename _Graph,
    941941           typename ForwardFilterMap, typename BackwardFilterMap>
    942   class SubBidirGraphWrapper :
     942  class SubBidirGraphAdaptor :
    943943    public IterableGraphExtender<
    944     SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
     944    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
    945945  public:
    946946    typedef _Graph Graph;
    947947    typedef IterableGraphExtender<
    948       SubBidirGraphWrapperBase<
     948      SubBidirGraphAdaptorBase<
    949949      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
    950950  protected:
    951     SubBidirGraphWrapper() { }
    952   public:
    953     SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
     951    SubBidirGraphAdaptor() { }
     952  public:
     953    SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
    954954                         BackwardFilterMap& _backward_filter) {
    955955      setGraph(_graph);
    … …  
    961961
    962962
    963   ///\brief A wrapper for composing bidirected graph from a directed one.
     963  ///\brief An adaptor for composing bidirected graph from a directed one.
    964964  ///
    965   ///\warning Graph wrappers are in even more experimental state than the other
     965  ///\warning Graph adaptors are in even more experimental state than the other
    966966  ///parts of the lib. Use them at you own risk.
    967967  ///
    968   /// A wrapper for composing bidirected graph from a directed one.
     968  /// An adaptor for composing bidirected graph from a directed one.
    969969  /// A bidirected graph is composed over the directed one without physical
    970970  /// storage. As the oppositely directed edges are logically different ones
    971971  /// the maps are able to attach different values for them.
    972972  template<typename Graph>
    973   class BidirGraphWrapper :
    974     public SubBidirGraphWrapper<
     973  class BidirGraphAdaptor :
     974    public SubBidirGraphAdaptor<
    975975    Graph,
    976976    ConstMap<typename Graph::Edge, bool>,
    977977    ConstMap<typename Graph::Edge, bool> > {
    978978  public:
    979     typedef  SubBidirGraphWrapper<
     979    typedef  SubBidirGraphAdaptor<
    980980      Graph,
    981981      ConstMap<typename Graph::Edge, bool>,
    … …  
    984984    ConstMap<typename Graph::Edge, bool> cm;
    985985
    986     BidirGraphWrapper() : Parent(), cm(true) {
     986    BidirGraphAdaptor() : Parent(), cm(true) {
    987987      Parent::setForwardFilterMap(cm);
    988988      Parent::setBackwardFilterMap(cm);
    989989    }
    990990  public:
    991     BidirGraphWrapper(Graph& _graph) : Parent(), cm(true) {
     991    BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
    992992      Parent::setGraph(_graph);
    993993      Parent::setForwardFilterMap(cm);
    … …  
    998998      return 2*this->graph->edgeNum();
    999999    }
    1000     //    KEEP_MAPS(Parent, BidirGraphWrapper);
     1000    //    KEEP_MAPS(Parent, BidirGraphAdaptor);
    10011001  };
    10021002
    … …  
    10381038
    10391039 
    1040   /*! \brief A wrapper for composing the residual graph for directed flow and circulation problems.
    1041 
    1042   A wrapper for composing the residual graph for directed flow and circulation problems.
     1040  /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
     1041
     1042  An adaptor for composing the residual graph for directed flow and circulation problems.
    10431043  Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
    10441044  number type. Let moreover
    10451045  \f$f,c:A\to F\f$, be functions on the edge-set.
    1046   In the appications of ResGraphWrapper, \f$f\f$ usually stands for a flow
     1046  In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
    10471047  and \f$c\f$ for a capacity function.   
    10481048  Suppose that a graph instange \c g of type
    … …  
    10511051  ListGraph g;
    10521052  \endcode
    1053   Then RevGraphWrapper implements the graph structure with node-set
     1053  Then RevGraphAdaptor implements the graph structure with node-set
    10541054  \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
    10551055  \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
    … …  
    10581058  When we take the union \f$A_{forward}\cup A_{backward}\f$,
    10591059  multilicities are counted, i.e. if an edge is in both
    1060   \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the wrapper it
     1060  \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
    10611061  appears twice.
    10621062  The following code shows how
    … …  
    10661066  Graph::EdgeMap<int> f(g);
    10671067  Graph::EdgeMap<int> c(g);
    1068   ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
     1068  ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
    10691069  \endcode
    10701070  \author Marton Makai
    … …  
    10721072  template<typename Graph, typename Number,
    10731073           typename CapacityMap, typename FlowMap>
    1074   class ResGraphWrapper :
    1075     public SubBidirGraphWrapper<
     1074  class ResGraphAdaptor :
     1075    public SubBidirGraphAdaptor<
    10761076    Graph,
    10771077    ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
    10781078    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
    10791079  public:
    1080     typedef SubBidirGraphWrapper<
     1080    typedef SubBidirGraphAdaptor<
    10811081      Graph,
    10821082      ResForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
    … …  
    10871087    ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
    10881088    ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
    1089     ResGraphWrapper() : Parent(),
     1089    ResGraphAdaptor() : Parent(),
    10901090                        capacity(0), flow(0) { }
    10911091    void setCapacityMap(const CapacityMap& _capacity) {
    … …  
    11001100    }
    11011101  public:
    1102     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
     1102    ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
    11031103                       FlowMap& _flow) :
    11041104      Parent(), capacity(&_capacity), flow(&_flow),
    … …  
    11251125    class ResCap {
    11261126    protected:
    1127       const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
     1127      const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
    11281128    public:
    11291129      typedef Number Value;
    11301130      typedef Edge Key;
    1131       ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
     1131      ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
    11321132             _res_graph) : res_graph(&_res_graph) { }
    11331133      Number operator[](const Edge& e) const {
    … …  
    11391139    };
    11401140
    1141     //    KEEP_MAPS(Parent, ResGraphWrapper);
     1141    //    KEEP_MAPS(Parent, ResGraphAdaptor);
    11421142  };
    11431143
    … …  
    11451145
    11461146  template <typename _Graph, typename FirstOutEdgesMap>
    1147   class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
     1147  class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
    11481148  public:
    11491149    typedef _Graph Graph;
    1150     typedef GraphWrapperBase<_Graph> Parent;
     1150    typedef GraphAdaptorBase<_Graph> Parent;
    11511151  protected:
    11521152    FirstOutEdgesMap* first_out_edges;
    1153     ErasingFirstGraphWrapperBase() : Parent(),
     1153    ErasingFirstGraphAdaptorBase() : Parent(),
    11541154                                     first_out_edges(0) { }
    11551155
    … …  
    11781178  /// For blocking flows.
    11791179
    1180   ///\warning Graph wrappers are in even more experimental state than the other
     1180  ///\warning Graph adaptors are in even more experimental state than the other
    11811181  ///parts of the lib. Use them at you own risk.
    11821182  ///
    1183   /// This graph wrapper is used for on-the-fly
     1183  /// This graph adaptor is used for on-the-fly
    11841184  /// Dinits blocking flow computations.
    11851185  /// For each node, an out-edge is stored which is used when the
    … …  
    11911191  /// \author Marton Makai
    11921192  template <typename _Graph, typename FirstOutEdgesMap>
    1193   class ErasingFirstGraphWrapper :
     1193  class ErasingFirstGraphAdaptor :
    11941194    public IterableGraphExtender<
    1195     ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
     1195    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
    11961196  public:
    11971197    typedef _Graph Graph;
    11981198    typedef IterableGraphExtender<
    1199       ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
    1200     ErasingFirstGraphWrapper(Graph& _graph,
     1199      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
     1200    ErasingFirstGraphAdaptor(Graph& _graph,
    12011201                             FirstOutEdgesMap& _first_out_edges) {
    12021202      setGraph(_graph);
    … …  
    12101210} //namespace lemon
    12111211
    1212 #endif //LEMON_GRAPH_WRAPPER_H
    1213 
     1212#endif //LEMON_GRAPH_ADAPTOR_H
     1213

  • src/lemon/min_cost_flow.h

    r1359 r1401  
    2424
    2525#include <lemon/dijkstra.h>
    26 #include <lemon/graph_wrapper.h>
     26#include <lemon/graph_adaptor.h>
    2727#include <lemon/maps.h>
    2828#include <vector>
    … …  
    6969    typedef typename Graph::template EdgeMap<int> EdgeIntMap;
    7070
    71     typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGW;
     71    typedef ResGraphAdaptor<const Graph,int,CapacityMap,EdgeIntMap> ResGW;
    7272    typedef typename ResGW::Edge ResGraphEdge;
    7373

  • src/test/Makefile.am

    r1387 r1401  
    1717        dijkstra_test \
    1818        graph_test \
    19         graph_wrapper_test \
     19        graph_adaptor_test \
    2020        graph_utils_test \
    2121        kruskal_test \
    … …  
    5050graph_test_SOURCES = graph_test.cc
    5151graph_utils_test_SOURCES = graph_utils_test.cc
    52 graph_wrapper_test_SOURCES = graph_wrapper_test.cc
     52graph_adaptor_test_SOURCES = graph_adaptor_test.cc
    5353kruskal_test_SOURCES = kruskal_test.cc
    5454maps_test_SOURCES = maps_test.cc

  • src/test/graph_adaptor_test.cc

    r1383 r1401  
    11/* -*- C++ -*-
    2  * src/test/graph_wrapper_test.cc - Part of LEMON, a generic C++ optimization library
     2 * src/test/graph_adaptor_test.cc - Part of LEMON, a generic C++ optimization library
    33 *
    44 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    … …  
    2424#include<lemon/list_graph.h>
    2525#include<lemon/full_graph.h>
    26 #include<lemon/graph_wrapper.h>
     26#include<lemon/graph_adaptor.h>
    2727
    2828#include"test/test_tools.h"
    … …  
    3131/**
    3232\file
    33 This test makes consistency checks of graph wrappers.
     33This test makes consistency checks of graph adaptors.
    3434
    3535\todo More extensive tests are needed
    … …  
    4545  {
    4646    typedef StaticGraph Graph;
    47     checkConcept<StaticGraph, GraphWrapper<Graph> >();
     47    checkConcept<StaticGraph, GraphAdaptor<Graph> >();
    4848
    49     checkConcept<StaticGraph, RevGraphWrapper<Graph> >();
     49    checkConcept<StaticGraph, RevGraphAdaptor<Graph> >();
    5050
    51     checkConcept<StaticGraph, SubGraphWrapper<Graph,
     51    checkConcept<StaticGraph, SubGraphAdaptor<Graph,
    5252      Graph::NodeMap<bool> , Graph::EdgeMap<bool> > >();
    53     checkConcept<StaticGraph, NodeSubGraphWrapper<Graph,
     53    checkConcept<StaticGraph, NodeSubGraphAdaptor<Graph,
    5454      Graph::NodeMap<bool> > >();
    55     checkConcept<StaticGraph, EdgeSubGraphWrapper<Graph,
     55    checkConcept<StaticGraph, EdgeSubGraphAdaptor<Graph,
    5656      Graph::EdgeMap<bool> > >();
    5757   
    58     checkConcept<StaticGraph, SubBidirGraphWrapper<Graph,
     58    checkConcept<StaticGraph, SubBidirGraphAdaptor<Graph,
    5959      Graph::EdgeMap<bool>, Graph::EdgeMap<bool> > >();
    6060    //    checkConcept<StaticGraph, BidirGraph<Graph> >();
    61     checkConcept<StaticGraph, ResGraphWrapper<Graph, int,
     61    checkConcept<StaticGraph, ResGraphAdaptor<Graph, int,
    6262      Graph::EdgeMap<int>, Graph::EdgeMap<int> > >();
    6363
    64     checkConcept<StaticGraph, ErasingFirstGraphWrapper<Graph,
     64    checkConcept<StaticGraph, ErasingFirstGraphAdaptor<Graph,
    6565      Graph::NodeMap<Graph::Edge> > >();
    6666
    6767    /// \bug why does not compile with StaticGraph
    68     checkConcept<BaseIterableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
    69     checkConcept<IterableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
    70     checkConcept<MappableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
     68    checkConcept<BaseIterableUndirGraphConcept, UndirGraphAdaptor<ListGraph> >();
     69    checkConcept<IterableUndirGraphConcept, UndirGraphAdaptor<ListGraph> >();
     70    checkConcept<MappableUndirGraphConcept, UndirGraphAdaptor<ListGraph> >();
    7171  }
    7272  std::cout << __FILE__ ": All tests passed.\n";
Note: See TracChangeset for help on using the changeset viewer.