diff -r 6114a8ab5d27 -r 7c463a7635d4 src/work/marci/graph_wrapper.h --- a/src/work/marci/graph_wrapper.h Fri Apr 30 13:52:17 2004 +0000 +++ b/src/work/marci/graph_wrapper.h Fri Apr 30 14:02:10 2004 +0000 @@ -933,747 +933,6 @@ } }; - /// A wrapper for composing a bipartite graph. - /// \c _graph have to be a reference to a graph of type \c Graph - /// and \c _s_false_t_true_map is an \c IterableBoolMap - /// reference containing the elements for the - /// color classes S and T. \c _graph is to be referred to an undirected - /// graph or a directed graph with edges oriented from S to T. - /// - ///\author Marton Makai - template - class BipartiteGraphWrapper : public GraphWrapper { - typedef IterableBoolMap< typename Graph::template NodeMap > - SFalseTTrueMap; - SFalseTTrueMap* s_false_t_true_map; - - public: - //marci - //FIXME vhogy igy kellene, csak az en forditom nem eszi meg - //static const bool S_CLASS=false; - //static const bool T_CLASS=true; - - bool S_CLASS; - bool T_CLASS; - - BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) - : GraphWrapper(_graph), s_false_t_true_map(&_s_false_t_true_map), - S_CLASS(false), T_CLASS(true) { } - typedef typename GraphWrapper::Node Node; - //using GraphWrapper::NodeIt; - typedef typename GraphWrapper::Edge Edge; - //using GraphWrapper::EdgeIt; - class ClassNodeIt; - friend class ClassNodeIt; - class OutEdgeIt; - friend class OutEdgeIt; - class InEdgeIt; - friend class InEdgeIt; - class ClassNodeIt { - friend class BipartiteGraphWrapper; - protected: - Node n; - public: - ClassNodeIt() { } - ClassNodeIt(const Invalid& i) : n(i) { } - ClassNodeIt(const BipartiteGraphWrapper& _G, bool _class) { - _G.s_false_t_true_map->first(n, _class); - } - //FIXME needed in new concept, important here - ClassNodeIt(const Node& _n) : n(_n) { } - operator Node() const { return n; } - }; -// class SNodeIt { -// Node n; -// public: -// SNodeIt() { } -// SNodeIt(const Invalid& i) : n(i) { } -// SNodeIt(const BipartiteGraphWrapper& _G) { -// _G.s_false_t_true_map->first(n, false); -// } -// operator Node() const { return n; } -// }; -// class TNodeIt { -// Node n; -// public: -// TNodeIt() { } -// TNodeIt(const Invalid& i) : n(i) { } -// TNodeIt(const BipartiteGraphWrapper& _G) { -// _G.s_false_t_true_map->first(n, true); -// } -// operator Node() const { return n; } -// }; - class OutEdgeIt { - friend class BipartiteGraphWrapper; - protected: - typename Graph::OutEdgeIt e; - public: - OutEdgeIt() { } - OutEdgeIt(const Invalid& i) : e(i) { } - OutEdgeIt(const BipartiteGraphWrapper& _G, const Node& _n) { - if (!(*(_G.s_false_t_true_map))[_n]) - e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n)); - else - e=INVALID; - } - operator Edge() const { return Edge(typename Graph::Edge(e)); } - }; - class InEdgeIt { - friend class BipartiteGraphWrapper; - protected: - typename Graph::InEdgeIt e; - public: - InEdgeIt() { } - InEdgeIt(const Invalid& i) : e(i) { } - InEdgeIt(const BipartiteGraphWrapper& _G, const Node& _n) { - if ((*(_G.s_false_t_true_map))[_n]) - e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n)); - else - e=INVALID; - } - operator Edge() const { return Edge(typename Graph::Edge(e)); } - }; - - using GraphWrapper::first; - ClassNodeIt& first(ClassNodeIt& n, bool _class) const { - n=ClassNodeIt(*this, _class) ; return n; } -// SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; } -// TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; } - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); return i; - } - InEdgeIt& first(InEdgeIt& i, const Node& p) const { - i=InEdgeIt(*this, p); return i; - } - - using GraphWrapper::next; - ClassNodeIt& next(ClassNodeIt& n) const { - this->s_false_t_true_map->next(n.n); return n; - } -// SNodeIt& next(SNodeIt& n) const { -// this->s_false_t_true_map->next(n); return n; -// } -// TNodeIt& next(TNodeIt& n) const { -// this->s_false_t_true_map->next(n); return n; -// } - OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; } - InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; } - - Node tail(const Edge& e) { - if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) - return Node(this->graph->tail(e)); - else - return Node(this->graph->head(e)); - } - Node head(const Edge& e) { - if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) - return Node(this->graph->head(e)); - else - return Node(this->graph->tail(e)); - } - - Node aNode(const OutEdgeIt& e) const { - return Node(this->graph->aNode(e.e)); - } - Node aNode(const InEdgeIt& e) const { - return Node(this->graph->aNode(e.e)); - } - Node bNode(const OutEdgeIt& e) const { - return Node(this->graph->bNode(e.e)); - } - Node bNode(const InEdgeIt& e) const { - return Node(this->graph->bNode(e.e)); - } - - bool inSClass(const Node& n) const { - return !(*(this->s_false_t_true_map))[n]; - } - bool inTClass(const Node& n) const { - return (*(this->s_false_t_true_map))[n]; - } - }; - - template - class stGraphWrapper; - -// template -// std::ostream& -// operator<<(std::ostream& os, const typename stGraphWrapper::Node& i) { -// os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; -// return os; -// } -// template -// std::ostream& -// operator<<(std::ostream& os, const typename stGraphWrapper::Edge& i) { -// os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << -// " node: " << i.n << ")"; -// return os; -// } - - /// experimentral, do not try it. - /// It eats a bipartite graph, oriented from S to T. - /// Such one can be made e.g. by the above wrapper. - /// - ///\author Marton Makai - template - class stGraphWrapper : public GraphWrapper { - public: - class Node; - friend class Node; -//GN, int -//0 normalis, 1 s, 2, true, ez az iteralasi sorrend, -//es a vege a false azaz (invalid, 3) - class NodeIt; - friend class NodeIt; -//GNI, int - class Edge; - friend class Edge; -//GE, int, GN -//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend, -//invalid: (invalid, 3, invalid) - class OutEdgeIt; - friend class OutEdgeIt; -//GO, int, GNI -//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid) -//s-bol (invalid, 1, first), ... (invalid, 3, invalid) -//t-bol (invalid, 3, invalid) - class InEdgeIt; - friend class InEdgeIt; -//GI, int, GNI -//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid) -//s-be (invalid, 3, invalid) -//t-be (invalid, 2, first), ... (invalid, 3, invalid) - class EdgeIt; - friend class EdgeIt; -//(first, 0, invalid) ... -//(invalid, 1, vmi) -//(invalid, 2, vmi) -//invalid, 3, invalid) - template class NodeMap; - template class EdgeMap; - -// template friend class NodeMap; -// template friend class EdgeMap; - - const Node S_NODE; - const Node T_NODE; - - static const bool S_CLASS=false; - static const bool T_CLASS=true; - - stGraphWrapper(Graph& _graph) : GraphWrapper(_graph) , - S_NODE(INVALID, 1), - T_NODE(INVALID, 2) { } - - -// std::ostream& -// operator<<(std::ostream& os, const /*typename stGraphWrapper::*/Node& i); -// friend std::ostream& -// operator<<(std::ostream& os, const /*typename stGraphWrapper::*/Node& i); -// friend std::ostream& -// operator<<(std::ostream& os, const /*typename stGraphWrapper::*/Edge& i); - - class Node : public Graph::Node { - protected: - friend class GraphWrapper; - friend class stGraphWrapper; - template friend class NodeMap; - friend class Edge; - friend class OutEdgeIt; - friend class InEdgeIt; - friend class EdgeIt; - int spec; - public: - Node() { } - Node(const typename Graph::Node& _n, int _spec=0) : - Graph::Node(_n), spec(_spec) { } - Node(const Invalid& i) : Graph::Node(i), spec(3) { } - friend bool operator==(const Node& u, const Node& v) { - return (u.spec==v.spec && - static_cast(u)== - static_cast(v)); - } - friend bool operator!=(const Node& u, const Node& v) { - return (v.spec!=u.spec || - static_cast(u)!= - static_cast(v)); - } -// template -// friend std::ostream& -// operator<<(std::ostream& os, const typename stGraphWrapper::Node& i); - friend std::ostream& operator<< (std::ostream& os, const Node& i); - int getSpec() const { return spec; } - }; - - class NodeIt { - friend class GraphWrapper; - friend class stGraphWrapper; - typename Graph::NodeIt n; - int spec; - public: - NodeIt() { } - NodeIt(const typename Graph::NodeIt& _n, int _spec) : - n(_n), spec(_spec) { } - NodeIt(const Invalid& i) : n(i), spec(3) { } - NodeIt(const stGraphWrapper& _G) : n(*(_G.graph)), spec(0) { - if (!_G.graph->valid(n)) spec=1; - } - operator Node() const { return Node(n, spec); } - }; - - class Edge : public Graph::Edge { - friend class GraphWrapper; - friend class stGraphWrapper; - template friend class EdgeMap; - int spec; - typename Graph::Node n; - public: - Edge() { } - Edge(const typename Graph::Edge& _e, int _spec, - const typename Graph::Node& _n) : - Graph::Edge(_e), spec(_spec), n(_n) { - } - Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { } - friend bool operator==(const Edge& u, const Edge& v) { - return (u.spec==v.spec && - static_cast(u)== - static_cast(v) && - u.n==v.n); - } - friend bool operator!=(const Edge& u, const Edge& v) { - return (v.spec!=u.spec || - static_cast(u)!= - static_cast(v) || - u.n!=v.n); - } -// template -// friend std::ostream& -// operator<<(std::ostream& os, const typename stGraphWrapper::Edge& i); - friend std::ostream& operator<< (std::ostream& os, const Edge& i); - int getSpec() const { return spec; } - }; - - class OutEdgeIt { - friend class GraphWrapper; - friend class stGraphWrapper; - typename Graph::OutEdgeIt e; - int spec; - typename Graph::ClassNodeIt n; - public: - OutEdgeIt() { } - OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec, - const typename Graph::ClassNodeIt& _n) : - e(_e), spec(_spec), n(_n) { - } - OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } - OutEdgeIt(const stGraphWrapper& _G, const Node& _n) { - switch (_n.spec) { - case 0 : - if (_G.graph->inSClass(_n)) { //S, van normalis kiel - e=typename Graph::OutEdgeIt(*(_G.graph), - typename Graph::Node(_n)); - spec=0; - n=INVALID; - if (!_G.graph->valid(e)) spec=3; - } else { //T, specko kiel van - e=INVALID; - spec=2; - n=_n; - } - break; - case 1: - e=INVALID; - spec=1; - _G.graph->first(n, S_CLASS); //s->vmi; - if (!_G.graph->valid(n)) spec=3; //Ha S ures - break; - case 2: - e=INVALID; - spec=3; - n=INVALID; - break; - } - } - operator Edge() const { return Edge(e, spec, n); } - }; - - class InEdgeIt { - friend class GraphWrapper; - friend class stGraphWrapper; - typename Graph::InEdgeIt e; - int spec; - typename Graph::ClassNodeIt n; - public: - InEdgeIt() { } - InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec, - const typename Graph::ClassNodeIt& _n) : - e(_e), spec(_spec), n(_n) { - } - InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } - InEdgeIt(const stGraphWrapper& _G, const Node& _n) { - switch (_n.spec) { - case 0 : - if (_G.graph->inTClass(_n)) { //T, van normalis beel - e=typename Graph::InEdgeIt(*(_G.graph), - typename Graph::Node(_n)); - spec=0; - n=INVALID; - if (!_G.graph->valid(e)) spec=3; - } else { //S, specko beel van - e=INVALID; - spec=1; - n=_n; - } - break; - case 1: - e=INVALID; - spec=3; - n=INVALID; - break; - case 2: - e=INVALID; - spec=2; - _G.graph->first(n, T_CLASS); //vmi->t; - if (!_G.graph->valid(n)) spec=3; //Ha T ures - break; - } - } - operator Edge() const { return Edge(e, spec, n); } - }; - - class EdgeIt { - friend class GraphWrapper; - friend class stGraphWrapper; - typename Graph::EdgeIt e; - int spec; - typename Graph::ClassNodeIt n; - public: - EdgeIt() { } - EdgeIt(const typename Graph::EdgeIt& _e, int _spec, - const typename Graph::ClassNodeIt& _n) : - e(_e), spec(_spec), n(_n) { } - EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { } - EdgeIt(const stGraphWrapper& _G) : - e(*(_G.graph)), spec(0), n(INVALID) { - if (!_G.graph->valid(e)) { - spec=1; - _G.graph->first(n, S_CLASS); - if (!_G.graph->valid(n)) { //Ha S ures - spec=2; - _G.graph->first(n, T_CLASS); - if (!_G.graph->valid(n)) { //Ha T ures - spec=3; - } - } - } - } - operator Edge() const { return Edge(e, spec, n); } - }; - - NodeIt& first(NodeIt& i) const { - i=NodeIt(*this); return i; - } - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); return i; - } - InEdgeIt& first(InEdgeIt& i, const Node& p) const { - i=InEdgeIt(*this, p); return i; - } - EdgeIt& first(EdgeIt& i) const { - i=EdgeIt(*this); return i; - } - - NodeIt& next(NodeIt& i) const { - switch (i.spec) { - case 0: - this->graph->next(i.n); - if (!this->graph->valid(i.n)) { - i.spec=1; - } - break; - case 1: - i.spec=2; - break; - case 2: - i.spec=3; - break; - } - return i; - } - OutEdgeIt& next(OutEdgeIt& i) const { - typename Graph::Node v; - switch (i.spec) { - case 0: //normal edge - v=this->graph->aNode(i.e); - this->graph->next(i.e); - if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk - if (this->graph->inSClass(v)) { //S, nincs kiel - i.spec=3; - i.n=INVALID; - } else { //T, van kiel - i.spec=2; - i.n=v; - } - } - break; - case 1: //s->vmi - this->graph->next(i.n); - if (!this->graph->valid(i.n)) i.spec=3; - break; - case 2: //vmi->t - i.spec=3; - i.n=INVALID; - break; - } - return i; - } - InEdgeIt& next(InEdgeIt& i) const { - typename Graph::Node v; - switch (i.spec) { - case 0: //normal edge - v=this->graph->aNode(i.e); - this->graph->next(i.e); - if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk - if (this->graph->inTClass(v)) { //S, nincs beel - i.spec=3; - i.n=INVALID; - } else { //S, van beel - i.spec=1; - i.n=v; - } - } - break; - case 1: //s->vmi - i.spec=3; - i.n=INVALID; - break; - case 2: //vmi->t - this->graph->next(i.n); - if (!this->graph->valid(i.n)) i.spec=3; - break; - } - return i; - } - - EdgeIt& next(EdgeIt& i) const { - switch (i.spec) { - case 0: - this->graph->next(i.e); - if (!this->graph->valid(i.e)) { - i.spec=1; - this->graph->first(i.n, S_CLASS); - if (!this->graph->valid(i.n)) { - i.spec=2; - this->graph->first(i.n, T_CLASS); - if (!this->graph->valid(i.n)) i.spec=3; - } - } - break; - case 1: - this->graph->next(i.n); - if (!this->graph->valid(i.n)) { - i.spec=2; - this->graph->first(i.n, T_CLASS); - if (!this->graph->valid(i.n)) i.spec=3; - } - break; - case 2: - this->graph->next(i.n); - if (!this->graph->valid(i.n)) i.spec=3; - break; - } - return i; - } - - Node tail(const Edge& e) const { - switch (e.spec) { - case 0: - return Node(this->graph->tail(e)); - break; - case 1: - return S_NODE; - break; - case 2: - default: - return Node(e.n); - break; - } - } - Node head(const Edge& e) const { - switch (e.spec) { - case 0: - return Node(this->graph->head(e)); - break; - case 1: - return Node(e.n); - break; - case 2: - default: - return T_NODE; - break; - } - } - - bool valid(const Node& n) const { return (n.spec<3); } - bool valid(const Edge& e) const { return (e.spec<3); } - - int nodeNum() const { return this->graph->nodeNum()+2; } - int edgeNum() const { - return this->graph->edgeNum()+this->graph->nodeNum(); - } - - Node aNode(const OutEdgeIt& e) const { return tail(e); } - Node aNode(const InEdgeIt& e) const { return head(e); } - Node bNode(const OutEdgeIt& e) const { return head(e); } - Node bNode(const InEdgeIt& e) const { return tail(e); } - - void addNode() const { } - void addEdge() const { } - -// Node addNode() const { return Node(this->graph->addNode()); } -// Edge addEdge(const Node& tail, const Node& head) const { -// return Edge(this->graph->addEdge(tail, head)); } - -// void erase(const Node& i) const { this->graph->erase(i); } -// void erase(const Edge& i) const { this->graph->erase(i); } - -// void clear() const { this->graph->clear(); } - - template class NodeMap : public GraphWrapper::template NodeMap { - typedef typename GraphWrapper::template NodeMap Parent; - T s_value, t_value; - public: - NodeMap(const stGraphWrapper& _G) : Parent(_G), - s_value(), - t_value() { } - NodeMap(const stGraphWrapper& _G, T a) : Parent(_G, a), - s_value(a), - t_value(a) { } - T operator[](const Node& n) const { - switch (n.spec) { - case 0: - return Parent::operator[](n); - break; - case 1: - return s_value; - break; - case 2: - default: - return t_value; - break; - } - } - void set(const Node& n, T t) { - switch (n.spec) { - case 0: - GraphWrapper::template NodeMap::set(n, t); - break; - case 1: - s_value=t; - break; - case 2: - default: - t_value=t; - break; - } - } - }; - - template::template EdgeMap > - class EdgeMap : public Parent { - //typedef typename GraphWrapper::template EdgeMap Parent; - typename GraphWrapper::template NodeMap node_value; - public: - EdgeMap(const stGraphWrapper& _G) : Parent(_G), - node_value(_G) { } - EdgeMap(const stGraphWrapper& _G, T a) : Parent(_G, a), - node_value(_G, a) { } - T operator[](const Edge& e) const { - switch (e.spec) { - case 0: - return Parent::operator[](e); - break; - case 1: - return node_value[e.n]; - break; - case 2: - default: - return node_value[e.n]; - break; - } - } - void set(const Edge& e, T t) { - switch (e.spec) { - case 0: - Parent::set(e, t); - break; - case 1: - node_value.set(e.n, t); - break; - case 2: - default: - node_value.set(e.n, t); - break; - } - } - }; - -// template class EdgeMap : public GraphWrapper::template EdgeMap { -// typedef typename GraphWrapper::template EdgeMap Parent; -// typename GraphWrapper::template NodeMap node_value; -// public: -// EdgeMap(const stGraphWrapper& _G) : Parent(_G), -// node_value(_G) { } -// EdgeMap(const stGraphWrapper& _G, T a) : Parent(_G, a), -// node_value(_G, a) { } -// T operator[](const Edge& e) const { -// switch (e.spec) { -// case 0: -// return Parent::operator[](e); -// break; -// case 1: -// return node_value[e.n]; -// break; -// case 2: -// default: -// return node_value[e.n]; -// break; -// } -// } -// void set(const Edge& e, T t) { -// switch (e.spec) { -// case 0: -// GraphWrapper::template EdgeMap::set(e, t); -// break; -// case 1: -// node_value.set(e.n, t); -// break; -// case 2: -// default: -// node_value.set(e.n, t); -// break; -// } -// } -// }; - -// template - friend std::ostream& - operator<<(std::ostream& os, const /*typename stGraphWrapper::*/Node& i) { - os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; - return os; - } -// template - friend std::ostream& - operator<<(std::ostream& os, const /*typename stGraphWrapper::*/Edge& i) { - os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << - " node: " << i.n << ")"; - return os; - } - - }; - ///@} } //namespace hugo