1.1 --- a/src/work/bfs_iterator.hh Mon Feb 16 10:57:01 2004 +0000
1.2 +++ b/src/work/bfs_iterator.hh Mon Feb 16 11:29:48 2004 +0000
1.3 @@ -3,6 +3,8 @@
1.4
1.5 #include <queue>
1.6 #include <stack>
1.7 +#include <utility>
1.8 +#include <graph_wrapper.h>
1.9
1.10 namespace marci {
1.11
1.12 @@ -466,6 +468,227 @@
1.13 const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
1.14 };
1.15
1.16 +
1.17 + template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.18 + class BfsIterator3 {
1.19 + typedef typename Graph::NodeIt NodeIt;
1.20 + const Graph& G;
1.21 + std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue;
1.22 + ReachedMap reached;
1.23 + bool b_node_newly_reached;
1.24 + OutEdgeIt actual_edge;
1.25 + public:
1.26 + BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
1.27 + void pushAndSetReached(NodeIt s) {
1.28 + reached.set(s, true);
1.29 + if (bfs_queue.empty()) {
1.30 + bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
1.31 + actual_edge=bfs_queue.front().second;
1.32 + if (actual_edge.valid()) {
1.33 + NodeIt w=G.bNode(actual_edge);
1.34 + if (!reached.get(w)) {
1.35 + bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
1.36 + reached.set(w, true);
1.37 + b_node_newly_reached=true;
1.38 + } else {
1.39 + b_node_newly_reached=false;
1.40 + }
1.41 + } //else {
1.42 + //}
1.43 + } else {
1.44 + bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
1.45 + }
1.46 + }
1.47 + BfsIterator3<Graph, OutEdgeIt, ReachedMap>&
1.48 + operator++() {
1.49 + if (bfs_queue.front().second.valid()) {
1.50 + ++(bfs_queue.front().second);
1.51 + actual_edge=bfs_queue.front().second;
1.52 + if (actual_edge.valid()) {
1.53 + NodeIt w=G.bNode(actual_edge);
1.54 + if (!reached.get(w)) {
1.55 + bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
1.56 + reached.set(w, true);
1.57 + b_node_newly_reached=true;
1.58 + } else {
1.59 + b_node_newly_reached=false;
1.60 + }
1.61 + }
1.62 + } else {
1.63 + bfs_queue.pop();
1.64 + if (!bfs_queue.empty()) {
1.65 + actual_edge=bfs_queue.front().second;
1.66 + if (actual_edge.valid()) {
1.67 + NodeIt w=G.bNode(actual_edge);
1.68 + if (!reached.get(w)) {
1.69 + bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
1.70 + reached.set(w, true);
1.71 + b_node_newly_reached=true;
1.72 + } else {
1.73 + b_node_newly_reached=false;
1.74 + }
1.75 + }
1.76 + }
1.77 + }
1.78 + return *this;
1.79 + }
1.80 + bool finished() const { return bfs_queue.empty(); }
1.81 + operator OutEdgeIt () const { return actual_edge; }
1.82 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.83 + bool isANodeExamined() const { return !(actual_edge.valid()); }
1.84 + NodeIt aNode() const { return bfs_queue.front().first; }
1.85 + NodeIt bNode() const { return G.bNode(actual_edge); }
1.86 + const ReachedMap& getReachedMap() const { return reached; }
1.87 + //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
1.88 + };
1.89 +
1.90 + template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.91 + class BfsIterator4 {
1.92 + typedef typename Graph::NodeIt NodeIt;
1.93 + const Graph& G;
1.94 + std::queue<NodeIt> bfs_queue;
1.95 + ReachedMap reached;
1.96 + bool b_node_newly_reached;
1.97 + OutEdgeIt actual_edge;
1.98 + public:
1.99 + BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { }
1.100 + void pushAndSetReached(NodeIt s) {
1.101 + reached.set(s, true);
1.102 + if (bfs_queue.empty()) {
1.103 + bfs_queue.push(s);
1.104 + G.getFirst(actual_edge, s);
1.105 + if (actual_edge.valid()) {
1.106 + NodeIt w=G.bNode(actual_edge);
1.107 + if (!reached.get(w)) {
1.108 + bfs_queue.push(w);
1.109 + reached.set(w, true);
1.110 + b_node_newly_reached=true;
1.111 + } else {
1.112 + b_node_newly_reached=false;
1.113 + }
1.114 + }
1.115 + } else {
1.116 + bfs_queue.push(s);
1.117 + }
1.118 + }
1.119 + BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
1.120 + operator++() {
1.121 + if (actual_edge.valid()) {
1.122 + ++actual_edge;
1.123 + if (actual_edge.valid()) {
1.124 + NodeIt w=G.bNode(actual_edge);
1.125 + if (!reached.get(w)) {
1.126 + bfs_queue.push(w);
1.127 + reached.set(w, true);
1.128 + b_node_newly_reached=true;
1.129 + } else {
1.130 + b_node_newly_reached=false;
1.131 + }
1.132 + }
1.133 + } else {
1.134 + bfs_queue.pop();
1.135 + if (!bfs_queue.empty()) {
1.136 + G.getFirst(actual_edge, bfs_queue.front());
1.137 + if (actual_edge.valid()) {
1.138 + NodeIt w=G.bNode(actual_edge);
1.139 + if (!reached.get(w)) {
1.140 + bfs_queue.push(w);
1.141 + reached.set(w, true);
1.142 + b_node_newly_reached=true;
1.143 + } else {
1.144 + b_node_newly_reached=false;
1.145 + }
1.146 + }
1.147 + }
1.148 + }
1.149 + return *this;
1.150 + }
1.151 + bool finished() const { return bfs_queue.empty(); }
1.152 + operator OutEdgeIt () const { return actual_edge; }
1.153 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.154 + bool isANodeExamined() const { return !(actual_edge.valid()); }
1.155 + NodeIt aNode() const { return bfs_queue.front(); }
1.156 + NodeIt bNode() const { return G.bNode(actual_edge); }
1.157 + const ReachedMap& getReachedMap() const { return reached; }
1.158 + const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
1.159 + };
1.160 +
1.161 +
1.162 + template <typename GraphWrapper, typename ReachedMap>
1.163 + class BfsIterator5 {
1.164 + typedef typename GraphWrapper::NodeIt NodeIt;
1.165 + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.166 + GraphWrapper gw;
1.167 + std::queue<NodeIt> bfs_queue;
1.168 + ReachedMap reached;
1.169 + bool b_node_newly_reached;
1.170 + OutEdgeIt actual_edge;
1.171 + public:
1.172 + BfsIterator5(GraphWrapper _gw) :
1.173 + gw(_gw), reached(_gw.getGraph()) { }
1.174 + void pushAndSetReached(NodeIt s) {
1.175 + reached.set(s, true);
1.176 + if (bfs_queue.empty()) {
1.177 + bfs_queue.push(s);
1.178 + gw.getFirst(actual_edge, s);
1.179 + if (actual_edge.valid()) {
1.180 + NodeIt w=gw.bNode(actual_edge);
1.181 + if (!reached.get(w)) {
1.182 + bfs_queue.push(w);
1.183 + reached.set(w, true);
1.184 + b_node_newly_reached=true;
1.185 + } else {
1.186 + b_node_newly_reached=false;
1.187 + }
1.188 + }
1.189 + } else {
1.190 + bfs_queue.push(s);
1.191 + }
1.192 + }
1.193 + BfsIterator5<GraphWrapper, ReachedMap>&
1.194 + operator++() {
1.195 + if (actual_edge.valid()) {
1.196 + ++actual_edge;
1.197 + if (actual_edge.valid()) {
1.198 + NodeIt w=gw.bNode(actual_edge);
1.199 + if (!reached.get(w)) {
1.200 + bfs_queue.push(w);
1.201 + reached.set(w, true);
1.202 + b_node_newly_reached=true;
1.203 + } else {
1.204 + b_node_newly_reached=false;
1.205 + }
1.206 + }
1.207 + } else {
1.208 + bfs_queue.pop();
1.209 + if (!bfs_queue.empty()) {
1.210 + gw.getFirst(actual_edge, bfs_queue.front());
1.211 + if (actual_edge.valid()) {
1.212 + NodeIt w=gw.bNode(actual_edge);
1.213 + if (!reached.get(w)) {
1.214 + bfs_queue.push(w);
1.215 + reached.set(w, true);
1.216 + b_node_newly_reached=true;
1.217 + } else {
1.218 + b_node_newly_reached=false;
1.219 + }
1.220 + }
1.221 + }
1.222 + }
1.223 + return *this;
1.224 + }
1.225 + bool finished() const { return bfs_queue.empty(); }
1.226 + operator OutEdgeIt () const { return actual_edge; }
1.227 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.228 + bool isANodeExamined() const { return !(actual_edge.valid()); }
1.229 + NodeIt aNode() const { return bfs_queue.front(); }
1.230 + NodeIt bNode() const { return gw.bNode(actual_edge); }
1.231 + const ReachedMap& getReachedMap() const { return reached; }
1.232 + const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
1.233 + };
1.234 +
1.235 +
1.236 +
1.237 } // namespace marci
1.238
1.239 #endif //BFS_ITERATOR_HH
2.1 --- a/src/work/edmonds_karp.hh Mon Feb 16 10:57:01 2004 +0000
2.2 +++ b/src/work/edmonds_karp.hh Mon Feb 16 11:29:48 2004 +0000
2.3 @@ -2,12 +2,14 @@
2.4 #define EDMONDS_KARP_HH
2.5
2.6 #include <algorithm>
2.7 +#include <list>
2.8 +#include <iterator>
2.9
2.10 #include <bfs_iterator.hh>
2.11
2.12 namespace marci {
2.13
2.14 - template<typename Graph, typename T, typename FlowMap, typename CapacityMap>
2.15 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.16 class ResGraph {
2.17 typedef typename Graph::NodeIt NodeIt;
2.18 typedef typename Graph::EachNodeIt EachNodeIt;
2.19 @@ -26,14 +28,14 @@
2.20 friend class OutEdgeIt;
2.21
2.22 class EdgeIt {
2.23 - friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
2.24 + friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
2.25 protected:
2.26 - const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;
2.27 + const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
2.28 OldSymEdgeIt sym;
2.29 public:
2.30 EdgeIt() { }
2.31 //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
2.32 - T free() const {
2.33 + Number free() const {
2.34 if (resG->G.aNode(sym)==resG->G.tail(sym)) {
2.35 return (resG->capacity.get(sym)-resG->flow.get(sym));
2.36 } else {
2.37 @@ -41,22 +43,24 @@
2.38 }
2.39 }
2.40 bool valid() const { return sym.valid(); }
2.41 - void augment(T a) const {
2.42 + void augment(Number a) const {
2.43 if (resG->G.aNode(sym)==resG->G.tail(sym)) {
2.44 resG->flow.set(sym, resG->flow.get(sym)+a);
2.45 + //resG->flow[sym]+=a;
2.46 } else {
2.47 resG->flow.set(sym, resG->flow.get(sym)-a);
2.48 + //resG->flow[sym]-=a;
2.49 }
2.50 }
2.51 };
2.52
2.53 class OutEdgeIt : public EdgeIt {
2.54 - friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
2.55 + friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
2.56 public:
2.57 OutEdgeIt() { }
2.58 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
2.59 private:
2.60 - OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) {
2.61 + OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
2.62 resG=&_resG;
2.63 sym=resG->G.template first<OldSymEdgeIt>(v);
2.64 while( sym.valid() && !(free()>0) ) { ++sym; }
2.65 @@ -76,6 +80,131 @@
2.66
2.67 template< typename It >
2.68 It first() const {
2.69 + It e;
2.70 + getFirst(e);
2.71 + return e;
2.72 + }
2.73 +
2.74 + template< typename It >
2.75 + It first(NodeIt v) const {
2.76 + It e;
2.77 + getFirst(e, v);
2.78 + return e;
2.79 + }
2.80 +
2.81 + NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
2.82 + NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
2.83 +
2.84 + NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
2.85 + NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
2.86 +
2.87 + int id(NodeIt v) const { return G.id(v); }
2.88 +
2.89 + template <typename S>
2.90 + class NodeMap {
2.91 + typename Graph::NodeMap<S> node_map;
2.92 + public:
2.93 + NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
2.94 + NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
2.95 + void set(NodeIt nit, S a) { node_map.set(nit, a); }
2.96 + S get(NodeIt nit) const { return node_map.get(nit); }
2.97 + S& operator[](NodeIt nit) { return node_map[nit]; }
2.98 + const S& operator[](NodeIt nit) const { return node_map[nit]; }
2.99 + };
2.100 +
2.101 + };
2.102 +
2.103 +
2.104 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.105 + class ResGraph2 {
2.106 + typedef typename Graph::NodeIt NodeIt;
2.107 + typedef typename Graph::EachNodeIt EachNodeIt;
2.108 + //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
2.109 + typedef typename Graph::OutEdgeIt OldOutEdgeIt;
2.110 + typedef typename Graph::InEdgeIt OldInEdgeIt;
2.111 +
2.112 + const Graph& G;
2.113 + FlowMap& flow;
2.114 + const CapacityMap& capacity;
2.115 + public:
2.116 + ResGraph2(const Graph& _G, FlowMap& _flow,
2.117 + const CapacityMap& _capacity) :
2.118 + G(_G), flow(_flow), capacity(_capacity) { }
2.119 +
2.120 + class EdgeIt;
2.121 + class OutEdgeIt;
2.122 + friend class EdgeIt;
2.123 + friend class OutEdgeIt;
2.124 +
2.125 + class EdgeIt {
2.126 + friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
2.127 + protected:
2.128 + const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
2.129 + //OldSymEdgeIt sym;
2.130 + OldOutEdgeIt out;
2.131 + OldInEdgeIt in;
2.132 + bool out_or_in; //1, iff out
2.133 + public:
2.134 + EdgeIt() : out_or_in(1) { }
2.135 + Number free() const {
2.136 + if (out_or_in) {
2.137 + return (resG->capacity.get(out)-resG->flow.get(out));
2.138 + } else {
2.139 + return (resG->flow.get(in));
2.140 + }
2.141 + }
2.142 + bool valid() const {
2.143 + return out_or_in && out.valid() || in.valid(); }
2.144 + void augment(Number a) const {
2.145 + if (out_or_in) {
2.146 + resG->flow.set(out, resG->flow.get(out)+a);
2.147 + } else {
2.148 + resG->flow.set(in, resG->flow.get(in)-a);
2.149 + }
2.150 + }
2.151 + };
2.152 +
2.153 + class OutEdgeIt : public EdgeIt {
2.154 + friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
2.155 + public:
2.156 + OutEdgeIt() { }
2.157 + private:
2.158 + OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
2.159 + resG=&_resG;
2.160 + out=resG->G.template first<OldOutEdgeIt>(v);
2.161 + while( out.valid() && !(free()>0) ) { ++out; }
2.162 + if (!out.valid()) {
2.163 + out_or_in=0;
2.164 + in=resG->G.template first<OldInEdgeIt>(v);
2.165 + while( in.valid() && !(free()>0) ) { ++in; }
2.166 + }
2.167 + }
2.168 + public:
2.169 + OutEdgeIt& operator++() {
2.170 + if (out_or_in) {
2.171 + NodeIt v=resG->G.aNode(out);
2.172 + ++out;
2.173 + while( out.valid() && !(free()>0) ) { ++out; }
2.174 + if (!out.valid()) {
2.175 + out_or_in=0;
2.176 + in=resG->G.template first<OldInEdgeIt>(v);
2.177 + while( in.valid() && !(free()>0) ) { ++in; }
2.178 + }
2.179 + } else {
2.180 + ++in;
2.181 + while( in.valid() && !(free()>0) ) { ++in; }
2.182 + }
2.183 + return *this;
2.184 + }
2.185 + };
2.186 +
2.187 + void getFirst(OutEdgeIt& e, NodeIt v) const {
2.188 + e=OutEdgeIt(*this, v);
2.189 + }
2.190 + void getFirst(EachNodeIt& v) const { G.getFirst(v); }
2.191 +
2.192 + template< typename It >
2.193 + It first() const {
2.194 It e;
2.195 getFirst(e);
2.196 return e;
2.197 @@ -88,11 +217,15 @@
2.198 return e;
2.199 }
2.200
2.201 - NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
2.202 - NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
2.203 + NodeIt tail(EdgeIt e) const {
2.204 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
2.205 + NodeIt head(EdgeIt e) const {
2.206 + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
2.207
2.208 - NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
2.209 - NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
2.210 + NodeIt aNode(OutEdgeIt e) const {
2.211 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
2.212 + NodeIt bNode(OutEdgeIt e) const {
2.213 + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
2.214
2.215 int id(NodeIt v) const { return G.id(v); }
2.216
2.217 @@ -100,15 +233,146 @@
2.218 class NodeMap {
2.219 typename Graph::NodeMap<S> node_map;
2.220 public:
2.221 - NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
2.222 - NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
2.223 + NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
2.224 + NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
2.225 + void set(NodeIt nit, S a) { node_map.set(nit, a); }
2.226 + S get(NodeIt nit) const { return node_map.get(nit); }
2.227 + };
2.228 + };
2.229 +
2.230 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.231 + class ResGraph3 {
2.232 + typedef typename Graph::NodeIt NodeIt;
2.233 + typedef typename Graph::EachNodeIt EachNodeIt;
2.234 + //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
2.235 + typedef typename Graph::OutEdgeIt OldOutEdgeIt;
2.236 + typedef typename Graph::InEdgeIt OldInEdgeIt;
2.237 +
2.238 + const Graph& G;
2.239 + FlowMap& flow;
2.240 + const CapacityMap& capacity;
2.241 + public:
2.242 + ResGraph3(const Graph& _G, FlowMap& _flow,
2.243 + const CapacityMap& _capacity) :
2.244 + G(_G), flow(_flow), capacity(_capacity) { }
2.245 +
2.246 + class EdgeIt;
2.247 + class OutEdgeIt;
2.248 + friend class EdgeIt;
2.249 + friend class OutEdgeIt;
2.250 +
2.251 + class EdgeIt {
2.252 + friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
2.253 + protected:
2.254 + //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
2.255 + const Graph* G;
2.256 + FlowMap* flow;
2.257 + const CapacityMap* capacity;
2.258 + //OldSymEdgeIt sym;
2.259 + OldOutEdgeIt out;
2.260 + OldInEdgeIt in;
2.261 + bool out_or_in; //1, iff out
2.262 + public:
2.263 + EdgeIt() : out_or_in(1) { }
2.264 + Number free() const {
2.265 + if (out_or_in) {
2.266 + return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
2.267 + } else {
2.268 + return (/*resG->*/flow->get(in));
2.269 + }
2.270 + }
2.271 + bool valid() const {
2.272 + return out_or_in && out.valid() || in.valid(); }
2.273 + void augment(Number a) const {
2.274 + if (out_or_in) {
2.275 + /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
2.276 + } else {
2.277 + /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
2.278 + }
2.279 + }
2.280 + };
2.281 +
2.282 + class OutEdgeIt : public EdgeIt {
2.283 + friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
2.284 + public:
2.285 + OutEdgeIt() { }
2.286 + private:
2.287 + OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {
2.288 + G=&_G;
2.289 + flow=&_flow;
2.290 + capacity=&_capacity;
2.291 + out=/*resG->*/G->template first<OldOutEdgeIt>(v);
2.292 + while( out.valid() && !(free()>0) ) { ++out; }
2.293 + if (!out.valid()) {
2.294 + out_or_in=0;
2.295 + in=/*resG->*/G->template first<OldInEdgeIt>(v);
2.296 + while( in.valid() && !(free()>0) ) { ++in; }
2.297 + }
2.298 + }
2.299 + public:
2.300 + OutEdgeIt& operator++() {
2.301 + if (out_or_in) {
2.302 + NodeIt v=/*resG->*/G->aNode(out);
2.303 + ++out;
2.304 + while( out.valid() && !(free()>0) ) { ++out; }
2.305 + if (!out.valid()) {
2.306 + out_or_in=0;
2.307 + in=/*resG->*/G->template first<OldInEdgeIt>(v);
2.308 + while( in.valid() && !(free()>0) ) { ++in; }
2.309 + }
2.310 + } else {
2.311 + ++in;
2.312 + while( in.valid() && !(free()>0) ) { ++in; }
2.313 + }
2.314 + return *this;
2.315 + }
2.316 + };
2.317 +
2.318 + void getFirst(OutEdgeIt& e, NodeIt v) const {
2.319 + e=OutEdgeIt(G, v, flow, capacity);
2.320 + }
2.321 + void getFirst(EachNodeIt& v) const { G.getFirst(v); }
2.322 +
2.323 + template< typename It >
2.324 + It first() const {
2.325 + It e;
2.326 + getFirst(e);
2.327 + return e;
2.328 + }
2.329 +
2.330 + template< typename It >
2.331 + It first(NodeIt v) const {
2.332 + It e;
2.333 + getFirst(e, v);
2.334 + return e;
2.335 + }
2.336 +
2.337 + NodeIt tail(EdgeIt e) const {
2.338 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
2.339 + NodeIt head(EdgeIt e) const {
2.340 + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
2.341 +
2.342 + NodeIt aNode(OutEdgeIt e) const {
2.343 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
2.344 + NodeIt bNode(OutEdgeIt e) const {
2.345 + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
2.346 +
2.347 + int id(NodeIt v) const { return G.id(v); }
2.348 +
2.349 + template <typename S>
2.350 + class NodeMap {
2.351 + typename Graph::NodeMap<S> node_map;
2.352 + public:
2.353 + NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
2.354 + NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
2.355 void set(NodeIt nit, S a) { node_map.set(nit, a); }
2.356 S get(NodeIt nit) const { return node_map.get(nit); }
2.357 };
2.358
2.359 };
2.360
2.361 - template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
2.362 +
2.363 + template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.364 class MaxFlow {
2.365 typedef typename Graph::NodeIt NodeIt;
2.366 typedef typename Graph::EdgeIt EdgeIt;
2.367 @@ -120,21 +384,30 @@
2.368 NodeIt t;
2.369 FlowMap& flow;
2.370 const CapacityMap& capacity;
2.371 - typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
2.372 + typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
2.373 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
2.374 typedef typename AugGraph::EdgeIt AugEdgeIt;
2.375 +
2.376 + //AugGraph res_graph;
2.377 + //typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.378 + //typename AugGraph::NodeMap<AugEdgeIt> pred;
2.379 + //typename AugGraph::NodeMap<int> free;
2.380 public:
2.381 - MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
2.382 + MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
2.383 + G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //,
2.384 + //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
2.385 + { }
2.386 bool augment() {
2.387 AugGraph res_graph(G, flow, capacity);
2.388 bool _augment=false;
2.389
2.390 typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.391 - BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
2.392 + BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
2.393 res_bfs.pushAndSetReached(s);
2.394
2.395 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
2.396 - //filled with invalid iterators
2.397 + //filled up with invalid iterators
2.398 + //pred.set(s, AugEdgeIt());
2.399
2.400 typename AugGraph::NodeMap<int> free(res_graph);
2.401
2.402 @@ -158,7 +431,7 @@
2.403
2.404 if (_augment) {
2.405 NodeIt n=t;
2.406 - T augment_value=free.get(t);
2.407 + Number augment_value=free.get(t);
2.408 while (pred.get(n).valid()) {
2.409 AugEdgeIt e=pred.get(n);
2.410 e.augment(augment_value);
2.411 @@ -171,8 +444,8 @@
2.412 void run() {
2.413 while (augment()) { }
2.414 }
2.415 - T flowValue() {
2.416 - T a=0;
2.417 + Number flowValue() {
2.418 + Number a=0;
2.419 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
2.420 a+=flow.get(i);
2.421 }
2.422 @@ -180,6 +453,153 @@
2.423 }
2.424 };
2.425
2.426 +
2.427 +/*
2.428 + template <typename Graph>
2.429 + class IteratorBoolNodeMap {
2.430 + typedef typename Graph::NodeIt NodeIt;
2.431 + typedef typename Graph::EachNodeIt EachNodeIt;
2.432 + class BoolItem {
2.433 + public:
2.434 + bool value;
2.435 + NodeIt prev;
2.436 + NodeIt next;
2.437 + BoolItem() : value(false), prev(), next() {}
2.438 + };
2.439 + NodeIt first_true;
2.440 + //NodeIt last_true;
2.441 + NodeIt first_false;
2.442 + //NodeIt last_false;
2.443 + const Graph& G;
2.444 + typename Graph::NodeMap<BoolItem> container;
2.445 + public:
2.446 + typedef bool ValueType;
2.447 + typedef NodeIt KeyType;
2.448 + IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {
2.449 + //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
2.450 + //BoolItem b=container.get(e);
2.451 + //b.me=e;
2.452 + //container.set(b);
2.453 + //}
2.454 + G.getFirst(first_false);
2.455 + NodeIt e_prev;
2.456 + for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
2.457 + container[e].prev=e_prev;
2.458 + if (e_prev.valid()) container[e_prev].next=e;
2.459 + e_prev=e;
2.460 + }
2.461 + }
2.462 + //NodeMap(const Graph& _G, T a) :
2.463 + // G(_G), container(G.node_id, a) { }
2.464 + //FIXME
2.465 + void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
2.466 + T get(NodeIt nit) const { return container[G.id(nit)]; }
2.467 + //void resize() { container.resize(G.node_id); }
2.468 + //void resize(T a) { container.resize(G.node_id, a); }
2.469 + };
2.470 +*/
2.471 +
2.472 +
2.473 + template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
2.474 + class MaxFlow2 {
2.475 + typedef typename Graph::NodeIt NodeIt;
2.476 + typedef typename Graph::EdgeIt EdgeIt;
2.477 + typedef typename Graph::EachEdgeIt EachEdgeIt;
2.478 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.479 + typedef typename Graph::InEdgeIt InEdgeIt;
2.480 + const Graph& G;
2.481 + std::list<NodeIt>& S;
2.482 + std::list<NodeIt>& T;
2.483 + FlowMap& flow;
2.484 + const CapacityMap& capacity;
2.485 + typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
2.486 + typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
2.487 + typedef typename AugGraph::EdgeIt AugEdgeIt;
2.488 + typename Graph::NodeMap<bool> SMap;
2.489 + typename Graph::NodeMap<bool> TMap;
2.490 + public:
2.491 + MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
2.492 + for(typename std::list<NodeIt>::const_iterator i=S.begin();
2.493 + i!=S.end(); ++i) {
2.494 + SMap.set(*i, true);
2.495 + }
2.496 + for (typename std::list<NodeIt>::const_iterator i=T.begin();
2.497 + i!=T.end(); ++i) {
2.498 + TMap.set(*i, true);
2.499 + }
2.500 + }
2.501 + bool augment() {
2.502 + AugGraph res_graph(G, flow, capacity);
2.503 + bool _augment=false;
2.504 + NodeIt reached_t_node;
2.505 +
2.506 + typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.507 + BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
2.508 + for(typename std::list<NodeIt>::const_iterator i=S.begin();
2.509 + i!=S.end(); ++i) {
2.510 + res_bfs.pushAndSetReached(*i);
2.511 + }
2.512 + //res_bfs.pushAndSetReached(s);
2.513 +
2.514 + typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
2.515 + //filled up with invalid iterators
2.516 +
2.517 + typename AugGraph::NodeMap<int> free(res_graph);
2.518 +
2.519 + //searching for augmenting path
2.520 + while ( !res_bfs.finished() ) {
2.521 + AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
2.522 + if (e.valid() && res_bfs.isBNodeNewlyReached()) {
2.523 + NodeIt v=res_graph.tail(e);
2.524 + NodeIt w=res_graph.head(e);
2.525 + pred.set(w, e);
2.526 + if (pred.get(v).valid()) {
2.527 + free.set(w, std::min(free.get(v), e.free()));
2.528 + } else {
2.529 + free.set(w, e.free());
2.530 + }
2.531 + if (TMap.get(res_graph.head(e))) {
2.532 + _augment=true;
2.533 + reached_t_node=res_graph.head(e);
2.534 + break;
2.535 + }
2.536 + }
2.537 +
2.538 + ++res_bfs;
2.539 + } //end of searching augmenting path
2.540 +
2.541 + if (_augment) {
2.542 + NodeIt n=reached_t_node;
2.543 + Number augment_value=free.get(reached_t_node);
2.544 + while (pred.get(n).valid()) {
2.545 + AugEdgeIt e=pred.get(n);
2.546 + e.augment(augment_value);
2.547 + n=res_graph.tail(e);
2.548 + }
2.549 + }
2.550 +
2.551 + return _augment;
2.552 + }
2.553 + void run() {
2.554 + while (augment()) { }
2.555 + }
2.556 + Number flowValue() {
2.557 + Number a=0;
2.558 + for(typename std::list<NodeIt>::const_iterator i=S.begin();
2.559 + i!=S.end(); ++i) {
2.560 + for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
2.561 + a+=flow.get(e);
2.562 + }
2.563 + for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
2.564 + a-=flow.get(e);
2.565 + }
2.566 + }
2.567 + return a;
2.568 + }
2.569 + };
2.570 +
2.571 +
2.572 +
2.573 } // namespace marci
2.574
2.575 #endif //EDMONDS_KARP_HH
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/iterator_bfs_demo.cc Mon Feb 16 11:29:48 2004 +0000
3.3 @@ -0,0 +1,129 @@
3.4 +#include <iostream>
3.5 +#include <vector>
3.6 +#include <string>
3.7 +
3.8 +#include <list_graph.hh>
3.9 +#include <bfs_iterator.hh>
3.10 +#include <graph_wrapper.h>
3.11 +
3.12 +using namespace marci;
3.13 +
3.14 +int main (int, char*[])
3.15 +{
3.16 + typedef ListGraph::NodeIt NodeIt;
3.17 + typedef ListGraph::EdgeIt EdgeIt;
3.18 + typedef ListGraph::EachNodeIt EachNodeIt;
3.19 + typedef ListGraph::EachEdgeIt EachEdgeIt;
3.20 + typedef ListGraph::OutEdgeIt OutEdgeIt;
3.21 + typedef ListGraph::InEdgeIt InEdgeIt;
3.22 + typedef ListGraph::SymEdgeIt SymEdgeIt;
3.23 +
3.24 + ListGraph G;
3.25 +
3.26 + NodeIt s=G.addNode();
3.27 + NodeIt v1=G.addNode();
3.28 + NodeIt v2=G.addNode();
3.29 + NodeIt v3=G.addNode();
3.30 + NodeIt v4=G.addNode();
3.31 + NodeIt t=G.addNode();
3.32 +
3.33 + G.addEdge(s, v1);
3.34 + G.addEdge(s, v2);
3.35 + G.addEdge(v1, v2);
3.36 + G.addEdge(v2, v1);
3.37 + G.addEdge(v1, v3);
3.38 + G.addEdge(v3, v2);
3.39 + G.addEdge(v2, v4);
3.40 + G.addEdge(v4, v3);
3.41 + G.addEdge(v3, t);
3.42 + G.addEdge(v4, t);
3.43 +
3.44 + std::cout << "bfs and dfs demo on the directed graph" << std::endl;
3.45 + for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
3.46 + std::cout << i << ": ";
3.47 + std::cout << "out edges: ";
3.48 + for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j)
3.49 + std::cout << j << " ";
3.50 + std::cout << "in edges: ";
3.51 + for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j)
3.52 + std::cout << j << " ";
3.53 + std::cout << std::endl;
3.54 + }
3.55 +
3.56 + {
3.57 + std::cout << "iterator bfs demo 4 ..." << std::endl;
3.58 + BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
3.59 + bfs.pushAndSetReached(s);
3.60 + while (!bfs.finished()) {
3.61 + if (OutEdgeIt(bfs).valid()) {
3.62 + std::cout << "OutEdgeIt: " << bfs;
3.63 + std::cout << " aNode: " << G.aNode(bfs);
3.64 + std::cout << " bNode: " << G.bNode(bfs) << " ";
3.65 + } else {
3.66 + std::cout << "OutEdgeIt: " << "invalid";
3.67 + std::cout << " aNode: " << bfs.aNode();
3.68 + std::cout << " bNode: " << "invalid" << " ";
3.69 + }
3.70 + if (bfs.isBNodeNewlyReached()) {
3.71 + std::cout << "bNodeIsNewlyReached ";
3.72 + } else {
3.73 + std::cout << "bNodeIsNotNewlyReached ";
3.74 + }
3.75 + if (bfs.isANodeExamined()) {
3.76 + std::cout << "aNodeIsExamined ";
3.77 + } else {
3.78 + std::cout << "aNodeIsNotExamined ";
3.79 + }
3.80 + std::cout<<std::endl;
3.81 + ++bfs;
3.82 + }
3.83 + }
3.84 +
3.85 + typedef ConstTrivGraphWrapper<ListGraph> CTGW;
3.86 + CTGW wG(G);
3.87 +
3.88 + std::cout << "bfs and dfs demo on the directed graph" << std::endl;
3.89 + for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) {
3.90 + std::cout << i << ": ";
3.91 + std::cout << "out edges: ";
3.92 + for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j)
3.93 + std::cout << j << " ";
3.94 + std::cout << "in edges: ";
3.95 + for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j)
3.96 + std::cout << j << " ";
3.97 + std::cout << std::endl;
3.98 + }
3.99 +
3.100 +
3.101 + {
3.102 + std::cout << "iterator bfs demo 5 ..." << std::endl;
3.103 + BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG);
3.104 + bfs.pushAndSetReached(s);
3.105 + while (!bfs.finished()) {
3.106 + if (OutEdgeIt(bfs).valid()) {
3.107 + std::cout << "OutEdgeIt: " << bfs;
3.108 + std::cout << " aNode: " << wG.aNode(bfs);
3.109 + std::cout << " bNode: " << wG.bNode(bfs) << " ";
3.110 + } else {
3.111 + std::cout << "OutEdgeIt: " << "invalid";
3.112 + std::cout << " aNode: " << bfs.aNode();
3.113 + std::cout << " bNode: " << "invalid" << " ";
3.114 + }
3.115 + if (bfs.isBNodeNewlyReached()) {
3.116 + std::cout << "bNodeIsNewlyReached ";
3.117 + } else {
3.118 + std::cout << "bNodeIsNotNewlyReached ";
3.119 + }
3.120 + if (bfs.isANodeExamined()) {
3.121 + std::cout << "aNodeIsExamined ";
3.122 + } else {
3.123 + std::cout << "aNodeIsNotExamined ";
3.124 + }
3.125 + std::cout<<std::endl;
3.126 + ++bfs;
3.127 + }
3.128 + }
3.129 +
3.130 +
3.131 + return 0;
3.132 +}
4.1 --- a/src/work/list_graph.hh Mon Feb 16 10:57:01 2004 +0000
4.2 +++ b/src/work/list_graph.hh Mon Feb 16 11:29:48 2004 +0000
4.3 @@ -44,8 +44,10 @@
4.4 NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { }
4.5 NodeMap(const ListGraph& _G, T a) :
4.6 G(_G), container(G.node_id, a) { }
4.7 - void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
4.8 - T get(NodeIt nit) const { return container[G.id(nit)]; }
4.9 + void set(NodeIt n, T a) { container[/*G.id(n)*/n.node->id]=a; }
4.10 + T get(NodeIt n) const { return container[/*G.id(n)*/n.node->id]; }
4.11 + T& operator[](NodeIt n) { return container[/*G.id(n)*/n.node->id]; }
4.12 + const T& operator[](NodeIt n) const { return container[/*G.id(n)*/n.node->id]; }
4.13 void resize() { container.resize(G.node_id); }
4.14 void resize(T a) { container.resize(G.node_id, a); }
4.15 };
4.16 @@ -60,8 +62,10 @@
4.17 EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { }
4.18 EdgeMap(const ListGraph& _G, T a) :
4.19 G(_G), container(G.edge_id, a) { }
4.20 - void set(EdgeIt eit, T a) { container[G.id(eit)]=a; }
4.21 - T get(EdgeIt eit) const { return container[G.id(eit)]; }
4.22 + void set(EdgeIt e, T a) { container[/*G.id(e)*/e.edge->id]=a; }
4.23 + T get(EdgeIt e) const { return container[/*G.id(e)*/e.edge->id]; }
4.24 + T& operator[](EdgeIt e) { return container[/*G.id(e)*/e.edge->id]; }
4.25 + const T& operator[](EdgeIt e) const { return container[/*G.id(e)*/e.edge->id]; }
4.26 void resize() { container.resize(G.edge_id); }
4.27 void resize(T a) { container.resize(G.edge_id, a); }
4.28 };
4.29 @@ -76,6 +80,8 @@
4.30
4.31 class node_item {
4.32 friend class ListGraph;
4.33 + template <typename T> friend class NodeMap;
4.34 +
4.35 friend class NodeIt;
4.36 friend class EachNodeIt;
4.37 friend class EdgeIt;
4.38 @@ -99,6 +105,8 @@
4.39
4.40 class edge_item {
4.41 friend class ListGraph;
4.42 + template <typename T> friend class EdgeMap;
4.43 +
4.44 friend class NodeIt;
4.45 friend class EachNodeIt;
4.46 friend class EdgeIt;
4.47 @@ -254,11 +262,16 @@
4.48 /* same methods in other style */
4.49 /* for experimental purpose */
4.50
4.51 - void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); }
4.52 - void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); }
4.53 - void getFirst(OutEdgeIt& e, NodeIt v) const { e=OutEdgeIt(v); }
4.54 - void getFirst(InEdgeIt& e, NodeIt v) const { e=InEdgeIt(v); }
4.55 - void getFirst(SymEdgeIt& e, NodeIt v) const { e=SymEdgeIt(v); }
4.56 + EachNodeIt& getFirst(EachNodeIt& v) const {
4.57 + v=EachNodeIt(*this); return v; }
4.58 + EachEdgeIt& getFirst(EachEdgeIt& e) const {
4.59 + e=EachEdgeIt(*this); return e; }
4.60 + OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const {
4.61 + e=OutEdgeIt(v); return e; }
4.62 + InEdgeIt& getFirst(InEdgeIt& e, NodeIt v) const {
4.63 + e=InEdgeIt(v); return e; }
4.64 + SymEdgeIt& getFirst(SymEdgeIt& e, NodeIt v) const {
4.65 + e=SymEdgeIt(v); return e; }
4.66 //void getTail(NodeIt& n, const EdgeIt& e) const { n=tail(e); }
4.67 //void getHead(NodeIt& n, const EdgeIt& e) const { n=head(e); }
4.68
4.69 @@ -333,6 +346,7 @@
4.70
4.71 class NodeIt {
4.72 friend class ListGraph;
4.73 + template <typename T> friend class NodeMap;
4.74
4.75 friend class EdgeIt;
4.76 friend class OutEdgeIt;
4.77 @@ -367,6 +381,7 @@
4.78
4.79 class EdgeIt {
4.80 friend class ListGraph;
4.81 + template <typename T> friend class EdgeMap;
4.82
4.83 friend class NodeIt;
4.84 friend class EachNodeIt;
4.85 @@ -413,53 +428,52 @@
4.86
4.87 class OutEdgeIt : public EdgeIt {
4.88 friend class ListGraph;
4.89 - node_item* v;
4.90 + //node_item* v;
4.91 protected:
4.92 - OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
4.93 + OutEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
4.94 public:
4.95 - OutEdgeIt() : EdgeIt(), v(0) { }
4.96 - OutEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
4.97 + OutEdgeIt() : EdgeIt()/*, v(0)*/ { }
4.98 + OutEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
4.99 OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
4.100 protected:
4.101 - NodeIt aNode() const { return NodeIt(v); }
4.102 - NodeIt bNode() const {
4.103 - return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
4.104 + NodeIt aNode() const { return NodeIt(edge->_tail); }
4.105 + NodeIt bNode() const { return NodeIt(edge->_head); }
4.106 };
4.107
4.108 class InEdgeIt : public EdgeIt {
4.109 friend class ListGraph;
4.110 - node_item* v;
4.111 + //node_item* v;
4.112 protected:
4.113 - InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; }
4.114 + InEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
4.115 public:
4.116 - InEdgeIt() : EdgeIt(), v(0) { }
4.117 - InEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
4.118 + InEdgeIt() : EdgeIt()/*, v(0)*/ { }
4.119 + InEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
4.120 InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
4.121 protected:
4.122 - NodeIt aNode() const { return NodeIt(v); }
4.123 - NodeIt bNode() const {
4.124 - return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
4.125 + NodeIt aNode() const { return NodeIt(edge->_head); }
4.126 + NodeIt bNode() const { return NodeIt(edge->_tail); }
4.127 };
4.128
4.129 class SymEdgeIt : public EdgeIt {
4.130 friend class ListGraph;
4.131 bool out_or_in; //1 iff out, 0 iff in
4.132 - node_item* v;
4.133 + //node_item* v;
4.134 protected:
4.135 - SymEdgeIt(const NodeIt& _v) : v(_v.node) {
4.136 + SymEdgeIt(const NodeIt& _v) /*: v(_v.node)*/ {
4.137 out_or_in=1;
4.138 - edge=v->_first_out_edge;
4.139 - if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
4.140 + edge=_v.node->_first_out_edge;
4.141 + if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
4.142 }
4.143 public:
4.144 - SymEdgeIt() : EdgeIt(), v(0) { }
4.145 - SymEdgeIt(const ListGraph& G, NodeIt _v) : v(_v.node) {
4.146 + SymEdgeIt() : EdgeIt() /*, v(0)*/ { }
4.147 + SymEdgeIt(const ListGraph& G, NodeIt _v) /*: v(_v.node)*/ {
4.148 out_or_in=1;
4.149 - edge=v->_first_out_edge;
4.150 - if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
4.151 + edge=_v.node->_first_out_edge;
4.152 + if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
4.153 }
4.154 SymEdgeIt& operator++() {
4.155 if (out_or_in) {
4.156 + node_item* v=edge->_tail;
4.157 edge=edge->_next_out;
4.158 if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
4.159 } else {
4.160 @@ -468,9 +482,10 @@
4.161 return *this;
4.162 }
4.163 protected:
4.164 - NodeIt aNode() const { return NodeIt(v); }
4.165 + NodeIt aNode() const {
4.166 + return (out_or_in) ? NodeIt(edge->_tail) : NodeIt(edge->_head); }
4.167 NodeIt bNode() const {
4.168 - return (edge->_tail==v) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
4.169 + return (out_or_in) ? NodeIt(edge->_head) : NodeIt(edge->_tail); }
4.170 };
4.171
4.172 };
5.1 --- a/src/work/marci_graph_demo.cc Mon Feb 16 10:57:01 2004 +0000
5.2 +++ b/src/work/marci_graph_demo.cc Mon Feb 16 11:29:48 2004 +0000
5.3 @@ -94,7 +94,7 @@
5.4 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
5.5 }
5.6 std::cout << std::endl;
5.7 -
5.8 +/*
5.9 std::cout << "bfs from the first node" << std::endl;
5.10 bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
5.11 bfs_test.run();
5.12 @@ -108,7 +108,7 @@
5.13 std::cout << bfs_test.dist.get(i) << " ";
5.14 }
5.15 std::cout<<std::endl;
5.16 -
5.17 +*/
5.18
5.19 std::cout << "augmenting path flow algorithm test..." << std::endl;
5.20 ListGraph flowG;
5.21 @@ -173,7 +173,7 @@
5.22
5.23 //flowG.setTail(v3_t, v2);
5.24 //flowG.setHead(v3_t, s);
5.25 -
5.26 +/*
5.27 for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
5.28 std::cout << node_name.get(i) << ": ";
5.29 std::cout << "out edges: ";
5.30 @@ -188,7 +188,7 @@
5.31 for(EachEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) {
5.32 std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
5.33 }
5.34 -
5.35 +*/
5.36 /*
5.37 while (flowG.first<EachEdgeIt>().valid()) {
5.38 flowG.deleteEdge(flowG.first<EachEdgeIt>());
5.39 @@ -219,19 +219,39 @@
5.40 }
5.41 */
5.42
5.43 - std::cout << std::endl;
5.44 - //std::cout << "meg jo" << std::flush;
5.45 + //std::cout << std::endl;
5.46
5.47 - ListGraph::EdgeMap<int> flow(flowG, 0);
5.48 - MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
5.49 - max_flow_test.run();
5.50
5.51 - std::cout << "maximum flow: "<< std::endl;
5.52 - for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
5.53 - std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
5.54 + {
5.55 + ListGraph::EdgeMap<int> flow(flowG, 0);
5.56 + MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
5.57 + max_flow_test.run();
5.58 +
5.59 + std::cout << "maximum flow: "<< std::endl;
5.60 + for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
5.61 + std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
5.62 + }
5.63 + std::cout<<std::endl;
5.64 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
5.65 }
5.66 - std::cout<<std::endl;
5.67 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
5.68 +
5.69 + {
5.70 + std::list<NodeIt> S;
5.71 + S.push_back(s); S.push_back(v3);
5.72 + std::list<NodeIt> T;
5.73 + T.push_back(t);
5.74 +
5.75 + ListGraph::EdgeMap<int> flow(flowG, 0);
5.76 + MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap);
5.77 + max_flow_test.run();
5.78 +
5.79 + std::cout << "maximum flow: "<< std::endl;
5.80 + for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
5.81 + std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
5.82 + }
5.83 + std::cout<<std::endl;
5.84 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
5.85 + }
5.86
5.87 return 0;
5.88 }