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