COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_graph_wrapper.h @ 549:5531429143bc

Last change on this file since 549:5531429143bc was 510:72143568cadc, checked in by marci, 20 years ago

matching, flows

File size: 23.6 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_BIPARTITE_GRAPH_WRAPPER_H
3#define HUGO_BIPARTITE_GRAPH_WRAPPER_H
4
5///\ingroup gwrappers
6///\file
7///\brief Several graph wrappers.
8///
9///This file contains several useful graph wrapper functions.
10///
11///\author Marton Makai
12
13#include <invalid.h>
14#include <iter_map.h>
15#include <graph_wrapper.h>
16
17namespace hugo {
18
19  /// A wrapper for composing a bipartite graph.
20  /// \c _graph have to be a reference to a graph of type \c Graph
21  /// and \c _s_false_t_true_map is an \c IterableBoolMap
22  /// reference containing the elements for the
23  /// color classes S and T. \c _graph is to be referred to an undirected
24  /// graph or a directed graph with edges oriented from S to T.
25  ///
26  ///\author Marton Makai
27  template<typename Graph>
28  class BipartiteGraphWrapper : public GraphWrapper<Graph> {
29  protected:
30    typedef IterableBoolMap< typename Graph::template NodeMap<int> >
31    SFalseTTrueMap;
32    SFalseTTrueMap* s_false_t_true_map;
33
34    BipartiteGraphWrapper() : GraphWrapper<Graph>()/*,
35                                                     S_CLASS(false), T_CLASS(true)*/ { }
36    void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) {
37      s_false_t_true_map=&_s_false_t_true_map;
38    }
39
40  public:
41    //marci
42    //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
43    static const bool S_CLASS;
44    static const bool T_CLASS;
45   
46    //bool S_CLASS;
47    //bool T_CLASS;
48
49    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
50      : GraphWrapper<Graph>(_graph),
51        s_false_t_true_map(&_s_false_t_true_map)/*,
52                                                  S_CLASS(false), T_CLASS(true)*/ { }
53    typedef typename GraphWrapper<Graph>::Node Node;
54    //using GraphWrapper<Graph>::NodeIt;
55    typedef typename GraphWrapper<Graph>::Edge Edge;
56    //using GraphWrapper<Graph>::EdgeIt;
57    class ClassNodeIt;
58    friend class ClassNodeIt;
59    class OutEdgeIt;
60    friend class OutEdgeIt;
61    class InEdgeIt;
62    friend class InEdgeIt;
63    class ClassNodeIt {
64      friend class BipartiteGraphWrapper<Graph>;
65    protected:
66      Node n;
67    public:
68      ClassNodeIt() { }
69      ClassNodeIt(const Invalid& i) : n(i) { }
70      ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {
71        _G.s_false_t_true_map->first(n, _class);
72      }
73      //FIXME needed in new concept, important here
74      ClassNodeIt(const Node& _n) : n(_n) { }
75      operator Node() const { return n; }
76    };
77//     class SNodeIt {
78//       Node n;
79//     public:
80//       SNodeIt() { }
81//       SNodeIt(const Invalid& i) : n(i) { }
82//       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
83//      _G.s_false_t_true_map->first(n, false);
84//       }
85//       operator Node() const { return n; }
86//     };
87//     class TNodeIt {
88//       Node n;
89//     public:
90//       TNodeIt() { }
91//       TNodeIt(const Invalid& i) : n(i) { }
92//       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
93//      _G.s_false_t_true_map->first(n, true);
94//       }
95//       operator Node() const { return n; }
96//     };
97    class OutEdgeIt {
98      friend class BipartiteGraphWrapper<Graph>;
99    protected:
100      typename Graph::OutEdgeIt e;
101    public:
102      OutEdgeIt() { }
103      OutEdgeIt(const Invalid& i) : e(i) { }
104      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
105        if (!(*(_G.s_false_t_true_map))[_n])
106          e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
107        else
108          e=INVALID;
109      }
110      operator Edge() const { return Edge(typename Graph::Edge(e)); }
111    };
112    class InEdgeIt {
113      friend class BipartiteGraphWrapper<Graph>;
114    protected:
115      typename Graph::InEdgeIt e;
116    public:
117      InEdgeIt() { }
118      InEdgeIt(const Invalid& i) : e(i) { }
119      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
120        if ((*(_G.s_false_t_true_map))[_n])
121          e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
122        else
123          e=INVALID;
124      }
125      operator Edge() const { return Edge(typename Graph::Edge(e)); }
126    };
127
128    using GraphWrapper<Graph>::first;
129    ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
130      n=ClassNodeIt(*this, _class) ; return n; }
131//    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
132//    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
133    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
134      i=OutEdgeIt(*this, p); return i;
135    }
136    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
137      i=InEdgeIt(*this, p); return i;
138    }
139
140    using GraphWrapper<Graph>::next;
141    ClassNodeIt& next(ClassNodeIt& n) const {
142      this->s_false_t_true_map->next(n.n); return n;
143    }
144//     SNodeIt& next(SNodeIt& n) const {
145//       this->s_false_t_true_map->next(n); return n;
146//     }
147//     TNodeIt& next(TNodeIt& n) const {
148//       this->s_false_t_true_map->next(n); return n;
149//     }
150    OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
151    InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
152
153    Node tail(const Edge& e) {
154      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
155        return Node(this->graph->tail(e));
156      else
157        return Node(this->graph->head(e));     
158    }
159    Node head(const Edge& e) {
160      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
161        return Node(this->graph->head(e));
162      else
163        return Node(this->graph->tail(e));     
164    }
165
166    Node aNode(const OutEdgeIt& e) const {
167      return Node(this->graph->aNode(e.e));
168    }
169    Node aNode(const InEdgeIt& e) const {
170      return Node(this->graph->aNode(e.e));
171    }
172    Node bNode(const OutEdgeIt& e) const {
173      return Node(this->graph->bNode(e.e));
174    }
175    Node bNode(const InEdgeIt& e) const {
176      return Node(this->graph->bNode(e.e));
177    }
178
179    bool inSClass(const Node& n) const {
180      return !(*(this->s_false_t_true_map))[n];
181    }
182    bool inTClass(const Node& n) const {
183      return (*(this->s_false_t_true_map))[n];
184    }
185  };
186
187
188  template<typename G>
189  const bool BipartiteGraphWrapper<G>::S_CLASS=false;
190  template<typename G>
191  const bool BipartiteGraphWrapper<G>::T_CLASS=true;
192
193
194
195
196
197
198
199
200
201
202
203
204  ///\bug Do not use this while the bipartitemap augmentation
205  /// does not work well.
206  template<typename Graph>
207  class BipartiteGraph : public BipartiteGraphWrapper<Graph> {
208    typedef IterableBoolMap< typename Graph::template NodeMap<int> >
209    SFalseTTrueMap;
210    typedef BipartiteGraphWrapper<Graph> Parent;
211  protected:
212    Graph gr;
213    typename Graph::template NodeMap<int> bipartite_map;
214    SFalseTTrueMap s_false_t_true_map;
215  public:
216    typedef typename Parent::Node Node;
217    typedef typename Parent::Edge Edge;
218    BipartiteGraph() : BipartiteGraphWrapper<Graph>(),
219                       gr(), bipartite_map(gr, -1),
220                       s_false_t_true_map(bipartite_map) {
221      Parent::setGraph(gr);
222      Parent::setSFalseTTrueMap(s_false_t_true_map);
223    }
224
225    /// the \c bool parameter which can be \c S_Class or \c T_Class shows
226    /// the color class where the new node is to be inserted.
227    Node addNode(bool b) {
228      Node n=Parent::graph->addNode();
229      bipartite_map.update();
230      //bipartite_map.set(n, -1);
231      s_false_t_true_map.insert(n, b);
232      return n;
233    }
234
235    /// A new edge is inserted.
236    ///\pre \c tail have to be in \c S_Class and \c head in \c T_Class.
237    Edge addEdge(const Node& tail, const Node& head) {
238      return Parent::graph->addEdge(tail, head);
239    }
240
241    void erase(const Node& n) {
242      s_false_t_true_map.remove(n);
243      Parent::graph->erase(n);
244    }
245    void erase(const Edge& e) {
246      Parent::graph->erase(e);
247    }
248   
249    void clear() {
250      FOR_EACH_LOC(typename Parent::EdgeIt, e, G) erase(e);
251      FOR_EACH_LOC(typename Parent::NodeIt, n, G) erase(n);
252    }
253  };
254
255
256  template<typename Graph>
257  class stGraphWrapper;
258
259//   template<typename Graph>
260//   std::ostream&
261//   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) {
262//     os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
263//     return os;
264//   }
265//   template<typename Graph>
266//   std::ostream&
267//   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) {
268//     os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
269//       " node: " << i.n << ")";
270//     return os;
271//   }
272
273  /// experimentral, do not try it.
274  /// It eats a bipartite graph, oriented from S to T.
275  /// Such one can be made e.g. by the above wrapper.
276  ///
277  ///\author Marton Makai
278  template<typename Graph>
279  class stGraphWrapper : public GraphWrapper<Graph> {
280  public:
281    class Node;
282    friend class Node;
283//GN, int
284//0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
285//es a vege a false azaz (invalid, 3)   
286    class NodeIt;
287    friend class NodeIt;
288//GNI, int
289    class Edge;
290    friend class Edge;
291//GE, int, GN
292//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
293//invalid: (invalid, 3, invalid)
294    class OutEdgeIt;
295    friend class OutEdgeIt;
296//GO, int, GNI
297//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
298//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
299//t-bol (invalid, 3, invalid)
300    class InEdgeIt;
301    friend class InEdgeIt;
302//GI, int, GNI
303//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
304//s-be (invalid, 3, invalid)
305//t-be (invalid, 2, first), ... (invalid, 3, invalid)
306    class EdgeIt;
307    friend class EdgeIt;
308//(first, 0, invalid) ...
309//(invalid, 1, vmi)
310//(invalid, 2, vmi)
311//invalid, 3, invalid)
312    template <typename T> class NodeMap;
313    template <typename T> class EdgeMap;
314
315//    template <typename T> friend class NodeMap;
316//    template <typename T> friend class EdgeMap;
317
318    ///\todo FIXME ezt majd static-ra kell javitani
319    const Node S_NODE;
320    const Node T_NODE;
321
322    static const bool S_CLASS=false;
323    static const bool T_CLASS=true;
324
325    stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
326                                    S_NODE(INVALID, 1),
327                                    T_NODE(INVALID, 2) { }
328
329   
330//    std::ostream&
331//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
332//    friend std::ostream&
333//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
334//    friend std::ostream&
335//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i);
336
337    class Node : public Graph::Node {
338    protected:
339      friend class GraphWrapper<Graph>;
340      friend class stGraphWrapper<Graph>;
341      template <typename T> friend class NodeMap;
342      friend class Edge;
343      friend class OutEdgeIt;
344      friend class InEdgeIt;
345      friend class EdgeIt;
346      int spec;
347    public:
348      Node() { }
349      Node(const typename Graph::Node& _n, int _spec=0) :
350        Graph::Node(_n), spec(_spec) { }
351      Node(const Invalid& i) : Graph::Node(i), spec(3) { }
352      friend bool operator==(const Node& u, const Node& v) {
353        return (u.spec==v.spec &&
354                static_cast<typename Graph::Node>(u)==
355                static_cast<typename Graph::Node>(v));
356      }
357      friend bool operator!=(const Node& u, const Node& v) {
358        return (v.spec!=u.spec ||
359                static_cast<typename Graph::Node>(u)!=
360                static_cast<typename Graph::Node>(v));
361      }
362//      template<typename G>
363//      friend std::ostream&
364//      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i);
365      friend std::ostream& operator<< (std::ostream& os, const Node& i);
366      int getSpec() const { return spec; }
367    };
368
369    class NodeIt {
370      friend class GraphWrapper<Graph>;
371      friend class stGraphWrapper<Graph>;
372      typename Graph::NodeIt n;
373      int spec;
374     public:
375      NodeIt() { }
376      NodeIt(const typename Graph::NodeIt& _n, int _spec) :
377        n(_n), spec(_spec) { }
378      NodeIt(const Invalid& i) : n(i), spec(3) { }
379      NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
380        if (!_G.graph->valid(n)) spec=1;
381      }
382      operator Node() const { return Node(n, spec); }
383    };
384
385    class Edge : public Graph::Edge {
386      friend class GraphWrapper<Graph>;
387      friend class stGraphWrapper<Graph>;
388      template <typename T> friend class EdgeMap;
389      int spec;
390      typename Graph::Node n;
391    public:
392      Edge() { }
393      Edge(const typename Graph::Edge& _e, int _spec,
394           const typename Graph::Node& _n) :
395        Graph::Edge(_e), spec(_spec), n(_n) {
396      }
397      Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
398      friend bool operator==(const Edge& u, const Edge& v) {
399        return (u.spec==v.spec &&
400                static_cast<typename Graph::Edge>(u)==
401                static_cast<typename Graph::Edge>(v) &&
402                u.n==v.n);
403      }
404      friend bool operator!=(const Edge& u, const Edge& v) {
405        return (v.spec!=u.spec ||
406                static_cast<typename Graph::Edge>(u)!=
407                static_cast<typename Graph::Edge>(v) ||
408                u.n!=v.n);
409      }
410//      template<typename G>
411//      friend std::ostream&
412//      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i);
413      friend std::ostream& operator<< (std::ostream& os, const Edge& i);
414      int getSpec() const { return spec; }
415      typename Graph::Node getNode() const { return n; }
416    };
417
418    class OutEdgeIt {
419      friend class GraphWrapper<Graph>;
420      friend class stGraphWrapper<Graph>;
421      typename Graph::OutEdgeIt e;
422      int spec;
423      typename Graph::ClassNodeIt n;
424    public:
425      OutEdgeIt() { }
426      OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
427                const typename Graph::ClassNodeIt& _n) :
428        e(_e), spec(_spec), n(_n) {
429      }
430      OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
431      OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
432        switch (_n.spec) {
433          case 0 :
434            if (_G.graph->inSClass(_n)) { //S, van normalis kiel
435              e=typename Graph::OutEdgeIt(*(_G.graph),
436                                          typename Graph::Node(_n));
437              spec=0;
438              n=INVALID;
439              if (!_G.graph->valid(e)) spec=3;
440            } else { //T, specko kiel van
441              e=INVALID;
442              spec=2;
443              n=_n;
444            }
445            break;
446          case 1:
447            e=INVALID;
448            spec=1;
449            _G.graph->first(n, S_CLASS); //s->vmi;
450            if (!_G.graph->valid(n)) spec=3; //Ha S ures
451            break;
452          case 2:
453            e=INVALID;
454            spec=3;
455            n=INVALID;
456            break;
457        }
458      }
459      operator Edge() const { return Edge(e, spec, n); }
460    };
461
462    class InEdgeIt {
463      friend class GraphWrapper<Graph>;
464      friend class stGraphWrapper<Graph>;
465      typename Graph::InEdgeIt e;
466      int spec;
467      typename Graph::ClassNodeIt n;
468    public:
469      InEdgeIt() { }
470      InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
471               const typename Graph::ClassNodeIt& _n) :
472        e(_e), spec(_spec), n(_n) {
473      }
474      InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
475      InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
476        switch (_n.spec) {
477          case 0 :
478            if (_G.graph->inTClass(_n)) { //T, van normalis beel
479              e=typename Graph::InEdgeIt(*(_G.graph),
480                                         typename Graph::Node(_n));
481              spec=0;
482              n=INVALID;
483              if (!_G.graph->valid(e)) spec=3;
484            } else { //S, specko beel van
485              e=INVALID;
486              spec=1;
487              n=_n;
488            }
489            break;
490          case 1:
491            e=INVALID;
492            spec=3;
493            n=INVALID;
494            break;
495          case 2:
496            e=INVALID;
497            spec=2;
498            _G.graph->first(n, T_CLASS); //vmi->t;
499            if (!_G.graph->valid(n)) spec=3; //Ha T ures
500            break;
501        }
502      }
503      operator Edge() const { return Edge(e, spec, n); }
504    };
505
506    class EdgeIt {
507      friend class GraphWrapper<Graph>;
508      friend class stGraphWrapper<Graph>;
509      typename Graph::EdgeIt e;
510      int spec;
511      typename Graph::ClassNodeIt n;
512    public:
513      EdgeIt() { }
514      EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
515             const typename Graph::ClassNodeIt& _n) :
516        e(_e), spec(_spec), n(_n) { }
517      EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
518      EdgeIt(const stGraphWrapper<Graph>& _G) :
519        e(*(_G.graph)), spec(0), n(INVALID) {
520        if (!_G.graph->valid(e)) {
521          spec=1;
522          _G.graph->first(n, S_CLASS);
523          if (!_G.graph->valid(n)) { //Ha S ures
524            spec=2;
525            _G.graph->first(n, T_CLASS);
526            if (!_G.graph->valid(n)) { //Ha T ures
527              spec=3;
528            }
529          }
530        }
531      }
532      operator Edge() const { return Edge(e, spec, n); }
533    };
534   
535    NodeIt& first(NodeIt& i) const {
536      i=NodeIt(*this); return i;
537    }
538    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
539      i=OutEdgeIt(*this, p); return i;
540    }
541    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
542      i=InEdgeIt(*this, p); return i;
543    }
544    EdgeIt& first(EdgeIt& i) const {
545      i=EdgeIt(*this); return i;
546    }
547
548    NodeIt& next(NodeIt& i) const {
549      switch (i.spec) {
550        case 0:
551          this->graph->next(i.n);
552          if (!this->graph->valid(i.n)) {
553            i.spec=1;
554          }
555          break;
556        case 1:
557          i.spec=2;
558          break;
559        case 2:
560          i.spec=3;
561          break;
562      }
563      return i;
564    }
565    OutEdgeIt& next(OutEdgeIt& i) const {
566      typename Graph::Node v;
567      switch (i.spec) {
568        case 0: //normal edge
569          v=this->graph->aNode(i.e);
570          this->graph->next(i.e);
571          if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
572            if (this->graph->inSClass(v)) { //S, nincs kiel
573              i.spec=3;
574              i.n=INVALID;
575            } else { //T, van kiel
576              i.spec=2;
577              i.n=v;
578            }
579          }
580          break;
581        case 1: //s->vmi
582          this->graph->next(i.n);
583          if (!this->graph->valid(i.n)) i.spec=3;
584          break;
585        case 2: //vmi->t
586          i.spec=3;
587          i.n=INVALID;
588          break;
589      }
590      return i;
591    }
592    InEdgeIt& next(InEdgeIt& i) const {
593      typename Graph::Node v;
594      switch (i.spec) {
595        case 0: //normal edge
596          v=this->graph->aNode(i.e);
597          this->graph->next(i.e);
598          if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
599            if (this->graph->inTClass(v)) { //S, nincs beel
600              i.spec=3;
601              i.n=INVALID;
602            } else { //S, van beel
603              i.spec=1;
604              i.n=v;
605            }
606          }
607          break;
608        case 1: //s->vmi
609          i.spec=3;
610          i.n=INVALID;
611          break;
612        case 2: //vmi->t
613          this->graph->next(i.n);
614          if (!this->graph->valid(i.n)) i.spec=3;
615          break;
616      }
617      return i;
618    }
619
620    EdgeIt& next(EdgeIt& i) const {
621      switch (i.spec) {
622        case 0:
623          this->graph->next(i.e);
624          if (!this->graph->valid(i.e)) {
625            i.spec=1;
626            this->graph->first(i.n, S_CLASS);
627            if (!this->graph->valid(i.n)) {
628              i.spec=2;
629              this->graph->first(i.n, T_CLASS);
630              if (!this->graph->valid(i.n)) i.spec=3;
631            }
632          }
633          break;
634        case 1:
635          this->graph->next(i.n);
636          if (!this->graph->valid(i.n)) {
637            i.spec=2;
638            this->graph->first(i.n, T_CLASS);
639            if (!this->graph->valid(i.n)) i.spec=3;
640          }
641          break;
642        case 2:
643          this->graph->next(i.n);
644          if (!this->graph->valid(i.n)) i.spec=3;
645          break;
646      }
647      return i;
648    }   
649
650    Node tail(const Edge& e) const {
651      switch (e.spec) {
652      case 0:
653        return Node(this->graph->tail(e));
654        break;
655      case 1:
656        return S_NODE;
657        break;
658      case 2:
659      default:
660        return Node(e.n);
661        break;
662      }
663    }
664    Node head(const Edge& e) const {
665      switch (e.spec) {
666      case 0:
667        return Node(this->graph->head(e));
668        break;
669      case 1:
670        return Node(e.n);
671        break;
672      case 2:
673      default:
674        return T_NODE;
675        break;
676      }
677    }
678
679    bool valid(const Node& n) const { return (n.spec<3); }
680    bool valid(const Edge& e) const { return (e.spec<3); }
681
682    int nodeNum() const { return this->graph->nodeNum()+2; }
683    int edgeNum() const {
684      return this->graph->edgeNum()+this->graph->nodeNum();
685    }
686 
687    Node aNode(const OutEdgeIt& e) const { return tail(e); }
688    Node aNode(const InEdgeIt& e) const { return head(e); }
689    Node bNode(const OutEdgeIt& e) const { return head(e); }
690    Node bNode(const InEdgeIt& e) const { return tail(e); }
691
692    void addNode() const { }
693    void addEdge() const { }
694   
695//    Node addNode() const { return Node(this->graph->addNode()); }
696//    Edge addEdge(const Node& tail, const Node& head) const {
697//      return Edge(this->graph->addEdge(tail, head)); }
698
699//    void erase(const Node& i) const { this->graph->erase(i); }
700//    void erase(const Edge& i) const { this->graph->erase(i); }
701 
702//    void clear() const { this->graph->clear(); }
703   
704    template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
705      typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
706    protected:
707      T s_value, t_value;
708    public:
709      NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G),
710                                                  s_value(),
711                                                  t_value() { }
712      NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
713                                                      s_value(a),
714                                                      t_value(a) { }
715      T operator[](const Node& n) const {
716        switch (n.spec) {
717        case 0:
718          return Parent::operator[](n);
719        case 1:
720          return s_value;
721        case 2:
722        default:
723          return t_value;
724        }
725      }
726      void set(const Node& n, T t) {
727        switch (n.spec) {
728        case 0:
729          GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
730          break;
731        case 1:
732          s_value=t;
733          break;
734        case 2:
735        default:
736          t_value=t;
737          break;
738        }
739      }
740    };
741
742    /// This class is to wrap a node-map of \c Graph and two variables
743    /// storing values for \c S_NODE and \c T_NODE to a node-map of
744    /// stGraphWrapper<Graph>.
745    template<typename NM> class NodeMapWrapper {
746    public:
747      typedef Node KeyType;
748      typedef typename NM::ValueType ValueType;
749    protected:
750      NM* nm;
751      ValueType* s_value, t_value;
752    public:
753      NodeMapWrapper(NM& _nm, ValueType& _s_value, ValueType& _t_value) :
754        nm(&_nm), s_value(&_s_value), t_value(&_t_value) { }
755      ValueType operator[](const Node& n) const {
756        switch (n.getSpec()) {
757        case 0:
758          return (*nm)[n];
759        case 1:
760          return *s_value;
761        case 2:
762        default:
763          return *t_value;
764        }
765      }
766      void set(const Node& n, ValueType t) {
767        switch (n.getSpec()) {
768        case 0:
769          nm->set(n, t);
770          break;
771        case 1:
772          *s_value=t;
773          break;
774        case 2:
775        default:
776          *t_value=t;
777          break;
778        }
779      }
780    };
781
782    template<typename T>
783    class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
784      typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
785    protected:
786      typename GraphWrapper<Graph>::template NodeMap<T> node_value;
787    public:
788      EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
789                                                 node_value(_G) { }
790      EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
791                                                      node_value(_G, a) { }
792      T operator[](const Edge& e) const {
793        switch (e.spec) {
794        case 0:
795          return Parent::operator[](e);
796        case 1:
797          return node_value[e.n];
798        case 2:
799        default:
800          return node_value[e.n];
801        }
802      }
803      void set(const Edge& e, T t) {
804        switch (e.spec) {
805        case 0:
806          Parent::set(e, t);
807          break;
808        case 1:
809          node_value.set(e.n, t);
810          break;
811        case 2:
812        default:
813          node_value.set(e.n, t);
814          break;
815        }
816      }
817    };
818
819    /// This class is to wrap an edge-map and a node-map of \c Graph
820    /// to an edge-map of stGraphWrapper<Graph>.
821    template<typename EM, typename NM>
822    class EdgeMapWrapper {
823    public:
824      typedef Edge KeyType;
825      typedef typename EM::ValueType ValueType;
826    protected:
827      EM* em;
828      NM* nm;
829    public:
830      EdgeMapWrapper(EM& _em, NM& _nm) : em(&_em), nm(&_nm) { }
831      ValueType operator[](const Edge& e) const {
832        switch (e.getSpec()) {
833        case 0:
834          return (*em)[e];
835        case 1:
836          return (*nm)[e.getNode()];
837        case 2:
838        default:
839          return (*nm)[e.getNode()];
840        }
841      }
842      void set(const Edge& e, ValueType t) {
843        switch (e.getSpec()) {
844        case 0:
845          em->set(e, t);
846          break;
847        case 1:
848          nm->set(e.getNode(), t);
849          break;
850        case 2:
851        default:
852          nm->set(e.getNode(), t);
853          break;
854        }
855      }
856    };
857
858
859//  template<typename G>
860    friend std::ostream&
861    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) {
862      os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
863      return os;
864    }
865//  template<typename G>
866    friend std::ostream&
867    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) {
868      os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
869        " node: " << i.n << ")";
870      return os;
871    }
872
873  };
874
875  ///@}
876
877} //namespace hugo
878
879
880#endif //HUGO_BIPARTITE_GRAPH_WRAPPER_H
881
Note: See TracBrowser for help on using the repository browser.