diff -r 4dfa1f79bf3e -r c3ad7c661a49 src/hugo/graph_wrapper.h --- a/src/hugo/graph_wrapper.h Thu May 20 17:21:55 2004 +0000 +++ b/src/hugo/graph_wrapper.h Fri May 21 08:15:45 2004 +0000 @@ -1012,346 +1012,340 @@ -// ///\brief A wrapper for composing bidirected graph from a directed one. -// /// experimental, for fezso's sake. -// /// -// /// A wrapper for composing bidirected graph from a directed one. -// /// experimental, for fezso's sake. -// /// A bidirected graph is composed over the directed one without physical -// /// storage. As the oppositely directed edges are logically different ones -// /// the maps are able to attach different values for them. -// template -// class BidirGraphWrapper : public GraphWrapper { -// public: -// typedef GraphWrapper Parent; -// protected: -// //const CapacityMap* capacity; -// //FlowMap* flow; + template + class OldBidirGraphWrapper : public GraphWrapper { + public: + typedef GraphWrapper Parent; + protected: + //const CapacityMap* capacity; + //FlowMap* flow; -// BidirGraphWrapper() : GraphWrapper()/*, -// capacity(0), flow(0)*/ { } -// // void setCapacityMap(const CapacityMap& _capacity) { -// // capacity=&_capacity; -// // } -// // void setFlowMap(FlowMap& _flow) { -// // flow=&_flow; -// // } - -// public: - -// BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, -// FlowMap& _flow*/) : -// GraphWrapper(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { } - -// 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 BidirGraphWrapper; -// ///\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 BidirGraphWrapper; -// 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 BidirGraphWrapper& _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 BidirGraphWrapper; -// 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 BidirGraphWrapper& _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 BidirGraphWrapper; -// protected: -// typename Graph::EdgeIt e; -// bool backward; -// public: -// EdgeIt() { } -// EdgeIt(const Invalid& i) : e(i), backward(true) { } -// EdgeIt(const BidirGraphWrapper& _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; + OldBidirGraphWrapper() : GraphWrapper()/*, + capacity(0), flow(0)*/ { } +// void setCapacityMap(const CapacityMap& _capacity) { +// capacity=&_capacity; // } -// // 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; +// void setFlowMap(FlowMap& _flow) { +// flow=&_flow; // } -// 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)); } + public: -// 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)); } + OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, + FlowMap& _flow*/) : + GraphWrapper(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { } -// 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)); } + class Edge; + class OutEdgeIt; + friend class Edge; + friend class OutEdgeIt; -// /// Gives back the opposite edge. -// Edge opposite(const Edge& e) const { -// Edge f=e; -// f.backward=!f.backward; -// return f; + //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; } + +// 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); // } -// // int nodeNum() const { return graph->nodeNum(); } -// //FIXME -// void edgeNum() const { } -// //int edgeNum() const { return graph->edgeNum(); } + 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; + } - -// // 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); +// 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]); // } -// bool forward(const Edge& e) const { return !e.backward; } -// bool backward(const Edge& e) const { return e.backward; } + 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); +// } + }; + }; -// // 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); -// // } -// 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 BidirGraphWrapper& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } -// EdgeMap(const BidirGraphWrapper& _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. /// @@ -1376,7 +1370,6 @@ - /// An experiment for ResGraphWrapper. template class ForwardFilter { @@ -1392,7 +1385,6 @@ } }; - /// An experiment for ResGraphWrapper. template class BackwardFilter { @@ -1408,11 +1400,13 @@ } }; + + /// A wrapper for composing the residual graph for directed flow and circulation problems. - /// An experiment for ResGraphWrapper. + /// A wrapper for composing the residual graph for directed flow and circulation problems. template - class ExpResGraphWrapper : + class ResGraphWrapper : public SubBidirGraphWrapper< Graph, ForwardFilter, @@ -1428,7 +1422,7 @@ ForwardFilter forward_filter; BackwardFilter backward_filter; public: - ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, + ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, FlowMap& _flow) : Parent(), capacity(&_capacity), flow(&_flow), forward_filter(_graph, _capacity, _flow), @@ -1464,77 +1458,16 @@ -// /// An experiment for ResGraphWrapper. -// template -// class ExpResGraphWrapper : -// public SubGraphWrapper< BidirGraphWrapper, -// ConstMap::Node, -// bool>, -// EdgeFilter< BidirGraphWrapper, -// CapacityMap, FlowMap> > { -// public: -// typedef SubGraphWrapper< BidirGraphWrapper, -// ConstMap::Node, -// bool>, -// EdgeFilter< BidirGraphWrapper, -// CapacityMap, FlowMap> > Parent; -// protected: -// const CapacityMap* capacity; -// FlowMap* flow; -// BidirGraphWrapper bidir_graph; -// ConstMap::Node, bool> node_filter; -// EdgeFilter< BidirGraphWrapper, CapacityMap, FlowMap> edge_filter; -// public: -// ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, -// FlowMap& _flow) : -// Parent(), capacity(&_capacity), flow(&_flow), -// bidir_graph(_graph), -// node_filter(true), -// edge_filter(bidir_graph, *capacity, *flow) { -// Parent::setGraph(bidir_graph); -// Parent::setNodeFilterMap(node_filter); -// Parent::setEdgeFilterMap(edge_filter); -// } - -// // bool forward(const Parent::Edge& e) const { return Parent::forward(e); } -// //bool backward(const Edge& e) const { return e.backward; } - -// void augment(const typename Parent::Edge& e, Number a) const { -// if (Parent::forward(e)) -// // 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 typename Parent::Edge& e) const { -// if (Parent::forward(e)) -// // return (capacity->get(e.out)-flow->get(e.out)); -// return ((*capacity)[e]-(*flow)[e]); -// else -// // return (flow->get(e.in)); -// return ((*flow)[e]); -// } - -// }; - - - - /// A wrapper for composing the residual graph for directed flow and circulation problems. - - /// A wrapper for composing the residual graph for directed flow and circulation problems. template - class ResGraphWrapper : public GraphWrapper { + class OldResGraphWrapper : public GraphWrapper { public: typedef GraphWrapper Parent; protected: const CapacityMap* capacity; FlowMap* flow; - ResGraphWrapper() : GraphWrapper(0), + OldResGraphWrapper() : GraphWrapper(0), capacity(0), flow(0) { } void setCapacityMap(const CapacityMap& _capacity) { capacity=&_capacity; @@ -1545,7 +1478,7 @@ public: - ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, + OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, FlowMap& _flow) : GraphWrapper(_graph), capacity(&_capacity), flow(&_flow) { } @@ -1557,7 +1490,7 @@ typedef typename GraphWrapper::Node Node; typedef typename GraphWrapper::NodeIt NodeIt; class Edge : public Graph::Edge { - friend class ResGraphWrapper; + friend class OldResGraphWrapper; protected: bool backward; //true, iff backward // typename Graph::Edge e; @@ -1580,7 +1513,7 @@ }; class OutEdgeIt { - friend class ResGraphWrapper; + friend class OldResGraphWrapper; protected: typename Graph::OutEdgeIt out; typename Graph::InEdgeIt in; @@ -1591,7 +1524,7 @@ // OutEdgeIt(const Edge& e) : Edge(e) { } OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } //the unique invalid iterator - OutEdgeIt(const ResGraphWrapper& _G, Node v) { + 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); } @@ -1614,7 +1547,7 @@ }; class InEdgeIt { - friend class ResGraphWrapper; + friend class OldResGraphWrapper; protected: typename Graph::OutEdgeIt out; typename Graph::InEdgeIt in; @@ -1625,7 +1558,7 @@ // OutEdgeIt(const Edge& e) : Edge(e) { } InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { } //the unique invalid iterator - InEdgeIt(const ResGraphWrapper& _G, Node v) { + 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); } @@ -1648,14 +1581,14 @@ }; class EdgeIt { - friend class ResGraphWrapper; + friend class OldResGraphWrapper; protected: typename Graph::EdgeIt e; bool backward; public: EdgeIt() { } EdgeIt(const Invalid& i) : e(i), backward(true) { } - EdgeIt(const ResGraphWrapper& _G) { + EdgeIt(const OldResGraphWrapper& _G) { backward=false; _G.graph->first(e); while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e); @@ -1815,8 +1748,8 @@ public: typedef T ValueType; typedef Edge KeyType; - EdgeMap(const ResGraphWrapper& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } - EdgeMap(const ResGraphWrapper& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } + 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);