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

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

     2 #ifndef LEMON_BIPARTITE_GRAPH_WRAPPER_H

     3 #define LEMON_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 <lemon/invalid.h>

    14 #include <iter_map.h>

    15 #include <lemon/graph_wrapper.h>

    16 #include <for_each_macros.h>

    18 namespace lemon {

    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 : public Node {

    75       friend class BipartiteGraphWrapper<Graph>;

    76     protected:

    77       const BipartiteGraphWrapper<Graph>* gw;

    78     public:

    79       ClassNodeIt() { }

    80       ClassNodeIt(Invalid i) : Node(i) { }

    81       ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, bool _class) :

    82 	Node(), gw(&_gw) {

    83 	_gw.s_false_t_true_map->first(*this, _class);

    84       }

    85       //FIXME needed in new concept, important here

    86       ClassNodeIt(const BipartiteGraphWrapper<Graph>& _gw, const Node& n) :

    87 	Node(n), gw(&_gw) { }

    88       ClassNodeIt& operator++() {

    89 	gw->s_false_t_true_map->next(*this);

    90 	return *this;

    91       }

    92     };

    93 //     class SNodeIt {

    94 //       Node n;

    95 //     public:

    96 //       SNodeIt() { }

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

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

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

   100 //       }

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

   102 //     };

   103 //     class TNodeIt {

   104 //       Node n;

   105 //     public:

   106 //       TNodeIt() { }

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

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

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

   110 //       }

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

   112 //     };

   113 //     class OutEdgeIt {

   114 //       friend class BipartiteGraphWrapper<Graph>;

   115 //     protected:

   116 //       typename Graph::OutEdgeIt e;

   117 //     public:

   118 //       OutEdgeIt() { }

   119 //       OutEdgeIt(const Invalid& i) : e(i) { }

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

   121 // 	if (!(*(_G.s_false_t_true_map))[_n])

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

   123 // 	else

   124 // 	  e=INVALID;

   125 //       }

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

   127 //     };

   128 //     class InEdgeIt {

   129 //       friend class BipartiteGraphWrapper<Graph>;

   130 //     protected:

   131 //       typename Graph::InEdgeIt e;

   132 //     public:

   133 //       InEdgeIt() { }

   134 //       InEdgeIt(const Invalid& i) : e(i) { }

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

   136 // 	if ((*(_G.s_false_t_true_map))[_n])

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

   138 // 	else

   139 // 	  e=INVALID;

   140 //       }

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

   142 //     };

   144     using GraphWrapper<Graph>::first;

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

   146       n=ClassNodeIt(*this, _class); return n;

   147     }

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

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

   150 //     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {

   151 //       i=OutEdgeIt(*this, p); return i;

   152 //     }

   153 //     InEdgeIt& first(InEdgeIt& i, const Node& p) const {

   154 //       i=InEdgeIt(*this, p); return i;

   155 //     }

   157 //     using GraphWrapper<Graph>::next;

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

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

   160 //     }

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

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

   163 //     }

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

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

   166 //     }

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

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

   170 //     Node source(const Edge& e) {

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

   172 // 	return Node(this->graph->source(e));

   173 //       else

   174 // 	return Node(this->graph->target(e));

   175 //     }

   176 //     Node target(const Edge& e) {

   177 //       if (!(*(this->s_false_t_true_map))[this->graph->source(e)])

   178 // 	return Node(this->graph->target(e));

   179 //       else

   180 // 	return Node(this->graph->source(e));

   181 //     }

   183 //     Node aNode(const OutEdgeIt& e) const {

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

   185 //     }

   186 //     Node aNode(const InEdgeIt& e) const {

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

   188 //     }

   189 //     Node bNode(const OutEdgeIt& e) const {

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

   191 //     }

   192 //     Node bNode(const InEdgeIt& e) const {

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

   194 //     }

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

   197     bool inSClass(const Node& n) const {

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

   199     }

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

   202     bool inTClass(const Node& n) const {

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

   204     }

   205   };

   208   template<typename G>

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

   210   template<typename G>

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

   213   /// \brief A bipartite graph template class

   214   ///

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

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

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

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

   219   /// reference containing the elements for the

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

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

   222   ///

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

   224   /// does not work well.

   225   template<typename Graph>

   226   class BipartiteGraph : public BipartiteGraphWrapper<Graph> {

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

   228 //     SFalseTTrueMap;

   229     typedef BipartiteGraphWrapper<Graph> Parent;

   230   protected:

   231     Graph gr;

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

   233     typename Parent::SFalseTTrueMap s_false_t_true_map;

   234   public:

   235     typedef typename Parent::Node Node;

   236     typedef typename Parent::Edge Edge;

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

   238 		       gr(), bipartite_map(gr, -1),

   239 		       s_false_t_true_map(bipartite_map) {

   240       Parent::setGraph(gr);

   241       Parent::setSFalseTTrueMap(s_false_t_true_map);

   242     }

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

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

   246     Node addNode(bool b) {

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

   248       bipartite_map.update();

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

   250       s_false_t_true_map.insert(n, b);

   251       return n;

   252     }

   254     /// A new edge is inserted.

   255     ///\pre \c source have to be in \c S_Class and \c target in \c T_Class.

   256     Edge addEdge(const Node& source, const Node& target) {

   257       return Parent::graph->addEdge(source, target);

   258     }

   260     void erase(const Node& n) {

   261       s_false_t_true_map.remove(n);

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

   263     }

   264     void erase(const Edge& e) {

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

   266     }

   268     void clear() {

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

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

   271     }

   272   };

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

   275   class stGraphWrapper;

   277   /// Easier stuff for bipartite graphs.

   278   template<typename Graph>

   279   class stBipartiteGraphWrapper : public

   280   stGraphWrapper<Graph, typename Graph::SFalseTTrueMap,

   281 		 typename Graph::SFalseTTrueMap> {

   282   public:

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

   284 			   typename Graph::SFalseTTrueMap> Parent;

   285     stBipartiteGraphWrapper(Graph& _graph) :

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

   287   };

   289 //   template<typename Graph>

   290 //   std::ostream&

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

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

   293 //     return os;

   294 //   }

   295 //   template<typename Graph>

   296 //   std::ostream&

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

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

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

   300 //     return os;

   301 //   }

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

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

   305   ///

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

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

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

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

   310   /// According to the bipartite graph concepts the bipartite

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

   312   ///

   313   /// \author Marton Makai

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

   315   class stGraphWrapper : public GraphWrapper<Graph> {

   316   protected:

   317     const sIterableMap* s_iterable_map;

   318     const tIterableMap* t_iterable_map;

   319   public:

   320     class Node;

   321     friend class Node;

   322 //GN, int

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

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

   325     class NodeIt;

   326     friend class NodeIt;

   327 //GNI, int

   328     class Edge;

   329     friend class Edge;

   330 //GE, int, GN

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

   332 //invalid: (invalid, 3, invalid)

   333     class OutEdgeIt;

   334     friend class OutEdgeIt;

   335 //GO, int, GNI

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

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

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

   339     class InEdgeIt;

   340     friend class InEdgeIt;

   341 //GI, int, GNI

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

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

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

   345     class EdgeIt;

   346     friend class EdgeIt;

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

   348 //(invalid, 1, vmi)

   349 //(invalid, 2, vmi)

   350 //invalid, 3, invalid)

   351     template <typename T> class NodeMap;

   352     template <typename T> class EdgeMap;

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

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

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

   358     const Node S_NODE;

   359     const Node T_NODE;

   361     static const bool S_CLASS=false;

   362     static const bool T_CLASS=true;

   364     // \bug not too nice constructor.

   365     stGraphWrapper(Graph& _graph,

   366 		   const sIterableMap& _s_iterable_map,

   367 		   const tIterableMap& _t_iterable_map) :

   368       GraphWrapper<Graph>(_graph),

   369       s_iterable_map(&_s_iterable_map),

   370       t_iterable_map(&_t_iterable_map),

   371       S_NODE(INVALID, 1),

   372       T_NODE(INVALID, 2) { }

   375 //    std::ostream&

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

   377 //    friend std::ostream&

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

   379 //    friend std::ostream&

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

   382     class Node : public Graph::Node {

   383     protected:

   384       friend class GraphWrapper<Graph>;

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

   386       template <typename T> friend class NodeMap;

   387       friend class Edge;

   388       friend class OutEdgeIt;

   389       friend class InEdgeIt;

   390       friend class EdgeIt;

   391       int spec;

   392     public:

   393       Node() { }

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

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

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

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

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

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

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

   401       }

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

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

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

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

   406       }

   407 //      template<typename G>

   408 //      friend std::ostream&

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

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

   411       int getSpec() const { return spec; }

   412     };

   414     class NodeIt {

   415       friend class GraphWrapper<Graph>;

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

   417       typename Graph::NodeIt n;

   418       int spec;

   419      public:

   420       NodeIt() { }

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

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

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

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

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

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

   427       }

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

   429     };

   431     class Edge : public Graph::Edge {

   432       friend class GraphWrapper<Graph>;

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

   434       template <typename T> friend class EdgeMap;

   435       int spec;

   436       typename Graph::Node n;

   437     public:

   438       Edge() { }

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

   440 	   const typename Graph::Node& _n) :

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

   442       }

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

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

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

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

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

   448 		u.n==v.n);

   449       }

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

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

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

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

   454 		u.n!=v.n);

   455       }

   456 //      template<typename G>

   457 //      friend std::ostream&

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

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

   460       int getSpec() const { return spec; }

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

   462     };

   464     class OutEdgeIt {

   465       friend class GraphWrapper<Graph>;

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

   467       typename Graph::OutEdgeIt e;

   468       int spec;

   469       typename Graph::ClassNodeIt n;

   470     public:

   471       OutEdgeIt() { }

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

   473 		const typename Graph::ClassNodeIt& _n) :

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

   475       }

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

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

   478 		const Node& _n) {

   479 	switch (_n.spec) {

   480 	  case 0 :

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

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

   483 					  typename Graph::Node(_n));

   484 	      spec=0;

   485 	      n=INVALID;

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

   487 	    } else { //T, specko kiel van

   488 	      e=INVALID;

   489 	      spec=2;

   490 	      n=_n;

   491 	    }

   492 	    break;

   493 	  case 1:

   494 	    e=INVALID;

   495 	    spec=1;

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

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

   498 	    break;

   499 	  case 2:

   500 	    e=INVALID;

   501 	    spec=3;

   502 	    n=INVALID;

   503 	    break;

   504 	}

   505       }

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

   507     };

   509     class InEdgeIt {

   510       friend class GraphWrapper<Graph>;

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

   512       typename Graph::InEdgeIt e;

   513       int spec;

   514       typename Graph::ClassNodeIt n;

   515     public:

   516       InEdgeIt() { }

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

   518 	       const typename Graph::ClassNodeIt& _n) :

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

   520       }

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

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

   523 	       const Node& _n) {

   524 	switch (_n.spec) {

   525 	  case 0 :

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

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

   528 					 typename Graph::Node(_n));

   529 	      spec=0;

   530 	      n=INVALID;

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

   532 	    } else { //S, specko beel van

   533 	      e=INVALID;

   534 	      spec=1;

   535 	      n=_n;

   536 	    }

   537 	    break;

   538 	  case 1:

   539 	    e=INVALID;

   540 	    spec=3;

   541 	    n=INVALID;

   542 	    break;

   543 	  case 2:

   544 	    e=INVALID;

   545 	    spec=2;

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

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

   548 	    break;

   549 	}

   550       }

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

   552     };

   554     class EdgeIt {

   555       friend class GraphWrapper<Graph>;

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

   557       typename Graph::EdgeIt e;

   558       int spec;

   559       typename Graph::ClassNodeIt n;

   560     public:

   561       EdgeIt() { }

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

   563 	     const typename Graph::ClassNodeIt& _n) :

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

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

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

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

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

   569 	  spec=1;

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

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

   572 	    spec=2;

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

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

   575 	      spec=3;

   576 	    }

   577 	  }

   578 	}

   579       }

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

   581     };

   583     NodeIt& first(NodeIt& i) const {

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

   585     }

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

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

   588     }

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

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

   591     }

   592     EdgeIt& first(EdgeIt& i) const {

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

   594     }

   596     NodeIt& next(NodeIt& i) const {

   597       switch (i.spec) {

   598 	case 0:

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

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

   601 	    i.spec=1;

   602 	  }

   603 	  break;

   604 	case 1:

   605 	  i.spec=2;

   606 	  break;

   607 	case 2:

   608 	  i.spec=3;

   609 	  break;

   610       }

   611       return i;

   612     }

   613     OutEdgeIt& next(OutEdgeIt& i) const {

   614       typename Graph::Node v;

   615       switch (i.spec) {

   616 	case 0: //normal edge

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

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

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

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

   621 	      i.spec=3;

   622 	      i.n=INVALID;

   623 	    } else { //T, van kiel

   624 	      i.spec=2;

   625 	      i.n=v;

   626 	    }

   627 	  }

   628 	  break;

   629 	case 1: //s->vmi

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

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

   632 	  break;

   633 	case 2: //vmi->t

   634 	  i.spec=3;

   635 	  i.n=INVALID;

   636 	  break;

   637       }

   638       return i;

   639     }

   640     InEdgeIt& next(InEdgeIt& i) const {

   641       typename Graph::Node v;

   642       switch (i.spec) {

   643 	case 0: //normal edge

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

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

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

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

   648 	      i.spec=3;

   649 	      i.n=INVALID;

   650 	    } else { //S, van beel

   651 	      i.spec=1;

   652 	      i.n=v;

   653 	    }

   654 	  }

   655 	  break;

   656 	case 1: //s->vmi

   657 	  i.spec=3;

   658 	  i.n=INVALID;

   659 	  break;

   660 	case 2: //vmi->t

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

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

   663 	  break;

   664       }

   665       return i;

   666     }

   668     EdgeIt& next(EdgeIt& i) const {

   669       switch (i.spec) {

   670 	case 0:

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

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

   673 	    i.spec=1;

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

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

   676 	      i.spec=2;

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

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

   679 	    }

   680 	  }

   681 	  break;

   682 	case 1:

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

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

   685 	    i.spec=2;

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

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

   688 	  }

   689 	  break;

   690 	case 2:

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

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

   693 	  break;

   694       }

   695       return i;

   696     }

   698     Node source(const Edge& e) const {

   699       switch (e.spec) {

   700       case 0:

   701 	return Node(this->graph->source(e));

   702 	break;

   703       case 1:

   704 	return S_NODE;

   705 	break;

   706       case 2:

   707       default:

   708 	return Node(e.n);

   709 	break;

   710       }

   711     }

   712     Node target(const Edge& e) const {

   713       switch (e.spec) {

   714       case 0:

   715 	return Node(this->graph->target(e));

   716 	break;

   717       case 1:

   718 	return Node(e.n);

   719 	break;

   720       case 2:

   721       default:

   722 	return T_NODE;

   723 	break;

   724       }

   725     }

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

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

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

   731     int edgeNum() const {

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

   733     }

   735     Node aNode(const OutEdgeIt& e) const { return source(e); }

   736     Node aNode(const InEdgeIt& e) const { return target(e); }

   737     Node bNode(const OutEdgeIt& e) const { return target(e); }

   738     Node bNode(const InEdgeIt& e) const { return source(e); }

   740     void addNode() const { }

   741     void addEdge() const { }

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

   744 //    Edge addEdge(const Node& source, const Node& target) const {

   745 //      return Edge(this->graph->addEdge(source, target)); }

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

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

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

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

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

   754     protected:

   755       T s_value, t_value;

   756     public:

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

   758 	Parent(_G),

   759 	s_value(),

   760 	t_value() { }

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

   762 	: Parent(_G, a),

   763 	  s_value(a),

   764 	  t_value(a) { }

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

   766 	switch (n.spec) {

   767 	case 0:

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

   769 	case 1:

   770 	  return s_value;

   771 	case 2:

   772 	default:

   773 	  return t_value;

   774 	}

   775       }

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

   777 	switch (n.spec) {

   778 	case 0:

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

   780 	  break;

   781 	case 1:

   782 	  s_value=t;

   783 	  break;

   784 	case 2:

   785 	default:

   786 	  t_value=t;

   787 	  break;

   788 	}

   789       }

   790     };

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

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

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

   795     template<typename NM> class NodeMapWrapper {

   796     public:

   797       typedef Node Key;

   798       typedef typename NM::Value Value;

   799     protected:

   800       NM* nm;

   801       Value* s_value, t_value;

   802     public:

   803       NodeMapWrapper(NM& _nm, Value& _s_value, Value& _t_value) :

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

   805       Value operator[](const Node& n) const {

   806 	switch (n.getSpec()) {

   807 	case 0:

   808 	  return (*nm)[n];

   809 	case 1:

   810 	  return *s_value;

   811 	case 2:

   812 	default:

   813 	  return *t_value;

   814 	}

   815       }

   816       void set(const Node& n, Value t) {

   817 	switch (n.getSpec()) {

   818 	case 0:

   819 	  nm->set(n, t);

   820 	  break;

   821 	case 1:

   822 	  *s_value=t;

   823 	  break;

   824 	case 2:

   825 	default:

   826 	  *t_value=t;

   827 	  break;

   828 	}

   829       }

   830     };

   832     template<typename T>

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

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

   835     protected:

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

   837     public:

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

   839 	: Parent(_G),

   840 	  node_value(_G) { }

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

   842 	: Parent(_G, a),

   843 	  node_value(_G, a) { }

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

   845 	switch (e.spec) {

   846 	case 0:

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

   848 	case 1:

   849 	  return node_value[e.n];

   850 	case 2:

   851 	default:

   852 	  return node_value[e.n];

   853 	}

   854       }

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

   856 	switch (e.spec) {

   857 	case 0:

   858 	  Parent::set(e, t);

   859 	  break;

   860 	case 1:

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

   862 	  break;

   863 	case 2:

   864 	default:

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

   866 	  break;

   867 	}

   868       }

   869     };

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

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

   873     template<typename EM, typename NM>

   874     class EdgeMapWrapper {

   875     public:

   876       typedef Edge Key;

   877       typedef typename EM::Value Value;

   878     protected:

   879       EM* em;

   880       NM* nm;

   881     public:

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

   883       Value operator[](const Edge& e) const {

   884 	switch (e.getSpec()) {

   885 	case 0:

   886 	  return (*em)[e];

   887 	case 1:

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

   889 	case 2:

   890 	default:

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

   892 	}

   893       }

   894       void set(const Edge& e, Value t) {

   895 	switch (e.getSpec()) {

   896 	case 0:

   897 	  em->set(e, t);

   898 	  break;

   899 	case 1:

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

   901 	  break;

   902 	case 2:

   903 	default:

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

   905 	  break;

   906 	}

   907       }

   908     };

   911 //  template<typename G>

   912     friend std::ostream&

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

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

   915       return os;

   916     }

   917 //  template<typename G>

   918     friend std::ostream&

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

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

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

   922       return os;

   923     }

   925   };

   927   ///@}

   929 } //namespace lemon

   932 #endif //LEMON_BIPARTITE_GRAPH_WRAPPER_H

author	alpar
	Sun, 14 Nov 2004 13:15:46 +0000
changeset 991	e619a466ca5d
parent 986	e997802b855c
permissions	-rw-r--r--