1.1 --- a/src/work/bfs_iterator.hh Tue Mar 02 20:40:39 2004 +0000
1.2 +++ b/src/work/bfs_iterator.hh Wed Mar 03 14:30:38 2004 +0000
1.3 @@ -544,7 +544,7 @@
1.4
1.5
1.6 template <typename Graph, typename OutEdgeIt,
1.7 - typename ReachedMap=typename Graph::NodeMap<bool> >
1.8 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.9 class BfsIterator4 {
1.10 typedef typename Graph::NodeIt NodeIt;
1.11 const Graph& G;
1.12 @@ -566,7 +566,7 @@
1.13 if (bfs_queue.empty()) {
1.14 bfs_queue.push(s);
1.15 G.getFirst(actual_edge, s);
1.16 - if (actual_edge.valid()) {
1.17 + if (G.valid(actual_edge)/*.valid()*/) {
1.18 NodeIt w=G.bNode(actual_edge);
1.19 if (!reached.get(w)) {
1.20 bfs_queue.push(w);
1.21 @@ -582,9 +582,9 @@
1.22 }
1.23 BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
1.24 operator++() {
1.25 - if (actual_edge.valid()) {
1.26 - ++actual_edge;
1.27 - if (actual_edge.valid()) {
1.28 + if (G.valid(actual_edge)/*.valid()*/) {
1.29 + /*++*/G.next(actual_edge);
1.30 + if (G.valid(actual_edge)/*.valid()*/) {
1.31 NodeIt w=G.bNode(actual_edge);
1.32 if (!reached.get(w)) {
1.33 bfs_queue.push(w);
1.34 @@ -598,7 +598,7 @@
1.35 bfs_queue.pop();
1.36 if (!bfs_queue.empty()) {
1.37 G.getFirst(actual_edge, bfs_queue.front());
1.38 - if (actual_edge.valid()) {
1.39 + if (G.valid(actual_edge)/*.valid()*/) {
1.40 NodeIt w=G.bNode(actual_edge);
1.41 if (!reached.get(w)) {
1.42 bfs_queue.push(w);
1.43 @@ -615,15 +615,95 @@
1.44 bool finished() const { return bfs_queue.empty(); }
1.45 operator OutEdgeIt () const { return actual_edge; }
1.46 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.47 - bool isANodeExamined() const { return !(actual_edge.valid()); }
1.48 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.49 NodeIt aNode() const { return bfs_queue.front(); }
1.50 NodeIt bNode() const { return G.bNode(actual_edge); }
1.51 const ReachedMap& getReachedMap() const { return reached; }
1.52 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
1.53 };
1.54
1.55 +
1.56 + template <typename GraphWrapper, typename OutEdgeIt,
1.57 + typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.58 + class BfsIterator5 {
1.59 + typedef typename GraphWrapper::NodeIt NodeIt;
1.60 + GraphWrapper G;
1.61 + std::queue<NodeIt> bfs_queue;
1.62 + ReachedMap& reached;
1.63 + bool b_node_newly_reached;
1.64 + OutEdgeIt actual_edge;
1.65 + bool own_reached_map;
1.66 + public:
1.67 + BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
1.68 + G(_G), reached(_reached),
1.69 + own_reached_map(false) { }
1.70 + BfsIterator5(const GraphWrapper& _G) :
1.71 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.72 + own_reached_map(true) { }
1.73 + ~BfsIterator5() { if (own_reached_map) delete &reached; }
1.74 + void pushAndSetReached(NodeIt s) {
1.75 + reached.set(s, true);
1.76 + if (bfs_queue.empty()) {
1.77 + bfs_queue.push(s);
1.78 + G.getFirst(actual_edge, s);
1.79 + if (G.valid(actual_edge)/*.valid()*/) {
1.80 + NodeIt w=G.bNode(actual_edge);
1.81 + if (!reached.get(w)) {
1.82 + bfs_queue.push(w);
1.83 + reached.set(w, true);
1.84 + b_node_newly_reached=true;
1.85 + } else {
1.86 + b_node_newly_reached=false;
1.87 + }
1.88 + }
1.89 + } else {
1.90 + bfs_queue.push(s);
1.91 + }
1.92 + }
1.93 + BfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
1.94 + operator++() {
1.95 + if (G.valid(actual_edge)/*.valid()*/) {
1.96 + /*++*/G.next(actual_edge);
1.97 + if (G.valid(actual_edge)/*.valid()*/) {
1.98 + NodeIt w=G.bNode(actual_edge);
1.99 + if (!reached.get(w)) {
1.100 + bfs_queue.push(w);
1.101 + reached.set(w, true);
1.102 + b_node_newly_reached=true;
1.103 + } else {
1.104 + b_node_newly_reached=false;
1.105 + }
1.106 + }
1.107 + } else {
1.108 + bfs_queue.pop();
1.109 + if (!bfs_queue.empty()) {
1.110 + G.getFirst(actual_edge, bfs_queue.front());
1.111 + if (G.valid(actual_edge)/*.valid()*/) {
1.112 + NodeIt w=G.bNode(actual_edge);
1.113 + if (!reached.get(w)) {
1.114 + bfs_queue.push(w);
1.115 + reached.set(w, true);
1.116 + b_node_newly_reached=true;
1.117 + } else {
1.118 + b_node_newly_reached=false;
1.119 + }
1.120 + }
1.121 + }
1.122 + }
1.123 + return *this;
1.124 + }
1.125 + bool finished() const { return bfs_queue.empty(); }
1.126 + operator OutEdgeIt () const { return actual_edge; }
1.127 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.128 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.129 + NodeIt aNode() const { return bfs_queue.front(); }
1.130 + NodeIt bNode() const { return G.bNode(actual_edge); }
1.131 + const ReachedMap& getReachedMap() const { return reached; }
1.132 + const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
1.133 + };
1.134 +
1.135 template <typename Graph, typename OutEdgeIt,
1.136 - typename ReachedMap=typename Graph::NodeMap<bool> >
1.137 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.138 class DfsIterator4 {
1.139 typedef typename Graph::NodeIt NodeIt;
1.140 const Graph& G;
1.141 @@ -650,7 +730,7 @@
1.142 operator++() {
1.143 actual_edge=dfs_stack.top();
1.144 //actual_node=G.aNode(actual_edge);
1.145 - if (actual_edge.valid()) {
1.146 + if (G.valid(actual_edge)/*.valid()*/) {
1.147 NodeIt w=G.bNode(actual_edge);
1.148 actual_node=w;
1.149 if (!reached.get(w)) {
1.150 @@ -659,7 +739,7 @@
1.151 b_node_newly_reached=true;
1.152 } else {
1.153 actual_node=G.aNode(actual_edge);
1.154 - ++(dfs_stack.top());
1.155 + /*++*/G.next(dfs_stack.top());
1.156 b_node_newly_reached=false;
1.157 }
1.158 } else {
1.159 @@ -671,87 +751,68 @@
1.160 bool finished() const { return dfs_stack.empty(); }
1.161 operator OutEdgeIt () const { return actual_edge; }
1.162 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.163 - bool isANodeExamined() const { return !(actual_edge.valid()); }
1.164 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.165 NodeIt aNode() const { return actual_node; /*FIXME*/}
1.166 NodeIt bNode() const { return G.bNode(actual_edge); }
1.167 const ReachedMap& getReachedMap() const { return reached; }
1.168 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.169 };
1.170
1.171 -
1.172 -
1.173 - template <typename GraphWrapper, typename ReachedMap>
1.174 - class BfsIterator5 {
1.175 + template <typename GraphWrapper, typename OutEdgeIt,
1.176 + typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.177 + class DfsIterator5 {
1.178 typedef typename GraphWrapper::NodeIt NodeIt;
1.179 - typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.180 - GraphWrapper gw;
1.181 - std::queue<NodeIt> bfs_queue;
1.182 - ReachedMap reached;
1.183 + GraphWrapper G;
1.184 + std::stack<OutEdgeIt> dfs_stack;
1.185 bool b_node_newly_reached;
1.186 OutEdgeIt actual_edge;
1.187 + NodeIt actual_node;
1.188 + ReachedMap& reached;
1.189 + bool own_reached_map;
1.190 public:
1.191 - BfsIterator5(GraphWrapper _gw) :
1.192 - gw(_gw), reached(_gw.getGraph()) { }
1.193 + DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
1.194 + G(_G), reached(_reached),
1.195 + own_reached_map(false) { }
1.196 + DfsIterator5(const GraphWrapper& _G) :
1.197 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.198 + own_reached_map(true) { }
1.199 + ~DfsIterator5() { if (own_reached_map) delete &reached; }
1.200 void pushAndSetReached(NodeIt s) {
1.201 + actual_node=s;
1.202 reached.set(s, true);
1.203 - if (bfs_queue.empty()) {
1.204 - bfs_queue.push(s);
1.205 - gw.getFirst(actual_edge, s);
1.206 - if (actual_edge.valid()) {
1.207 - NodeIt w=gw.bNode(actual_edge);
1.208 - if (!reached.get(w)) {
1.209 - bfs_queue.push(w);
1.210 - reached.set(w, true);
1.211 - b_node_newly_reached=true;
1.212 - } else {
1.213 - b_node_newly_reached=false;
1.214 - }
1.215 - }
1.216 - } else {
1.217 - bfs_queue.push(s);
1.218 - }
1.219 + dfs_stack.push(G.template first<OutEdgeIt>(s));
1.220 }
1.221 - BfsIterator5<GraphWrapper, ReachedMap>&
1.222 + DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
1.223 operator++() {
1.224 - if (actual_edge.valid()) {
1.225 - ++actual_edge;
1.226 - if (actual_edge.valid()) {
1.227 - NodeIt w=gw.bNode(actual_edge);
1.228 - if (!reached.get(w)) {
1.229 - bfs_queue.push(w);
1.230 - reached.set(w, true);
1.231 - b_node_newly_reached=true;
1.232 - } else {
1.233 - b_node_newly_reached=false;
1.234 - }
1.235 + actual_edge=dfs_stack.top();
1.236 + //actual_node=G.aNode(actual_edge);
1.237 + if (G.valid(actual_edge)/*.valid()*/) {
1.238 + NodeIt w=G.bNode(actual_edge);
1.239 + actual_node=w;
1.240 + if (!reached.get(w)) {
1.241 + dfs_stack.push(G.template first<OutEdgeIt>(w));
1.242 + reached.set(w, true);
1.243 + b_node_newly_reached=true;
1.244 + } else {
1.245 + actual_node=G.aNode(actual_edge);
1.246 + /*++*/G.next(dfs_stack.top());
1.247 + b_node_newly_reached=false;
1.248 }
1.249 } else {
1.250 - bfs_queue.pop();
1.251 - if (!bfs_queue.empty()) {
1.252 - gw.getFirst(actual_edge, bfs_queue.front());
1.253 - if (actual_edge.valid()) {
1.254 - NodeIt w=gw.bNode(actual_edge);
1.255 - if (!reached.get(w)) {
1.256 - bfs_queue.push(w);
1.257 - reached.set(w, true);
1.258 - b_node_newly_reached=true;
1.259 - } else {
1.260 - b_node_newly_reached=false;
1.261 - }
1.262 - }
1.263 - }
1.264 + //actual_node=G.aNode(dfs_stack.top());
1.265 + dfs_stack.pop();
1.266 }
1.267 return *this;
1.268 }
1.269 - bool finished() const { return bfs_queue.empty(); }
1.270 + bool finished() const { return dfs_stack.empty(); }
1.271 operator OutEdgeIt () const { return actual_edge; }
1.272 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.273 - bool isANodeExamined() const { return !(actual_edge.valid()); }
1.274 - NodeIt aNode() const { return bfs_queue.front(); }
1.275 - NodeIt bNode() const { return gw.bNode(actual_edge); }
1.276 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.277 + NodeIt aNode() const { return actual_node; /*FIXME*/}
1.278 + NodeIt bNode() const { return G.bNode(actual_edge); }
1.279 const ReachedMap& getReachedMap() const { return reached; }
1.280 - const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
1.281 - };
1.282 + const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.283 + };
1.284
1.285
1.286
2.1 --- a/src/work/edmonds_karp.hh Tue Mar 02 20:40:39 2004 +0000
2.2 +++ b/src/work/edmonds_karp.hh Wed Mar 03 14:30:38 2004 +0000
2.3 @@ -148,9 +148,9 @@
2.4 //OldSymEdgeIt sym;
2.5 OldOutEdgeIt out;
2.6 OldInEdgeIt in;
2.7 - bool out_or_in; //1, iff out
2.8 + bool out_or_in; //true, iff out
2.9 public:
2.10 - EdgeIt() : out_or_in(1) { }
2.11 + EdgeIt() : out_or_in(true) { }
2.12 Number free() const {
2.13 if (out_or_in) {
2.14 return (resG->capacity.get(out)-resG->flow.get(out));
2.15 @@ -246,30 +246,29 @@
2.16 };
2.17
2.18 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.19 - class ResGraph3 {
2.20 + class ResGraphWrapper {
2.21 public:
2.22 typedef typename Graph::NodeIt NodeIt;
2.23 typedef typename Graph::EachNodeIt EachNodeIt;
2.24 -
2.25 private:
2.26 - //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
2.27 typedef typename Graph::OutEdgeIt OldOutEdgeIt;
2.28 typedef typename Graph::InEdgeIt OldInEdgeIt;
2.29 - const Graph& G;
2.30 - FlowMap& flow;
2.31 - const CapacityMap& capacity;
2.32 + const Graph* G;
2.33 + FlowMap* flow;
2.34 + const CapacityMap* capacity;
2.35 public:
2.36 - ResGraph3(const Graph& _G, FlowMap& _flow,
2.37 + ResGraphWrapper(const Graph& _G, FlowMap& _flow,
2.38 const CapacityMap& _capacity) :
2.39 - G(_G), flow(_flow), capacity(_capacity) { }
2.40 -
2.41 + G(&_G), flow(&_flow), capacity(&_capacity) { }
2.42 +// ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
2.43 +// G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
2.44 class EdgeIt;
2.45 class OutEdgeIt;
2.46 friend class EdgeIt;
2.47 friend class OutEdgeIt;
2.48
2.49 class EdgeIt {
2.50 - friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
2.51 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
2.52 protected:
2.53 //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
2.54 const Graph* G;
2.55 @@ -278,9 +277,11 @@
2.56 //OldSymEdgeIt sym;
2.57 OldOutEdgeIt out;
2.58 OldInEdgeIt in;
2.59 - bool out_or_in; //1, iff out
2.60 + bool out_or_in; //true, iff out
2.61 public:
2.62 - EdgeIt() : out_or_in(1) { }
2.63 + EdgeIt() : out_or_in(true) { }
2.64 + EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
2.65 + G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
2.66 //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
2.67 Number free() const {
2.68 if (out_or_in) {
2.69 @@ -317,23 +318,27 @@
2.70 }
2.71 };
2.72
2.73 + Number free(OldOutEdgeIt out) const {
2.74 + return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
2.75 + }
2.76 + Number free(OldInEdgeIt in) const {
2.77 + return (/*resG->*/flow->get(in));
2.78 + }
2.79 +
2.80 class OutEdgeIt : public EdgeIt {
2.81 - friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
2.82 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
2.83 public:
2.84 OutEdgeIt() { }
2.85 private:
2.86 - OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {
2.87 - G=&_G;
2.88 - flow=&_flow;
2.89 - capacity=&_capacity;
2.90 + OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
2.91 //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
2.92 G->getFirst(out, v);
2.93 - while( out.valid() && !(free()>0) ) { ++out; }
2.94 + while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
2.95 if (!out.valid()) {
2.96 out_or_in=0;
2.97 //in=/*resG->*/G->template first<OldInEdgeIt>(v);
2.98 G->getFirst(in, v);
2.99 - while( in.valid() && !(free()>0) ) { ++in; }
2.100 + while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
2.101 }
2.102 }
2.103 public:
2.104 @@ -341,91 +346,141 @@
2.105 if (out_or_in) {
2.106 NodeIt v=/*resG->*/G->aNode(out);
2.107 ++out;
2.108 - while( out.valid() && !(free()>0) ) { ++out; }
2.109 + while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
2.110 if (!out.valid()) {
2.111 out_or_in=0;
2.112 G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
2.113 - while( in.valid() && !(free()>0) ) { ++in; }
2.114 + while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
2.115 }
2.116 } else {
2.117 ++in;
2.118 - while( in.valid() && !(free()>0) ) { ++in; }
2.119 + while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
2.120 }
2.121 return *this;
2.122 }
2.123 };
2.124
2.125 class EachEdgeIt : public EdgeIt {
2.126 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
2.127 typename Graph::EachNodeIt v;
2.128 public:
2.129 EachEdgeIt() { }
2.130 //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
2.131 - EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) {
2.132 - G=&_G;
2.133 - flow=&_flow;
2.134 - capacity=&_capacity;
2.135 - out_or_in=1;
2.136 + EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
2.137 + out_or_in=true;
2.138 G->getFirst(v);
2.139 if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
2.140 - while (out.valid() && !(free()>0) ) { ++out; }
2.141 + while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
2.142 while (v.valid() && !out.valid()) {
2.143 ++v;
2.144 if (v.valid()) G->getFirst(out, v);
2.145 - while (out.valid() && !(free()>0) ) { ++out; }
2.146 + while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
2.147 }
2.148 if (!out.valid()) {
2.149 out_or_in=0;
2.150 G->getFirst(v);
2.151 if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
2.152 - while (in.valid() && !(free()>0) ) { ++in; }
2.153 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
2.154 while (v.valid() && !in.valid()) {
2.155 ++v;
2.156 if (v.valid()) G->getFirst(in, v);
2.157 - while (in.valid() && !(free()>0) ) { ++in; }
2.158 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
2.159 }
2.160 }
2.161 }
2.162 EachEdgeIt& operator++() {
2.163 if (out_or_in) {
2.164 ++out;
2.165 - while (out.valid() && !(free()>0) ) { ++out; }
2.166 + while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
2.167 while (v.valid() && !out.valid()) {
2.168 ++v;
2.169 if (v.valid()) G->getFirst(out, v);
2.170 - while (out.valid() && !(free()>0) ) { ++out; }
2.171 + while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
2.172 }
2.173 if (!out.valid()) {
2.174 out_or_in=0;
2.175 G->getFirst(v);
2.176 if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
2.177 - while (in.valid() && !(free()>0) ) { ++in; }
2.178 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
2.179 while (v.valid() && !in.valid()) {
2.180 ++v;
2.181 if (v.valid()) G->getFirst(in, v);
2.182 - while (in.valid() && !(free()>0) ) { ++in; }
2.183 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
2.184 }
2.185 }
2.186 } else {
2.187 ++in;
2.188 - while (in.valid() && !(free()>0) ) { ++in; }
2.189 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
2.190 while (v.valid() && !in.valid()) {
2.191 ++v;
2.192 if (v.valid()) G->getFirst(in, v);
2.193 - while (in.valid() && !(free()>0) ) { ++in; }
2.194 + while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
2.195 }
2.196 }
2.197 return *this;
2.198 }
2.199 };
2.200
2.201 + void getFirst(EachNodeIt& v) const { G->getFirst(v); }
2.202 void getFirst(OutEdgeIt& e, NodeIt v) const {
2.203 - e=OutEdgeIt(G, v, flow, capacity);
2.204 + e=OutEdgeIt(*G, v, *flow, *capacity);
2.205 }
2.206 void getFirst(EachEdgeIt& e) const {
2.207 - e=EachEdgeIt(G, flow, capacity);
2.208 + e=EachEdgeIt(*G, *flow, *capacity);
2.209 }
2.210 - void getFirst(EachNodeIt& v) const { G.getFirst(v); }
2.211 +
2.212 + EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
2.213 +
2.214 + OutEdgeIt& next(OutEdgeIt& e) const {
2.215 + if (e.out_or_in) {
2.216 + NodeIt v=G->aNode(e.out);
2.217 + ++(e.out);
2.218 + while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
2.219 + if (!G->valid(e.out)) {
2.220 + e.out_or_in=0;
2.221 + G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
2.222 + while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
2.223 + }
2.224 + } else {
2.225 + ++(e.in);
2.226 + while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
2.227 + }
2.228 + return e;
2.229 + }
2.230 +
2.231 + EachEdgeIt& next(EachEdgeIt& e) const {
2.232 + if (e.out_or_in) {
2.233 + ++(e.out);
2.234 + while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
2.235 + while (G->valid(e.v) && !G->valid(e.out)) {
2.236 + ++(e.v);
2.237 + if (G->valid(e.v)) G->getFirst(e.out, e.v);
2.238 + while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
2.239 + }
2.240 + if (!G->valid(e.out)) {
2.241 + e.out_or_in=0;
2.242 + G->getFirst(e.v);
2.243 + if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
2.244 + while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
2.245 + while (G->valid(e.v) && !G->valid(e.in)) {
2.246 + ++(e.v);
2.247 + if (G->valid(e.v)) G->getFirst(e.in, e.v);
2.248 + while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
2.249 + }
2.250 + }
2.251 + } else {
2.252 + ++(e.in);
2.253 + while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
2.254 + while (G->valid(e.v) && !G->valid(e.in)) {
2.255 + ++(e.v);
2.256 + if (G->valid(e.v)) G->getFirst(e.in, e.v);
2.257 + while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
2.258 + }
2.259 + }
2.260 + return e;
2.261 + }
2.262
2.263 +
2.264 template< typename It >
2.265 It first() const {
2.266 It e;
2.267 @@ -441,23 +496,27 @@
2.268 }
2.269
2.270 NodeIt tail(EdgeIt e) const {
2.271 - return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
2.272 + return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
2.273 NodeIt head(EdgeIt e) const {
2.274 - return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
2.275 + return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
2.276
2.277 NodeIt aNode(OutEdgeIt e) const {
2.278 - return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
2.279 + return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
2.280 NodeIt bNode(OutEdgeIt e) const {
2.281 - return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
2.282 + return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
2.283
2.284 - int id(NodeIt v) const { return G.id(v); }
2.285 + int id(NodeIt v) const { return G->id(v); }
2.286 +
2.287 + bool valid(NodeIt n) const { return G->valid(n); }
2.288 + bool valid(EdgeIt e) const {
2.289 + return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
2.290
2.291 template <typename T>
2.292 class NodeMap {
2.293 typename Graph::NodeMap<T> node_map;
2.294 public:
2.295 - NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
2.296 - NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(_G.G, a) { }
2.297 + NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
2.298 + NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
2.299 void set(NodeIt nit, T a) { node_map.set(nit, a); }
2.300 T get(NodeIt nit) const { return node_map.get(nit); }
2.301 };
2.302 @@ -466,8 +525,8 @@
2.303 class EdgeMap {
2.304 typename Graph::EdgeMap<T> forward_map, backward_map;
2.305 public:
2.306 - EdgeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.G), backward_map(_G.G) { }
2.307 - EdgeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.G, a), backward_map(_G.G, a) { }
2.308 + EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
2.309 + EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
2.310 void set(EdgeIt e, T a) {
2.311 if (e.out_or_in)
2.312 forward_map.set(e.out, a);
2.313 @@ -494,12 +553,12 @@
2.314 typedef typename Graph::InEdgeIt InEdgeIt;
2.315
2.316 private:
2.317 - const Graph& G;
2.318 + const Graph* G;
2.319 NodeIt s;
2.320 NodeIt t;
2.321 - FlowMap& flow;
2.322 - const CapacityMap& capacity;
2.323 - typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
2.324 + FlowMap* flow;
2.325 + const CapacityMap* capacity;
2.326 + typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
2.327 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
2.328 typedef typename AugGraph::EdgeIt AugEdgeIt;
2.329
2.330 @@ -509,15 +568,15 @@
2.331 //typename AugGraph::NodeMap<Number> free;
2.332 public:
2.333 MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
2.334 - G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //,
2.335 + G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //,
2.336 //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
2.337 { }
2.338 bool augmentOnShortestPath() {
2.339 - AugGraph res_graph(G, flow, capacity);
2.340 + AugGraph res_graph(*G, *flow, *capacity);
2.341 bool _augment=false;
2.342
2.343 typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.344 - BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
2.345 + BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
2.346 res_bfs.pushAndSetReached(s);
2.347
2.348 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
2.349 @@ -529,11 +588,11 @@
2.350 //searching for augmenting path
2.351 while ( !res_bfs.finished() ) {
2.352 AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
2.353 - if (e.valid() && res_bfs.isBNodeNewlyReached()) {
2.354 + if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
2.355 NodeIt v=res_graph.tail(e);
2.356 NodeIt w=res_graph.head(e);
2.357 pred.set(w, e);
2.358 - if (pred.get(v).valid()) {
2.359 + if (res_graph.valid(pred.get(v))) {
2.360 free.set(w, std::min(free.get(v), e.free()));
2.361 } else {
2.362 free.set(w, e.free());
2.363 @@ -547,7 +606,7 @@
2.364 if (_augment) {
2.365 NodeIt n=t;
2.366 Number augment_value=free.get(t);
2.367 - while (pred.get(n).valid()) {
2.368 + while (res_graph.valid(pred.get(n))) {
2.369 AugEdgeIt e=pred.get(n);
2.370 e.augment(augment_value);
2.371 n=res_graph.tail(e);
2.372 @@ -560,7 +619,7 @@
2.373 template<typename MutableGraph> bool augmentOnBlockingFlow() {
2.374 bool _augment=false;
2.375
2.376 - AugGraph res_graph(G, flow, capacity);
2.377 + AugGraph res_graph(*G, *flow, *capacity);
2.378
2.379 typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.380 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
2.381 @@ -569,7 +628,7 @@
2.382 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
2.383 while ( !bfs.finished() ) {
2.384 AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
2.385 - if (e.valid() && bfs.isBNodeNewlyReached()) {
2.386 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.387 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.388 }
2.389
2.390 @@ -578,7 +637,7 @@
2.391
2.392 MutableGraph F;
2.393 typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
2.394 - for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) {
2.395 + for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
2.396 res_graph_to_F.set(n, F.addNode());
2.397 }
2.398
2.399 @@ -586,17 +645,17 @@
2.400 typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
2.401
2.402 typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
2.403 - typename MutableGraph::EdgeMap<Number> free_on_edge(F);
2.404 + typename MutableGraph::EdgeMap<Number> residual_capacity(F);
2.405
2.406 //Making F to the graph containing the edges of the residual graph
2.407 //which are in some shortest paths
2.408 - for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) {
2.409 + for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
2.410 if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
2.411 typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
2.412 original_edge.update();
2.413 original_edge.set(f, e);
2.414 - free_on_edge.update();
2.415 - free_on_edge.set(f, e.free());
2.416 + residual_capacity.update();
2.417 + residual_capacity.set(f, e.free());
2.418 }
2.419 }
2.420
2.421 @@ -613,7 +672,7 @@
2.422 dfs.pushAndSetReached(sF);
2.423 while (!dfs.finished()) {
2.424 ++dfs;
2.425 - if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
2.426 + if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
2.427 //std::cout << "OutEdgeIt: " << dfs;
2.428 //std::cout << " aNode: " << F.aNode(dfs);
2.429 //std::cout << " bNode: " << F.bNode(dfs) << " ";
2.430 @@ -621,10 +680,10 @@
2.431 typename MutableGraph::NodeIt v=F.aNode(dfs);
2.432 typename MutableGraph::NodeIt w=F.bNode(dfs);
2.433 pred.set(w, dfs);
2.434 - if (pred.get(v).valid()) {
2.435 - free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));
2.436 + if (F.valid(pred.get(v))) {
2.437 + free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
2.438 } else {
2.439 - free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/);
2.440 + free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);
2.441 }
2.442 if (w==tF) {
2.443 //std::cout << "AUGMENTATION"<<std::endl;
2.444 @@ -657,14 +716,14 @@
2.445 if (__augment) {
2.446 typename MutableGraph::NodeIt n=tF;
2.447 Number augment_value=free.get(tF);
2.448 - while (pred.get(n).valid()) {
2.449 + while (F.valid(pred.get(n))) {
2.450 typename MutableGraph::EdgeIt e=pred.get(n);
2.451 original_edge.get(e).augment(augment_value);
2.452 n=F.tail(e);
2.453 - if (free_on_edge.get(e)==augment_value)
2.454 + if (residual_capacity.get(e)==augment_value)
2.455 F.erase(e);
2.456 else
2.457 - free_on_edge.set(e, free_on_edge.get(e)-augment_value);
2.458 + residual_capacity.set(e, residual_capacity.get(e)-augment_value);
2.459 }
2.460 }
2.461
2.462 @@ -690,59 +749,14 @@
2.463 }
2.464 Number flowValue() {
2.465 Number a=0;
2.466 - for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
2.467 - a+=flow.get(i);
2.468 + OutEdgeIt e;
2.469 + for(G->getFirst(e, s); G->valid(e); G->next(e)) {
2.470 + a+=flow->get(e);
2.471 }
2.472 return a;
2.473 }
2.474 };
2.475
2.476 -
2.477 -/*
2.478 - template <typename Graph>
2.479 - class IteratorBoolNodeMap {
2.480 - typedef typename Graph::NodeIt NodeIt;
2.481 - typedef typename Graph::EachNodeIt EachNodeIt;
2.482 - class BoolItem {
2.483 - public:
2.484 - bool value;
2.485 - NodeIt prev;
2.486 - NodeIt next;
2.487 - BoolItem() : value(false), prev(), next() {}
2.488 - };
2.489 - NodeIt first_true;
2.490 - //NodeIt last_true;
2.491 - NodeIt first_false;
2.492 - //NodeIt last_false;
2.493 - const Graph& G;
2.494 - typename Graph::NodeMap<BoolItem> container;
2.495 - public:
2.496 - typedef bool ValueType;
2.497 - typedef NodeIt KeyType;
2.498 - IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {
2.499 - //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
2.500 - //BoolItem b=container.get(e);
2.501 - //b.me=e;
2.502 - //container.set(b);
2.503 - //}
2.504 - G.getFirst(first_false);
2.505 - NodeIt e_prev;
2.506 - for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
2.507 - container[e].prev=e_prev;
2.508 - if (e_prev.valid()) container[e_prev].next=e;
2.509 - e_prev=e;
2.510 - }
2.511 - }
2.512 - //NodeMap(const Graph& _G, T a) :
2.513 - // G(_G), container(G.node_id, a) { }
2.514 - //FIXME
2.515 - void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
2.516 - T get(NodeIt nit) const { return container[G.id(nit)]; }
2.517 - //void update() { container.resize(G.node_id); }
2.518 - //void update(T a) { container.resize(G.node_id, a); }
2.519 - };
2.520 -*/
2.521 -
2.522
2.523 template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.524 class MaxFlow2 {
3.1 --- a/src/work/list_graph.hh Tue Mar 02 20:40:39 2004 +0000
3.2 +++ b/src/work/list_graph.hh Wed Mar 03 14:30:38 2004 +0000
3.3 @@ -302,8 +302,8 @@
3.4 return e;
3.5 }
3.6
3.7 + bool valid(NodeIt n) const { return n.valid(); }
3.8 bool valid(EdgeIt e) const { return e.valid(); }
3.9 - bool valid(NodeIt n) const { return n.valid(); }
3.10
3.11 template <typename It> It getNext(It it) const {
3.12 It tmp(it); return next(tmp); }
4.1 --- a/src/work/marci/graph_wrapper.h Tue Mar 02 20:40:39 2004 +0000
4.2 +++ b/src/work/marci/graph_wrapper.h Wed Mar 03 14:30:38 2004 +0000
4.3 @@ -275,299 +275,300 @@
4.4 };
4.5
4.6
4.7 -// FIXME: comparison should be made better!!!
4.8 - template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
4.9 - class ResGraphWrapper
4.10 - {
4.11 - Graph* graph;
4.12 +
4.13 +// // FIXME: comparison should be made better!!!
4.14 +// template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
4.15 +// class ResGraphWrapper
4.16 +// {
4.17 +// Graph* graph;
4.18
4.19 - public:
4.20 - typedef Graph BaseGraph;
4.21 +// public:
4.22 +// typedef Graph BaseGraph;
4.23
4.24 - typedef typename Graph::NodeIt NodeIt;
4.25 - typedef typename Graph::EdgeIt EdgeIt;
4.26 +// typedef typename Graph::NodeIt NodeIt;
4.27 +// typedef typename Graph::EdgeIt EdgeIt;
4.28
4.29 - typedef typename Graph::EachNodeIt EachNodeIt;
4.30 +// typedef typename Graph::EachNodeIt EachNodeIt;
4.31
4.32 - class OutEdgeIt {
4.33 - public:
4.34 - //Graph::NodeIt n;
4.35 - bool out_or_in;
4.36 - typename Graph::OutEdgeIt o;
4.37 - typename Graph::InEdgeIt i;
4.38 - };
4.39 - class InEdgeIt {
4.40 - public:
4.41 - //Graph::NodeIt n;
4.42 - bool out_or_in;
4.43 - typename Graph::OutEdgeIt o;
4.44 - typename Graph::InEdgeIt i;
4.45 - };
4.46 - typedef typename Graph::SymEdgeIt SymEdgeIt;
4.47 - typedef typename Graph::EachEdgeIt EachEdgeIt;
4.48 +// class OutEdgeIt {
4.49 +// public:
4.50 +// //Graph::NodeIt n;
4.51 +// bool out_or_in;
4.52 +// typename Graph::OutEdgeIt o;
4.53 +// typename Graph::InEdgeIt i;
4.54 +// };
4.55 +// class InEdgeIt {
4.56 +// public:
4.57 +// //Graph::NodeIt n;
4.58 +// bool out_or_in;
4.59 +// typename Graph::OutEdgeIt o;
4.60 +// typename Graph::InEdgeIt i;
4.61 +// };
4.62 +// typedef typename Graph::SymEdgeIt SymEdgeIt;
4.63 +// typedef typename Graph::EachEdgeIt EachEdgeIt;
4.64
4.65 - int nodeNum() const { return graph->nodeNum(); }
4.66 - int edgeNum() const { return graph->edgeNum(); }
4.67 +// int nodeNum() const { return graph->nodeNum(); }
4.68 +// int edgeNum() const { return graph->edgeNum(); }
4.69
4.70 - NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
4.71 +// NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
4.72
4.73 - // EachEdge and SymEdge is missing!!!!
4.74 - // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
4.75 +// // EachEdge and SymEdge is missing!!!!
4.76 +// // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
4.77
4.78 - //FIXME
4.79 - OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
4.80 - {
4.81 - e.n=n;
4.82 - graph->getFirst(e.o,n);
4.83 - while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
4.84 - graph->goNext(e.o);
4.85 - if(!graph->valid(e.o)) {
4.86 - graph->getFirst(e.i,n);
4.87 - while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
4.88 - graph->goNext(e.i);
4.89 - }
4.90 - return e;
4.91 - }
4.92 -/*
4.93 - OutEdgeIt &goNext(OutEdgeIt &e)
4.94 - {
4.95 - if(graph->valid(e.o)) {
4.96 - while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
4.97 - graph->goNext(e.o);
4.98 - if(graph->valid(e.o)) return e;
4.99 - else graph->getFirst(e.i,e.n);
4.100 - }
4.101 - else {
4.102 - while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
4.103 - graph->goNext(e.i);
4.104 - return e;
4.105 - }
4.106 - }
4.107 - OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
4.108 -*/
4.109 - //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
4.110 +// //FIXME
4.111 +// OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
4.112 +// {
4.113 +// e.n=n;
4.114 +// graph->getFirst(e.o,n);
4.115 +// while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
4.116 +// graph->goNext(e.o);
4.117 +// if(!graph->valid(e.o)) {
4.118 +// graph->getFirst(e.i,n);
4.119 +// while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
4.120 +// graph->goNext(e.i);
4.121 +// }
4.122 +// return e;
4.123 +// }
4.124 +// /*
4.125 +// OutEdgeIt &goNext(OutEdgeIt &e)
4.126 +// {
4.127 +// if(graph->valid(e.o)) {
4.128 +// while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
4.129 +// graph->goNext(e.o);
4.130 +// if(graph->valid(e.o)) return e;
4.131 +// else graph->getFirst(e.i,e.n);
4.132 +// }
4.133 +// else {
4.134 +// while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
4.135 +// graph->goNext(e.i);
4.136 +// return e;
4.137 +// }
4.138 +// }
4.139 +// OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
4.140 +// */
4.141 +// //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
4.142
4.143 - //FIXME
4.144 - InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
4.145 - {
4.146 - e.n=n;
4.147 - graph->getFirst(e.i,n);
4.148 - while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
4.149 - graph->goNext(e.i);
4.150 - if(!graph->valid(e.i)) {
4.151 - graph->getFirst(e.o,n);
4.152 - while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
4.153 - graph->goNext(e.o);
4.154 - }
4.155 - return e;
4.156 - }
4.157 -/*
4.158 - InEdgeIt &goNext(InEdgeIt &e)
4.159 - {
4.160 - if(graph->valid(e.i)) {
4.161 - while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
4.162 - graph->goNext(e.i);
4.163 - if(graph->valid(e.i)) return e;
4.164 - else graph->getFirst(e.o,e.n);
4.165 - }
4.166 - else {
4.167 - while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
4.168 - graph->goNext(e.o);
4.169 - return e;
4.170 - }
4.171 - }
4.172 - InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
4.173 -*/
4.174 - //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
4.175 +// //FIXME
4.176 +// InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
4.177 +// {
4.178 +// e.n=n;
4.179 +// graph->getFirst(e.i,n);
4.180 +// while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
4.181 +// graph->goNext(e.i);
4.182 +// if(!graph->valid(e.i)) {
4.183 +// graph->getFirst(e.o,n);
4.184 +// while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
4.185 +// graph->goNext(e.o);
4.186 +// }
4.187 +// return e;
4.188 +// }
4.189 +// /*
4.190 +// InEdgeIt &goNext(InEdgeIt &e)
4.191 +// {
4.192 +// if(graph->valid(e.i)) {
4.193 +// while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
4.194 +// graph->goNext(e.i);
4.195 +// if(graph->valid(e.i)) return e;
4.196 +// else graph->getFirst(e.o,e.n);
4.197 +// }
4.198 +// else {
4.199 +// while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
4.200 +// graph->goNext(e.o);
4.201 +// return e;
4.202 +// }
4.203 +// }
4.204 +// InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
4.205 +// */
4.206 +// //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
4.207
4.208 - //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
4.209 - //template<typename I> I next(const I i); { return graph->goNext(i); }
4.210 +// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
4.211 +// //template<typename I> I next(const I i); { return graph->goNext(i); }
4.212
4.213 - template< typename It > It first() const {
4.214 - It e; getFirst(e); return e; }
4.215 +// template< typename It > It first() const {
4.216 +// It e; getFirst(e); return e; }
4.217
4.218 - template< typename It > It first(NodeIt v) const {
4.219 - It e; getFirst(e, v); return e; }
4.220 +// template< typename It > It first(NodeIt v) const {
4.221 +// It e; getFirst(e, v); return e; }
4.222
4.223 - NodeIt head(const EdgeIt& e) const { return graph->head(e); }
4.224 - NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
4.225 +// NodeIt head(const EdgeIt& e) const { return graph->head(e); }
4.226 +// NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
4.227
4.228 - template<typename I> NodeIt aNode(const I& e) const {
4.229 - return graph->aNode(e); }
4.230 - template<typename I> NodeIt bNode(const I& e) const {
4.231 - return graph->bNode(e); }
4.232 +// template<typename I> NodeIt aNode(const I& e) const {
4.233 +// return graph->aNode(e); }
4.234 +// template<typename I> NodeIt bNode(const I& e) const {
4.235 +// return graph->bNode(e); }
4.236
4.237 - //template<typename I> bool valid(const I i);
4.238 - //{ return graph->valid(i); }
4.239 +// //template<typename I> bool valid(const I i);
4.240 +// //{ return graph->valid(i); }
4.241
4.242 - //template<typename I> void setInvalid(const I &i);
4.243 - //{ return graph->setInvalid(i); }
4.244 +// //template<typename I> void setInvalid(const I &i);
4.245 +// //{ return graph->setInvalid(i); }
4.246
4.247 - NodeIt addNode() { return graph->addNode(); }
4.248 - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
4.249 - return graph->addEdge(tail, head); }
4.250 +// NodeIt addNode() { return graph->addNode(); }
4.251 +// EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
4.252 +// return graph->addEdge(tail, head); }
4.253
4.254 - template<typename I> void erase(const I& i) { graph->erase(i); }
4.255 +// template<typename I> void erase(const I& i) { graph->erase(i); }
4.256
4.257 - void clear() { graph->clear(); }
4.258 +// void clear() { graph->clear(); }
4.259
4.260 - template<typename S> class NodeMap : public Graph::NodeMap<S> { };
4.261 - template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
4.262 +// template<typename S> class NodeMap : public Graph::NodeMap<S> { };
4.263 +// template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
4.264
4.265 - void setGraph(Graph& _graph) { graph = &_graph; }
4.266 - Graph& getGraph() { return (*graph); }
4.267 +// void setGraph(Graph& _graph) { graph = &_graph; }
4.268 +// Graph& getGraph() { return (*graph); }
4.269
4.270 - //ResGraphWrapper() : graph(0) { }
4.271 - ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.272 - };
4.273 +// //ResGraphWrapper() : graph(0) { }
4.274 +// ResGraphWrapper(Graph& _graph) : graph(&_graph) { }
4.275 +// };
4.276
4.277
4.278 -// FIXME: comparison should be made better!!!
4.279 - template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
4.280 - class ConstResGraphWrapper
4.281 - {
4.282 - const Graph* graph;
4.283 - const LowerMap* low;
4.284 - FlowMap* flow;
4.285 - const UpperMap* up;
4.286 - public:
4.287 - typedef Graph BaseGraph;
4.288 +// // FIXME: comparison should be made better!!!
4.289 +// template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
4.290 +// class ConstResGraphWrapper
4.291 +// {
4.292 +// const Graph* graph;
4.293 +// const LowerMap* low;
4.294 +// FlowMap* flow;
4.295 +// const UpperMap* up;
4.296 +// public:
4.297 +// typedef Graph BaseGraph;
4.298
4.299 - typedef typename Graph::NodeIt NodeIt;
4.300 - typedef typename Graph::EdgeIt EdgeIt;
4.301 +// typedef typename Graph::NodeIt NodeIt;
4.302 +// typedef typename Graph::EdgeIt EdgeIt;
4.303
4.304 - typedef typename Graph::EachNodeIt EachNodeIt;
4.305 +// typedef typename Graph::EachNodeIt EachNodeIt;
4.306
4.307 - class OutEdgeIt {
4.308 - public:
4.309 - //Graph::NodeIt n;
4.310 - bool out_or_in;
4.311 - typename Graph::SymEdgeIt sym;
4.312 - };
4.313 - class InEdgeIt {
4.314 - public:
4.315 - //Graph::NodeIt n;
4.316 - bool out_or_in;
4.317 - typename Graph::OutEdgeIt sym;
4.318 - };
4.319 - //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.320 - //typedef typename Graph::EachEdgeIt EachEdgeIt;
4.321 +// class OutEdgeIt {
4.322 +// public:
4.323 +// //Graph::NodeIt n;
4.324 +// bool out_or_in;
4.325 +// typename Graph::SymEdgeIt sym;
4.326 +// };
4.327 +// class InEdgeIt {
4.328 +// public:
4.329 +// //Graph::NodeIt n;
4.330 +// bool out_or_in;
4.331 +// typename Graph::OutEdgeIt sym;
4.332 +// };
4.333 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
4.334 +// //typedef typename Graph::EachEdgeIt EachEdgeIt;
4.335
4.336 - int nodeNum() const { return graph->nodeNum(); }
4.337 - //int edgeNum() const { return graph->edgeNum(); }
4.338 +// int nodeNum() const { return graph->nodeNum(); }
4.339 +// //int edgeNum() const { return graph->edgeNum(); }
4.340
4.341 - NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
4.342 +// NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
4.343
4.344 - // EachEdge and SymEdge is missing!!!!
4.345 - // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
4.346 +// // EachEdge and SymEdge is missing!!!!
4.347 +// // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
4.348
4.349
4.350 - //FIXME
4.351 - OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
4.352 - {
4.353 - e.n=n;
4.354 - graph->getFirst(e.o,n);
4.355 - while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
4.356 - graph->goNext(e.o);
4.357 - if(!graph->valid(e.o)) {
4.358 - graph->getFirst(e.i,n);
4.359 - while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
4.360 - graph->goNext(e.i);
4.361 - }
4.362 - return e;
4.363 - }
4.364 -/*
4.365 - OutEdgeIt &goNext(OutEdgeIt &e)
4.366 - {
4.367 - if(graph->valid(e.o)) {
4.368 - while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
4.369 - graph->goNext(e.o);
4.370 - if(graph->valid(e.o)) return e;
4.371 - else graph->getFirst(e.i,e.n);
4.372 - }
4.373 - else {
4.374 - while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
4.375 - graph->goNext(e.i);
4.376 - return e;
4.377 - }
4.378 - }
4.379 - OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
4.380 -*/
4.381 - //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
4.382 +// //FIXME
4.383 +// OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
4.384 +// {
4.385 +// e.n=n;
4.386 +// graph->getFirst(e.o,n);
4.387 +// while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
4.388 +// graph->goNext(e.o);
4.389 +// if(!graph->valid(e.o)) {
4.390 +// graph->getFirst(e.i,n);
4.391 +// while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
4.392 +// graph->goNext(e.i);
4.393 +// }
4.394 +// return e;
4.395 +// }
4.396 +// /*
4.397 +// OutEdgeIt &goNext(OutEdgeIt &e)
4.398 +// {
4.399 +// if(graph->valid(e.o)) {
4.400 +// while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
4.401 +// graph->goNext(e.o);
4.402 +// if(graph->valid(e.o)) return e;
4.403 +// else graph->getFirst(e.i,e.n);
4.404 +// }
4.405 +// else {
4.406 +// while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
4.407 +// graph->goNext(e.i);
4.408 +// return e;
4.409 +// }
4.410 +// }
4.411 +// OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
4.412 +// */
4.413 +// //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
4.414
4.415 - //FIXME
4.416 - InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
4.417 - {
4.418 - e.n=n;
4.419 - graph->getFirst(e.i,n);
4.420 - while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
4.421 - graph->goNext(e.i);
4.422 - if(!graph->valid(e.i)) {
4.423 - graph->getFirst(e.o,n);
4.424 - while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
4.425 - graph->goNext(e.o);
4.426 - }
4.427 - return e;
4.428 - }
4.429 -/*
4.430 - InEdgeIt &goNext(InEdgeIt &e)
4.431 - {
4.432 - if(graph->valid(e.i)) {
4.433 - while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
4.434 - graph->goNext(e.i);
4.435 - if(graph->valid(e.i)) return e;
4.436 - else graph->getFirst(e.o,e.n);
4.437 - }
4.438 - else {
4.439 - while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
4.440 - graph->goNext(e.o);
4.441 - return e;
4.442 - }
4.443 - }
4.444 - InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
4.445 -*/
4.446 - //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
4.447 +// //FIXME
4.448 +// InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
4.449 +// {
4.450 +// e.n=n;
4.451 +// graph->getFirst(e.i,n);
4.452 +// while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
4.453 +// graph->goNext(e.i);
4.454 +// if(!graph->valid(e.i)) {
4.455 +// graph->getFirst(e.o,n);
4.456 +// while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
4.457 +// graph->goNext(e.o);
4.458 +// }
4.459 +// return e;
4.460 +// }
4.461 +// /*
4.462 +// InEdgeIt &goNext(InEdgeIt &e)
4.463 +// {
4.464 +// if(graph->valid(e.i)) {
4.465 +// while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
4.466 +// graph->goNext(e.i);
4.467 +// if(graph->valid(e.i)) return e;
4.468 +// else graph->getFirst(e.o,e.n);
4.469 +// }
4.470 +// else {
4.471 +// while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
4.472 +// graph->goNext(e.o);
4.473 +// return e;
4.474 +// }
4.475 +// }
4.476 +// InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
4.477 +// */
4.478 +// //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
4.479
4.480 - //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
4.481 - //template<typename I> I next(const I i); { return graph->goNext(i); }
4.482 +// //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
4.483 +// //template<typename I> I next(const I i); { return graph->goNext(i); }
4.484
4.485 - template< typename It > It first() const {
4.486 - It e; getFirst(e); return e; }
4.487 +// template< typename It > It first() const {
4.488 +// It e; getFirst(e); return e; }
4.489
4.490 - template< typename It > It first(NodeIt v) const {
4.491 - It e; getFirst(e, v); return e; }
4.492 +// template< typename It > It first(NodeIt v) const {
4.493 +// It e; getFirst(e, v); return e; }
4.494
4.495 - NodeIt head(const EdgeIt& e) const { return graph->head(e); }
4.496 - NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
4.497 +// NodeIt head(const EdgeIt& e) const { return graph->head(e); }
4.498 +// NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
4.499
4.500 - template<typename I> NodeIt aNode(const I& e) const {
4.501 - return graph->aNode(e); }
4.502 - template<typename I> NodeIt bNode(const I& e) const {
4.503 - return graph->bNode(e); }
4.504 +// template<typename I> NodeIt aNode(const I& e) const {
4.505 +// return graph->aNode(e); }
4.506 +// template<typename I> NodeIt bNode(const I& e) const {
4.507 +// return graph->bNode(e); }
4.508
4.509 - //template<typename I> bool valid(const I i);
4.510 - //{ return graph->valid(i); }
4.511 +// //template<typename I> bool valid(const I i);
4.512 +// //{ return graph->valid(i); }
4.513
4.514 - //template<typename I> void setInvalid(const I &i);
4.515 - //{ return graph->setInvalid(i); }
4.516 +// //template<typename I> void setInvalid(const I &i);
4.517 +// //{ return graph->setInvalid(i); }
4.518
4.519 - NodeIt addNode() { return graph->addNode(); }
4.520 - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
4.521 - return graph->addEdge(tail, head); }
4.522 +// NodeIt addNode() { return graph->addNode(); }
4.523 +// EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
4.524 +// return graph->addEdge(tail, head); }
4.525
4.526 - template<typename I> void erase(const I& i) { graph->erase(i); }
4.527 +// template<typename I> void erase(const I& i) { graph->erase(i); }
4.528
4.529 - void clear() { graph->clear(); }
4.530 +// void clear() { graph->clear(); }
4.531
4.532 - template<typename S> class NodeMap : public Graph::NodeMap<S> { };
4.533 - template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
4.534 +// template<typename S> class NodeMap : public Graph::NodeMap<S> { };
4.535 +// template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
4.536
4.537 - void setGraph(const Graph& _graph) { graph = &_graph; }
4.538 - const Graph& getGraph() { return (*graph); }
4.539 +// void setGraph(const Graph& _graph) { graph = &_graph; }
4.540 +// const Graph& getGraph() { return (*graph); }
4.541
4.542 - //ConstResGraphWrapper() : graph(0) { }
4.543 - ConstResGraphWrapper(const Graph& _graph) : graph(&_graph) { }
4.544 - };
4.545 +// //ConstResGraphWrapper() : graph(0) { }
4.546 +// ConstResGraphWrapper(const Graph& _graph) : graph(&_graph) { }
4.547 +// };
4.548
4.549
4.550