2 * src/lemon/merge_node_graph_wrapper.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
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.
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
17 #ifndef LEMON_MERGE_NODE_GRAPH_WRAPPER_H
18 #define LEMON_MERGE_NODE_GRAPH_WRAPPER_H
20 #include <lemon/invalid.h>
21 #include <lemon/maps.h>
22 #include <lemon/map_defines.h>
23 #include <lemon/graph_wrapper.h>
28 #include <boost/type_traits.hpp>
29 #include <boost/utility/enable_if.hpp>
33 template <class _Graph1>
34 class P1 : public GraphWrapperBase<_Graph1> {
37 template <class _Graph2>
38 class P2 : public GraphWrapperBase<_Graph2> {
41 /*! A base class for merging the node-set of two node-disjoint graphs
42 into the node-set of one graph.
44 template <typename _Graph1, typename _Graph2, typename Enable=void>
45 class MergeNodeGraphWrapperBase :
46 public P1<_Graph1>, public P2<_Graph2> {
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;
56 MergeNodeGraphWrapperBase() { }
58 template <typename _Value> class NodeMap;
60 class Node : public Graph1Node, public Graph2Node {
61 friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
62 template <typename Value> friend class NodeMap;
64 bool backward; //true, iff backward
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));
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));
93 void first(Node& i) const {
94 Parent1::graph->first(*static_cast<Graph1Node*>(&i));
96 if (*static_cast<Graph1Node*>(&i)==INVALID) {
97 Parent2::graph->first(*static_cast<Graph2Node*>(&i));
101 void next(Node& i) const {
103 Parent1::graph->next(*static_cast<Graph1Node*>(&i));
104 if (*static_cast<Graph1Node*>(&i)==INVALID) {
105 Parent2::graph->first(*static_cast<Graph2Node*>(&i));
109 Parent2::graph->next(*static_cast<Graph2Node*>(&i));
113 int id(const Node& n) const {
115 return this->Parent1::graph->id(n);
117 return this->Parent2::graph->id(n);
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;
126 typedef _Value Value;
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 {
135 return ParentMap1::operator[](n);
137 return ParentMap2::operator[](n);
139 void set(const Node& n, const _Value& value) {
141 ParentMap1::set(n, value);
143 ParentMap2::set(n, value);
145 // using ParentMap1::operator[];
146 // using ParentMap2::operator[];
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> {
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;
166 MergeNodeGraphWrapperBase() { }
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> {
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;
189 MergeNodeGraphWrapperBase() { }
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> {
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;
212 MergeNodeGraphWrapperBase() { }
221 template <typename _Graph1, typename _Graph2>
222 class MergeNodeGraphWrapper : public
223 IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
225 typedef _Graph1 Graph1;
226 typedef _Graph2 Graph2;
227 typedef IterableGraphExtender<
228 MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
230 MergeNodeGraphWrapper() { }
232 MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
233 Parent::Parent1::setGraph(_graph1);
234 Parent::Parent2::setGraph(_graph2);
239 /*! A base class for merging the node-sets and edge-sets of
240 two node-disjoint graphs
243 template <typename _Graph1, typename _Graph2, typename Enable=void>
244 class MergeEdgeGraphWrapperBase :
245 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
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;
258 MergeEdgeGraphWrapperBase() { }
260 template <typename _Value> class EdgeMap;
262 typedef typename Parent::Node Node;
264 class Edge : public Graph1Edge, public Graph2Edge {
265 friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
266 template <typename Value> friend class EdgeMap;
268 bool backward; //true, iff backward
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));
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));
295 void first(Edge& i) const {
296 Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
298 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
299 Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
303 void firstIn(Edge& i, const Node& n) const {
304 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
306 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
307 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
311 void firstOut(Edge& i, const Node& n) const {
312 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
314 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
315 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
321 void next(Edge& i) const {
323 Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
324 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
325 Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
329 Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
332 void nextIn(Edge& i) const {
334 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
335 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
336 Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
340 Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
343 void nextOut(Edge& i) const {
345 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
346 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
347 Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
351 Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
355 Node source(const Edge& i) const {
358 Node(Parent1::graph->source(i), INVALID, false);
361 Node(INVALID, Parent2::graph->source(i), true);
365 Node target(const Edge& i) const {
368 Node(Parent1::graph->target(i), INVALID, false);
371 Node(INVALID, Parent2::graph->target(i), true);
376 int id(const Edge& n) const {
378 return this->Parent1::graph->id(n);
380 return this->Parent2::graph->id(n);
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;
389 typedef _Value Value;
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 {
398 return ParentMap1::operator[](n);
400 return ParentMap2::operator[](n);
402 void set(const Edge& n, const _Value& value) {
404 ParentMap1::set(n, value);
406 ParentMap2::set(n, value);
408 // using ParentMap1::operator[];
409 // using ParentMap2::operator[];
415 template <typename _Graph1, typename _Graph2>
416 class MergeEdgeGraphWrapper : public
417 IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
419 typedef _Graph1 Graph1;
420 typedef _Graph2 Graph2;
421 typedef IterableGraphExtender<
422 MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
424 MergeEdgeGraphWrapper() { }
426 MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
427 Parent::Parent1::setGraph(_graph1);
428 Parent::Parent2::setGraph(_graph2);
433 template <typename _Graph, typename _EdgeSetGraph>
434 class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
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;
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;
448 /// For each node of \c Graph, this gives a node of \c EdgeSetGraph .
449 void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) {
452 /// For each node of \c EdgeSetGraph, this gives a node of \c Graph .
453 void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) {
457 class Edge : public EdgeSetGraph::Edge {
458 typedef typename EdgeSetGraph::Edge Parent;
461 Edge(const Parent& e) : Parent(e) { }
462 Edge(Invalid i) : Parent(i) { }
466 void first(Edge &e) const {
467 edge_set_graph->first(e);
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]);
474 void firstIn(Edge& e, const Node& n) const {
475 edge_set_graph->firstIn(e, (*e_node)[n]);
479 void next(Edge &e) const {
480 edge_set_graph->next(e);
482 void nextOut(Edge& e) const {
483 edge_set_graph->nextOut(e);
485 void nextIn(Edge& e) const {
486 edge_set_graph->nextIn(e);
489 Node source(const Edge& e) const {
490 return (*n_node)[edge_set_graph->source(e)];
492 Node target(const Edge& e) const {
493 return (*n_node)[edge_set_graph->target(e)];
496 int edgeNum() const { return edge_set_graph->edgeNum(); }
498 Edge addEdge(const Node& u, const Node& v) {
499 return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
503 void erase(const Edge& i) const { edge_set_graph->erase(i); }
505 void clear() const { Parent::clear(); edge_set_graph->clear(); }
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); }
511 int id(const Edge& e) const { return edge_set_graph->id(e); }
513 Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
515 template <typename _Value>
516 class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {
518 typedef typename EdgeSetGraph::EdgeMap<_Value> Parent;
519 typedef _Value Value;
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) { }
529 template <typename _Graph, typename _EdgeSetGraph>
530 class NewEdgeSetGraphWrapper :
531 public IterableGraphExtender<
532 NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
534 typedef _Graph Graph;
535 typedef _EdgeSetGraph EdgeSetGraph;
536 typedef IterableGraphExtender<
537 NewEdgeSetGraphWrapper<_Graph, _EdgeSetGraph> > Parent;
539 NewEdgeSetGraphWrapper() { }
541 NewEdgeSetGraphWrapper(_Graph& _graph,
542 _EdgeSetGraph& _edge_set_graph,
544 NodeMap<typename _EdgeSetGraph::Node>& _e_node,
545 typename _EdgeSetGraph::
546 NodeMap<typename _Graph::Node>& _n_node) {
548 setEdgeSetGraph(_edge_set_graph);
550 setENodeMap(_e_node);
556 #endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H