COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

source: lemon-0.x/src/work/marci/merge_node_graph_wrapper.h @ 1025:3b1ad8bc21da

Last change on this file since 1025:3b1ad8bc21da was 1025:3b1ad8bc21da, checked in by marci, 19 years ago

MergeGraphWrapper? bug fixes
File size: 46.8 KB
Line 
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
26using std::cout;
27using std::endl;
28
29#include <boost/type_traits.hpp>
30#include <boost/utility/enable_if.hpp>
31
32namespace lemon {
33
34  template <class _Graph1>
35  class P1 : public GraphWrapperBase<_Graph1> {
36  };
37
38  template <class _Graph2>
39  class P2 : public GraphWrapperBase<_Graph2> {
40  };
41
42
43  template <typename _Graph1, typename _Graph2, typename Enable=void>
44  class MergeNodeGraphWrapperBaseBase :
45    public P1<_Graph1>, public P2<_Graph2> {
46  public:
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;
54  protected:
55    MergeNodeGraphWrapperBaseBase() { }
56  public:
57
58    class Node : public Graph1Node, public Graph2Node {
59      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
60    protected:
61      bool backward; //true, iff backward
62    public:
63      Node() { }
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 {
72        if (backward)
73          return (v.backward &&
74                  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
75        else
76          return (!v.backward &&
77                  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
78      }
79      bool operator!=(const Node& v) const {
80        return !(*this==v);
81      }
82    };
83
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; }   
88  };
89
90
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> {
96  public:
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;
104  protected:
105    MergeNodeGraphWrapperBaseBase() { }
106  public:
107
108    class Node : public Graph1Node {
109      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
110    protected:
111      bool backward; //true, iff backward
112    public:
113      Node() { }
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));
124      }
125      bool operator!=(const Node& v) const {
126        return !(*this==v);
127      }
128    };
129
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; }
134  };
135
136
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> {
142  public :
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;
150  protected:
151    MergeNodeGraphWrapperBaseBase() { }
152  public:
153
154    class Node : public Graph2Node {
155      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
156    protected:
157      bool backward; //true, iff backward
158    public:
159      Node() { }
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;
167      }
168      Node(Invalid i) : Graph2Node(i), backward(true) { }
169      bool operator==(const Node& v) const {
170        if (backward)
171          return (v.backward &&
172                  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
173        else
174          return (!v.backward &&
175                  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
176      }
177      bool operator!=(const Node& v) const {
178        return !(*this==v);
179      }
180    };
181
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; }
186  };
187 
188
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> {
194  public :
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;
202  protected:
203    MergeNodeGraphWrapperBaseBase() { }
204  public:
205
206    class Node : public Graph1Node {
207      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
208    protected:
209      bool backward; //true, iff backward
210    public:
211      Node() { }
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;
219      }
220      Node(Invalid i) : Graph1Node(i), backward(true) { }
221      bool operator==(const Node& v) const {
222        if (backward)
223          return (v.backward &&
224                  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
225        else
226          return (!v.backward &&
227                  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
228      }
229      bool operator!=(const Node& v) const {
230        return !(*this==v);
231      }
232    };
233
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; }
238  };
239
240
241  template <typename _Graph1, typename _Graph2>
242  class MergeNodeGraphWrapperBase :
243    public MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> {
244  public:
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;
252
253    typedef typename Parent::Node Node;
254    class Edge { };
255   
256    void first(Node& i) const {
257      Parent1::graph->first(*static_cast<Graph1Node*>(&i));
258      this->setForward(i);
259      if (*static_cast<Graph1Node*>(&i)==INVALID) {
260        Parent2::graph->first(*static_cast<Graph2Node*>(&i));
261        this->setBackward(i);
262      }
263    }
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);
270        }
271      } else {
272        Parent2::graph->next(*static_cast<Graph2Node*>(&i));
273      }
274    }
275
276    int id(const Node& n) const {
277      if (this->forward(n))
278        return this->Parent1::graph->id(n);
279      else
280        return this->Parent2::graph->id(n);
281    }
282
283    template <typename _Value>
284    class NodeMap {
285    protected:
286      typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
287      typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
288      ParentMap1 forward_map;
289      ParentMap2 backward_map;
290    public:
291      typedef _Value Value;
292      typedef Node Key;
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];
303        else
304          return backward_map[n];
305      }
306      void set(const Node& n, const _Value& value) {
307        if (Parent::forward(n))
308          forward_map.set(n, value);
309        else
310          backward_map.set(n, value);
311      }
312//       using ParentMap1::operator[];
313//       using ParentMap2::operator[];
314    };
315
316  };
317
318
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.
334    It does not satisfy
335    StaticGraph concept as it has no edge-set which
336    works together with the node-set.
337  */
338  template <typename _Graph1, typename _Graph2>
339  class MergeNodeGraphWrapper : public
340  IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
341  public:
342    typedef _Graph1 Graph1;
343    typedef _Graph2 Graph2;
344    typedef IterableGraphExtender<
345      MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
346  protected:
347    MergeNodeGraphWrapper() { }
348  public:
349    MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
350      Parent::Parent1::setGraph(_graph1);
351      Parent::Parent2::setGraph(_graph2);
352    }
353  };
354
355
356  /*! A grah wrapper base class
357    for merging the node-sets and edge-sets of
358    two node-disjoint graphs
359    into one graph.
360    Generic implementation for unrelated _Graph1::Edge and _Graph2::Edge.
361   */
362  template <typename _Graph1, typename _Graph2, typename Enable=void>
363  class MergeEdgeGraphWrapperBase :
364    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
365  public:
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;
376  protected:
377    MergeEdgeGraphWrapperBase() { }
378  public:
379    template <typename _Value> class EdgeMap;
380
381    typedef typename Parent::Node Node;
382
383    class Edge : public Graph1Edge, public Graph2Edge {
384      friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
385      template <typename _Value> friend class EdgeMap;
386    protected:
387      bool backward; //true, iff backward
388    public:
389      Edge() { }
390      /// \todo =false is needed, or causes problems?
391      /// If \c _backward is false, then we get an edge corresponding to the
392      /// original one, otherwise its oppositely directed pair is obtained.
393      Edge(const Graph1Edge& n1,
394           const Graph2Edge& n2, bool _backward) :
395        Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
396      Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
397      bool operator==(const Edge& v) const {
398        if (backward)
399          return (v.backward &&
400                  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
401        else
402          return (!v.backward &&
403                  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
404      }
405      bool operator!=(const Edge& v) const {
406        return !(*this==v);
407      }
408    };
409
410    using Parent::forward;
411    using Parent::backward;
412    bool forward(const Edge& e) const { return !e.backward; }
413    bool backward(const Edge& e) const { return e.backward; }
414
415    using Parent::first;
416    void first(Edge& i) const {
417      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
418      i.backward=false;
419      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
420        Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
421        i.backward=true;
422      }
423    }
424    void firstIn(Edge& i, const Node& n) const {
425      if (!backward(n)) {
426        Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
427        if (*static_cast<Graph1Edge*>(&i)==INVALID)
428          i=INVALID;
429        else
430          i.backward=false;
431      } else {
432        Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
433        i.backward=true;
434      }
435    }
436    void firstOut(Edge& i, const Node& n) const {
437      if (!backward(n)) {
438        Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
439        if (*static_cast<Graph1Edge*>(&i)==INVALID)
440          i=INVALID;
441        else
442          i.backward=false;
443      } else {
444        Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
445        i.backward=true;
446      }
447    }
448
449    using Parent::next;
450    void next(Edge& i) const {
451      if (!(i.backward)) {
452        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
453        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
454          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
455          i.backward=true;
456        }
457      } else {
458        Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
459      }
460    }
461    void nextIn(Edge& i) const {
462      if (!(i.backward)) {
463        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
464        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
465      } else {
466        Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
467      }
468    }
469    void nextOut(Edge& i) const {
470      if (!(i.backward)) {
471        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
472        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
473      } else {
474        Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
475      }
476    }
477
478    Node source(const Edge& i) const {
479      if (!(i.backward)) {
480        return
481          Node(Parent1::graph->source(i), INVALID, false);
482      } else {
483        return
484          Node(INVALID, Parent2::graph->source(i), true);
485      }
486    }
487
488    Node target(const Edge& i) const {
489      if (!(i.backward)) {
490        return
491          Node(Parent1::graph->target(i), INVALID, false);
492      } else {
493        return
494          Node(INVALID, Parent2::graph->target(i), true);
495      }
496    }
497
498    using Parent::id;
499    int id(const Edge& n) const {
500      if (!n.backward)
501        return this->Parent1::graph->id(n);
502      else
503        return this->Parent2::graph->id(n);
504    }
505
506    template <typename _Value>
507    class EdgeMap {
508    protected:
509      typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
510      typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
511      ParentMap1 forward_map;
512      ParentMap2 backward_map;
513    public:
514      typedef _Value Value;
515      typedef Edge Key;
516      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
517        forward_map(*(gw.Parent1::graph)),
518        backward_map(*(gw.Parent2::graph)) { }
519      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
520              const _Value& value) :
521        forward_map(*(gw.Parent1::graph), value),
522        backward_map(*(gw.Parent2::graph), value) { }
523      _Value operator[](const Edge& n) const {
524        if (!n.backward)
525          return forward_map[n];
526        else
527          return backward_map[n];
528      }
529      void set(const Edge& n, const _Value& value) {
530        if (!n.backward)
531          forward_map.set(n, value);
532        else
533          backward_map.set(n, value);
534      }
535//       using ParentMap1::operator[];
536//       using ParentMap2::operator[];
537    };
538
539  };
540
541
542  /*! A graph wrapper base class
543    for merging the node-sets and edge-sets of
544    two node-disjoint graphs
545    into one graph.
546    Specialization for the case when _Graph1::Edge and _Graph2::Edge
547    are the same.
548   */
549  template <typename _Graph1, typename _Graph2>
550  class MergeEdgeGraphWrapperBase<
551    _Graph1, _Graph2, typename boost::enable_if<
552    boost::is_same<typename _Graph1::Edge, typename _Graph2::Edge> >::type> :
553    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
554  public:
555    static void printEdge() { std::cout << "edge: same" << std::endl; }
556    typedef _Graph1 Graph1;
557    typedef _Graph2 Graph2;
558    typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
559    typedef typename Parent::Parent1 Parent1;
560    typedef typename Parent::Parent2 Parent2;
561//     typedef P1<_Graph1> Parent1;
562//     typedef P2<_Graph2> Parent2;
563    typedef typename Parent1::Edge Graph1Edge;
564    typedef typename Parent2::Edge Graph2Edge;
565  protected:
566    MergeEdgeGraphWrapperBase() { }
567  public:
568    template <typename _Value> class EdgeMap;
569
570    typedef typename Parent::Node Node;
571
572    class Edge : public Graph1Edge {
573      friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
574      template <typename _Value> friend class EdgeMap;
575    protected:
576      bool backward; //true, iff backward
577    public:
578      Edge() { }
579      /// \todo =false is needed, or causes problems?
580      /// If \c _backward is false, then we get an edge corresponding to the
581      /// original one, otherwise its oppositely directed pair is obtained.
582      Edge(const Graph1Edge& n1,
583           const Graph2Edge& n2, bool _backward) :
584        Graph1Edge(!_backward ? n1 : n2), backward(_backward) { }
585      Edge(Invalid i) : Graph1Edge(i), backward(true) { }
586      bool operator==(const Edge& v) const {
587        return (backward==v.backward &&
588                static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
589      }
590      bool operator!=(const Edge& v) const {
591        return !(*this==v);
592      }
593    };
594
595    using Parent::forward;
596    using Parent::backward;
597    bool forward(const Edge& e) const { return !e.backward; }
598    bool backward(const Edge& e) const { return e.backward; }
599
600    using Parent::first;
601    void first(Edge& i) const {
602      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
603      i.backward=false;
604      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
605        Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
606        i.backward=true;
607      }
608    }
609    void firstIn(Edge& i, const Node& n) const {
610      if (!backward(n)) {
611        Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
612        if (*static_cast<Graph1Edge*>(&i)==INVALID)
613          i=INVALID;
614        else
615          i.backward=false;
616      } else {
617        Parent2::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
618        i.backward=true;
619      }
620    }
621    void firstOut(Edge& i, const Node& n) const {
622      if (!backward(n)) {
623        Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
624        if (*static_cast<Graph1Edge*>(&i)==INVALID)
625          i=INVALID;
626        else
627          i.backward=false;
628      } else {
629        Parent2::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
630        i.backward=true;
631      }
632    }
633
634    using Parent::next;
635    void next(Edge& i) const {
636      if (!(i.backward)) {
637        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
638        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
639          Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
640          i.backward=true;
641        }
642      } else {
643        Parent2::graph->next(*static_cast<Graph1Edge*>(&i));
644      }
645    }
646    void nextIn(Edge& i) const {
647      if (!(i.backward)) {
648        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
649        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
650      } else {
651        Parent2::graph->nextIn(*static_cast<Graph1Edge*>(&i));
652      }
653    }
654    void nextOut(Edge& i) const {
655      if (!(i.backward)) {
656        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
657        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
658      } else {
659        Parent2::graph->nextOut(*static_cast<Graph1Edge*>(&i));
660      }
661    }
662
663    Node source(const Edge& i) const {
664      if (!(i.backward)) {
665        return
666          Node(Parent1::graph->source(i), INVALID, false);
667      } else {
668        return
669          Node(INVALID, Parent2::graph->source(i), true);
670      }
671    }
672
673    Node target(const Edge& i) const {
674      if (!(i.backward)) {
675        return
676          Node(Parent1::graph->target(i), INVALID, false);
677      } else {
678        return
679          Node(INVALID, Parent2::graph->target(i), true);
680      }
681    }
682
683    using Parent::id;
684    int id(const Edge& n) const {
685      if (!n.backward)
686        return this->Parent1::graph->id(n);
687      else
688        return this->Parent2::graph->id(n);
689    }
690
691    template <typename _Value>
692    class EdgeMap {
693    protected:
694      typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
695      typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
696      ParentMap1 forward_map;
697      ParentMap2 backward_map;
698    public:
699      typedef _Value Value;
700      typedef Edge Key;
701      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
702        forward_map(*(gw.Parent1::graph)),
703        backward_map(*(gw.Parent2::graph)) { }
704      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
705              const _Value& value) :
706        forward_map(*(gw.Parent1::graph), value),
707        backward_map(*(gw.Parent2::graph), value) { }
708      _Value operator[](const Edge& n) const {
709        if (!n.backward)
710          return forward_map[n];
711        else
712          return backward_map[n];
713      }
714      void set(const Edge& n, const _Value& value) {
715        if (!n.backward)
716          forward_map.set(n, value);
717        else
718          backward_map.set(n, value);
719      }
720//       using ParentMap1::operator[];
721//       using ParentMap2::operator[];
722    };
723
724  };
725
726
727  /*! A grah wrapper base class
728    for merging the node-sets and edge-sets of
729    two node-disjoint graphs
730    into one graph.
731    Specialized implementation for the case
732    when _Graph1::Edge is a base class and _Graph2::Edge
733    is derived from it.
734   */
735  template <typename _Graph1, typename _Graph2>
736  class MergeEdgeGraphWrapperBase<
737    _Graph1, _Graph2, typename boost::enable_if<
738    boost::is_base_and_derived<typename _Graph1::Edge, typename _Graph2::Edge> >::type> :
739    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
740  public:
741    static void printEdge() { std::cout << "edge: 2nd is derived" << std::endl; }
742    typedef _Graph1 Graph1;
743    typedef _Graph2 Graph2;
744    typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
745    typedef typename Parent::Parent1 Parent1;
746    typedef typename Parent::Parent2 Parent2;
747//     typedef P1<_Graph1> Parent1;
748//     typedef P2<_Graph2> Parent2;
749    typedef typename Parent1::Edge Graph1Edge;
750    typedef typename Parent2::Edge Graph2Edge;
751  protected:
752    MergeEdgeGraphWrapperBase() { }
753  public:
754    template <typename _Value> class EdgeMap;
755
756    typedef typename Parent::Node Node;
757
758    class Edge : public Graph2Edge {
759      friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
760      template <typename _Value> friend class EdgeMap;
761    protected:
762      bool backward; //true, iff backward
763    public:
764      Edge() { }
765      /// \todo =false is needed, or causes problems?
766      /// If \c _backward is false, then we get an edge corresponding to the
767      /// original one, otherwise its oppositely directed pair is obtained.
768      Edge(const Graph1Edge& n1,
769           const Graph2Edge& n2, bool _backward) :
770        Graph2Edge(n2), backward(_backward) {
771        if (!backward) *this=n1;
772      }
773      Edge(Invalid i) : Graph2Edge(i), backward(true) { }
774      bool operator==(const Edge& v) const {
775        if (backward)
776          return (v.backward &&
777                  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
778        else
779          return (!v.backward &&
780                  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
781      }
782      bool operator!=(const Edge& v) const {
783        return !(*this==v);
784      }
785    };
786
787    using Parent::forward;
788    using Parent::backward;
789    bool forward(const Edge& e) const { return !e.backward; }
790    bool backward(const Edge& e) const { return e.backward; }
791
792    using Parent::first;
793    void first(Edge& i) const {
794      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
795      i.backward=false;
796      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
797        Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
798        i.backward=true;
799      }
800    }
801    void firstIn(Edge& i, const Node& n) const {
802      if (!backward(n)) {
803        Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
804        if (*static_cast<Graph1Edge*>(&i)==INVALID)
805          i=INVALID;
806        else
807          i.backward=false;
808      } else {
809        Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
810        i.backward=true;
811      }
812    }
813    void firstOut(Edge& i, const Node& n) const {
814      if (!backward(n)) {
815        Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
816        if (*static_cast<Graph1Edge*>(&i)==INVALID)
817          i=INVALID;
818        else   
819          i.backward=false;
820      } else {
821        Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
822        i.backward=true;
823      }
824    }
825
826    using Parent::next;
827    void next(Edge& i) const {
828      if (!(i.backward)) {
829        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
830        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
831          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
832          i.backward=true;
833        }
834      } else {
835        Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
836      }
837    }
838    void nextIn(Edge& i) const {
839      if (!(i.backward)) {
840        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
841        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
842      } else {
843        Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
844      }
845    }
846    void nextOut(Edge& i) const {
847      if (!(i.backward)) {
848        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
849        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
850      } else {
851        Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
852      }
853    }
854
855    Node source(const Edge& i) const {
856      if (!(i.backward)) {
857        return
858          Node(Parent1::graph->source(i), INVALID, false);
859      } else {
860        return
861          Node(INVALID, Parent2::graph->source(i), true);
862      }
863    }
864
865    Node target(const Edge& i) const {
866      if (!(i.backward)) {
867        return
868          Node(Parent1::graph->target(i), INVALID, false);
869      } else {
870        return
871          Node(INVALID, Parent2::graph->target(i), true);
872      }
873    }
874
875    using Parent::id;
876    int id(const Edge& n) const {
877      if (!n.backward)
878        return this->Parent1::graph->id(n);
879      else
880        return this->Parent2::graph->id(n);
881    }
882
883    template <typename _Value>
884    class EdgeMap {
885    protected:
886      typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
887      typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
888      ParentMap1 forward_map;
889      ParentMap2 backward_map;
890    public:
891      typedef _Value Value;
892      typedef Edge Key;
893      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
894        forward_map(*(gw.Parent1::graph)),
895        backward_map(*(gw.Parent2::graph)) { }
896      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
897              const _Value& value) :
898        forward_map(*(gw.Parent1::graph), value),
899        backward_map(*(gw.Parent2::graph), value) { }
900      _Value operator[](const Edge& n) const {
901        if (!n.backward)
902          return forward_map[n];
903        else
904          return backward_map[n];
905      }
906      void set(const Edge& n, const _Value& value) {
907        if (!n.backward)
908          forward_map.set(n, value);
909        else
910          backward_map.set(n, value);
911      }
912//       using ParentMap1::operator[];
913//       using ParentMap2::operator[];
914    };
915
916  };
917
918
919  /*! A grah wrapper base class
920    for merging the node-sets and edge-sets of
921    two node-disjoint graphs
922    into one graph.
923    Specialized implementation for the case
924    when _Graph1::Edge is derived from _Graph2::Edge.
925   */
926  template <typename _Graph1, typename _Graph2>
927  class MergeEdgeGraphWrapperBase<
928    _Graph1, _Graph2, typename boost::enable_if<
929    boost::is_base_and_derived<typename _Graph2::Edge, typename _Graph1::Edge> >::type> :
930    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
931  public:
932    static void printEdge() { std::cout << "edge: 1st is derived" << std::endl; }
933    typedef _Graph1 Graph1;
934    typedef _Graph2 Graph2;
935    typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
936    typedef typename Parent::Parent1 Parent1;
937    typedef typename Parent::Parent2 Parent2;
938//     typedef P1<_Graph1> Parent1;
939//     typedef P2<_Graph2> Parent2;
940    typedef typename Parent1::Edge Graph1Edge;
941    typedef typename Parent2::Edge Graph2Edge;
942  protected:
943    MergeEdgeGraphWrapperBase() { }
944  public:
945    template <typename _Value> class EdgeMap;
946
947    typedef typename Parent::Node Node;
948
949    class Edge : public Graph1Edge {
950      friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
951      template <typename _Value> friend class EdgeMap;
952    protected:
953      bool backward; //true, iff backward
954    public:
955      Edge() { }
956      /// \todo =false is needed, or causes problems?
957      /// If \c _backward is false, then we get an edge corresponding to the
958      /// original one, otherwise its oppositely directed pair is obtained.
959      Edge(const Graph1Edge& n1,
960           const Graph2Edge& n2, bool _backward) :
961        Graph1Edge(n1), backward(_backward) {
962        if (backward) *this=n2;
963      }
964      Edge(Invalid i) : Graph1Edge(i), backward(true) { }
965      bool operator==(const Edge& v) const {
966        if (backward)
967          return (v.backward &&
968                  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
969        else
970          return (!v.backward &&
971                  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
972      }
973      bool operator!=(const Edge& v) const {
974        return !(*this==v);
975      }
976    };
977
978    using Parent::forward;
979    using Parent::backward;
980    bool forward(const Edge& e) const { return !e.backward; }
981    bool backward(const Edge& e) const { return e.backward; }
982
983    using Parent::first;
984    void first(Edge& i) const {
985      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
986      i.backward=false;
987      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
988        Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
989        i.backward=true;
990      }
991    }
992    void firstIn(Edge& i, const Node& n) const {
993      if (!backward(n)) {
994        Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
995        if (*static_cast<Graph1Edge*>(&i)==INVALID)
996          i=INVALID;
997        else
998          i.backward=false;
999      } else {
1000        Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
1001        i.backward=true;
1002      }
1003    }
1004    void firstOut(Edge& i, const Node& n) const {
1005      if (!backward(n)) {
1006        Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
1007        if (*static_cast<Graph1Edge*>(&i)==INVALID)
1008          i=INVALID;
1009        else   
1010          i.backward=false;
1011      } else {
1012        Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
1013        i.backward=true;
1014      }
1015    }
1016
1017    using Parent::next;
1018    void next(Edge& i) const {
1019      if (!(i.backward)) {
1020        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
1021        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1022          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
1023          i.backward=true;
1024        }
1025      } else {
1026        Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
1027      }
1028    }
1029    void nextIn(Edge& i) const {
1030      if (!(i.backward)) {
1031        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
1032        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
1033      } else {
1034        Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
1035      }
1036    }
1037    void nextOut(Edge& i) const {
1038      if (!(i.backward)) {
1039        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
1040        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
1041      } else {
1042        Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
1043      }
1044    }
1045
1046    Node source(const Edge& i) const {
1047      if (!(i.backward)) {
1048        return
1049          Node(Parent1::graph->source(i), INVALID, false);
1050      } else {
1051        return
1052          Node(INVALID, Parent2::graph->source(i), true);
1053      }
1054    }
1055
1056    Node target(const Edge& i) const {
1057      if (!(i.backward)) {
1058        return
1059          Node(Parent1::graph->target(i), INVALID, false);
1060      } else {
1061        return
1062          Node(INVALID, Parent2::graph->target(i), true);
1063      }
1064    }
1065
1066    using Parent::id;
1067    int id(const Edge& n) const {
1068      if (!n.backward)
1069        return this->Parent1::graph->id(n);
1070      else
1071        return this->Parent2::graph->id(n);
1072    }
1073
1074    template <typename _Value>
1075    class EdgeMap {
1076    protected:
1077      typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
1078      typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
1079      ParentMap1 forward_map;
1080      ParentMap2 backward_map;
1081    public:
1082      typedef _Value Value;
1083      typedef Edge Key;
1084      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
1085        forward_map(*(gw.Parent1::graph)),
1086        backward_map(*(gw.Parent2::graph)) { }
1087      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
1088              const _Value& value) :
1089        forward_map(*(gw.Parent1::graph), value),
1090        backward_map(*(gw.Parent2::graph), value) { }
1091      _Value operator[](const Edge& n) const {
1092        if (!n.backward)
1093          return forward_map[n];
1094        else
1095          return backward_map[n];
1096      }
1097      void set(const Edge& n, const _Value& value) {
1098        if (!n.backward)
1099          forward_map.set(n, value);
1100        else
1101          backward_map.set(n, value);
1102      }
1103//       using ParentMap1::operator[];
1104//       using ParentMap2::operator[];
1105    };
1106
1107  };
1108
1109
1110  /*! A graph wrapper class
1111    for merging the node-sets and edge-sets of
1112    two node-disjoint graphs
1113    into one graph.
1114   */
1115  template <typename _Graph1, typename _Graph2>
1116  class MergeEdgeGraphWrapper : public
1117  IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
1118  public:
1119    typedef _Graph1 Graph1;
1120    typedef _Graph2 Graph2;
1121    typedef IterableGraphExtender<
1122      MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
1123  protected:
1124    MergeEdgeGraphWrapper() { }
1125  public:
1126    MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
1127      Parent::Parent1::setGraph(_graph1);
1128      Parent::Parent2::setGraph(_graph2);
1129    }
1130  };
1131
1132 
1133  /*! A graph wrapper base class for the following functionality.
1134    If a bijection is given between the node-sets of two graphs,
1135    then the second one can be considered as a new edge-set
1136    over th first node-set.
1137   */
1138  template <typename _Graph, typename _EdgeSetGraph>
1139  class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
1140  public:
1141    typedef GraphWrapperBase<_Graph> Parent;
1142    typedef _Graph Graph;
1143    typedef _EdgeSetGraph EdgeSetGraph;
1144    typedef typename _Graph::Node Node;
1145    typedef typename _EdgeSetGraph::Node ENode;
1146  protected:
1147    EdgeSetGraph* edge_set_graph;
1148    typename Graph::NodeMap<ENode>* e_node;
1149    typename EdgeSetGraph::NodeMap<Node>* n_node;
1150    void setEdgeSetGraph(EdgeSetGraph& _edge_set_graph) {
1151      edge_set_graph=&_edge_set_graph;
1152    }
1153    /// For each node of \c Graph, this gives a node of \c EdgeSetGraph .
1154    void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) {
1155      n_node=&_n_node;
1156    }
1157    /// For each node of \c EdgeSetGraph, this gives a node of \c Graph .
1158    void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) {
1159      e_node=&_e_node;
1160    }
1161  public:
1162    class Edge : public EdgeSetGraph::Edge {
1163      typedef typename EdgeSetGraph::Edge Parent;
1164    public:
1165      Edge() { }
1166      Edge(const Parent& e) : Parent(e) { }
1167      Edge(Invalid i) : Parent(i) { }
1168    };
1169
1170    using Parent::first;
1171    void first(Edge &e) const {
1172      edge_set_graph->first(e);
1173    }
1174    void firstOut(Edge& e, const Node& n) const {
1175//       cout << e_node << endl;
1176//       cout << n_node << endl;
1177      edge_set_graph->firstOut(e, (*e_node)[n]);
1178    }
1179    void firstIn(Edge& e, const Node& n) const {
1180      edge_set_graph->firstIn(e, (*e_node)[n]);
1181    }
1182
1183    using Parent::next;
1184    void next(Edge &e) const {
1185      edge_set_graph->next(e);
1186    }
1187    void nextOut(Edge& e) const {
1188      edge_set_graph->nextOut(e);
1189    }
1190    void nextIn(Edge& e) const {
1191      edge_set_graph->nextIn(e);
1192    }
1193
1194    Node source(const Edge& e) const {
1195      return (*n_node)[edge_set_graph->source(e)];
1196    }
1197    Node target(const Edge& e) const {
1198      return (*n_node)[edge_set_graph->target(e)];
1199    }
1200
1201    int edgeNum() const { return edge_set_graph->edgeNum(); }
1202
1203//     NNode addOldNode() {
1204//       return Parent::addNode();
1205//     }
1206
1207//     ENode addNewNode() {
1208//       return edge_set_graph->addNode();
1209//     }
1210
1211    Edge addEdge(const Node& u, const Node& v) {
1212      return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
1213    }
1214
1215    using Parent::erase;
1216    void erase(const Edge& i) const { edge_set_graph->erase(i); }
1217 
1218    void clear() const { Parent::clear(); edge_set_graph->clear(); }
1219
1220    bool forward(const Edge& e) const { return edge_set_graph->forward(e); }
1221    bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
1222
1223    int id(const Node& e) const { return Parent::id(e); }
1224    int id(const Edge& e) const { return edge_set_graph->id(e); }
1225   
1226    Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
1227
1228    template <typename _Value>
1229    class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {
1230    public:
1231      typedef typename EdgeSetGraph::EdgeMap<_Value> Parent;
1232      typedef _Value Value;
1233      typedef Edge Key;
1234      EdgeMap(const NewEdgeSetGraphWrapperBase& gw) :
1235        Parent(*(gw.edge_set_graph)) { }
1236      EdgeMap(const NewEdgeSetGraphWrapperBase& gw, const _Value& _value) :
1237        Parent(*(gw.edge_set_graph), _value) { }
1238    };
1239
1240  };
1241
1242
1243  /*! A graph wrapper class for the following functionality.
1244    If a bijection is given between the node-sets of two graphs,
1245    then the second one can be considered as a new edge-set
1246    over th first node-set.
1247   */
1248  template <typename _Graph, typename _EdgeSetGraph>
1249  class NewEdgeSetGraphWrapper :
1250    public IterableGraphExtender<
1251    NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
1252  public:
1253    typedef _Graph Graph;
1254    typedef _EdgeSetGraph EdgeSetGraph;
1255    typedef IterableGraphExtender<
1256      NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
1257  protected:
1258    NewEdgeSetGraphWrapper() { }
1259  public:
1260    NewEdgeSetGraphWrapper(_Graph& _graph,
1261                           _EdgeSetGraph& _edge_set_graph,
1262                           typename _Graph::
1263                           NodeMap<typename _EdgeSetGraph::Node>& _e_node,
1264                           typename _EdgeSetGraph::
1265                           NodeMap<typename _Graph::Node>& _n_node) {
1266      setGraph(_graph);
1267      setEdgeSetGraph(_edge_set_graph);
1268      setNodeMap(_n_node);
1269      setENodeMap(_e_node);
1270    }
1271  };
1272
1273  /*! A graph wrapper class for the following functionality.
1274    The same as NewEdgeSetGrapWrapper, but the bijection and the graph of
1275    new edges is andled inthe class.
1276   */
1277  template <typename _Graph, typename _EdgeSetGraph>
1278  class NewEdgeSetGraphWrapper2 :
1279    public IterableGraphExtender<
1280    NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
1281  public:
1282    typedef _Graph Graph;
1283    typedef _EdgeSetGraph EdgeSetGraph;
1284    typedef IterableGraphExtender<
1285      NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
1286  protected:
1287    _EdgeSetGraph _edge_set_graph;
1288    typename Graph::template NodeMap<typename EdgeSetGraph::Node> _e_node;
1289    typename EdgeSetGraph::template NodeMap<typename Graph::Node> _n_node;
1290    NewEdgeSetGraphWrapper2() { }
1291  public:
1292    typedef typename Graph::Node Node;
1293    //    typedef typename Parent::Edge Edge;
1294
1295    NewEdgeSetGraphWrapper2(_Graph& _graph) :
1296      _edge_set_graph(),
1297      _e_node(_graph), _n_node(_edge_set_graph) {
1298      setGraph(_graph);
1299      setEdgeSetGraph(_edge_set_graph);
1300      setNodeMap(_n_node); setENodeMap(_e_node);
1301      Node n;
1302      for (this->first(n); n!=INVALID; this->next(n)) {
1303        typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
1304        _e_node.set(n, e);
1305        _n_node.set(e, n);
1306      }
1307    }
1308
1309//     Node addNode() {
1310//       Node n=(*this).Parent::addNode();
1311//       typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
1312//       _e_node.set(n, e);
1313//       _n_node.set(e, n);
1314//       return n;
1315//     }
1316
1317  };
1318
1319  /*! A graph wrapper base class
1320    for merging graphs of type _Graph1 and _Graph2
1321    which are given on the same node-set
1322    (specially on the node-set of Graph1)
1323    into one graph.
1324    In an other point of view, _Graph1 is extended with
1325    the edge-set of _Graph2.
1326    \warning we need specialize dimplementations
1327    \todo we need specialize dimplementations
1328    \bug we need specialize dimplementations
1329   */
1330  template <typename _Graph1, typename _Graph2, typename Enable=void>
1331  class AugmentingGraphWrapperBase :
1332    public P1<_Graph1> {
1333  public:
1334    void printAugment() const { std::cout << "generic" << std::endl; }
1335    typedef _Graph1 Graph1;
1336    typedef _Graph2 Graph2;
1337    typedef P1<_Graph1> Parent1;
1338    typedef P2<_Graph2> Parent2;
1339    typedef typename Parent1::Edge Graph1Edge;
1340    typedef typename Parent2::Edge Graph2Edge;
1341  protected:
1342    AugmentingGraphWrapperBase() { }
1343    _Graph2* graph2;
1344    void setGraph2(_Graph2& _graph2) { graph2=&_graph2; }
1345  public:
1346   
1347    template <typename _Value> class EdgeMap;
1348
1349    typedef typename Parent1::Node Node;
1350
1351    class Edge : public Graph1Edge, public Graph2Edge {
1352      friend class AugmentingGraphWrapperBase<_Graph1, _Graph2>;
1353      template <typename _Value> friend class EdgeMap;
1354    protected:
1355      bool backward; //true, iff backward
1356    public:
1357      Edge() { }
1358      /// \todo =false is needed, or causes problems?
1359      /// If \c _backward is false, then we get an edge corresponding to the
1360      /// original one, otherwise its oppositely directed pair is obtained.
1361      Edge(const Graph1Edge& n1,
1362           const Graph2Edge& n2, bool _backward) :
1363        Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
1364      Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
1365      bool operator==(const Edge& v) const {
1366        if (backward)
1367          return (v.backward &&
1368                  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
1369        else
1370          return (!v.backward &&
1371                  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
1372      }
1373      bool operator!=(const Edge& v) const {
1374        return !(*this==v);
1375      }
1376    };
1377
1378    using Parent1::first;
1379    void first(Edge& i) const {
1380      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
1381      i.backward=false;
1382      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1383        graph2->first(*static_cast<Graph2Edge*>(&i));
1384        i.backward=true;
1385      }
1386    }
1387    void firstIn(Edge& i, const Node& n) const {
1388      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
1389      i.backward=false;
1390      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1391        graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
1392        i.backward=true;
1393      }
1394    }
1395    void firstOut(Edge& i, const Node& n) const {
1396      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
1397      i.backward=false;
1398      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1399        graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
1400        i.backward=true;
1401      }
1402    }
1403
1404    using Parent1::next;
1405    void next(Edge& i) const {
1406      if (!(i.backward)) {
1407        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
1408        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1409          graph2->first(*static_cast<Graph2Edge*>(&i));
1410          i.backward=true;
1411        }
1412      } else {
1413        graph2->next(*static_cast<Graph2Edge*>(&i));
1414      }
1415    }
1416    void nextIn(Edge& i) const {
1417      if (!(i.backward)) {
1418        Node n=target(i);
1419        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
1420        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1421          graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
1422          i.backward=true;
1423        }
1424      } else {
1425        graph2->nextIn(*static_cast<Graph2Edge*>(&i));
1426      }
1427    }
1428    void nextOut(Edge& i) const {
1429      if (!(i.backward)) {
1430        Node n=source(i);
1431        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
1432        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1433          graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
1434          i.backward=true;
1435        }
1436      } else {
1437        graph2->nextOut(*static_cast<Graph2Edge*>(&i));
1438      }
1439    }
1440
1441    Node source(const Edge& i) const {
1442      if (!(i.backward)) {
1443        return Parent1::graph->source(i);
1444      } else {
1445        return graph2->source(i);
1446      }
1447    }
1448
1449    Node target(const Edge& i) const {
1450      if (!(i.backward)) {
1451        return Parent1::graph->target(i);
1452      } else {
1453        return graph2->target(i);
1454      }
1455    }
1456
1457    int id(const Node& n) const {
1458      return Parent1::id(n);
1459    };
1460    int id(const Edge& n) const {
1461      if (!n.backward)
1462        return this->Parent1::graph->id(n);
1463      else
1464        return this->graph2->id(n);
1465    }
1466
1467    template <typename _Value>
1468    class EdgeMap {
1469    protected:
1470      typedef typename _Graph1::template EdgeMap<_Value> ParentMap1;
1471      typedef typename _Graph2::template EdgeMap<_Value> ParentMap2;
1472      ParentMap1 forward_map;
1473      ParentMap2 backward_map;
1474    public:
1475      typedef _Value Value;
1476      typedef Edge Key;
1477      EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw) :
1478        forward_map(*(gw.Parent1::graph)),
1479        backward_map(*(gw.graph2)) { }
1480      EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw,
1481              const _Value& value) :
1482        forward_map(*(gw.Parent1::graph), value),
1483        backward_map(*(gw.graph2), value) { }
1484      _Value operator[](const Edge& n) const {
1485        if (!n.backward)
1486          return forward_map[n];
1487        else
1488          return backward_map[n];
1489      }
1490      void set(const Edge& n, const _Value& value) {
1491        if (!n.backward)
1492          forward_map.set(n, value);
1493        else
1494          backward_map.set(n, value);
1495      }
1496//       using ParentMap1::operator[];
1497//       using ParentMap2::operator[];
1498    };
1499
1500  };
1501
1502
1503  /*! A graph wrapper class
1504    for merging two graphs (of type _Graph1 and _Graph2)
1505    with the same node-set
1506    (specially on the node-set of Graph1)
1507    into one graph.
1508    In an other point of view, _Graph1 is extended with
1509    the edge-set of _Graph2.
1510   */ 
1511  template <typename _Graph1, typename _Graph2>
1512  class AugmentingGraphWrapper : public
1513  IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > {
1514  public:
1515    typedef
1516    IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> >
1517    Parent;
1518    typedef _Graph1 Graph1;
1519    typedef _Graph2 Graph2;
1520  protected:
1521    AugmentingGraphWrapper() { }
1522  public:
1523    AugmentingGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
1524      setGraph(_graph1);
1525      setGraph2(_graph2);
1526    }
1527  };
1528
1529} //namespace lemon
1530
1531#endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.