COIN-OR::LEMON - Graph Library

Changeset 1013:b3bdd856faf4 in lemon-0.x


Ignore:
Timestamp:
11/20/04 15:09:27 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1403
Message:

MergeGraphWrapper?

Location:
src
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/graph_wrapper.h

    r1004 r1013  
    11761176              ForwardFilterMap, BackwardFilterMap>& g, T a) :
    11771177        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
    1178 
    1179 //       template <typename TT>
    1180 //       EdgeMap(const EdgeMap<TT>& copy)
    1181 //      : forward_map(copy.forward_map), backward_map(copy.backward_map) {}
    1182 
    1183 //       template <typename TT>
    1184 //       EdgeMap& operator=(const EdgeMap<TT>& copy) {
    1185 //      forward_map = copy.forward_map;
    1186 //      backward_map = copy.backward_map;
    1187 //      return *this;
    1188 //       }
    11891178     
    11901179      void set(Edge e, T a) {
  • src/work/marci/merge_node_graph_wrapper.h

    r1009 r1013  
    2323#include <lemon/graph_wrapper.h>
    2424#include <iostream>
     25
    2526using std::cout;
    2627using std::endl;
     
    3940  };
    4041
    41   /*! A base class for merging the node-set of two node-disjoint graphs
    42     into the node-set of one graph.
     42
     43  /*! A graph wrapper base class
     44    for merging the node-set of two node-disjoint graphs
     45    into the node-set of one graph.
     46    Generic implementation for unrelated _Graph1::Node and _Graph2::Node.
    4347   */
    4448  template <typename _Graph1, typename _Graph2, typename Enable=void>
     
    4650    public P1<_Graph1>, public P2<_Graph2> {
    4751  public:
    48     void printNode() const { std::cout << "generic" << std::endl; }
     52    static void printNode() { std::cout << "node: generic" << std::endl; }
    4953    typedef _Graph1 Graph1;
    5054    typedef _Graph2 Graph2;
     
    6064    class Node : public Graph1Node, public Graph2Node {
    6165      friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
    62       template <typename Value> friend class NodeMap;
     66      template <typename _Value> friend class NodeMap;
    6367    protected:
    6468      bool backward; //true, iff backward
     
    7377      Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { }
    7478      bool operator==(const Node& v) const {
    75         return (this->backward==v.backward &&
    76                 static_cast<Graph1Node>(*this)==
    77                 static_cast<Graph1Node>(v) &&
    78                 static_cast<Graph2Node>(*this)==
    79                 static_cast<Graph2Node>(v));
     79        if (backward)
     80          return (v.backward &&
     81                  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
     82        else
     83          return (!v.backward &&
     84                  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
    8085      }
    8186      bool operator!=(const Node& v) const {
    82         return (this->backward!=v.backward ||
    83                 static_cast<Graph1Node>(*this)!=
    84                 static_cast<Graph1Node>(v) ||
    85                 static_cast<Graph2Node>(*this)!=
    86                 static_cast<Graph2Node>(v));
     87        return !(*this==v);
    8788      }
    8889    };
     
    119120
    120121    template <typename _Value>
    121     class NodeMap : public Parent1::template NodeMap<_Value>,
    122                     public Parent2::template NodeMap<_Value> {
    123       typedef typename Parent1::template NodeMap<_Value> ParentMap1;
    124       typedef typename Parent2::template NodeMap<_Value> ParentMap2;
     122    class NodeMap {
     123    protected:
     124      typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
     125      typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
     126      ParentMap1 forward_map;
     127      ParentMap2 backward_map;
    125128    public:
    126129      typedef _Value Value;
    127130      typedef Node Key;
    128131      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
    129         ParentMap1(gw), ParentMap2(gw) { }
     132        forward_map(*(gw.Parent1::graph)),
     133        backward_map(*(gw.Parent2::graph)) { }
    130134      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
    131135              const _Value& value) :
    132         ParentMap1(gw, value), ParentMap2(gw, value) { }
     136        forward_map(*(gw.Parent1::graph), value),
     137        backward_map(*(gw.Parent2::graph), value) { }
    133138      _Value operator[](const Node& n) const {
    134139        if (!n.backward)
    135           return ParentMap1::operator[](n);
    136         else
    137           return ParentMap2::operator[](n);
     140          return forward_map[n];
     141        else
     142          return backward_map[n];
    138143      }
    139144      void set(const Node& n, const _Value& value) {
    140145        if (!n.backward)
    141           ParentMap1::set(n, value);
    142         else
    143           ParentMap2::set(n, value);
     146          forward_map.set(n, value);
     147        else
     148          backward_map.set(n, value);
    144149      }
    145150//       using ParentMap1::operator[];
     
    149154  };
    150155
    151   //not yet working
     156
     157  /*! A graph wrapper base class
     158    for merging the node-set of two node-disjoint graphs
     159    into the node-set of one graph.
     160    Specialization for the case when _Graph1::Node are the same _Graph2::Node.
     161   */
    152162  template <typename _Graph1, typename _Graph2>
    153163  class MergeNodeGraphWrapperBase<
     
    155165    boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
    156166    public P1<_Graph1>, public P2<_Graph2> {
    157   public :
    158     void printNode() const { std::cout << "same" << std::endl; }
     167  public:
     168    static void printNode() { std::cout << "node: same" << std::endl; }
    159169    typedef _Graph1 Graph1;
    160170    typedef _Graph2 Graph2;
     
    166176    MergeNodeGraphWrapperBase() { }
    167177  public:
    168     class Node { };
     178    template <typename _Value> class NodeMap;
     179
     180    class Node : public Graph1Node {
     181      friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
     182      template <typename _Value> friend class NodeMap;
     183    protected:
     184      bool backward; //true, iff backward
     185    public:
     186      Node() { }
     187      /// \todo =false is needed, or causes problems?
     188      /// If \c _backward is false, then we get an edge corresponding to the
     189      /// original one, otherwise its oppositely directed pair is obtained.
     190      Node(const Graph1Node& n1,
     191           const Graph2Node& n2, bool _backward) :
     192        Graph1Node(!backward ? n1 : n2), backward(_backward) { }
     193      Node(Invalid i) : Graph1Node(i), backward(true) { }
     194      bool operator==(const Node& v) const {
     195        return (backward==v.backward &&
     196                static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
     197      }
     198      bool operator!=(const Node& v) const {
     199        return !(*this==v);
     200      }
     201    };
     202
     203    //typedef void Edge;
    169204    class Edge { };
    170     void first() const;
    171     void next() const;
    172   };
    173 
    174   //not yet working
     205   
     206    void first(Node& i) const {
     207      Parent1::graph->first(*static_cast<Graph1Node*>(&i));
     208      i.backward=false;
     209      if (*static_cast<Graph1Node*>(&i)==INVALID) {
     210        Parent2::graph->first(*static_cast<Graph1Node*>(&i));
     211        i.backward=true;
     212      }
     213    }
     214    void next(Node& i) const {
     215      if (!(i.backward)) {
     216        Parent1::graph->next(*static_cast<Graph1Node*>(&i));
     217        if (*static_cast<Graph1Node*>(&i)==INVALID) {
     218          Parent2::graph->first(*static_cast<Graph1Node*>(&i));
     219          i.backward=true;
     220        }
     221      } else {
     222        Parent2::graph->next(*static_cast<Graph1Node*>(&i));
     223      }
     224    }
     225
     226    int id(const Node& n) const {
     227      if (!n.backward)
     228        return this->Parent1::graph->id(n);
     229      else
     230        return this->Parent2::graph->id(n);
     231    }
     232
     233    template <typename _Value>
     234    class NodeMap {
     235    protected:
     236      typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
     237      typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
     238      ParentMap1 forward_map;
     239      ParentMap2 backward_map;
     240    public:
     241      typedef _Value Value;
     242      typedef Node Key;
     243      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
     244        forward_map(*(gw.Parent1::graph)),
     245        backward_map(*(gw.Parent2::graph)) { }
     246      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
     247              const _Value& value) :
     248        forward_map(*(gw.Parent1::graph), value),
     249        backward_map(*(gw.Parent2::graph), value) { }
     250      _Value operator[](const Node& n) const {
     251        if (!n.backward)
     252          return forward_map[n];
     253        else
     254          return backward_map[n];
     255      }
     256      void set(const Node& n, const _Value& value) {
     257        if (!n.backward)
     258          forward_map.set(n, value);
     259        else
     260          backward_map.set(n, value);
     261      }
     262//       using ParentMap1::operator[];
     263//       using ParentMap2::operator[];
     264    };
     265
     266  };
     267
     268
     269  /*! A graph wrapper base class
     270    for merging the node-set of two node-disjoint graphs
     271    into the node-set of one graph.
     272    Specialization for the case when
     273    _Graph1::Node are base and derived _Graph2::Node.
     274    NOT YET IMPLEMENTED
     275   */
    175276  template <typename _Graph1, typename _Graph2>
    176277  class MergeNodeGraphWrapperBase<
     
    179280    public P1<_Graph1>, public P2<_Graph2> {
    180281  public :
    181     void printNode() const { std::cout << "2. nagyobb" << std::endl; }
     282    static void printNode() { std::cout << "node: 2nd is derived" << std::endl; }
    182283    typedef _Graph1 Graph1;
    183284    typedef _Graph2 Graph2;
     
    202303    public P1<_Graph1>, public P2<_Graph2> {
    203304  public :
    204     void printNode() const { std::cout << "1. nagyobb" << std::endl; }
     305    static void printNode() { std::cout << "node: 1st is derived" << std::endl; }
    205306    typedef _Graph1 Graph1;
    206307    typedef _Graph2 Graph2;
     
    219320
    220321
     322  /*! A graph wrapper class
     323    fors merging the node-set of two node-disjoint graphs
     324    into one node-set. It does not satisfy
     325    StaticGraph concept as it has no edge-set which
     326    works together with the node-set.
     327   */
    221328  template <typename _Graph1, typename _Graph2>
    222329  class MergeNodeGraphWrapper : public
     
    237344
    238345
    239   /*! A base class for merging the node-sets and edge-sets of
     346  /*! A grah wrapper base class
     347    for merging the node-sets and edge-sets of
    240348    two node-disjoint graphs
    241349    into one graph.
     350    Generic implementation for unrelated _Graph1::Edge and _Graph2::Edge.
    242351   */
    243352  template <typename _Graph1, typename _Graph2, typename Enable=void>
     
    245354    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
    246355  public:
    247     void printEdge() const { std::cout << "generic" << std::endl; }
     356    static void printEdge() { std::cout << "edge: generic" << std::endl; }
    248357    typedef _Graph1 Graph1;
    249358    typedef _Graph2 Graph2;
     
    264373    class Edge : public Graph1Edge, public Graph2Edge {
    265374      friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
    266       template <typename Value> friend class EdgeMap;
     375      template <typename _Value> friend class EdgeMap;
    267376    protected:
    268377      bool backward; //true, iff backward
     
    277386      Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
    278387      bool operator==(const Edge& v) const {
    279         return (this->backward==v.backward &&
    280                 static_cast<Graph1Edge>(*this)==
    281                 static_cast<Graph1Edge>(v) &&
    282                 static_cast<Graph2Edge>(*this)==
    283                 static_cast<Graph2Edge>(v));
     388        if (backward)
     389          return (v.backward &&
     390                  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
     391        else
     392          return (!v.backward &&
     393                  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
    284394      }
    285395      bool operator!=(const Edge& v) const {
    286         return (this->backward!=v.backward ||
    287                 static_cast<Graph1Edge>(*this)!=
    288                 static_cast<Graph1Edge>(v) ||
    289                 static_cast<Graph2Edge>(*this)!=
    290                 static_cast<Graph2Edge>(v));
     396        return !(*this==v);
    291397      }
    292398    };
     
    382488
    383489    template <typename _Value>
    384     class EdgeMap : public Parent1::template EdgeMap<_Value>,
    385                     public Parent2::template EdgeMap<_Value> {
    386       typedef typename Parent1::template EdgeMap<_Value> ParentMap1;
    387       typedef typename Parent2::template EdgeMap<_Value> ParentMap2;
     490    class EdgeMap {
     491    protected:
     492      typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
     493      typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
     494      ParentMap1 forward_map;
     495      ParentMap2 backward_map;
    388496    public:
    389497      typedef _Value Value;
    390498      typedef Edge Key;
    391499      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
    392         ParentMap1(gw), ParentMap2(gw) { }
     500        forward_map(*(gw.Parent1::graph)),
     501        backward_map(*(gw.Parent2::graph)) { }
    393502      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
    394503              const _Value& value) :
    395         ParentMap1(gw, value), ParentMap2(gw, value) { }
     504        forward_map(*(gw.Parent1::graph), value),
     505        backward_map(*(gw.Parent2::graph), value) { }
    396506      _Value operator[](const Edge& n) const {
    397507        if (!n.backward)
    398           return ParentMap1::operator[](n);
    399         else
    400           return ParentMap2::operator[](n);
     508          return forward_map[n];
     509        else
     510          return backward_map[n];
    401511      }
    402512      void set(const Edge& n, const _Value& value) {
    403513        if (!n.backward)
    404           ParentMap1::set(n, value);
    405         else
    406           ParentMap2::set(n, value);
     514          forward_map.set(n, value);
     515        else
     516          backward_map.set(n, value);
    407517      }
    408518//       using ParentMap1::operator[];
     
    413523
    414524
     525  /*! A graph wrapper base class
     526    for merging the node-sets and edge-sets of
     527    two node-disjoint graphs
     528    into one graph.
     529    Specialization for the case when _Graph1::Edge and _Graph2::Edge
     530    are the same.
     531   */
     532  template <typename _Graph1, typename _Graph2>
     533  class MergeEdgeGraphWrapperBase<
     534    _Graph1, _Graph2, typename boost::enable_if<
     535    boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
     536    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
     537  public:
     538    static void printEdge() { std::cout << "edge: same" << std::endl; }
     539    typedef _Graph1 Graph1;
     540    typedef _Graph2 Graph2;
     541    typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
     542    typedef typename Parent::Parent1 Parent1;
     543    typedef typename Parent::Parent2 Parent2;
     544//     typedef P1<_Graph1> Parent1;
     545//     typedef P2<_Graph2> Parent2;
     546    typedef typename Parent1::Edge Graph1Edge;
     547    typedef typename Parent2::Edge Graph2Edge;
     548  protected:
     549    MergeEdgeGraphWrapperBase() { }
     550  public:
     551    template <typename _Value> class EdgeMap;
     552
     553    typedef typename Parent::Node Node;
     554
     555    class Edge : public Graph1Edge {
     556      friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
     557      template <typename _Value> friend class EdgeMap;
     558    protected:
     559      bool backward; //true, iff backward
     560    public:
     561      Edge() { }
     562      /// \todo =false is needed, or causes problems?
     563      /// If \c _backward is false, then we get an edge corresponding to the
     564      /// original one, otherwise its oppositely directed pair is obtained.
     565      Edge(const Graph1Edge& n1,
     566           const Graph2Edge& n2, bool _backward) :
     567        Graph1Edge(!backward ? n1 : n2), backward(_backward) { }
     568      Edge(Invalid i) : Graph1Edge(i), backward(true) { }
     569      bool operator==(const Edge& v) const {
     570        return (backward==v.backward &&
     571                static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
     572      }
     573      bool operator!=(const Edge& v) const {
     574        return !(*this==v);
     575      }
     576    };
     577
     578    using Parent::first;
     579    void first(Edge& i) const {
     580      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
     581      i.backward=false;
     582      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     583        Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
     584        i.backward=true;
     585      }
     586    }
     587    void firstIn(Edge& i, const Node& n) const {
     588      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
     589      i.backward=false;
     590      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     591        Parent2::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
     592        i.backward=true;
     593      }
     594    }
     595    void firstOut(Edge& i, const Node& n) const {
     596      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
     597      i.backward=false;
     598      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     599        Parent2::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
     600        i.backward=true;
     601      }
     602    }
     603
     604    using Parent::next;
     605    void next(Edge& i) const {
     606      if (!(i.backward)) {
     607        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
     608        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     609          Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
     610          i.backward=true;
     611        }
     612      } else {
     613        Parent2::graph->next(*static_cast<Graph1Edge*>(&i));
     614      }
     615    }
     616    void nextIn(Edge& i) const {
     617      if (!(i.backward)) {
     618        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
     619        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     620          Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
     621          i.backward=true;
     622        }
     623      } else {
     624        Parent2::graph->nextIn(*static_cast<Graph1Edge*>(&i));
     625      }
     626    }
     627    void nextOut(Edge& i) const {
     628      if (!(i.backward)) {
     629        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
     630        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     631          Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
     632          i.backward=true;
     633        }
     634      } else {
     635        Parent2::graph->nextOut(*static_cast<Graph1Edge*>(&i));
     636      }
     637    }
     638
     639    Node source(const Edge& i) const {
     640      if (!(i.backward)) {
     641        return
     642          Node(Parent1::graph->source(i), INVALID, false);
     643      } else {
     644        return
     645          Node(INVALID, Parent2::graph->source(i), true);
     646      }
     647    }
     648
     649    Node target(const Edge& i) const {
     650      if (!(i.backward)) {
     651        return
     652          Node(Parent1::graph->target(i), INVALID, false);
     653      } else {
     654        return
     655          Node(INVALID, Parent2::graph->target(i), true);
     656      }
     657    }
     658
     659    using Parent::id;
     660    int id(const Edge& n) const {
     661      if (!n.backward)
     662        return this->Parent1::graph->id(n);
     663      else
     664        return this->Parent2::graph->id(n);
     665    }
     666
     667    template <typename _Value>
     668    class EdgeMap {
     669    protected:
     670      typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
     671      typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
     672      ParentMap1 forward_map;
     673      ParentMap2 backward_map;
     674    public:
     675      typedef _Value Value;
     676      typedef Edge Key;
     677      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
     678        forward_map(*(gw.Parent1::graph)),
     679        backward_map(*(gw.Parent2::graph)) { }
     680      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
     681              const _Value& value) :
     682        forward_map(*(gw.Parent1::graph), value),
     683        backward_map(*(gw.Parent2::graph), value) { }
     684      _Value operator[](const Edge& n) const {
     685        if (!n.backward)
     686          return forward_map[n];
     687        else
     688          return backward_map[n];
     689      }
     690      void set(const Edge& n, const _Value& value) {
     691        if (!n.backward)
     692          forward_map.set(n, value);
     693        else
     694          backward_map.set(n, value);
     695      }
     696//       using ParentMap1::operator[];
     697//       using ParentMap2::operator[];
     698    };
     699
     700  };
     701
     702
     703  /*! A graph wrapper class
     704    for merging the node-sets and edge-sets of
     705    two node-disjoint graphs
     706    into one graph.
     707   */
    415708  template <typename _Graph1, typename _Graph2>
    416709  class MergeEdgeGraphWrapper : public
     
    431724
    432725 
     726  /*! A graph wrapper base class for the following functionality.
     727    If a bijection is given between the node-sets of two graphs,
     728    then the second one can be considered as a new edge-set
     729    over th first node-set.
     730   */
    433731  template <typename _Graph, typename _EdgeSetGraph>
    434732  class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
     
    508806    bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
    509807
    510     using Parent::id;
     808    int id(const Node& e) const { return Parent::id(e); }
    511809    int id(const Edge& e) const { return edge_set_graph->id(e); }
    512810   
     
    527825  };
    528826
     827
     828  /*! A graph wrapper class for the following functionality.
     829    If a bijection is given between the node-sets of two graphs,
     830    then the second one can be considered as a new edge-set
     831    over th first node-set.
     832   */
    529833  template <typename _Graph, typename _EdgeSetGraph>
    530834  class NewEdgeSetGraphWrapper :
     
    552856  };
    553857
     858
     859  /*! A graph wrapper base class
     860    for merging graphs of type _Graph1 and _Graph2
     861    which are given on the same node-set
     862    (specially on the node-set of Graph1)
     863    into one graph.
     864    In an other point of view, _Graph1 is extended with
     865    the edge-set of _Graph2.
     866   */
     867  template <typename _Graph1, typename _Graph2, typename Enable=void>
     868  class AugmentingGraphWrapperBase :
     869    public P1<_Graph1> {
     870  public:
     871    void printAugment() const { std::cout << "generic" << std::endl; }
     872    typedef _Graph1 Graph1;
     873    typedef _Graph2 Graph2;
     874    typedef P1<_Graph1> Parent1;
     875    typedef P2<_Graph2> Parent2;
     876    typedef typename Parent1::Edge Graph1Edge;
     877    typedef typename Parent2::Edge Graph2Edge;
     878  protected:
     879    AugmentingGraphWrapperBase() { }
     880    _Graph2* graph2;
     881    void setGraph2(_Graph2& _graph2) { graph2=&_graph2; }
     882  public:
     883   
     884    template <typename _Value> class EdgeMap;
     885
     886    typedef typename Parent1::Node Node;
     887
     888    class Edge : public Graph1Edge, public Graph2Edge {
     889      friend class AugmentingGraphWrapperBase<_Graph1, _Graph2>;
     890      template <typename _Value> friend class EdgeMap;
     891    protected:
     892      bool backward; //true, iff backward
     893    public:
     894      Edge() { }
     895      /// \todo =false is needed, or causes problems?
     896      /// If \c _backward is false, then we get an edge corresponding to the
     897      /// original one, otherwise its oppositely directed pair is obtained.
     898      Edge(const Graph1Edge& n1,
     899           const Graph2Edge& n2, bool _backward) :
     900        Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
     901      Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
     902      bool operator==(const Edge& v) const {
     903        if (backward)
     904          return (v.backward &&
     905                  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
     906        else
     907          return (!v.backward &&
     908                  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
     909      }
     910      bool operator!=(const Edge& v) const {
     911        return !(*this==v);
     912      }
     913    };
     914
     915    using Parent1::first;
     916    void first(Edge& i) const {
     917      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
     918      i.backward=false;
     919      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     920        graph2->first(*static_cast<Graph2Edge*>(&i));
     921        i.backward=true;
     922      }
     923    }
     924    void firstIn(Edge& i, const Node& n) const {
     925      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
     926      i.backward=false;
     927      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     928        graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
     929        i.backward=true;
     930      }
     931    }
     932    void firstOut(Edge& i, const Node& n) const {
     933      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
     934      i.backward=false;
     935      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     936        graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
     937        i.backward=true;
     938      }
     939    }
     940
     941    using Parent1::next;
     942    void next(Edge& i) const {
     943      if (!(i.backward)) {
     944        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
     945        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     946          graph2->first(*static_cast<Graph2Edge*>(&i));
     947          i.backward=true;
     948        }
     949      } else {
     950        graph2->next(*static_cast<Graph2Edge*>(&i));
     951      }
     952    }
     953    void nextIn(Edge& i) const {
     954      if (!(i.backward)) {
     955        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
     956        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     957          graph2->first(*static_cast<Graph2Edge*>(&i));
     958          i.backward=true;
     959        }
     960      } else {
     961        graph2->nextIn(*static_cast<Graph2Edge*>(&i));
     962      }
     963    }
     964    void nextOut(Edge& i) const {
     965      if (!(i.backward)) {
     966        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
     967        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     968          graph2->first(*static_cast<Graph2Edge*>(&i));
     969          i.backward=true;
     970        }
     971      } else {
     972        graph2->nextOut(*static_cast<Graph2Edge*>(&i));
     973      }
     974    }
     975
     976    Node source(const Edge& i) const {
     977      if (!(i.backward)) {
     978        return Parent1::graph->source(i);
     979      } else {
     980        return graph2->source(i);
     981      }
     982    }
     983
     984    Node target(const Edge& i) const {
     985      if (!(i.backward)) {
     986        return Parent1::graph->target(i);
     987      } else {
     988        return graph2->target(i);
     989      }
     990    }
     991
     992    int id(const Node& n) const {
     993      return Parent1::id(n);
     994    };
     995    int id(const Edge& n) const {
     996      if (!n.backward)
     997        return this->Parent1::graph->id(n);
     998      else
     999        return this->graph2->id(n);
     1000    }
     1001
     1002    template <typename _Value>
     1003    class EdgeMap {
     1004    protected:
     1005      typedef typename _Graph1::template EdgeMap<_Value> ParentMap1;
     1006      typedef typename _Graph2::template EdgeMap<_Value> ParentMap2;
     1007      ParentMap1 forward_map;
     1008      ParentMap2 backward_map;
     1009    public:
     1010      typedef _Value Value;
     1011      typedef Edge Key;
     1012      EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw) :
     1013        forward_map(*(gw.Parent1::graph)),
     1014        backward_map(*(gw.graph2)) { }
     1015      EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw,
     1016              const _Value& value) :
     1017        forward_map(*(gw.Parent1::graph), value),
     1018        backward_map(*(gw.graph2), value) { }
     1019      _Value operator[](const Edge& n) const {
     1020        if (!n.backward)
     1021          return forward_map[n];
     1022        else
     1023          return backward_map[n];
     1024      }
     1025      void set(const Edge& n, const _Value& value) {
     1026        if (!n.backward)
     1027          forward_map.set(n, value);
     1028        else
     1029          backward_map.set(n, value);
     1030      }
     1031//       using ParentMap1::operator[];
     1032//       using ParentMap2::operator[];
     1033    };
     1034
     1035  };
     1036
     1037
     1038  /*! A graph wrapper class
     1039    for merging two graphs (of type _Graph1 and _Graph2)
     1040    with the same node-set
     1041    (specially on the node-set of Graph1)
     1042    into one graph.
     1043    In an other point of view, _Graph1 is extended with
     1044    the edge-set of _Graph2.
     1045   */ 
     1046  template <typename _Graph1, typename _Graph2>
     1047  class AugmentingGraphWrapper : public
     1048  IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > {
     1049  public:
     1050    typedef
     1051    IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> >
     1052    Parent;
     1053    typedef _Graph1 Graph1;
     1054    typedef _Graph2 Graph2;
     1055  protected:
     1056    AugmentingGraphWrapper() { }
     1057  public:
     1058    AugmentingGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
     1059      setGraph(_graph1);
     1060      setGraph2(_graph2);
     1061    }
     1062  };
     1063
    5541064} //namespace lemon
    5551065
  • src/work/marci/merge_node_graph_wrapper_test.cc

    r1009 r1013  
    55#include <lemon/smart_graph.h>
    66#include <lemon/dimacs.h>
     7#include <lemon/full_graph.h>
    78#include <merge_node_graph_wrapper.h>
    89
     
    2223};
    2324
    24 int main() {
    25   typedef SmartGraph Graph1;
    26   typedef ListGraph Graph2;
    27  
    28   {
    29     checkConcept<StaticGraph, NewEdgeSetGraphWrapper<Graph1, Graph2> >();
    30   }
    31   {
    32     checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >();
    33   }
    34  
    35   Graph1 g;
    36   Graph2 h;
    37   typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
    38   GW gw(g, h);
    39 
    40   std::ifstream f1("graph1.dim");
    41   std::ifstream f2("graph2.dim");
    42   readDimacs(f1, g);
    43   readDimacs(f2, h);
    44   {
    45 
    46 //   Graph1::Node n1=g.addNode();
    47 //   Graph1::Node n2=g.addNode();
    48 //   Graph1::Node n3=g.addNode();
    49 //   Graph2::Node n4=h.addNode();
    50 //   Graph2::Node n5=h.addNode();
    51 //   Graph2::Node n6=h.addNode();
    52 //   Graph1::Edge e1=g.addEdge(n1, n2);
    53 //   Graph1::Edge e2=g.addEdge(n1, n3);
    54 //   Graph2::Edge e3=h.addEdge(n4, n5);
    55 //   Graph2::Edge e4=h.addEdge(n4, n5);
    56   //GW::NodeIt n(gw)
    57   cout << "1st graph" << endl;
     25template <typename Graph>
     26void printGraph(const Graph& g) {
    5827  cout << " nodes:" << endl;
    59   for (Graph1::NodeIt n(g); n!=INVALID; ++n) {
     28  for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
    6029    cout << "  " << g.id(n) << endl;
    6130  }
    6231  cout << " edges:" << endl;
    63   for (Graph1::EdgeIt n(g); n!=INVALID; ++n) {
     32  for (typename Graph::EdgeIt n(g); n!=INVALID; ++n) {
    6433    cout << "  " << g.id(n) << ": "
    6534         << g.id(g.source(n)) << "->" << g.id(g.target(n)) << endl;
    66   }
    67   cout << "2nd graph" << endl;
    68   cout << " nodes:" << endl;
    69   for (Graph2::NodeIt n(h); n!=INVALID; ++n) {
    70     cout << "  " << h.id(n) << endl;
    71   }
    72   cout << " edges:" << endl;
    73   for (Graph2::EdgeIt n(h); n!=INVALID; ++n) {
    74     cout << "  " << h.id(n) << ": "
    75          << h.id(h.source(n)) << "->" << h.id(h.target(n)) << endl;
    76   }
    77   cout << "merged graph" << endl;
    78   cout << " nodes:" << endl;
    79   for (GW::NodeIt n(gw); n!=INVALID; ++n) {
    80     cout << "  "<< gw.id(n) << endl;
    81   }
    82   cout << " edges:" << endl;
    83   for (GW::EdgeIt n(gw); n!=INVALID; ++n) {
    84     cout << "  " << gw.id(n) << ": "
    85          << gw.id(gw.source(n)) << "->" << gw.id(gw.target(n)) << endl;
     35  } 
     36}
     37
     38int main() {
     39  {
     40    cout << "FIRST TEST" << endl;
     41    typedef SmartGraph Graph1;
     42    typedef ListGraph Graph2;
     43   
     44    {
     45      checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >();   
     46      MergeEdgeGraphWrapper<Graph1, Graph2>::printNode();
     47      MergeEdgeGraphWrapper<Graph1, Graph2>::printEdge();
     48      checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph1> >();   
     49      MergeEdgeGraphWrapper<Graph1, Graph1>::printNode();
     50      MergeEdgeGraphWrapper<Graph1, Graph1>::printEdge();
     51    }
     52 
     53    Graph1 g1;
     54    Graph2 g2;
     55    typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
     56    GW gw(g1, g2);
     57
     58    std::ifstream f1("graph1.dim");
     59    std::ifstream f2("graph2.dim");
     60    readDimacs(f1, g1);
     61    readDimacs(f2, g2);
     62   
     63    cout << "1st graph" << endl;
     64    printGraph(g1);
     65
     66    cout << "2nd graph" << endl;
     67    printGraph(g2);
     68
     69    cout << "merged graph" << endl;
     70    printGraph(gw);
     71
    8672  }
    8773
    88   GW::NodeMap<int> nm(gw);
    89   int i=0;
    90   for (GW::NodeIt n(gw); n!=INVALID; ++n) {
    91     ++i;
    92     nm.set(n, i);
    93   }
    94   for (Graph1::NodeIt n(g); n!=INVALID; ++n) {
    95     cout << nm[GW::Node(n,INVALID,false)] << endl;
    96   }
    97   for (Graph2::NodeIt n(h); n!=INVALID; ++n) {
    98     cout << nm[GW::Node(INVALID,n,true)] << endl;
     74
     75  {
     76    cout << "SECOND TEST" << endl;
     77    typedef SmartGraph Graph1;
     78    {
     79      checkConcept<StaticGraph, Graph1>();
     80    }
     81
     82    Graph1 g1;
     83
     84    FullGraph pre_g2(2);
     85    ConstMap<FullGraph::Edge, bool> const_false_map(false);
     86    typedef EdgeSubGraphWrapper<FullGraph, ConstMap<FullGraph::Edge, bool> >
     87      Graph2;
     88    {
     89      checkConcept<StaticGraph, Graph2>();
     90    }
     91
     92    Graph2 g2(pre_g2, const_false_map);
     93
     94    typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
     95    {
     96      checkConcept<StaticGraph, GW>();   
     97    }
     98    GW gw(g1, g2);
     99    GW::Node sw;
     100    GW::Node tw;
     101    {
     102      Graph2::NodeIt k(g2);
     103      sw=GW::Node(INVALID, k, true);
     104      ++k;
     105      tw=GW::Node(INVALID, k, true);
     106    }
     107
     108    std::ifstream f1("graph2.dim");
     109    readDimacs(f1, g1);
     110
     111    cout << "1st graph" << endl;
     112    printGraph(g1);
     113
     114    cout << "2nd graph" << endl;
     115    printGraph(g2);
     116
     117    cout << "merged graph" << endl;
     118    printGraph(gw);
     119
     120    typedef ListGraph Graph3;
     121    Graph3 g3;
     122    GW::NodeMap<Graph3::Node> gwn(gw);
     123    Graph3::NodeMap<GW::Node> g3n(g3);
     124    for (GW::NodeIt n(gw); n!=INVALID; ++n) {
     125      Graph3::Node m=g3.addNode();
     126      gwn.set(n, m);
     127      g3n.set(m, n);
     128    }
     129
     130    typedef NewEdgeSetGraphWrapper<GW, Graph3> GWW;
     131    {
     132      checkConcept<StaticGraph, GWW>();   
     133    }
     134
     135    GWW gww(gw, g3, gwn, g3n);
     136
     137    for (Graph1::NodeIt n(g1); n!=INVALID; ++n) {
     138      g3.addEdge(gwn[sw], gwn[GW::Node(n,INVALID,false)]);
     139    }
     140
     141//     for (Graph1::NodeIt n(g1); n!=INVALID; ++n) {
     142//       gww.addEdge(sw, GW::Node(n,INVALID,false));
     143//     }
     144
     145    cout << "new edges" << endl;
     146    printGraph(g3);
     147
     148    cout << "new edges in the new graph" << endl;
     149    printGraph(gww);
     150
     151    typedef AugmentingGraphWrapper<GW, GWW> GWWW;
     152    {
     153      checkConcept<StaticGraph, GWWW>();   
     154    }
     155    GWWW gwww(gw, gww);
     156
     157    cout << "new edges merged into the original graph" << endl;
     158    printGraph(gwww);
     159
    99160  }
    100161
    101   gw.printNode();
    102 
    103   {
    104 //    typedef SmartGraph Graph1;
    105     typedef ListGraph Graph1;
    106     typedef ListGraph Graph2;
    107     Graph1 g;
    108     Graph2 h;
    109     typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
    110     GW gw(g, h);   
    111     gw.printNode();
    112   }
    113   {
    114 //    typedef SmartGraph Graph1;
    115     typedef Graph3 Graph1;
    116     typedef ListGraph Graph2;
    117     Graph1 g;
    118     Graph2 h;
    119     typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
    120     GW gw(g, h);   
    121     gw.printNode();
    122   }
    123   {
    124 //    typedef SmartGraph Graph1;
    125     typedef ListGraph Graph1;
    126     typedef Graph3 Graph2;
    127     Graph1 g;
    128     Graph2 h;
    129     typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
    130     GW gw(g, h);   
    131     gw.printNode();
    132   }
    133   }
    134   {
    135     Graph1 g;
    136     Graph2 h;
    137     typedef Graph1::Node Node1;
    138     typedef Graph2::Node Node2;
    139     typedef NewEdgeSetGraphWrapper<Graph1, Graph2> GW;
    140     Graph1::NodeMap<Graph2::Node> e_node(g);
    141     Graph2::NodeMap<Graph1::Node> n_node(h);
    142     GW gw(g, h, e_node, n_node);
    143     for (int i=0; i<4; ++i) {
    144       Node1 n=g.addNode();
    145       e_node.set(n, INVALID);
    146     }
    147     for (int i=0; i<4; ++i) {
    148       Graph1::Node n1=g.addNode();
    149       Graph2::Node n2=h.addNode();
    150       e_node.set(n1, n2);
    151       n_node.set(n2, n1);
    152     }
    153     for (Graph2::NodeIt n(h); n!=INVALID; ++n)
    154       for (Graph2::NodeIt m(h); m!=INVALID; ++m)
    155         if ((h.id(n)+h.id(m))%3==0) h.addEdge(n, m);
    156 //     Graph1::NodeIt n(g);
    157 //     Node1 n1=n;
    158 //     Node1 n2=++n;
    159 //     Node1 n3=++n;
    160 //     Node1 n4=n;
    161 //     gw.addEdge(n1, n2);
    162 //     gw.addEdge(n1, n2);
    163 //     for (EdgeIt(e))
    164 //   Graph1::Node n1=g.addNode();
    165 //   Graph1::Node n2=g.addNode();
    166 //   Graph1::Node n3=g.addNode();
    167 //   Graph2::Node n4=h.addNode();
    168 //   Graph2::Node n5=h.addNode();
    169     for (GW::EdgeIt e(gw); e!=INVALID; ++e)
    170       cout << gw.id(e) << endl;
    171     for (GW::NodeIt n(gw); n!=INVALID; ++n) {
    172       if (e_node[n]==INVALID) {
    173         cout<<gw.id(n)<<" INVALID"<<endl;
    174       } else {
    175         cout <<gw.id(n)<<" "<<h.id(e_node[n])<<" out_edges: ";
    176         //      cout << &e_node << endl;
    177         //cout << &n_node << endl;
    178         for (GW::OutEdgeIt e(gw, n); e!=INVALID; ++e) {
    179           cout<<gw.id(e)<<" ";
    180         }
    181         cout<< endl;
    182       }
    183     }
    184   }
    185162}
Note: See TracChangeset for help on using the changeset viewer.