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 <invalid.h>

    14 #include <iter_map.h>

    15 #include <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     typedef IterableBoolMap< typename Graph::template NodeMap<int> >

    30     SFalseTTrueMap;

    31     SFalseTTrueMap* s_false_t_true_map;

    33   public:

    34     //marci

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

    36     //static const bool S_CLASS=false;

    37     //static const bool T_CLASS=true;

    39     bool S_CLASS;

    40     bool T_CLASS;

    42     BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)

    43       : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map),

    44       S_CLASS(false), T_CLASS(true) { }

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

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

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

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

    49     class ClassNodeIt;

    50     friend class ClassNodeIt;

    51     class OutEdgeIt;

    52     friend class OutEdgeIt;

    53     class InEdgeIt;

    54     friend class InEdgeIt;

    55     class ClassNodeIt {

    56       friend class BipartiteGraphWrapper<Graph>;

    57     protected:

    58       Node n;

    59     public:

    60       ClassNodeIt() { }

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

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

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

    64       }

    65       //FIXME needed in new concept, important here

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

    67       operator Node() const { return n; }

    68     };

    69 //     class SNodeIt {

    70 //       Node n;

    71 //     public:

    72 //       SNodeIt() { }

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

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

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

    76 //       }

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

    78 //     };

    79 //     class TNodeIt {

    80 //       Node n;

    81 //     public:

    82 //       TNodeIt() { }

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

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

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

    86 //       }

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

    88 //     };

    89     class OutEdgeIt {

    90       friend class BipartiteGraphWrapper<Graph>;

    91     protected:

    92       typename Graph::OutEdgeIt e;

    93     public:

    94       OutEdgeIt() { }

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

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

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

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

    99 	else

   100 	  e=INVALID;

   101       }

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

   103     };

   104     class InEdgeIt {

   105       friend class BipartiteGraphWrapper<Graph>;

   106     protected:

   107       typename Graph::InEdgeIt e;

   108     public:

   109       InEdgeIt() { }

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

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

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

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

   114 	else

   115 	  e=INVALID;

   116       }

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

   118     };

   120     using GraphWrapper<Graph>::first;

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

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

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

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

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

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

   127     }

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

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

   130     }

   132     using GraphWrapper<Graph>::next;

   133     ClassNodeIt& next(ClassNodeIt& n) const {

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

   135     }

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

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

   138 //     }

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

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

   141 //     }

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

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

   145     Node tail(const Edge& e) {

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

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

   148       else

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

   150     }

   151     Node head(const Edge& e) {

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

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

   154       else

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

   156     }

   158     Node aNode(const OutEdgeIt& e) const {

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

   160     }

   161     Node aNode(const InEdgeIt& e) const {

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

   163     }

   164     Node bNode(const OutEdgeIt& e) const {

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

   166     }

   167     Node bNode(const InEdgeIt& e) const {

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

   169     }

   171     bool inSClass(const Node& n) const {

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

   173     }

   174     bool inTClass(const Node& n) const {

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

   176     }

   177   };

   179   template<typename Graph>

   180   class stGraphWrapper;

   182 //   template<typename Graph>

   183 //   std::ostream&

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

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

   186 //     return os;

   187 //   }

   188 //   template<typename Graph>

   189 //   std::ostream&

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

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

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

   193 //     return os;

   194 //   }

   196   /// experimentral, do not try it.

   197   /// It eats a bipartite graph, oriented from S to T.

   198   /// Such one can be made e.g. by the above wrapper.

   199   ///

   200   ///\author Marton Makai

   201   template<typename Graph>

   202   class stGraphWrapper : public GraphWrapper<Graph> {

   203   public:

   204     class Node;

   205     friend class Node;

   206 //GN, int

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

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

   209     class NodeIt;

   210     friend class NodeIt;

   211 //GNI, int

   212     class Edge;

   213     friend class Edge;

   214 //GE, int, GN

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

   216 //invalid: (invalid, 3, invalid)

   217     class OutEdgeIt;

   218     friend class OutEdgeIt;

   219 //GO, int, GNI

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

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

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

   223     class InEdgeIt;

   224     friend class InEdgeIt;

   225 //GI, int, GNI

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

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

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

   229     class EdgeIt;

   230     friend class EdgeIt;

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

   232 //(invalid, 1, vmi)

   233 //(invalid, 2, vmi)

   234 //invalid, 3, invalid)

   235     template <typename T> class NodeMap;

   236     template <typename T, typename Parent> class EdgeMap;

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

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

   241     const Node S_NODE;

   242     const Node T_NODE;

   244     static const bool S_CLASS=false;

   245     static const bool T_CLASS=true;

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

   248 				    S_NODE(INVALID, 1),

   249 				    T_NODE(INVALID, 2) { }

   252 //    std::ostream&

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

   254 //    friend std::ostream&

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

   256 //    friend std::ostream&

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

   259     class Node : public Graph::Node {

   260     protected:

   261       friend class GraphWrapper<Graph>;

   262       friend class stGraphWrapper<Graph>;

   263       template <typename T> friend class NodeMap;

   264       friend class Edge;

   265       friend class OutEdgeIt;

   266       friend class InEdgeIt;

   267       friend class EdgeIt;

   268       int spec;

   269     public:

   270       Node() { }

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

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

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

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

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

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

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

   278       }

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

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

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

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

   283       }

   284 //      template<typename G>

   285 //      friend std::ostream&

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

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

   288       int getSpec() const { return spec; }

   289     };

   291     class NodeIt {

   292       friend class GraphWrapper<Graph>;

   293       friend class stGraphWrapper<Graph>;

   294       typename Graph::NodeIt n;

   295       int spec;

   296      public:

   297       NodeIt() { }

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

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

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

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

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

   303       }

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

   305     };

   307     class Edge : public Graph::Edge {

   308       friend class GraphWrapper<Graph>;

   309       friend class stGraphWrapper<Graph>;

   310       template <typename T, typename Parent> friend class EdgeMap;

   311       int spec;

   312       typename Graph::Node n;

   313     public:

   314       Edge() { }

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

   316 	   const typename Graph::Node& _n) :

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

   318       }

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

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

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

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

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

   324 		u.n==v.n);

   325       }

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

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

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

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

   330 		u.n!=v.n);

   331       }

   332 //      template<typename G>

   333 //      friend std::ostream&

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

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

   336       int getSpec() const { return spec; }

   337     };

   339     class OutEdgeIt {

   340       friend class GraphWrapper<Graph>;

   341       friend class stGraphWrapper<Graph>;

   342       typename Graph::OutEdgeIt e;

   343       int spec;

   344       typename Graph::ClassNodeIt n;

   345     public:

   346       OutEdgeIt() { }

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

   348 		const typename Graph::ClassNodeIt& _n) :

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

   350       }

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

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

   353 	switch (_n.spec) {

   354 	  case 0 :

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

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

   357 					  typename Graph::Node(_n));

   358 	      spec=0;

   359 	      n=INVALID;

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

   361 	    } else { //T, specko kiel van

   362 	      e=INVALID;

   363 	      spec=2;

   364 	      n=_n;

   365 	    }

   366 	    break;

   367 	  case 1:

   368 	    e=INVALID;

   369 	    spec=1;

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

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

   372 	    break;

   373 	  case 2:

   374 	    e=INVALID;

   375 	    spec=3;

   376 	    n=INVALID;

   377 	    break;

   378 	}

   379       }

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

   381     };

   383     class InEdgeIt {

   384       friend class GraphWrapper<Graph>;

   385       friend class stGraphWrapper<Graph>;

   386       typename Graph::InEdgeIt e;

   387       int spec;

   388       typename Graph::ClassNodeIt n;

   389     public:

   390       InEdgeIt() { }

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

   392 	       const typename Graph::ClassNodeIt& _n) :

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

   394       }

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

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

   397 	switch (_n.spec) {

   398 	  case 0 :

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

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

   401 					 typename Graph::Node(_n));

   402 	      spec=0;

   403 	      n=INVALID;

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

   405 	    } else { //S, specko beel van

   406 	      e=INVALID;

   407 	      spec=1;

   408 	      n=_n;

   409 	    }

   410 	    break;

   411 	  case 1:

   412 	    e=INVALID;

   413 	    spec=3;

   414 	    n=INVALID;

   415 	    break;

   416 	  case 2:

   417 	    e=INVALID;

   418 	    spec=2;

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

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

   421 	    break;

   422 	}

   423       }

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

   425     };

   427     class EdgeIt {

   428       friend class GraphWrapper<Graph>;

   429       friend class stGraphWrapper<Graph>;

   430       typename Graph::EdgeIt e;

   431       int spec;

   432       typename Graph::ClassNodeIt n;

   433     public:

   434       EdgeIt() { }

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

   436 	     const typename Graph::ClassNodeIt& _n) :

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

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

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

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

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

   442 	  spec=1;

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

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

   445 	    spec=2;

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

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

   448 	      spec=3;

   449 	    }

   450 	  }

   451 	}

   452       }

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

   454     };

   456     NodeIt& first(NodeIt& i) const {

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

   458     }

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

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

   461     }

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

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

   464     }

   465     EdgeIt& first(EdgeIt& i) const {

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

   467     }

   469     NodeIt& next(NodeIt& i) const {

   470       switch (i.spec) {

   471 	case 0:

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

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

   474 	    i.spec=1;

   475 	  }

   476 	  break;

   477 	case 1:

   478 	  i.spec=2;

   479 	  break;

   480 	case 2:

   481 	  i.spec=3;

   482 	  break;

   483       }

   484       return i;

   485     }

   486     OutEdgeIt& next(OutEdgeIt& i) const {

   487       typename Graph::Node v;

   488       switch (i.spec) {

   489 	case 0: //normal edge

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

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

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

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

   494 	      i.spec=3;

   495 	      i.n=INVALID;

   496 	    } else { //T, van kiel

   497 	      i.spec=2;

   498 	      i.n=v;

   499 	    }

   500 	  }

   501 	  break;

   502 	case 1: //s->vmi

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

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

   505 	  break;

   506 	case 2: //vmi->t

   507 	  i.spec=3;

   508 	  i.n=INVALID;

   509 	  break;

   510       }

   511       return i;

   512     }

   513     InEdgeIt& next(InEdgeIt& i) const {

   514       typename Graph::Node v;

   515       switch (i.spec) {

   516 	case 0: //normal edge

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

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

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

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

   521 	      i.spec=3;

   522 	      i.n=INVALID;

   523 	    } else { //S, van beel

   524 	      i.spec=1;

   525 	      i.n=v;

   526 	    }

   527 	  }

   528 	  break;

   529 	case 1: //s->vmi

   530 	  i.spec=3;

   531 	  i.n=INVALID;

   532 	  break;

   533 	case 2: //vmi->t

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

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

   536 	  break;

   537       }

   538       return i;

   539     }

   541     EdgeIt& next(EdgeIt& i) const {

   542       switch (i.spec) {

   543 	case 0:

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

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

   546 	    i.spec=1;

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

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

   549 	      i.spec=2;

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

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

   552 	    }

   553 	  }

   554 	  break;

   555 	case 1:

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

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

   558 	    i.spec=2;

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

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

   561 	  }

   562 	  break;

   563 	case 2:

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

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

   566 	  break;

   567       }

   568       return i;

   569     }

   571     Node tail(const Edge& e) const {

   572       switch (e.spec) {

   573       case 0:

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

   575 	break;

   576       case 1:

   577 	return S_NODE;

   578 	break;

   579       case 2:

   580       default:

   581 	return Node(e.n);

   582 	break;

   583       }

   584     }

   585     Node head(const Edge& e) const {

   586       switch (e.spec) {

   587       case 0:

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

   589 	break;

   590       case 1:

   591 	return Node(e.n);

   592 	break;

   593       case 2:

   594       default:

   595 	return T_NODE;

   596 	break;

   597       }

   598     }

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

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

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

   604     int edgeNum() const {

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

   606     }

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

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

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

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

   613     void addNode() const { }

   614     void addEdge() const { }

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

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

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

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

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

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

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

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

   627       T s_value, t_value;

   628     public:

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

   630 						  s_value(),

   631 						  t_value() { }

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

   633 						      s_value(a),

   634 						      t_value(a) { }

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

   636 	switch (n.spec) {

   637 	case 0:

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

   639 	  break;

   640 	case 1:

   641 	  return s_value;

   642 	  break;

   643 	case 2:

   644 	default:

   645 	  return t_value;

   646 	  break;

   647 	}

   648       }

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

   650 	switch (n.spec) {

   651 	case 0:

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

   653 	  break;

   654 	case 1:

   655 	  s_value=t;

   656 	  break;

   657 	case 2:

   658 	default:

   659 	  t_value=t;

   660 	  break;

   661 	}

   662       }

   663     };

   665     template<typename T,

   666 	     typename Parent=

   667 	     typename GraphWrapper<Graph>::template EdgeMap<T> >

   668     class EdgeMap : public Parent {

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

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

   671     public:

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

   673 						 node_value(_G) { }

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

   675 						      node_value(_G, a) { }

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

   677 	switch (e.spec) {

   678 	case 0:

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

   680 	  break;

   681 	case 1:

   682 	  return node_value[e.n];

   683 	  break;

   684 	case 2:

   685 	default:

   686 	  return node_value[e.n];

   687 	  break;

   688 	}

   689       }

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

   691 	switch (e.spec) {

   692 	case 0:

   693 	  Parent::set(e, t);

   694 	  break;

   695 	case 1:

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

   697 	  break;

   698 	case 2:

   699 	default:

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

   701 	  break;

   702 	}

   703       }

   704     };

   706 //     template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> {

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

   708 //       typename GraphWrapper<Graph>::template NodeMap<T> node_value;

   709 //     public:

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

   711 // 						 node_value(_G) { }

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

   713 // 						      node_value(_G, a) { }

   714 //       T operator[](const Edge& e) const {

   715 // 	switch (e.spec) {

   716 // 	case 0:

   717 // 	  return Parent::operator[](e);

   718 // 	  break;

   719 // 	case 1:

   720 // 	  return node_value[e.n];

   721 // 	  break;

   722 // 	case 2:

   723 // 	default:

   724 // 	  return node_value[e.n];

   725 // 	  break;

   726 // 	}

   727 //       }

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

   729 // 	switch (e.spec) {

   730 // 	case 0:

   731 // 	  GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);

   732 // 	  break;

   733 // 	case 1:

   734 // 	  node_value.set(e.n, t);

   735 // 	  break;

   736 // 	case 2:

   737 // 	default:

   738 // 	  node_value.set(e.n, t);

   739 // 	  break;

   740 // 	}

   741 //       }

   742 //     };

   744 //  template<typename G>

   745     friend std::ostream&

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

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

   748       return os;

   749     }

   750 //  template<typename G>

   751     friend std::ostream&

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

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

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

   755       return os;

   756     }

   758   };

   760   ///@}

   762 } //namespace hugo

   765 #endif //HUGO_GRAPH_WRAPPER_H

author	marci
	Fri, 30 Apr 2004 14:02:10 +0000
changeset 496	7c463a7635d4
parent 495	6114a8ab5d27
child 497	500456d50d21
permissions	-rw-r--r--