COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_graph_wrapper.h @ 1007:a7d5fe18d8f9

Last change on this file since 1007:a7d5fe18d8f9 was 987:87f7c54892df, checked in by Alpar Juttner, 19 years ago

Naming changes:

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