COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_graph_wrapper.h @ 643:f8053cb51047

Last change on this file since 643:f8053cb51047 was 641:bfd6c14e2975, checked in by marci, 17 years ago

some documentation in stGraphWrapper<Gr> and BipartiteGraphWrapper?<Gr>

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