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>

    16 #include <for_each_macros.h>

    18 namespace hugo {

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

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

    22   ///

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

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

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

    26   /// reference containing the elements for the

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

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

    29   ///

    30   /// \author Marton Makai

    31   template<typename Graph>

    32   class BipartiteGraphWrapper : public GraphWrapper<Graph> {

    33   protected:

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

    35     SFalseTTrueMap;

    36     SFalseTTrueMap* s_false_t_true_map;

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

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

    40     void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) {

    41       s_false_t_true_map=&_s_false_t_true_map;

    42     }

    44   public:

    45     //marci

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

    47     static const bool S_CLASS;

    48     static const bool T_CLASS;

    50     //bool S_CLASS;

    51     //bool T_CLASS;

    53     BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)

    54       : GraphWrapper<Graph>(_graph),

    55 	s_false_t_true_map(&_s_false_t_true_map)/*,

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

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

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

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

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

    61     class ClassNodeIt;

    62     friend class ClassNodeIt;

    63     class OutEdgeIt;

    64     friend class OutEdgeIt;

    65     class InEdgeIt;

    66     friend class InEdgeIt;

    67     class ClassNodeIt {

    68       friend class BipartiteGraphWrapper<Graph>;

    69     protected:

    70       Node n;

    71     public:

    72       ClassNodeIt() { }

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

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

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

    76       }

    77       //FIXME needed in new concept, important here

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

    79       operator Node() const { return n; }

    80     };

    81 //     class SNodeIt {

    82 //       Node n;

    83 //     public:

    84 //       SNodeIt() { }

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

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

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

    88 //       }

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

    90 //     };

    91 //     class TNodeIt {

    92 //       Node n;

    93 //     public:

    94 //       TNodeIt() { }

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

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

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

    98 //       }

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

   100 //     };

   101     class OutEdgeIt {

   102       friend class BipartiteGraphWrapper<Graph>;

   103     protected:

   104       typename Graph::OutEdgeIt e;

   105     public:

   106       OutEdgeIt() { }

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

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

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

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

   111 	else

   112 	  e=INVALID;

   113       }

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

   115     };

   116     class InEdgeIt {

   117       friend class BipartiteGraphWrapper<Graph>;

   118     protected:

   119       typename Graph::InEdgeIt e;

   120     public:

   121       InEdgeIt() { }

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

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

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

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

   126 	else

   127 	  e=INVALID;

   128       }

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

   130     };

   132     using GraphWrapper<Graph>::first;

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

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

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

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

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

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

   139     }

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

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

   142     }

   144     using GraphWrapper<Graph>::next;

   145     ClassNodeIt& next(ClassNodeIt& n) const {

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

   147     }

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

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

   150 //     }

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

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

   153 //     }

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

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

   157     Node tail(const Edge& e) {

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

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

   160       else

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

   162     }

   163     Node head(const Edge& e) {

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

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

   166       else

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

   168     }

   170     Node aNode(const OutEdgeIt& e) const {

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

   172     }

   173     Node aNode(const InEdgeIt& e) const {

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

   175     }

   176     Node bNode(const OutEdgeIt& e) const {

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

   178     }

   179     Node bNode(const InEdgeIt& e) const {

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

   181     }

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

   184     bool inSClass(const Node& n) const {

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

   186     }

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

   189     bool inTClass(const Node& n) const {

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

   191     }

   192   };

   195   template<typename G>

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

   197   template<typename G>

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

   200   /// \brief A bipartite graph template class

   201   ///

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

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

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

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

   206   /// reference containing the elements for the

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

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

   209   ///

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

   211   /// does not work well.

   212   template<typename Graph>

   213   class BipartiteGraph : public BipartiteGraphWrapper<Graph> {

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

   215     SFalseTTrueMap;

   216     typedef BipartiteGraphWrapper<Graph> Parent;

   217   protected:

   218     Graph gr;

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

   220     SFalseTTrueMap s_false_t_true_map;

   221   public:

   222     typedef typename Parent::Node Node;

   223     typedef typename Parent::Edge Edge;

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

   225 		       gr(), bipartite_map(gr, -1),

   226 		       s_false_t_true_map(bipartite_map) {

   227       Parent::setGraph(gr);

   228       Parent::setSFalseTTrueMap(s_false_t_true_map);

   229     }

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

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

   233     Node addNode(bool b) {

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

   235       bipartite_map.update();

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

   237       s_false_t_true_map.insert(n, b);

   238       return n;

   239     }

   241     /// A new edge is inserted.

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

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

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

   245     }

   247     void erase(const Node& n) {

   248       s_false_t_true_map.remove(n);

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

   250     }

   251     void erase(const Edge& e) {

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

   253     }

   255     void clear() {

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

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

   258     }

   259   };

   262   template<typename Graph>

   263   class stGraphWrapper;

   265 //   template<typename Graph>

   266 //   std::ostream&

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

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

   269 //     return os;

   270 //   }

   271 //   template<typename Graph>

   272 //   std::ostream&

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

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

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

   276 //     return os;

   277 //   }

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

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

   281   ///

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

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

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

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

   286   /// According to the bipartite graph concepts the bipartite

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

   288   ///

   289   /// \author Marton Makai

   290   template<typename Graph>

   291   class stGraphWrapper : public GraphWrapper<Graph> {

   292   public:

   293     class Node;

   294     friend class Node;

   295 //GN, int

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

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

   298     class NodeIt;

   299     friend class NodeIt;

   300 //GNI, int

   301     class Edge;

   302     friend class Edge;

   303 //GE, int, GN

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

   305 //invalid: (invalid, 3, invalid)

   306     class OutEdgeIt;

   307     friend class OutEdgeIt;

   308 //GO, int, GNI

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

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

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

   312     class InEdgeIt;

   313     friend class InEdgeIt;

   314 //GI, int, GNI

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

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

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

   318     class EdgeIt;

   319     friend class EdgeIt;

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

   321 //(invalid, 1, vmi)

   322 //(invalid, 2, vmi)

   323 //invalid, 3, invalid)

   324     template <typename T> class NodeMap;

   325     template <typename T> class EdgeMap;

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

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

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

   331     const Node S_NODE;

   332     const Node T_NODE;

   334     static const bool S_CLASS=false;

   335     static const bool T_CLASS=true;

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

   338 				    S_NODE(INVALID, 1),

   339 				    T_NODE(INVALID, 2) { }

   342 //    std::ostream&

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

   344 //    friend std::ostream&

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

   346 //    friend std::ostream&

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

   349     class Node : public Graph::Node {

   350     protected:

   351       friend class GraphWrapper<Graph>;

   352       friend class stGraphWrapper<Graph>;

   353       template <typename T> friend class NodeMap;

   354       friend class Edge;

   355       friend class OutEdgeIt;

   356       friend class InEdgeIt;

   357       friend class EdgeIt;

   358       int spec;

   359     public:

   360       Node() { }

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

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

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

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

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

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

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

   368       }

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

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

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

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

   373       }

   374 //      template<typename G>

   375 //      friend std::ostream&

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

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

   378       int getSpec() const { return spec; }

   379     };

   381     class NodeIt {

   382       friend class GraphWrapper<Graph>;

   383       friend class stGraphWrapper<Graph>;

   384       typename Graph::NodeIt n;

   385       int spec;

   386      public:

   387       NodeIt() { }

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

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

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

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

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

   393       }

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

   395     };

   397     class Edge : public Graph::Edge {

   398       friend class GraphWrapper<Graph>;

   399       friend class stGraphWrapper<Graph>;

   400       template <typename T> friend class EdgeMap;

   401       int spec;

   402       typename Graph::Node n;

   403     public:

   404       Edge() { }

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

   406 	   const typename Graph::Node& _n) :

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

   408       }

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

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

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

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

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

   414 		u.n==v.n);

   415       }

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

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

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

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

   420 		u.n!=v.n);

   421       }

   422 //      template<typename G>

   423 //      friend std::ostream&

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

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

   426       int getSpec() const { return spec; }

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

   428     };

   430     class OutEdgeIt {

   431       friend class GraphWrapper<Graph>;

   432       friend class stGraphWrapper<Graph>;

   433       typename Graph::OutEdgeIt e;

   434       int spec;

   435       typename Graph::ClassNodeIt n;

   436     public:

   437       OutEdgeIt() { }

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

   439 		const typename Graph::ClassNodeIt& _n) :

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

   441       }

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

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

   444 	switch (_n.spec) {

   445 	  case 0 :

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

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

   448 					  typename Graph::Node(_n));

   449 	      spec=0;

   450 	      n=INVALID;

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

   452 	    } else { //T, specko kiel van

   453 	      e=INVALID;

   454 	      spec=2;

   455 	      n=_n;

   456 	    }

   457 	    break;

   458 	  case 1:

   459 	    e=INVALID;

   460 	    spec=1;

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

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

   463 	    break;

   464 	  case 2:

   465 	    e=INVALID;

   466 	    spec=3;

   467 	    n=INVALID;

   468 	    break;

   469 	}

   470       }

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

   472     };

   474     class InEdgeIt {

   475       friend class GraphWrapper<Graph>;

   476       friend class stGraphWrapper<Graph>;

   477       typename Graph::InEdgeIt e;

   478       int spec;

   479       typename Graph::ClassNodeIt n;

   480     public:

   481       InEdgeIt() { }

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

   483 	       const typename Graph::ClassNodeIt& _n) :

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

   485       }

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

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

   488 	switch (_n.spec) {

   489 	  case 0 :

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

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

   492 					 typename Graph::Node(_n));

   493 	      spec=0;

   494 	      n=INVALID;

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

   496 	    } else { //S, specko beel van

   497 	      e=INVALID;

   498 	      spec=1;

   499 	      n=_n;

   500 	    }

   501 	    break;

   502 	  case 1:

   503 	    e=INVALID;

   504 	    spec=3;

   505 	    n=INVALID;

   506 	    break;

   507 	  case 2:

   508 	    e=INVALID;

   509 	    spec=2;

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

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

   512 	    break;

   513 	}

   514       }

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

   516     };

   518     class EdgeIt {

   519       friend class GraphWrapper<Graph>;

   520       friend class stGraphWrapper<Graph>;

   521       typename Graph::EdgeIt e;

   522       int spec;

   523       typename Graph::ClassNodeIt n;

   524     public:

   525       EdgeIt() { }

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

   527 	     const typename Graph::ClassNodeIt& _n) :

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

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

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

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

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

   533 	  spec=1;

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

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

   536 	    spec=2;

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

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

   539 	      spec=3;

   540 	    }

   541 	  }

   542 	}

   543       }

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

   545     };

   547     NodeIt& first(NodeIt& i) const {

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

   549     }

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

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

   552     }

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

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

   555     }

   556     EdgeIt& first(EdgeIt& i) const {

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

   558     }

   560     NodeIt& next(NodeIt& i) const {

   561       switch (i.spec) {

   562 	case 0:

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

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

   565 	    i.spec=1;

   566 	  }

   567 	  break;

   568 	case 1:

   569 	  i.spec=2;

   570 	  break;

   571 	case 2:

   572 	  i.spec=3;

   573 	  break;

   574       }

   575       return i;

   576     }

   577     OutEdgeIt& next(OutEdgeIt& i) const {

   578       typename Graph::Node v;

   579       switch (i.spec) {

   580 	case 0: //normal edge

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

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

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

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

   585 	      i.spec=3;

   586 	      i.n=INVALID;

   587 	    } else { //T, van kiel

   588 	      i.spec=2;

   589 	      i.n=v;

   590 	    }

   591 	  }

   592 	  break;

   593 	case 1: //s->vmi

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

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

   596 	  break;

   597 	case 2: //vmi->t

   598 	  i.spec=3;

   599 	  i.n=INVALID;

   600 	  break;

   601       }

   602       return i;

   603     }

   604     InEdgeIt& next(InEdgeIt& i) const {

   605       typename Graph::Node v;

   606       switch (i.spec) {

   607 	case 0: //normal edge

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

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

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

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

   612 	      i.spec=3;

   613 	      i.n=INVALID;

   614 	    } else { //S, van beel

   615 	      i.spec=1;

   616 	      i.n=v;

   617 	    }

   618 	  }

   619 	  break;

   620 	case 1: //s->vmi

   621 	  i.spec=3;

   622 	  i.n=INVALID;

   623 	  break;

   624 	case 2: //vmi->t

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

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

   627 	  break;

   628       }

   629       return i;

   630     }

   632     EdgeIt& next(EdgeIt& i) const {

   633       switch (i.spec) {

   634 	case 0:

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

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

   637 	    i.spec=1;

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

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

   640 	      i.spec=2;

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

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

   643 	    }

   644 	  }

   645 	  break;

   646 	case 1:

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

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

   649 	    i.spec=2;

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

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

   652 	  }

   653 	  break;

   654 	case 2:

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

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

   657 	  break;

   658       }

   659       return i;

   660     }

   662     Node tail(const Edge& e) const {

   663       switch (e.spec) {

   664       case 0:

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

   666 	break;

   667       case 1:

   668 	return S_NODE;

   669 	break;

   670       case 2:

   671       default:

   672 	return Node(e.n);

   673 	break;

   674       }

   675     }

   676     Node head(const Edge& e) const {

   677       switch (e.spec) {

   678       case 0:

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

   680 	break;

   681       case 1:

   682 	return Node(e.n);

   683 	break;

   684       case 2:

   685       default:

   686 	return T_NODE;

   687 	break;

   688       }

   689     }

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

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

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

   695     int edgeNum() const {

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

   697     }

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

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

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

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

   704     void addNode() const { }

   705     void addEdge() const { }

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

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

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

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

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

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

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

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

   718     protected:

   719       T s_value, t_value;

   720     public:

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

   722 						  s_value(),

   723 						  t_value() { }

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

   725 						      s_value(a),

   726 						      t_value(a) { }

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

   728 	switch (n.spec) {

   729 	case 0:

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

   731 	case 1:

   732 	  return s_value;

   733 	case 2:

   734 	default:

   735 	  return t_value;

   736 	}

   737       }

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

   739 	switch (n.spec) {

   740 	case 0:

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

   742 	  break;

   743 	case 1:

   744 	  s_value=t;

   745 	  break;

   746 	case 2:

   747 	default:

   748 	  t_value=t;

   749 	  break;

   750 	}

   751       }

   752     };

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

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

   756     /// stGraphWrapper<Graph>.

   757     template<typename NM> class NodeMapWrapper {

   758     public:

   759       typedef Node KeyType;

   760       typedef typename NM::ValueType ValueType;

   761     protected:

   762       NM* nm;

   763       ValueType* s_value, t_value;

   764     public:

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

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

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

   768 	switch (n.getSpec()) {

   769 	case 0:

   770 	  return (*nm)[n];

   771 	case 1:

   772 	  return *s_value;

   773 	case 2:

   774 	default:

   775 	  return *t_value;

   776 	}

   777       }

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

   779 	switch (n.getSpec()) {

   780 	case 0:

   781 	  nm->set(n, t);

   782 	  break;

   783 	case 1:

   784 	  *s_value=t;

   785 	  break;

   786 	case 2:

   787 	default:

   788 	  *t_value=t;

   789 	  break;

   790 	}

   791       }

   792     };

   794     template<typename T>

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

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

   797     protected:

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

   799     public:

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

   801 						 node_value(_G) { }

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

   803 						      node_value(_G, a) { }

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

   805 	switch (e.spec) {

   806 	case 0:

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

   808 	case 1:

   809 	  return node_value[e.n];

   810 	case 2:

   811 	default:

   812 	  return node_value[e.n];

   813 	}

   814       }

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

   816 	switch (e.spec) {

   817 	case 0:

   818 	  Parent::set(e, t);

   819 	  break;

   820 	case 1:

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

   822 	  break;

   823 	case 2:

   824 	default:

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

   826 	  break;

   827 	}

   828       }

   829     };

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

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

   833     template<typename EM, typename NM>

   834     class EdgeMapWrapper {

   835     public:

   836       typedef Edge KeyType;

   837       typedef typename EM::ValueType ValueType;

   838     protected:

   839       EM* em;

   840       NM* nm;

   841     public:

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

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

   844 	switch (e.getSpec()) {

   845 	case 0:

   846 	  return (*em)[e];

   847 	case 1:

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

   849 	case 2:

   850 	default:

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

   852 	}

   853       }

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

   855 	switch (e.getSpec()) {

   856 	case 0:

   857 	  em->set(e, t);

   858 	  break;

   859 	case 1:

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

   861 	  break;

   862 	case 2:

   863 	default:

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

   865 	  break;

   866 	}

   867       }

   868     };

   871 //  template<typename G>

   872     friend std::ostream&

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

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

   875       return os;

   876     }

   877 //  template<typename G>

   878     friend std::ostream&

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

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

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

   882       return os;

   883     }

   885   };

   887   ///@}

   889 } //namespace hugo

   892 #endif //HUGO_BIPARTITE_GRAPH_WRAPPER_H

author	marci
	Tue, 17 Aug 2004 13:05:59 +0000
changeset 763	151b5754c7c6
parent 641	bfd6c14e2975
child 768	a5e9303a5511
permissions	-rw-r--r--