lemon-0.x: src/work/marci/bipartite_graph

     1 // -*- c++ -*-

     2 #ifndef HUGO_BIPARTITE_GRAPH_WRAPPER_H

     3 #define HUGO_BIPARTITE_GRAPH_WRAPPER_H

     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

    13 #include <hugo/invalid.h>

    14 #include <iter_map.h>

    15 #include <hugo/graph_wrapper.h>

    17 namespace hugo {

    19   /// \brief A wrapper for composing a bipartite graph from a graph

    20   /// and from a node-map showing for any node which color class it belongs to.

    21   ///

    22   /// A wrapper for composing a bipartite graph.

    23   /// \c _graph have to be a reference to a graph of type \c Graph

    24   /// and \c _s_false_t_true_map is an \c IterableBoolMap

    25   /// reference containing the elements for the

    26   /// color classes S and T. \c _graph is to be referred to an undirected

    27   /// graph or a directed graph with edges oriented from S to T.

    28   ///

    29   /// \author Marton Makai

    30   template<typename Graph>

    31   class BipartiteGraphWrapper : public GraphWrapper<Graph> {

    32   protected:

    33     typedef IterableBoolMap< typename Graph::template NodeMap<int> >

    34     SFalseTTrueMap;

    35     SFalseTTrueMap* s_false_t_true_map;

    37     BipartiteGraphWrapper() : GraphWrapper<Graph>()/*,

    38 						     S_CLASS(false), T_CLASS(true)*/ { }

    39     void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) {

    40       s_false_t_true_map=&_s_false_t_true_map;

    41     }

    43   public:

    44     //marci

    45     //FIXME vhogy igy kellene, csak az en forditom nem eszi meg

    46     static const bool S_CLASS;

    47     static const bool T_CLASS;

    49     //bool S_CLASS;

    50     //bool T_CLASS;

    52     BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)

    53       : GraphWrapper<Graph>(_graph),

    54 	s_false_t_true_map(&_s_false_t_true_map)/*,

    55 						  S_CLASS(false), T_CLASS(true)*/ { }

    56     typedef typename GraphWrapper<Graph>::Node Node;

    57     //using GraphWrapper<Graph>::NodeIt;

    58     typedef typename GraphWrapper<Graph>::Edge Edge;

    59     //using GraphWrapper<Graph>::EdgeIt;

    60     class ClassNodeIt;

    61     friend class ClassNodeIt;

    62     class OutEdgeIt;

    63     friend class OutEdgeIt;

    64     class InEdgeIt;

    65     friend class InEdgeIt;

    66     class ClassNodeIt {

    67       friend class BipartiteGraphWrapper<Graph>;

    68     protected:

    69       Node n;

    70     public:

    71       ClassNodeIt() { }

    72       ClassNodeIt(const Invalid& i) : n(i) { }

    73       ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {

    74 	_G.s_false_t_true_map->first(n, _class);

    75       }

    76       //FIXME needed in new concept, important here

    77       ClassNodeIt(const Node& _n) : n(_n) { }

    78       operator Node() const { return n; }

    79     };

    80 //     class SNodeIt {

    81 //       Node n;

    82 //     public:

    83 //       SNodeIt() { }

    84 //       SNodeIt(const Invalid& i) : n(i) { }

    85 //       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {

    86 // 	_G.s_false_t_true_map->first(n, false);

    87 //       }

    88 //       operator Node() const { return n; }

    89 //     };

    90 //     class TNodeIt {

    91 //       Node n;

    92 //     public:

    93 //       TNodeIt() { }

    94 //       TNodeIt(const Invalid& i) : n(i) { }

    95 //       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {

    96 // 	_G.s_false_t_true_map->first(n, true);

    97 //       }

    98 //       operator Node() const { return n; }

    99 //     };

   100     class OutEdgeIt {

   101       friend class BipartiteGraphWrapper<Graph>;

   102     protected:

   103       typename Graph::OutEdgeIt e;

   104     public:

   105       OutEdgeIt() { }

   106       OutEdgeIt(const Invalid& i) : e(i) { }

   107       OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {

   108 	if (!(*(_G.s_false_t_true_map))[_n])

   109 	  e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));

   110 	else

   111 	  e=INVALID;

   112       }

   113       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   114     };

   115     class InEdgeIt {

   116       friend class BipartiteGraphWrapper<Graph>;

   117     protected:

   118       typename Graph::InEdgeIt e;

   119     public:

   120       InEdgeIt() { }

   121       InEdgeIt(const Invalid& i) : e(i) { }

   122       InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {

   123 	if ((*(_G.s_false_t_true_map))[_n])

   124 	  e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));

   125 	else

   126 	  e=INVALID;

   127       }

   128       operator Edge() const { return Edge(typename Graph::Edge(e)); }

   129     };

   131     using GraphWrapper<Graph>::first;

   132     ClassNodeIt& first(ClassNodeIt& n, bool _class) const {

   133       n=ClassNodeIt(*this, _class) ; return n; }

   134 //    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }

   135 //    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }

   136     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

   137       i=OutEdgeIt(*this, p); return i;

   138     }

   139     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

   140       i=InEdgeIt(*this, p); return i;

   141     }

   143     using GraphWrapper<Graph>::next;

   144     ClassNodeIt& next(ClassNodeIt& n) const {

   145       this->s_false_t_true_map->next(n.n); return n;

   146     }

   147 //     SNodeIt& next(SNodeIt& n) const {

   148 //       this->s_false_t_true_map->next(n); return n;

   149 //     }

   150 //     TNodeIt& next(TNodeIt& n) const {

   151 //       this->s_false_t_true_map->next(n); return n;

   152 //     }

   153     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }

   154     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }

   156     Node tail(const Edge& e) {

   157       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])

   158 	return Node(this->graph->tail(e));

   159       else

   160 	return Node(this->graph->head(e));

   161     }

   162     Node head(const Edge& e) {

   163       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])

   164 	return Node(this->graph->head(e));

   165       else

   166 	return Node(this->graph->tail(e));

   167     }

   169     Node aNode(const OutEdgeIt& e) const {

   170       return Node(this->graph->aNode(e.e));

   171     }

   172     Node aNode(const InEdgeIt& e) const {

   173       return Node(this->graph->aNode(e.e));

   174     }

   175     Node bNode(const OutEdgeIt& e) const {

   176       return Node(this->graph->bNode(e.e));

   177     }

   178     Node bNode(const InEdgeIt& e) const {

   179       return Node(this->graph->bNode(e.e));

   180     }

   182     /// Returns true iff \c n is in S.

   183     bool inSClass(const Node& n) const {

   184       return !(*(this->s_false_t_true_map))[n];

   185     }

   187     /// Returns true iff \c n is in T.

   188     bool inTClass(const Node& n) const {

   189       return (*(this->s_false_t_true_map))[n];

   190     }

   191   };

   194   template<typename G>

   195   const bool BipartiteGraphWrapper<G>::S_CLASS=false;

   196   template<typename G>

   197   const bool BipartiteGraphWrapper<G>::T_CLASS=true;

   199   /// \brief A bipartite graph template class

   200   ///

   201   /// This class composes a bipartite graph over a directed or undirected

   202   /// graph structure of type \c Graph.

   203   /// \c _graph have to be a reference to a graph of type \c Graph

   204   /// and \c _s_false_t_true_map is an \c IterableBoolMap

   205   /// reference containing the elements for the

   206   /// color classes S and T. \c _graph is to be referred to an undirected

   207   /// graph or a directed graph with edges oriented from S to T.

   208   ///

   209   ///\bug experimental. Do not use this while the bipartitemap augmentation

   210   /// does not work well.

   211   template<typename Graph>

   212   class BipartiteGraph : public BipartiteGraphWrapper<Graph> {

   213     typedef IterableBoolMap< typename Graph::template NodeMap<int> >

   214     SFalseTTrueMap;

   215     typedef BipartiteGraphWrapper<Graph> Parent;

   216   protected:

   217     Graph gr;

   218     typename Graph::template NodeMap<int> bipartite_map;

   219     SFalseTTrueMap s_false_t_true_map;

   220   public:

   221     typedef typename Parent::Node Node;

   222     typedef typename Parent::Edge Edge;

   223     BipartiteGraph() : BipartiteGraphWrapper<Graph>(),

   224 		       gr(), bipartite_map(gr, -1),

   225 		       s_false_t_true_map(bipartite_map) {

   226       Parent::setGraph(gr);

   227       Parent::setSFalseTTrueMap(s_false_t_true_map);

   228     }

   230     /// the \c bool parameter which can be \c S_Class or \c T_Class shows

   231     /// the color class where the new node is to be inserted.

   232     Node addNode(bool b) {

   233       Node n=Parent::graph->addNode();

   234       bipartite_map.update();

   235       //bipartite_map.set(n, -1);

   236       s_false_t_true_map.insert(n, b);

   237       return n;

   238     }

   240     /// A new edge is inserted.

   241     ///\pre \c tail have to be in \c S_Class and \c head in \c T_Class.

   242     Edge addEdge(const Node& tail, const Node& head) {

   243       return Parent::graph->addEdge(tail, head);

   244     }

   246     void erase(const Node& n) {

   247       s_false_t_true_map.remove(n);

   248       Parent::graph->erase(n);

   249     }

   250     void erase(const Edge& e) {

   251       Parent::graph->erase(e);

   252     }

   254     void clear() {

   255       FOR_EACH_LOC(typename Parent::EdgeIt, e, *this) erase(e);

   256       FOR_EACH_LOC(typename Parent::NodeIt, n, *this) erase(n);

   257     }

   258   };

   261   template<typename Graph>

   262   class stGraphWrapper;

   264 //   template<typename Graph>

   265 //   std::ostream&

   266 //   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) {

   267 //     os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";

   268 //     return os;

   269 //   }

   270 //   template<typename Graph>

   271 //   std::ostream&

   272 //   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) {

   273 //     os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<

   274 //       " node: " << i.n << ")";

   275 //     return os;

   276 //   }

   278   /// \brief A wrapper for adding extra nodes s and t to a bipartite graph

   279   /// and edges from s to each node of S and form each node of T to t.

   280   ///

   281   /// A wrapper for adding extra nodes s and t to a bipartite graph

   282   /// and edges from s to each node of S and form each node of T to t.

   283   /// This class is very useful to reduce some matching or more

   284   /// generally, capacitataed b-matching problem to a flow problem.

   285   /// According to the bipartite graph concepts the bipartite

   286   /// graph have to be oriented from S to T.

   287   ///

   288   /// \author Marton Makai

   289   template<typename Graph>

   290   class stGraphWrapper : public GraphWrapper<Graph> {

   291   public:

   292     class Node;

   293     friend class Node;

   294 //GN, int

   295 //0 normalis, 1 s, 2, true, ez az iteralasi sorrend,

   296 //es a vege a false azaz (invalid, 3)

   297     class NodeIt;

   298     friend class NodeIt;

   299 //GNI, int

   300     class Edge;

   301     friend class Edge;

   302 //GE, int, GN

   303 //0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,

   304 //invalid: (invalid, 3, invalid)

   305     class OutEdgeIt;

   306     friend class OutEdgeIt;

   307 //GO, int, GNI

   308 //normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)

   309 //s-bol (invalid, 1, first), ... (invalid, 3, invalid)

   310 //t-bol (invalid, 3, invalid)

   311     class InEdgeIt;

   312     friend class InEdgeIt;

   313 //GI, int, GNI

   314 //normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)

   315 //s-be (invalid, 3, invalid)

   316 //t-be (invalid, 2, first), ... (invalid, 3, invalid)

   317     class EdgeIt;

   318     friend class EdgeIt;

   319 //(first, 0, invalid) ...

   320 //(invalid, 1, vmi)

   321 //(invalid, 2, vmi)

   322 //invalid, 3, invalid)

   323     template <typename T> class NodeMap;

   324     template <typename T> class EdgeMap;

   326 //    template <typename T> friend class NodeMap;

   327 //    template <typename T> friend class EdgeMap;

   329     ///\todo FIXME ezt majd static-ra kell javitani

   330     const Node S_NODE;

   331     const Node T_NODE;

   333     static const bool S_CLASS=false;

   334     static const bool T_CLASS=true;

   336     stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,

   337 				    S_NODE(INVALID, 1),

   338 				    T_NODE(INVALID, 2) { }

   341 //    std::ostream&

   342 //    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);

   343 //    friend std::ostream&

   344 //    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);

   345 //    friend std::ostream&

   346 //    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i);

   348     class Node : public Graph::Node {

   349     protected:

   350       friend class GraphWrapper<Graph>;

   351       friend class stGraphWrapper<Graph>;

   352       template <typename T> friend class NodeMap;

   353       friend class Edge;

   354       friend class OutEdgeIt;

   355       friend class InEdgeIt;

   356       friend class EdgeIt;

   357       int spec;

   358     public:

   359       Node() { }

   360       Node(const typename Graph::Node& _n, int _spec=0) :

   361 	Graph::Node(_n), spec(_spec) { }

   362       Node(const Invalid& i) : Graph::Node(i), spec(3) { }

   363       friend bool operator==(const Node& u, const Node& v) {

   364 	return (u.spec==v.spec &&

   365 		static_cast<typename Graph::Node>(u)==

   366 		static_cast<typename Graph::Node>(v));

   367       }

   368       friend bool operator!=(const Node& u, const Node& v) {

   369 	return (v.spec!=u.spec ||

   370 		static_cast<typename Graph::Node>(u)!=

   371 		static_cast<typename Graph::Node>(v));

   372       }

   373 //      template<typename G>

   374 //      friend std::ostream&

   375 //      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i);

   376       friend std::ostream& operator<< (std::ostream& os, const Node& i);

   377       int getSpec() const { return spec; }

   378     };

   380     class NodeIt {

   381       friend class GraphWrapper<Graph>;

   382       friend class stGraphWrapper<Graph>;

   383       typename Graph::NodeIt n;

   384       int spec;

   385      public:

   386       NodeIt() { }

   387       NodeIt(const typename Graph::NodeIt& _n, int _spec) :

   388 	n(_n), spec(_spec) { }

   389       NodeIt(const Invalid& i) : n(i), spec(3) { }

   390       NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {

   391 	if (!_G.graph->valid(n)) spec=1;

   392       }

   393       operator Node() const { return Node(n, spec); }

   394     };

   396     class Edge : public Graph::Edge {

   397       friend class GraphWrapper<Graph>;

   398       friend class stGraphWrapper<Graph>;

   399       template <typename T> friend class EdgeMap;

   400       int spec;

   401       typename Graph::Node n;

   402     public:

   403       Edge() { }

   404       Edge(const typename Graph::Edge& _e, int _spec,

   405 	   const typename Graph::Node& _n) :

   406 	Graph::Edge(_e), spec(_spec), n(_n) {

   407       }

   408       Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }

   409       friend bool operator==(const Edge& u, const Edge& v) {

   410 	return (u.spec==v.spec &&

   411 		static_cast<typename Graph::Edge>(u)==

   412 		static_cast<typename Graph::Edge>(v) &&

   413 		u.n==v.n);

   414       }

   415       friend bool operator!=(const Edge& u, const Edge& v) {

   416 	return (v.spec!=u.spec ||

   417 		static_cast<typename Graph::Edge>(u)!=

   418 		static_cast<typename Graph::Edge>(v) ||

   419 		u.n!=v.n);

   420       }

   421 //      template<typename G>

   422 //      friend std::ostream&

   423 //      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i);

   424       friend std::ostream& operator<< (std::ostream& os, const Edge& i);

   425       int getSpec() const { return spec; }

   426       typename Graph::Node getNode() const { return n; }

   427     };

   429     class OutEdgeIt {

   430       friend class GraphWrapper<Graph>;

   431       friend class stGraphWrapper<Graph>;

   432       typename Graph::OutEdgeIt e;

   433       int spec;

   434       typename Graph::ClassNodeIt n;

   435     public:

   436       OutEdgeIt() { }

   437       OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,

   438 		const typename Graph::ClassNodeIt& _n) :

   439 	e(_e), spec(_spec), n(_n) {

   440       }

   441       OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }

   442       OutEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {

   443 	switch (_n.spec) {

   444 	  case 0 :

   445 	    if (_G.graph->inSClass(_n)) { //S, van normalis kiel

   446 	      e=typename Graph::OutEdgeIt(*(_G.graph),

   447 					  typename Graph::Node(_n));

   448 	      spec=0;

   449 	      n=INVALID;

   450 	      if (!_G.graph->valid(e)) spec=3;

   451 	    } else { //T, specko kiel van

   452 	      e=INVALID;

   453 	      spec=2;

   454 	      n=_n;

   455 	    }

   456 	    break;

   457 	  case 1:

   458 	    e=INVALID;

   459 	    spec=1;

   460 	    _G.graph->first(n, S_CLASS); //s->vmi;

   461 	    if (!_G.graph->valid(n)) spec=3; //Ha S ures

   462 	    break;

   463 	  case 2:

   464 	    e=INVALID;

   465 	    spec=3;

   466 	    n=INVALID;

   467 	    break;

   468 	}

   469       }

   470       operator Edge() const { return Edge(e, spec, n); }

   471     };

   473     class InEdgeIt {

   474       friend class GraphWrapper<Graph>;

   475       friend class stGraphWrapper<Graph>;

   476       typename Graph::InEdgeIt e;

   477       int spec;

   478       typename Graph::ClassNodeIt n;

   479     public:

   480       InEdgeIt() { }

   481       InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,

   482 	       const typename Graph::ClassNodeIt& _n) :

   483 	e(_e), spec(_spec), n(_n) {

   484       }

   485       InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }

   486       InEdgeIt(const stGraphWrapper<Graph>& _G, const Node& _n) {

   487 	switch (_n.spec) {

   488 	  case 0 :

   489 	    if (_G.graph->inTClass(_n)) { //T, van normalis beel

   490 	      e=typename Graph::InEdgeIt(*(_G.graph),

   491 					 typename Graph::Node(_n));

   492 	      spec=0;

   493 	      n=INVALID;

   494 	      if (!_G.graph->valid(e)) spec=3;

   495 	    } else { //S, specko beel van

   496 	      e=INVALID;

   497 	      spec=1;

   498 	      n=_n;

   499 	    }

   500 	    break;

   501 	  case 1:

   502 	    e=INVALID;

   503 	    spec=3;

   504 	    n=INVALID;

   505 	    break;

   506 	  case 2:

   507 	    e=INVALID;

   508 	    spec=2;

   509 	    _G.graph->first(n, T_CLASS); //vmi->t;

   510 	    if (!_G.graph->valid(n)) spec=3; //Ha T ures

   511 	    break;

   512 	}

   513       }

   514       operator Edge() const { return Edge(e, spec, n); }

   515     };

   517     class EdgeIt {

   518       friend class GraphWrapper<Graph>;

   519       friend class stGraphWrapper<Graph>;

   520       typename Graph::EdgeIt e;

   521       int spec;

   522       typename Graph::ClassNodeIt n;

   523     public:

   524       EdgeIt() { }

   525       EdgeIt(const typename Graph::EdgeIt& _e, int _spec,

   526 	     const typename Graph::ClassNodeIt& _n) :

   527 	e(_e), spec(_spec), n(_n) { }

   528       EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }

   529       EdgeIt(const stGraphWrapper<Graph>& _G) :

   530 	e(*(_G.graph)), spec(0), n(INVALID) {

   531 	if (!_G.graph->valid(e)) {

   532 	  spec=1;

   533 	  _G.graph->first(n, S_CLASS);

   534 	  if (!_G.graph->valid(n)) { //Ha S ures

   535 	    spec=2;

   536 	    _G.graph->first(n, T_CLASS);

   537 	    if (!_G.graph->valid(n)) { //Ha T ures

   538 	      spec=3;

   539 	    }

   540 	  }

   541 	}

   542       }

   543       operator Edge() const { return Edge(e, spec, n); }

   544     };

   546     NodeIt& first(NodeIt& i) const {

   547       i=NodeIt(*this); return i;

   548     }

   549     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

   550       i=OutEdgeIt(*this, p); return i;

   551     }

   552     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

   553       i=InEdgeIt(*this, p); return i;

   554     }

   555     EdgeIt& first(EdgeIt& i) const {

   556       i=EdgeIt(*this); return i;

   557     }

   559     NodeIt& next(NodeIt& i) const {

   560       switch (i.spec) {

   561 	case 0:

   562 	  this->graph->next(i.n);

   563 	  if (!this->graph->valid(i.n)) {

   564 	    i.spec=1;

   565 	  }

   566 	  break;

   567 	case 1:

   568 	  i.spec=2;

   569 	  break;

   570 	case 2:

   571 	  i.spec=3;

   572 	  break;

   573       }

   574       return i;

   575     }

   576     OutEdgeIt& next(OutEdgeIt& i) const {

   577       typename Graph::Node v;

   578       switch (i.spec) {

   579 	case 0: //normal edge

   580 	  v=this->graph->aNode(i.e);

   581 	  this->graph->next(i.e);

   582 	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk

   583 	    if (this->graph->inSClass(v)) { //S, nincs kiel

   584 	      i.spec=3;

   585 	      i.n=INVALID;

   586 	    } else { //T, van kiel

   587 	      i.spec=2;

   588 	      i.n=v;

   589 	    }

   590 	  }

   591 	  break;

   592 	case 1: //s->vmi

   593 	  this->graph->next(i.n);

   594 	  if (!this->graph->valid(i.n)) i.spec=3;

   595 	  break;

   596 	case 2: //vmi->t

   597 	  i.spec=3;

   598 	  i.n=INVALID;

   599 	  break;

   600       }

   601       return i;

   602     }

   603     InEdgeIt& next(InEdgeIt& i) const {

   604       typename Graph::Node v;

   605       switch (i.spec) {

   606 	case 0: //normal edge

   607 	  v=this->graph->aNode(i.e);

   608 	  this->graph->next(i.e);

   609 	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk

   610 	    if (this->graph->inTClass(v)) { //S, nincs beel

   611 	      i.spec=3;

   612 	      i.n=INVALID;

   613 	    } else { //S, van beel

   614 	      i.spec=1;

   615 	      i.n=v;

   616 	    }

   617 	  }

   618 	  break;

   619 	case 1: //s->vmi

   620 	  i.spec=3;

   621 	  i.n=INVALID;

   622 	  break;

   623 	case 2: //vmi->t

   624 	  this->graph->next(i.n);

   625 	  if (!this->graph->valid(i.n)) i.spec=3;

   626 	  break;

   627       }

   628       return i;

   629     }

   631     EdgeIt& next(EdgeIt& i) const {

   632       switch (i.spec) {

   633 	case 0:

   634 	  this->graph->next(i.e);

   635 	  if (!this->graph->valid(i.e)) {

   636 	    i.spec=1;

   637 	    this->graph->first(i.n, S_CLASS);

   638 	    if (!this->graph->valid(i.n)) {

   639 	      i.spec=2;

   640 	      this->graph->first(i.n, T_CLASS);

   641 	      if (!this->graph->valid(i.n)) i.spec=3;

   642 	    }

   643 	  }

   644 	  break;

   645 	case 1:

   646 	  this->graph->next(i.n);

   647 	  if (!this->graph->valid(i.n)) {

   648 	    i.spec=2;

   649 	    this->graph->first(i.n, T_CLASS);

   650 	    if (!this->graph->valid(i.n)) i.spec=3;

   651 	  }

   652 	  break;

   653 	case 2:

   654 	  this->graph->next(i.n);

   655 	  if (!this->graph->valid(i.n)) i.spec=3;

   656 	  break;

   657       }

   658       return i;

   659     }

   661     Node tail(const Edge& e) const {

   662       switch (e.spec) {

   663       case 0:

   664 	return Node(this->graph->tail(e));

   665 	break;

   666       case 1:

   667 	return S_NODE;

   668 	break;

   669       case 2:

   670       default:

   671 	return Node(e.n);

   672 	break;

   673       }

   674     }

   675     Node head(const Edge& e) const {

   676       switch (e.spec) {

   677       case 0:

   678 	return Node(this->graph->head(e));

   679 	break;

   680       case 1:

   681 	return Node(e.n);

   682 	break;

   683       case 2:

   684       default:

   685 	return T_NODE;

   686 	break;

   687       }

   688     }

   690     bool valid(const Node& n) const { return (n.spec<3); }

   691     bool valid(const Edge& e) const { return (e.spec<3); }

   693     int nodeNum() const { return this->graph->nodeNum()+2; }

   694     int edgeNum() const {

   695       return this->graph->edgeNum()+this->graph->nodeNum();

   696     }

   698     Node aNode(const OutEdgeIt& e) const { return tail(e); }

   699     Node aNode(const InEdgeIt& e) const { return head(e); }

   700     Node bNode(const OutEdgeIt& e) const { return head(e); }

   701     Node bNode(const InEdgeIt& e) const { return tail(e); }

   703     void addNode() const { }

   704     void addEdge() const { }

   706 //    Node addNode() const { return Node(this->graph->addNode()); }

   707 //    Edge addEdge(const Node& tail, const Node& head) const {

   708 //      return Edge(this->graph->addEdge(tail, head)); }

   710 //    void erase(const Node& i) const { this->graph->erase(i); }

   711 //    void erase(const Edge& i) const { this->graph->erase(i); }

   713 //    void clear() const { this->graph->clear(); }

   715     template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> {

   716       typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;

   717     protected:

   718       T s_value, t_value;

   719     public:

   720       NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G),

   721 						  s_value(),

   722 						  t_value() { }

   723       NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),

   724 						      s_value(a),

   725 						      t_value(a) { }

   726       T operator[](const Node& n) const {

   727 	switch (n.spec) {

   728 	case 0:

   729 	  return Parent::operator[](n);

   730 	case 1:

   731 	  return s_value;

   732 	case 2:

   733 	default:

   734 	  return t_value;

   735 	}

   736       }

   737       void set(const Node& n, T t) {

   738 	switch (n.spec) {

   739 	case 0:

   740 	  GraphWrapper<Graph>::template NodeMap<T>::set(n, t);

   741 	  break;

   742 	case 1:

   743 	  s_value=t;

   744 	  break;

   745 	case 2:

   746 	default:

   747 	  t_value=t;

   748 	  break;

   749 	}

   750       }

   751     };

   753     /// This class is to wrap a node-map of \c Graph and two variables

   754     /// storing values for \c S_NODE and \c T_NODE to a node-map of

   755     /// stGraphWrapper<Graph>.

   756     template<typename NM> class NodeMapWrapper {

   757     public:

   758       typedef Node KeyType;

   759       typedef typename NM::ValueType ValueType;

   760     protected:

   761       NM* nm;

   762       ValueType* s_value, t_value;

   763     public:

   764       NodeMapWrapper(NM& _nm, ValueType& _s_value, ValueType& _t_value) :

   765 	nm(&_nm), s_value(&_s_value), t_value(&_t_value) { }

   766       ValueType operator[](const Node& n) const {

   767 	switch (n.getSpec()) {

   768 	case 0:

   769 	  return (*nm)[n];

   770 	case 1:

   771 	  return *s_value;

   772 	case 2:

   773 	default:

   774 	  return *t_value;

   775 	}

   776       }

   777       void set(const Node& n, ValueType t) {

   778 	switch (n.getSpec()) {

   779 	case 0:

   780 	  nm->set(n, t);

   781 	  break;

   782 	case 1:

   783 	  *s_value=t;

   784 	  break;

   785 	case 2:

   786 	default:

   787 	  *t_value=t;

   788 	  break;

   789 	}

   790       }

   791     };

   793     template<typename T>

   794     class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {

   795       typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;

   796     protected:

   797       typename GraphWrapper<Graph>::template NodeMap<T> node_value;

   798     public:

   799       EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G),

   800 						 node_value(_G) { }

   801       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a),

   802 						      node_value(_G, a) { }

   803       T operator[](const Edge& e) const {

   804 	switch (e.spec) {

   805 	case 0:

   806 	  return Parent::operator[](e);

   807 	case 1:

   808 	  return node_value[e.n];

   809 	case 2:

   810 	default:

   811 	  return node_value[e.n];

   812 	}

   813       }

   814       void set(const Edge& e, T t) {

   815 	switch (e.spec) {

   816 	case 0:

   817 	  Parent::set(e, t);

   818 	  break;

   819 	case 1:

   820 	  node_value.set(e.n, t);

   821 	  break;

   822 	case 2:

   823 	default:

   824 	  node_value.set(e.n, t);

   825 	  break;

   826 	}

   827       }

   828     };

   830     /// This class is to wrap an edge-map and a node-map of \c Graph

   831     /// to an edge-map of stGraphWrapper<Graph>.

   832     template<typename EM, typename NM>

   833     class EdgeMapWrapper {

   834     public:

   835       typedef Edge KeyType;

   836       typedef typename EM::ValueType ValueType;

   837     protected:

   838       EM* em;

   839       NM* nm;

   840     public:

   841       EdgeMapWrapper(EM& _em, NM& _nm) : em(&_em), nm(&_nm) { }

   842       ValueType operator[](const Edge& e) const {

   843 	switch (e.getSpec()) {

   844 	case 0:

   845 	  return (*em)[e];

   846 	case 1:

   847 	  return (*nm)[e.getNode()];

   848 	case 2:

   849 	default:

   850 	  return (*nm)[e.getNode()];

   851 	}

   852       }

   853       void set(const Edge& e, ValueType t) {

   854 	switch (e.getSpec()) {

   855 	case 0:

   856 	  em->set(e, t);

   857 	  break;

   858 	case 1:

   859 	  nm->set(e.getNode(), t);

   860 	  break;

   861 	case 2:

   862 	default:

   863 	  nm->set(e.getNode(), t);

   864 	  break;

   865 	}

   866       }

   867     };

   870 //  template<typename G>

   871     friend std::ostream&

   872     operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) {

   873       os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")";

   874       return os;

   875     }

   876 //  template<typename G>

   877     friend std::ostream&

   878     operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) {

   879       os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec <<

   880 	" node: " << i.n << ")";

   881       return os;

   882     }

   884   };

   886   ///@}

   888 } //namespace hugo

   891 #endif //HUGO_BIPARTITE_GRAPH_WRAPPER_H

author	alpar
	Thu, 05 Aug 2004 07:57:20 +0000
changeset 756	c54cf1e83039
parent 558	4cbfb435ec2b
child 762	511200bdb71f
permissions	-rw-r--r--