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>()/*,

    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, G) erase(e);

   251       FOR_EACH_LOC(typename Parent::NodeIt, n, G) 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, typename Parent> 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, typename Parent> 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     };

   417     class OutEdgeIt {

   418       friend class GraphWrapper<Graph>;

   419       friend class stGraphWrapper<Graph>;

   420       typename Graph::OutEdgeIt e;

   421       int spec;

   422       typename Graph::ClassNodeIt n;

   423     public:

   424       OutEdgeIt() { }

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

   426 		const typename Graph::ClassNodeIt& _n) :

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

   428       }

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

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

   431 	switch (_n.spec) {

   432 	  case 0 :

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

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

   435 					  typename Graph::Node(_n));

   436 	      spec=0;

   437 	      n=INVALID;

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

   439 	    } else { //T, specko kiel van

   440 	      e=INVALID;

   441 	      spec=2;

   442 	      n=_n;

   443 	    }

   444 	    break;

   445 	  case 1:

   446 	    e=INVALID;

   447 	    spec=1;

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

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

   450 	    break;

   451 	  case 2:

   452 	    e=INVALID;

   453 	    spec=3;

   454 	    n=INVALID;

   455 	    break;

   456 	}

   457       }

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

   459     };

   461     class InEdgeIt {

   462       friend class GraphWrapper<Graph>;

   463       friend class stGraphWrapper<Graph>;

   464       typename Graph::InEdgeIt e;

   465       int spec;

   466       typename Graph::ClassNodeIt n;

   467     public:

   468       InEdgeIt() { }

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

   470 	       const typename Graph::ClassNodeIt& _n) :

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

   472       }

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

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

   475 	switch (_n.spec) {

   476 	  case 0 :

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

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

   479 					 typename Graph::Node(_n));

   480 	      spec=0;

   481 	      n=INVALID;

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

   483 	    } else { //S, specko beel van

   484 	      e=INVALID;

   485 	      spec=1;

   486 	      n=_n;

   487 	    }

   488 	    break;

   489 	  case 1:

   490 	    e=INVALID;

   491 	    spec=3;

   492 	    n=INVALID;

   493 	    break;

   494 	  case 2:

   495 	    e=INVALID;

   496 	    spec=2;

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

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

   499 	    break;

   500 	}

   501       }

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

   503     };

   505     class EdgeIt {

   506       friend class GraphWrapper<Graph>;

   507       friend class stGraphWrapper<Graph>;

   508       typename Graph::EdgeIt e;

   509       int spec;

   510       typename Graph::ClassNodeIt n;

   511     public:

   512       EdgeIt() { }

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

   514 	     const typename Graph::ClassNodeIt& _n) :

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

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

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

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

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

   520 	  spec=1;

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

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

   523 	    spec=2;

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

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

   526 	      spec=3;

   527 	    }

   528 	  }

   529 	}

   530       }

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

   532     };

   534     NodeIt& first(NodeIt& i) const {

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

   536     }

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

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

   539     }

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

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

   542     }

   543     EdgeIt& first(EdgeIt& i) const {

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

   545     }

   547     NodeIt& next(NodeIt& i) const {

   548       switch (i.spec) {

   549 	case 0:

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

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

   552 	    i.spec=1;

   553 	  }

   554 	  break;

   555 	case 1:

   556 	  i.spec=2;

   557 	  break;

   558 	case 2:

   559 	  i.spec=3;

   560 	  break;

   561       }

   562       return i;

   563     }

   564     OutEdgeIt& next(OutEdgeIt& i) const {

   565       typename Graph::Node v;

   566       switch (i.spec) {

   567 	case 0: //normal edge

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

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

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

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

   572 	      i.spec=3;

   573 	      i.n=INVALID;

   574 	    } else { //T, van kiel

   575 	      i.spec=2;

   576 	      i.n=v;

   577 	    }

   578 	  }

   579 	  break;

   580 	case 1: //s->vmi

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

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

   583 	  break;

   584 	case 2: //vmi->t

   585 	  i.spec=3;

   586 	  i.n=INVALID;

   587 	  break;

   588       }

   589       return i;

   590     }

   591     InEdgeIt& next(InEdgeIt& i) const {

   592       typename Graph::Node v;

   593       switch (i.spec) {

   594 	case 0: //normal edge

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

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

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

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

   599 	      i.spec=3;

   600 	      i.n=INVALID;

   601 	    } else { //S, van beel

   602 	      i.spec=1;

   603 	      i.n=v;

   604 	    }

   605 	  }

   606 	  break;

   607 	case 1: //s->vmi

   608 	  i.spec=3;

   609 	  i.n=INVALID;

   610 	  break;

   611 	case 2: //vmi->t

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

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

   614 	  break;

   615       }

   616       return i;

   617     }

   619     EdgeIt& next(EdgeIt& i) const {

   620       switch (i.spec) {

   621 	case 0:

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

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

   624 	    i.spec=1;

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

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

   627 	      i.spec=2;

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

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

   630 	    }

   631 	  }

   632 	  break;

   633 	case 1:

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

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

   636 	    i.spec=2;

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

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

   639 	  }

   640 	  break;

   641 	case 2:

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

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

   644 	  break;

   645       }

   646       return i;

   647     }

   649     Node tail(const Edge& e) const {

   650       switch (e.spec) {

   651       case 0:

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

   653 	break;

   654       case 1:

   655 	return S_NODE;

   656 	break;

   657       case 2:

   658       default:

   659 	return Node(e.n);

   660 	break;

   661       }

   662     }

   663     Node head(const Edge& e) const {

   664       switch (e.spec) {

   665       case 0:

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

   667 	break;

   668       case 1:

   669 	return Node(e.n);

   670 	break;

   671       case 2:

   672       default:

   673 	return T_NODE;

   674 	break;

   675       }

   676     }

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

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

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

   682     int edgeNum() const {

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

   684     }

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

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

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

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

   691     void addNode() const { }

   692     void addEdge() const { }

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

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

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

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

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

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

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

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

   705       T s_value, t_value;

   706     public:

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

   708 						  s_value(),

   709 						  t_value() { }

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

   711 						      s_value(a),

   712 						      t_value(a) { }

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

   714 	switch (n.spec) {

   715 	case 0:

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

   717 	  break;

   718 	case 1:

   719 	  return s_value;

   720 	  break;

   721 	case 2:

   722 	default:

   723 	  return t_value;

   724 	  break;

   725 	}

   726       }

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

   728 	switch (n.spec) {

   729 	case 0:

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

   731 	  break;

   732 	case 1:

   733 	  s_value=t;

   734 	  break;

   735 	case 2:

   736 	default:

   737 	  t_value=t;

   738 	  break;

   739 	}

   740       }

   741     };

   743     template<typename T,

   744 	     typename Parent=

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

   746     class EdgeMap : public Parent {

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

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

   749     public:

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

   751 						 node_value(_G) { }

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

   753 						      node_value(_G, a) { }

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

   755 	switch (e.spec) {

   756 	case 0:

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

   758 	  break;

   759 	case 1:

   760 	  return node_value[e.n];

   761 	  break;

   762 	case 2:

   763 	default:

   764 	  return node_value[e.n];

   765 	  break;

   766 	}

   767       }

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

   769 	switch (e.spec) {

   770 	case 0:

   771 	  Parent::set(e, t);

   772 	  break;

   773 	case 1:

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

   775 	  break;

   776 	case 2:

   777 	default:

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

   779 	  break;

   780 	}

   781       }

   782     };

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

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

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

   797 // 	case 1:

   798 // 	  return node_value[e.n];

   799 // 	  break;

   800 // 	case 2:

   801 // 	default:

   802 // 	  return node_value[e.n];

   803 // 	  break;

   804 // 	}

   805 //       }

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

   807 // 	switch (e.spec) {

   808 // 	case 0:

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

   810 // 	  break;

   811 // 	case 1:

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

   813 // 	  break;

   814 // 	case 2:

   815 // 	default:

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

   817 // 	  break;

   818 // 	}

   819 //       }

   820 //     };

   822 //  template<typename G>

   823     friend std::ostream&

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

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

   826       return os;

   827     }

   828 //  template<typename G>

   829     friend std::ostream&

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

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

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

   833       return os;

   834     }

   836   };

   838   ///@}

   840 } //namespace hugo

   843 #endif //HUGO_GRAPH_WRAPPER_H

author	athos
	Mon, 03 May 2004 09:00:09 +0000
changeset 505	8589c0658839
parent 501	20e4941a354a
child 510	72143568cadc
permissions	-rw-r--r--