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   protected:

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

    31     SFalseTTrueMap;

    32     SFalseTTrueMap* s_false_t_true_map;

    34     BipartiteGraphWrapper() : GraphWrapper<Graph>(0) { }

    35     void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) {

    36       s_false_t_true_map=_s_false_t_true_map;

    37     }

    39   public:

    40     //marci

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

    42     //static const bool S_CLASS=false;

    43     //static const bool T_CLASS=true;

    45     bool S_CLASS;

    46     bool T_CLASS;

    48     BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)

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

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

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

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

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

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

    55     class ClassNodeIt;

    56     friend class ClassNodeIt;

    57     class OutEdgeIt;

    58     friend class OutEdgeIt;

    59     class InEdgeIt;

    60     friend class InEdgeIt;

    61     class ClassNodeIt {

    62       friend class BipartiteGraphWrapper<Graph>;

    63     protected:

    64       Node n;

    65     public:

    66       ClassNodeIt() { }

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

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

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

    70       }

    71       //FIXME needed in new concept, important here

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

    73       operator Node() const { return n; }

    74     };

    75 //     class SNodeIt {

    76 //       Node n;

    77 //     public:

    78 //       SNodeIt() { }

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

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

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

    82 //       }

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

    84 //     };

    85 //     class TNodeIt {

    86 //       Node n;

    87 //     public:

    88 //       TNodeIt() { }

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

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

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

    92 //       }

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

    94 //     };

    95     class OutEdgeIt {

    96       friend class BipartiteGraphWrapper<Graph>;

    97     protected:

    98       typename Graph::OutEdgeIt e;

    99     public:

   100       OutEdgeIt() { }

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

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

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

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

   105 	else

   106 	  e=INVALID;

   107       }

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

   109     };

   110     class InEdgeIt {

   111       friend class BipartiteGraphWrapper<Graph>;

   112     protected:

   113       typename Graph::InEdgeIt e;

   114     public:

   115       InEdgeIt() { }

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

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

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

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

   120 	else

   121 	  e=INVALID;

   122       }

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

   124     };

   126     using GraphWrapper<Graph>::first;

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

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

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

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

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

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

   133     }

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

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

   136     }

   138     using GraphWrapper<Graph>::next;

   139     ClassNodeIt& next(ClassNodeIt& n) const {

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

   141     }

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

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

   144 //     }

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

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

   147 //     }

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

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

   151     Node tail(const Edge& e) {

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

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

   154       else

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

   156     }

   157     Node head(const Edge& e) {

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

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

   160       else

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

   162     }

   164     Node aNode(const OutEdgeIt& e) const {

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

   166     }

   167     Node aNode(const InEdgeIt& e) const {

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

   169     }

   170     Node bNode(const OutEdgeIt& e) const {

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

   172     }

   173     Node bNode(const InEdgeIt& e) const {

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

   175     }

   177     bool inSClass(const Node& n) const {

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

   179     }

   180     bool inTClass(const Node& n) const {

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

   182     }

   183   };

   185   ///\bug Do not use this while the bipartitemap augmentation

   186   /// does not work well.

   187   template<typename Graph>

   188   class BipartiteGraph : public BipartiteGraphWrapper<Graph> {

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

   190     SFalseTTrueMap;

   191     typedef BipartiteGraphWrapper<Graph> Parent;

   192   protected:

   193     Graph gr;

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

   195     SFalseTTrueMap s_false_t_true_map;

   196   public:

   197     typedef typename Parent::Node Node;

   198     typedef typename Parent::Edge Edge;

   199     BipartiteGraph() : BipartiteGraphWrapper<Graph>(0),

   200 		       gr(), bipartite_map(gr),

   201 		       s_false_t_true_map(bipartite_map) {

   202       Parent::setGraph(gr);

   203       Parent::setSFalseTTrueMap(bipartite_map);

   204     }

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

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

   208     Node addNode(bool b) {

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

   210       bipartite_map.update();

   211       s_false_t_true_map.insert(n, b);

   212       return n;

   213     }

   215     /// A new edge is inserted.

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

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

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

   219     }

   221     void erase(const Node& n) {

   222       s_false_t_true_map.remove(n);

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

   224     }

   225     void erase(const Edge& e) {

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

   227     }

   229     void clear() {

   230       FOR_EACH_LOC(typename Parent::EdgeIt, e, G) erase(e);

   231       FOR_EACH_LOC(typename Parent::NodeIt, n, G) erase(n);

   232     }

   233   };

   236   template<typename Graph>

   237   class stGraphWrapper;

   239 //   template<typename Graph>

   240 //   std::ostream&

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

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

   243 //     return os;

   244 //   }

   245 //   template<typename Graph>

   246 //   std::ostream&

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

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

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

   250 //     return os;

   251 //   }

   253   /// experimentral, do not try it.

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

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

   256   ///

   257   ///\author Marton Makai

   258   template<typename Graph>

   259   class stGraphWrapper : public GraphWrapper<Graph> {

   260   public:

   261     class Node;

   262     friend class Node;

   263 //GN, int

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

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

   266     class NodeIt;

   267     friend class NodeIt;

   268 //GNI, int

   269     class Edge;

   270     friend class Edge;

   271 //GE, int, GN

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

   273 //invalid: (invalid, 3, invalid)

   274     class OutEdgeIt;

   275     friend class OutEdgeIt;

   276 //GO, int, GNI

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

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

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

   280     class InEdgeIt;

   281     friend class InEdgeIt;

   282 //GI, int, GNI

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

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

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

   286     class EdgeIt;

   287     friend class EdgeIt;

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

   289 //(invalid, 1, vmi)

   290 //(invalid, 2, vmi)

   291 //invalid, 3, invalid)

   292     template <typename T> class NodeMap;

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

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

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

   298     const Node S_NODE;

   299     const Node T_NODE;

   301     static const bool S_CLASS=false;

   302     static const bool T_CLASS=true;

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

   305 				    S_NODE(INVALID, 1),

   306 				    T_NODE(INVALID, 2) { }

   309 //    std::ostream&

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

   311 //    friend std::ostream&

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

   313 //    friend std::ostream&

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

   316     class Node : public Graph::Node {

   317     protected:

   318       friend class GraphWrapper<Graph>;

   319       friend class stGraphWrapper<Graph>;

   320       template <typename T> friend class NodeMap;

   321       friend class Edge;

   322       friend class OutEdgeIt;

   323       friend class InEdgeIt;

   324       friend class EdgeIt;

   325       int spec;

   326     public:

   327       Node() { }

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

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

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

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

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

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

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

   335       }

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

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

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

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

   340       }

   341 //      template<typename G>

   342 //      friend std::ostream&

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

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

   345       int getSpec() const { return spec; }

   346     };

   348     class NodeIt {

   349       friend class GraphWrapper<Graph>;

   350       friend class stGraphWrapper<Graph>;

   351       typename Graph::NodeIt n;

   352       int spec;

   353      public:

   354       NodeIt() { }

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

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

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

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

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

   360       }

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

   362     };

   364     class Edge : public Graph::Edge {

   365       friend class GraphWrapper<Graph>;

   366       friend class stGraphWrapper<Graph>;

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

   368       int spec;

   369       typename Graph::Node n;

   370     public:

   371       Edge() { }

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

   373 	   const typename Graph::Node& _n) :

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

   375       }

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

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

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

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

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

   381 		u.n==v.n);

   382       }

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

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

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

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

   387 		u.n!=v.n);

   388       }

   389 //      template<typename G>

   390 //      friend std::ostream&

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

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

   393       int getSpec() const { return spec; }

   394     };

   396     class OutEdgeIt {

   397       friend class GraphWrapper<Graph>;

   398       friend class stGraphWrapper<Graph>;

   399       typename Graph::OutEdgeIt e;

   400       int spec;

   401       typename Graph::ClassNodeIt n;

   402     public:

   403       OutEdgeIt() { }

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

   405 		const typename Graph::ClassNodeIt& _n) :

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

   407       }

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

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

   410 	switch (_n.spec) {

   411 	  case 0 :

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

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

   414 					  typename Graph::Node(_n));

   415 	      spec=0;

   416 	      n=INVALID;

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

   418 	    } else { //T, specko kiel van

   419 	      e=INVALID;

   420 	      spec=2;

   421 	      n=_n;

   422 	    }

   423 	    break;

   424 	  case 1:

   425 	    e=INVALID;

   426 	    spec=1;

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

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

   429 	    break;

   430 	  case 2:

   431 	    e=INVALID;

   432 	    spec=3;

   433 	    n=INVALID;

   434 	    break;

   435 	}

   436       }

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

   438     };

   440     class InEdgeIt {

   441       friend class GraphWrapper<Graph>;

   442       friend class stGraphWrapper<Graph>;

   443       typename Graph::InEdgeIt e;

   444       int spec;

   445       typename Graph::ClassNodeIt n;

   446     public:

   447       InEdgeIt() { }

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

   449 	       const typename Graph::ClassNodeIt& _n) :

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

   451       }

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

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

   454 	switch (_n.spec) {

   455 	  case 0 :

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

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

   458 					 typename Graph::Node(_n));

   459 	      spec=0;

   460 	      n=INVALID;

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

   462 	    } else { //S, specko beel van

   463 	      e=INVALID;

   464 	      spec=1;

   465 	      n=_n;

   466 	    }

   467 	    break;

   468 	  case 1:

   469 	    e=INVALID;

   470 	    spec=3;

   471 	    n=INVALID;

   472 	    break;

   473 	  case 2:

   474 	    e=INVALID;

   475 	    spec=2;

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

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

   478 	    break;

   479 	}

   480       }

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

   482     };

   484     class EdgeIt {

   485       friend class GraphWrapper<Graph>;

   486       friend class stGraphWrapper<Graph>;

   487       typename Graph::EdgeIt e;

   488       int spec;

   489       typename Graph::ClassNodeIt n;

   490     public:

   491       EdgeIt() { }

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

   493 	     const typename Graph::ClassNodeIt& _n) :

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

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

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

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

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

   499 	  spec=1;

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

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

   502 	    spec=2;

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

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

   505 	      spec=3;

   506 	    }

   507 	  }

   508 	}

   509       }

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

   511     };

   513     NodeIt& first(NodeIt& i) const {

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

   515     }

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

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

   518     }

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

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

   521     }

   522     EdgeIt& first(EdgeIt& i) const {

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

   524     }

   526     NodeIt& next(NodeIt& i) const {

   527       switch (i.spec) {

   528 	case 0:

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

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

   531 	    i.spec=1;

   532 	  }

   533 	  break;

   534 	case 1:

   535 	  i.spec=2;

   536 	  break;

   537 	case 2:

   538 	  i.spec=3;

   539 	  break;

   540       }

   541       return i;

   542     }

   543     OutEdgeIt& next(OutEdgeIt& i) const {

   544       typename Graph::Node v;

   545       switch (i.spec) {

   546 	case 0: //normal edge

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

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

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

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

   551 	      i.spec=3;

   552 	      i.n=INVALID;

   553 	    } else { //T, van kiel

   554 	      i.spec=2;

   555 	      i.n=v;

   556 	    }

   557 	  }

   558 	  break;

   559 	case 1: //s->vmi

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

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

   562 	  break;

   563 	case 2: //vmi->t

   564 	  i.spec=3;

   565 	  i.n=INVALID;

   566 	  break;

   567       }

   568       return i;

   569     }

   570     InEdgeIt& next(InEdgeIt& i) const {

   571       typename Graph::Node v;

   572       switch (i.spec) {

   573 	case 0: //normal edge

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

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

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

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

   578 	      i.spec=3;

   579 	      i.n=INVALID;

   580 	    } else { //S, van beel

   581 	      i.spec=1;

   582 	      i.n=v;

   583 	    }

   584 	  }

   585 	  break;

   586 	case 1: //s->vmi

   587 	  i.spec=3;

   588 	  i.n=INVALID;

   589 	  break;

   590 	case 2: //vmi->t

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

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

   593 	  break;

   594       }

   595       return i;

   596     }

   598     EdgeIt& next(EdgeIt& i) const {

   599       switch (i.spec) {

   600 	case 0:

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

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

   603 	    i.spec=1;

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

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

   606 	      i.spec=2;

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

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

   609 	    }

   610 	  }

   611 	  break;

   612 	case 1:

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

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

   615 	    i.spec=2;

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

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

   618 	  }

   619 	  break;

   620 	case 2:

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

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

   623 	  break;

   624       }

   625       return i;

   626     }

   628     Node tail(const Edge& e) const {

   629       switch (e.spec) {

   630       case 0:

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

   632 	break;

   633       case 1:

   634 	return S_NODE;

   635 	break;

   636       case 2:

   637       default:

   638 	return Node(e.n);

   639 	break;

   640       }

   641     }

   642     Node head(const Edge& e) const {

   643       switch (e.spec) {

   644       case 0:

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

   646 	break;

   647       case 1:

   648 	return Node(e.n);

   649 	break;

   650       case 2:

   651       default:

   652 	return T_NODE;

   653 	break;

   654       }

   655     }

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

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

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

   661     int edgeNum() const {

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

   663     }

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

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

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

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

   670     void addNode() const { }

   671     void addEdge() const { }

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

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

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

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

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

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

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

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

   684       T s_value, t_value;

   685     public:

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

   687 						  s_value(),

   688 						  t_value() { }

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

   690 						      s_value(a),

   691 						      t_value(a) { }

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

   693 	switch (n.spec) {

   694 	case 0:

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

   696 	  break;

   697 	case 1:

   698 	  return s_value;

   699 	  break;

   700 	case 2:

   701 	default:

   702 	  return t_value;

   703 	  break;

   704 	}

   705       }

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

   707 	switch (n.spec) {

   708 	case 0:

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

   710 	  break;

   711 	case 1:

   712 	  s_value=t;

   713 	  break;

   714 	case 2:

   715 	default:

   716 	  t_value=t;

   717 	  break;

   718 	}

   719       }

   720     };

   722     template<typename T,

   723 	     typename Parent=

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

   725     class EdgeMap : public Parent {

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

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

   728     public:

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

   730 						 node_value(_G) { }

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

   732 						      node_value(_G, a) { }

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

   734 	switch (e.spec) {

   735 	case 0:

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

   737 	  break;

   738 	case 1:

   739 	  return node_value[e.n];

   740 	  break;

   741 	case 2:

   742 	default:

   743 	  return node_value[e.n];

   744 	  break;

   745 	}

   746       }

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

   748 	switch (e.spec) {

   749 	case 0:

   750 	  Parent::set(e, t);

   751 	  break;

   752 	case 1:

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

   754 	  break;

   755 	case 2:

   756 	default:

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

   758 	  break;

   759 	}

   760       }

   761     };

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

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

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

   766 //     public:

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

   768 // 						 node_value(_G) { }

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

   770 // 						      node_value(_G, a) { }

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

   772 // 	switch (e.spec) {

   773 // 	case 0:

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

   775 // 	  break;

   776 // 	case 1:

   777 // 	  return node_value[e.n];

   778 // 	  break;

   779 // 	case 2:

   780 // 	default:

   781 // 	  return node_value[e.n];

   782 // 	  break;

   783 // 	}

   784 //       }

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

   786 // 	switch (e.spec) {

   787 // 	case 0:

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

   789 // 	  break;

   790 // 	case 1:

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

   792 // 	  break;

   793 // 	case 2:

   794 // 	default:

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

   796 // 	  break;

   797 // 	}

   798 //       }

   799 //     };

   801 //  template<typename G>

   802     friend std::ostream&

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

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

   805       return os;

   806     }

   807 //  template<typename G>

   808     friend std::ostream&

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

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

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

   812       return os;

   813     }

   815   };

   817   ///@}

   819 } //namespace hugo

   822 #endif //HUGO_GRAPH_WRAPPER_H

author	marci
	Fri, 30 Apr 2004 16:46:19 +0000
changeset 498	eb8bfa683d92
parent 497	500456d50d21
child 499	767f3da8ce0e
permissions	-rw-r--r--