lemon-0.x: src/work/marci/bipartite_graph

     1 // -*- c++ -*-

     2 #ifndef HUGO_BIPARTITE_GRAPH_WRAPPER_H

     3 #define HUGO_BIPARTITE_GRAPH_WRAPPER_H

     5 ///\ingroup gwrappers

     6 ///\file

     7 ///\brief Several graph wrappers.

     8 ///

     9 ///This file contains several useful graph wrapper functions.

    10 ///

    11 ///\author Marton Makai

    13 #include <hugo/invalid.h>

    14 #include <iter_map.h>

    15 #include <hugo/graph_wrapper.h>

    16 #include <for_each_macros.h>

    18 namespace hugo {

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

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

    22   ///

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

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

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

    26   /// reference containing the elements for the

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

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

    29   ///

    30   /// \author Marton Makai

    31   template<typename Graph>

    32   class BipartiteGraphWrapper : public GraphWrapper<Graph> {

    33   public:

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

    35     SFalseTTrueMap;

    36   protected:

    37     SFalseTTrueMap* s_false_t_true_map;

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

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

    41     void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) {

    42       s_false_t_true_map=&_s_false_t_true_map;

    43     }

    45   public:

    46     //marci

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

    48     static const bool S_CLASS;

    49     static const bool T_CLASS;

    51     /// This method is to reach the iterable maps of the bipartite graph or

    52     /// bipartite graph wrapper.

    53     const SFalseTTrueMap& sFalseTTrueMap() const {

    54       return *s_false_t_true_map;

    55     }

    57     //bool S_CLASS;

    58     //bool T_CLASS;

    60     BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)

    61       : GraphWrapper<Graph>(_graph),

    62 	s_false_t_true_map(&_s_false_t_true_map)/*,

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

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

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

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

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

    68     class ClassNodeIt;

    69     friend class ClassNodeIt;

    70     class OutEdgeIt;

    71     friend class OutEdgeIt;

    72     class InEdgeIt;

    73     friend class InEdgeIt;

    74     class ClassNodeIt {

    75       friend class BipartiteGraphWrapper<Graph>;

    76     protected:

    77       Node n;

    78     public:

    79       ClassNodeIt() { }

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

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

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

    83       }

    84       //FIXME needed in new concept, important here

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

    86       operator Node() const { return n; }

    87     };

    88 //     class SNodeIt {

    89 //       Node n;

    90 //     public:

    91 //       SNodeIt() { }

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

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

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

    95 //       }

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

    97 //     };

    98 //     class TNodeIt {

    99 //       Node n;

   100 //     public:

   101 //       TNodeIt() { }

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

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

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

   105 //       }

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

   107 //     };

   108     class OutEdgeIt {

   109       friend class BipartiteGraphWrapper<Graph>;

   110     protected:

   111       typename Graph::OutEdgeIt e;

   112     public:

   113       OutEdgeIt() { }

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

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

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

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

   118 	else

   119 	  e=INVALID;

   120       }

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

   122     };

   123     class InEdgeIt {

   124       friend class BipartiteGraphWrapper<Graph>;

   125     protected:

   126       typename Graph::InEdgeIt e;

   127     public:

   128       InEdgeIt() { }

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

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

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

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

   133 	else

   134 	  e=INVALID;

   135       }

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

   137     };

   139     using GraphWrapper<Graph>::first;

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

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

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

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

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

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

   146     }

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

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

   149     }

   151     using GraphWrapper<Graph>::next;

   152     ClassNodeIt& next(ClassNodeIt& n) const {

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

   154     }

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

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

   157 //     }

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

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

   160 //     }

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

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

   164     Node tail(const Edge& e) {

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

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

   167       else

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

   169     }

   170     Node head(const Edge& e) {

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

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

   173       else

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

   175     }

   177     Node aNode(const OutEdgeIt& e) const {

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

   179     }

   180     Node aNode(const InEdgeIt& e) const {

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

   182     }

   183     Node bNode(const OutEdgeIt& e) const {

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

   185     }

   186     Node bNode(const InEdgeIt& e) const {

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

   188     }

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

   191     bool inSClass(const Node& n) const {

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

   193     }

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

   196     bool inTClass(const Node& n) const {

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

   198     }

   199   };

   202   template<typename G>

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

   204   template<typename G>

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

   207   /// \brief A bipartite graph template class

   208   ///

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

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

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

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

   213   /// reference containing the elements for the

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

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

   216   ///

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

   218   /// does not work well.

   219   template<typename Graph>

   220   class BipartiteGraph : public BipartiteGraphWrapper<Graph> {

   221 //     typedef IterableBoolMap< typename Graph::template NodeMap<int> >

   222 //     SFalseTTrueMap;

   223     typedef BipartiteGraphWrapper<Graph> Parent;

   224   protected:

   225     Graph gr;

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

   227     typename Parent::SFalseTTrueMap s_false_t_true_map;

   228   public:

   229     typedef typename Parent::Node Node;

   230     typedef typename Parent::Edge Edge;

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

   232 		       gr(), bipartite_map(gr, -1),

   233 		       s_false_t_true_map(bipartite_map) {

   234       Parent::setGraph(gr);

   235       Parent::setSFalseTTrueMap(s_false_t_true_map);

   236     }

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

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

   240     Node addNode(bool b) {

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

   242       bipartite_map.update();

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

   244       s_false_t_true_map.insert(n, b);

   245       return n;

   246     }

   248     /// A new edge is inserted.

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

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

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

   252     }

   254     void erase(const Node& n) {

   255       s_false_t_true_map.remove(n);

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

   257     }

   258     void erase(const Edge& e) {

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

   260     }

   262     void clear() {

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

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

   265     }

   266   };

   268   template<typename Graph, typename sIterableMap, typename tIterableMap>

   269   class stGraphWrapper;

   271   /// Easier stuff for bipartite graphs.

   272   template<typename Graph>

   273   class stBipartiteGraphWrapper : public

   274   stGraphWrapper<Graph, typename Graph::SFalseTTrueMap,

   275 		 typename Graph::SFalseTTrueMap> {

   276   public:

   277     typedef stGraphWrapper<Graph, typename Graph::SFalseTTrueMap,

   278 			   typename Graph::SFalseTTrueMap> Parent;

   279     stBipartiteGraphWrapper(Graph& _graph) :

   280       Parent(_graph, _graph.sFalseTTrueMap(), _graph.sFalseTTrueMap()) { }

   281   };

   283 //   template<typename Graph>

   284 //   std::ostream&

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

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

   287 //     return os;

   288 //   }

   289 //   template<typename Graph>

   290 //   std::ostream&

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

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

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

   294 //     return os;

   295 //   }

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

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

   299   ///

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

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

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

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

   304   /// According to the bipartite graph concepts the bipartite

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

   306   ///

   307   /// \author Marton Makai

   308   template<typename Graph, typename sIterableMap, typename tIterableMap>

   309   class stGraphWrapper : public GraphWrapper<Graph> {

   310   protected:

   311     const sIterableMap* s_iterable_map;

   312     const tIterableMap* t_iterable_map;

   313   public:

   314     class Node;

   315     friend class Node;

   316 //GN, int

   317 //0 normalis, 1 s, 2 t, ez az iteralasi sorrend,

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

   319     class NodeIt;

   320     friend class NodeIt;

   321 //GNI, int

   322     class Edge;

   323     friend class Edge;

   324 //GE, int, GN

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

   326 //invalid: (invalid, 3, invalid)

   327     class OutEdgeIt;

   328     friend class OutEdgeIt;

   329 //GO, int, GNI

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

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

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

   333     class InEdgeIt;

   334     friend class InEdgeIt;

   335 //GI, int, GNI

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

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

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

   339     class EdgeIt;

   340     friend class EdgeIt;

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

   342 //(invalid, 1, vmi)

   343 //(invalid, 2, vmi)

   344 //invalid, 3, invalid)

   345     template <typename T> class NodeMap;

   346     template <typename T> class EdgeMap;

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

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

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

   352     const Node S_NODE;

   353     const Node T_NODE;

   355     static const bool S_CLASS=false;

   356     static const bool T_CLASS=true;

   358     // \bug not too nice constructor.

   359     stGraphWrapper(Graph& _graph,

   360 		   const sIterableMap& _s_iterable_map,

   361 		   const tIterableMap& _t_iterable_map) :

   362       GraphWrapper<Graph>(_graph),

   363       s_iterable_map(&_s_iterable_map),

   364       t_iterable_map(&_t_iterable_map),

   365       S_NODE(INVALID, 1),

   366       T_NODE(INVALID, 2) { }

   369 //    std::ostream&

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

   371 //    friend std::ostream&

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

   373 //    friend std::ostream&

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

   376     class Node : public Graph::Node {

   377     protected:

   378       friend class GraphWrapper<Graph>;

   379       friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;

   380       template <typename T> friend class NodeMap;

   381       friend class Edge;

   382       friend class OutEdgeIt;

   383       friend class InEdgeIt;

   384       friend class EdgeIt;

   385       int spec;

   386     public:

   387       Node() { }

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

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

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

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

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

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

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

   395       }

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

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

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

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

   400       }

   401 //      template<typename G>

   402 //      friend std::ostream&

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

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

   405       int getSpec() const { return spec; }

   406     };

   408     class NodeIt {

   409       friend class GraphWrapper<Graph>;

   410       friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;

   411       typename Graph::NodeIt n;

   412       int spec;

   413      public:

   414       NodeIt() { }

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

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

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

   418       NodeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G)

   419 	: n(*(_G.graph)), spec(0) {

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

   421       }

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

   423     };

   425     class Edge : public Graph::Edge {

   426       friend class GraphWrapper<Graph>;

   427       friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;

   428       template <typename T> friend class EdgeMap;

   429       int spec;

   430       typename Graph::Node n;

   431     public:

   432       Edge() { }

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

   434 	   const typename Graph::Node& _n) :

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

   436       }

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

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

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

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

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

   442 		u.n==v.n);

   443       }

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

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

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

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

   448 		u.n!=v.n);

   449       }

   450 //      template<typename G>

   451 //      friend std::ostream&

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

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

   454       int getSpec() const { return spec; }

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

   456     };

   458     class OutEdgeIt {

   459       friend class GraphWrapper<Graph>;

   460       friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;

   461       typename Graph::OutEdgeIt e;

   462       int spec;

   463       typename Graph::ClassNodeIt n;

   464     public:

   465       OutEdgeIt() { }

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

   467 		const typename Graph::ClassNodeIt& _n) :

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

   469       }

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

   471       OutEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G,

   472 		const Node& _n) {

   473 	switch (_n.spec) {

   474 	  case 0 :

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

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

   477 					  typename Graph::Node(_n));

   478 	      spec=0;

   479 	      n=INVALID;

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

   481 	    } else { //T, specko kiel van

   482 	      e=INVALID;

   483 	      spec=2;

   484 	      n=_n;

   485 	    }

   486 	    break;

   487 	  case 1:

   488 	    e=INVALID;

   489 	    spec=1;

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

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

   492 	    break;

   493 	  case 2:

   494 	    e=INVALID;

   495 	    spec=3;

   496 	    n=INVALID;

   497 	    break;

   498 	}

   499       }

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

   501     };

   503     class InEdgeIt {

   504       friend class GraphWrapper<Graph>;

   505       friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;

   506       typename Graph::InEdgeIt e;

   507       int spec;

   508       typename Graph::ClassNodeIt n;

   509     public:

   510       InEdgeIt() { }

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

   512 	       const typename Graph::ClassNodeIt& _n) :

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

   514       }

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

   516       InEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G,

   517 	       const Node& _n) {

   518 	switch (_n.spec) {

   519 	  case 0 :

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

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

   522 					 typename Graph::Node(_n));

   523 	      spec=0;

   524 	      n=INVALID;

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

   526 	    } else { //S, specko beel van

   527 	      e=INVALID;

   528 	      spec=1;

   529 	      n=_n;

   530 	    }

   531 	    break;

   532 	  case 1:

   533 	    e=INVALID;

   534 	    spec=3;

   535 	    n=INVALID;

   536 	    break;

   537 	  case 2:

   538 	    e=INVALID;

   539 	    spec=2;

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

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

   542 	    break;

   543 	}

   544       }

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

   546     };

   548     class EdgeIt {

   549       friend class GraphWrapper<Graph>;

   550       friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;

   551       typename Graph::EdgeIt e;

   552       int spec;

   553       typename Graph::ClassNodeIt n;

   554     public:

   555       EdgeIt() { }

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

   557 	     const typename Graph::ClassNodeIt& _n) :

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

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

   560       EdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) :

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

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

   563 	  spec=1;

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

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

   566 	    spec=2;

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

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

   569 	      spec=3;

   570 	    }

   571 	  }

   572 	}

   573       }

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

   575     };

   577     NodeIt& first(NodeIt& i) const {

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

   579     }

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

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

   582     }

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

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

   585     }

   586     EdgeIt& first(EdgeIt& i) const {

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

   588     }

   590     NodeIt& next(NodeIt& i) const {

   591       switch (i.spec) {

   592 	case 0:

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

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

   595 	    i.spec=1;

   596 	  }

   597 	  break;

   598 	case 1:

   599 	  i.spec=2;

   600 	  break;

   601 	case 2:

   602 	  i.spec=3;

   603 	  break;

   604       }

   605       return i;

   606     }

   607     OutEdgeIt& next(OutEdgeIt& i) const {

   608       typename Graph::Node v;

   609       switch (i.spec) {

   610 	case 0: //normal edge

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

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

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

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

   615 	      i.spec=3;

   616 	      i.n=INVALID;

   617 	    } else { //T, van kiel

   618 	      i.spec=2;

   619 	      i.n=v;

   620 	    }

   621 	  }

   622 	  break;

   623 	case 1: //s->vmi

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

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

   626 	  break;

   627 	case 2: //vmi->t

   628 	  i.spec=3;

   629 	  i.n=INVALID;

   630 	  break;

   631       }

   632       return i;

   633     }

   634     InEdgeIt& next(InEdgeIt& i) const {

   635       typename Graph::Node v;

   636       switch (i.spec) {

   637 	case 0: //normal edge

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

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

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

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

   642 	      i.spec=3;

   643 	      i.n=INVALID;

   644 	    } else { //S, van beel

   645 	      i.spec=1;

   646 	      i.n=v;

   647 	    }

   648 	  }

   649 	  break;

   650 	case 1: //s->vmi

   651 	  i.spec=3;

   652 	  i.n=INVALID;

   653 	  break;

   654 	case 2: //vmi->t

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

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

   657 	  break;

   658       }

   659       return i;

   660     }

   662     EdgeIt& next(EdgeIt& i) const {

   663       switch (i.spec) {

   664 	case 0:

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

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

   667 	    i.spec=1;

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

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

   670 	      i.spec=2;

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

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

   673 	    }

   674 	  }

   675 	  break;

   676 	case 1:

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

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

   679 	    i.spec=2;

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

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

   682 	  }

   683 	  break;

   684 	case 2:

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

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

   687 	  break;

   688       }

   689       return i;

   690     }

   692     Node tail(const Edge& e) const {

   693       switch (e.spec) {

   694       case 0:

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

   696 	break;

   697       case 1:

   698 	return S_NODE;

   699 	break;

   700       case 2:

   701       default:

   702 	return Node(e.n);

   703 	break;

   704       }

   705     }

   706     Node head(const Edge& e) const {

   707       switch (e.spec) {

   708       case 0:

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

   710 	break;

   711       case 1:

   712 	return Node(e.n);

   713 	break;

   714       case 2:

   715       default:

   716 	return T_NODE;

   717 	break;

   718       }

   719     }

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

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

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

   725     int edgeNum() const {

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

   727     }

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

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

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

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

   734     void addNode() const { }

   735     void addEdge() const { }

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

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

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

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

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

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

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

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

   748     protected:

   749       T s_value, t_value;

   750     public:

   751       NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) :

   752 	Parent(_G),

   753 	s_value(),

   754 	t_value() { }

   755       NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, T a)

   756 	: Parent(_G, a),

   757 	  s_value(a),

   758 	  t_value(a) { }

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

   760 	switch (n.spec) {

   761 	case 0:

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

   763 	case 1:

   764 	  return s_value;

   765 	case 2:

   766 	default:

   767 	  return t_value;

   768 	}

   769       }

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

   771 	switch (n.spec) {

   772 	case 0:

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

   774 	  break;

   775 	case 1:

   776 	  s_value=t;

   777 	  break;

   778 	case 2:

   779 	default:

   780 	  t_value=t;

   781 	  break;

   782 	}

   783       }

   784     };

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

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

   788     /// stGraphWrapper<Graph, sIterableMap, tIterableMap>.

   789     template<typename NM> class NodeMapWrapper {

   790     public:

   791       typedef Node KeyType;

   792       typedef typename NM::ValueType ValueType;

   793     protected:

   794       NM* nm;

   795       ValueType* s_value, t_value;

   796     public:

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

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

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

   800 	switch (n.getSpec()) {

   801 	case 0:

   802 	  return (*nm)[n];

   803 	case 1:

   804 	  return *s_value;

   805 	case 2:

   806 	default:

   807 	  return *t_value;

   808 	}

   809       }

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

   811 	switch (n.getSpec()) {

   812 	case 0:

   813 	  nm->set(n, t);

   814 	  break;

   815 	case 1:

   816 	  *s_value=t;

   817 	  break;

   818 	case 2:

   819 	default:

   820 	  *t_value=t;

   821 	  break;

   822 	}

   823       }

   824     };

   826     template<typename T>

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

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

   829     protected:

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

   831     public:

   832       EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G)

   833 	: Parent(_G),

   834 	  node_value(_G) { }

   835       EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, T a)

   836 	: Parent(_G, a),

   837 	  node_value(_G, a) { }

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

   839 	switch (e.spec) {

   840 	case 0:

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

   842 	case 1:

   843 	  return node_value[e.n];

   844 	case 2:

   845 	default:

   846 	  return node_value[e.n];

   847 	}

   848       }

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

   850 	switch (e.spec) {

   851 	case 0:

   852 	  Parent::set(e, t);

   853 	  break;

   854 	case 1:

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

   856 	  break;

   857 	case 2:

   858 	default:

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

   860 	  break;

   861 	}

   862       }

   863     };

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

   866     /// to an edge-map of stGraphWrapper<Graph, sIterableMap, tIterableMap>.

   867     template<typename EM, typename NM>

   868     class EdgeMapWrapper {

   869     public:

   870       typedef Edge KeyType;

   871       typedef typename EM::ValueType ValueType;

   872     protected:

   873       EM* em;

   874       NM* nm;

   875     public:

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

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

   878 	switch (e.getSpec()) {

   879 	case 0:

   880 	  return (*em)[e];

   881 	case 1:

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

   883 	case 2:

   884 	default:

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

   886 	}

   887       }

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

   889 	switch (e.getSpec()) {

   890 	case 0:

   891 	  em->set(e, t);

   892 	  break;

   893 	case 1:

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

   895 	  break;

   896 	case 2:

   897 	default:

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

   899 	  break;

   900 	}

   901       }

   902     };

   905 //  template<typename G>

   906     friend std::ostream&

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

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

   909       return os;

   910     }

   911 //  template<typename G>

   912     friend std::ostream&

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

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

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

   916       return os;

   917     }

   919   };

   921   ///@}

   923 } //namespace hugo

   926 #endif //HUGO_BIPARTITE_GRAPH_WRAPPER_H

author	marci
	Thu, 16 Sep 2004 13:54:46 +0000
changeset 865	2f3f87afb1d2
parent 762	511200bdb71f
child 902	309d81806228
permissions	-rw-r--r--