# HG changeset patch
# User marci
# Date 1085127345 0
# Node ID c3ad7c661a49bd51f74ede828ab0b26e27afa068
# Parent 4dfa1f79bf3e1e1297b160f06442bbfd213b751a
misc
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<typename Graph>
-// class BidirGraphWrapper : public GraphWrapper<Graph> {
-// public:
-// typedef GraphWrapper<Graph> Parent;
-// protected:
-// //const CapacityMap* capacity;
-// //FlowMap* flow;
+ template<typename Graph>
+ class OldBidirGraphWrapper : public GraphWrapper<Graph> {
+ public:
+ typedef GraphWrapper<Graph> Parent;
+ protected:
+ //const CapacityMap* capacity;
+ //FlowMap* flow;
-// BidirGraphWrapper() : GraphWrapper<Graph>()/*,
-// 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>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
-
-// class Edge;
-// class OutEdgeIt;
-// friend class Edge;
-// friend class OutEdgeIt;
-
-// //template<typename T> class NodeMap;
-// template<typename T> class EdgeMap;
-
-// typedef typename GraphWrapper<Graph>::Node Node;
-// typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
-
-// class Edge : public Graph::Edge {
-// friend class BidirGraphWrapper<Graph>;
-// ///\bug ez nem is kell
-// //template<typename T> friend class NodeMap;
-// template<typename T> 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<typename Graph::Edge>(u)==
-// static_cast<typename Graph::Edge>(v));
-// }
-// friend bool operator!=(const Edge& u, const Edge& v) {
-// return (v.backward!=u.backward ||
-// static_cast<typename Graph::Edge>(u)!=
-// static_cast<typename Graph::Edge>(v));
-// }
-// };
-
-// class OutEdgeIt {
-// friend class BidirGraphWrapper<Graph>;
-// 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<Graph>& _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<Graph>;
-// 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<Graph>& _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<Graph>;
-// protected:
-// typename Graph::EdgeIt e;
-// bool backward;
-// public:
-// EdgeIt() { }
-// EdgeIt(const Invalid& i) : e(i), backward(true) { }
-// EdgeIt(const BidirGraphWrapper<Graph>& _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<Graph>::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<Graph>()/*,
+ 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<Graph>::next;
-// // NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::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>(_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<typename T> class NodeMap;
+ template<typename T> class EdgeMap;
+
+ typedef typename GraphWrapper<Graph>::Node Node;
+ typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
+
+ class Edge : public Graph::Edge {
+ friend class OldBidirGraphWrapper<Graph>;
+ ///\bug ez nem is kell
+ //template<typename T> friend class NodeMap;
+ template<typename T> 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<typename Graph::Edge>(u)==
+ static_cast<typename Graph::Edge>(v));
+ }
+ friend bool operator!=(const Edge& u, const Edge& v) {
+ return (v.backward!=u.backward ||
+ static_cast<typename Graph::Edge>(u)!=
+ static_cast<typename Graph::Edge>(v));
+ }
+ };
+
+ class OutEdgeIt {
+ friend class OldBidirGraphWrapper<Graph>;
+ 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<Graph>& _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<Graph>;
+ 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<Graph>& _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<Graph>;
+ protected:
+ typename Graph::EdgeIt e;
+ bool backward;
+ public:
+ EdgeIt() { }
+ EdgeIt(const Invalid& i) : e(i), backward(true) { }
+ EdgeIt(const OldBidirGraphWrapper<Graph>& _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<Graph>::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<Graph>::next;
+// NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::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<Graph>::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<Graph>::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 <typename T>
+ class EdgeMap {
+ typename Graph::template EdgeMap<T> forward_map, backward_map;
+ public:
+ typedef T ValueType;
+ typedef Edge KeyType;
+ EdgeMap(const OldBidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
+ EdgeMap(const OldBidirGraphWrapper<Graph>& _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 <typename T>
-// class EdgeMap {
-// typename Graph::template EdgeMap<T> forward_map, backward_map;
-// public:
-// typedef T ValueType;
-// typedef Edge KeyType;
-// EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
-// EdgeMap(const BidirGraphWrapper<Graph>& _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<typename Graph, typename Number,
typename CapacityMap, typename FlowMap>
class ForwardFilter {
@@ -1392,7 +1385,6 @@
}
};
- /// An experiment for ResGraphWrapper.
template<typename Graph, typename Number,
typename CapacityMap, typename FlowMap>
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<typename Graph, typename Number,
typename CapacityMap, typename FlowMap>
- class ExpResGraphWrapper :
+ class ResGraphWrapper :
public SubBidirGraphWrapper<
Graph,
ForwardFilter<Graph, Number, CapacityMap, FlowMap>,
@@ -1428,7 +1422,7 @@
ForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
BackwardFilter<Graph, Number, CapacityMap, FlowMap> 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<typename Graph, typename Number,
-// typename CapacityMap, typename FlowMap>
-// class ExpResGraphWrapper :
-// public SubGraphWrapper< BidirGraphWrapper<Graph>,
-// ConstMap<typename BidirGraphWrapper<Graph>::Node,
-// bool>,
-// EdgeFilter< BidirGraphWrapper<Graph>,
-// CapacityMap, FlowMap> > {
-// public:
-// typedef SubGraphWrapper< BidirGraphWrapper<Graph>,
-// ConstMap<typename BidirGraphWrapper<Graph>::Node,
-// bool>,
-// EdgeFilter< BidirGraphWrapper<Graph>,
-// CapacityMap, FlowMap> > Parent;
-// protected:
-// const CapacityMap* capacity;
-// FlowMap* flow;
-// BidirGraphWrapper<Graph> bidir_graph;
-// ConstMap<typename BidirGraphWrapper<Graph>::Node, bool> node_filter;
-// EdgeFilter< BidirGraphWrapper<Graph>, 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<typename Graph, typename Number,
typename CapacityMap, typename FlowMap>
- class ResGraphWrapper : public GraphWrapper<Graph> {
+ class OldResGraphWrapper : public GraphWrapper<Graph> {
public:
typedef GraphWrapper<Graph> Parent;
protected:
const CapacityMap* capacity;
FlowMap* flow;
- ResGraphWrapper() : GraphWrapper<Graph>(0),
+ OldResGraphWrapper() : GraphWrapper<Graph>(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>(_graph), capacity(&_capacity), flow(&_flow) { }
@@ -1557,7 +1490,7 @@
typedef typename GraphWrapper<Graph>::Node Node;
typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
class Edge : public Graph::Edge {
- friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
+ friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
protected:
bool backward; //true, iff backward
// typename Graph::Edge e;
@@ -1580,7 +1513,7 @@
};
class OutEdgeIt {
- friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
+ friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
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<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
+ OutEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _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<Graph, Number, CapacityMap, FlowMap>;
+ friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
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<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
+ InEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _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<Graph, Number, CapacityMap, FlowMap>;
+ friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
protected:
typename Graph::EdgeIt e;
bool backward;
public:
EdgeIt() { }
EdgeIt(const Invalid& i) : e(i), backward(true) { }
- EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
+ EdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _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<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
- EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
+ EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
+ EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _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);
diff -r 4dfa1f79bf3e -r c3ad7c661a49 src/work/jacint/max_flow.h
--- a/src/work/jacint/max_flow.h Thu May 20 17:21:55 2004 +0000
+++ b/src/work/jacint/max_flow.h Fri May 21 08:15:45 2004 +0000
@@ -63,8 +63,8 @@
const CapMap* capacity;
FlowMap* flow;
int n; //the number of nodes of G
- // typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
- typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
+ typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
+ //typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
typedef typename ResGW::Edge ResGWEdge;
//typedef typename ResGW::template NodeMap<bool> ReachedMap;