src/work/marci/merge_node_graph_wrapper.h
author alpar
Sat, 20 Nov 2004 10:19:06 +0000 (2004-11-20)
changeset 1011 5bd6c7671c9e
parent 1008 3fef334f5f37
child 1013 b3bdd856faf4
permissions -rw-r--r--
- snapshot-rollback functionarity added to ListGraph
- The iterface of the snapshot-rollback functionarity in SmartGraph has
changed to be compatible with ListGraph::SnapShot.
     1 /* -*- C++ -*-
     2  * src/lemon/merge_node_graph_wrapper.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Combinatorial Optimization Research Group, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_MERGE_NODE_GRAPH_WRAPPER_H
    18 #define LEMON_MERGE_NODE_GRAPH_WRAPPER_H
    19 
    20 #include <lemon/invalid.h>
    21 #include <lemon/maps.h>
    22 #include <lemon/map_defines.h>
    23 #include <lemon/graph_wrapper.h>
    24 #include <iostream>
    25 using std::cout;
    26 using std::endl;
    27 
    28 #include <boost/type_traits.hpp>
    29 #include <boost/utility/enable_if.hpp>
    30 
    31 namespace lemon {
    32 
    33   template <class _Graph1>
    34   class P1 : public GraphWrapperBase<_Graph1> {
    35   };
    36 
    37   template <class _Graph2>
    38   class P2 : public GraphWrapperBase<_Graph2> {
    39   };
    40 
    41   /*! A base class for merging the node-set of two node-disjoint graphs 
    42     into the node-set of one graph.
    43    */
    44   template <typename _Graph1, typename _Graph2, typename Enable=void>
    45   class MergeNodeGraphWrapperBase : 
    46     public P1<_Graph1>, public P2<_Graph2> {
    47   public:
    48     void printNode() const { std::cout << "generic" << std::endl; }
    49     typedef _Graph1 Graph1;
    50     typedef _Graph2 Graph2;
    51     typedef P1<_Graph1> Parent1;
    52     typedef P2<_Graph2> Parent2;
    53     typedef typename Parent1::Node Graph1Node;
    54     typedef typename Parent2::Node Graph2Node;
    55   protected:
    56     MergeNodeGraphWrapperBase() { }
    57   public:
    58     template <typename _Value> class NodeMap;
    59 
    60     class Node : public Graph1Node, public Graph2Node {
    61       friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
    62       template <typename Value> friend class NodeMap;
    63     protected:
    64       bool backward; //true, iff backward
    65     public:
    66       Node() { }
    67       /// \todo =false is needed, or causes problems?
    68       /// If \c _backward is false, then we get an edge corresponding to the 
    69       /// original one, otherwise its oppositely directed pair is obtained.
    70       Node(const Graph1Node& n1, 
    71 	   const Graph2Node& n2, bool _backward) : 
    72 	Graph1Node(n1), Graph2Node(n2), backward(_backward) { }
    73       Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { }
    74       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));
    80       } 
    81       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       }
    88     };
    89 
    90     //typedef void Edge;
    91     class Edge { };
    92     
    93     void first(Node& i) const {
    94       Parent1::graph->first(*static_cast<Graph1Node*>(&i));
    95       i.backward=false;
    96       if (*static_cast<Graph1Node*>(&i)==INVALID) {
    97 	Parent2::graph->first(*static_cast<Graph2Node*>(&i));
    98 	i.backward=true;
    99       }
   100     }
   101     void next(Node& i) const {
   102       if (!(i.backward)) {
   103 	Parent1::graph->next(*static_cast<Graph1Node*>(&i));
   104 	if (*static_cast<Graph1Node*>(&i)==INVALID) {
   105 	  Parent2::graph->first(*static_cast<Graph2Node*>(&i));
   106 	  i.backward=true;
   107 	}
   108       } else {
   109 	Parent2::graph->next(*static_cast<Graph2Node*>(&i));
   110       }
   111     }
   112 
   113     int id(const Node& n) const { 
   114       if (!n.backward) 
   115 	return this->Parent1::graph->id(n);
   116       else
   117 	return this->Parent2::graph->id(n);
   118     }
   119 
   120     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;
   125     public:
   126       typedef _Value Value;
   127       typedef Node Key;
   128       NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) : 
   129 	ParentMap1(gw), ParentMap2(gw) { }
   130       NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw, 
   131 	      const _Value& value) : 
   132 	ParentMap1(gw, value), ParentMap2(gw, value) { }
   133       _Value operator[](const Node& n) const {
   134 	if (!n.backward) 
   135 	  return ParentMap1::operator[](n);
   136 	else 
   137 	  return ParentMap2::operator[](n);
   138       }
   139       void set(const Node& n, const _Value& value) {
   140 	if (!n.backward) 
   141 	  ParentMap1::set(n, value);
   142 	else 
   143 	  ParentMap2::set(n, value);
   144       }
   145 //       using ParentMap1::operator[];
   146 //       using ParentMap2::operator[];
   147     };
   148 
   149   };
   150 
   151   //not yet working
   152   template <typename _Graph1, typename _Graph2>
   153   class MergeNodeGraphWrapperBase<
   154     _Graph1, _Graph2, typename boost::enable_if<
   155     boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> : 
   156     public P1<_Graph1>, public P2<_Graph2> {
   157   public :
   158     void printNode() const { std::cout << "same" << std::endl; }
   159     typedef _Graph1 Graph1;
   160     typedef _Graph2 Graph2;
   161     typedef P1<_Graph1> Parent1;
   162     typedef P2<_Graph2> Parent2;
   163     typedef typename Parent1::Node Graph1Node;
   164     typedef typename Parent2::Node Graph2Node;
   165   protected:
   166     MergeNodeGraphWrapperBase() { }
   167   public:
   168     class Node { };
   169     class Edge { };
   170     void first() const;
   171     void next() const;
   172   };
   173 
   174   //not yet working
   175   template <typename _Graph1, typename _Graph2>
   176   class MergeNodeGraphWrapperBase<
   177     _Graph1, _Graph2, typename boost::enable_if<
   178     boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> : 
   179     public P1<_Graph1>, public P2<_Graph2> {
   180   public :
   181     void printNode() const { std::cout << "2. nagyobb" << std::endl; }
   182     typedef _Graph1 Graph1;
   183     typedef _Graph2 Graph2;
   184     typedef P1<_Graph1> Parent1;
   185     typedef P2<_Graph2> Parent2;
   186     typedef typename Parent1::Node Graph1Node;
   187     typedef typename Parent2::Node Graph2Node;
   188   protected:
   189     MergeNodeGraphWrapperBase() { }
   190   public:
   191     class Node { };
   192     class Edge { };
   193     void first() const;
   194     void next() const;
   195   };
   196 
   197   //not yet working
   198   template <typename _Graph1, typename _Graph2>
   199   class MergeNodeGraphWrapperBase<
   200     _Graph1, _Graph2, typename boost::enable_if<
   201     boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> : 
   202     public P1<_Graph1>, public P2<_Graph2> {
   203   public :
   204     void printNode() const { std::cout << "1. nagyobb" << std::endl; }
   205     typedef _Graph1 Graph1;
   206     typedef _Graph2 Graph2;
   207     typedef P1<_Graph1> Parent1;
   208     typedef P2<_Graph2> Parent2;
   209     typedef typename Parent1::Node Graph1Node;
   210     typedef typename Parent2::Node Graph2Node;
   211   protected:
   212     MergeNodeGraphWrapperBase() { }
   213   public:
   214     class Node { };
   215     class Edge { };
   216     void first() const;
   217     void next() const;
   218   };
   219 
   220 
   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    */
   243   template <typename _Graph1, typename _Graph2, typename Enable=void>
   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> > {
   418   public:
   419     typedef _Graph1 Graph1;
   420     typedef _Graph2 Graph2;
   421     typedef IterableGraphExtender<
   422       MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
   423   protected:
   424     MergeEdgeGraphWrapper() { }
   425   public:
   426     MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) { 
   427       Parent::Parent1::setGraph(_graph1);
   428       Parent::Parent2::setGraph(_graph2);
   429     }
   430   };
   431 
   432   
   433   template <typename _Graph, typename _EdgeSetGraph>
   434   class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
   435   public:
   436     typedef GraphWrapperBase<_Graph> Parent; 
   437     typedef _Graph Graph;
   438     typedef _EdgeSetGraph EdgeSetGraph;
   439     typedef typename _Graph::Node Node;
   440     typedef typename _EdgeSetGraph::Node ENode;
   441   protected:
   442     EdgeSetGraph* edge_set_graph;
   443     typename Graph::NodeMap<ENode>* e_node;
   444     typename EdgeSetGraph::NodeMap<Node>* n_node;
   445     void setEdgeSetGraph(EdgeSetGraph& _edge_set_graph) { 
   446       edge_set_graph=&_edge_set_graph; 
   447     }
   448     /// For each node of \c Graph, this gives a node of \c EdgeSetGraph .
   449     void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) { 
   450       n_node=&_n_node; 
   451     }
   452     /// For each node of \c EdgeSetGraph, this gives a node of \c Graph .
   453     void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) { 
   454       e_node=&_e_node; 
   455     }
   456   public:
   457     class Edge : public EdgeSetGraph::Edge {
   458       typedef typename EdgeSetGraph::Edge Parent;
   459     public:
   460       Edge() { }
   461       Edge(const Parent& e) : Parent(e) { }
   462       Edge(Invalid i) : Parent(i) { }
   463     };
   464 
   465     using Parent::first;
   466     void first(Edge &e) const { 
   467       edge_set_graph->first(e);
   468     }
   469     void firstOut(Edge& e, const Node& n) const {
   470 //       cout << e_node << endl;
   471 //       cout << n_node << endl;
   472       edge_set_graph->firstOut(e, (*e_node)[n]);
   473     }
   474     void firstIn(Edge& e, const Node& n) const {
   475       edge_set_graph->firstIn(e, (*e_node)[n]);
   476     }
   477 
   478     using Parent::next;
   479     void next(Edge &e) const { 
   480       edge_set_graph->next(e);
   481     }
   482     void nextOut(Edge& e) const {
   483       edge_set_graph->nextOut(e);
   484     }
   485     void nextIn(Edge& e) const {
   486       edge_set_graph->nextIn(e);
   487     }
   488 
   489     Node source(const Edge& e) const { 
   490       return (*n_node)[edge_set_graph->source(e)];
   491     }
   492     Node target(const Edge& e) const { 
   493       return (*n_node)[edge_set_graph->target(e)];
   494     }
   495 
   496     int edgeNum() const { return edge_set_graph->edgeNum(); }
   497 
   498     Edge addEdge(const Node& u, const Node& v) {
   499       return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
   500     }
   501 
   502     using Parent::erase;
   503     void erase(const Edge& i) const { edge_set_graph->erase(i); }
   504   
   505     void clear() const { Parent::clear(); edge_set_graph->clear(); }
   506 
   507     bool forward(const Edge& e) const { return edge_set_graph->forward(e); }
   508     bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
   509 
   510     using Parent::id;
   511     int id(const Edge& e) const { return edge_set_graph->id(e); }
   512     
   513     Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
   514 
   515     template <typename _Value>
   516     class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {
   517     public:
   518       typedef typename EdgeSetGraph::EdgeMap<_Value> Parent; 
   519       typedef _Value Value;
   520       typedef Edge Key;
   521       EdgeMap(const NewEdgeSetGraphWrapperBase& gw) : 
   522 	Parent(*(gw.edge_set_graph)) { }
   523       EdgeMap(const NewEdgeSetGraphWrapperBase& gw, const _Value& _value) : 
   524 	Parent(*(gw.edge_set_graph), _value) { }
   525     };
   526 
   527   };
   528 
   529   template <typename _Graph, typename _EdgeSetGraph>
   530   class NewEdgeSetGraphWrapper : 
   531     public IterableGraphExtender<
   532     NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
   533   public:
   534     typedef _Graph Graph;
   535     typedef _EdgeSetGraph EdgeSetGraph;
   536     typedef IterableGraphExtender<
   537       NewEdgeSetGraphWrapper<_Graph, _EdgeSetGraph> > Parent;
   538   protected:
   539     NewEdgeSetGraphWrapper() { }
   540   public:
   541     NewEdgeSetGraphWrapper(_Graph& _graph, 
   542 			   _EdgeSetGraph& _edge_set_graph, 
   543 			   typename _Graph::
   544 			   NodeMap<typename _EdgeSetGraph::Node>& _e_node, 
   545 			   typename _EdgeSetGraph::
   546 			   NodeMap<typename _Graph::Node>& _n_node) { 
   547       setGraph(_graph);
   548       setEdgeSetGraph(_edge_set_graph);
   549       setNodeMap(_n_node);
   550       setENodeMap(_e_node);
   551     }
   552   };
   553 
   554 } //namespace lemon
   555 
   556 #endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H