COIN-OR::LEMON - Graph Library

Changeset 1009:8cb323dbae93 in lemon-0.x


Ignore:
Timestamp:
11/19/04 18:22:29 (19 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1399
Message:

RoadMap? to STGraphWrapper

Location:
src/work/marci
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/merge_node_graph_wrapper.h

    r1008 r1009  
    3939  };
    4040
     41  /*! A base class for merging the node-set of two node-disjoint graphs
     42    into the node-set of one graph.
     43   */
    4144  template <typename _Graph1, typename _Graph2, typename Enable=void>
    4245  class MergeNodeGraphWrapperBase :
    4346    public P1<_Graph1>, public P2<_Graph2> {
    4447  public:
    45     void print() const { std::cout << "generic" << std::endl; }
     48    void printNode() const { std::cout << "generic" << std::endl; }
    4649    typedef _Graph1 Graph1;
    4750    typedef _Graph2 Graph2;
     
    140143          ParentMap2::set(n, value);
    141144      }
    142       using ParentMap1::operator[];
    143       using ParentMap2::operator[];
     145//       using ParentMap1::operator[];
     146//       using ParentMap2::operator[];
    144147    };
    145148
     
    153156    public P1<_Graph1>, public P2<_Graph2> {
    154157  public :
    155     void print() const { std::cout << "same" << std::endl; }
     158    void printNode() const { std::cout << "same" << std::endl; }
    156159    typedef _Graph1 Graph1;
    157160    typedef _Graph2 Graph2;
     
    176179    public P1<_Graph1>, public P2<_Graph2> {
    177180  public :
    178     void print() const { std::cout << "2. nagyobb" << std::endl; }
     181    void printNode() const { std::cout << "2. nagyobb" << std::endl; }
    179182    typedef _Graph1 Graph1;
    180183    typedef _Graph2 Graph2;
     
    199202    public P1<_Graph1>, public P2<_Graph2> {
    200203  public :
    201     void print() const { std::cout << "1. nagyobb" << std::endl; }
     204    void printNode() const { std::cout << "1. nagyobb" << std::endl; }
    202205    typedef _Graph1 Graph1;
    203206    typedef _Graph2 Graph2;
     
    216219
    217220
     221  template <typename _Graph1, typename _Graph2>
     222  class MergeNodeGraphWrapper : public
     223  IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
     224  public:
     225    typedef _Graph1 Graph1;
     226    typedef _Graph2 Graph2;
     227    typedef IterableGraphExtender<
     228      MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
     229  protected:
     230    MergeNodeGraphWrapper() { }
     231  public:
     232    MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
     233      Parent::Parent1::setGraph(_graph1);
     234      Parent::Parent2::setGraph(_graph2);
     235    }
     236  };
     237
     238
     239  /*! A base class for merging the node-sets and edge-sets of
     240    two node-disjoint graphs
     241    into one graph.
     242   */
    218243  template <typename _Graph1, typename _Graph2, typename Enable=void>
    219   class MergeNodeGraphWrapper : public
    220   IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2, Enable> > {
     244  class MergeEdgeGraphWrapperBase :
     245    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
     246  public:
     247    void printEdge() const { std::cout << "generic" << std::endl; }
     248    typedef _Graph1 Graph1;
     249    typedef _Graph2 Graph2;
     250    typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
     251    typedef typename Parent::Parent1 Parent1;
     252    typedef typename Parent::Parent2 Parent2;
     253//     typedef P1<_Graph1> Parent1;
     254//     typedef P2<_Graph2> Parent2;
     255    typedef typename Parent1::Edge Graph1Edge;
     256    typedef typename Parent2::Edge Graph2Edge;
     257  protected:
     258    MergeEdgeGraphWrapperBase() { }
     259  public:
     260    template <typename _Value> class EdgeMap;
     261
     262    typedef typename Parent::Node Node;
     263
     264    class Edge : public Graph1Edge, public Graph2Edge {
     265      friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
     266      template <typename Value> friend class EdgeMap;
     267    protected:
     268      bool backward; //true, iff backward
     269    public:
     270      Edge() { }
     271      /// \todo =false is needed, or causes problems?
     272      /// If \c _backward is false, then we get an edge corresponding to the
     273      /// original one, otherwise its oppositely directed pair is obtained.
     274      Edge(const Graph1Edge& n1,
     275           const Graph2Edge& n2, bool _backward) :
     276        Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
     277      Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
     278      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));
     284      }
     285      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));
     291      }
     292    };
     293
     294    using Parent::first;
     295    void first(Edge& i) const {
     296      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
     297      i.backward=false;
     298      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     299        Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
     300        i.backward=true;
     301      }
     302    }
     303    void firstIn(Edge& i, const Node& n) const {
     304      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
     305      i.backward=false;
     306      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     307        Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
     308        i.backward=true;
     309      }
     310    }
     311    void firstOut(Edge& i, const Node& n) const {
     312      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
     313      i.backward=false;
     314      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     315        Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
     316        i.backward=true;
     317      }
     318    }
     319
     320    using Parent::next;
     321    void next(Edge& i) const {
     322      if (!(i.backward)) {
     323        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
     324        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     325          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
     326          i.backward=true;
     327        }
     328      } else {
     329        Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
     330      }
     331    }
     332    void nextIn(Edge& i) const {
     333      if (!(i.backward)) {
     334        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
     335        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     336          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
     337          i.backward=true;
     338        }
     339      } else {
     340        Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
     341      }
     342    }
     343    void nextOut(Edge& i) const {
     344      if (!(i.backward)) {
     345        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
     346        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     347          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
     348          i.backward=true;
     349        }
     350      } else {
     351        Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
     352      }
     353    }
     354
     355    Node source(const Edge& i) const {
     356      if (!(i.backward)) {
     357        return
     358          Node(Parent1::graph->source(i), INVALID, false);
     359      } else {
     360        return
     361          Node(INVALID, Parent2::graph->source(i), true);
     362      }
     363    }
     364
     365    Node target(const Edge& i) const {
     366      if (!(i.backward)) {
     367        return
     368          Node(Parent1::graph->target(i), INVALID, false);
     369      } else {
     370        return
     371          Node(INVALID, Parent2::graph->target(i), true);
     372      }
     373    }
     374
     375    using Parent::id;
     376    int id(const Edge& n) const {
     377      if (!n.backward)
     378        return this->Parent1::graph->id(n);
     379      else
     380        return this->Parent2::graph->id(n);
     381    }
     382
     383    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;
     388    public:
     389      typedef _Value Value;
     390      typedef Edge Key;
     391      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
     392        ParentMap1(gw), ParentMap2(gw) { }
     393      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
     394              const _Value& value) :
     395        ParentMap1(gw, value), ParentMap2(gw, value) { }
     396      _Value operator[](const Edge& n) const {
     397        if (!n.backward)
     398          return ParentMap1::operator[](n);
     399        else
     400          return ParentMap2::operator[](n);
     401      }
     402      void set(const Edge& n, const _Value& value) {
     403        if (!n.backward)
     404          ParentMap1::set(n, value);
     405        else
     406          ParentMap2::set(n, value);
     407      }
     408//       using ParentMap1::operator[];
     409//       using ParentMap2::operator[];
     410    };
     411
     412  };
     413
     414
     415  template <typename _Graph1, typename _Graph2>
     416  class MergeEdgeGraphWrapper : public
     417  IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
    221418  public:
    222419    typedef _Graph1 Graph1;
    223420    typedef _Graph2 Graph2;
    224421    typedef IterableGraphExtender<
    225       MergeNodeGraphWrapperBase<_Graph1, _Graph2, Enable> > Parent;
    226   protected:
    227     MergeNodeGraphWrapper() { }
    228   public:
    229     MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
     422      MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
     423  protected:
     424    MergeEdgeGraphWrapper() { }
     425  public:
     426    MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
    230427      Parent::Parent1::setGraph(_graph1);
    231428      Parent::Parent2::setGraph(_graph2);
  • src/work/marci/merge_node_graph_wrapper_test.cc

    r1008 r1009  
    11#include <iostream>
     2#include <fstream>
    23
    34#include <lemon/list_graph.h>
    45#include <lemon/smart_graph.h>
     6#include <lemon/dimacs.h>
    57#include <merge_node_graph_wrapper.h>
    68
     
    2426  typedef ListGraph Graph2;
    2527 
    26 //   {
    27 //     checkConcept<StaticGraph, NewEdgeSetGraphWrapper<Graph1, Graph2> >();
    28 //   }
    2928  {
     29    checkConcept<StaticGraph, NewEdgeSetGraphWrapper<Graph1, Graph2> >();
     30  }
     31  {
     32    checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >();
     33  }
     34 
    3035  Graph1 g;
    3136  Graph2 h;
    32   typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
     37  typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
    3338  GW gw(g, h);
    34   Graph1::Node n1=g.addNode();
    35   Graph1::Node n2=g.addNode();
    36   Graph1::Node n3=g.addNode();
    37   Graph2::Node n4=h.addNode();
    38   Graph2::Node n5=h.addNode();
     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);
    3956  //GW::NodeIt n(gw)
     57  cout << "1st graph" << endl;
     58  cout << " nodes:" << endl;
     59  for (Graph1::NodeIt n(g); n!=INVALID; ++n) {
     60    cout << "  " << g.id(n) << endl;
     61  }
     62  cout << " edges:" << endl;
     63  for (Graph1::EdgeIt n(g); n!=INVALID; ++n) {
     64    cout << "  " << g.id(n) << ": "
     65         << 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;
    4079  for (GW::NodeIt n(gw); n!=INVALID; ++n) {
    41     cout << gw.id(n) << endl;
     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;
    4286  }
    4387
     
    4993  }
    5094  for (Graph1::NodeIt n(g); n!=INVALID; ++n) {
    51     cout << nm[n] << endl;
     95    cout << nm[GW::Node(n,INVALID,false)] << endl;
    5296  }
    5397  for (Graph2::NodeIt n(h); n!=INVALID; ++n) {
    54     cout << nm[n] << endl;
     98    cout << nm[GW::Node(INVALID,n,true)] << endl;
    5599  }
    56100
    57   gw.print();
     101  gw.printNode();
    58102
    59103  {
     
    65109    typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
    66110    GW gw(g, h);   
    67     gw.print();
     111    gw.printNode();
    68112  }
    69113  {
     
    75119    typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
    76120    GW gw(g, h);   
    77     gw.print();
     121    gw.printNode();
    78122  }
    79123  {
     
    85129    typedef MergeNodeGraphWrapper<Graph1, Graph2> GW;
    86130    GW gw(g, h);   
    87     gw.print();
     131    gw.printNode();
    88132  }
    89133  }
Note: See TracChangeset for help on using the changeset viewer.