marci@174: // -*- c++ -*-
marci@496: #ifndef HUGO_BIPARTITE_GRAPH_WRAPPER_H
marci@496: #define HUGO_BIPARTITE_GRAPH_WRAPPER_H
marci@76: 
klao@491: ///\ingroup gwrappers
alpar@457: ///\file
alpar@457: ///\brief Several graph wrappers.
alpar@457: ///
alpar@457: ///This file contains several useful graph wrapper functions.
alpar@457: ///
alpar@457: ///\author Marton Makai
alpar@457: 
marci@555: #include <hugo/invalid.h>
marci@368: #include <iter_map.h>
marci@557: #include <hugo/graph_wrapper.h>
marci@762: #include <for_each_macros.h>
marci@174: 
alpar@105: namespace hugo {
marci@76: 
marci@641:   /// \brief A wrapper for composing a bipartite graph from a graph 
marci@641:   /// and from a node-map showing for any node which color class it belongs to.
marci@641:   ///
marci@368:   /// A wrapper for composing a bipartite graph.
marci@371:   /// \c _graph have to be a reference to a graph of type \c Graph 
marci@371:   /// and \c _s_false_t_true_map is an \c IterableBoolMap 
marci@368:   /// reference containing the elements for the 
marci@371:   /// color classes S and T. \c _graph is to be referred to an undirected 
marci@371:   /// graph or a directed graph with edges oriented from S to T.
alpar@457:   ///
marci@641:   /// \author Marton Makai
marci@368:   template<typename Graph> 
marci@368:   class BipartiteGraphWrapper : public GraphWrapper<Graph> {
marci@768:   public:
marci@389:     typedef IterableBoolMap< typename Graph::template NodeMap<int> > 
marci@389:     SFalseTTrueMap;
marci@768:   protected:
marci@368:     SFalseTTrueMap* s_false_t_true_map;
marci@393: 
marci@501:     BipartiteGraphWrapper() : GraphWrapper<Graph>()/*, 
marci@501: 						     S_CLASS(false), T_CLASS(true)*/ { }
marci@497:     void setSFalseTTrueMap(SFalseTTrueMap& _s_false_t_true_map) { 
marci@499:       s_false_t_true_map=&_s_false_t_true_map;
marci@497:     }
marci@497: 
marci@368:   public:
marci@409:     //marci
marci@409:     //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
marci@502:     static const bool S_CLASS;
marci@502:     static const bool T_CLASS;
marci@768: 
marci@768:     /// This method is to reach the iterable maps of the bipartite graph or 
marci@768:     /// bipartite graph wrapper.
marci@768:     const SFalseTTrueMap& sFalseTTrueMap() const { 
marci@768:       return *s_false_t_true_map; 
marci@768:     }
marci@379:     
marci@501:     //bool S_CLASS;
marci@501:     //bool T_CLASS;
marci@409: 
marci@368:     BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 
marci@500:       : GraphWrapper<Graph>(_graph), 
marci@501: 	s_false_t_true_map(&_s_false_t_true_map)/*, 
marci@501: 						  S_CLASS(false), T_CLASS(true)*/ { }
marci@368:     typedef typename GraphWrapper<Graph>::Node Node;
marci@368:     //using GraphWrapper<Graph>::NodeIt;
marci@368:     typedef typename GraphWrapper<Graph>::Edge Edge;
marci@368:     //using GraphWrapper<Graph>::EdgeIt;
marci@393:     class ClassNodeIt;
marci@393:     friend class ClassNodeIt;
marci@393:     class OutEdgeIt;
marci@393:     friend class OutEdgeIt;
marci@393:     class InEdgeIt;
marci@393:     friend class InEdgeIt;
marci@379:     class ClassNodeIt {
marci@393:       friend class BipartiteGraphWrapper<Graph>;
marci@393:     protected:
marci@368:       Node n;
marci@368:     public:
marci@379:       ClassNodeIt() { }
marci@379:       ClassNodeIt(const Invalid& i) : n(i) { }
marci@379:       ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) { 
marci@379: 	_G.s_false_t_true_map->first(n, _class); 
marci@368:       }
marci@381:       //FIXME needed in new concept, important here
marci@381:       ClassNodeIt(const Node& _n) : n(_n) { }
marci@368:       operator Node() const { return n; }
marci@368:     };
marci@379: //     class SNodeIt {
marci@379: //       Node n;
marci@379: //     public:
marci@379: //       SNodeIt() { }
marci@379: //       SNodeIt(const Invalid& i) : n(i) { }
marci@379: //       SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
marci@379: // 	_G.s_false_t_true_map->first(n, false); 
marci@379: //       }
marci@379: //       operator Node() const { return n; }
marci@379: //     };
marci@379: //     class TNodeIt {
marci@379: //       Node n;
marci@379: //     public:
marci@379: //       TNodeIt() { }
marci@379: //       TNodeIt(const Invalid& i) : n(i) { }
marci@379: //       TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
marci@379: // 	_G.s_false_t_true_map->first(n, true); 
marci@379: //       }
marci@379: //       operator Node() const { return n; }
marci@379: //     };
marci@368:     class OutEdgeIt { 
marci@393:       friend class BipartiteGraphWrapper<Graph>;
marci@393:     protected:
marci@368:       typename Graph::OutEdgeIt e;
marci@368:     public:
marci@368:       OutEdgeIt() { }
marci@368:       OutEdgeIt(const Invalid& i) : e(i) { }
marci@368:       OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
marci@368: 	if (!(*(_G.s_false_t_true_map))[_n]) 
marci@379: 	  e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
marci@368: 	else 
marci@368: 	  e=INVALID;
marci@368:       }
marci@368:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@368:     };
marci@368:     class InEdgeIt { 
marci@393:       friend class BipartiteGraphWrapper<Graph>;
marci@393:     protected:
marci@368:       typename Graph::InEdgeIt e;
marci@368:     public:
marci@368:       InEdgeIt() { }
marci@368:       InEdgeIt(const Invalid& i) : e(i) { }
marci@368:       InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
marci@368: 	if ((*(_G.s_false_t_true_map))[_n]) 
marci@379: 	  e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
marci@368: 	else 
marci@368: 	  e=INVALID;
marci@368:       }
marci@368:       operator Edge() const { return Edge(typename Graph::Edge(e)); }
marci@368:     };
marci@368: 
marci@368:     using GraphWrapper<Graph>::first;
marci@379:     ClassNodeIt& first(ClassNodeIt& n, bool _class) const { 
marci@393:       n=ClassNodeIt(*this, _class) ; return n; }
marci@379: //    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
marci@379: //    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
marci@379:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
marci@379:       i=OutEdgeIt(*this, p); return i;
marci@379:     }
marci@379:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
marci@379:       i=InEdgeIt(*this, p); return i;
marci@379:     }
marci@368: 
marci@368:     using GraphWrapper<Graph>::next;
marci@379:     ClassNodeIt& next(ClassNodeIt& n) const { 
marci@393:       this->s_false_t_true_map->next(n.n); return n; 
marci@368:     }
marci@379: //     SNodeIt& next(SNodeIt& n) const { 
marci@379: //       this->s_false_t_true_map->next(n); return n; 
marci@379: //     }
marci@379: //     TNodeIt& next(TNodeIt& n) const { 
marci@379: //       this->s_false_t_true_map->next(n); return n; 
marci@379: //     }
marci@389:     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
marci@389:     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
marci@368: 
marci@368:     Node tail(const Edge& e) { 
marci@368:       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
marci@368: 	return Node(this->graph->tail(e));
marci@368:       else
marci@368: 	return Node(this->graph->head(e));	
marci@368:     }
marci@368:     Node head(const Edge& e) { 
marci@368:       if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
marci@368: 	return Node(this->graph->head(e));
marci@368:       else
marci@368: 	return Node(this->graph->tail(e));	
marci@368:     }
marci@368: 
marci@368:     Node aNode(const OutEdgeIt& e) const { 
marci@368:       return Node(this->graph->aNode(e.e)); 
marci@368:     }
marci@368:     Node aNode(const InEdgeIt& e) const { 
marci@368:       return Node(this->graph->aNode(e.e)); 
marci@368:     }
marci@368:     Node bNode(const OutEdgeIt& e) const { 
marci@368:       return Node(this->graph->bNode(e.e)); 
marci@368:     }
marci@368:     Node bNode(const InEdgeIt& e) const { 
marci@368:       return Node(this->graph->bNode(e.e)); 
marci@368:     }
marci@379: 
marci@641:     /// Returns true iff \c n is in S.
marci@379:     bool inSClass(const Node& n) const {
marci@381:       return !(*(this->s_false_t_true_map))[n];
marci@379:     }
marci@641: 
marci@641:     /// Returns true iff \c n is in T.
marci@379:     bool inTClass(const Node& n) const {
marci@381:       return (*(this->s_false_t_true_map))[n];
marci@379:     }
marci@368:   };
marci@368: 
marci@502: 
marci@502:   template<typename G>
marci@502:   const bool BipartiteGraphWrapper<G>::S_CLASS=false;
marci@502:   template<typename G>
marci@502:   const bool BipartiteGraphWrapper<G>::T_CLASS=true;
marci@502: 
marci@641:   /// \brief A bipartite graph template class
marci@641:   ///
marci@641:   /// This class composes a bipartite graph over a directed or undirected 
marci@641:   /// graph structure of type \c Graph.
marci@641:   /// \c _graph have to be a reference to a graph of type \c Graph 
marci@641:   /// and \c _s_false_t_true_map is an \c IterableBoolMap 
marci@641:   /// reference containing the elements for the 
marci@641:   /// color classes S and T. \c _graph is to be referred to an undirected 
marci@641:   /// graph or a directed graph with edges oriented from S to T.
marci@641:   ///
marci@641:   ///\bug experimental. Do not use this while the bipartitemap augmentation 
marci@497:   /// does not work well.
marci@497:   template<typename Graph>
marci@497:   class BipartiteGraph : public BipartiteGraphWrapper<Graph> {
marci@768: //     typedef IterableBoolMap< typename Graph::template NodeMap<int> > 
marci@768: //     SFalseTTrueMap;
marci@497:     typedef BipartiteGraphWrapper<Graph> Parent;
marci@497:   protected:
marci@497:     Graph gr;
marci@497:     typename Graph::template NodeMap<int> bipartite_map;
marci@768:     typename Parent::SFalseTTrueMap s_false_t_true_map;
marci@497:   public:
marci@497:     typedef typename Parent::Node Node;
marci@497:     typedef typename Parent::Edge Edge;
marci@499:     BipartiteGraph() : BipartiteGraphWrapper<Graph>(), 
marci@500: 		       gr(), bipartite_map(gr, -1), 
marci@497: 		       s_false_t_true_map(bipartite_map) { 
marci@497:       Parent::setGraph(gr); 
marci@499:       Parent::setSFalseTTrueMap(s_false_t_true_map);
marci@497:     }
marci@497: 
marci@497:     /// the \c bool parameter which can be \c S_Class or \c T_Class shows 
marci@497:     /// the color class where the new node is to be inserted.
marci@498:     Node addNode(bool b) {
marci@498:       Node n=Parent::graph->addNode();
marci@498:       bipartite_map.update();
marci@501:       //bipartite_map.set(n, -1);
marci@498:       s_false_t_true_map.insert(n, b);
marci@498:       return n;
marci@498:     }
marci@497: 
marci@497:     /// A new edge is inserted.
marci@497:     ///\pre \c tail have to be in \c S_Class and \c head in \c T_Class.
marci@498:     Edge addEdge(const Node& tail, const Node& head) {
marci@498:       return Parent::graph->addEdge(tail, head);
marci@498:     }
marci@497: 
marci@498:     void erase(const Node& n) {
marci@498:       s_false_t_true_map.remove(n);
marci@498:       Parent::graph->erase(n);
marci@498:     }
marci@498:     void erase(const Edge& e) {
marci@498:       Parent::graph->erase(e);
marci@498:     }
marci@497:     
marci@497:     void clear() {
marci@558:       FOR_EACH_LOC(typename Parent::EdgeIt, e, *this) erase(e);
marci@558:       FOR_EACH_LOC(typename Parent::NodeIt, n, *this) erase(n);
marci@497:     }
marci@497:   };
marci@497: 
marci@768:   template<typename Graph, typename sIterableMap, typename tIterableMap>
marci@768:   class stGraphWrapper;
marci@497: 
marci@768:   /// Easier stuff for bipartite graphs.
marci@435:   template<typename Graph>
marci@768:   class stBipartiteGraphWrapper : public 
marci@768:   stGraphWrapper<Graph, typename Graph::SFalseTTrueMap, 
marci@768: 		 typename Graph::SFalseTTrueMap> {
marci@768:   public:
marci@768:     typedef stGraphWrapper<Graph, typename Graph::SFalseTTrueMap, 
marci@768: 			   typename Graph::SFalseTTrueMap> Parent;
marci@768:     stBipartiteGraphWrapper(Graph& _graph) : 
marci@768:       Parent(_graph, _graph.sFalseTTrueMap(), _graph.sFalseTTrueMap()) { }
marci@768:   };
marci@435: 
marci@435: //   template<typename Graph> 
marci@435: //   std::ostream& 
marci@435: //   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Node& i) { 
marci@435: //     os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; 
marci@435: //     return os; 
marci@435: //   }
marci@435: //   template<typename Graph> 
marci@435: //   std::ostream& 
marci@435: //   operator<<(std::ostream& os, const typename stGraphWrapper<Graph>::Edge& i) { 
marci@435: //     os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << 
marci@435: //       " node: " << i.n << ")"; 
marci@435: //     return os; 
marci@435: //   }
marci@341: 
marci@641:   /// \brief A wrapper for adding extra nodes s and t to a bipartite graph
marci@641:   /// and edges from s to each node of S and form each node of T to t.
marci@641:   /// 
marci@641:   /// A wrapper for adding extra nodes s and t to a bipartite graph
marci@641:   /// and edges from s to each node of S and form each node of T to t.
marci@641:   /// This class is very useful to reduce some matching or more
marci@641:   /// generally, capacitataed b-matching problem to a flow problem.
marci@641:   /// According to the bipartite graph concepts the bipartite 
marci@641:   /// graph have to be oriented from S to T.
alpar@457:   ///
marci@641:   /// \author Marton Makai
marci@768:   template<typename Graph, typename sIterableMap, typename tIterableMap>
marci@379:   class stGraphWrapper : public GraphWrapper<Graph> {
marci@768:   protected:    
marci@768:     const sIterableMap* s_iterable_map;
marci@768:     const tIterableMap* t_iterable_map;
marci@379:   public:
marci@379:     class Node; 
marci@381:     friend class Node;
marci@379: //GN, int
marci@768: //0 normalis, 1 s, 2 t, ez az iteralasi sorrend, 
marci@379: //es a vege a false azaz (invalid, 3)    
marci@379:     class NodeIt;
marci@381:     friend class NodeIt;
marci@379: //GNI, int
marci@379:     class Edge;
marci@381:     friend class Edge;
marci@379: //GE, int, GN
marci@379: //0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
marci@379: //invalid: (invalid, 3, invalid)
marci@379:     class OutEdgeIt;
marci@381:     friend class OutEdgeIt;
marci@379: //GO, int, GNI
marci@379: //normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
marci@379: //s-bol (invalid, 1, first), ... (invalid, 3, invalid)
marci@379: //t-bol (invalid, 3, invalid)
marci@379:     class InEdgeIt;
marci@381:     friend class InEdgeIt;
marci@379: //GI, int, GNI
marci@379: //normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
marci@379: //s-be (invalid, 3, invalid)
marci@379: //t-be (invalid, 2, first), ... (invalid, 3, invalid)
marci@379:     class EdgeIt;
marci@381:     friend class EdgeIt;
marci@379: //(first, 0, invalid) ...
marci@379: //(invalid, 1, vmi)
marci@379: //(invalid, 2, vmi)
marci@379: //invalid, 3, invalid)
marci@379:     template <typename T> class NodeMap;
marci@510:     template <typename T> class EdgeMap;
marci@341: 
marci@379: //    template <typename T> friend class NodeMap;
marci@379: //    template <typename T> friend class EdgeMap;
marci@341: 
marci@502:     ///\todo FIXME ezt majd static-ra kell javitani
marci@379:     const Node S_NODE;
marci@379:     const Node T_NODE;
marci@341: 
marci@379:     static const bool S_CLASS=false;
marci@379:     static const bool T_CLASS=true;
marci@341: 
marci@768:     // \bug not too nice constructor.
marci@768:     stGraphWrapper(Graph& _graph, 
marci@768: 		   const sIterableMap& _s_iterable_map, 
marci@768: 		   const tIterableMap& _t_iterable_map) : 
marci@768:       GraphWrapper<Graph>(_graph), 
marci@768:       s_iterable_map(&_s_iterable_map), 
marci@768:       t_iterable_map(&_t_iterable_map), 
marci@768:       S_NODE(INVALID, 1), 
marci@768:       T_NODE(INVALID, 2) { }
marci@341: 
marci@435:     
marci@435: //    std::ostream& 
marci@435: //    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
marci@435: //    friend std::ostream& 
marci@435: //    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i);
marci@435: //    friend std::ostream& 
marci@435: //    operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i);
marci@435: 
marci@379:     class Node : public Graph::Node {
marci@379:     protected:
marci@379:       friend class GraphWrapper<Graph>;
marci@768:       friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
marci@389:       template <typename T> friend class NodeMap;
marci@380:       friend class Edge;
marci@380:       friend class OutEdgeIt;
marci@380:       friend class InEdgeIt;
marci@380:       friend class EdgeIt;
marci@379:       int spec; 
marci@379:     public:
marci@379:       Node() { }
marci@379:       Node(const typename Graph::Node& _n, int _spec=0) : 
marci@379: 	Graph::Node(_n), spec(_spec) { }
marci@379:       Node(const Invalid& i) : Graph::Node(i), spec(3) { }
marci@379:       friend bool operator==(const Node& u, const Node& v) { 
marci@379: 	return (u.spec==v.spec && 
marci@379: 		static_cast<typename Graph::Node>(u)==
marci@379: 		static_cast<typename Graph::Node>(v));
marci@379:       } 
marci@379:       friend bool operator!=(const Node& u, const Node& v) { 
marci@379: 	return (v.spec!=u.spec || 
marci@379: 		static_cast<typename Graph::Node>(u)!=
marci@379: 		static_cast<typename Graph::Node>(v));
marci@409:       }
marci@435: //      template<typename G> 
marci@435: //      friend std::ostream& 
marci@435: //      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Node& i); 
marci@435:       friend std::ostream& operator<< (std::ostream& os, const Node& i);
marci@379:       int getSpec() const { return spec; }
marci@379:     };
marci@409: 
marci@379:     class NodeIt { 
marci@379:       friend class GraphWrapper<Graph>;
marci@768:       friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
marci@379:       typename Graph::NodeIt n;
marci@379:       int spec; 
marci@379:      public:
marci@379:       NodeIt() { }
marci@379:       NodeIt(const typename Graph::NodeIt& _n, int _spec) : 
marci@379: 	n(_n), spec(_spec) { }
marci@379:       NodeIt(const Invalid& i) : n(i), spec(3) { }
marci@768:       NodeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) 
marci@768: 	: n(*(_G.graph)), spec(0) { 
marci@409: 	if (!_G.graph->valid(n)) spec=1;
marci@379:       }
marci@379:       operator Node() const { return Node(n, spec); }
marci@379:     };
marci@409: 
marci@379:     class Edge : public Graph::Edge {
marci@379:       friend class GraphWrapper<Graph>;
marci@768:       friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
marci@510:       template <typename T> friend class EdgeMap;
marci@379:       int spec;
marci@379:       typename Graph::Node n;
marci@379:     public:
marci@379:       Edge() { }
marci@379:       Edge(const typename Graph::Edge& _e, int _spec, 
marci@379: 	   const typename Graph::Node& _n) : 
marci@379: 	Graph::Edge(_e), spec(_spec), n(_n) { 
marci@379:       }
marci@379:       Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
marci@379:       friend bool operator==(const Edge& u, const Edge& v) { 
marci@379: 	return (u.spec==v.spec && 
marci@379: 		static_cast<typename Graph::Edge>(u)==
marci@379: 		static_cast<typename Graph::Edge>(v) && 
marci@379: 		u.n==v.n);
marci@379:       } 
marci@379:       friend bool operator!=(const Edge& u, const Edge& v) { 
marci@379: 	return (v.spec!=u.spec || 
marci@379: 		static_cast<typename Graph::Edge>(u)!=
marci@379: 		static_cast<typename Graph::Edge>(v) || 
marci@379: 		u.n!=v.n);
marci@379:       } 
marci@435: //      template<typename G> 
marci@435: //      friend std::ostream& 
marci@435: //      operator<<(std::ostream& os, const typename stGraphWrapper<G>::Edge& i); 
marci@435:       friend std::ostream& operator<< (std::ostream& os, const Edge& i);
marci@379:       int getSpec() const { return spec; }
marci@510:       typename Graph::Node getNode() const { return n; }
marci@379:     };
marci@409: 
marci@379:     class OutEdgeIt { 
marci@379:       friend class GraphWrapper<Graph>;
marci@768:       friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
marci@379:       typename Graph::OutEdgeIt e;
marci@379:       int spec;
marci@379:       typename Graph::ClassNodeIt n;
marci@379:     public:
marci@379:       OutEdgeIt() { }
marci@379:       OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, 
marci@379: 		const typename Graph::ClassNodeIt& _n) : 
marci@379: 	e(_e), spec(_spec), n(_n) { 
marci@379:       }
marci@379:       OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
marci@768:       OutEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, 
marci@768: 		const Node& _n) {
marci@379: 	switch (_n.spec) {
marci@379: 	  case 0 : 
marci@381: 	    if (_G.graph->inSClass(_n)) { //S, van normalis kiel 
marci@379: 	      e=typename Graph::OutEdgeIt(*(_G.graph), 
marci@379: 					  typename Graph::Node(_n)); 
marci@379: 	      spec=0;
marci@379: 	      n=INVALID;
marci@379: 	      if (!_G.graph->valid(e)) spec=3;
marci@379: 	    } else { //T, specko kiel van
marci@379: 	      e=INVALID;
marci@379: 	      spec=2;
marci@379: 	      n=_n;
marci@379: 	    }
marci@379: 	    break;
marci@379: 	  case 1:
marci@379: 	    e=INVALID;
marci@379: 	    spec=1;
marci@379: 	    _G.graph->first(n, S_CLASS); //s->vmi;
marci@379: 	    if (!_G.graph->valid(n)) spec=3; //Ha S ures
marci@379: 	    break;
marci@379: 	  case 2:
marci@379: 	    e=INVALID;
marci@379: 	    spec=3;
marci@379: 	    n=INVALID;
marci@379: 	    break;
marci@379: 	}
marci@379:       }
marci@379:       operator Edge() const { return Edge(e, spec, n); }
marci@379:     };
marci@409: 
marci@379:     class InEdgeIt { 
marci@379:       friend class GraphWrapper<Graph>;
marci@768:       friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
marci@379:       typename Graph::InEdgeIt e;
marci@379:       int spec;
marci@379:       typename Graph::ClassNodeIt n;
marci@379:     public:
marci@379:       InEdgeIt() { }
marci@379:       InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, 
marci@379: 	       const typename Graph::ClassNodeIt& _n) : 
marci@379: 	e(_e), spec(_spec), n(_n) { 
marci@379:       }
marci@379:       InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
marci@768:       InEdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, 
marci@768: 	       const Node& _n) {
marci@379: 	switch (_n.spec) {
marci@379: 	  case 0 : 
marci@381: 	    if (_G.graph->inTClass(_n)) { //T, van normalis beel 
marci@379: 	      e=typename Graph::InEdgeIt(*(_G.graph), 
marci@379: 					 typename Graph::Node(_n)); 
marci@379: 	      spec=0;
marci@379: 	      n=INVALID;
marci@379: 	      if (!_G.graph->valid(e)) spec=3;
marci@379: 	    } else { //S, specko beel van
marci@379: 	      e=INVALID;
marci@379: 	      spec=1;
marci@379: 	      n=_n;
marci@379: 	    }
marci@379: 	    break;
marci@379: 	  case 1:
marci@379: 	    e=INVALID;
marci@379: 	    spec=3;
marci@379: 	    n=INVALID;
marci@409: 	    break;
marci@379: 	  case 2:
marci@379: 	    e=INVALID;
marci@409: 	    spec=2;
marci@379: 	    _G.graph->first(n, T_CLASS); //vmi->t;
marci@379: 	    if (!_G.graph->valid(n)) spec=3; //Ha T ures
marci@379: 	    break;
marci@379: 	}
marci@379:       }
marci@379:       operator Edge() const { return Edge(e, spec, n); }
marci@379:     };
marci@409: 
marci@379:     class EdgeIt { 
marci@379:       friend class GraphWrapper<Graph>;
marci@768:       friend class stGraphWrapper<Graph, sIterableMap, tIterableMap>;
marci@379:       typename Graph::EdgeIt e;
marci@379:       int spec;
marci@379:       typename Graph::ClassNodeIt n;
marci@379:     public:
marci@379:       EdgeIt() { }
marci@379:       EdgeIt(const typename Graph::EdgeIt& _e, int _spec, 
marci@379: 	     const typename Graph::ClassNodeIt& _n) : 
marci@379: 	e(_e), spec(_spec), n(_n) { }
marci@379:       EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
marci@768:       EdgeIt(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) : 
marci@379: 	e(*(_G.graph)), spec(0), n(INVALID) { 
marci@379: 	if (!_G.graph->valid(e)) {
marci@379: 	  spec=1;
marci@379: 	  _G.graph->first(n, S_CLASS);
marci@379: 	  if (!_G.graph->valid(n)) { //Ha S ures
marci@379: 	    spec=2;
marci@379: 	    _G.graph->first(n, T_CLASS);
marci@379: 	    if (!_G.graph->valid(n)) { //Ha T ures
marci@379: 	      spec=3;
marci@379: 	    }
marci@379: 	  }
marci@379: 	}
marci@379:       }
marci@379:       operator Edge() const { return Edge(e, spec, n); }
marci@379:     };
marci@341:    
marci@379:     NodeIt& first(NodeIt& i) const { 
marci@379:       i=NodeIt(*this); return i;
marci@379:     }
marci@379:     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
marci@379:       i=OutEdgeIt(*this, p); return i;
marci@379:     }
marci@379:     InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
marci@379:       i=InEdgeIt(*this, p); return i;
marci@379:     }
marci@379:     EdgeIt& first(EdgeIt& i) const { 
marci@379:       i=EdgeIt(*this); return i;
marci@379:     }
marci@341: 
marci@379:     NodeIt& next(NodeIt& i) const { 
marci@379:       switch (i.spec) {
marci@379: 	case 0:
marci@389: 	  this->graph->next(i.n);
marci@389: 	  if (!this->graph->valid(i.n)) {
marci@379: 	    i.spec=1;
marci@379: 	  }
marci@379: 	  break;
marci@379: 	case 1:
marci@379: 	  i.spec=2;
marci@379: 	  break;
marci@379: 	case 2:
marci@379: 	  i.spec=3;
marci@379: 	  break;
marci@379:       }
marci@379:       return i; 
marci@379:     }
marci@379:     OutEdgeIt& next(OutEdgeIt& i) const { 
marci@393:       typename Graph::Node v;
marci@379:       switch (i.spec) {
marci@379: 	case 0: //normal edge
marci@409: 	  v=this->graph->aNode(i.e);
marci@389: 	  this->graph->next(i.e);
marci@389: 	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
marci@389: 	    if (this->graph->inSClass(v)) { //S, nincs kiel
marci@379: 	      i.spec=3;
marci@379: 	      i.n=INVALID;
marci@379: 	    } else { //T, van kiel
marci@379: 	      i.spec=2; 
marci@379: 	      i.n=v;
marci@379: 	    }
marci@379: 	  }
marci@379: 	  break;
marci@379: 	case 1: //s->vmi
marci@389: 	  this->graph->next(i.n);
marci@389: 	  if (!this->graph->valid(i.n)) i.spec=3;
marci@379: 	  break;
marci@379: 	case 2: //vmi->t
marci@379: 	  i.spec=3;
marci@379: 	  i.n=INVALID;
marci@379: 	  break;
marci@379:       }
marci@379:       return i; 
marci@379:     }
marci@379:     InEdgeIt& next(InEdgeIt& i) const { 
marci@393:       typename Graph::Node v;
marci@379:       switch (i.spec) {
marci@379: 	case 0: //normal edge
marci@393: 	  v=this->graph->aNode(i.e);
marci@389: 	  this->graph->next(i.e);
marci@389: 	  if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
marci@389: 	    if (this->graph->inTClass(v)) { //S, nincs beel
marci@379: 	      i.spec=3;
marci@379: 	      i.n=INVALID;
marci@379: 	    } else { //S, van beel
marci@379: 	      i.spec=1; 
marci@379: 	      i.n=v;
marci@379: 	    }
marci@379: 	  }
marci@379: 	  break;
marci@379: 	case 1: //s->vmi
marci@379: 	  i.spec=3;
marci@379: 	  i.n=INVALID;
marci@379: 	  break;
marci@379: 	case 2: //vmi->t
marci@389: 	  this->graph->next(i.n);
marci@389: 	  if (!this->graph->valid(i.n)) i.spec=3;
marci@379: 	  break;
marci@379:       }
marci@379:       return i; 
marci@379:     }
marci@341: 
marci@379:     EdgeIt& next(EdgeIt& i) const { 
marci@379:       switch (i.spec) {
marci@379: 	case 0:
marci@389: 	  this->graph->next(i.e);
marci@389: 	  if (!this->graph->valid(i.e)) { 
marci@379: 	    i.spec=1;
marci@389: 	    this->graph->first(i.n, S_CLASS);
marci@389: 	    if (!this->graph->valid(i.n)) {
marci@379: 	      i.spec=2;
marci@389: 	      this->graph->first(i.n, T_CLASS);
marci@389: 	      if (!this->graph->valid(i.n)) i.spec=3;
marci@379: 	    }
marci@379: 	  }
marci@379: 	  break;
marci@379: 	case 1:
marci@389: 	  this->graph->next(i.n);
marci@389: 	  if (!this->graph->valid(i.n)) {
marci@379: 	    i.spec=2;
marci@389: 	    this->graph->first(i.n, T_CLASS);
marci@389: 	    if (!this->graph->valid(i.n)) i.spec=3;
marci@379: 	  }
marci@379: 	  break;
marci@379: 	case 2:
marci@389: 	  this->graph->next(i.n);
marci@389: 	  if (!this->graph->valid(i.n)) i.spec=3;
marci@379: 	  break;
marci@379:       }
marci@379:       return i; 
marci@379:     }    
marci@341: 
marci@379:     Node tail(const Edge& e) const { 
marci@379:       switch (e.spec) {
marci@393:       case 0: 
marci@393: 	return Node(this->graph->tail(e));
marci@393: 	break;
marci@393:       case 1:
marci@393: 	return S_NODE;
marci@393: 	break;
marci@393:       case 2:
marci@393:       default:
marci@393: 	return Node(e.n);
marci@393: 	break;
marci@379:       }
marci@379:     }
marci@379:     Node head(const Edge& e) const { 
marci@379:       switch (e.spec) {
marci@393:       case 0: 
marci@393: 	return Node(this->graph->head(e));
marci@393: 	break;
marci@393:       case 1:
marci@393: 	return Node(e.n);
marci@393: 	break;
marci@393:       case 2:
marci@393:       default:
marci@393: 	return T_NODE;
marci@393: 	break;
marci@379:       }
marci@379:     }
marci@341: 
marci@379:     bool valid(const Node& n) const { return (n.spec<3); }
marci@379:     bool valid(const Edge& e) const { return (e.spec<3); }
marci@379: 
marci@409:     int nodeNum() const { return this->graph->nodeNum()+2; }
marci@409:     int edgeNum() const { 
marci@409:       return this->graph->edgeNum()+this->graph->nodeNum(); 
marci@409:     }
marci@341:   
marci@379:     Node aNode(const OutEdgeIt& e) const { return tail(e); }
marci@379:     Node aNode(const InEdgeIt& e) const { return head(e); }
marci@379:     Node bNode(const OutEdgeIt& e) const { return head(e); }
marci@379:     Node bNode(const InEdgeIt& e) const { return tail(e); }
marci@409: 
marci@409:     void addNode() const { }
marci@409:     void addEdge() const { }
marci@409:     
marci@389: //    Node addNode() const { return Node(this->graph->addNode()); }
marci@379: //    Edge addEdge(const Node& tail, const Node& head) const { 
marci@389: //      return Edge(this->graph->addEdge(tail, head)); }
marci@341: 
marci@389: //    void erase(const Node& i) const { this->graph->erase(i); }
marci@389: //    void erase(const Edge& i) const { this->graph->erase(i); }
marci@341:   
marci@389: //    void clear() const { this->graph->clear(); }
marci@341:     
marci@389:     template<typename T> class NodeMap : public GraphWrapper<Graph>::template NodeMap<T> { 
marci@389:       typedef typename GraphWrapper<Graph>::template NodeMap<T> Parent;
marci@510:     protected:
marci@379:       T s_value, t_value;
marci@379:     public:
marci@768:       NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) : 
marci@768: 	Parent(_G), 
marci@768: 	s_value(), 
marci@768: 	t_value() { }
marci@768:       NodeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, T a) 
marci@768: 	: Parent(_G, a), 
marci@768: 	  s_value(a), 
marci@768: 	  t_value(a) { }
marci@379:       T operator[](const Node& n) const { 
marci@379: 	switch (n.spec) {
marci@393: 	case 0: 
marci@393: 	  return Parent::operator[](n);
marci@393: 	case 1:
marci@393: 	  return s_value;
marci@393: 	case 2: 
marci@393: 	default:
marci@393: 	  return t_value;
marci@379: 	}
marci@379:       }
marci@379:       void set(const Node& n, T t) { 
marci@379: 	switch (n.spec) {
marci@393: 	case 0: 
marci@393: 	  GraphWrapper<Graph>::template NodeMap<T>::set(n, t);
marci@393: 	  break;
marci@393: 	case 1:
marci@393: 	  s_value=t;
marci@393: 	  break;
marci@393: 	case 2:
marci@393: 	default:
marci@393: 	  t_value=t;
marci@393: 	  break;
marci@379: 	}
marci@379:       }
marci@379:     };
marci@341: 
marci@510:     /// This class is to wrap a node-map of \c Graph and two variables 
marci@510:     /// storing values for \c S_NODE and \c T_NODE to a node-map of 
marci@768:     /// stGraphWrapper<Graph, sIterableMap, tIterableMap>.
marci@510:     template<typename NM> class NodeMapWrapper { 
marci@510:     public:
marci@510:       typedef Node KeyType;
marci@510:       typedef typename NM::ValueType ValueType;
marci@510:     protected:
marci@510:       NM* nm;
marci@510:       ValueType* s_value, t_value;
marci@510:     public:
marci@510:       NodeMapWrapper(NM& _nm, ValueType& _s_value, ValueType& _t_value) : 
marci@510: 	nm(&_nm), s_value(&_s_value), t_value(&_t_value) { }
marci@510:       ValueType operator[](const Node& n) const { 
marci@510: 	switch (n.getSpec()) {
marci@510: 	case 0: 
marci@510: 	  return (*nm)[n];
marci@510: 	case 1:
marci@510: 	  return *s_value;
marci@510: 	case 2: 
marci@510: 	default:
marci@510: 	  return *t_value;
marci@510: 	}
marci@510:       }
marci@510:       void set(const Node& n, ValueType t) { 
marci@510: 	switch (n.getSpec()) {
marci@510: 	case 0: 
marci@510: 	  nm->set(n, t);
marci@510: 	  break;
marci@510: 	case 1:
marci@510: 	  *s_value=t;
marci@510: 	  break;
marci@510: 	case 2:
marci@510: 	default:
marci@510: 	  *t_value=t;
marci@510: 	  break;
marci@510: 	}
marci@510:       }
marci@510:     };
marci@510: 
marci@510:     template<typename T> 
marci@510:     class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 
marci@510:       typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
marci@510:     protected:
marci@389:       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
marci@379:     public:
marci@768:       EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G) 
marci@768: 	: Parent(_G), 
marci@768: 	  node_value(_G) { }
marci@768:       EdgeMap(const stGraphWrapper<Graph, sIterableMap, tIterableMap>& _G, T a) 
marci@768: 	: Parent(_G, a), 
marci@768: 	  node_value(_G, a) { }
marci@379:       T operator[](const Edge& e) const { 
marci@379: 	switch (e.spec) {
marci@393: 	case 0: 
marci@393: 	  return Parent::operator[](e);
marci@393: 	case 1:
marci@393: 	  return node_value[e.n];
marci@393: 	case 2:
marci@393: 	default:
marci@393: 	  return node_value[e.n];
marci@379: 	}
marci@379:       }
marci@379:       void set(const Edge& e, T t) { 
marci@379: 	switch (e.spec) {
marci@393: 	case 0: 
marci@409: 	  Parent::set(e, t);
marci@393: 	  break;
marci@393: 	case 1:
marci@393: 	  node_value.set(e.n, t);
marci@393: 	  break;
marci@393: 	case 2:
marci@393: 	default:
marci@393: 	  node_value.set(e.n, t);
marci@393: 	  break;
marci@379: 	}
marci@379:       }
marci@379:     };
marci@409: 
marci@510:     /// This class is to wrap an edge-map and a node-map of \c Graph 
marci@768:     /// to an edge-map of stGraphWrapper<Graph, sIterableMap, tIterableMap>.
marci@510:     template<typename EM, typename NM> 
marci@510:     class EdgeMapWrapper {
marci@510:     public: 
marci@510:       typedef Edge KeyType;
marci@510:       typedef typename EM::ValueType ValueType;
marci@510:     protected:
marci@510:       EM* em;
marci@510:       NM* nm;
marci@510:     public:
marci@510:       EdgeMapWrapper(EM& _em, NM& _nm) : em(&_em), nm(&_nm) { }
marci@510:       ValueType operator[](const Edge& e) const { 
marci@510: 	switch (e.getSpec()) {
marci@510: 	case 0: 
marci@510: 	  return (*em)[e];
marci@510: 	case 1:
marci@510: 	  return (*nm)[e.getNode()];
marci@510: 	case 2:
marci@510: 	default:
marci@510: 	  return (*nm)[e.getNode()];
marci@510: 	}
marci@510:       }
marci@510:       void set(const Edge& e, ValueType t) { 
marci@510: 	switch (e.getSpec()) {
marci@510: 	case 0: 
marci@510: 	  em->set(e, t);
marci@510: 	  break;
marci@510: 	case 1:
marci@510: 	  nm->set(e.getNode(), t);
marci@510: 	  break;
marci@510: 	case 2:
marci@510: 	default:
marci@510: 	  nm->set(e.getNode(), t);
marci@510: 	  break;
marci@510: 	}
marci@510:       }
marci@510:     };
marci@510: 
marci@409: 
marci@435: //  template<typename G> 
marci@435:     friend std::ostream& 
marci@435:     operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Node& i) { 
marci@409:       os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; 
marci@409:       return os; 
marci@409:     }
marci@435: //  template<typename G> 
marci@435:     friend std::ostream& 
marci@435:     operator<<(std::ostream& os, const /*typename stGraphWrapper<Graph>::*/Edge& i) { 
marci@409:       os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << 
marci@409: 	" node: " << i.n << ")"; 
marci@409:       return os; 
marci@409:     }
marci@409: 
marci@379:   };
marci@379: 
alpar@406:   ///@}
marci@341: 
alpar@105: } //namespace hugo
marci@76: 
alpar@406: 
marci@510: #endif //HUGO_BIPARTITE_GRAPH_WRAPPER_H
marci@76: