COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/merge_node_graph_wrapper.h @ 1359:1581f961cfaa

Last change on this file since 1359:1581f961cfaa was 1359:1581f961cfaa, checked in by Alpar Juttner, 15 years ago

Correct the english name of EGRES.

File size: 38.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) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_MERGE_NODE_GRAPH_WRAPPER_H
18#define LEMON_MERGE_NODE_GRAPH_WRAPPER_H
19
20#include <lemon/invalid.h>
21#include <lemon/maps.h>
22#include <lemon/map_defines.h>
23#include <lemon/graph_wrapper.h>
24#include <iostream>
25
26using std::cout;
27using std::endl;
28
29#include <boost/type_traits.hpp>
30#include <boost/utility/enable_if.hpp>
31
32namespace lemon {
33
34  template <class _Graph1>
35  class P1 : public GraphWrapperBase<_Graph1> {
36  };
37
38  template <class _Graph2>
39  class P2 : public GraphWrapperBase<_Graph2> {
40  };
41
42
43  template <typename _Graph1, typename _Graph2, typename Enable=void>
44  class MergeNodeGraphWrapperBaseBase :
45    public P1<_Graph1>, public P2<_Graph2> {
46  public:
47    static void printNode() { std::cout << "node: generic" << std::endl; }
48    typedef _Graph1 Graph1;
49    typedef _Graph2 Graph2;
50    typedef P1<_Graph1> Parent1;
51    typedef P2<_Graph2> Parent2;
52    typedef typename Parent1::Node Graph1Node;
53    typedef typename Parent2::Node Graph2Node;
54  protected:
55    MergeNodeGraphWrapperBaseBase() { }
56  public:
57
58    class Node : public Graph1Node, public Graph2Node {
59      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
60    protected:
61      bool backward; //true, iff backward
62    public:
63      Node() { }
64      /// \todo =false is needed, or causes problems?
65      /// If \c _backward is false, then we get an edge corresponding to the
66      /// original one, otherwise its oppositely directed pair is obtained.
67      Node(const Graph1Node& n1,
68           const Graph2Node& n2, bool _backward) :
69        Graph1Node(n1), Graph2Node(n2), backward(_backward) { }
70      Node(Invalid i) : Graph1Node(i), Graph2Node(i), backward(true) { }
71      bool operator==(const Node& v) const {
72        if (backward)
73          return (v.backward &&
74                  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
75        else
76          return (!v.backward &&
77                  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
78      }
79      bool operator!=(const Node& v) const {
80        return !(*this==v);
81      }
82    };
83
84    static bool forward(const Node& n) { return !n.backward; }
85    static bool backward(const Node& n) { return n.backward; }
86    static void setForward(Node& n) { n.backward=false; }
87    static void setBackward(Node& n) { n.backward=true; }   
88  };
89
90
91  template <typename _Graph1, typename _Graph2>
92  class MergeNodeGraphWrapperBaseBase<
93    _Graph1, _Graph2, typename boost::enable_if<
94    boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
95    public P1<_Graph1>, public P2<_Graph2> {
96  public:
97    static void printNode() { std::cout << "node: same" << std::endl; }
98    typedef _Graph1 Graph1;
99    typedef _Graph2 Graph2;
100    typedef P1<_Graph1> Parent1;
101    typedef P2<_Graph2> Parent2;
102    typedef typename Parent1::Node Graph1Node;
103    typedef typename Parent2::Node Graph2Node;
104  protected:
105    MergeNodeGraphWrapperBaseBase() { }
106  public:
107
108    class Node : public Graph1Node {
109      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
110    protected:
111      bool backward; //true, iff backward
112    public:
113      Node() { }
114      /// \todo =false is needed, or causes problems?
115      /// If \c _backward is false, then we get an edge corresponding to the
116      /// original one, otherwise its oppositely directed pair is obtained.
117      Node(const Graph1Node& n1,
118           const Graph2Node& n2, bool _backward) :
119        Graph1Node(!_backward ? n1 : n2), backward(_backward) { }
120      Node(Invalid i) : Graph1Node(i), backward(true) { }
121      bool operator==(const Node& v) const {
122        return (backward==v.backward &&
123                static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
124      }
125      bool operator!=(const Node& v) const {
126        return !(*this==v);
127      }
128    };
129
130    static bool forward(const Node& n) { return !n.backward; }
131    static bool backward(const Node& n) { return n.backward; }
132    static void setForward(Node& n) { n.backward=false; }
133    static void setBackward(Node& n) { n.backward=true; }
134  };
135
136
137  template <typename _Graph1, typename _Graph2>
138  class MergeNodeGraphWrapperBaseBase<
139    _Graph1, _Graph2, typename boost::enable_if<
140    boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> :
141    public P1<_Graph1>, public P2<_Graph2> {
142  public :
143    static void printNode() { std::cout << "node: 2nd is derived" << std::endl; }
144    typedef _Graph1 Graph1;
145    typedef _Graph2 Graph2;
146    typedef P1<_Graph1> Parent1;
147    typedef P2<_Graph2> Parent2;
148    typedef typename Parent1::Node Graph1Node;
149    typedef typename Parent2::Node Graph2Node;
150  protected:
151    MergeNodeGraphWrapperBaseBase() { }
152  public:
153
154    class Node : public Graph2Node {
155      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
156    protected:
157      bool backward; //true, iff backward
158    public:
159      Node() { }
160      /// \todo =false is needed, or causes problems?
161      /// If \c _backward is false, then we get an edge corresponding to the
162      /// original one, otherwise its oppositely directed pair is obtained.
163      Node(const Graph1Node& n1,
164           const Graph2Node& n2, bool _backward) :
165        Graph2Node(n2), backward(_backward) {
166        if (!backward) *this=n1;
167      }
168      Node(Invalid i) : Graph2Node(i), backward(true) { }
169      bool operator==(const Node& v) const {
170        if (backward)
171          return (v.backward &&
172                  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
173        else
174          return (!v.backward &&
175                  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
176      }
177      bool operator!=(const Node& v) const {
178        return !(*this==v);
179      }
180    };
181
182    static bool forward(const Node& n) { return !n.backward; }
183    static bool backward(const Node& n) { return n.backward; }
184    static void setForward(Node& n) { n.backward=false; }
185    static void setBackward(Node& n) { n.backward=true; }
186  };
187 
188
189  template <typename _Graph1, typename _Graph2>
190  class MergeNodeGraphWrapperBaseBase<
191    _Graph1, _Graph2, typename boost::enable_if<
192    boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> :
193    public P1<_Graph1>, public P2<_Graph2> {
194  public :
195    static void printNode() { std::cout << "node: 1st is derived" << std::endl; }
196    typedef _Graph1 Graph1;
197    typedef _Graph2 Graph2;
198    typedef P1<_Graph1> Parent1;
199    typedef P2<_Graph2> Parent2;
200    typedef typename Parent1::Node Graph1Node;
201    typedef typename Parent2::Node Graph2Node;
202  protected:
203    MergeNodeGraphWrapperBaseBase() { }
204  public:
205
206    class Node : public Graph1Node {
207      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
208    protected:
209      bool backward; //true, iff backward
210    public:
211      Node() { }
212      /// \todo =false is needed, or causes problems?
213      /// If \c _backward is false, then we get an edge corresponding to the
214      /// original one, otherwise its oppositely directed pair is obtained.
215      Node(const Graph1Node& n1,
216           const Graph2Node& n2, bool _backward) :
217        Graph1Node(n1), backward(_backward) {
218        if (backward) *this=n2;
219      }
220      Node(Invalid i) : Graph1Node(i), backward(true) { }
221      bool operator==(const Node& v) const {
222        if (backward)
223          return (v.backward &&
224                  static_cast<Graph2Node>(*this)==static_cast<Graph2Node>(v));
225        else
226          return (!v.backward &&
227                  static_cast<Graph1Node>(*this)==static_cast<Graph1Node>(v));
228      }
229      bool operator!=(const Node& v) const {
230        return !(*this==v);
231      }
232    };
233
234    static bool forward(const Node& n) { return !n.backward; }
235    static bool backward(const Node& n) { return n.backward; }
236    static void setForward(Node& n) { n.backward=false; }
237    static void setBackward(Node& n) { n.backward=true; }
238  };
239
240
241  template <typename _Graph1, typename _Graph2>
242  class MergeNodeGraphWrapperBase :
243    public MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> {
244  public:
245    typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
246    typedef _Graph1 Graph1;
247    typedef _Graph2 Graph2;
248    typedef P1<_Graph1> Parent1;
249    typedef P2<_Graph2> Parent2;
250    typedef typename Parent1::Node Graph1Node;
251    typedef typename Parent2::Node Graph2Node;
252
253    typedef typename Parent::Node Node;
254    class Edge { };
255   
256    void first(Node& i) const {
257      Parent1::graph->first(*static_cast<Graph1Node*>(&i));
258      this->setForward(i);
259      if (*static_cast<Graph1Node*>(&i)==INVALID) {
260        Parent2::graph->first(*static_cast<Graph2Node*>(&i));
261        this->setBackward(i);
262      }
263    }
264    void next(Node& i) const {
265      if (this->forward(i)) {
266        Parent1::graph->next(*static_cast<Graph1Node*>(&i));
267        if (*static_cast<Graph1Node*>(&i)==INVALID) {
268          Parent2::graph->first(*static_cast<Graph2Node*>(&i));
269          this->setBackward(i);
270        }
271      } else {
272        Parent2::graph->next(*static_cast<Graph2Node*>(&i));
273      }
274    }
275
276    int id(const Node& n) const {
277      if (this->forward(n))
278        return this->Parent1::graph->id(n);
279      else
280        return this->Parent2::graph->id(n);
281    }
282
283    template <typename _Value>
284    class NodeMap {
285    protected:
286      typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
287      typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
288      ParentMap1 forward_map;
289      ParentMap2 backward_map;
290    public:
291      typedef _Value Value;
292      typedef Node Key;
293      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
294        forward_map(*(gw.Parent1::graph)),
295        backward_map(*(gw.Parent2::graph)) { }
296      NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
297              const _Value& value) :
298        forward_map(*(gw.Parent1::graph), value),
299        backward_map(*(gw.Parent2::graph), value) { }
300      _Value operator[](const Node& n) const {
301        if (Parent::forward(n))
302          return forward_map[n];
303        else
304          return backward_map[n];
305      }
306      void set(const Node& n, const _Value& value) {
307        if (Parent::forward(n))
308          forward_map.set(n, value);
309        else
310          backward_map.set(n, value);
311      }
312//       using ParentMap1::operator[];
313//       using ParentMap2::operator[];
314    };
315
316  };
317
318
319  /*! A graph wrapper class
320    for merging the node-set of two node-disjoint graphs
321    into the node-set of one graph.
322    Different implementations are according to the relation of
323    _Graph1::Node and _Graph2::Node.
324    If _Graph1::Node and _Graph2::Node are unrelated, then
325    MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
326    is derived from both.
327    If _Graph1::Node and _Graph2::Node are the same type, then
328    MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
329    is derived from _Graph1::Node.
330    If one of _Graph1::Node and _Graph2::Node
331    is derived from the other one, then
332    MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
333    is derived from the derived type.
334    It does not satisfy
335    StaticGraph concept as it has no edge-set which
336    works together with the node-set.
337  */
338  template <typename _Graph1, typename _Graph2>
339  class MergeNodeGraphWrapper : public
340  IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
341  public:
342    typedef _Graph1 Graph1;
343    typedef _Graph2 Graph2;
344    typedef IterableGraphExtender<
345      MergeNodeGraphWrapperBase<_Graph1, _Graph2> > Parent;
346  protected:
347    MergeNodeGraphWrapper() { }
348  public:
349    MergeNodeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
350      Parent::Parent1::setGraph(_graph1);
351      Parent::Parent2::setGraph(_graph2);
352    }
353  };
354
355
356  /*! A grah wrapper base class
357    for merging the node-sets and edge-sets of
358    two node-disjoint graphs
359    into one graph.
360    Generic implementation for unrelated _Graph1::Edge and _Graph2::Edge.
361   */
362  template <typename _Graph1, typename _Graph2, typename Enable=void>
363  class MergeEdgeGraphWrapperBaseBase :
364    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
365  public:
366    static void printEdge() { std::cout << "edge: generic" << std::endl; }
367    typedef _Graph1 Graph1;
368    typedef _Graph2 Graph2;
369    typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
370    typedef typename Parent::Parent1 Parent1;
371    typedef typename Parent::Parent2 Parent2;
372//     typedef P1<_Graph1> Parent1;
373//     typedef P2<_Graph2> Parent2;
374    typedef typename Parent1::Edge Graph1Edge;
375    typedef typename Parent2::Edge Graph2Edge;
376  protected:
377    MergeEdgeGraphWrapperBaseBase() { }
378  public:
379
380    class Edge : public Graph1Edge, public Graph2Edge {
381      friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
382    protected:
383      bool backward; //true, iff backward
384    public:
385      Edge() { }
386      /// \todo =false is needed, or causes problems?
387      /// If \c _backward is false, then we get an edge corresponding to the
388      /// original one, otherwise its oppositely directed pair is obtained.
389      Edge(const Graph1Edge& n1,
390           const Graph2Edge& n2, bool _backward) :
391        Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
392      Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
393      bool operator==(const Edge& v) const {
394        if (backward)
395          return (v.backward &&
396                  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
397        else
398          return (!v.backward &&
399                  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
400      }
401      bool operator!=(const Edge& v) const {
402        return !(*this==v);
403      }
404    };
405
406    using Parent::forward;
407    using Parent::backward;
408    using Parent::setForward;
409    using Parent::setBackward;
410    static bool forward(const Edge& e) { return !e.backward; }
411    static bool backward(const Edge& e) { return e.backward; }
412    static void setForward(Edge& e) { e.backward=false; }
413    static void setBackward(Edge& e) { e.backward=true; }
414  };
415
416
417
418  /*! A graph wrapper base class
419    for merging the node-sets and edge-sets of
420    two node-disjoint graphs
421    into one graph.
422    Specialization for the case when _Graph1::Edge and _Graph2::Edge
423    are the same.
424   */
425  template <typename _Graph1, typename _Graph2>
426  class MergeEdgeGraphWrapperBaseBase<
427    _Graph1, _Graph2, typename boost::enable_if<
428    boost::is_same<typename _Graph1::Edge, typename _Graph2::Edge> >::type> :
429    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
430  public:
431    static void printEdge() { std::cout << "edge: same" << std::endl; }
432    typedef _Graph1 Graph1;
433    typedef _Graph2 Graph2;
434    typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
435    typedef typename Parent::Parent1 Parent1;
436    typedef typename Parent::Parent2 Parent2;
437//     typedef P1<_Graph1> Parent1;
438//     typedef P2<_Graph2> Parent2;
439    typedef typename Parent1::Edge Graph1Edge;
440    typedef typename Parent2::Edge Graph2Edge;
441  protected:
442    MergeEdgeGraphWrapperBaseBase() { }
443  public:
444
445    class Edge : public Graph1Edge {
446      friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
447    protected:
448      bool backward; //true, iff backward
449    public:
450      Edge() { }
451      /// \todo =false is needed, or causes problems?
452      /// If \c _backward is false, then we get an edge corresponding to the
453      /// original one, otherwise its oppositely directed pair is obtained.
454      Edge(const Graph1Edge& n1,
455           const Graph2Edge& n2, bool _backward) :
456        Graph1Edge(!_backward ? n1 : n2), backward(_backward) { }
457      Edge(Invalid i) : Graph1Edge(i), backward(true) { }
458      bool operator==(const Edge& v) const {
459        return (backward==v.backward &&
460                static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
461      }
462      bool operator!=(const Edge& v) const {
463        return !(*this==v);
464      }
465    };
466
467    using Parent::forward;
468    using Parent::backward;
469    using Parent::setForward;
470    using Parent::setBackward;
471    static bool forward(const Edge& e) { return !e.backward; }
472    static bool backward(const Edge& e) { return e.backward; }
473    static void setForward(Edge& e) { e.backward=false; }
474    static void setBackward(Edge& e) { e.backward=true; }
475  };
476
477
478  /*! A grah wrapper base class
479    for merging the node-sets and edge-sets of
480    two node-disjoint graphs
481    into one graph.
482    Specialized implementation for the case
483    when _Graph1::Edge is a base class and _Graph2::Edge
484    is derived from it.
485   */
486  template <typename _Graph1, typename _Graph2>
487  class MergeEdgeGraphWrapperBaseBase<
488    _Graph1, _Graph2, typename boost::enable_if<
489    boost::is_base_and_derived<typename _Graph1::Edge, typename _Graph2::Edge> >::type> :
490    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
491  public:
492    static void printEdge() { std::cout << "edge: 2nd is derived" << std::endl; }
493    typedef _Graph1 Graph1;
494    typedef _Graph2 Graph2;
495    typedef MergeNodeGraphWrapperBase<_Graph1, _Graph2> Parent;
496    typedef typename Parent::Parent1 Parent1;
497    typedef typename Parent::Parent2 Parent2;
498//     typedef P1<_Graph1> Parent1;
499//     typedef P2<_Graph2> Parent2;
500    typedef typename Parent1::Edge Graph1Edge;
501    typedef typename Parent2::Edge Graph2Edge;
502  protected:
503    MergeEdgeGraphWrapperBaseBase() { }
504  public:
505
506    class Edge : public Graph2Edge {
507      friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
508    protected:
509      bool backward; //true, iff backward
510    public:
511      Edge() { }
512      /// \todo =false is needed, or causes problems?
513      /// If \c _backward is false, then we get an edge corresponding to the
514      /// original one, otherwise its oppositely directed pair is obtained.
515      Edge(const Graph1Edge& n1,
516           const Graph2Edge& n2, bool _backward) :
517        Graph2Edge(n2), backward(_backward) {
518        if (!backward) *this=n1;
519      }
520      Edge(Invalid i) : Graph2Edge(i), backward(true) { }
521      bool operator==(const Edge& v) const {
522        if (backward)
523          return (v.backward &&
524                  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
525        else
526          return (!v.backward &&
527                  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
528      }
529      bool operator!=(const Edge& v) const {
530        return !(*this==v);
531      }
532    };
533
534    using Parent::forward;
535    using Parent::backward;
536    using Parent::setForward;
537    using Parent::setBackward;
538    static bool forward(const Edge& e) { return !e.backward; }
539    static bool backward(const Edge& e) { return e.backward; }
540    static void setForward(Edge& e) { e.backward=false; }
541    static void setBackward(Edge& e) { e.backward=true; }
542  };
543
544
545  /*! A grah wrapper base class
546    for merging the node-sets and edge-sets of
547    two node-disjoint graphs
548    into one graph.
549    Specialized implementation for the case
550    when _Graph1::Edge is derived from _Graph2::Edge.
551   */
552  template <typename _Graph1, typename _Graph2>
553  class MergeEdgeGraphWrapperBaseBase<
554    _Graph1, _Graph2, typename boost::enable_if<
555    boost::is_base_and_derived<typename _Graph2::Edge, typename _Graph1::Edge> >::type> :
556    public MergeNodeGraphWrapperBase<_Graph1, _Graph2> {
557  public:
558    static void printEdge() { std::cout << "edge: 1st is derived" << std::endl; }
559    typedef _Graph1 Graph1;
560    typedef _Graph2 Graph2;
561    typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
562    typedef typename Parent::Parent1 Parent1;
563    typedef typename Parent::Parent2 Parent2;
564//     typedef P1<_Graph1> Parent1;
565//     typedef P2<_Graph2> Parent2;
566    typedef typename Parent1::Edge Graph1Edge;
567    typedef typename Parent2::Edge Graph2Edge;
568  protected:
569    MergeEdgeGraphWrapperBaseBase() { }
570  public:
571
572    class Edge : public Graph1Edge {
573      friend class MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2>;
574    protected:
575      bool backward; //true, iff backward
576    public:
577      Edge() { }
578      /// \todo =false is needed, or causes problems?
579      /// If \c _backward is false, then we get an edge corresponding to the
580      /// original one, otherwise its oppositely directed pair is obtained.
581      Edge(const Graph1Edge& n1,
582           const Graph2Edge& n2, bool _backward) :
583        Graph1Edge(n1), backward(_backward) {
584        if (backward) *this=n2;
585      }
586      Edge(Invalid i) : Graph1Edge(i), backward(true) { }
587      bool operator==(const Edge& v) const {
588        if (backward)
589          return (v.backward &&
590                  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
591        else
592          return (!v.backward &&
593                  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
594      }
595      bool operator!=(const Edge& v) const {
596        return !(*this==v);
597      }
598    };
599
600    using Parent::forward;
601    using Parent::backward;
602    using Parent::setForward;
603    using Parent::setBackward;
604    static bool forward(const Edge& e) { return !e.backward; }
605    static bool backward(const Edge& e) { return e.backward; }
606    static void setForward(Edge& e) { e.backward=false; }
607    static void setBackward(Edge& e) { e.backward=true; }
608  };
609
610
611  template <typename _Graph1, typename _Graph2>
612  class MergeEdgeGraphWrapperBase :
613    public MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> {
614  public:
615    typedef MergeEdgeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
616    typedef _Graph1 Graph1;
617    typedef _Graph2 Graph2;
618    typedef typename Parent::Parent1 Parent1;
619    typedef typename Parent::Parent2 Parent2;
620    typedef typename Parent1::Node Graph1Node;
621    typedef typename Parent2::Node Graph2Node;
622    typedef typename Parent1::Edge Graph1Edge;
623    typedef typename Parent2::Edge Graph2Edge;
624
625    typedef typename Parent::Node Node;
626    typedef typename Parent::Edge Edge;
627
628    using Parent::first;
629    void first(Edge& i) const {
630      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
631      this->setForward(i);
632      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
633        Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
634        this->setBackward(i);
635      }
636    }
637    void firstIn(Edge& i, const Node& n) const {
638      if (forward(n)) {
639        Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
640        if (*static_cast<Graph1Edge*>(&i)==INVALID)
641          i=INVALID;
642        else
643          this->setForward(i);
644      } else {
645        Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
646        this->setBackward(i);
647      }
648    }
649    void firstOut(Edge& i, const Node& n) const {
650      if (forward(n)) {
651        Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
652        if (*static_cast<Graph1Edge*>(&i)==INVALID)
653          i=INVALID;
654        else
655          this->setForward(i);
656      } else {
657        Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
658        this->setBackward(i);
659      }
660    }
661
662    using Parent::next;
663    void next(Edge& i) const {
664      if (forward(i)) {
665        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
666        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
667          Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
668          this->setBackward(i);
669        }
670      } else {
671        Parent2::graph->next(*static_cast<Graph2Edge*>(&i));
672      }
673    }
674    void nextIn(Edge& i) const {
675      if (forward(i)) {
676        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
677        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
678      } else {
679        Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
680      }
681    }
682    void nextOut(Edge& i) const {
683      if (Parent::forward(i)) {
684        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
685        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
686      } else {
687        Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
688      }
689    }
690
691    Node source(const Edge& i) const {
692      if (forward(i)) {
693        return
694          Node(Parent1::graph->source(i), INVALID, false);
695      } else {
696        return
697          Node(INVALID, Parent2::graph->source(i), true);
698      }
699    }
700
701    Node target(const Edge& i) const {
702      if (forward(i)) {
703        return
704          Node(Parent1::graph->target(i), INVALID, false);
705      } else {
706        return
707          Node(INVALID, Parent2::graph->target(i), true);
708      }
709    }
710
711    using Parent::id;
712    int id(const Edge& n) const {
713      if (forward(n))
714        return this->Parent1::graph->id(n);
715      else
716        return this->Parent2::graph->id(n);
717    }
718
719    template <typename _Value>
720    class EdgeMap {
721    protected:
722      typedef typename Parent::Graph1::template EdgeMap<_Value> ParentMap1;
723      typedef typename Parent::Graph2::template EdgeMap<_Value> ParentMap2;
724      ParentMap1 forward_map;
725      ParentMap2 backward_map;
726    public:
727      typedef _Value Value;
728      typedef Edge Key;
729      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw) :
730        forward_map(*(gw.Parent1::graph)),
731        backward_map(*(gw.Parent2::graph)) { }
732      EdgeMap(const MergeEdgeGraphWrapperBase<_Graph1, _Graph2>& gw,
733              const _Value& value) :
734        forward_map(*(gw.Parent1::graph), value),
735        backward_map(*(gw.Parent2::graph), value) { }
736      _Value operator[](const Edge& n) const {
737        if (Parent::forward(n))
738          return forward_map[n];
739        else
740          return backward_map[n];
741      }
742      void set(const Edge& n, const _Value& value) {
743        if (Parent::forward(n))
744          forward_map.set(n, value);
745        else
746          backward_map.set(n, value);
747      }
748//       using ParentMap1::operator[];
749//       using ParentMap2::operator[];
750    };
751
752  };
753
754
755
756  /*! A graph wrapper class
757    for merging two node-disjoint graphs
758    into one graph.
759    Different implementations are according to the relation of
760    _Graph1::Edge and _Graph2::Edge.
761    If _Graph1::Edge and _Graph2::Edge are unrelated, then
762    MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge
763    is derived from both.
764    If _Graph1::Edge and _Graph2::Edge are the same type, then
765    MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge
766    is derived from _Graph1::Edge.
767    If one of _Graph1::Edge and _Graph2::Edge
768    is derived from the other one, then
769    MergeEdgeGraphWrapper<_Graph1, _Graph2>::Edge
770    is derived from the derived type.
771    It does not satisfy
772  */
773  template <typename _Graph1, typename _Graph2>
774  class MergeEdgeGraphWrapper : public
775  IterableGraphExtender<MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > {
776  public:
777    typedef _Graph1 Graph1;
778    typedef _Graph2 Graph2;
779    typedef IterableGraphExtender<
780      MergeEdgeGraphWrapperBase<_Graph1, _Graph2> > Parent;
781  protected:
782    MergeEdgeGraphWrapper() { }
783  public:
784    MergeEdgeGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
785      Parent::Parent1::setGraph(_graph1);
786      Parent::Parent2::setGraph(_graph2);
787    }
788  };
789
790 
791  /*! A graph wrapper base class for the following functionality.
792    If a bijection is given between the node-sets of two graphs,
793    then the second one can be considered as a new edge-set
794    over th first node-set.
795   */
796  template <typename _Graph, typename _EdgeSetGraph>
797  class NewEdgeSetGraphWrapperBase : public GraphWrapperBase<_Graph> {
798  public:
799    typedef GraphWrapperBase<_Graph> Parent;
800    typedef _Graph Graph;
801    typedef _EdgeSetGraph EdgeSetGraph;
802    typedef typename _Graph::Node Node;
803    typedef typename _EdgeSetGraph::Node ENode;
804  protected:
805    EdgeSetGraph* edge_set_graph;
806    typename Graph::NodeMap<ENode>* e_node;
807    typename EdgeSetGraph::NodeMap<Node>* n_node;
808    void setEdgeSetGraph(EdgeSetGraph& _edge_set_graph) {
809      edge_set_graph=&_edge_set_graph;
810    }
811    /// For each node of \c Graph, this gives a node of \c EdgeSetGraph .
812    void setNodeMap(typename EdgeSetGraph::NodeMap<Node>& _n_node) {
813      n_node=&_n_node;
814    }
815    /// For each node of \c EdgeSetGraph, this gives a node of \c Graph .
816    void setENodeMap(typename Graph::NodeMap<ENode>& _e_node) {
817      e_node=&_e_node;
818    }
819  public:
820    class Edge : public EdgeSetGraph::Edge {
821      typedef typename EdgeSetGraph::Edge Parent;
822    public:
823      Edge() { }
824      Edge(const Parent& e) : Parent(e) { }
825      Edge(Invalid i) : Parent(i) { }
826    };
827
828    using Parent::first;
829    void first(Edge &e) const {
830      edge_set_graph->first(e);
831    }
832    void firstOut(Edge& e, const Node& n) const {
833//       cout << e_node << endl;
834//       cout << n_node << endl;
835      edge_set_graph->firstOut(e, (*e_node)[n]);
836    }
837    void firstIn(Edge& e, const Node& n) const {
838      edge_set_graph->firstIn(e, (*e_node)[n]);
839    }
840
841    using Parent::next;
842    void next(Edge &e) const {
843      edge_set_graph->next(e);
844    }
845    void nextOut(Edge& e) const {
846      edge_set_graph->nextOut(e);
847    }
848    void nextIn(Edge& e) const {
849      edge_set_graph->nextIn(e);
850    }
851
852    Node source(const Edge& e) const {
853      return (*n_node)[edge_set_graph->source(e)];
854    }
855    Node target(const Edge& e) const {
856      return (*n_node)[edge_set_graph->target(e)];
857    }
858
859    int edgeNum() const { return edge_set_graph->edgeNum(); }
860
861//     NNode addOldNode() {
862//       return Parent::addNode();
863//     }
864
865//     ENode addNewNode() {
866//       return edge_set_graph->addNode();
867//     }
868
869    Edge addEdge(const Node& u, const Node& v) {
870      return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
871    }
872
873    using Parent::erase;
874    void erase(const Edge& i) const { edge_set_graph->erase(i); }
875 
876    void clear() const { Parent::clear(); edge_set_graph->clear(); }
877
878    bool forward(const Edge& e) const { return edge_set_graph->forward(e); }
879    bool backward(const Edge& e) const { return edge_set_graph->backward(e); }
880
881    int id(const Node& e) const { return Parent::id(e); }
882    int id(const Edge& e) const { return edge_set_graph->id(e); }
883   
884    Edge opposite(const Edge& e) const { return edge_set_graph->opposite(e); }
885
886    template <typename _Value>
887    class EdgeMap : public EdgeSetGraph::EdgeMap<_Value> {
888    public:
889      typedef typename EdgeSetGraph::EdgeMap<_Value> Parent;
890      typedef _Value Value;
891      typedef Edge Key;
892      EdgeMap(const NewEdgeSetGraphWrapperBase& gw) :
893        Parent(*(gw.edge_set_graph)) { }
894      EdgeMap(const NewEdgeSetGraphWrapperBase& gw, const _Value& _value) :
895        Parent(*(gw.edge_set_graph), _value) { }
896    };
897
898  };
899
900
901  /*! A graph wrapper class for the following functionality.
902    If a bijection is given between the node-sets of two graphs,
903    then the second one can be considered as a new edge-set
904    over th first node-set.
905   */
906  template <typename _Graph, typename _EdgeSetGraph>
907  class NewEdgeSetGraphWrapper :
908    public IterableGraphExtender<
909    NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
910  public:
911    typedef _Graph Graph;
912    typedef _EdgeSetGraph EdgeSetGraph;
913    typedef IterableGraphExtender<
914      NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
915  protected:
916    NewEdgeSetGraphWrapper() { }
917  public:
918    NewEdgeSetGraphWrapper(_Graph& _graph,
919                           _EdgeSetGraph& _edge_set_graph,
920                           typename _Graph::
921                           NodeMap<typename _EdgeSetGraph::Node>& _e_node,
922                           typename _EdgeSetGraph::
923                           NodeMap<typename _Graph::Node>& _n_node) {
924      setGraph(_graph);
925      setEdgeSetGraph(_edge_set_graph);
926      setNodeMap(_n_node);
927      setENodeMap(_e_node);
928    }
929  };
930
931  /*! A graph wrapper class for the following functionality.
932    The same as NewEdgeSetGrapWrapper, but the bijection and the graph of
933    new edges is andled inthe class.
934   */
935  template <typename _Graph, typename _EdgeSetGraph>
936  class NewEdgeSetGraphWrapper2 :
937    public IterableGraphExtender<
938    NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
939  public:
940    typedef _Graph Graph;
941    typedef _EdgeSetGraph EdgeSetGraph;
942    typedef IterableGraphExtender<
943      NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
944  protected:
945    _EdgeSetGraph _edge_set_graph;
946    typename Graph::template NodeMap<typename EdgeSetGraph::Node> _e_node;
947    typename EdgeSetGraph::template NodeMap<typename Graph::Node> _n_node;
948    NewEdgeSetGraphWrapper2() { }
949  public:
950    typedef typename Graph::Node Node;
951    //    typedef typename Parent::Edge Edge;
952
953    NewEdgeSetGraphWrapper2(_Graph& _graph) :
954      _edge_set_graph(),
955      _e_node(_graph), _n_node(_edge_set_graph) {
956      setGraph(_graph);
957      setEdgeSetGraph(_edge_set_graph);
958      setNodeMap(_n_node); setENodeMap(_e_node);
959      Node n;
960      for (this->first(n); n!=INVALID; this->next(n)) {
961        typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
962        _e_node.set(n, e);
963        _n_node.set(e, n);
964      }
965    }
966
967//     Node addNode() {
968//       Node n=(*this).Parent::addNode();
969//       typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
970//       _e_node.set(n, e);
971//       _n_node.set(e, n);
972//       return n;
973//     }
974
975  };
976
977  /*! A graph wrapper base class
978    for merging graphs of type _Graph1 and _Graph2
979    which are given on the same node-set
980    (specially on the node-set of Graph1)
981    into one graph.
982    In an other point of view, _Graph1 is extended with
983    the edge-set of _Graph2.
984    \warning we need specialize dimplementations
985    \todo we need specialize dimplementations
986    \bug we need specialize dimplementations
987   */
988  template <typename _Graph1, typename _Graph2, typename Enable=void>
989  class AugmentingGraphWrapperBase :
990    public P1<_Graph1> {
991  public:
992    void printAugment() const { std::cout << "generic" << std::endl; }
993    typedef _Graph1 Graph1;
994    typedef _Graph2 Graph2;
995    typedef P1<_Graph1> Parent1;
996    typedef P2<_Graph2> Parent2;
997    typedef typename Parent1::Edge Graph1Edge;
998    typedef typename Parent2::Edge Graph2Edge;
999  protected:
1000    AugmentingGraphWrapperBase() { }
1001    _Graph2* graph2;
1002    void setGraph2(_Graph2& _graph2) { graph2=&_graph2; }
1003  public:
1004   
1005    template <typename _Value> class EdgeMap;
1006
1007    typedef typename Parent1::Node Node;
1008
1009    class Edge : public Graph1Edge, public Graph2Edge {
1010      friend class AugmentingGraphWrapperBase<_Graph1, _Graph2>;
1011      template <typename _Value> friend class EdgeMap;
1012    protected:
1013      bool backward; //true, iff backward
1014    public:
1015      Edge() { }
1016      /// \todo =false is needed, or causes problems?
1017      /// If \c _backward is false, then we get an edge corresponding to the
1018      /// original one, otherwise its oppositely directed pair is obtained.
1019      Edge(const Graph1Edge& n1,
1020           const Graph2Edge& n2, bool _backward) :
1021        Graph1Edge(n1), Graph2Edge(n2), backward(_backward) { }
1022      Edge(Invalid i) : Graph1Edge(i), Graph2Edge(i), backward(true) { }
1023      bool operator==(const Edge& v) const {
1024        if (backward)
1025          return (v.backward &&
1026                  static_cast<Graph2Edge>(*this)==static_cast<Graph2Edge>(v));
1027        else
1028          return (!v.backward &&
1029                  static_cast<Graph1Edge>(*this)==static_cast<Graph1Edge>(v));
1030      }
1031      bool operator!=(const Edge& v) const {
1032        return !(*this==v);
1033      }
1034    };
1035
1036    using Parent1::first;
1037    void first(Edge& i) const {
1038      Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
1039      i.backward=false;
1040      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1041        graph2->first(*static_cast<Graph2Edge*>(&i));
1042        i.backward=true;
1043      }
1044    }
1045    void firstIn(Edge& i, const Node& n) const {
1046      Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
1047      i.backward=false;
1048      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1049        graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
1050        i.backward=true;
1051      }
1052    }
1053    void firstOut(Edge& i, const Node& n) const {
1054      Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
1055      i.backward=false;
1056      if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1057        graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
1058        i.backward=true;
1059      }
1060    }
1061
1062    using Parent1::next;
1063    void next(Edge& i) const {
1064      if (!(i.backward)) {
1065        Parent1::graph->next(*static_cast<Graph1Edge*>(&i));
1066        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1067          graph2->first(*static_cast<Graph2Edge*>(&i));
1068          i.backward=true;
1069        }
1070      } else {
1071        graph2->next(*static_cast<Graph2Edge*>(&i));
1072      }
1073    }
1074    void nextIn(Edge& i) const {
1075      if (!(i.backward)) {
1076        Node n=target(i);
1077        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
1078        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1079          graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
1080          i.backward=true;
1081        }
1082      } else {
1083        graph2->nextIn(*static_cast<Graph2Edge*>(&i));
1084      }
1085    }
1086    void nextOut(Edge& i) const {
1087      if (!(i.backward)) {
1088        Node n=source(i);
1089        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
1090        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
1091          graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
1092          i.backward=true;
1093        }
1094      } else {
1095        graph2->nextOut(*static_cast<Graph2Edge*>(&i));
1096      }
1097    }
1098
1099    Node source(const Edge& i) const {
1100      if (!(i.backward)) {
1101        return Parent1::graph->source(i);
1102      } else {
1103        return graph2->source(i);
1104      }
1105    }
1106
1107    Node target(const Edge& i) const {
1108      if (!(i.backward)) {
1109        return Parent1::graph->target(i);
1110      } else {
1111        return graph2->target(i);
1112      }
1113    }
1114
1115    int id(const Node& n) const {
1116      return Parent1::id(n);
1117    };
1118    int id(const Edge& n) const {
1119      if (!n.backward)
1120        return this->Parent1::graph->id(n);
1121      else
1122        return this->graph2->id(n);
1123    }
1124
1125    template <typename _Value>
1126    class EdgeMap {
1127    protected:
1128      typedef typename _Graph1::template EdgeMap<_Value> ParentMap1;
1129      typedef typename _Graph2::template EdgeMap<_Value> ParentMap2;
1130      ParentMap1 forward_map;
1131      ParentMap2 backward_map;
1132    public:
1133      typedef _Value Value;
1134      typedef Edge Key;
1135      EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw) :
1136        forward_map(*(gw.Parent1::graph)),
1137        backward_map(*(gw.graph2)) { }
1138      EdgeMap(const AugmentingGraphWrapperBase<_Graph1, _Graph2>& gw,
1139              const _Value& value) :
1140        forward_map(*(gw.Parent1::graph), value),
1141        backward_map(*(gw.graph2), value) { }
1142      _Value operator[](const Edge& n) const {
1143        if (!n.backward)
1144          return forward_map[n];
1145        else
1146          return backward_map[n];
1147      }
1148      void set(const Edge& n, const _Value& value) {
1149        if (!n.backward)
1150          forward_map.set(n, value);
1151        else
1152          backward_map.set(n, value);
1153      }
1154//       using ParentMap1::operator[];
1155//       using ParentMap2::operator[];
1156    };
1157
1158  };
1159
1160
1161  /*! A graph wrapper class
1162    for merging two graphs (of type _Graph1 and _Graph2)
1163    with the same node-set
1164    (specially on the node-set of Graph1)
1165    into one graph.
1166    In an other point of view, _Graph1 is extended with
1167    the edge-set of _Graph2.
1168   */ 
1169  template <typename _Graph1, typename _Graph2>
1170  class AugmentingGraphWrapper : public
1171  IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> > {
1172  public:
1173    typedef
1174    IterableGraphExtender<AugmentingGraphWrapperBase<_Graph1, _Graph2> >
1175    Parent;
1176    typedef _Graph1 Graph1;
1177    typedef _Graph2 Graph2;
1178  protected:
1179    AugmentingGraphWrapper() { }
1180  public:
1181    AugmentingGraphWrapper(_Graph1& _graph1, _Graph2& _graph2) {
1182      setGraph(_graph1);
1183      setGraph2(_graph2);
1184    }
1185  };
1186
1187} //namespace lemon
1188
1189#endif //LEMON_MERGE_NODE_GRAPH_WRAPPER_H
Note: See TracBrowser for help on using the repository browser.