diff -r 2d50d1f045c5 -r 51dcd224455c src/hugo/graph_wrapper.h --- a/src/hugo/graph_wrapper.h Mon Sep 13 15:30:01 2004 +0000 +++ b/src/hugo/graph_wrapper.h Mon Sep 13 16:15:12 2004 +0000 @@ -331,9 +331,12 @@ /// A graph wrapper for hiding nodes and edges from a graph. /// This wrapper shows a graph with filtered node-set and - /// edge-set. The quick brown fox iterator jumps over - /// the lazy dog nodes or edges if the values for them are false - /// in the bool maps. + /// edge-set. Given a bool-valued map on the node-set and one on + /// the edge-set of the graphs, the iterators shows only the objects + /// having true value. + /// The quick brown fox iterators jump over + /// the lazy dog nodes or edges if their values for are false in the + /// corresponding bool maps. /// ///\author Marton Makai template class UndirGraphWrapper : public GraphWrapper { public: @@ -1118,324 +1122,6 @@ }; - - // this is a direct implementation of the bidirected-graph wrapper. - // in early hugo, it was implemented that way. - template - class OldBidirGraphWrapper : public GraphWrapper { - public: - typedef GraphWrapper Parent; - protected: - OldBidirGraphWrapper() : GraphWrapper() { } - - public: - - OldBidirGraphWrapper(Graph& _graph) : - GraphWrapper(_graph) { } - - class Edge; - class OutEdgeIt; - friend class Edge; - friend class OutEdgeIt; - - //template class NodeMap; - template class EdgeMap; - - typedef typename GraphWrapper::Node Node; - typedef typename GraphWrapper::NodeIt NodeIt; - - class Edge : public Graph::Edge { - friend class OldBidirGraphWrapper; - ///\bug ez nem is kell - //template friend class NodeMap; - template friend class EdgeMap; - protected: - bool backward; //true, iff backward -// typename Graph::Edge e; - public: - Edge() { } - ///\bug =false kell-e? zsoltnak kell az addEdge miatt - Edge(const typename Graph::Edge& _e, bool _backward=false) : - Graph::Edge(_e), backward(_backward) { } - Edge(const Invalid& i) : Graph::Edge(i), backward(true) { } -//the unique invalid iterator - friend bool operator==(const Edge& u, const Edge& v) { - return (v.backward==u.backward && - static_cast(u)== - static_cast(v)); - } - friend bool operator!=(const Edge& u, const Edge& v) { - return (v.backward!=u.backward || - static_cast(u)!= - static_cast(v)); - } - }; - - class OutEdgeIt { - friend class OldBidirGraphWrapper; - protected: - typename Graph::OutEdgeIt out; - typename Graph::InEdgeIt in; - bool backward; - public: - OutEdgeIt() { } - //FIXME -// OutEdgeIt(const Edge& e) : Edge(e) { } - OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } -//the unique invalid iterator - OutEdgeIt(const OldBidirGraphWrapper& _G, Node v) { - backward=false; - _G.graph->first(out, v); - while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); } - if (!_G.graph->valid(out)) { - backward=true; - _G.graph->first(in, v); - while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); } - } - } - operator Edge() const { -// Edge e; -// e.forward=this->forward; -// if (this->forward) e=out; else e=in; -// return e; - if (this->backward) - return Edge(in, this->backward); - else - return Edge(out, this->backward); - } - }; - - class InEdgeIt { - friend class OldBidirGraphWrapper; - protected: - typename Graph::OutEdgeIt out; - typename Graph::InEdgeIt in; - bool backward; - public: - InEdgeIt() { } - //FIXME -// OutEdgeIt(const Edge& e) : Edge(e) { } - InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } -//the unique invalid iterator - InEdgeIt(const OldBidirGraphWrapper& _G, Node v) { - backward=false; - _G.graph->first(in, v); - while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); } - if (!_G.graph->valid(in)) { - backward=true; - _G.graph->first(out, v); - while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); } - } - } - operator Edge() const { -// Edge e; -// e.forward=this->forward; -// if (this->forward) e=out; else e=in; -// return e; - if (this->backward) - return Edge(out, this->backward); - else - return Edge(in, this->backward); - } - }; - - class EdgeIt { - friend class OldBidirGraphWrapper; - protected: - typename Graph::EdgeIt e; - bool backward; - public: - EdgeIt() { } - EdgeIt(const Invalid& i) : e(i), backward(true) { } - EdgeIt(const OldBidirGraphWrapper& _G) { - backward=false; - _G.graph->first(e); - while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e); - if (!_G.graph->valid(e)) { - backward=true; - _G.graph->first(e); - while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e); - } - } - operator Edge() const { - return Edge(e, this->backward); - } - }; - - using GraphWrapper::first; -// NodeIt& first(NodeIt& i) const { -// i=NodeIt(*this); return i; -// } - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); return i; - } -// FIXME not tested - InEdgeIt& first(InEdgeIt& i, const Node& p) const { - i=InEdgeIt(*this, p); return i; - } - EdgeIt& first(EdgeIt& i) const { - i=EdgeIt(*this); return i; - } - - using GraphWrapper::next; -// NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); return n; } - OutEdgeIt& next(OutEdgeIt& e) const { - if (!e.backward) { - Node v=this->graph->aNode(e.out); - this->graph->next(e.out); - while(this->graph->valid(e.out) && !enabled(e)) { - this->graph->next(e.out); } - if (!this->graph->valid(e.out)) { - e.backward=true; - this->graph->first(e.in, v); - while(this->graph->valid(e.in) && !enabled(e)) { - this->graph->next(e.in); } - } - } else { - this->graph->next(e.in); - while(this->graph->valid(e.in) && !enabled(e)) { - this->graph->next(e.in); } - } - return e; - } -// FIXME Not tested - InEdgeIt& next(InEdgeIt& e) const { - if (!e.backward) { - Node v=this->graph->aNode(e.in); - this->graph->next(e.in); - while(this->graph->valid(e.in) && !enabled(e)) { - this->graph->next(e.in); } - if (!this->graph->valid(e.in)) { - e.backward=true; - this->graph->first(e.out, v); - while(this->graph->valid(e.out) && !enabled(e)) { - this->graph->next(e.out); } - } - } else { - this->graph->next(e.out); - while(this->graph->valid(e.out) && !enabled(e)) { - this->graph->next(e.out); } - } - return e; - } - EdgeIt& next(EdgeIt& e) const { - if (!e.backward) { - this->graph->next(e.e); - while(this->graph->valid(e.e) && !enabled(e)) { - this->graph->next(e.e); } - if (!this->graph->valid(e.e)) { - e.backward=true; - this->graph->first(e.e); - while(this->graph->valid(e.e) && !enabled(e)) { - this->graph->next(e.e); } - } - } else { - this->graph->next(e.e); - while(this->graph->valid(e.e) && !enabled(e)) { - this->graph->next(e.e); } - } - return e; - } - - Node tail(Edge e) const { - return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } - Node head(Edge e) const { - return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } - - Node aNode(OutEdgeIt e) const { - return ((!e.backward) ? this->graph->aNode(e.out) : - this->graph->aNode(e.in)); } - Node bNode(OutEdgeIt e) const { - return ((!e.backward) ? this->graph->bNode(e.out) : - this->graph->bNode(e.in)); } - - Node aNode(InEdgeIt e) const { - return ((!e.backward) ? this->graph->aNode(e.in) : - this->graph->aNode(e.out)); } - Node bNode(InEdgeIt e) const { - return ((!e.backward) ? this->graph->bNode(e.in) : - this->graph->bNode(e.out)); } - - /// Gives back the opposite edge. - Edge opposite(const Edge& e) const { - Edge f=e; - f.backward=!f.backward; - return f; - } - -// int nodeNum() const { return graph->nodeNum(); } - //FIXME - void edgeNum() const { } - //int edgeNum() const { return graph->edgeNum(); } - - -// int id(Node v) const { return graph->id(v); } - - bool valid(Node n) const { return GraphWrapper::valid(n); } - bool valid(Edge e) const { - return this->graph->valid(e); - //return e.forward ? graph->valid(e.out) : graph->valid(e.in); - } - - bool forward(const Edge& e) const { return !e.backward; } - bool backward(const Edge& e) const { return e.backward; } - - bool enabled(const Edge& e) const { - if (!e.backward) -// return (capacity->get(e.out)-flow->get(e.out)); - //return ((*capacity)[e]-(*flow)[e]); - return true; - else -// return (flow->get(e.in)); - //return ((*flow)[e]); - return true; - } - -// Number enabled(typename Graph::OutEdgeIt out) const { -// // return (capacity->get(out)-flow->get(out)); -// return ((*capacity)[out]-(*flow)[out]); -// } - -// Number enabled(typename Graph::InEdgeIt in) const { -// // return (flow->get(in)); -// return ((*flow)[in]); -// } - - template - class EdgeMap { - typename Graph::template EdgeMap forward_map, backward_map; - public: - typedef T ValueType; - typedef Edge KeyType; - EdgeMap(const OldBidirGraphWrapper& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } - EdgeMap(const OldBidirGraphWrapper& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } - void set(Edge e, T a) { - if (!e.backward) - forward_map.set(e/*.out*/, a); - else - backward_map.set(e/*.in*/, a); - } - T operator[](Edge e) const { - if (!e.backward) - return forward_map[e/*.out*/]; - else - return backward_map[e/*.in*/]; - } - void update() { - forward_map.update(); - backward_map.update(); - } -// T get(Edge e) const { -// if (e.out_or_in) -// return forward_map.get(e.out); -// else -// return backward_map.get(e.in); -// } - }; - }; - - - /// \brief A bidirected graph template. /// /// A bidirected graph template. @@ -1598,325 +1284,6 @@ }; - template - class OldResGraphWrapper : public GraphWrapper { - public: - typedef GraphWrapper Parent; - protected: - const CapacityMap* capacity; - FlowMap* flow; - - OldResGraphWrapper() : GraphWrapper(0), - capacity(0), flow(0) { } - void setCapacityMap(const CapacityMap& _capacity) { - capacity=&_capacity; - } - void setFlowMap(FlowMap& _flow) { - flow=&_flow; - } - - public: - - OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, - FlowMap& _flow) : - GraphWrapper(_graph), capacity(&_capacity), flow(&_flow) { } - - class Edge; - class OutEdgeIt; - friend class Edge; - friend class OutEdgeIt; - - typedef typename GraphWrapper::Node Node; - typedef typename GraphWrapper::NodeIt NodeIt; - class Edge : public Graph::Edge { - friend class OldResGraphWrapper; - protected: - bool backward; //true, iff backward -// typename Graph::Edge e; - public: - Edge() { } - Edge(const typename Graph::Edge& _e, bool _backward) : - Graph::Edge(_e), backward(_backward) { } - Edge(const Invalid& i) : Graph::Edge(i), backward(true) { } -//the unique invalid iterator - friend bool operator==(const Edge& u, const Edge& v) { - return (v.backward==u.backward && - static_cast(u)== - static_cast(v)); - } - friend bool operator!=(const Edge& u, const Edge& v) { - return (v.backward!=u.backward || - static_cast(u)!= - static_cast(v)); - } - }; - - class OutEdgeIt { - friend class OldResGraphWrapper; - protected: - typename Graph::OutEdgeIt out; - typename Graph::InEdgeIt in; - bool backward; - public: - OutEdgeIt() { } - //FIXME -// OutEdgeIt(const Edge& e) : Edge(e) { } - OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } -//the unique invalid iterator - OutEdgeIt(const OldResGraphWrapper& _G, Node v) { - backward=false; - _G.graph->first(out, v); - while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); } - if (!_G.graph->valid(out)) { - backward=true; - _G.graph->first(in, v); - while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); } - } - } - operator Edge() const { -// Edge e; -// e.forward=this->forward; -// if (this->forward) e=out; else e=in; -// return e; - if (this->backward) - return Edge(in, this->backward); - else - return Edge(out, this->backward); - } - }; - - class InEdgeIt { - friend class OldResGraphWrapper; - protected: - typename Graph::OutEdgeIt out; - typename Graph::InEdgeIt in; - bool backward; - public: - InEdgeIt() { } - //FIXME -// OutEdgeIt(const Edge& e) : Edge(e) { } - InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } -//the unique invalid iterator - InEdgeIt(const OldResGraphWrapper& _G, Node v) { - backward=false; - _G.graph->first(in, v); - while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); } - if (!_G.graph->valid(in)) { - backward=true; - _G.graph->first(out, v); - while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); } - } - } - operator Edge() const { -// Edge e; -// e.forward=this->forward; -// if (this->forward) e=out; else e=in; -// return e; - if (this->backward) - return Edge(out, this->backward); - else - return Edge(in, this->backward); - } - }; - - class EdgeIt { - friend class OldResGraphWrapper; - protected: - typename Graph::EdgeIt e; - bool backward; - public: - EdgeIt() { } - EdgeIt(const Invalid& i) : e(i), backward(true) { } - EdgeIt(const OldResGraphWrapper& _G) { - backward=false; - _G.graph->first(e); - while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e); - if (!_G.graph->valid(e)) { - backward=true; - _G.graph->first(e); - while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e); - } - } - operator Edge() const { - return Edge(e, this->backward); - } - }; - - using GraphWrapper::first; -// NodeIt& first(NodeIt& i) const { -// i=NodeIt(*this); return i; -// } - OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { - i=OutEdgeIt(*this, p); return i; - } -// FIXME not tested - InEdgeIt& first(InEdgeIt& i, const Node& p) const { - i=InEdgeIt(*this, p); return i; - } - EdgeIt& first(EdgeIt& i) const { - i=EdgeIt(*this); return i; - } - - using GraphWrapper::next; -// NodeIt& next(NodeIt& n) const { GraphWrapper::next(n); return n; } - OutEdgeIt& next(OutEdgeIt& e) const { - if (!e.backward) { - Node v=this->graph->aNode(e.out); - this->graph->next(e.out); - while( this->graph->valid(e.out) && !(resCap(e)>0) ) { - this->graph->next(e.out); } - if (!this->graph->valid(e.out)) { - e.backward=true; - this->graph->first(e.in, v); - while( this->graph->valid(e.in) && !(resCap(e)>0) ) { - this->graph->next(e.in); } - } - } else { - this->graph->next(e.in); - while( this->graph->valid(e.in) && !(resCap(e)>0) ) { - this->graph->next(e.in); } - } - return e; - } -// FIXME Not tested - InEdgeIt& next(InEdgeIt& e) const { - if (!e.backward) { - Node v=this->graph->aNode(e.in); - this->graph->next(e.in); - while( this->graph->valid(e.in) && !(resCap(e)>0) ) { - this->graph->next(e.in); } - if (!this->graph->valid(e.in)) { - e.backward=true; - this->graph->first(e.out, v); - while( this->graph->valid(e.out) && !(resCap(e)>0) ) { - this->graph->next(e.out); } - } - } else { - this->graph->next(e.out); - while( this->graph->valid(e.out) && !(resCap(e)>0) ) { - this->graph->next(e.out); } - } - return e; - } - EdgeIt& next(EdgeIt& e) const { - if (!e.backward) { - this->graph->next(e.e); - while( this->graph->valid(e.e) && !(resCap(e)>0) ) { - this->graph->next(e.e); } - if (!this->graph->valid(e.e)) { - e.backward=true; - this->graph->first(e.e); - while( this->graph->valid(e.e) && !(resCap(e)>0) ) { - this->graph->next(e.e); } - } - } else { - this->graph->next(e.e); - while( this->graph->valid(e.e) && !(resCap(e)>0) ) { - this->graph->next(e.e); } - } - return e; - } - - Node tail(Edge e) const { - return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); } - Node head(Edge e) const { - return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); } - - Node aNode(OutEdgeIt e) const { - return ((!e.backward) ? this->graph->aNode(e.out) : - this->graph->aNode(e.in)); } - Node bNode(OutEdgeIt e) const { - return ((!e.backward) ? this->graph->bNode(e.out) : - this->graph->bNode(e.in)); } - - Node aNode(InEdgeIt e) const { - return ((!e.backward) ? this->graph->aNode(e.in) : - this->graph->aNode(e.out)); } - Node bNode(InEdgeIt e) const { - return ((!e.backward) ? this->graph->bNode(e.in) : - this->graph->bNode(e.out)); } - -// int nodeNum() const { return graph->nodeNum(); } - //FIXME - void edgeNum() const { } - //int edgeNum() const { return graph->edgeNum(); } - - -// int id(Node v) const { return graph->id(v); } - - bool valid(Node n) const { return GraphWrapper::valid(n); } - bool valid(Edge e) const { - return this->graph->valid(e); - //return e.forward ? graph->valid(e.out) : graph->valid(e.in); - } - - bool forward(const Edge& e) const { return !e.backward; } - bool backward(const Edge& e) const { return e.backward; } - - void augment(const Edge& e, Number a) const { - if (!e.backward) -// flow->set(e.out, flow->get(e.out)+a); - flow->set(e, (*flow)[e]+a); - else -// flow->set(e.in, flow->get(e.in)-a); - flow->set(e, (*flow)[e]-a); - } - - Number resCap(const Edge& e) const { - if (!e.backward) -// return (capacity->get(e.out)-flow->get(e.out)); - return ((*capacity)[e]-(*flow)[e]); - else -// return (flow->get(e.in)); - return ((*flow)[e]); - } - -// Number resCap(typename Graph::OutEdgeIt out) const { -// // return (capacity->get(out)-flow->get(out)); -// return ((*capacity)[out]-(*flow)[out]); -// } - -// Number resCap(typename Graph::InEdgeIt in) const { -// // return (flow->get(in)); -// return ((*flow)[in]); -// } - - template - class EdgeMap { - typename Graph::template EdgeMap forward_map, backward_map; - public: - typedef T ValueType; - typedef Edge KeyType; - EdgeMap(const OldResGraphWrapper& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } - EdgeMap(const OldResGraphWrapper& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } - void set(Edge e, T a) { - if (!e.backward) - forward_map.set(e/*.out*/, a); - else - backward_map.set(e/*.in*/, a); - } - T operator[](Edge e) const { - if (!e.backward) - return forward_map[e/*.out*/]; - else - return backward_map[e/*.in*/]; - } - void update() { - forward_map.update(); - backward_map.update(); - } -// T get(Edge e) const { -// if (e.out_or_in) -// return forward_map.get(e.out); -// else -// return backward_map.get(e.in); -// } - }; - }; - - - /// For blocking flows. /// This graph wrapper is used for on-the-fly