COIN-OR::LEMON - Graph Library

Changeset 2031:080d51024ac5 in lemon-0.x for lemon/graph_adaptor.h


Ignore:
Timestamp:
04/03/06 11:45:23 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2670
Message:

Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.

Some bugfix in the adaptors

New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_adaptor.h

    r1999 r2031  
    2020#define LEMON_GRAPH_ADAPTOR_H
    2121
    22 ///\ingroup graph_adaptors
    23 ///\file
    24 ///\brief Several graph adaptors.
     22/// \ingroup graph_adaptors
     23/// \file
     24/// \brief Several graph adaptors.
    2525///
    26 ///This file contains several useful graph adaptor functions.
     26/// This file contains several useful graph adaptor functions.
    2727///
    28 ///\author Marton Makai
     28/// \author Marton Makai and Balazs Dezso
    2929
    3030#include <lemon/bits/invalid.h>
     
    6262  public:
    6363    typedef _Graph Graph;
     64    typedef GraphAdaptorBase Adaptor;
    6465    typedef Graph ParentGraph;
    6566
     
    116117    int id(const Edge& e) const { return graph->id(e); }
    117118
     119    Node fromNodeId(int id) const {
     120      return graph->fromNodeId(id);
     121    }
     122
     123    Edge fromEdgeId(int id) const {
     124      return graph->fromEdgeId(id);
     125    }
     126
    118127    int maxNodeId() const {
    119128      return graph->maxNodeId();
     
    137146   
    138147    template <typename _Value>
    139     class NodeMap : public _Graph::template NodeMap<_Value> {
     148    class NodeMap : public Graph::template NodeMap<_Value> {
    140149    public:
    141       typedef typename _Graph::template NodeMap<_Value> Parent;
    142       explicit NodeMap(const GraphAdaptorBase<_Graph>& ga)
    143         : Parent(*ga.graph) { }
    144       NodeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value)
     150
     151      typedef typename Graph::template NodeMap<_Value> Parent;
     152
     153      explicit NodeMap(const Adaptor& ga)
     154        : Parent(*ga.graph) {}
     155
     156      NodeMap(const Adaptor& ga, const _Value& value)
    145157        : Parent(*ga.graph, value) { }
     158
     159      NodeMap& operator=(const NodeMap& cmap) {
     160        return operator=<NodeMap>(cmap);
     161      }
     162
     163      template <typename CMap>
     164      NodeMap& operator=(const CMap& cmap) {
     165        Parent::operator=(cmap);
     166        return *this;
     167      }
     168     
    146169    };
    147170
    148171    template <typename _Value>
    149     class EdgeMap : public _Graph::template EdgeMap<_Value> {
     172    class EdgeMap : public Graph::template EdgeMap<_Value> {
    150173    public:
    151       typedef typename _Graph::template EdgeMap<_Value> Parent;
    152       explicit EdgeMap(const GraphAdaptorBase<_Graph>& ga)
    153         : Parent(*ga.graph) { }
    154       EdgeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value)
    155         : Parent(*ga.graph, value) { }
     174     
     175      typedef typename Graph::template EdgeMap<_Value> Parent;
     176     
     177      explicit EdgeMap(const Adaptor& ga)
     178        : Parent(*ga.graph) {}
     179
     180      EdgeMap(const Adaptor& ga, const _Value& value)
     181        : Parent(*ga.graph, value) {}
     182
     183      EdgeMap& operator=(const EdgeMap& cmap) {
     184        return operator=<EdgeMap>(cmap);
     185      }
     186
     187      template <typename CMap>
     188      EdgeMap& operator=(const CMap& cmap) {
     189        Parent::operator=(cmap);
     190        return *this;
     191      }
     192
    156193    };
    157194
     
    256293  public:
    257294    typedef _Graph Graph;
     295    typedef SubGraphAdaptorBase Adaptor;
    258296    typedef GraphAdaptorBase<_Graph> Parent;
    259297  protected:
     
    378416      return edge;
    379417    }
     418
     419    template <typename _Value>
     420    class NodeMap
     421      : public SubMapExtender<Adaptor,
     422                              typename Parent::template NodeMap<_Value> >
     423    {
     424    public:
     425      typedef Adaptor Graph;
     426      typedef SubMapExtender<Adaptor, typename Parent::
     427                             template NodeMap<_Value> > Parent;
     428   
     429      NodeMap(const Graph& graph)
     430        : Parent(graph) {}
     431      NodeMap(const Graph& graph, const _Value& value)
     432        : Parent(graph, value) {}
     433   
     434      NodeMap& operator=(const NodeMap& cmap) {
     435        return operator=<NodeMap>(cmap);
     436      }
     437   
     438      template <typename CMap>
     439      NodeMap& operator=(const CMap& cmap) {
     440        Parent::operator=(cmap);
     441        return *this;
     442      }
     443    };
     444
     445    template <typename _Value>
     446    class EdgeMap
     447      : public SubMapExtender<Adaptor,
     448                              typename Parent::template EdgeMap<_Value> >
     449    {
     450    public:
     451      typedef Adaptor Graph;
     452      typedef SubMapExtender<Adaptor, typename Parent::
     453                             template EdgeMap<_Value> > Parent;
     454   
     455      EdgeMap(const Graph& graph)
     456        : Parent(graph) {}
     457      EdgeMap(const Graph& graph, const _Value& value)
     458        : Parent(graph, value) {}
     459   
     460      EdgeMap& operator=(const EdgeMap& cmap) {
     461        return operator=<EdgeMap>(cmap);
     462      }
     463   
     464      template <typename CMap>
     465      EdgeMap& operator=(const CMap& cmap) {
     466        Parent::operator=(cmap);
     467        return *this;
     468      }
     469    };
     470
    380471  };
    381472
     
    385476  public:
    386477    typedef _Graph Graph;
     478    typedef SubGraphAdaptorBase Adaptor;
    387479    typedef GraphAdaptorBase<_Graph> Parent;
    388480  protected:
     
    497589      return edge;
    498590    }
     591
     592    template <typename _Value>
     593    class NodeMap
     594      : public SubMapExtender<Adaptor,
     595                              typename Parent::template NodeMap<_Value> >
     596    {
     597    public:
     598      typedef Adaptor Graph;
     599      typedef SubMapExtender<Adaptor, typename Parent::
     600                             template NodeMap<_Value> > Parent;
     601   
     602      NodeMap(const Graph& graph)
     603        : Parent(graph) {}
     604      NodeMap(const Graph& graph, const _Value& value)
     605        : Parent(graph, value) {}
     606   
     607      NodeMap& operator=(const NodeMap& cmap) {
     608        return operator=<NodeMap>(cmap);
     609      }
     610   
     611      template <typename CMap>
     612      NodeMap& operator=(const CMap& cmap) {
     613        Parent::operator=(cmap);
     614        return *this;
     615      }
     616    };
     617
     618    template <typename _Value>
     619    class EdgeMap
     620      : public SubMapExtender<Adaptor,
     621                              typename Parent::template EdgeMap<_Value> >
     622    {
     623    public:
     624      typedef Adaptor Graph;
     625      typedef SubMapExtender<Adaptor, typename Parent::
     626                             template EdgeMap<_Value> > Parent;
     627   
     628      EdgeMap(const Graph& graph)
     629        : Parent(graph) {}
     630      EdgeMap(const Graph& graph, const _Value& value)
     631        : Parent(graph, value) {}
     632   
     633      EdgeMap& operator=(const EdgeMap& cmap) {
     634        return operator=<EdgeMap>(cmap);
     635      }
     636   
     637      template <typename CMap>
     638      EdgeMap& operator=(const CMap& cmap) {
     639        Parent::operator=(cmap);
     640        return *this;
     641      }
     642    };
     643
    499644  };
    500645
     
    567712  public:
    568713    typedef _Graph Graph;
    569     typedef GraphAdaptorExtender<
    570       SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
     714    typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap,
     715                                                      EdgeFilterMap, checked> >
     716    Parent;
     717
    571718  protected:
    572719    SubGraphAdaptor() { }
    573720  public:
     721
    574722    SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
    575723                    EdgeFilterMap& _edge_filter_map) {
     
    578726      setEdgeFilterMap(_edge_filter_map);
    579727    }
     728
    580729  };
    581730
     
    636785                           ConstMap<typename Graph::Edge,bool>, checked> {
    637786  public:
     787
    638788    typedef SubGraphAdaptor<Graph, NodeFilterMap,
    639                             ConstMap<typename Graph::Edge,bool> > Parent;
     789                            ConstMap<typename Graph::Edge,bool>, checked >
     790    Parent;
     791
    640792  protected:
    641793    ConstMap<typename Graph::Edge, bool> const_true_map;
     
    646798
    647799  public:
     800
    648801    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
    649802      Parent(), const_true_map(true) {
     
    652805      Parent::setEdgeFilterMap(const_true_map);
    653806    }
     807
    654808  };
    655809
     
    821975
    822976  public:
     977
    823978    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
    824979      Parent(), const_true_map(true) {
     
    827982      Parent::setEdgeFilterMap(_edge_filter_map);
    828983    }
     984
    829985  };
    830986
     
    8491005  public:
    8501006    typedef _Graph Graph;
     1007    typedef UndirGraphAdaptorBase Adaptor;
    8511008    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
    8521009
     
    8601017    typedef typename Parent::Edge Edge;
    8611018
     1019  private:
    8621020   
    8631021    template <typename _Value>
    864     class EdgeMap {
     1022    class EdgeMapBase {
    8651023    private:
    8661024     
     
    8741032      typedef Edge Key;
    8751033     
    876       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) :
    877         forward_map(*(_g.graph)), backward_map(*(_g.graph)) {}
    878 
    879       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a)
    880         : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {}
     1034      EdgeMapBase(const Adaptor& adaptor) :
     1035        forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
     1036
     1037      EdgeMapBase(const Adaptor& adaptor, const Value& v)
     1038        : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
    8811039     
    8821040      void set(const Edge& e, const Value& a) {
     
    9091067
    9101068    };
     1069
     1070  public:
     1071
     1072    template <typename _Value>
     1073    class EdgeMap
     1074      : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
     1075    {
     1076    public:
     1077      typedef Adaptor Graph;
     1078      typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
     1079   
     1080      EdgeMap(const Graph& graph)
     1081        : Parent(graph) {}
     1082      EdgeMap(const Graph& graph, const _Value& value)
     1083        : Parent(graph, value) {}
     1084   
     1085      EdgeMap& operator=(const EdgeMap& cmap) {
     1086        return operator=<EdgeMap>(cmap);
     1087      }
     1088   
     1089      template <typename CMap>
     1090      EdgeMap& operator=(const CMap& cmap) {
     1091        Parent::operator=(cmap);
     1092        return *this;
     1093      }
     1094    };
    9111095       
    9121096    template <typename _Value>
    913     class UEdgeMap : public _Graph::template EdgeMap<_Value> {
     1097    class UEdgeMap : public Graph::template EdgeMap<_Value> {
    9141098    public:
    915 
    916       typedef typename _Graph::template EdgeMap<_Value> Parent;
    917 
    918       UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g)
    919         : Parent(*(g.graph)) {}
    920 
    921       UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a)
    922         : Parent(*(g.graph), a) {}
    923      
     1099     
     1100      typedef typename Graph::template EdgeMap<_Value> Parent;
     1101     
     1102      explicit UEdgeMap(const Adaptor& ga)
     1103        : Parent(*ga.graph) {}
     1104
     1105      UEdgeMap(const Adaptor& ga, const _Value& value)
     1106        : Parent(*ga.graph, value) {}
     1107
     1108      UEdgeMap& operator=(const UEdgeMap& cmap) {
     1109        return operator=<UEdgeMap>(cmap);
     1110      }
     1111
     1112      template <typename CMap>
     1113      UEdgeMap& operator=(const CMap& cmap) {
     1114        Parent::operator=(cmap);
     1115        return *this;
     1116      }
     1117
    9241118    };
    9251119     
     
    9341128
    9351129    typedef _Graph Graph;
     1130    typedef UndirGraphAdaptorBase Adaptor;
    9361131    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
    9371132
     
    10341229    NotifierProxy edge_notifier_proxy;
    10351230
    1036   public:
    1037    
     1231  private:
    10381232   
    10391233    template <typename _Value>
    1040     class EdgeMap {
     1234    class EdgeMapBase {
    10411235    private:
    10421236     
     
    10501244      typedef Edge Key;
    10511245     
    1052       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) :
    1053         forward_map(*(_g.graph)), backward_map(*(_g.graph)) {}
    1054 
    1055       EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a)
    1056         : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {}
     1246      EdgeMapBase(const Adaptor& adaptor) :
     1247        forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
     1248
     1249      EdgeMapBase(const Adaptor& adaptor, const Value& v)
     1250        : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
    10571251     
    10581252      void set(const Edge& e, const Value& a) {
     
    10641258      }
    10651259
    1066       typename MapTraits<MapImpl>::ConstReturnValue
    1067       operator[](const Edge& e) const {
     1260      typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
    10681261        if (Parent::direction(e)) {
    10691262          return forward_map[e];
     
    10731266      }
    10741267
    1075       typename MapTraits<MapImpl>::ReturnValue
    1076       operator[](const Edge& e) {
     1268      typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
    10771269        if (Parent::direction(e)) {
    10781270          return forward_map[e];
     
    10871279
    10881280    };
     1281
     1282  public:
     1283
     1284    template <typename _Value>
     1285    class EdgeMap
     1286      : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
     1287    {
     1288    public:
     1289      typedef Adaptor Graph;
     1290      typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
     1291   
     1292      EdgeMap(const Graph& graph)
     1293        : Parent(graph) {}
     1294      EdgeMap(const Graph& graph, const _Value& value)
     1295        : Parent(graph, value) {}
     1296   
     1297      EdgeMap& operator=(const EdgeMap& cmap) {
     1298        return operator=<EdgeMap>(cmap);
     1299      }
     1300   
     1301      template <typename CMap>
     1302      EdgeMap& operator=(const CMap& cmap) {
     1303        Parent::operator=(cmap);
     1304        return *this;
     1305      }
     1306    };
    10891307       
    10901308    template <typename _Value>
    1091     class UEdgeMap : public _Graph::template EdgeMap<_Value> {
     1309    class UEdgeMap : public Graph::template EdgeMap<_Value> {
    10921310    public:
    1093 
    1094       typedef typename _Graph::template EdgeMap<_Value> Parent;
    1095 
    1096       UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g)
    1097         : Parent(*(g.graph)) {}
    1098 
    1099       UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a)
    1100         : Parent(*(g.graph), a) {}
    1101      
     1311     
     1312      typedef typename Graph::template EdgeMap<_Value> Parent;
     1313     
     1314      explicit UEdgeMap(const Adaptor& ga)
     1315        : Parent(*ga.graph) {}
     1316
     1317      UEdgeMap(const Adaptor& ga, const _Value& value)
     1318        : Parent(*ga.graph, value) {}
     1319
     1320      UEdgeMap& operator=(const UEdgeMap& cmap) {
     1321        return operator=<UEdgeMap>(cmap);
     1322      }
     1323
     1324      template <typename CMap>
     1325      UEdgeMap& operator=(const CMap& cmap) {
     1326        Parent::operator=(cmap);
     1327        return *this;
     1328      }
     1329
    11021330    };
    11031331     
Note: See TracChangeset for help on using the changeset viewer.