COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_graph_wrapper.h @ 768:a5e9303a5511

Last change on this file since 768:a5e9303a5511 was 768:a5e9303a5511, checked in by marci, 15 years ago

stGraphWrapper modifications

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