COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/merge_node_graph_wrapper.h @ 1016:18d009b23e42

Last change on this file since 1016:18d009b23e42 was 1016:18d009b23e42, checked in by marci, 19 years ago

bug fix in SubBidirGraphWrapper?, roadmap to MergeGraphWrapper?

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