COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_graph_wrapper.h @ 501:20e4941a354a

Last change on this file since 501:20e4941a354a was 501:20e4941a354a, checked in by marci, 16 years ago

bipatite

File size: 22.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 <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=false;
44    static const bool T_CLASS=true;
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  ///\bug Do not use this while the bipartitemap augmentation
188  /// does not work well.
189  template<typename Graph>
190  class BipartiteGraph : public BipartiteGraphWrapper<Graph> {
191    typedef IterableBoolMap< typename Graph::template NodeMap<int> >
192    SFalseTTrueMap;
193    typedef BipartiteGraphWrapper<Graph> Parent;
194  protected:
195    Graph gr;
196    typename Graph::template NodeMap<int> bipartite_map;
197    SFalseTTrueMap s_false_t_true_map;
198  public:
199    typedef typename Parent::Node Node;
200    typedef typename Parent::Edge Edge;
201    BipartiteGraph() : BipartiteGraphWrapper<Graph>(),
202                       gr(), bipartite_map(gr, -1),
203                       s_false_t_true_map(bipartite_map) {
204      Parent::setGraph(gr);
205      Parent::setSFalseTTrueMap(s_false_t_true_map);
206    }
207
208    /// the \c bool parameter which can be \c S_Class or \c T_Class shows
209    /// the color class where the new node is to be inserted.
210    Node addNode(bool b) {
211      Node n=Parent::graph->addNode();
212      bipartite_map.update();
213      //bipartite_map.set(n, -1);
214      s_false_t_true_map.insert(n, b);
215      return n;
216    }
217
218    /// A new edge is inserted.
219    ///\pre \c tail have to be in \c S_Class and \c head in \c T_Class.
220    Edge addEdge(const Node& tail, const Node& head) {
221      return Parent::graph->addEdge(tail, head);
222    }
223
224    void erase(const Node& n) {
225      s_false_t_true_map.remove(n);
226      Parent::graph->erase(n);
227    }
228    void erase(const Edge& e) {
229      Parent::graph->erase(e);
230    }
231   
232    void clear() {
233      FOR_EACH_LOC(typename Parent::EdgeIt, e, G) erase(e);
234      FOR_EACH_LOC(typename Parent::NodeIt, n, G) erase(n);
235    }
236  };
237
238
239  template<typename Graph>
240  class stGraphWrapper;
241
242//   template<typename Graph>
243//   std::ostream&
244//   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) {
245//     os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
246//     return os;
247//   }
248//   template<typename Graph>
249//   std::ostream&
250//   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) {
251//     os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
252//       " node: " << i.n << ")";
253//     return os;
254//   }
255
256  /// experimentral, do not try it.
257  /// It eats a bipartite graph, oriented from S to T.
258  /// Such one can be made e.g. by the above wrapper.
259  ///
260  ///\author Marton Makai
261  template<typename Graph>
262  class stGraphWrapper : public GraphWrapper<Graph> {
263  public:
264    class Node;
265    friend class Node;
266//GN, int
267//0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
268//es a vege a false azaz (invalid, 3)   
269    class NodeIt;
270    friend class NodeIt;
271//GNI, int
272    class Edge;
273    friend class Edge;
274//GE, int, GN
275//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
276//invalid: (invalid, 3, invalid)
277    class OutEdgeIt;
278    friend class OutEdgeIt;
279//GO, int, GNI
280//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
281//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
282//t-bol (invalid, 3, invalid)
283    class InEdgeIt;
284    friend class InEdgeIt;
285//GI, int, GNI
286//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
287//s-be (invalid, 3, invalid)
288//t-be (invalid, 2, first), ... (invalid, 3, invalid)
289    class EdgeIt;
290    friend class EdgeIt;
291//(first, 0, invalid) ...
292//(invalid, 1, vmi)
293//(invalid, 2, vmi)
294//invalid, 3, invalid)
295    template <typename T> class NodeMap;
296    template <typename T, typename Parent> class EdgeMap;
297
298//    template <typename T> friend class NodeMap;
299//    template <typename T> friend class EdgeMap;
300
301    const Node S_NODE;
302    const Node T_NODE;
303
304    static const bool S_CLASS=false;
305    static const bool T_CLASS=true;
306
307    stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
308                                    S_NODE(INVALID, 1),
309                                    T_NODE(INVALID, 2) { }
310
311   
312//    std::ostream&
313//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
314//    friend std::ostream&
315//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
316//    friend std::ostream&
317//    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i);
318
319    class Node : public Graph::Node {
320    protected:
321      friend class GraphWrapper<Graph>;
322      friend class stGraphWrapper<Graph>;
323      template <typename T> friend class NodeMap;
324      friend class Edge;
325      friend class OutEdgeIt;
326      friend class InEdgeIt;
327      friend class EdgeIt;
328      int spec;
329    public:
330      Node() { }
331      Node(const typename Graph::Node& _n, int _spec=0) :
332        Graph::Node(_n), spec(_spec) { }
333      Node(const Invalid& i) : Graph::Node(i), spec(3) { }
334      friend bool operator==(const Node& u, const Node& v) {
335        return (u.spec==v.spec &&
336                static_cast<typename Graph::Node>(u)==
337                static_cast<typename Graph::Node>(v));
338      }
339      friend bool operator!=(const Node& u, const Node& v) {
340        return (v.spec!=u.spec ||
341                static_cast<typename Graph::Node>(u)!=
342                static_cast<typename Graph::Node>(v));
343      }
344//      template<typename G>
345//      friend std::ostream&
346//      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i);
347      friend std::ostream& operator<< (std::ostream& os, const Node& i);
348      int getSpec() const { return spec; }
349    };
350
351    class NodeIt {
352      friend class GraphWrapper<Graph>;
353      friend class stGraphWrapper<Graph>;
354      typename Graph::NodeIt n;
355      int spec;
356     public:
357      NodeIt() { }
358      NodeIt(const typename Graph::NodeIt& _n, int _spec) :
359        n(_n), spec(_spec) { }
360      NodeIt(const Invalid& i) : n(i), spec(3) { }
361      NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
362        if (!_G.graph->valid(n)) spec=1;
363      }
364      operator Node() const { return Node(n, spec); }
365    };
366
367    class Edge : public Graph::Edge {
368      friend class GraphWrapper<Graph>;
369      friend class stGraphWrapper<Graph>;
370      template <typename T, typename Parent> friend class EdgeMap;
371      int spec;
372      typename Graph::Node n;
373    public:
374      Edge() { }
375      Edge(const typename Graph::Edge& _e, int _spec,
376           const typename Graph::Node& _n) :
377        Graph::Edge(_e), spec(_spec), n(_n) {
378      }
379      Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
380      friend bool operator==(const Edge& u, const Edge& v) {
381        return (u.spec==v.spec &&
382                static_cast<typename Graph::Edge>(u)==
383                static_cast<typename Graph::Edge>(v) &&
384                u.n==v.n);
385      }
386      friend bool operator!=(const Edge& u, const Edge& v) {
387        return (v.spec!=u.spec ||
388                static_cast<typename Graph::Edge>(u)!=
389                static_cast<typename Graph::Edge>(v) ||
390                u.n!=v.n);
391      }
392//      template<typename G>
393//      friend std::ostream&
394//      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i);
395      friend std::ostream& operator<< (std::ostream& os, const Edge& i);
396      int getSpec() const { return spec; }
397    };
398
399    class OutEdgeIt {
400      friend class GraphWrapper<Graph>;
401      friend class stGraphWrapper<Graph>;
402      typename Graph::OutEdgeIt e;
403      int spec;
404      typename Graph::ClassNodeIt n;
405    public:
406      OutEdgeIt() { }
407      OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
408                const typename Graph::ClassNodeIt& _n) :
409        e(_e), spec(_spec), n(_n) {
410      }
411      OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
412      OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
413        switch (_n.spec) {
414          case 0 :
415            if (_G.graph->inSClass(_n)) { //S, van normalis kiel
416              e=typename Graph::OutEdgeIt(*(_G.graph),
417                                          typename Graph::Node(_n));
418              spec=0;
419              n=INVALID;
420              if (!_G.graph->valid(e)) spec=3;
421            } else { //T, specko kiel van
422              e=INVALID;
423              spec=2;
424              n=_n;
425            }
426            break;
427          case 1:
428            e=INVALID;
429            spec=1;
430            _G.graph->first(n, S_CLASS); //s->vmi;
431            if (!_G.graph->valid(n)) spec=3; //Ha S ures
432            break;
433          case 2:
434            e=INVALID;
435            spec=3;
436            n=INVALID;
437            break;
438        }
439      }
440      operator Edge() const { return Edge(e, spec, n); }
441    };
442
443    class InEdgeIt {
444      friend class GraphWrapper<Graph>;
445      friend class stGraphWrapper<Graph>;
446      typename Graph::InEdgeIt e;
447      int spec;
448      typename Graph::ClassNodeIt n;
449    public:
450      InEdgeIt() { }
451      InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
452               const typename Graph::ClassNodeIt& _n) :
453        e(_e), spec(_spec), n(_n) {
454      }
455      InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
456      InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {
457        switch (_n.spec) {
458          case 0 :
459            if (_G.graph->inTClass(_n)) { //T, van normalis beel
460              e=typename Graph::InEdgeIt(*(_G.graph),
461                                         typename Graph::Node(_n));
462              spec=0;
463              n=INVALID;
464              if (!_G.graph->valid(e)) spec=3;
465            } else { //S, specko beel van
466              e=INVALID;
467              spec=1;
468              n=_n;
469            }
470            break;
471          case 1:
472            e=INVALID;
473            spec=3;
474            n=INVALID;
475            break;
476          case 2:
477            e=INVALID;
478            spec=2;
479            _G.graph->first(n, T_CLASS); //vmi->t;
480            if (!_G.graph->valid(n)) spec=3; //Ha T ures
481            break;
482        }
483      }
484      operator Edge() const { return Edge(e, spec, n); }
485    };
486
487    class EdgeIt {
488      friend class GraphWrapper<Graph>;
489      friend class stGraphWrapper<Graph>;
490      typename Graph::EdgeIt e;
491      int spec;
492      typename Graph::ClassNodeIt n;
493    public:
494      EdgeIt() { }
495      EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
496             const typename Graph::ClassNodeIt& _n) :
497        e(_e), spec(_spec), n(_n) { }
498      EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
499      EdgeIt(const stGraphWrapper<Graph>& _G) :
500        e(*(_G.graph)), spec(0), n(INVALID) {
501        if (!_G.graph->valid(e)) {
502          spec=1;
503          _G.graph->first(n, S_CLASS);
504          if (!_G.graph->valid(n)) { //Ha S ures
505            spec=2;
506            _G.graph->first(n, T_CLASS);
507            if (!_G.graph->valid(n)) { //Ha T ures
508              spec=3;
509            }
510          }
511        }
512      }
513      operator Edge() const { return Edge(e, spec, n); }
514    };
515   
516    NodeIt& first(NodeIt& i) const {
517      i=NodeIt(*this); return i;
518    }
519    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
520      i=OutEdgeIt(*this, p); return i;
521    }
522    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
523      i=InEdgeIt(*this, p); return i;
524    }
525    EdgeIt& first(EdgeIt& i) const {
526      i=EdgeIt(*this); return i;
527    }
528
529    NodeIt& next(NodeIt& i) const {
530      switch (i.spec) {
531        case 0:
532          this->graph->next(i.n);
533          if (!this->graph->valid(i.n)) {
534            i.spec=1;
535          }
536          break;
537        case 1:
538          i.spec=2;
539          break;
540        case 2:
541          i.spec=3;
542          break;
543      }
544      return i;
545    }
546    OutEdgeIt& next(OutEdgeIt& i) const {
547      typename Graph::Node v;
548      switch (i.spec) {
549        case 0: //normal edge
550          v=this->graph->aNode(i.e);
551          this->graph->next(i.e);
552          if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
553            if (this->graph->inSClass(v)) { //S, nincs kiel
554              i.spec=3;
555              i.n=INVALID;
556            } else { //T, van kiel
557              i.spec=2;
558              i.n=v;
559            }
560          }
561          break;
562        case 1: //s->vmi
563          this->graph->next(i.n);
564          if (!this->graph->valid(i.n)) i.spec=3;
565          break;
566        case 2: //vmi->t
567          i.spec=3;
568          i.n=INVALID;
569          break;
570      }
571      return i;
572    }
573    InEdgeIt& next(InEdgeIt& i) const {
574      typename Graph::Node v;
575      switch (i.spec) {
576        case 0: //normal edge
577          v=this->graph->aNode(i.e);
578          this->graph->next(i.e);
579          if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
580            if (this->graph->inTClass(v)) { //S, nincs beel
581              i.spec=3;
582              i.n=INVALID;
583            } else { //S, van beel
584              i.spec=1;
585              i.n=v;
586            }
587          }
588          break;
589        case 1: //s->vmi
590          i.spec=3;
591          i.n=INVALID;
592          break;
593        case 2: //vmi->t
594          this->graph->next(i.n);
595          if (!this->graph->valid(i.n)) i.spec=3;
596          break;
597      }
598      return i;
599    }
600
601    EdgeIt& next(EdgeIt& i) const {
602      switch (i.spec) {
603        case 0:
604          this->graph->next(i.e);
605          if (!this->graph->valid(i.e)) {
606            i.spec=1;
607            this->graph->first(i.n, S_CLASS);
608            if (!this->graph->valid(i.n)) {
609              i.spec=2;
610              this->graph->first(i.n, T_CLASS);
611              if (!this->graph->valid(i.n)) i.spec=3;
612            }
613          }
614          break;
615        case 1:
616          this->graph->next(i.n);
617          if (!this->graph->valid(i.n)) {
618            i.spec=2;
619            this->graph->first(i.n, T_CLASS);
620            if (!this->graph->valid(i.n)) i.spec=3;
621          }
622          break;
623        case 2:
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    Node tail(const Edge& e) const {
632      switch (e.spec) {
633      case 0:
634        return Node(this->graph->tail(e));
635        break;
636      case 1:
637        return S_NODE;
638        break;
639      case 2:
640      default:
641        return Node(e.n);
642        break;
643      }
644    }
645    Node head(const Edge& e) const {
646      switch (e.spec) {
647      case 0:
648        return Node(this->graph->head(e));
649        break;
650      case 1:
651        return Node(e.n);
652        break;
653      case 2:
654      default:
655        return T_NODE;
656        break;
657      }
658    }
659
660    bool valid(const Node& n) const { return (n.spec<3); }
661    bool valid(const Edge& e) const { return (e.spec<3); }
662
663    int nodeNum() const { return this->graph->nodeNum()+2; }
664    int edgeNum() const {
665      return this->graph->edgeNum()+this->graph->nodeNum();
666    }
667 
668    Node aNode(const OutEdgeIt& e) const { return tail(e); }
669    Node aNode(const InEdgeIt& e) const { return head(e); }
670    Node bNode(const OutEdgeIt& e) const { return head(e); }
671    Node bNode(const InEdgeIt& e) const { return tail(e); }
672
673    void addNode() const { }
674    void addEdge() const { }
675   
676//    Node addNode() const { return Node(this->graph->addNode()); }
677//    Edge addEdge(const Node& tail, const Node& head) const {
678//      return Edge(this->graph->addEdge(tail, head)); }
679
680//    void erase(const Node& i) const { this->graph->erase(i); }
681//    void erase(const Edge& i) const { this->graph->erase(i); }
682 
683//    void clear() const { this->graph->clear(); }
684   
685    template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
686      typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
687      T s_value, t_value;
688    public:
689      NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G),
690                                                  s_value(),
691                                                  t_value() { }
692      NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
693                                                      s_value(a),
694                                                      t_value(a) { }
695      T operator[](const Node& n) const {
696        switch (n.spec) {
697        case 0:
698          return Parent::operator[](n);
699          break;
700        case 1:
701          return s_value;
702          break;
703        case 2:
704        default:
705          return t_value;
706          break;
707        }
708      }
709      void set(const Node& n, T t) {
710        switch (n.spec) {
711        case 0:
712          GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
713          break;
714        case 1:
715          s_value=t;
716          break;
717        case 2:
718        default:
719          t_value=t;
720          break;
721        }
722      }
723    };
724
725    template<typename T,
726             typename Parent=
727             typename GraphWrapper<Graph>::template EdgeMap<T> >
728    class EdgeMap : public Parent {
729      //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
730      typename GraphWrapper<Graph>::template NodeMap<T> node_value;
731    public:
732      EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
733                                                 node_value(_G) { }
734      EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
735                                                      node_value(_G, a) { }
736      T operator[](const Edge& e) const {
737        switch (e.spec) {
738        case 0:
739          return Parent::operator[](e);
740          break;
741        case 1:
742          return node_value[e.n];
743          break;
744        case 2:
745        default:
746          return node_value[e.n];
747          break;
748        }
749      }
750      void set(const Edge& e, T t) {
751        switch (e.spec) {
752        case 0:
753          Parent::set(e, t);
754          break;
755        case 1:
756          node_value.set(e.n, t);
757          break;
758        case 2:
759        default:
760          node_value.set(e.n, t);
761          break;
762        }
763      }
764    };
765
766//     template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {
767//       typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
768//       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
769//     public:
770//       EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),
771//                                               node_value(_G) { }
772//       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),
773//                                                    node_value(_G, a) { }
774//       T operator[](const Edge& e) const {
775//      switch (e.spec) {
776//      case 0:
777//        return Parent::operator[](e);
778//        break;
779//      case 1:
780//        return node_value[e.n];
781//        break;
782//      case 2:
783//      default:
784//        return node_value[e.n];
785//        break;
786//      }
787//       }
788//       void set(const Edge& e, T t) {
789//      switch (e.spec) {
790//      case 0:
791//        GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
792//        break;
793//      case 1:
794//        node_value.set(e.n, t);
795//        break;
796//      case 2:
797//      default:
798//        node_value.set(e.n, t);
799//        break;
800//      }
801//       }
802//     };
803
804//  template<typename G>
805    friend std::ostream&
806    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) {
807      os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
808      return os;
809    }
810//  template<typename G>
811    friend std::ostream&
812    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) {
813      os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
814        " node: " << i.n << ")";
815      return os;
816    }
817
818  };
819
820  ///@}
821
822} //namespace hugo
823
824
825#endif //HUGO_GRAPH_WRAPPER_H
826
Note: See TracBrowser for help on using the repository browser.