COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/merge_node_graph_wrapper.h @ 1013:b3bdd856faf4

Last change on this file since 1013:b3bdd856faf4 was 1013:b3bdd856faf4, checked in by marci, 16 years ago

MergeGraphWrapper?

File size: 32.2 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 are base and derived _Graph2::Node.
274    NOT YET IMPLEMENTED
275   */
276  template <typename _Graph1, typename _Graph2>
277  class MergeNodeGraphWrapperBase<
278    _Graph1, _Graph2, typename boost::enable_if<
279    boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> :
280    public P1<_Graph1>, public P2<_Graph2> {
281  public :
282    static void printNode() { std::cout << "node: 2nd is derived" << std::endl; }
283    typedef _Graph1 Graph1;
284    typedef _Graph2 Graph2;
285    typedef P1<_Graph1> Parent1;
286    typedef P2<_Graph2> Parent2;
287    typedef typename Parent1::Node Graph1Node;
288    typedef typename Parent2::Node Graph2Node;
289  protected:
290    MergeNodeGraphWrapperBase() { }
291  public:
292    class Node { };
293    class Edge { };
294    void first() const;
295    void next() const;
296  };
297
298  //not yet working
299  template <typename _Graph1, typename _Graph2>
300  class MergeNodeGraphWrapperBase<
301    _Graph1, _Graph2, typename boost::enable_if<
302    boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> :
303    public P1<_Graph1>, public P2<_Graph2> {
304  public :
305    static void printNode() { std::cout << "node: 1st is derived" << std::endl; }
306    typedef _Graph1 Graph1;
307    typedef _Graph2 Graph2;
308    typedef P1<_Graph1> Parent1;
309    typedef P2<_Graph2> Parent2;
310    typedef typename Parent1::Node Graph1Node;
311    typedef typename Parent2::Node Graph2Node;
312  protected:
313    MergeNodeGraphWrapperBase() { }
314  public:
315    class Node { };
316    class Edge { };
317    void first() const;
318    void next() const;
319  };
320
321
322  /*! A graph wrapper class
323    fors merging the node-set of two node-disjoint graphs
324    into one node-set. It does not satisfy
325    StaticGraph concept as it has no edge-set which
326    works together with the node-set.
327   */
328  template <typename _Graph1, typename _Graph2>
329  class MergeNodeGraphWrapper : public
330  IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
331  public:
332    typedef _Graph1 Graph1;
333    typedef _Graph2 Graph2;
334    typedef IterableGraphExtender<
335      MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
336  protected:
337    MergeNodeGraphWrapper() { }
338  public:
339    MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
340      Parent::Parent1::setGraph(_graph1);
341      Parent::Parent2::setGraph(_graph2);
342    }
343  };
344
345
346  /*! A grah wrapper base class
347    for merging the node-sets and edge-sets of
348    two node-disjoint graphs
349    into one graph.
350    Generic implementation for unrelated _Graph1::Edge and _Graph2::Edge.
351   */
352  template <typename _Graph1, typename _Graph2, typename Enable=void>
353  class MergeEdgeGraphWrapperBase :
354    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
355  public:
356    static void printEdge() { std::cout << "edge: generic" << std::endl; }
357    typedef _Graph1 Graph1;
358    typedef _Graph2 Graph2;
359    typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
360    typedef typename Parent::Parent1 Parent1;
361    typedef typename Parent::Parent2 Parent2;
362//     typedef P1<_Graph1> Parent1;
363//     typedef P2<_Graph2> Parent2;
364    typedef typename Parent1::Edge Graph1Edge;
365    typedef typename Parent2::Edge Graph2Edge;
366  protected:
367    MergeEdgeGraphWrapperBase() { }
368  public:
369    template <typename _Value> class EdgeMap;
370
371    typedef typename Parent::Node Node;
372
373    class Edge : public Graph1Edge, public Graph2Edge {
374      friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
375      template <typename _Value> friend class EdgeMap;
376    protected:
377      bool backward; //true, iff backward
378    public:
379      Edge() { }
380      /// \todo =false is needed, or causes problems?
381      /// If \c _backward is false, then we get an edge corresponding to the
382      /// original one, otherwise its oppositely directed pair is obtained.
383      Edge(const Graph1Edge& n1,
384           const Graph2Edge& n2, bool _backward) :
385        Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
386      Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
387      bool operator==(const Edge& v) const {
388        if (backward)
389          return (v.backward &&
390                  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
391        else
392          return (!v.backward &&
393                  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
394      }
395      bool operator!=(const Edge& v) const {
396        return !(*this==v);
397      }
398    };
399
400    using Parent::first;
401    void first(Edge& i) const {
402      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
403      i.backward=false;
404      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
405        Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
406        i.backward=true;
407      }
408    }
409    void firstIn(Edge& i, const Node& n) const {
410      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
411      i.backward=false;
412      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
413        Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
414        i.backward=true;
415      }
416    }
417    void firstOut(Edge& i, const Node& n) const {
418      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
419      i.backward=false;
420      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
421        Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
422        i.backward=true;
423      }
424    }
425
426    using Parent::next;
427    void next(Edge& i) const {
428      if (!(i.backward)) {
429        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
430        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
431          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
432          i.backward=true;
433        }
434      } else {
435        Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
436      }
437    }
438    void nextIn(Edge& i) const {
439      if (!(i.backward)) {
440        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
441        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
442          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
443          i.backward=true;
444        }
445      } else {
446        Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
447      }
448    }
449    void nextOut(Edge& i) const {
450      if (!(i.backward)) {
451        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
452        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
453          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
454          i.backward=true;
455        }
456      } else {
457        Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
458      }
459    }
460
461    Node source(const Edge& i) const {
462      if (!(i.backward)) {
463        return
464          Node(Parent1::graph->source(i), INVALID, false);
465      } else {
466        return
467          Node(INVALID, Parent2::graph->source(i), true);
468      }
469    }
470
471    Node target(const Edge& i) const {
472      if (!(i.backward)) {
473        return
474          Node(Parent1::graph->target(i), INVALID, false);
475      } else {
476        return
477          Node(INVALID, Parent2::graph->target(i), true);
478      }
479    }
480
481    using Parent::id;
482    int id(const Edge& n) const {
483      if (!n.backward)
484        return this->Parent1::graph->id(n);
485      else
486        return this->Parent2::graph->id(n);
487    }
488
489    template <typename _Value>
490    class EdgeMap {
491    protected:
492      typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
493      typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
494      ParentMap1 forward_map;
495      ParentMap2 backward_map;
496    public:
497      typedef _Value Value;
498      typedef Edge Key;
499      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
500        forward_map(*(gw.Parent1::graph)),
501        backward_map(*(gw.Parent2::graph)) { }
502      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
503              const _Value& value) :
504        forward_map(*(gw.Parent1::graph), value),
505        backward_map(*(gw.Parent2::graph), value) { }
506      _Value operator[](const Edge& n) const {
507        if (!n.backward)
508          return forward_map[n];
509        else
510          return backward_map[n];
511      }
512      void set(const Edge& n, const _Value& value) {
513        if (!n.backward)
514          forward_map.set(n, value);
515        else
516          backward_map.set(n, value);
517      }
518//       using ParentMap1::operator[];
519//       using ParentMap2::operator[];
520    };
521
522  };
523
524
525  /*! A graph wrapper base class
526    for merging the node-sets and edge-sets of
527    two node-disjoint graphs
528    into one graph.
529    Specialization for the case when _Graph1::Edge and _Graph2::Edge
530    are the same.
531   */
532  template <typename _Graph1, typename _Graph2>
533  class MergeEdgeGraphWrapperBase<
534    _Graph1, _Graph2, typename boost::enable_if<
535    boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
536    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
537  public:
538    static void printEdge() { std::cout << "edge: same" << std::endl; }
539    typedef _Graph1 Graph1;
540    typedef _Graph2 Graph2;
541    typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
542    typedef typename Parent::Parent1 Parent1;
543    typedef typename Parent::Parent2 Parent2;
544//     typedef P1<_Graph1> Parent1;
545//     typedef P2<_Graph2> Parent2;
546    typedef typename Parent1::Edge Graph1Edge;
547    typedef typename Parent2::Edge Graph2Edge;
548  protected:
549    MergeEdgeGraphWrapperBase() { }
550  public:
551    template <typename _Value> class EdgeMap;
552
553    typedef typename Parent::Node Node;
554
555    class Edge : public Graph1Edge {
556      friend class MergeEdgeGraphWrapperBase<_Graph1, _Graph2>;
557      template <typename _Value> friend class EdgeMap;
558    protected:
559      bool backward; //true, iff backward
560    public:
561      Edge() { }
562      /// \todo =false is needed, or causes problems?
563      /// If \c _backward is false, then we get an edge corresponding to the
564      /// original one, otherwise its oppositely directed pair is obtained.
565      Edge(const Graph1Edge& n1,
566           const Graph2Edge& n2, bool _backward) :
567        Graph1Edge(!backward ? n1 : n2), backward(_backward) { }
568      Edge(Invalid i) : Graph1Edge(i), backward(true) { }
569      bool operator==(const Edge& v) const {
570        return (backward==v.backward &&
571                static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
572      }
573      bool operator!=(const Edge& v) const {
574        return !(*this==v);
575      }
576    };
577
578    using Parent::first;
579    void first(Edge& i) const {
580      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
581      i.backward=false;
582      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
583        Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
584        i.backward=true;
585      }
586    }
587    void firstIn(Edge& i, const Node& n) const {
588      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
589      i.backward=false;
590      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
591        Parent2::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
592        i.backward=true;
593      }
594    }
595    void firstOut(Edge& i, const Node& n) const {
596      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
597      i.backward=false;
598      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
599        Parent2::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
600        i.backward=true;
601      }
602    }
603
604    using Parent::next;
605    void next(Edge& i) const {
606      if (!(i.backward)) {
607        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
608        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
609          Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
610          i.backward=true;
611        }
612      } else {
613        Parent2::graph->next(*static_cast<Graph1Edge*>(&i));
614      }
615    }
616    void nextIn(Edge& i) const {
617      if (!(i.backward)) {
618        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
619        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
620          Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
621          i.backward=true;
622        }
623      } else {
624        Parent2::graph->nextIn(*static_cast<Graph1Edge*>(&i));
625      }
626    }
627    void nextOut(Edge& i) const {
628      if (!(i.backward)) {
629        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
630        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
631          Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
632          i.backward=true;
633        }
634      } else {
635        Parent2::graph->nextOut(*static_cast<Graph1Edge*>(&i));
636      }
637    }
638
639    Node source(const Edge& i) const {
640      if (!(i.backward)) {
641        return
642          Node(Parent1::graph->source(i), INVALID, false);
643      } else {
644        return
645          Node(INVALID, Parent2::graph->source(i), true);
646      }
647    }
648
649    Node target(const Edge& i) const {
650      if (!(i.backward)) {
651        return
652          Node(Parent1::graph->target(i), INVALID, false);
653      } else {
654        return
655          Node(INVALID, Parent2::graph->target(i), true);
656      }
657    }
658
659    using Parent::id;
660    int id(const Edge& n) const {
661      if (!n.backward)
662        return this->Parent1::graph->id(n);
663      else
664        return this->Parent2::graph->id(n);
665    }
666
667    template <typename _Value>
668    class EdgeMap {
669    protected:
670      typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
671      typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
672      ParentMap1 forward_map;
673      ParentMap2 backward_map;
674    public:
675      typedef _Value Value;
676      typedef Edge Key;
677      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
678        forward_map(*(gw.Parent1::graph)),
679        backward_map(*(gw.Parent2::graph)) { }
680      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
681              const _Value& value) :
682        forward_map(*(gw.Parent1::graph), value),
683        backward_map(*(gw.Parent2::graph), value) { }
684      _Value operator[](const Edge& n) const {
685        if (!n.backward)
686          return forward_map[n];
687        else
688          return backward_map[n];
689      }
690      void set(const Edge& n, const _Value& value) {
691        if (!n.backward)
692          forward_map.set(n, value);
693        else
694          backward_map.set(n, value);
695      }
696//       using ParentMap1::operator[];
697//       using ParentMap2::operator[];
698    };
699
700  };
701
702
703  /*! A graph wrapper class
704    for merging the node-sets and edge-sets of
705    two node-disjoint graphs
706    into one graph.
707   */
708  template <typename _Graph1, typename _Graph2>
709  class MergeEdgeGraphWrapper : public
710  IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
711  public:
712    typedef _Graph1 Graph1;
713    typedef _Graph2 Graph2;
714    typedef IterableGraphExtender<
715      MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
716  protected:
717    MergeEdgeGraphWrapper() { }
718  public:
719    MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
720      Parent::Parent1::setGraph(_graph1);
721      Parent::Parent2::setGraph(_graph2);
722    }
723  };
724
725 
726  /*! A graph wrapper base class for the following functionality.
727    If a bijection is given between the node-sets of two graphs,
728    then the second one can be considered as a new edge-set
729    over th first node-set.
730   */
731  template <typename _Graph, typename _EdgeSetGraph>
732  class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
733  public:
734    typedef GraphWrapperBase<_Graph> Parent;
735    typedef _Graph Graph;
736    typedef _EdgeSetGraph EdgeSetGraph;
737    typedef typename _Graph::Node Node;
738    typedef typename _EdgeSetGraph::Node ENode;
739  protected:
740    EdgeSetGraph* edge_set_graph;
741    typename Graph::NodeMap<ENode>* e_node;
742    typename EdgeSetGraph::NodeMap<Node>* n_node;
743    void setEdgeSetGraph(EdgeSetGraph& _edge_set_graph) {
744      edge_set_graph=&_edge_set_graph;
745    }
746    /// For each node of \c Graph, this gives a node of \c EdgeSetGraph .
747    void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) {
748      n_node=&_n_node;
749    }
750    /// For each node of \c EdgeSetGraph, this gives a node of \c Graph .
751    void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) {
752      e_node=&_e_node;
753    }
754  public:
755    class Edge : public EdgeSetGraph::Edge {
756      typedef typename EdgeSetGraph::Edge Parent;
757    public:
758      Edge() { }
759      Edge(const Parent& e) : Parent(e) { }
760      Edge(Invalid i) : Parent(i) { }
761    };
762
763    using Parent::first;
764    void first(Edge &e) const {
765      edge_set_graph->first(e);
766    }
767    void firstOut(Edge& e, const Node& n) const {
768//       cout << e_node << endl;
769//       cout << n_node << endl;
770      edge_set_graph->firstOut(e, (*e_node)[n]);
771    }
772    void firstIn(Edge& e, const Node& n) const {
773      edge_set_graph->firstIn(e, (*e_node)[n]);
774    }
775
776    using Parent::next;
777    void next(Edge &e) const {
778      edge_set_graph->next(e);
779    }
780    void nextOut(Edge& e) const {
781      edge_set_graph->nextOut(e);
782    }
783    void nextIn(Edge& e) const {
784      edge_set_graph->nextIn(e);
785    }
786
787    Node source(const Edge& e) const {
788      return (*n_node)[edge_set_graph->source(e)];
789    }
790    Node target(const Edge& e) const {
791      return (*n_node)[edge_set_graph->target(e)];
792    }
793
794    int edgeNum() const { return edge_set_graph->edgeNum(); }
795
796    Edge addEdge(const Node& u, const Node& v) {
797      return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
798    }
799
800    using Parent::erase;
801    void erase(const Edge& i) const { edge_set_graph->erase(i); }
802 
803    void clear() const { Parent::clear(); edge_set_graph->clear(); }
804
805    bool forward(const Edge& e) const { return edge_set_graph->forward(e); }
806    bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
807
808    int id(const Node& e) const { return Parent::id(e); }
809    int id(const Edge& e) const { return edge_set_graph->id(e); }
810   
811    Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
812
813    template <typename _Value>
814    class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {
815    public:
816      typedef typename EdgeSetGraph::EdgeMap<_Value> Parent;
817      typedef _Value Value;
818      typedef Edge Key;
819      EdgeMap(const NewEdgeSetGraphWrapperBase& gw) :
820        Parent(*(gw.edge_set_graph)) { }
821      EdgeMap(const NewEdgeSetGraphWrapperBase& gw, const _Value& _value) :
822        Parent(*(gw.edge_set_graph), _value) { }
823    };
824
825  };
826
827
828  /*! A graph wrapper class for the following functionality.
829    If a bijection is given between the node-sets of two graphs,
830    then the second one can be considered as a new edge-set
831    over th first node-set.
832   */
833  template <typename _Graph, typename _EdgeSetGraph>
834  class NewEdgeSetGraphWrapper :
835    public IterableGraphExtender<
836    NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
837  public:
838    typedef _Graph Graph;
839    typedef _EdgeSetGraph EdgeSetGraph;
840    typedef IterableGraphExtender<
841      NewEdgeSetGraphWrapper<_Graph, _EdgeSetGraph> > Parent;
842  protected:
843    NewEdgeSetGraphWrapper() { }
844  public:
845    NewEdgeSetGraphWrapper(_Graph& _graph,
846                           _EdgeSetGraph& _edge_set_graph,
847                           typename _Graph::
848                           NodeMap<typename _EdgeSetGraph::Node>& _e_node,
849                           typename _EdgeSetGraph::
850                           NodeMap<typename _Graph::Node>& _n_node) {
851      setGraph(_graph);
852      setEdgeSetGraph(_edge_set_graph);
853      setNodeMap(_n_node);
854      setENodeMap(_e_node);
855    }
856  };
857
858
859  /*! A graph wrapper base class
860    for merging graphs of type _Graph1 and _Graph2
861    which are given on the same node-set
862    (specially on the node-set of Graph1)
863    into one graph.
864    In an other point of view, _Graph1 is extended with
865    the edge-set of _Graph2.
866   */
867  template <typename _Graph1, typename _Graph2, typename Enable=void>
868  class AugmentingGraphWrapperBase :
869    public P1<_Graph1> {
870  public:
871    void printAugment() const { std::cout << "generic" << std::endl; }
872    typedef _Graph1 Graph1;
873    typedef _Graph2 Graph2;
874    typedef P1<_Graph1> Parent1;
875    typedef P2<_Graph2> Parent2;
876    typedef typename Parent1::Edge Graph1Edge;
877    typedef typename Parent2::Edge Graph2Edge;
878  protected:
879    AugmentingGraphWrapperBase() { }
880    _Graph2* graph2;
881    void setGraph2(_Graph2& _graph2) { graph2=&_graph2; }
882  public:
883   
884    template <typename _Value> class EdgeMap;
885
886    typedef typename Parent1::Node Node;
887
888    class Edge : public Graph1Edge, public Graph2Edge {
889      friend class AugmentingGraphWrapperBase<_Graph1, _Graph2>;
890      template <typename _Value> friend class EdgeMap;
891    protected:
892      bool backward; //true, iff backward
893    public:
894      Edge() { }
895      /// \todo =false is needed, or causes problems?
896      /// If \c _backward is false, then we get an edge corresponding to the
897      /// original one, otherwise its oppositely directed pair is obtained.
898      Edge(const Graph1Edge& n1,
899           const Graph2Edge& n2, bool _backward) :
900        Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
901      Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
902      bool operator==(const Edge& v) const {
903        if (backward)
904          return (v.backward &&
905                  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
906        else
907          return (!v.backward &&
908                  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
909      }
910      bool operator!=(const Edge& v) const {
911        return !(*this==v);
912      }
913    };
914
915    using Parent1::first;
916    void first(Edge& i) const {
917      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
918      i.backward=false;
919      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
920        graph2->first(*static_cast<Graph2Edge*>(&i));
921        i.backward=true;
922      }
923    }
924    void firstIn(Edge& i, const Node& n) const {
925      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
926      i.backward=false;
927      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
928        graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
929        i.backward=true;
930      }
931    }
932    void firstOut(Edge& i, const Node& n) const {
933      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
934      i.backward=false;
935      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
936        graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
937        i.backward=true;
938      }
939    }
940
941    using Parent1::next;
942    void next(Edge& i) const {
943      if (!(i.backward)) {
944        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
945        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
946          graph2->first(*static_cast<Graph2Edge*>(&i));
947          i.backward=true;
948        }
949      } else {
950        graph2->next(*static_cast<Graph2Edge*>(&i));
951      }
952    }
953    void nextIn(Edge& i) const {
954      if (!(i.backward)) {
955        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
956        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
957          graph2->first(*static_cast<Graph2Edge*>(&i));
958          i.backward=true;
959        }
960      } else {
961        graph2->nextIn(*static_cast<Graph2Edge*>(&i));
962      }
963    }
964    void nextOut(Edge& i) const {
965      if (!(i.backward)) {
966        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
967        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
968          graph2->first(*static_cast<Graph2Edge*>(&i));
969          i.backward=true;
970        }
971      } else {
972        graph2->nextOut(*static_cast<Graph2Edge*>(&i));
973      }
974    }
975
976    Node source(const Edge& i) const {
977      if (!(i.backward)) {
978        return Parent1::graph->source(i);
979      } else {
980        return graph2->source(i);
981      }
982    }
983
984    Node target(const Edge& i) const {
985      if (!(i.backward)) {
986        return Parent1::graph->target(i);
987      } else {
988        return graph2->target(i);
989      }
990    }
991
992    int id(const Node& n) const {
993      return Parent1::id(n);
994    };
995    int id(const Edge& n) const {
996      if (!n.backward)
997        return this->Parent1::graph->id(n);
998      else
999        return this->graph2->id(n);
1000    }
1001
1002    template <typename _Value>
1003    class EdgeMap {
1004    protected:
1005      typedef typename _Graph1::template EdgeMap<_Value> ParentMap1;
1006      typedef typename _Graph2::template EdgeMap<_Value> ParentMap2;
1007      ParentMap1 forward_map;
1008      ParentMap2 backward_map;
1009    public:
1010      typedef _Value Value;
1011      typedef Edge Key;
1012      EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw) :
1013        forward_map(*(gw.Parent1::graph)),
1014        backward_map(*(gw.graph2)) { }
1015      EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw,
1016              const _Value& value) :
1017        forward_map(*(gw.Parent1::graph), value),
1018        backward_map(*(gw.graph2), value) { }
1019      _Value operator[](const Edge& n) const {
1020        if (!n.backward)
1021          return forward_map[n];
1022        else
1023          return backward_map[n];
1024      }
1025      void set(const Edge& n, const _Value& value) {
1026        if (!n.backward)
1027          forward_map.set(n, value);
1028        else
1029          backward_map.set(n, value);
1030      }
1031//       using ParentMap1::operator[];
1032//       using ParentMap2::operator[];
1033    };
1034
1035  };
1036
1037
1038  /*! A graph wrapper class
1039    for merging two graphs (of type _Graph1 and _Graph2)
1040    with the same node-set
1041    (specially on the node-set of Graph1)
1042    into one graph.
1043    In an other point of view, _Graph1 is extended with
1044    the edge-set of _Graph2.
1045   */ 
1046  template <typename _Graph1, typename _Graph2>
1047  class AugmentingGraphWrapper : public
1048  IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > {
1049  public:
1050    typedef
1051    IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> >
1052    Parent;
1053    typedef _Graph1 Graph1;
1054    typedef _Graph2 Graph2;
1055  protected:
1056    AugmentingGraphWrapper() { }
1057  public:
1058    AugmentingGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
1059      setGraph(_graph1);
1060      setGraph2(_graph2);
1061    }
1062  };
1063
1064} //namespace lemon
1065
1066#endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.