COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_graph_wrapper.h @ 1153:4b0468de3a31

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

Naming changes:

File size: 26.6 KB
RevLine 
[174]1// -*- c++ -*-
[921]2#ifndef LEMON_BIPARTITE_GRAPH_WRAPPER_H
3#define LEMON_BIPARTITE_GRAPH_WRAPPER_H
[76]4
[491]5///\ingroup gwrappers
[457]6///\file
7///\brief Several graph wrappers.
8///
9///This file contains several useful graph wrapper functions.
10///
11///\author Marton Makai
12
[921]13#include <lemon/invalid.h>
[368]14#include <iter_map.h>
[921]15#include <lemon/graph_wrapper.h>
[762]16#include <for_each_macros.h>
[174]17
[921]18namespace lemon {
[76]19
[641]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  ///
[368]23  /// A wrapper for composing a bipartite graph.
[371]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
[368]26  /// reference containing the elements for the
[371]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.
[457]29  ///
[641]30  /// \author Marton Makai
[368]31  template<typename Graph>
32  class BipartiteGraphWrapper : public GraphWrapper<Graph> {
[768]33  public:
[389]34    typedef IterableBoolMap< typename Graph::template NodeMap<int> >
35    SFalseTTrueMap;
[768]36  protected:
[368]37    SFalseTTrueMap* s_false_t_true_map;
[393]38
[501]39    BipartiteGraphWrapper() : GraphWrapper<Graph>()/*,
40                                                     S_CLASS(false), T_CLASS(true)*/ { }
[497]41    void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) {
[499]42      s_false_t_true_map=&_s_false_t_true_map;
[497]43    }
44
[368]45  public:
[409]46    //marci
47    //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
[502]48    static const bool S_CLASS;
49    static const bool T_CLASS;
[768]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    }
[379]56   
[501]57    //bool S_CLASS;
58    //bool T_CLASS;
[409]59
[368]60    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
[500]61      : GraphWrapper<Graph>(_graph),
[501]62        s_false_t_true_map(&_s_false_t_true_map)/*,
63                                                  S_CLASS(false), T_CLASS(true)*/ { }
[368]64    typedef typename GraphWrapper<Graph>::Node Node;
65    //using GraphWrapper<Graph>::NodeIt;
66    typedef typename GraphWrapper<Graph>::Edge Edge;
67    //using GraphWrapper<Graph>::EdgeIt;
[393]68    class ClassNodeIt;
69    friend class ClassNodeIt;
70    class OutEdgeIt;
71    friend class OutEdgeIt;
72    class InEdgeIt;
73    friend class InEdgeIt;
[902]74    class ClassNodeIt : public Node {
[393]75      friend class BipartiteGraphWrapper<Graph>;
76    protected:
[902]77      const BipartiteGraphWrapper<Graph>* gw;
[368]78    public:
[379]79      ClassNodeIt() { }
[902]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);
[368]84      }
[381]85      //FIXME needed in new concept, important here
[902]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      }
[368]92    };
[379]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//     };
[902]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//     };
[368]143
144    using GraphWrapper<Graph>::first;
[379]145    ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
[902]146      n=ClassNodeIt(*this, _class); return n;
147    }
[379]148//    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
149//    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
[902]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//     }
[368]156
[902]157//     using GraphWrapper<Graph>::next;
158//     ClassNodeIt& next(ClassNodeIt& n) const {
159//       this->s_false_t_true_map->next(n.n); return n;
160//     }
[379]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//     }
[902]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; }
[368]169
[986]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));
[902]173//       else
[986]174//      return Node(this->graph->target(e));   
[902]175//     }
[986]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));
[902]179//       else
[986]180//      return Node(this->graph->source(e));   
[902]181//     }
[368]182
[902]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//     }
[379]195
[641]196    /// Returns true iff \c n is in S.
[379]197    bool inSClass(const Node& n) const {
[381]198      return !(*(this->s_false_t_true_map))[n];
[379]199    }
[641]200
201    /// Returns true iff \c n is in T.
[379]202    bool inTClass(const Node& n) const {
[381]203      return (*(this->s_false_t_true_map))[n];
[379]204    }
[368]205  };
206
[502]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
[641]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
[497]224  /// does not work well.
225  template<typename Graph>
226  class BipartiteGraph : public BipartiteGraphWrapper<Graph> {
[768]227//     typedef IterableBoolMap< typename Graph::template NodeMap<int> >
228//     SFalseTTrueMap;
[497]229    typedef BipartiteGraphWrapper<Graph> Parent;
230  protected:
231    Graph gr;
232    typename Graph::template NodeMap<int> bipartite_map;
[768]233    typename Parent::SFalseTTrueMap s_false_t_true_map;
[497]234  public:
235    typedef typename Parent::Node Node;
236    typedef typename Parent::Edge Edge;
[499]237    BipartiteGraph() : BipartiteGraphWrapper<Graph>(),
[500]238                       gr(), bipartite_map(gr, -1),
[497]239                       s_false_t_true_map(bipartite_map) {
240      Parent::setGraph(gr);
[499]241      Parent::setSFalseTTrueMap(s_false_t_true_map);
[497]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.
[498]246    Node addNode(bool b) {
247      Node n=Parent::graph->addNode();
248      bipartite_map.update();
[501]249      //bipartite_map.set(n, -1);
[498]250      s_false_t_true_map.insert(n, b);
251      return n;
252    }
[497]253
254    /// A new edge is inserted.
[986]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);
[498]258    }
[497]259
[498]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    }
[497]267   
268    void clear() {
[558]269      FOR_EACH_LOC(typename Parent::EdgeIt, e, *this) erase(e);
270      FOR_EACH_LOC(typename Parent::NodeIt, n, *this) erase(n);
[497]271    }
272  };
273
[768]274  template<typename Graph, typename sIterableMap, typename tIterableMap>
275  class stGraphWrapper;
[497]276
[768]277  /// Easier stuff for bipartite graphs.
[435]278  template<typename Graph>
[768]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  };
[435]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//   }
[341]302
[641]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.
[457]312  ///
[641]313  /// \author Marton Makai
[768]314  template<typename Graph, typename sIterableMap, typename tIterableMap>
[379]315  class stGraphWrapper : public GraphWrapper<Graph> {
[768]316  protected:   
317    const sIterableMap* s_iterable_map;
318    const tIterableMap* t_iterable_map;
[379]319  public:
320    class Node;
[381]321    friend class Node;
[379]322//GN, int
[768]323//0 normalis, 1 s, 2 t, ez az iteralasi sorrend,
[379]324//es a vege a false azaz (invalid, 3)   
325    class NodeIt;
[381]326    friend class NodeIt;
[379]327//GNI, int
328    class Edge;
[381]329    friend class Edge;
[379]330//GE, int, GN
331//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
332//invalid: (invalid, 3, invalid)
333    class OutEdgeIt;
[381]334    friend class OutEdgeIt;
[379]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;
[381]340    friend class InEdgeIt;
[379]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;
[381]346    friend class EdgeIt;
[379]347//(first, 0, invalid) ...
348//(invalid, 1, vmi)
349//(invalid, 2, vmi)
350//invalid, 3, invalid)
351    template <typename T> class NodeMap;
[510]352    template <typename T> class EdgeMap;
[341]353
[379]354//    template <typename T> friend class NodeMap;
355//    template <typename T> friend class EdgeMap;
[341]356
[502]357    ///\todo FIXME ezt majd static-ra kell javitani
[379]358    const Node S_NODE;
359    const Node T_NODE;
[341]360
[379]361    static const bool S_CLASS=false;
362    static const bool T_CLASS=true;
[341]363
[768]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) { }
[341]373
[435]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
[379]382    class Node : public Graph::Node {
383    protected:
384      friend class GraphWrapper<Graph>;
[768]385      friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
[389]386      template <typename T> friend class NodeMap;
[380]387      friend class Edge;
388      friend class OutEdgeIt;
389      friend class InEdgeIt;
390      friend class EdgeIt;
[379]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));
[409]406      }
[435]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);
[379]411      int getSpec() const { return spec; }
412    };
[409]413
[379]414    class NodeIt {
415      friend class GraphWrapper<Graph>;
[768]416      friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
[379]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) { }
[768]424      NodeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G)
425        : n(*(_G.graph)), spec(0) {
[409]426        if (!_G.graph->valid(n)) spec=1;
[379]427      }
428      operator Node() const { return Node(n, spec); }
429    };
[409]430
[379]431    class Edge : public Graph::Edge {
432      friend class GraphWrapper<Graph>;
[768]433      friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
[510]434      template <typename T> friend class EdgeMap;
[379]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      }
[435]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);
[379]460      int getSpec() const { return spec; }
[510]461      typename Graph::Node getNode() const { return n; }
[379]462    };
[409]463
[379]464    class OutEdgeIt {
465      friend class GraphWrapper<Graph>;
[768]466      friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
[379]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) { }
[768]477      OutEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G,
478                const Node& _n) {
[379]479        switch (_n.spec) {
480          case 0 :
[381]481            if (_G.graph->inSClass(_n)) { //S, van normalis kiel
[379]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    };
[409]508
[379]509    class InEdgeIt {
510      friend class GraphWrapper<Graph>;
[768]511      friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
[379]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) { }
[768]522      InEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G,
523               const Node& _n) {
[379]524        switch (_n.spec) {
525          case 0 :
[381]526            if (_G.graph->inTClass(_n)) { //T, van normalis beel
[379]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;
[409]542            break;
[379]543          case 2:
544            e=INVALID;
[409]545            spec=2;
[379]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    };
[409]553
[379]554    class EdgeIt {
555      friend class GraphWrapper<Graph>;
[768]556      friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
[379]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) { }
[768]566      EdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) :
[379]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    };
[341]582   
[379]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    }
[341]595
[379]596    NodeIt& next(NodeIt& i) const {
597      switch (i.spec) {
598        case 0:
[389]599          this->graph->next(i.n);
600          if (!this->graph->valid(i.n)) {
[379]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 {
[393]614      typename Graph::Node v;
[379]615      switch (i.spec) {
616        case 0: //normal edge
[409]617          v=this->graph->aNode(i.e);
[389]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
[379]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
[389]630          this->graph->next(i.n);
631          if (!this->graph->valid(i.n)) i.spec=3;
[379]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 {
[393]641      typename Graph::Node v;
[379]642      switch (i.spec) {
643        case 0: //normal edge
[393]644          v=this->graph->aNode(i.e);
[389]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
[379]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
[389]661          this->graph->next(i.n);
662          if (!this->graph->valid(i.n)) i.spec=3;
[379]663          break;
664      }
665      return i;
666    }
[341]667
[379]668    EdgeIt& next(EdgeIt& i) const {
669      switch (i.spec) {
670        case 0:
[389]671          this->graph->next(i.e);
672          if (!this->graph->valid(i.e)) {
[379]673            i.spec=1;
[389]674            this->graph->first(i.n, S_CLASS);
675            if (!this->graph->valid(i.n)) {
[379]676              i.spec=2;
[389]677              this->graph->first(i.n, T_CLASS);
678              if (!this->graph->valid(i.n)) i.spec=3;
[379]679            }
680          }
681          break;
682        case 1:
[389]683          this->graph->next(i.n);
684          if (!this->graph->valid(i.n)) {
[379]685            i.spec=2;
[389]686            this->graph->first(i.n, T_CLASS);
687            if (!this->graph->valid(i.n)) i.spec=3;
[379]688          }
689          break;
690        case 2:
[389]691          this->graph->next(i.n);
692          if (!this->graph->valid(i.n)) i.spec=3;
[379]693          break;
694      }
695      return i;
696    }   
[341]697
[986]698    Node source(const Edge& e) const {
[379]699      switch (e.spec) {
[393]700      case 0:
[986]701        return Node(this->graph->source(e));
[393]702        break;
703      case 1:
704        return S_NODE;
705        break;
706      case 2:
707      default:
708        return Node(e.n);
709        break;
[379]710      }
711    }
[986]712    Node target(const Edge& e) const {
[379]713      switch (e.spec) {
[393]714      case 0:
[986]715        return Node(this->graph->target(e));
[393]716        break;
717      case 1:
718        return Node(e.n);
719        break;
720      case 2:
721      default:
722        return T_NODE;
723        break;
[379]724      }
725    }
[341]726
[379]727    bool valid(const Node& n) const { return (n.spec<3); }
728    bool valid(const Edge& e) const { return (e.spec<3); }
729
[409]730    int nodeNum() const { return this->graph->nodeNum()+2; }
731    int edgeNum() const {
732      return this->graph->edgeNum()+this->graph->nodeNum();
733    }
[341]734 
[986]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); }
[409]739
740    void addNode() const { }
741    void addEdge() const { }
742   
[389]743//    Node addNode() const { return Node(this->graph->addNode()); }
[986]744//    Edge addEdge(const Node& source, const Node& target) const {
745//      return Edge(this->graph->addEdge(source, target)); }
[341]746
[389]747//    void erase(const Node& i) const { this->graph->erase(i); }
748//    void erase(const Edge& i) const { this->graph->erase(i); }
[341]749 
[389]750//    void clear() const { this->graph->clear(); }
[341]751   
[389]752    template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {
753      typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
[510]754    protected:
[379]755      T s_value, t_value;
756    public:
[768]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) { }
[379]765      T operator[](const Node& n) const {
766        switch (n.spec) {
[393]767        case 0:
768          return Parent::operator[](n);
769        case 1:
770          return s_value;
771        case 2:
772        default:
773          return t_value;
[379]774        }
775      }
776      void set(const Node& n, T t) {
777        switch (n.spec) {
[393]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;
[379]788        }
789      }
790    };
[341]791
[510]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
[768]794    /// stGraphWrapper<Graph, sIterableMap, tIterableMap>.
[510]795    template<typename NM> class NodeMapWrapper {
796    public:
[987]797      typedef Node Key;
798      typedef typename NM::Value Value;
[510]799    protected:
800      NM* nm;
[987]801      Value* s_value, t_value;
[510]802    public:
[987]803      NodeMapWrapper(NM& _nm, Value& _s_value, Value& _t_value) :
[510]804        nm(&_nm), s_value(&_s_value), t_value(&_t_value) { }
[987]805      Value operator[](const Node& n) const {
[510]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      }
[987]816      void set(const Node& n, Value t) {
[510]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:
[389]836      typename GraphWrapper<Graph>::template NodeMap<T> node_value;
[379]837    public:
[768]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) { }
[379]844      T operator[](const Edge& e) const {
845        switch (e.spec) {
[393]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];
[379]853        }
854      }
855      void set(const Edge& e, T t) {
856        switch (e.spec) {
[393]857        case 0:
[409]858          Parent::set(e, t);
[393]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;
[379]867        }
868      }
869    };
[409]870
[510]871    /// This class is to wrap an edge-map and a node-map of \c Graph
[768]872    /// to an edge-map of stGraphWrapper<Graph, sIterableMap, tIterableMap>.
[510]873    template<typename EM, typename NM>
874    class EdgeMapWrapper {
875    public:
[987]876      typedef Edge Key;
877      typedef typename EM::Value Value;
[510]878    protected:
879      EM* em;
880      NM* nm;
881    public:
882      EdgeMapWrapper(EM& _em, NM& _nm) : em(&_em), nm(&_nm) { }
[987]883      Value operator[](const Edge& e) const {
[510]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      }
[987]894      void set(const Edge& e, Value t) {
[510]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
[409]910
[435]911//  template<typename G>
912    friend std::ostream&
913    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) {
[409]914      os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";
915      return os;
916    }
[435]917//  template<typename G>
918    friend std::ostream&
919    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) {
[409]920      os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<
921        " node: " << i.n << ")";
922      return os;
923    }
924
[379]925  };
926
[406]927  ///@}
[341]928
[921]929} //namespace lemon
[76]930
[406]931
[921]932#endif //LEMON_BIPARTITE_GRAPH_WRAPPER_H
[76]933
Note: See TracBrowser for help on using the repository browser.