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   /// 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;

    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     }

    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;

    46     //bool S_CLASS;

    47     //bool T_CLASS;

    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     };

   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     }

   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; }

   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     }

   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     }

   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   };

   188   template<typename G>

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

   190   template<typename G>

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

   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     }

   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     }

   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     }

   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     }

   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   };

   256   template<typename Graph>

   257   class stGraphWrapper;

   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 //   }

   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;

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

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

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

   319     const Node S_NODE;

   320     const Node T_NODE;

   322     static const bool S_CLASS=false;

   323     static const bool T_CLASS=true;

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

   326 				    S_NODE(INVALID, 1),

   327 				    T_NODE(INVALID, 2) { }

   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);

   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     };

   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     };

   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     };

   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     };

   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     };

   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     };

   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     }

   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     }

   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     }

   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     }

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

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

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

   683     int edgeNum() const {

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

   685     }

   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); }

   692     void addNode() const { }

   693     void addEdge() const { }

   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)); }

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

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

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

   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     };

   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     };

   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     };

   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     };

   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     }

   873   };

   875   ///@}

   877 } //namespace hugo

   880 #endif //HUGO_BIPARTITE_GRAPH_WRAPPER_H

author	alpar
	Sun, 09 May 2004 16:21:56 +0000
changeset 590	5c1465127b79
parent 557	9c0ce0a1f000
child 641	bfd6c14e2975
permissions	-rw-r--r--