Concept modification to resolve the item by its ID.
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>
29 #include <boost/type_traits.hpp>
30 #include <boost/utility/enable_if.hpp>
34 template <class _Graph1>
35 class P1 : public GraphWrapperBase<_Graph1> {
38 template <class _Graph2>
39 class P2 : public GraphWrapperBase<_Graph2> {
43 template <typename _Graph1, typename _Graph2, typename Enable=void>
44 class MergeNodeGraphWrapperBaseBase :
45 public P1<_Graph1>, public P2<_Graph2> {
47 static void printNode() { std::cout << "node: generic" << std::endl; }
48 typedef _Graph1 Graph1;
49 typedef _Graph2 Graph2;
50 typedef P1<_Graph1> Parent1;
51 typedef P2<_Graph2> Parent2;
52 typedef typename Parent1::Node Graph1Node;
53 typedef typename Parent2::Node Graph2Node;
55 MergeNodeGraphWrapperBaseBase() { }
58 class Node : public Graph1Node, public Graph2Node {
59 friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
61 bool backward; //true, iff backward
64 /// \todo =false is needed, or causes problems?
65 /// If \c _backward is false, then we get an edge corresponding to the
66 /// original one, otherwise its oppositely directed pair is obtained.
67 Node(const Graph1Node& n1,
68 const Graph2Node& n2, bool _backward) :
69 Graph1Node(n1), Graph2Node(n2), backward(_backward) { }
70 Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { }
71 bool operator==(const Node& v) const {
74 static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
76 return (!v.backward &&
77 static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
79 bool operator!=(const Node& v) const {
84 static bool forward(const Node& n) { return !n.backward; }
85 static bool backward(const Node& n) { return n.backward; }
86 static void setForward(Node& n) { n.backward=false; }
87 static void setBackward(Node& n) { n.backward=true; }
91 template <typename _Graph1, typename _Graph2>
92 class MergeNodeGraphWrapperBaseBase<
93 _Graph1, _Graph2, typename boost::enable_if<
94 boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
95 public P1<_Graph1>, public P2<_Graph2> {
97 static void printNode() { std::cout << "node: same" << std::endl; }
98 typedef _Graph1 Graph1;
99 typedef _Graph2 Graph2;
100 typedef P1<_Graph1> Parent1;
101 typedef P2<_Graph2> Parent2;
102 typedef typename Parent1::Node Graph1Node;
103 typedef typename Parent2::Node Graph2Node;
105 MergeNodeGraphWrapperBaseBase() { }
108 class Node : public Graph1Node {
109 friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
111 bool backward; //true, iff backward
114 /// \todo =false is needed, or causes problems?
115 /// If \c _backward is false, then we get an edge corresponding to the
116 /// original one, otherwise its oppositely directed pair is obtained.
117 Node(const Graph1Node& n1,
118 const Graph2Node& n2, bool _backward) :
119 Graph1Node(!_backward ? n1 : n2), backward(_backward) { }
120 Node(Invalid i) : Graph1Node(i), backward(true) { }
121 bool operator==(const Node& v) const {
122 return (backward==v.backward &&
123 static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
125 bool operator!=(const Node& v) const {
130 static bool forward(const Node& n) { return !n.backward; }
131 static bool backward(const Node& n) { return n.backward; }
132 static void setForward(Node& n) { n.backward=false; }
133 static void setBackward(Node& n) { n.backward=true; }
137 template <typename _Graph1, typename _Graph2>
138 class MergeNodeGraphWrapperBaseBase<
139 _Graph1, _Graph2, typename boost::enable_if<
140 boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> :
141 public P1<_Graph1>, public P2<_Graph2> {
143 static void printNode() { std::cout << "node: 2nd is derived" << std::endl; }
144 typedef _Graph1 Graph1;
145 typedef _Graph2 Graph2;
146 typedef P1<_Graph1> Parent1;
147 typedef P2<_Graph2> Parent2;
148 typedef typename Parent1::Node Graph1Node;
149 typedef typename Parent2::Node Graph2Node;
151 MergeNodeGraphWrapperBaseBase() { }
154 class Node : public Graph2Node {
155 friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
157 bool backward; //true, iff backward
160 /// \todo =false is needed, or causes problems?
161 /// If \c _backward is false, then we get an edge corresponding to the
162 /// original one, otherwise its oppositely directed pair is obtained.
163 Node(const Graph1Node& n1,
164 const Graph2Node& n2, bool _backward) :
165 Graph2Node(n2), backward(_backward) {
166 if (!backward) *this=n1;
168 Node(Invalid i) : Graph2Node(i), backward(true) { }
169 bool operator==(const Node& v) const {
171 return (v.backward &&
172 static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
174 return (!v.backward &&
175 static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
177 bool operator!=(const Node& v) const {
182 static bool forward(const Node& n) { return !n.backward; }
183 static bool backward(const Node& n) { return n.backward; }
184 static void setForward(Node& n) { n.backward=false; }
185 static void setBackward(Node& n) { n.backward=true; }
189 template <typename _Graph1, typename _Graph2>
190 class MergeNodeGraphWrapperBaseBase<
191 _Graph1, _Graph2, typename boost::enable_if<
192 boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> :
193 public P1<_Graph1>, public P2<_Graph2> {
195 static void printNode() { std::cout << "node: 1st is derived" << std::endl; }
196 typedef _Graph1 Graph1;
197 typedef _Graph2 Graph2;
198 typedef P1<_Graph1> Parent1;
199 typedef P2<_Graph2> Parent2;
200 typedef typename Parent1::Node Graph1Node;
201 typedef typename Parent2::Node Graph2Node;
203 MergeNodeGraphWrapperBaseBase() { }
206 class Node : public Graph1Node {
207 friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
209 bool backward; //true, iff backward
212 /// \todo =false is needed, or causes problems?
213 /// If \c _backward is false, then we get an edge corresponding to the
214 /// original one, otherwise its oppositely directed pair is obtained.
215 Node(const Graph1Node& n1,
216 const Graph2Node& n2, bool _backward) :
217 Graph1Node(n1), backward(_backward) {
218 if (backward) *this=n2;
220 Node(Invalid i) : Graph1Node(i), backward(true) { }
221 bool operator==(const Node& v) const {
223 return (v.backward &&
224 static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
226 return (!v.backward &&
227 static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
229 bool operator!=(const Node& v) const {
234 static bool forward(const Node& n) { return !n.backward; }
235 static bool backward(const Node& n) { return n.backward; }
236 static void setForward(Node& n) { n.backward=false; }
237 static void setBackward(Node& n) { n.backward=true; }
241 template <typename _Graph1, typename _Graph2>
242 class MergeNodeGraphWrapperBase :
243 public MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> {
245 typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
246 typedef _Graph1 Graph1;
247 typedef _Graph2 Graph2;
248 typedef P1<_Graph1> Parent1;
249 typedef P2<_Graph2> Parent2;
250 typedef typename Parent1::Node Graph1Node;
251 typedef typename Parent2::Node Graph2Node;
253 typedef typename Parent::Node Node;
256 void first(Node& i) const {
257 Parent1::graph->first(*static_cast<Graph1Node*>(&i));
259 if (*static_cast<Graph1Node*>(&i)==INVALID) {
260 Parent2::graph->first(*static_cast<Graph2Node*>(&i));
261 this->setBackward(i);
264 void next(Node& i) const {
265 if (this->forward(i)) {
266 Parent1::graph->next(*static_cast<Graph1Node*>(&i));
267 if (*static_cast<Graph1Node*>(&i)==INVALID) {
268 Parent2::graph->first(*static_cast<Graph2Node*>(&i));
269 this->setBackward(i);
272 Parent2::graph->next(*static_cast<Graph2Node*>(&i));
276 int id(const Node& n) const {
277 if (this->forward(n))
278 return this->Parent1::graph->id(n);
280 return this->Parent2::graph->id(n);
283 template <typename _Value>
286 typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
287 typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
288 ParentMap1 forward_map;
289 ParentMap2 backward_map;
291 typedef _Value Value;
293 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
294 forward_map(*(gw.Parent1::graph)),
295 backward_map(*(gw.Parent2::graph)) { }
296 NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
297 const _Value& value) :
298 forward_map(*(gw.Parent1::graph), value),
299 backward_map(*(gw.Parent2::graph), value) { }
300 _Value operator[](const Node& n) const {
301 if (Parent::forward(n))
302 return forward_map[n];
304 return backward_map[n];
306 void set(const Node& n, const _Value& value) {
307 if (Parent::forward(n))
308 forward_map.set(n, value);
310 backward_map.set(n, value);
312 // using ParentMap1::operator[];
313 // using ParentMap2::operator[];
319 /*! A graph wrapper class
320 for merging the node-set of two node-disjoint graphs
321 into the node-set of one graph.
322 Different implementations are according to the relation of
323 _Graph1::Node and _Graph2::Node.
324 If _Graph1::Node and _Graph2::Node are unrelated, then
325 MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
326 is derived from both.
327 If _Graph1::Node and _Graph2::Node are the same type, then
328 MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
329 is derived from _Graph1::Node.
330 If one of _Graph1::Node and _Graph2::Node
331 is derived from the other one, then
332 MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
333 is derived from the derived type.
335 StaticGraph concept as it has no edge-set which
336 works together with the node-set.
338 template <typename _Graph1, typename _Graph2>
339 class MergeNodeGraphWrapper : public
340 IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
342 typedef _Graph1 Graph1;
343 typedef _Graph2 Graph2;
344 typedef IterableGraphExtender<
345 MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
347 MergeNodeGraphWrapper() { }
349 MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
350 Parent::Parent1::setGraph(_graph1);
351 Parent::Parent2::setGraph(_graph2);
356 /*! A grah wrapper base class
357 for merging the node-sets and edge-sets of
358 two node-disjoint graphs
360 Generic implementation for unrelated _Graph1::Edge and _Graph2::Edge.
362 template <typename _Graph1, typename _Graph2, typename Enable=void>
363 class MergeEdgeGraphWrapperBaseBase :
364 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
366 static void printEdge() { std::cout << "edge: generic" << std::endl; }
367 typedef _Graph1 Graph1;
368 typedef _Graph2 Graph2;
369 typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
370 typedef typename Parent::Parent1 Parent1;
371 typedef typename Parent::Parent2 Parent2;
372 // typedef P1<_Graph1> Parent1;
373 // typedef P2<_Graph2> Parent2;
374 typedef typename Parent1::Edge Graph1Edge;
375 typedef typename Parent2::Edge Graph2Edge;
377 MergeEdgeGraphWrapperBaseBase() { }
380 class Edge : public Graph1Edge, public Graph2Edge {
381 friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
383 bool backward; //true, iff backward
386 /// \todo =false is needed, or causes problems?
387 /// If \c _backward is false, then we get an edge corresponding to the
388 /// original one, otherwise its oppositely directed pair is obtained.
389 Edge(const Graph1Edge& n1,
390 const Graph2Edge& n2, bool _backward) :
391 Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
392 Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
393 bool operator==(const Edge& v) const {
395 return (v.backward &&
396 static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
398 return (!v.backward &&
399 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
401 bool operator!=(const Edge& v) const {
406 using Parent::forward;
407 using Parent::backward;
408 using Parent::setForward;
409 using Parent::setBackward;
410 static bool forward(const Edge& e) { return !e.backward; }
411 static bool backward(const Edge& e) { return e.backward; }
412 static void setForward(Edge& e) { e.backward=false; }
413 static void setBackward(Edge& e) { e.backward=true; }
418 /*! A graph wrapper base class
419 for merging the node-sets and edge-sets of
420 two node-disjoint graphs
422 Specialization for the case when _Graph1::Edge and _Graph2::Edge
425 template <typename _Graph1, typename _Graph2>
426 class MergeEdgeGraphWrapperBaseBase<
427 _Graph1, _Graph2, typename boost::enable_if<
428 boost::is_same<typename _Graph1::Edge, typename _Graph2::Edge> >::type> :
429 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
431 static void printEdge() { std::cout << "edge: same" << std::endl; }
432 typedef _Graph1 Graph1;
433 typedef _Graph2 Graph2;
434 typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
435 typedef typename Parent::Parent1 Parent1;
436 typedef typename Parent::Parent2 Parent2;
437 // typedef P1<_Graph1> Parent1;
438 // typedef P2<_Graph2> Parent2;
439 typedef typename Parent1::Edge Graph1Edge;
440 typedef typename Parent2::Edge Graph2Edge;
442 MergeEdgeGraphWrapperBaseBase() { }
445 class Edge : public Graph1Edge {
446 friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
448 bool backward; //true, iff backward
451 /// \todo =false is needed, or causes problems?
452 /// If \c _backward is false, then we get an edge corresponding to the
453 /// original one, otherwise its oppositely directed pair is obtained.
454 Edge(const Graph1Edge& n1,
455 const Graph2Edge& n2, bool _backward) :
456 Graph1Edge(!_backward ? n1 : n2), backward(_backward) { }
457 Edge(Invalid i) : Graph1Edge(i), backward(true) { }
458 bool operator==(const Edge& v) const {
459 return (backward==v.backward &&
460 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
462 bool operator!=(const Edge& v) const {
467 using Parent::forward;
468 using Parent::backward;
469 using Parent::setForward;
470 using Parent::setBackward;
471 static bool forward(const Edge& e) { return !e.backward; }
472 static bool backward(const Edge& e) { return e.backward; }
473 static void setForward(Edge& e) { e.backward=false; }
474 static void setBackward(Edge& e) { e.backward=true; }
478 /*! A grah wrapper base class
479 for merging the node-sets and edge-sets of
480 two node-disjoint graphs
482 Specialized implementation for the case
483 when _Graph1::Edge is a base class and _Graph2::Edge
486 template <typename _Graph1, typename _Graph2>
487 class MergeEdgeGraphWrapperBaseBase<
488 _Graph1, _Graph2, typename boost::enable_if<
489 boost::is_base_and_derived<typename _Graph1::Edge, typename _Graph2::Edge> >::type> :
490 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
492 static void printEdge() { std::cout << "edge: 2nd is derived" << std::endl; }
493 typedef _Graph1 Graph1;
494 typedef _Graph2 Graph2;
495 typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
496 typedef typename Parent::Parent1 Parent1;
497 typedef typename Parent::Parent2 Parent2;
498 // typedef P1<_Graph1> Parent1;
499 // typedef P2<_Graph2> Parent2;
500 typedef typename Parent1::Edge Graph1Edge;
501 typedef typename Parent2::Edge Graph2Edge;
503 MergeEdgeGraphWrapperBaseBase() { }
506 class Edge : public Graph2Edge {
507 friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
509 bool backward; //true, iff backward
512 /// \todo =false is needed, or causes problems?
513 /// If \c _backward is false, then we get an edge corresponding to the
514 /// original one, otherwise its oppositely directed pair is obtained.
515 Edge(const Graph1Edge& n1,
516 const Graph2Edge& n2, bool _backward) :
517 Graph2Edge(n2), backward(_backward) {
518 if (!backward) *this=n1;
520 Edge(Invalid i) : Graph2Edge(i), backward(true) { }
521 bool operator==(const Edge& v) const {
523 return (v.backward &&
524 static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
526 return (!v.backward &&
527 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
529 bool operator!=(const Edge& v) const {
534 using Parent::forward;
535 using Parent::backward;
536 using Parent::setForward;
537 using Parent::setBackward;
538 static bool forward(const Edge& e) { return !e.backward; }
539 static bool backward(const Edge& e) { return e.backward; }
540 static void setForward(Edge& e) { e.backward=false; }
541 static void setBackward(Edge& e) { e.backward=true; }
545 /*! A grah wrapper base class
546 for merging the node-sets and edge-sets of
547 two node-disjoint graphs
549 Specialized implementation for the case
550 when _Graph1::Edge is derived from _Graph2::Edge.
552 template <typename _Graph1, typename _Graph2>
553 class MergeEdgeGraphWrapperBaseBase<
554 _Graph1, _Graph2, typename boost::enable_if<
555 boost::is_base_and_derived<typename _Graph2::Edge, typename _Graph1::Edge> >::type> :
556 public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
558 static void printEdge() { std::cout << "edge: 1st is derived" << std::endl; }
559 typedef _Graph1 Graph1;
560 typedef _Graph2 Graph2;
561 typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
562 typedef typename Parent::Parent1 Parent1;
563 typedef typename Parent::Parent2 Parent2;
564 // typedef P1<_Graph1> Parent1;
565 // typedef P2<_Graph2> Parent2;
566 typedef typename Parent1::Edge Graph1Edge;
567 typedef typename Parent2::Edge Graph2Edge;
569 MergeEdgeGraphWrapperBaseBase() { }
572 class Edge : public Graph1Edge {
573 friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
575 bool backward; //true, iff backward
578 /// \todo =false is needed, or causes problems?
579 /// If \c _backward is false, then we get an edge corresponding to the
580 /// original one, otherwise its oppositely directed pair is obtained.
581 Edge(const Graph1Edge& n1,
582 const Graph2Edge& n2, bool _backward) :
583 Graph1Edge(n1), backward(_backward) {
584 if (backward) *this=n2;
586 Edge(Invalid i) : Graph1Edge(i), backward(true) { }
587 bool operator==(const Edge& v) const {
589 return (v.backward &&
590 static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
592 return (!v.backward &&
593 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
595 bool operator!=(const Edge& v) const {
600 using Parent::forward;
601 using Parent::backward;
602 using Parent::setForward;
603 using Parent::setBackward;
604 static bool forward(const Edge& e) { return !e.backward; }
605 static bool backward(const Edge& e) { return e.backward; }
606 static void setForward(Edge& e) { e.backward=false; }
607 static void setBackward(Edge& e) { e.backward=true; }
611 template <typename _Graph1, typename _Graph2>
612 class MergeEdgeGraphWrapperBase :
613 public MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> {
615 typedef MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
616 typedef _Graph1 Graph1;
617 typedef _Graph2 Graph2;
618 typedef typename Parent::Parent1 Parent1;
619 typedef typename Parent::Parent2 Parent2;
620 typedef typename Parent1::Node Graph1Node;
621 typedef typename Parent2::Node Graph2Node;
622 typedef typename Parent1::Edge Graph1Edge;
623 typedef typename Parent2::Edge Graph2Edge;
625 typedef typename Parent::Node Node;
626 typedef typename Parent::Edge Edge;
629 void first(Edge& i) const {
630 Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
632 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
633 Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
634 this->setBackward(i);
637 void firstIn(Edge& i, const Node& n) const {
639 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
640 if (*static_cast<Graph1Edge*>(&i)==INVALID)
645 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
646 this->setBackward(i);
649 void firstOut(Edge& i, const Node& n) const {
651 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
652 if (*static_cast<Graph1Edge*>(&i)==INVALID)
657 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
658 this->setBackward(i);
663 void next(Edge& i) const {
665 Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
666 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
667 Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
668 this->setBackward(i);
671 Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
674 void nextIn(Edge& i) const {
676 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
677 if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
679 Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
682 void nextOut(Edge& i) const {
683 if (Parent::forward(i)) {
684 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
685 if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
687 Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
691 Node source(const Edge& i) const {
694 Node(Parent1::graph->source(i), INVALID, false);
697 Node(INVALID, Parent2::graph->source(i), true);
701 Node target(const Edge& i) const {
704 Node(Parent1::graph->target(i), INVALID, false);
707 Node(INVALID, Parent2::graph->target(i), true);
712 int id(const Edge& n) const {
714 return this->Parent1::graph->id(n);
716 return this->Parent2::graph->id(n);
719 template <typename _Value>
722 typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
723 typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
724 ParentMap1 forward_map;
725 ParentMap2 backward_map;
727 typedef _Value Value;
729 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
730 forward_map(*(gw.Parent1::graph)),
731 backward_map(*(gw.Parent2::graph)) { }
732 EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
733 const _Value& value) :
734 forward_map(*(gw.Parent1::graph), value),
735 backward_map(*(gw.Parent2::graph), value) { }
736 _Value operator[](const Edge& n) const {
737 if (Parent::forward(n))
738 return forward_map[n];
740 return backward_map[n];
742 void set(const Edge& n, const _Value& value) {
743 if (Parent::forward(n))
744 forward_map.set(n, value);
746 backward_map.set(n, value);
748 // using ParentMap1::operator[];
749 // using ParentMap2::operator[];
756 /*! A graph wrapper class
757 for merging two node-disjoint graphs
759 Different implementations are according to the relation of
760 _Graph1::Edge and _Graph2::Edge.
761 If _Graph1::Edge and _Graph2::Edge are unrelated, then
762 MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge
763 is derived from both.
764 If _Graph1::Edge and _Graph2::Edge are the same type, then
765 MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge
766 is derived from _Graph1::Edge.
767 If one of _Graph1::Edge and _Graph2::Edge
768 is derived from the other one, then
769 MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge
770 is derived from the derived type.
773 template <typename _Graph1, typename _Graph2>
774 class MergeEdgeGraphWrapper : public
775 IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
777 typedef _Graph1 Graph1;
778 typedef _Graph2 Graph2;
779 typedef IterableGraphExtender<
780 MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
782 MergeEdgeGraphWrapper() { }
784 MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
785 Parent::Parent1::setGraph(_graph1);
786 Parent::Parent2::setGraph(_graph2);
791 /*! A graph wrapper base class for the following functionality.
792 If a bijection is given between the node-sets of two graphs,
793 then the second one can be considered as a new edge-set
794 over th first node-set.
796 template <typename _Graph, typename _EdgeSetGraph>
797 class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
799 typedef GraphWrapperBase<_Graph> Parent;
800 typedef _Graph Graph;
801 typedef _EdgeSetGraph EdgeSetGraph;
802 typedef typename _Graph::Node Node;
803 typedef typename _EdgeSetGraph::Node ENode;
805 EdgeSetGraph* edge_set_graph;
806 typename Graph::NodeMap<ENode>* e_node;
807 typename EdgeSetGraph::NodeMap<Node>* n_node;
808 void setEdgeSetGraph(EdgeSetGraph& _edge_set_graph) {
809 edge_set_graph=&_edge_set_graph;
811 /// For each node of \c Graph, this gives a node of \c EdgeSetGraph .
812 void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) {
815 /// For each node of \c EdgeSetGraph, this gives a node of \c Graph .
816 void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) {
820 class Edge : public EdgeSetGraph::Edge {
821 typedef typename EdgeSetGraph::Edge Parent;
824 Edge(const Parent& e) : Parent(e) { }
825 Edge(Invalid i) : Parent(i) { }
829 void first(Edge &e) const {
830 edge_set_graph->first(e);
832 void firstOut(Edge& e, const Node& n) const {
833 // cout << e_node << endl;
834 // cout << n_node << endl;
835 edge_set_graph->firstOut(e, (*e_node)[n]);
837 void firstIn(Edge& e, const Node& n) const {
838 edge_set_graph->firstIn(e, (*e_node)[n]);
842 void next(Edge &e) const {
843 edge_set_graph->next(e);
845 void nextOut(Edge& e) const {
846 edge_set_graph->nextOut(e);
848 void nextIn(Edge& e) const {
849 edge_set_graph->nextIn(e);
852 Node source(const Edge& e) const {
853 return (*n_node)[edge_set_graph->source(e)];
855 Node target(const Edge& e) const {
856 return (*n_node)[edge_set_graph->target(e)];
859 int edgeNum() const { return edge_set_graph->edgeNum(); }
861 // NNode addOldNode() {
862 // return Parent::addNode();
865 // ENode addNewNode() {
866 // return edge_set_graph->addNode();
869 Edge addEdge(const Node& u, const Node& v) {
870 return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
874 void erase(const Edge& i) const { edge_set_graph->erase(i); }
876 void clear() const { Parent::clear(); edge_set_graph->clear(); }
878 bool forward(const Edge& e) const { return edge_set_graph->forward(e); }
879 bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
881 int id(const Node& e) const { return Parent::id(e); }
882 int id(const Edge& e) const { return edge_set_graph->id(e); }
884 Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
886 template <typename _Value>
887 class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {
889 typedef typename EdgeSetGraph::EdgeMap<_Value> Parent;
890 typedef _Value Value;
892 EdgeMap(const NewEdgeSetGraphWrapperBase& gw) :
893 Parent(*(gw.edge_set_graph)) { }
894 EdgeMap(const NewEdgeSetGraphWrapperBase& gw, const _Value& _value) :
895 Parent(*(gw.edge_set_graph), _value) { }
901 /*! A graph wrapper class for the following functionality.
902 If a bijection is given between the node-sets of two graphs,
903 then the second one can be considered as a new edge-set
904 over th first node-set.
906 template <typename _Graph, typename _EdgeSetGraph>
907 class NewEdgeSetGraphWrapper :
908 public IterableGraphExtender<
909 NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
911 typedef _Graph Graph;
912 typedef _EdgeSetGraph EdgeSetGraph;
913 typedef IterableGraphExtender<
914 NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
916 NewEdgeSetGraphWrapper() { }
918 NewEdgeSetGraphWrapper(_Graph& _graph,
919 _EdgeSetGraph& _edge_set_graph,
921 NodeMap<typename _EdgeSetGraph::Node>& _e_node,
922 typename _EdgeSetGraph::
923 NodeMap<typename _Graph::Node>& _n_node) {
925 setEdgeSetGraph(_edge_set_graph);
927 setENodeMap(_e_node);
931 /*! A graph wrapper class for the following functionality.
932 The same as NewEdgeSetGrapWrapper, but the bijection and the graph of
933 new edges is andled inthe class.
935 template <typename _Graph, typename _EdgeSetGraph>
936 class NewEdgeSetGraphWrapper2 :
937 public IterableGraphExtender<
938 NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
940 typedef _Graph Graph;
941 typedef _EdgeSetGraph EdgeSetGraph;
942 typedef IterableGraphExtender<
943 NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
945 _EdgeSetGraph _edge_set_graph;
946 typename Graph::template NodeMap<typename EdgeSetGraph::Node> _e_node;
947 typename EdgeSetGraph::template NodeMap<typename Graph::Node> _n_node;
948 NewEdgeSetGraphWrapper2() { }
950 typedef typename Graph::Node Node;
951 // typedef typename Parent::Edge Edge;
953 NewEdgeSetGraphWrapper2(_Graph& _graph) :
955 _e_node(_graph), _n_node(_edge_set_graph) {
957 setEdgeSetGraph(_edge_set_graph);
958 setNodeMap(_n_node); setENodeMap(_e_node);
960 for (this->first(n); n!=INVALID; this->next(n)) {
961 typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
968 // Node n=(*this).Parent::addNode();
969 // typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
970 // _e_node.set(n, e);
971 // _n_node.set(e, n);
977 /*! A graph wrapper base class
978 for merging graphs of type _Graph1 and _Graph2
979 which are given on the same node-set
980 (specially on the node-set of Graph1)
982 In an other point of view, _Graph1 is extended with
983 the edge-set of _Graph2.
984 \warning we need specialize dimplementations
985 \todo we need specialize dimplementations
986 \bug we need specialize dimplementations
988 template <typename _Graph1, typename _Graph2, typename Enable=void>
989 class AugmentingGraphWrapperBase :
992 void printAugment() const { std::cout << "generic" << std::endl; }
993 typedef _Graph1 Graph1;
994 typedef _Graph2 Graph2;
995 typedef P1<_Graph1> Parent1;
996 typedef P2<_Graph2> Parent2;
997 typedef typename Parent1::Edge Graph1Edge;
998 typedef typename Parent2::Edge Graph2Edge;
1000 AugmentingGraphWrapperBase() { }
1002 void setGraph2(_Graph2& _graph2) { graph2=&_graph2; }
1005 template <typename _Value> class EdgeMap;
1007 typedef typename Parent1::Node Node;
1009 class Edge : public Graph1Edge, public Graph2Edge {
1010 friend class AugmentingGraphWrapperBase<_Graph1, _Graph2>;
1011 template <typename _Value> friend class EdgeMap;
1013 bool backward; //true, iff backward
1016 /// \todo =false is needed, or causes problems?
1017 /// If \c _backward is false, then we get an edge corresponding to the
1018 /// original one, otherwise its oppositely directed pair is obtained.
1019 Edge(const Graph1Edge& n1,
1020 const Graph2Edge& n2, bool _backward) :
1021 Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
1022 Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
1023 bool operator==(const Edge& v) const {
1025 return (v.backward &&
1026 static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
1028 return (!v.backward &&
1029 static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
1031 bool operator!=(const Edge& v) const {
1036 using Parent1::first;
1037 void first(Edge& i) const {
1038 Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
1040 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1041 graph2->first(*static_cast<Graph2Edge*>(&i));
1045 void firstIn(Edge& i, const Node& n) const {
1046 Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
1048 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1049 graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
1053 void firstOut(Edge& i, const Node& n) const {
1054 Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
1056 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1057 graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
1062 using Parent1::next;
1063 void next(Edge& i) const {
1064 if (!(i.backward)) {
1065 Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
1066 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1067 graph2->first(*static_cast<Graph2Edge*>(&i));
1071 graph2->next(*static_cast<Graph2Edge*>(&i));
1074 void nextIn(Edge& i) const {
1075 if (!(i.backward)) {
1077 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
1078 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1079 graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
1083 graph2->nextIn(*static_cast<Graph2Edge*>(&i));
1086 void nextOut(Edge& i) const {
1087 if (!(i.backward)) {
1089 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
1090 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1091 graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
1095 graph2->nextOut(*static_cast<Graph2Edge*>(&i));
1099 Node source(const Edge& i) const {
1100 if (!(i.backward)) {
1101 return Parent1::graph->source(i);
1103 return graph2->source(i);
1107 Node target(const Edge& i) const {
1108 if (!(i.backward)) {
1109 return Parent1::graph->target(i);
1111 return graph2->target(i);
1115 int id(const Node& n) const {
1116 return Parent1::id(n);
1118 int id(const Edge& n) const {
1120 return this->Parent1::graph->id(n);
1122 return this->graph2->id(n);
1125 template <typename _Value>
1128 typedef typename _Graph1::template EdgeMap<_Value> ParentMap1;
1129 typedef typename _Graph2::template EdgeMap<_Value> ParentMap2;
1130 ParentMap1 forward_map;
1131 ParentMap2 backward_map;
1133 typedef _Value Value;
1135 EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw) :
1136 forward_map(*(gw.Parent1::graph)),
1137 backward_map(*(gw.graph2)) { }
1138 EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw,
1139 const _Value& value) :
1140 forward_map(*(gw.Parent1::graph), value),
1141 backward_map(*(gw.graph2), value) { }
1142 _Value operator[](const Edge& n) const {
1144 return forward_map[n];
1146 return backward_map[n];
1148 void set(const Edge& n, const _Value& value) {
1150 forward_map.set(n, value);
1152 backward_map.set(n, value);
1154 // using ParentMap1::operator[];
1155 // using ParentMap2::operator[];
1161 /*! A graph wrapper class
1162 for merging two graphs (of type _Graph1 and _Graph2)
1163 with the same node-set
1164 (specially on the node-set of Graph1)
1166 In an other point of view, _Graph1 is extended with
1167 the edge-set of _Graph2.
1169 template <typename _Graph1, typename _Graph2>
1170 class AugmentingGraphWrapper : public
1171 IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > {
1174 IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> >
1176 typedef _Graph1 Graph1;
1177 typedef _Graph2 Graph2;
1179 AugmentingGraphWrapper() { }
1181 AugmentingGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
1189 #endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H