COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_graph_wrapper.h @ 762:511200bdb71f

Last change on this file since 762:511200bdb71f was 762:511200bdb71f, checked in by marci, 16 years ago

technical corrections

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