1.1 --- a/src/work/alpar/emptygraph.h Thu Mar 11 23:31:13 2004 +0000
1.2 +++ b/src/work/alpar/emptygraph.h Fri Mar 12 09:19:54 2004 +0000
1.3 @@ -1,4 +1,6 @@
1.4 -// -*-mode: c++; -*-
1.5 +// -*- c++ -*-
1.6 +#ifndef EMPTYGRAPH_H
1.7 +#define EMPTYGRAPH_H
1.8
1.9 #include <invalid.h>
1.10
1.11 @@ -34,7 +36,7 @@
1.12 /// to an undefined value.
1.13 Node() {} //FIXME
1.14 /// Initialize the iterator to be invalid
1.15 - Node(Invalid) {};
1.16 + Node(Invalid) {}
1.17 //Node(const Node &) {}
1.18 bool operator==(Node n) const { return true; } //FIXME
1.19 bool operator!=(Node n) const { return true; } //FIXME
1.20 @@ -47,7 +49,7 @@
1.21 /// to an undefined value.
1.22 NodeIt() {} //FIXME
1.23 /// Initialize the iterator to be invalid
1.24 - NodeIt(Invalid) {};
1.25 + NodeIt(Invalid) {}
1.26 /// Sets the iterator to the first node of \c G.
1.27 NodeIt(const EmptyGraph &G) {}
1.28 NodeIt(const NodeIt &) {} //FIXME
1.29 @@ -61,7 +63,7 @@
1.30 /// to an undefined value.
1.31 Edge() {} //FIXME
1.32 /// Initialize the iterator to be invalid
1.33 - Edge(Invalid) {};
1.34 + Edge(Invalid) {}
1.35 //Edge(const Edge &) {}
1.36 bool operator==(Edge n) const { return true; } //FIXME
1.37 bool operator!=(Edge n) const { return true; } //FIXME
1.38 @@ -75,7 +77,7 @@
1.39 /// to an undefined value.
1.40 OutEdgeIt() {}
1.41 /// Initialize the iterator to be invalid
1.42 - OutEdgeIt(Invalid) {};
1.43 + OutEdgeIt(Invalid) {}
1.44 /// This constructor sets the iterator to first outgoing edge.
1.45
1.46 /// This constructor set the iterator to the first outgoing edge of
1.47 @@ -91,7 +93,7 @@
1.48 /// to an undefined value.
1.49 InEdgeIt() {}
1.50 /// Initialize the iterator to be invalid
1.51 - InEdgeIt(Invalid) {};
1.52 + InEdgeIt(Invalid) {}
1.53 InEdgeIt(const EmptyGraph &, Node) {}
1.54 };
1.55 // class SymEdgeIt : public Edge {};
1.56 @@ -101,7 +103,7 @@
1.57 /// to an undefined value.
1.58 EdgeIt() {}
1.59 /// Initialize the iterator to be invalid
1.60 - EdgeIt(Invalid) {};
1.61 + EdgeIt(Invalid) {}
1.62 EdgeIt(const EmptyGraph &) {}
1.63 };
1.64
1.65 @@ -149,14 +151,14 @@
1.66 // Node bNode(SymEdgeIt) const {}
1.67
1.68 /// Checks if a node iterator is valid
1.69 - bool valid(const Node) const { return true;};
1.70 + bool valid(const Node) const { return true;}
1.71 /// Checks if an edge iterator is valid
1.72 - bool valid(const Edge) const { return true;};
1.73 + bool valid(const Edge) const { return true;}
1.74
1.75 ///Gives back the \e id of a node.
1.76 - int id(const Node) const { return 0;};
1.77 + int id(const Node) const { return 0;}
1.78 ///Gives back the \e id of an edge.
1.79 - int id(const Edge) const { return 0;};
1.80 + int id(const Edge) const { return 0;}
1.81
1.82 //void setInvalid(Node &) const {};
1.83 //void setInvalid(Edge &) const {};
1.84 @@ -172,8 +174,8 @@
1.85 int nodeNum() { return 0;}
1.86 int edgeNum() { return 0;}
1.87
1.88 - EmptyGraph() {};
1.89 - EmptyGraph(const EmptyGraph &G) {};
1.90 + EmptyGraph() {}
1.91 + EmptyGraph(const EmptyGraph &G) {}
1.92
1.93
1.94
1.95 @@ -217,7 +219,7 @@
1.96
1.97 // @}
1.98
1.99 -};
1.100 +} //namespace hugo
1.101
1.102
1.103
1.104 @@ -236,3 +238,5 @@
1.105 // NodeClass getClass(Node n) {}
1.106
1.107 // }
1.108 +
1.109 +#endif // EMPTYGRAPH_H
2.1 --- a/src/work/alpar/smart_graph.h Thu Mar 11 23:31:13 2004 +0000
2.2 +++ b/src/work/alpar/smart_graph.h Fri Mar 12 09:19:54 2004 +0000
2.3 @@ -96,12 +96,14 @@
2.4 Node tail(Edge e) const { return edges[e.n].tail; }
2.5 Node head(Edge e) const { return edges[e.n].head; }
2.6
2.7 -// Node aNode(const OutEdgeIt& e) const { return tail(e); }
2.8 -// Node aNode(const InEdgeIt& e) const { return head(e); }
2.9 + // Marci
2.10 + Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
2.11 + Node aNode(InEdgeIt e) const { return edges[e.n].head; }
2.12 // //Node aNode(const SymEdge& e) const { return e.aNode(); }
2.13
2.14 -// Node bNode(const OutEdgeIt& e) const { return head(e); }
2.15 -// Node bNode(const InEdgeIt& e) const { return tail(e); }
2.16 + // Marci
2.17 + Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
2.18 + Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
2.19 // //Node bNode(const SymEdge& e) const { return e.bNode(); }
2.20
2.21 NodeIt& first(NodeIt& v) const {
2.22 @@ -116,14 +118,16 @@
2.23 template< typename It >
2.24 It first() const {
2.25 It e;
2.26 - getFirst(e);
2.27 + //Marci
2.28 + /*getF*/first(e);
2.29 return e;
2.30 }
2.31
2.32 template< typename It >
2.33 It first(Node v) const {
2.34 It e;
2.35 - getFirst(e, v);
2.36 + //Marci
2.37 + /*getF*/first(e, v);
2.38 return e;
2.39 }
2.40
2.41 @@ -138,7 +142,12 @@
2.42 { It tmp(it); return next(tmp); }
2.43 //{ It tmp; tmp.n=it.n+1; return tmp; }
2.44
2.45 - Node& next(Node& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
2.46 + //FIXME correction Marci: I changed to NodeIt from Node
2.47 + //NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
2.48 + NodeIt& next(NodeIt& it) const {
2.49 + it.n=(it.n+2)%(nodes.size()+1)-1;
2.50 + return it;
2.51 + }
2.52 OutEdgeIt& next(OutEdgeIt& it) const
2.53 { it.n=edges[it.n].next_out; return it; }
2.54 InEdgeIt& next(InEdgeIt& it) const
2.55 @@ -216,7 +225,8 @@
2.56 Edge(int nn) {n=nn;}
2.57 public:
2.58 Edge() { }
2.59 - Edge (Invalid i) { n=-1; }
2.60 + // Marci: kiszedtem az Invalid i-bol az i-t
2.61 + Edge (Invalid) { n=-1; }
2.62 bool operator==(const Edge i) const {return n==i.n;}
2.63 bool operator!=(const Edge i) const {return n!=i.n;}
2.64 bool operator<(const Edge i) const {return n<i.n;}
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/bfs_iterator.h Fri Mar 12 09:19:54 2004 +0000
3.3 @@ -0,0 +1,837 @@
3.4 +// -*- c++ -*-
3.5 +#ifndef BFS_ITERATOR_H
3.6 +#define BFS_ITERATOR_H
3.7 +
3.8 +#include <queue>
3.9 +#include <stack>
3.10 +#include <utility>
3.11 +#include <graph_wrapper.h>
3.12 +
3.13 +namespace hugo {
3.14 +
3.15 + template <typename Graph>
3.16 + struct bfs {
3.17 + typedef typename Graph::Node Node;
3.18 + typedef typename Graph::Edge Edge;
3.19 + typedef typename Graph::NodeIt NodeIt;
3.20 + typedef typename Graph::OutEdgeIt OutEdgeIt;
3.21 + Graph& G;
3.22 + Node s;
3.23 + typename Graph::NodeMap<bool> reached;
3.24 + typename Graph::NodeMap<Edge> pred;
3.25 + typename Graph::NodeMap<int> dist;
3.26 + std::queue<Node> bfs_queue;
3.27 + bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
3.28 + bfs_queue.push(s);
3.29 + for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i)
3.30 + reached.set(i, false);
3.31 + reached.set(s, true);
3.32 + dist.set(s, 0);
3.33 + }
3.34 +
3.35 + void run() {
3.36 + while (!bfs_queue.empty()) {
3.37 + Node v=bfs_queue.front();
3.38 + OutEdgeIt e=G.template first<OutEdgeIt>(v);
3.39 + bfs_queue.pop();
3.40 + for( ; e.valid(); ++e) {
3.41 + Node w=G.bNode(e);
3.42 + std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
3.43 + if (!reached.get(w)) {
3.44 + std::cout << G.id(w) << " is newly reached :-)" << std::endl;
3.45 + bfs_queue.push(w);
3.46 + dist.set(w, dist.get(v)+1);
3.47 + pred.set(w, e);
3.48 + reached.set(w, true);
3.49 + } else {
3.50 + std::cout << G.id(w) << " is already reached" << std::endl;
3.51 + }
3.52 + }
3.53 + }
3.54 + }
3.55 + };
3.56 +
3.57 +// template <typename Graph>
3.58 +// struct bfs_visitor {
3.59 +// typedef typename Graph::Node Node;
3.60 +// typedef typename Graph::Edge Edge;
3.61 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
3.62 +// Graph& G;
3.63 +// bfs_visitor(Graph& _G) : G(_G) { }
3.64 +// void at_previously_reached(OutEdgeIt& e) {
3.65 +// //Node v=G.aNode(e);
3.66 +// Node w=G.bNode(e);
3.67 +// std::cout << G.id(w) << " is already reached" << std::endl;
3.68 +// }
3.69 +// void at_newly_reached(OutEdgeIt& e) {
3.70 +// //Node v=G.aNode(e);
3.71 +// Node w=G.bNode(e);
3.72 +// std::cout << G.id(w) << " is newly reached :-)" << std::endl;
3.73 +// }
3.74 +// };
3.75 +
3.76 +// template <typename Graph, typename ReachedMap, typename visitor_type>
3.77 +// struct bfs_iterator {
3.78 +// typedef typename Graph::Node Node;
3.79 +// typedef typename Graph::Edge Edge;
3.80 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
3.81 +// Graph& G;
3.82 +// std::queue<OutEdgeIt>& bfs_queue;
3.83 +// ReachedMap& reached;
3.84 +// visitor_type& visitor;
3.85 +// void process() {
3.86 +// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
3.87 +// if (bfs_queue.empty()) return;
3.88 +// OutEdgeIt e=bfs_queue.front();
3.89 +// //Node v=G.aNode(e);
3.90 +// Node w=G.bNode(e);
3.91 +// if (!reached.get(w)) {
3.92 +// visitor.at_newly_reached(e);
3.93 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
3.94 +// reached.set(w, true);
3.95 +// } else {
3.96 +// visitor.at_previously_reached(e);
3.97 +// }
3.98 +// }
3.99 +// bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
3.100 +// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
3.101 +// valid();
3.102 +// }
3.103 +// bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {
3.104 +// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
3.105 +// //if (bfs_queue.empty()) return *this;
3.106 +// if (!valid()) return *this;
3.107 +// ++(bfs_queue.front());
3.108 +// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
3.109 +// valid();
3.110 +// return *this;
3.111 +// }
3.112 +// //void next() {
3.113 +// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
3.114 +// // if (bfs_queue.empty()) return;
3.115 +// // ++(bfs_queue.front());
3.116 +// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
3.117 +// //}
3.118 +// bool valid() {
3.119 +// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
3.120 +// if (bfs_queue.empty()) return false; else return true;
3.121 +// }
3.122 +// //bool finished() {
3.123 +// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
3.124 +// // if (bfs_queue.empty()) return true; else return false;
3.125 +// //}
3.126 +// operator Edge () { return bfs_queue.front(); }
3.127 +
3.128 +// };
3.129 +
3.130 +// template <typename Graph, typename ReachedMap>
3.131 +// struct bfs_iterator1 {
3.132 +// typedef typename Graph::Node Node;
3.133 +// typedef typename Graph::Edge Edge;
3.134 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
3.135 +// Graph& G;
3.136 +// std::queue<OutEdgeIt>& bfs_queue;
3.137 +// ReachedMap& reached;
3.138 +// bool _newly_reached;
3.139 +// bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
3.140 +// valid();
3.141 +// if (!bfs_queue.empty() && bfs_queue.front().valid()) {
3.142 +// OutEdgeIt e=bfs_queue.front();
3.143 +// Node w=G.bNode(e);
3.144 +// if (!reached.get(w)) {
3.145 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
3.146 +// reached.set(w, true);
3.147 +// _newly_reached=true;
3.148 +// } else {
3.149 +// _newly_reached=false;
3.150 +// }
3.151 +// }
3.152 +// }
3.153 +// bfs_iterator1<Graph, ReachedMap>& operator++() {
3.154 +// if (!valid()) return *this;
3.155 +// ++(bfs_queue.front());
3.156 +// valid();
3.157 +// if (!bfs_queue.empty() && bfs_queue.front().valid()) {
3.158 +// OutEdgeIt e=bfs_queue.front();
3.159 +// Node w=G.bNode(e);
3.160 +// if (!reached.get(w)) {
3.161 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
3.162 +// reached.set(w, true);
3.163 +// _newly_reached=true;
3.164 +// } else {
3.165 +// _newly_reached=false;
3.166 +// }
3.167 +// }
3.168 +// return *this;
3.169 +// }
3.170 +// bool valid() {
3.171 +// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
3.172 +// if (bfs_queue.empty()) return false; else return true;
3.173 +// }
3.174 +// operator OutEdgeIt() { return bfs_queue.front(); }
3.175 +// //ize
3.176 +// bool newly_reached() { return _newly_reached; }
3.177 +
3.178 +// };
3.179 +
3.180 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
3.181 +// struct BfsIterator {
3.182 +// typedef typename Graph::Node Node;
3.183 +// Graph& G;
3.184 +// std::queue<OutEdgeIt>& bfs_queue;
3.185 +// ReachedMap& reached;
3.186 +// bool b_node_newly_reached;
3.187 +// OutEdgeIt actual_edge;
3.188 +// BfsIterator(Graph& _G,
3.189 +// std::queue<OutEdgeIt>& _bfs_queue,
3.190 +// ReachedMap& _reached) :
3.191 +// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
3.192 +// actual_edge=bfs_queue.front();
3.193 +// if (actual_edge.valid()) {
3.194 +// Node w=G.bNode(actual_edge);
3.195 +// if (!reached.get(w)) {
3.196 +// bfs_queue.push(G.firstOutEdge(w));
3.197 +// reached.set(w, true);
3.198 +// b_node_newly_reached=true;
3.199 +// } else {
3.200 +// b_node_newly_reached=false;
3.201 +// }
3.202 +// }
3.203 +// }
3.204 +// BfsIterator<Graph, OutEdgeIt, ReachedMap>&
3.205 +// operator++() {
3.206 +// if (bfs_queue.front().valid()) {
3.207 +// ++(bfs_queue.front());
3.208 +// actual_edge=bfs_queue.front();
3.209 +// if (actual_edge.valid()) {
3.210 +// Node w=G.bNode(actual_edge);
3.211 +// if (!reached.get(w)) {
3.212 +// bfs_queue.push(G.firstOutEdge(w));
3.213 +// reached.set(w, true);
3.214 +// b_node_newly_reached=true;
3.215 +// } else {
3.216 +// b_node_newly_reached=false;
3.217 +// }
3.218 +// }
3.219 +// } else {
3.220 +// bfs_queue.pop();
3.221 +// actual_edge=bfs_queue.front();
3.222 +// if (actual_edge.valid()) {
3.223 +// Node w=G.bNode(actual_edge);
3.224 +// if (!reached.get(w)) {
3.225 +// bfs_queue.push(G.firstOutEdge(w));
3.226 +// reached.set(w, true);
3.227 +// b_node_newly_reached=true;
3.228 +// } else {
3.229 +// b_node_newly_reached=false;
3.230 +// }
3.231 +// }
3.232 +// }
3.233 +// return *this;
3.234 +// }
3.235 +// bool finished() { return bfs_queue.empty(); }
3.236 +// operator OutEdgeIt () { return actual_edge; }
3.237 +// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
3.238 +// bool aNodeIsExamined() { return !(actual_edge.valid()); }
3.239 +// };
3.240 +
3.241 +
3.242 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
3.243 +// struct DfsIterator {
3.244 +// typedef typename Graph::Node Node;
3.245 +// Graph& G;
3.246 +// std::stack<OutEdgeIt>& bfs_queue;
3.247 +// ReachedMap& reached;
3.248 +// bool b_node_newly_reached;
3.249 +// OutEdgeIt actual_edge;
3.250 +// DfsIterator(Graph& _G,
3.251 +// std::stack<OutEdgeIt>& _bfs_queue,
3.252 +// ReachedMap& _reached) :
3.253 +// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
3.254 +// actual_edge=bfs_queue.top();
3.255 +// if (actual_edge.valid()) {
3.256 +// Node w=G.bNode(actual_edge);
3.257 +// if (!reached.get(w)) {
3.258 +// bfs_queue.push(G.firstOutEdge(w));
3.259 +// reached.set(w, true);
3.260 +// b_node_newly_reached=true;
3.261 +// } else {
3.262 +// ++(bfs_queue.top());
3.263 +// b_node_newly_reached=false;
3.264 +// }
3.265 +// } else {
3.266 +// bfs_queue.pop();
3.267 +// }
3.268 +// }
3.269 +// DfsIterator<Graph, OutEdgeIt, ReachedMap>&
3.270 +// operator++() {
3.271 +// actual_edge=bfs_queue.top();
3.272 +// if (actual_edge.valid()) {
3.273 +// Node w=G.bNode(actual_edge);
3.274 +// if (!reached.get(w)) {
3.275 +// bfs_queue.push(G.firstOutEdge(w));
3.276 +// reached.set(w, true);
3.277 +// b_node_newly_reached=true;
3.278 +// } else {
3.279 +// ++(bfs_queue.top());
3.280 +// b_node_newly_reached=false;
3.281 +// }
3.282 +// } else {
3.283 +// bfs_queue.pop();
3.284 +// }
3.285 +// return *this;
3.286 +// }
3.287 +// bool finished() { return bfs_queue.empty(); }
3.288 +// operator OutEdgeIt () { return actual_edge; }
3.289 +// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
3.290 +// bool aNodeIsExamined() { return !(actual_edge.valid()); }
3.291 +// };
3.292 +
3.293 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
3.294 +// struct BfsIterator1 {
3.295 +// typedef typename Graph::Node Node;
3.296 +// Graph& G;
3.297 +// std::queue<OutEdgeIt>& bfs_queue;
3.298 +// ReachedMap& reached;
3.299 +// bool b_node_newly_reached;
3.300 +// OutEdgeIt actual_edge;
3.301 +// BfsIterator1(Graph& _G,
3.302 +// std::queue<OutEdgeIt>& _bfs_queue,
3.303 +// ReachedMap& _reached) :
3.304 +// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
3.305 +// actual_edge=bfs_queue.front();
3.306 +// if (actual_edge.valid()) {
3.307 +// Node w=G.bNode(actual_edge);
3.308 +// if (!reached.get(w)) {
3.309 +// bfs_queue.push(OutEdgeIt(G, w));
3.310 +// reached.set(w, true);
3.311 +// b_node_newly_reached=true;
3.312 +// } else {
3.313 +// b_node_newly_reached=false;
3.314 +// }
3.315 +// }
3.316 +// }
3.317 +// void next() {
3.318 +// if (bfs_queue.front().valid()) {
3.319 +// ++(bfs_queue.front());
3.320 +// actual_edge=bfs_queue.front();
3.321 +// if (actual_edge.valid()) {
3.322 +// Node w=G.bNode(actual_edge);
3.323 +// if (!reached.get(w)) {
3.324 +// bfs_queue.push(OutEdgeIt(G, w));
3.325 +// reached.set(w, true);
3.326 +// b_node_newly_reached=true;
3.327 +// } else {
3.328 +// b_node_newly_reached=false;
3.329 +// }
3.330 +// }
3.331 +// } else {
3.332 +// bfs_queue.pop();
3.333 +// actual_edge=bfs_queue.front();
3.334 +// if (actual_edge.valid()) {
3.335 +// Node w=G.bNode(actual_edge);
3.336 +// if (!reached.get(w)) {
3.337 +// bfs_queue.push(OutEdgeIt(G, w));
3.338 +// reached.set(w, true);
3.339 +// b_node_newly_reached=true;
3.340 +// } else {
3.341 +// b_node_newly_reached=false;
3.342 +// }
3.343 +// }
3.344 +// }
3.345 +// //return *this;
3.346 +// }
3.347 +// bool finished() { return bfs_queue.empty(); }
3.348 +// operator OutEdgeIt () { return actual_edge; }
3.349 +// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
3.350 +// bool aNodeIsExamined() { return !(actual_edge.valid()); }
3.351 +// };
3.352 +
3.353 +
3.354 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
3.355 +// struct DfsIterator1 {
3.356 +// typedef typename Graph::Node Node;
3.357 +// Graph& G;
3.358 +// std::stack<OutEdgeIt>& bfs_queue;
3.359 +// ReachedMap& reached;
3.360 +// bool b_node_newly_reached;
3.361 +// OutEdgeIt actual_edge;
3.362 +// DfsIterator1(Graph& _G,
3.363 +// std::stack<OutEdgeIt>& _bfs_queue,
3.364 +// ReachedMap& _reached) :
3.365 +// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
3.366 +// //actual_edge=bfs_queue.top();
3.367 +// //if (actual_edge.valid()) {
3.368 +// // Node w=G.bNode(actual_edge);
3.369 +// //if (!reached.get(w)) {
3.370 +// // bfs_queue.push(OutEdgeIt(G, w));
3.371 +// // reached.set(w, true);
3.372 +// // b_node_newly_reached=true;
3.373 +// //} else {
3.374 +// // ++(bfs_queue.top());
3.375 +// // b_node_newly_reached=false;
3.376 +// //}
3.377 +// //} else {
3.378 +// // bfs_queue.pop();
3.379 +// //}
3.380 +// }
3.381 +// void next() {
3.382 +// actual_edge=bfs_queue.top();
3.383 +// if (actual_edge.valid()) {
3.384 +// Node w=G.bNode(actual_edge);
3.385 +// if (!reached.get(w)) {
3.386 +// bfs_queue.push(OutEdgeIt(G, w));
3.387 +// reached.set(w, true);
3.388 +// b_node_newly_reached=true;
3.389 +// } else {
3.390 +// ++(bfs_queue.top());
3.391 +// b_node_newly_reached=false;
3.392 +// }
3.393 +// } else {
3.394 +// bfs_queue.pop();
3.395 +// }
3.396 +// //return *this;
3.397 +// }
3.398 +// bool finished() { return bfs_queue.empty(); }
3.399 +// operator OutEdgeIt () { return actual_edge; }
3.400 +// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
3.401 +// bool aNodeIsLeaved() { return !(actual_edge.valid()); }
3.402 +// };
3.403 +
3.404 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
3.405 +// class BfsIterator2 {
3.406 +// typedef typename Graph::Node Node;
3.407 +// const Graph& G;
3.408 +// std::queue<OutEdgeIt> bfs_queue;
3.409 +// ReachedMap reached;
3.410 +// bool b_node_newly_reached;
3.411 +// OutEdgeIt actual_edge;
3.412 +// public:
3.413 +// BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
3.414 +// void pushAndSetReached(Node s) {
3.415 +// reached.set(s, true);
3.416 +// if (bfs_queue.empty()) {
3.417 +// bfs_queue.push(G.template first<OutEdgeIt>(s));
3.418 +// actual_edge=bfs_queue.front();
3.419 +// if (actual_edge.valid()) {
3.420 +// Node w=G.bNode(actual_edge);
3.421 +// if (!reached.get(w)) {
3.422 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
3.423 +// reached.set(w, true);
3.424 +// b_node_newly_reached=true;
3.425 +// } else {
3.426 +// b_node_newly_reached=false;
3.427 +// }
3.428 +// } //else {
3.429 +// //}
3.430 +// } else {
3.431 +// bfs_queue.push(G.template first<OutEdgeIt>(s));
3.432 +// }
3.433 +// }
3.434 +// BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
3.435 +// operator++() {
3.436 +// if (bfs_queue.front().valid()) {
3.437 +// ++(bfs_queue.front());
3.438 +// actual_edge=bfs_queue.front();
3.439 +// if (actual_edge.valid()) {
3.440 +// Node w=G.bNode(actual_edge);
3.441 +// if (!reached.get(w)) {
3.442 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
3.443 +// reached.set(w, true);
3.444 +// b_node_newly_reached=true;
3.445 +// } else {
3.446 +// b_node_newly_reached=false;
3.447 +// }
3.448 +// }
3.449 +// } else {
3.450 +// bfs_queue.pop();
3.451 +// if (!bfs_queue.empty()) {
3.452 +// actual_edge=bfs_queue.front();
3.453 +// if (actual_edge.valid()) {
3.454 +// Node w=G.bNode(actual_edge);
3.455 +// if (!reached.get(w)) {
3.456 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
3.457 +// reached.set(w, true);
3.458 +// b_node_newly_reached=true;
3.459 +// } else {
3.460 +// b_node_newly_reached=false;
3.461 +// }
3.462 +// }
3.463 +// }
3.464 +// }
3.465 +// return *this;
3.466 +// }
3.467 +// bool finished() const { return bfs_queue.empty(); }
3.468 +// operator OutEdgeIt () const { return actual_edge; }
3.469 +// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
3.470 +// bool isANodeExamined() const { return !(actual_edge.valid()); }
3.471 +// const ReachedMap& getReachedMap() const { return reached; }
3.472 +// const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
3.473 +// };
3.474 +
3.475 +
3.476 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
3.477 +// class BfsIterator3 {
3.478 +// typedef typename Graph::Node Node;
3.479 +// const Graph& G;
3.480 +// std::queue< std::pair<Node, OutEdgeIt> > bfs_queue;
3.481 +// ReachedMap reached;
3.482 +// bool b_node_newly_reached;
3.483 +// OutEdgeIt actual_edge;
3.484 +// public:
3.485 +// BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
3.486 +// void pushAndSetReached(Node s) {
3.487 +// reached.set(s, true);
3.488 +// if (bfs_queue.empty()) {
3.489 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
3.490 +// actual_edge=bfs_queue.front().second;
3.491 +// if (actual_edge.valid()) {
3.492 +// Node w=G.bNode(actual_edge);
3.493 +// if (!reached.get(w)) {
3.494 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
3.495 +// reached.set(w, true);
3.496 +// b_node_newly_reached=true;
3.497 +// } else {
3.498 +// b_node_newly_reached=false;
3.499 +// }
3.500 +// } //else {
3.501 +// //}
3.502 +// } else {
3.503 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
3.504 +// }
3.505 +// }
3.506 +// BfsIterator3<Graph, OutEdgeIt, ReachedMap>&
3.507 +// operator++() {
3.508 +// if (bfs_queue.front().second.valid()) {
3.509 +// ++(bfs_queue.front().second);
3.510 +// actual_edge=bfs_queue.front().second;
3.511 +// if (actual_edge.valid()) {
3.512 +// Node w=G.bNode(actual_edge);
3.513 +// if (!reached.get(w)) {
3.514 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
3.515 +// reached.set(w, true);
3.516 +// b_node_newly_reached=true;
3.517 +// } else {
3.518 +// b_node_newly_reached=false;
3.519 +// }
3.520 +// }
3.521 +// } else {
3.522 +// bfs_queue.pop();
3.523 +// if (!bfs_queue.empty()) {
3.524 +// actual_edge=bfs_queue.front().second;
3.525 +// if (actual_edge.valid()) {
3.526 +// Node w=G.bNode(actual_edge);
3.527 +// if (!reached.get(w)) {
3.528 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
3.529 +// reached.set(w, true);
3.530 +// b_node_newly_reached=true;
3.531 +// } else {
3.532 +// b_node_newly_reached=false;
3.533 +// }
3.534 +// }
3.535 +// }
3.536 +// }
3.537 +// return *this;
3.538 +// }
3.539 +// bool finished() const { return bfs_queue.empty(); }
3.540 +// operator OutEdgeIt () const { return actual_edge; }
3.541 +// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
3.542 +// bool isANodeExamined() const { return !(actual_edge.valid()); }
3.543 +// Node aNode() const { return bfs_queue.front().first; }
3.544 +// Node bNode() const { return G.bNode(actual_edge); }
3.545 +// const ReachedMap& getReachedMap() const { return reached; }
3.546 +// //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
3.547 +// };
3.548 +
3.549 +
3.550 + template <typename Graph, typename OutEdgeIt,
3.551 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
3.552 + class BfsIterator4 {
3.553 + typedef typename Graph::Node Node;
3.554 + const Graph& G;
3.555 + std::queue<Node> bfs_queue;
3.556 + ReachedMap& reached;
3.557 + bool b_node_newly_reached;
3.558 + OutEdgeIt actual_edge;
3.559 + bool own_reached_map;
3.560 + public:
3.561 + BfsIterator4(const Graph& _G, ReachedMap& _reached) :
3.562 + G(_G), reached(_reached),
3.563 + own_reached_map(false) { }
3.564 + BfsIterator4(const Graph& _G) :
3.565 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
3.566 + own_reached_map(true) { }
3.567 + ~BfsIterator4() { if (own_reached_map) delete &reached; }
3.568 + void pushAndSetReached(Node s) {
3.569 + //std::cout << "mimi" << &reached << std::endl;
3.570 + reached.set(s, true);
3.571 + //std::cout << "mumus" << std::endl;
3.572 + if (bfs_queue.empty()) {
3.573 + //std::cout << "bibi1" << std::endl;
3.574 + bfs_queue.push(s);
3.575 + //std::cout << "zizi" << std::endl;
3.576 + G./*getF*/first(actual_edge, s);
3.577 + //std::cout << "kiki" << std::endl;
3.578 + if (G.valid(actual_edge)/*.valid()*/) {
3.579 + Node w=G.bNode(actual_edge);
3.580 + if (!reached.get(w)) {
3.581 + bfs_queue.push(w);
3.582 + reached.set(w, true);
3.583 + b_node_newly_reached=true;
3.584 + } else {
3.585 + b_node_newly_reached=false;
3.586 + }
3.587 + }
3.588 + } else {
3.589 + //std::cout << "bibi2" << std::endl;
3.590 + bfs_queue.push(s);
3.591 + }
3.592 + }
3.593 + BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
3.594 + operator++() {
3.595 + if (G.valid(actual_edge)/*.valid()*/) {
3.596 + /*++*/G.next(actual_edge);
3.597 + if (G.valid(actual_edge)/*.valid()*/) {
3.598 + Node w=G.bNode(actual_edge);
3.599 + if (!reached.get(w)) {
3.600 + bfs_queue.push(w);
3.601 + reached.set(w, true);
3.602 + b_node_newly_reached=true;
3.603 + } else {
3.604 + b_node_newly_reached=false;
3.605 + }
3.606 + }
3.607 + } else {
3.608 + bfs_queue.pop();
3.609 + if (!bfs_queue.empty()) {
3.610 + G./*getF*/first(actual_edge, bfs_queue.front());
3.611 + if (G.valid(actual_edge)/*.valid()*/) {
3.612 + Node w=G.bNode(actual_edge);
3.613 + if (!reached.get(w)) {
3.614 + bfs_queue.push(w);
3.615 + reached.set(w, true);
3.616 + b_node_newly_reached=true;
3.617 + } else {
3.618 + b_node_newly_reached=false;
3.619 + }
3.620 + }
3.621 + }
3.622 + }
3.623 + return *this;
3.624 + }
3.625 + bool finished() const { return bfs_queue.empty(); }
3.626 + operator OutEdgeIt () const { return actual_edge; }
3.627 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
3.628 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
3.629 + Node aNode() const { return bfs_queue.front(); }
3.630 + Node bNode() const { return G.bNode(actual_edge); }
3.631 + const ReachedMap& getReachedMap() const { return reached; }
3.632 + const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
3.633 + };
3.634 +
3.635 +
3.636 + template <typename GraphWrapper, /*typename OutEdgeIt,*/
3.637 + typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
3.638 + class BfsIterator5 {
3.639 + typedef typename GraphWrapper::Node Node;
3.640 + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
3.641 + GraphWrapper G;
3.642 + std::queue<Node> bfs_queue;
3.643 + ReachedMap& reached;
3.644 + bool b_node_newly_reached;
3.645 + OutEdgeIt actual_edge;
3.646 + bool own_reached_map;
3.647 + public:
3.648 + BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
3.649 + G(_G), reached(_reached),
3.650 + own_reached_map(false) { }
3.651 + BfsIterator5(const GraphWrapper& _G) :
3.652 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
3.653 + own_reached_map(true) { }
3.654 +// BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
3.655 +// ReachedMap& _reached) :
3.656 +// G(_G), reached(_reached),
3.657 +// own_reached_map(false) { }
3.658 +// BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
3.659 +// G(_G), reached(*(new ReachedMap(G /*, false*/))),
3.660 +// own_reached_map(true) { }
3.661 + ~BfsIterator5() { if (own_reached_map) delete &reached; }
3.662 + void pushAndSetReached(Node s) {
3.663 + reached.set(s, true);
3.664 + if (bfs_queue.empty()) {
3.665 + bfs_queue.push(s);
3.666 + G./*getF*/first(actual_edge, s);
3.667 + if (G.valid(actual_edge)/*.valid()*/) {
3.668 + Node w=G.bNode(actual_edge);
3.669 + if (!reached.get(w)) {
3.670 + bfs_queue.push(w);
3.671 + reached.set(w, true);
3.672 + b_node_newly_reached=true;
3.673 + } else {
3.674 + b_node_newly_reached=false;
3.675 + }
3.676 + }
3.677 + } else {
3.678 + bfs_queue.push(s);
3.679 + }
3.680 + }
3.681 + BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
3.682 + operator++() {
3.683 + if (G.valid(actual_edge)/*.valid()*/) {
3.684 + /*++*/G.next(actual_edge);
3.685 + if (G.valid(actual_edge)/*.valid()*/) {
3.686 + Node w=G.bNode(actual_edge);
3.687 + if (!reached.get(w)) {
3.688 + bfs_queue.push(w);
3.689 + reached.set(w, true);
3.690 + b_node_newly_reached=true;
3.691 + } else {
3.692 + b_node_newly_reached=false;
3.693 + }
3.694 + }
3.695 + } else {
3.696 + bfs_queue.pop();
3.697 + if (!bfs_queue.empty()) {
3.698 + G./*getF*/first(actual_edge, bfs_queue.front());
3.699 + if (G.valid(actual_edge)/*.valid()*/) {
3.700 + Node w=G.bNode(actual_edge);
3.701 + if (!reached.get(w)) {
3.702 + bfs_queue.push(w);
3.703 + reached.set(w, true);
3.704 + b_node_newly_reached=true;
3.705 + } else {
3.706 + b_node_newly_reached=false;
3.707 + }
3.708 + }
3.709 + }
3.710 + }
3.711 + return *this;
3.712 + }
3.713 + bool finished() const { return bfs_queue.empty(); }
3.714 + operator OutEdgeIt () const { return actual_edge; }
3.715 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
3.716 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
3.717 + Node aNode() const { return bfs_queue.front(); }
3.718 + Node bNode() const { return G.bNode(actual_edge); }
3.719 + const ReachedMap& getReachedMap() const { return reached; }
3.720 + const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
3.721 + };
3.722 +
3.723 + template <typename Graph, typename OutEdgeIt,
3.724 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
3.725 + class DfsIterator4 {
3.726 + typedef typename Graph::Node Node;
3.727 + const Graph& G;
3.728 + std::stack<OutEdgeIt> dfs_stack;
3.729 + bool b_node_newly_reached;
3.730 + OutEdgeIt actual_edge;
3.731 + Node actual_node;
3.732 + ReachedMap& reached;
3.733 + bool own_reached_map;
3.734 + public:
3.735 + DfsIterator4(const Graph& _G, ReachedMap& _reached) :
3.736 + G(_G), reached(_reached),
3.737 + own_reached_map(false) { }
3.738 + DfsIterator4(const Graph& _G) :
3.739 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
3.740 + own_reached_map(true) { }
3.741 + ~DfsIterator4() { if (own_reached_map) delete &reached; }
3.742 + void pushAndSetReached(Node s) {
3.743 + actual_node=s;
3.744 + reached.set(s, true);
3.745 + dfs_stack.push(G.template first<OutEdgeIt>(s));
3.746 + }
3.747 + DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
3.748 + operator++() {
3.749 + actual_edge=dfs_stack.top();
3.750 + //actual_node=G.aNode(actual_edge);
3.751 + if (G.valid(actual_edge)/*.valid()*/) {
3.752 + Node w=G.bNode(actual_edge);
3.753 + actual_node=w;
3.754 + if (!reached.get(w)) {
3.755 + dfs_stack.push(G.template first<OutEdgeIt>(w));
3.756 + reached.set(w, true);
3.757 + b_node_newly_reached=true;
3.758 + } else {
3.759 + actual_node=G.aNode(actual_edge);
3.760 + /*++*/G.next(dfs_stack.top());
3.761 + b_node_newly_reached=false;
3.762 + }
3.763 + } else {
3.764 + //actual_node=G.aNode(dfs_stack.top());
3.765 + dfs_stack.pop();
3.766 + }
3.767 + return *this;
3.768 + }
3.769 + bool finished() const { return dfs_stack.empty(); }
3.770 + operator OutEdgeIt () const { return actual_edge; }
3.771 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
3.772 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
3.773 + Node aNode() const { return actual_node; /*FIXME*/}
3.774 + Node bNode() const { return G.bNode(actual_edge); }
3.775 + const ReachedMap& getReachedMap() const { return reached; }
3.776 + const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
3.777 + };
3.778 +
3.779 + template <typename GraphWrapper, /*typename OutEdgeIt,*/
3.780 + typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
3.781 + class DfsIterator5 {
3.782 + typedef typename GraphWrapper::Node Node;
3.783 + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
3.784 + GraphWrapper G;
3.785 + std::stack<OutEdgeIt> dfs_stack;
3.786 + bool b_node_newly_reached;
3.787 + OutEdgeIt actual_edge;
3.788 + Node actual_node;
3.789 + ReachedMap& reached;
3.790 + bool own_reached_map;
3.791 + public:
3.792 + DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
3.793 + G(_G), reached(_reached),
3.794 + own_reached_map(false) { }
3.795 + DfsIterator5(const GraphWrapper& _G) :
3.796 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
3.797 + own_reached_map(true) { }
3.798 + ~DfsIterator5() { if (own_reached_map) delete &reached; }
3.799 + void pushAndSetReached(Node s) {
3.800 + actual_node=s;
3.801 + reached.set(s, true);
3.802 + dfs_stack.push(G.template first<OutEdgeIt>(s));
3.803 + }
3.804 + DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
3.805 + operator++() {
3.806 + actual_edge=dfs_stack.top();
3.807 + //actual_node=G.aNode(actual_edge);
3.808 + if (G.valid(actual_edge)/*.valid()*/) {
3.809 + Node w=G.bNode(actual_edge);
3.810 + actual_node=w;
3.811 + if (!reached.get(w)) {
3.812 + dfs_stack.push(G.template first<OutEdgeIt>(w));
3.813 + reached.set(w, true);
3.814 + b_node_newly_reached=true;
3.815 + } else {
3.816 + actual_node=G.aNode(actual_edge);
3.817 + /*++*/G.next(dfs_stack.top());
3.818 + b_node_newly_reached=false;
3.819 + }
3.820 + } else {
3.821 + //actual_node=G.aNode(dfs_stack.top());
3.822 + dfs_stack.pop();
3.823 + }
3.824 + return *this;
3.825 + }
3.826 + bool finished() const { return dfs_stack.empty(); }
3.827 + operator OutEdgeIt () const { return actual_edge; }
3.828 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
3.829 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
3.830 + Node aNode() const { return actual_node; /*FIXME*/}
3.831 + Node bNode() const { return G.bNode(actual_edge); }
3.832 + const ReachedMap& getReachedMap() const { return reached; }
3.833 + const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
3.834 + };
3.835 +
3.836 +
3.837 +
3.838 +} // namespace hugo
3.839 +
3.840 +#endif //BFS_ITERATOR_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/edmonds_karp.h Fri Mar 12 09:19:54 2004 +0000
4.3 @@ -0,0 +1,707 @@
4.4 +// -*- c++ -*-
4.5 +#ifndef EDMONDS_KARP_H
4.6 +#define EDMONDS_KARP_H
4.7 +
4.8 +#include <algorithm>
4.9 +#include <list>
4.10 +#include <iterator>
4.11 +
4.12 +#include <bfs_iterator.h>
4.13 +#include <invalid.h>
4.14 +
4.15 +namespace hugo {
4.16 +
4.17 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
4.18 + class ResGraph {
4.19 + public:
4.20 + typedef typename Graph::Node Node;
4.21 + typedef typename Graph::NodeIt NodeIt;
4.22 + private:
4.23 + typedef typename Graph::SymEdgeIt OldSymEdgeIt;
4.24 + const Graph& G;
4.25 + FlowMap& flow;
4.26 + const CapacityMap& capacity;
4.27 + public:
4.28 + ResGraph(const Graph& _G, FlowMap& _flow,
4.29 + const CapacityMap& _capacity) :
4.30 + G(_G), flow(_flow), capacity(_capacity) { }
4.31 +
4.32 + class Edge;
4.33 + class OutEdgeIt;
4.34 + friend class Edge;
4.35 + friend class OutEdgeIt;
4.36 +
4.37 + class Edge {
4.38 + friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
4.39 + protected:
4.40 + const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
4.41 + OldSymEdgeIt sym;
4.42 + public:
4.43 + Edge() { }
4.44 + //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
4.45 + Number free() const {
4.46 + if (resG->G.aNode(sym)==resG->G.tail(sym)) {
4.47 + return (resG->capacity.get(sym)-resG->flow.get(sym));
4.48 + } else {
4.49 + return (resG->flow.get(sym));
4.50 + }
4.51 + }
4.52 + bool valid() const { return sym.valid(); }
4.53 + void augment(Number a) const {
4.54 + if (resG->G.aNode(sym)==resG->G.tail(sym)) {
4.55 + resG->flow.set(sym, resG->flow.get(sym)+a);
4.56 + //resG->flow[sym]+=a;
4.57 + } else {
4.58 + resG->flow.set(sym, resG->flow.get(sym)-a);
4.59 + //resG->flow[sym]-=a;
4.60 + }
4.61 + }
4.62 + };
4.63 +
4.64 + class OutEdgeIt : public Edge {
4.65 + friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
4.66 + public:
4.67 + OutEdgeIt() { }
4.68 + //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
4.69 + private:
4.70 + OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
4.71 + resG=&_resG;
4.72 + sym=resG->G.template first<OldSymEdgeIt>(v);
4.73 + while( sym.valid() && !(free()>0) ) { ++sym; }
4.74 + }
4.75 + public:
4.76 + OutEdgeIt& operator++() {
4.77 + ++sym;
4.78 + while( sym.valid() && !(free()>0) ) { ++sym; }
4.79 + return *this;
4.80 + }
4.81 + };
4.82 +
4.83 + void /*getF*/first(OutEdgeIt& e, Node v) const {
4.84 + e=OutEdgeIt(*this, v);
4.85 + }
4.86 + void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
4.87 +
4.88 + template< typename It >
4.89 + It first() const {
4.90 + It e;
4.91 + /*getF*/first(e);
4.92 + return e;
4.93 + }
4.94 +
4.95 + template< typename It >
4.96 + It first(Node v) const {
4.97 + It e;
4.98 + /*getF*/first(e, v);
4.99 + return e;
4.100 + }
4.101 +
4.102 + Node tail(Edge e) const { return G.aNode(e.sym); }
4.103 + Node head(Edge e) const { return G.bNode(e.sym); }
4.104 +
4.105 + Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
4.106 + Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
4.107 +
4.108 + int id(Node v) const { return G.id(v); }
4.109 +
4.110 + template <typename S>
4.111 + class NodeMap {
4.112 + typename Graph::NodeMap<S> node_map;
4.113 + public:
4.114 + NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
4.115 + NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
4.116 + void set(Node nit, S a) { node_map.set(nit, a); }
4.117 + S get(Node nit) const { return node_map.get(nit); }
4.118 + S& operator[](Node nit) { return node_map[nit]; }
4.119 + const S& operator[](Node nit) const { return node_map[nit]; }
4.120 + };
4.121 +
4.122 + };
4.123 +
4.124 +
4.125 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
4.126 + class ResGraph2 {
4.127 + public:
4.128 + typedef typename Graph::Node Node;
4.129 + typedef typename Graph::NodeIt NodeIt;
4.130 + private:
4.131 + //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
4.132 + typedef typename Graph::OutEdgeIt OldOutEdgeIt;
4.133 + typedef typename Graph::InEdgeIt OldInEdgeIt;
4.134 +
4.135 + const Graph& G;
4.136 + FlowMap& flow;
4.137 + const CapacityMap& capacity;
4.138 + public:
4.139 + ResGraph2(const Graph& _G, FlowMap& _flow,
4.140 + const CapacityMap& _capacity) :
4.141 + G(_G), flow(_flow), capacity(_capacity) { }
4.142 +
4.143 + class Edge;
4.144 + class OutEdgeIt;
4.145 + friend class Edge;
4.146 + friend class OutEdgeIt;
4.147 +
4.148 + class Edge {
4.149 + friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
4.150 + protected:
4.151 + const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
4.152 + //OldSymEdgeIt sym;
4.153 + OldOutEdgeIt out;
4.154 + OldInEdgeIt in;
4.155 + bool out_or_in; //true, iff out
4.156 + public:
4.157 + Edge() : out_or_in(true) { }
4.158 + Number free() const {
4.159 + if (out_or_in) {
4.160 + return (resG->capacity.get(out)-resG->flow.get(out));
4.161 + } else {
4.162 + return (resG->flow.get(in));
4.163 + }
4.164 + }
4.165 + bool valid() const {
4.166 + return out_or_in && out.valid() || in.valid(); }
4.167 + void augment(Number a) const {
4.168 + if (out_or_in) {
4.169 + resG->flow.set(out, resG->flow.get(out)+a);
4.170 + } else {
4.171 + resG->flow.set(in, resG->flow.get(in)-a);
4.172 + }
4.173 + }
4.174 + };
4.175 +
4.176 + class OutEdgeIt : public Edge {
4.177 + friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
4.178 + public:
4.179 + OutEdgeIt() { }
4.180 + private:
4.181 + OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
4.182 + resG=&_resG;
4.183 + out=resG->G.template first<OldOutEdgeIt>(v);
4.184 + while( out.valid() && !(free()>0) ) { ++out; }
4.185 + if (!out.valid()) {
4.186 + out_or_in=0;
4.187 + in=resG->G.template first<OldInEdgeIt>(v);
4.188 + while( in.valid() && !(free()>0) ) { ++in; }
4.189 + }
4.190 + }
4.191 + public:
4.192 + OutEdgeIt& operator++() {
4.193 + if (out_or_in) {
4.194 + Node v=resG->G.aNode(out);
4.195 + ++out;
4.196 + while( out.valid() && !(free()>0) ) { ++out; }
4.197 + if (!out.valid()) {
4.198 + out_or_in=0;
4.199 + in=resG->G.template first<OldInEdgeIt>(v);
4.200 + while( in.valid() && !(free()>0) ) { ++in; }
4.201 + }
4.202 + } else {
4.203 + ++in;
4.204 + while( in.valid() && !(free()>0) ) { ++in; }
4.205 + }
4.206 + return *this;
4.207 + }
4.208 + };
4.209 +
4.210 + void /*getF*/first(OutEdgeIt& e, Node v) const {
4.211 + e=OutEdgeIt(*this, v);
4.212 + }
4.213 + void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
4.214 +
4.215 + template< typename It >
4.216 + It first() const {
4.217 + It e;
4.218 + /*getF*/first(e);
4.219 + return e;
4.220 + }
4.221 +
4.222 + template< typename It >
4.223 + It first(Node v) const {
4.224 + It e;
4.225 + /*getF*/first(e, v);
4.226 + return e;
4.227 + }
4.228 +
4.229 + Node tail(Edge e) const {
4.230 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
4.231 + Node head(Edge e) const {
4.232 + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
4.233 +
4.234 + Node aNode(OutEdgeIt e) const {
4.235 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
4.236 + Node bNode(OutEdgeIt e) const {
4.237 + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
4.238 +
4.239 + int id(Node v) const { return G.id(v); }
4.240 +
4.241 + template <typename S>
4.242 + class NodeMap {
4.243 + typename Graph::NodeMap<S> node_map;
4.244 + public:
4.245 + NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
4.246 + NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
4.247 + void set(Node nit, S a) { node_map.set(nit, a); }
4.248 + S get(Node nit) const { return node_map.get(nit); }
4.249 + };
4.250 + };
4.251 +
4.252 +
4.253 + template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
4.254 + class MaxFlow {
4.255 + public:
4.256 + typedef typename Graph::Node Node;
4.257 + typedef typename Graph::Edge Edge;
4.258 + typedef typename Graph::EdgeIt EdgeIt;
4.259 + typedef typename Graph::OutEdgeIt OutEdgeIt;
4.260 + typedef typename Graph::InEdgeIt InEdgeIt;
4.261 +
4.262 + private:
4.263 + const Graph* G;
4.264 + Node s;
4.265 + Node t;
4.266 + FlowMap* flow;
4.267 + const CapacityMap* capacity;
4.268 + typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
4.269 + typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
4.270 + typedef typename AugGraph::Edge AugEdge;
4.271 +
4.272 + //AugGraph res_graph;
4.273 + //typedef typename AugGraph::NodeMap<bool> ReachedMap;
4.274 + //typename AugGraph::NodeMap<AugEdge> pred;
4.275 + //typename AugGraph::NodeMap<Number> free;
4.276 + public:
4.277 + MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
4.278 + G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //,
4.279 + //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
4.280 + { }
4.281 + bool augmentOnShortestPath() {
4.282 + AugGraph res_graph(*G, *flow, *capacity);
4.283 + bool _augment=false;
4.284 +
4.285 + typedef typename AugGraph::NodeMap<bool> ReachedMap;
4.286 + BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
4.287 + res_bfs.pushAndSetReached(s);
4.288 +
4.289 + typename AugGraph::NodeMap<AugEdge> pred(res_graph);
4.290 + pred.set(s, AugEdge(INVALID));
4.291 +
4.292 + typename AugGraph::NodeMap<Number> free(res_graph);
4.293 +
4.294 + //searching for augmenting path
4.295 + while ( !res_bfs.finished() ) {
4.296 + AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
4.297 + if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
4.298 + Node v=res_graph.tail(e);
4.299 + Node w=res_graph.head(e);
4.300 + pred.set(w, e);
4.301 + if (res_graph.valid(pred.get(v))) {
4.302 + free.set(w, std::min(free.get(v), res_graph.free(e)));
4.303 + } else {
4.304 + free.set(w, res_graph.free(e));
4.305 + }
4.306 + if (res_graph.head(e)==t) { _augment=true; break; }
4.307 + }
4.308 +
4.309 + ++res_bfs;
4.310 + } //end of searching augmenting path
4.311 +
4.312 + if (_augment) {
4.313 + Node n=t;
4.314 + Number augment_value=free.get(t);
4.315 + while (res_graph.valid(pred.get(n))) {
4.316 + AugEdge e=pred.get(n);
4.317 + res_graph.augment(e, augment_value);
4.318 + //e.augment(augment_value);
4.319 + n=res_graph.tail(e);
4.320 + }
4.321 + }
4.322 +
4.323 + return _augment;
4.324 + }
4.325 +
4.326 + template<typename MutableGraph> bool augmentOnBlockingFlow() {
4.327 +
4.328 +// std::cout << "number of nodes: " << G->nodeNum() << std::endl;
4.329 +// typename Graph::NodeIt n;
4.330 +// G->first(n);
4.331 +// for( ; G->valid(n); G->next(n)) {
4.332 +// std::cout << G->id(n) << std::endl;
4.333 +// }
4.334 +// std::cout << "meg elek 1";
4.335 +
4.336 +// for(typename Graph::NodeIt n=G->template first<typename Graph::NodeIt>(); G->valid(n); G->next(n)) {
4.337 +// std::cout << G->id(n) << std::endl;
4.338 +// }
4.339 +// std::cout << "meg elek 2";
4.340 +
4.341 + bool _augment=false;
4.342 +
4.343 + AugGraph res_graph(*G, *flow, *capacity);
4.344 +
4.345 + typedef typename AugGraph::NodeMap<bool> ReachedMap;
4.346 + BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
4.347 +
4.348 + bfs.pushAndSetReached(s);
4.349 + typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
4.350 + while ( !bfs.finished() ) {
4.351 + AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
4.352 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
4.353 + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
4.354 + }
4.355 +
4.356 + ++bfs;
4.357 + } //computing distances from s in the residual graph
4.358 +
4.359 +// for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
4.360 +// std::cout << res_graph.id(n) << std::endl;
4.361 +// }
4.362 +// std::cout << "meg elek";
4.363 +
4.364 + MutableGraph F;
4.365 + typename AugGraph::NodeMap<typename MutableGraph::Node>
4.366 + res_graph_to_F(res_graph);
4.367 + for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
4.368 + res_graph_to_F.set(n, F.addNode());
4.369 + }
4.370 +
4.371 + typename MutableGraph::Node sF=res_graph_to_F.get(s);
4.372 + typename MutableGraph::Node tF=res_graph_to_F.get(t);
4.373 +
4.374 + typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
4.375 + typename MutableGraph::EdgeMap<Number> residual_capacity(F);
4.376 +
4.377 + //Making F to the graph containing the edges of the residual graph
4.378 + //which are in some shortest paths
4.379 + for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
4.380 + if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
4.381 + typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
4.382 + original_edge.update();
4.383 + original_edge.set(f, e);
4.384 + residual_capacity.update();
4.385 + residual_capacity.set(f, res_graph.free(e));
4.386 + }
4.387 + }
4.388 +
4.389 +// for(typename MutableGraph::NodeIt n=F.template first<typename MutableGraph::NodeIt>(); F.valid(n); F.next(n)) {
4.390 +// std::cout << F.id(n) << std::endl;
4.391 +// }
4.392 +
4.393 + bool __augment=true;
4.394 +
4.395 + while (__augment) {
4.396 + __augment=false;
4.397 + //computing blocking flow with dfs
4.398 + typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
4.399 + DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
4.400 + typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
4.401 + pred.set(sF, typename MutableGraph::Edge(INVALID));
4.402 + //invalid iterators for sources
4.403 +
4.404 + typename MutableGraph::NodeMap<Number> free(F);
4.405 +
4.406 + dfs.pushAndSetReached(sF);
4.407 + while (!dfs.finished()) {
4.408 + ++dfs;
4.409 + if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
4.410 + if (dfs.isBNodeNewlyReached()) {
4.411 +// std::cout << "OutEdgeIt: " << dfs;
4.412 +// std::cout << " aNode: " << F.aNode(dfs);
4.413 +// std::cout << " bNode: " << F.bNode(dfs) << " ";
4.414 +
4.415 + typename MutableGraph::Node v=F.aNode(dfs);
4.416 + typename MutableGraph::Node w=F.bNode(dfs);
4.417 + pred.set(w, dfs);
4.418 + if (F.valid(pred.get(v))) {
4.419 + free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
4.420 + } else {
4.421 + free.set(w, residual_capacity.get(dfs));
4.422 + }
4.423 + if (w==tF) {
4.424 + //std::cout << "AUGMENTATION"<<std::endl;
4.425 + __augment=true;
4.426 + _augment=true;
4.427 + break;
4.428 + }
4.429 +
4.430 + } else {
4.431 + F.erase(typename MutableGraph::OutEdgeIt(dfs));
4.432 + }
4.433 + }
4.434 + }
4.435 +
4.436 + if (__augment) {
4.437 + typename MutableGraph::Node n=tF;
4.438 + Number augment_value=free.get(tF);
4.439 + while (F.valid(pred.get(n))) {
4.440 + typename MutableGraph::Edge e=pred.get(n);
4.441 + res_graph.augment(original_edge.get(e), augment_value);
4.442 + //original_edge.get(e).augment(augment_value);
4.443 + n=F.tail(e);
4.444 + if (residual_capacity.get(e)==augment_value)
4.445 + F.erase(e);
4.446 + else
4.447 + residual_capacity.set(e, residual_capacity.get(e)-augment_value);
4.448 + }
4.449 + }
4.450 +
4.451 + }
4.452 +
4.453 + return _augment;
4.454 + }
4.455 + bool augmentOnBlockingFlow2() {
4.456 + bool _augment=false;
4.457 +
4.458 + //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
4.459 + typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
4.460 + typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
4.461 + typedef typename EAugGraph::Edge EAugEdge;
4.462 +
4.463 + EAugGraph res_graph(*G, *flow, *capacity);
4.464 +
4.465 + //std::cout << "meg jo1" << std::endl;
4.466 +
4.467 + //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
4.468 + BfsIterator4<
4.469 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
4.470 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
4.471 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
4.472 +
4.473 + //std::cout << "meg jo2" << std::endl;
4.474 +
4.475 + bfs.pushAndSetReached(s);
4.476 + //std::cout << "meg jo2.5" << std::endl;
4.477 +
4.478 + //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
4.479 + typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
4.480 + NodeMap<int>& dist=res_graph.dist;
4.481 + //std::cout << "meg jo2.6" << std::endl;
4.482 +
4.483 + while ( !bfs.finished() ) {
4.484 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
4.485 +// EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
4.486 + //if (res_graph.valid(e)) {
4.487 + // std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
4.488 + //}
4.489 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
4.490 + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
4.491 + }
4.492 +
4.493 + ++bfs;
4.494 + } //computing distances from s in the residual graph
4.495 +
4.496 +
4.497 + //std::cout << "meg jo3" << std::endl;
4.498 +
4.499 +// typedef typename EAugGraph::NodeIt EAugNodeIt;
4.500 +// for(EAugNodeIt n=res_graph.template first<EAugNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
4.501 +// std::cout << "dist: " << dist.get(n) << std::endl;
4.502 +// }
4.503 +
4.504 + bool __augment=true;
4.505 +
4.506 + while (__augment) {
4.507 +// std::cout << "new iteration"<< std::endl;
4.508 +
4.509 + __augment=false;
4.510 + //computing blocking flow with dfs
4.511 + typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
4.512 + DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
4.513 + dfs(res_graph);
4.514 + typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
4.515 + pred.set(s, EAugEdge(INVALID));
4.516 + //invalid iterators for sources
4.517 +
4.518 + typename EAugGraph::NodeMap<Number> free(res_graph);
4.519 +
4.520 + dfs.pushAndSetReached(s);
4.521 + while (!dfs.finished()) {
4.522 + ++dfs;
4.523 + if (res_graph.valid(EAugOutEdgeIt(dfs))) {
4.524 + if (dfs.isBNodeNewlyReached()) {
4.525 +// std::cout << "OutEdgeIt: " << dfs;
4.526 +// std::cout << " aNode: " << res_graph.aNode(dfs);
4.527 +// std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
4.528 +// std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
4.529 +
4.530 + typename EAugGraph::Node v=res_graph.aNode(dfs);
4.531 + typename EAugGraph::Node w=res_graph.bNode(dfs);
4.532 +
4.533 + pred.set(w, EAugOutEdgeIt(dfs));
4.534 +
4.535 + //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
4.536 + if (res_graph.valid(pred.get(v))) {
4.537 + free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
4.538 + } else {
4.539 + free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs)));
4.540 + }
4.541 +
4.542 + if (w==t) {
4.543 +// std::cout << "t is reached, AUGMENTATION"<<std::endl;
4.544 + __augment=true;
4.545 + _augment=true;
4.546 + break;
4.547 + }
4.548 + } else {
4.549 +// std::cout << "<<DELETE ";
4.550 +// std::cout << " aNode: " << res_graph.aNode(dfs);
4.551 +// std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
4.552 +// std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
4.553 +// std::cout << "DELETE>> ";
4.554 +
4.555 + res_graph.erase(dfs);
4.556 + }
4.557 + }
4.558 +
4.559 + }
4.560 +
4.561 + if (__augment) {
4.562 + typename EAugGraph::Node n=t;
4.563 + Number augment_value=free.get(t);
4.564 +// std::cout << "av:" << augment_value << std::endl;
4.565 + while (res_graph.valid(pred.get(n))) {
4.566 + EAugEdge e=pred.get(n);
4.567 + res_graph.augment(e, augment_value);
4.568 + //e.augment(augment_value);
4.569 + n=res_graph.tail(e);
4.570 + if (res_graph.free(e)==0)
4.571 + res_graph.erase(e);
4.572 + }
4.573 + }
4.574 +
4.575 + }
4.576 +
4.577 + return _augment;
4.578 + }
4.579 + void run() {
4.580 + //int num_of_augmentations=0;
4.581 + while (augmentOnShortestPath()) {
4.582 + //while (augmentOnBlockingFlow<MutableGraph>()) {
4.583 + //std::cout << ++num_of_augmentations << " ";
4.584 + //std::cout<<std::endl;
4.585 + }
4.586 + }
4.587 + template<typename MutableGraph> void run() {
4.588 + //int num_of_augmentations=0;
4.589 + //while (augmentOnShortestPath()) {
4.590 + while (augmentOnBlockingFlow<MutableGraph>()) {
4.591 + //std::cout << ++num_of_augmentations << " ";
4.592 + //std::cout<<std::endl;
4.593 + }
4.594 + }
4.595 + Number flowValue() {
4.596 + Number a=0;
4.597 + OutEdgeIt e;
4.598 + for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
4.599 + a+=flow->get(e);
4.600 + }
4.601 + return a;
4.602 + }
4.603 + };
4.604 +
4.605 +
4.606 +// template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
4.607 +// class MaxFlow2 {
4.608 +// public:
4.609 +// typedef typename Graph::Node Node;
4.610 +// typedef typename Graph::Edge Edge;
4.611 +// typedef typename Graph::EdgeIt EdgeIt;
4.612 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
4.613 +// typedef typename Graph::InEdgeIt InEdgeIt;
4.614 +// private:
4.615 +// const Graph& G;
4.616 +// std::list<Node>& S;
4.617 +// std::list<Node>& T;
4.618 +// FlowMap& flow;
4.619 +// const CapacityMap& capacity;
4.620 +// typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
4.621 +// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
4.622 +// typedef typename AugGraph::Edge AugEdge;
4.623 +// typename Graph::NodeMap<bool> SMap;
4.624 +// typename Graph::NodeMap<bool> TMap;
4.625 +// public:
4.626 +// MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
4.627 +// for(typename std::list<Node>::const_iterator i=S.begin();
4.628 +// i!=S.end(); ++i) {
4.629 +// SMap.set(*i, true);
4.630 +// }
4.631 +// for (typename std::list<Node>::const_iterator i=T.begin();
4.632 +// i!=T.end(); ++i) {
4.633 +// TMap.set(*i, true);
4.634 +// }
4.635 +// }
4.636 +// bool augment() {
4.637 +// AugGraph res_graph(G, flow, capacity);
4.638 +// bool _augment=false;
4.639 +// Node reached_t_node;
4.640 +
4.641 +// typedef typename AugGraph::NodeMap<bool> ReachedMap;
4.642 +// BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
4.643 +// for(typename std::list<Node>::const_iterator i=S.begin();
4.644 +// i!=S.end(); ++i) {
4.645 +// res_bfs.pushAndSetReached(*i);
4.646 +// }
4.647 +// //res_bfs.pushAndSetReached(s);
4.648 +
4.649 +// typename AugGraph::NodeMap<AugEdge> pred(res_graph);
4.650 +// //filled up with invalid iterators
4.651 +
4.652 +// typename AugGraph::NodeMap<Number> free(res_graph);
4.653 +
4.654 +// //searching for augmenting path
4.655 +// while ( !res_bfs.finished() ) {
4.656 +// AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
4.657 +// if (e.valid() && res_bfs.isBNodeNewlyReached()) {
4.658 +// Node v=res_graph.tail(e);
4.659 +// Node w=res_graph.head(e);
4.660 +// pred.set(w, e);
4.661 +// if (pred.get(v).valid()) {
4.662 +// free.set(w, std::min(free.get(v), e.free()));
4.663 +// } else {
4.664 +// free.set(w, e.free());
4.665 +// }
4.666 +// if (TMap.get(res_graph.head(e))) {
4.667 +// _augment=true;
4.668 +// reached_t_node=res_graph.head(e);
4.669 +// break;
4.670 +// }
4.671 +// }
4.672 +
4.673 +// ++res_bfs;
4.674 +// } //end of searching augmenting path
4.675 +
4.676 +// if (_augment) {
4.677 +// Node n=reached_t_node;
4.678 +// Number augment_value=free.get(reached_t_node);
4.679 +// while (pred.get(n).valid()) {
4.680 +// AugEdge e=pred.get(n);
4.681 +// e.augment(augment_value);
4.682 +// n=res_graph.tail(e);
4.683 +// }
4.684 +// }
4.685 +
4.686 +// return _augment;
4.687 +// }
4.688 +// void run() {
4.689 +// while (augment()) { }
4.690 +// }
4.691 +// Number flowValue() {
4.692 +// Number a=0;
4.693 +// for(typename std::list<Node>::const_iterator i=S.begin();
4.694 +// i!=S.end(); ++i) {
4.695 +// for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
4.696 +// a+=flow.get(e);
4.697 +// }
4.698 +// for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
4.699 +// a-=flow.get(e);
4.700 +// }
4.701 +// }
4.702 +// return a;
4.703 +// }
4.704 +// };
4.705 +
4.706 +
4.707 +
4.708 +} // namespace hugo
4.709 +
4.710 +#endif //EDMONDS_KARP_H
5.1 --- a/src/work/iterator_bfs_demo.cc Thu Mar 11 23:31:13 2004 +0000
5.2 +++ b/src/work/iterator_bfs_demo.cc Fri Mar 12 09:19:54 2004 +0000
5.3 @@ -1,9 +1,11 @@
5.4 +// -*- c++ -*-
5.5 #include <iostream>
5.6 #include <vector>
5.7 #include <string>
5.8
5.9 -#include <list_graph.hh>
5.10 -#include <bfs_iterator.hh>
5.11 +#include <list_graph.h>
5.12 +#include <smart_graph.h>
5.13 +#include <bfs_iterator.h>
5.14 #include <graph_wrapper.h>
5.15
5.16 using namespace hugo;
5.17 @@ -18,7 +20,7 @@
5.18 public:
5.19 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
5.20 graph(_graph), node_name_map(_node_name_map) { }
5.21 - string get(typename Graph::EdgeIt e) const {
5.22 + string get(typename Graph::Edge e) const {
5.23 return
5.24 (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));
5.25 }
5.26 @@ -26,24 +28,27 @@
5.27
5.28 int main (int, char*[])
5.29 {
5.30 - typedef ListGraph::NodeIt NodeIt;
5.31 - typedef ListGraph::EdgeIt EdgeIt;
5.32 - //typedef ListGraph::EachNodeIt EachNodeIt;
5.33 - //typedef ListGraph::EachEdgeIt EachEdgeIt;
5.34 - //typedef ListGraph::OutEdgeIt OutEdgeIt;
5.35 - //typedef ListGraph::InEdgeIt InEdgeIt;
5.36 - //typedef ListGraph::SymEdgeIt SymEdgeIt;
5.37 + //typedef SmartGraph Graph;
5.38 + typedef ListGraph Graph;
5.39 +
5.40 + typedef Graph::Node Node;
5.41 + typedef Graph::Edge Edge;
5.42 + //typedef Graph::NodeIt NodeIt;
5.43 + //typedef Graph::EdgeIt EdgeIt;
5.44 + //typedef Graph::OutEdgeIt OutEdgeIt;
5.45 + //typedef Graph::InEdgeIt InEdgeIt;
5.46 + //typedef Graph::SymEdgeIt SymEdgeIt;
5.47
5.48 - ListGraph G;
5.49 + Graph G;
5.50
5.51 - NodeIt s=G.addNode();
5.52 - NodeIt v1=G.addNode();
5.53 - NodeIt v2=G.addNode();
5.54 - NodeIt v3=G.addNode();
5.55 - NodeIt v4=G.addNode();
5.56 - NodeIt t=G.addNode();
5.57 + Node s=G.addNode();
5.58 + Node v1=G.addNode();
5.59 + Node v2=G.addNode();
5.60 + Node v3=G.addNode();
5.61 + Node v4=G.addNode();
5.62 + Node t=G.addNode();
5.63
5.64 - ListGraph::NodeMap<string> node_name(G);
5.65 + Graph::NodeMap<string> node_name(G);
5.66 node_name.set(s, "s");
5.67 node_name.set(v1, "v1");
5.68 node_name.set(v2, "v2");
5.69 @@ -72,72 +77,11 @@
5.70 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
5.71 cout << " \\--> -------------> "<< endl;
5.72
5.73 -/*
5.74 - {
5.75 - cout << "iterator bfs demo 4 ..." << endl;
5.76 - BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
5.77 - bfs.pushAndSetReached(s);
5.78 - while (!bfs.finished()) {
5.79 - if (OutEdgeIt(bfs).valid()) {
5.80 - cout << "OutEdgeIt: " << bfs;
5.81 - cout << " aNode: " << G.aNode(bfs);
5.82 - cout << " bNode: " << G.bNode(bfs) << " ";
5.83 - } else {
5.84 - cout << "OutEdgeIt: " << "invalid";
5.85 - cout << " aNode: " << bfs.aNode();
5.86 - cout << " bNode: " << "invalid" << " ";
5.87 - }
5.88 - if (bfs.isBNodeNewlyReached()) {
5.89 - cout << "bNodeIsNewlyReached ";
5.90 - } else {
5.91 - cout << "bNodeIsNotNewlyReached ";
5.92 - }
5.93 - if (bfs.isANodeExamined()) {
5.94 - cout << "aNodeIsExamined ";
5.95 - } else {
5.96 - cout << "aNodeIsNotExamined ";
5.97 - }
5.98 - cout << endl;
5.99 - ++bfs;
5.100 - }
5.101 - }
5.102 -
5.103 - {
5.104 - cout << "iterator dfs demo 4 ..." << endl;
5.105 - DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
5.106 - dfs.pushAndSetReached(s);
5.107 - while (!dfs.finished()) {
5.108 - ++dfs;
5.109 - if (OutEdgeIt(dfs).valid()) {
5.110 - cout << "OutEdgeIt: " << dfs;
5.111 - cout << " aNode: " << G.aNode(dfs);
5.112 - cout << " bNode: " << G.bNode(dfs) << " ";
5.113 - } else {
5.114 - cout << "OutEdgeIt: " << "invalid";
5.115 - cout << " aNode: " << dfs.aNode();
5.116 - cout << " bNode: " << "invalid" << " ";
5.117 - }
5.118 - if (dfs.isBNodeNewlyReached()) {
5.119 - cout << "bNodeIsNewlyReached ";
5.120 - } else {
5.121 - cout << "bNodeIsNotNewlyReached ";
5.122 - }
5.123 - if (dfs.isANodeExamined()) {
5.124 - cout << "aNodeIsExamined ";
5.125 - } else {
5.126 - cout << "aNodeIsNotExamined ";
5.127 - }
5.128 - cout << endl;
5.129 - //++dfs;
5.130 - }
5.131 - }
5.132 -*/
5.133 -
5.134 -// typedef TrivGraphWrapper<const ListGraph> CGW;
5.135 +// typedef TrivGraphWrapper<const Graph> CGW;
5.136 // CGW wG(G);
5.137
5.138 // cout << "bfs and dfs demo on the directed graph" << endl;
5.139 -// for(CGW::EachNodeIt n=wG.first<CGW::EachNodeIt>(); n.valid(); ++n) {
5.140 +// for(CGW::NodeIt n=wG.first<CGW::NodeIt>(); n.valid(); ++n) {
5.141 // cout << n << ": ";
5.142 // cout << "out edges: ";
5.143 // for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
5.144 @@ -149,13 +93,13 @@
5.145 // }
5.146
5.147 {
5.148 - typedef TrivGraphWrapper<const ListGraph> GW;
5.149 + typedef TrivGraphWrapper<const Graph> GW;
5.150 GW wG(G);
5.151
5.152 - EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
5.153 + EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
5.154
5.155 cout << "bfs and dfs iterator demo on the directed graph" << endl;
5.156 - for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {
5.157 + for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
5.158 cout << node_name.get(n) << ": ";
5.159 cout << "out edges: ";
5.160 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
5.161 @@ -225,13 +169,13 @@
5.162
5.163
5.164 {
5.165 - typedef RevGraphWrapper<const ListGraph> GW;
5.166 + typedef RevGraphWrapper<const Graph> GW;
5.167 GW wG(G);
5.168
5.169 - EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
5.170 + EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
5.171
5.172 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
5.173 - for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {
5.174 + for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
5.175 cout << node_name.get(n) << ": ";
5.176 cout << "out edges: ";
5.177 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
5.178 @@ -300,13 +244,13 @@
5.179 }
5.180
5.181 {
5.182 - typedef UndirGraphWrapper<const ListGraph> GW;
5.183 + typedef UndirGraphWrapper<const Graph> GW;
5.184 GW wG(G);
5.185
5.186 - EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
5.187 + EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
5.188
5.189 cout << "bfs and dfs iterator demo on the undirected graph" << endl;
5.190 - for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) {
5.191 + for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) {
5.192 cout << node_name.get(n) << ": ";
5.193 cout << "out edges: ";
5.194 for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
6.1 --- a/src/work/jacint/preflow.h Thu Mar 11 23:31:13 2004 +0000
6.2 +++ b/src/work/jacint/preflow.h Fri Mar 12 09:19:54 2004 +0000
6.3 @@ -526,9 +526,11 @@
6.4
6.5
6.6 };
6.7 -}//namespace marci
6.8 -#endif
6.9
6.10 +} //namespace hugo
6.11
6.12 +#endif //PREFLOW_H
6.13
6.14
6.15 +
6.16 +
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/work/list_graph.h Fri Mar 12 09:19:54 2004 +0000
7.3 @@ -0,0 +1,562 @@
7.4 +// -*- c++ -*-
7.5 +#ifndef LIST_GRAPH_H
7.6 +#define LIST_GRAPH_H
7.7 +
7.8 +#include <iostream>
7.9 +#include <vector>
7.10 +
7.11 +#include <invalid.h>
7.12 +
7.13 +namespace hugo {
7.14 +
7.15 + template <typename It>
7.16 + int count(It it) {
7.17 + int i=0;
7.18 + for( ; it.valid(); ++it) { ++i; }
7.19 + return i;
7.20 + }
7.21 +
7.22 + class ListGraph {
7.23 + class node_item;
7.24 + class edge_item;
7.25 + public:
7.26 + class Node;
7.27 + class NodeIt;
7.28 + class Edge;
7.29 + class EdgeIt;
7.30 + class OutEdgeIt;
7.31 + class InEdgeIt;
7.32 + class SymEdgeIt;
7.33 + template <typename T> class NodeMap;
7.34 + template <typename T> class EdgeMap;
7.35 + private:
7.36 + template <typename T> friend class NodeMap;
7.37 + template <typename T> friend class EdgeMap;
7.38 +
7.39 + template <typename T>
7.40 + class NodeMap {
7.41 + const ListGraph& G;
7.42 + std::vector<T> container;
7.43 + public:
7.44 + typedef T ValueType;
7.45 + typedef Node KeyType;
7.46 + NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { }
7.47 + NodeMap(const ListGraph& _G, T a) :
7.48 + G(_G), container(G.node_id, a) { }
7.49 + void set(Node n, T a) { container[/*G.id(n)*/n.node->id]=a; }
7.50 + T get(Node n) const { return container[/*G.id(n)*/n.node->id]; }
7.51 + T& operator[](Node n) { return container[/*G.id(n)*/n.node->id]; }
7.52 + const T& operator[](Node n) const {
7.53 + return container[/*G.id(n)*/n.node->id];
7.54 + }
7.55 + void update() { container.resize(G.node_id); }
7.56 + void update(T a) { container.resize(G.node_id, a); }
7.57 + };
7.58 +
7.59 + template <typename T>
7.60 + class EdgeMap {
7.61 + const ListGraph& G;
7.62 + std::vector<T> container;
7.63 + public:
7.64 + typedef T ValueType;
7.65 + typedef Edge KeyType;
7.66 + EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { }
7.67 + EdgeMap(const ListGraph& _G, T a) :
7.68 + G(_G), container(G.edge_id, a) { }
7.69 + void set(Edge e, T a) { container[/*G.id(e)*/e.edge->id]=a; }
7.70 + T get(Edge e) const { return container[/*G.id(e)*/e.edge->id]; }
7.71 + T& operator[](Edge e) { return container[/*G.id(e)*/e.edge->id]; }
7.72 + const T& operator[](Edge e) const {
7.73 + return container[/*G.id(e)*/e.edge->id];
7.74 + }
7.75 + void update() { container.resize(G.edge_id); }
7.76 + void update(T a) { container.resize(G.edge_id, a); }
7.77 + };
7.78 +
7.79 + int node_id;
7.80 + int edge_id;
7.81 + int _node_num;
7.82 + int _edge_num;
7.83 +
7.84 + node_item* _first_node;
7.85 + node_item* _last_node;
7.86 +
7.87 + class node_item {
7.88 + friend class ListGraph;
7.89 + template <typename T> friend class NodeMap;
7.90 +
7.91 + friend class Node;
7.92 + friend class NodeIt;
7.93 + friend class Edge;
7.94 + friend class EdgeIt;
7.95 + friend class OutEdgeIt;
7.96 + friend class InEdgeIt;
7.97 + friend class SymEdgeIt;
7.98 + friend std::ostream& operator<<(std::ostream& os, const Node& i);
7.99 + friend std::ostream& operator<<(std::ostream& os, const Edge& i);
7.100 + //ListGraph* G;
7.101 + int id;
7.102 + edge_item* _first_out_edge;
7.103 + edge_item* _last_out_edge;
7.104 + edge_item* _first_in_edge;
7.105 + edge_item* _last_in_edge;
7.106 + node_item* _next_node;
7.107 + node_item* _prev_node;
7.108 + public:
7.109 + node_item() { }
7.110 + };
7.111 +
7.112 + class edge_item {
7.113 + friend class ListGraph;
7.114 + template <typename T> friend class EdgeMap;
7.115 +
7.116 + friend class Node;
7.117 + friend class NodeIt;
7.118 + friend class Edge;
7.119 + friend class EdgeIt;
7.120 + friend class OutEdgeIt;
7.121 + friend class InEdgeIt;
7.122 + friend class SymEdgeIt;
7.123 + friend std::ostream& operator<<(std::ostream& os, const Edge& i);
7.124 + //ListGraph* G;
7.125 + int id;
7.126 + node_item* _tail;
7.127 + node_item* _head;
7.128 + edge_item* _next_out;
7.129 + edge_item* _prev_out;
7.130 + edge_item* _next_in;
7.131 + edge_item* _prev_in;
7.132 + public:
7.133 + edge_item() { }
7.134 + };
7.135 +
7.136 + node_item* _add_node() {
7.137 + node_item* p=new node_item;
7.138 + p->id=node_id++;
7.139 + p->_first_out_edge=0;
7.140 + p->_last_out_edge=0;
7.141 + p->_first_in_edge=0;
7.142 + p->_last_in_edge=0;
7.143 + p->_prev_node=_last_node;
7.144 + p->_next_node=0;
7.145 + if (_last_node) _last_node->_next_node=p;
7.146 + _last_node=p;
7.147 + if (!_first_node) _first_node=p;
7.148 +
7.149 + ++_node_num;
7.150 + return p;
7.151 + }
7.152 +
7.153 + edge_item* _add_edge(node_item* _tail, node_item* _head) {
7.154 + edge_item* e=new edge_item;
7.155 + e->id=edge_id++;
7.156 + e->_tail=_tail;
7.157 + e->_head=_head;
7.158 +
7.159 + e->_prev_out=_tail->_last_out_edge;
7.160 + if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
7.161 + _tail->_last_out_edge=e;
7.162 + if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
7.163 + e->_next_out=0;
7.164 +
7.165 + e->_prev_in=_head->_last_in_edge;
7.166 + if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
7.167 + _head->_last_in_edge=e;
7.168 + if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
7.169 + e->_next_in=0;
7.170 +
7.171 + ++_edge_num;
7.172 + return e;
7.173 + }
7.174 +
7.175 + //deletes a node which has no out edge and no in edge
7.176 + void _delete_node(node_item* v) {
7.177 + if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else
7.178 + _last_node=v->_prev_node;
7.179 + if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else
7.180 + _first_node=v->_next_node;
7.181 +
7.182 + delete v;
7.183 + --_node_num;
7.184 + }
7.185 +
7.186 + void _delete_edge(edge_item* e) {
7.187 + if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
7.188 + (e->_tail)->_last_out_edge=e->_prev_out;
7.189 + if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
7.190 + (e->_tail)->_first_out_edge=e->_next_out;
7.191 + if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
7.192 + (e->_head)->_last_in_edge=e->_prev_in;
7.193 + if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
7.194 + (e->_head)->_first_in_edge=e->_next_in;
7.195 +
7.196 + delete e;
7.197 + --_edge_num;
7.198 + }
7.199 +
7.200 + void _set_tail(edge_item* e, node_item* _tail) {
7.201 + if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
7.202 + (e->_tail)->_last_out_edge=e->_prev_out;
7.203 + if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
7.204 + (e->_tail)->_first_out_edge=e->_next_out;
7.205 +
7.206 + e->_tail=_tail;
7.207 +
7.208 + e->_prev_out=_tail->_last_out_edge;
7.209 + if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
7.210 + _tail->_last_out_edge=e;
7.211 + if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
7.212 + e->_next_out=0;
7.213 + }
7.214 +
7.215 + void _set_head(edge_item* e, node_item* _head) {
7.216 + if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
7.217 + (e->_head)->_last_in_edge=e->_prev_in;
7.218 + if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
7.219 + (e->_head)->_first_in_edge=e->_next_in;
7.220 +
7.221 + e->_head=_head;
7.222 +
7.223 + e->_prev_in=_head->_last_in_edge;
7.224 + if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
7.225 + _head->_last_in_edge=e;
7.226 + if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
7.227 + e->_next_in=0;
7.228 + }
7.229 +
7.230 + public:
7.231 +
7.232 + /* default constructor */
7.233 +
7.234 + ListGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
7.235 +
7.236 + ~ListGraph() {
7.237 + while (first<NodeIt>().valid()) erase(first<NodeIt>());
7.238 + }
7.239 +
7.240 + int nodeNum() const { return _node_num; }
7.241 + int edgeNum() const { return _edge_num; }
7.242 +
7.243 + /* functions to construct iterators from the graph, or from each other */
7.244 +
7.245 + //NodeIt firstNode() const { return NodeIt(*this); }
7.246 + //EdgeIt firstEdge() const { return EdgeIt(*this); }
7.247 +
7.248 + //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); }
7.249 + //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); }
7.250 + //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); }
7.251 + Node tail(Edge e) const { return e.tailNode(); }
7.252 + Node head(Edge e) const { return e.headNode(); }
7.253 +
7.254 + Node aNode(const OutEdgeIt& e) const { return e.aNode(); }
7.255 + Node aNode(const InEdgeIt& e) const { return e.aNode(); }
7.256 + Node aNode(const SymEdgeIt& e) const { return e.aNode(); }
7.257 +
7.258 + Node bNode(const OutEdgeIt& e) const { return e.bNode(); }
7.259 + Node bNode(const InEdgeIt& e) const { return e.bNode(); }
7.260 + Node bNode(const SymEdgeIt& e) const { return e.bNode(); }
7.261 +
7.262 + //Node invalid_node() { return Node(); }
7.263 + //Edge invalid_edge() { return Edge(); }
7.264 + //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); }
7.265 + //InEdgeIt invalid_in_edge() { return InEdgeIt(); }
7.266 + //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); }
7.267 +
7.268 + /* same methods in other style */
7.269 + /* for experimental purpose */
7.270 +
7.271 + NodeIt& /*getF*/first(NodeIt& v) const {
7.272 + v=NodeIt(*this); return v; }
7.273 + EdgeIt& /*getF*/first(EdgeIt& e) const {
7.274 + e=EdgeIt(*this); return e; }
7.275 + OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const {
7.276 + e=OutEdgeIt(*this, v); return e; }
7.277 + InEdgeIt& /*getF*/first(InEdgeIt& e, Node v) const {
7.278 + e=InEdgeIt(*this, v); return e; }
7.279 + SymEdgeIt& /*getF*/first(SymEdgeIt& e, Node v) const {
7.280 + e=SymEdgeIt(*this, v); return e; }
7.281 + //void getTail(Node& n, const Edge& e) const { n=tail(e); }
7.282 + //void getHead(Node& n, const Edge& e) const { n=head(e); }
7.283 +
7.284 + //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); }
7.285 + //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); }
7.286 + //void getANode(Node& n, const SymEdgeIt& e) const { n=e.aNode(); }
7.287 + //void getBNode(Node& n, const OutEdgeIt& e) const { n=e.bNode(); }
7.288 + //void getBNode(Node& n, const InEdgeIt& e) const { n=e.bNode(); }
7.289 + //void getBNode(Node& n, const SymEdgeIt& e) const { n=e.bNode(); }
7.290 + //void get_invalid(Node& n) { n=Node(); }
7.291 + //void get_invalid(Edge& e) { e=Edge(); }
7.292 + //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }
7.293 + //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }
7.294 + //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
7.295 +
7.296 + template< typename It >
7.297 + It first() const {
7.298 + It e;
7.299 + /*getF*/first(e);
7.300 + return e;
7.301 + }
7.302 +
7.303 + template< typename It >
7.304 + It first(Node v) const {
7.305 + It e;
7.306 + /*getF*/first(e, v);
7.307 + return e;
7.308 + }
7.309 +
7.310 + bool valid(Node n) const { return n.valid(); }
7.311 + bool valid(Edge e) const { return e.valid(); }
7.312 +
7.313 + template <typename It> It getNext(It it) const {
7.314 + It tmp(it); return next(tmp); }
7.315 + template <typename It> It& next(It& it) const { return ++it; }
7.316 +
7.317 +
7.318 + /* for getting id's of graph objects */
7.319 + /* these are important for the implementation of property vectors */
7.320 +
7.321 + int id(Node v) const { return v.node->id; }
7.322 + int id(Edge e) const { return e.edge->id; }
7.323 +
7.324 + /* adding nodes and edges */
7.325 +
7.326 + Node addNode() { return Node(_add_node()); }
7.327 + Edge addEdge(Node u, Node v) {
7.328 + return Edge(_add_edge(u.node, v.node));
7.329 + }
7.330 +
7.331 + void erase(Node i) {
7.332 + while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
7.333 + while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
7.334 + _delete_node(i.node);
7.335 + }
7.336 +
7.337 + void erase(Edge e) { _delete_edge(e.edge); }
7.338 +
7.339 + void clear() {
7.340 + while (first<NodeIt>().valid()) erase(first<NodeIt>());
7.341 + }
7.342 +
7.343 + void setTail(Edge e, Node tail) {
7.344 + _set_tail(e.edge, tail.node);
7.345 + }
7.346 +
7.347 + void setHead(Edge e, Node head) {
7.348 + _set_head(e.edge, head.node);
7.349 + }
7.350 +
7.351 + /* stream operations, for testing purpose */
7.352 +
7.353 + friend std::ostream& operator<<(std::ostream& os, const Node& i) {
7.354 + os << i.node->id; return os;
7.355 + }
7.356 + friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
7.357 + os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
7.358 + return os;
7.359 + }
7.360 +
7.361 + class Node {
7.362 + friend class ListGraph;
7.363 + template <typename T> friend class NodeMap;
7.364 +
7.365 + friend class Edge;
7.366 + friend class OutEdgeIt;
7.367 + friend class InEdgeIt;
7.368 + friend class SymEdgeIt;
7.369 + //public: //FIXME: It is required by op= of NodeIt
7.370 + protected:
7.371 + node_item* node;
7.372 + protected:
7.373 + friend int ListGraph::id(Node v) const;
7.374 + public:
7.375 + Node() /*: node(0)*/ { }
7.376 + Node(const Invalid&) : node(0) { }
7.377 + protected:
7.378 + Node(node_item* _node) : node(_node) { }
7.379 + bool valid() const { return (node); }
7.380 + public:
7.381 + //void makeInvalid() { node=0; }
7.382 + friend bool operator==(Node u, Node v) { return v.node==u.node; }
7.383 + friend bool operator!=(Node u, Node v) { return v.node!=u.node; }
7.384 + friend std::ostream& operator<<(std::ostream& os, const Node& i);
7.385 + };
7.386 +
7.387 + class NodeIt : public Node {
7.388 + friend class ListGraph;
7.389 + //protected:
7.390 + public: //for everybody but marci
7.391 + NodeIt(const ListGraph& G) : Node(G._first_node) { }
7.392 + public:
7.393 + NodeIt() : Node() { }
7.394 + NodeIt(const Invalid& i) : Node(i) { }
7.395 + protected:
7.396 + NodeIt(node_item* v) : Node(v) { }
7.397 + NodeIt& operator++() { node=node->_next_node; return *this; }
7.398 + //FIXME::
7.399 + // NodeIt& operator=(const Node& e)
7.400 + // { node=e.node; return *this; }
7.401 + };
7.402 +
7.403 + class Edge {
7.404 + friend class ListGraph;
7.405 + template <typename T> friend class EdgeMap;
7.406 +
7.407 + friend class Node;
7.408 + friend class NodeIt;
7.409 + protected:
7.410 + edge_item* edge;
7.411 + friend int ListGraph::id(Edge e) const;
7.412 + public:
7.413 + Edge() /*: edge(0)*/ { }
7.414 + Edge(const Invalid&) : edge(0) { }
7.415 + //Edge() { }
7.416 + protected:
7.417 + Edge(edge_item* _edge) : edge(_edge) { }
7.418 + bool valid() const { return (edge); }
7.419 + public:
7.420 + //void makeInvalid() { edge=0; }
7.421 + friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; }
7.422 + friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; }
7.423 + protected:
7.424 + Node tailNode() const { return Node(edge->_tail); }
7.425 + Node headNode() const { return Node(edge->_head); }
7.426 + public:
7.427 + friend std::ostream& operator<<(std::ostream& os, const Edge& i);
7.428 + };
7.429 +
7.430 + class EdgeIt : public Edge {
7.431 + friend class ListGraph;
7.432 + //protected:
7.433 + public: //for alpar
7.434 + EdgeIt(const ListGraph& G) {
7.435 + node_item* v=G._first_node;
7.436 + if (v) edge=v->_first_out_edge; else edge=0;
7.437 + while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
7.438 + }
7.439 + public:
7.440 + EdgeIt() : Edge() { }
7.441 + EdgeIt(const Invalid& i) : Edge(i) { }
7.442 + protected:
7.443 + EdgeIt(edge_item* _e) : Edge(_e) { }
7.444 + EdgeIt& operator++() {
7.445 + node_item* v=edge->_tail;
7.446 + edge=edge->_next_out;
7.447 + while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
7.448 + return *this;
7.449 + }
7.450 + };
7.451 +
7.452 + class OutEdgeIt : public Edge {
7.453 + friend class ListGraph;
7.454 + //node_item* v;
7.455 + //protected:
7.456 + protected: //for alpar
7.457 + OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
7.458 + public:
7.459 + OutEdgeIt() : Edge()/*, v(0)*/ { }
7.460 + OutEdgeIt(const Invalid& i) : Edge(i) { }
7.461 + OutEdgeIt(const ListGraph& G, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
7.462 + protected:
7.463 + OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
7.464 + protected:
7.465 + Node aNode() const { return Node(edge->_tail); }
7.466 + Node bNode() const { return Node(edge->_head); }
7.467 + };
7.468 +
7.469 + class InEdgeIt : public Edge {
7.470 + friend class ListGraph;
7.471 + //node_item* v;
7.472 + //protected:
7.473 + protected: //for alpar
7.474 + InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
7.475 + public:
7.476 + InEdgeIt() : Edge()/*, v(0)*/ { }
7.477 + InEdgeIt(const Invalid& i) : Edge(i) { }
7.478 + InEdgeIt(const ListGraph& G, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
7.479 + protected:
7.480 + InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
7.481 + protected:
7.482 + Node aNode() const { return Node(edge->_head); }
7.483 + Node bNode() const { return Node(edge->_tail); }
7.484 + };
7.485 +
7.486 + class SymEdgeIt : public Edge {
7.487 + friend class ListGraph;
7.488 + bool out_or_in; //1 iff out, 0 iff in
7.489 + //node_item* v;
7.490 + //protected:
7.491 + public: //for alpar
7.492 + SymEdgeIt(const Node& _v) /*: v(_v.node)*/ {
7.493 + out_or_in=1;
7.494 + edge=_v.node->_first_out_edge;
7.495 + if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
7.496 + }
7.497 + public:
7.498 + SymEdgeIt() : Edge() /*, v(0)*/ { }
7.499 + SymEdgeIt(const Invalid& i) : Edge(i) { }
7.500 + SymEdgeIt(const ListGraph& G, Node _v) /*: v(_v.node)*/ {
7.501 + out_or_in=1;
7.502 + edge=_v.node->_first_out_edge;
7.503 + if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
7.504 + }
7.505 + protected:
7.506 + SymEdgeIt& operator++() {
7.507 + if (out_or_in) {
7.508 + node_item* v=edge->_tail;
7.509 + edge=edge->_next_out;
7.510 + if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
7.511 + } else {
7.512 + edge=edge->_next_in;
7.513 + }
7.514 + return *this;
7.515 + }
7.516 + protected:
7.517 + Node aNode() const {
7.518 + return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); }
7.519 + Node bNode() const {
7.520 + return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); }
7.521 + };
7.522 +
7.523 + };
7.524 +
7.525 +// template< typename T >
7.526 +// T ListGraph::first() const {
7.527 +// std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>();" << std::endl;
7.528 +// return T();
7.529 +// }
7.530 +
7.531 +// template<>
7.532 +// ListGraph::NodeIt ListGraph::first<ListGraph::NodeIt>() const {
7.533 +// return firstNode();
7.534 +// }
7.535 +
7.536 +// template<>
7.537 +// ListGraph::EdgeIt ListGraph::first<ListGraph::EdgeIt>() const {
7.538 +// return firstEdge();
7.539 +// }
7.540 +
7.541 +// template< typename T >
7.542 +// T ListGraph::first(ListGraph::Node v) const {
7.543 +// std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>(ListGRaph::Node);" << std::endl;
7.544 +// return T();
7.545 +// }
7.546 +
7.547 +// template<>
7.548 +// ListGraph::OutEdgeIt ListGraph::first<ListGraph::OutEdgeIt>(const ListGraph::Node v) const {
7.549 +// return firstOutEdge(v);
7.550 +// }
7.551 +
7.552 +// template<>
7.553 +// ListGraph::InEdgeIt ListGraph::first<ListGraph::InEdgeIt>(const ListGraph::Node v) const {
7.554 +// return firstInEdge(v);
7.555 +// }
7.556 +
7.557 +// template<>
7.558 +// ListGraph::SymEdgeIt ListGraph::first<ListGraph::SymEdgeIt>(const ListGraph::Node v) const {
7.559 +// return firstSymEdge(v);
7.560 +// }
7.561 +
7.562 +
7.563 +} //namespace hugo
7.564 +
7.565 +#endif //LIST_GRAPH_H
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/src/work/marci/dimacs.h Fri Mar 12 09:19:54 2004 +0000
8.3 @@ -0,0 +1,62 @@
8.4 +// -*- c++ -*-
8.5 +#ifndef DIMACS_H
8.6 +#define DIMACS_H
8.7 +
8.8 +#include <iostream>
8.9 +#include <string>
8.10 +#include <vector>
8.11 +
8.12 +namespace hugo {
8.13 +
8.14 + template<typename Graph, typename CapacityMap>
8.15 + void readDimacsMaxFlow(std::istream& is, Graph &G, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) {
8.16 + G.clear();
8.17 + int cap;
8.18 + char d;
8.19 + std::string problem;
8.20 + char c;
8.21 + int i, j;
8.22 + std::string str;
8.23 + int n, m;
8.24 + std::vector<typename Graph::Node> nodes;
8.25 + while (is>>c) {
8.26 + switch (c) {
8.27 + case 'c': //comment
8.28 + getline(is, str);
8.29 + break;
8.30 +// case 't': //type
8.31 +// getline(is, str);
8.32 +// break;
8.33 + case 'p': //problem definition
8.34 + is >> problem >> n >> m;
8.35 + getline(is, str);
8.36 + nodes.resize(n+1);
8.37 + for (int k=1; k<=n; ++k) nodes[k]=G.addNode();
8.38 + break;
8.39 + case 'n': //node definition
8.40 + if (problem=="sp") { //shortest path problem
8.41 + is >> i;
8.42 + getline(is, str);
8.43 + s=nodes[i];
8.44 + }
8.45 + if (problem=="max") { //max flow problem
8.46 + is >> i >> d;
8.47 + getline(is, str);
8.48 + if (d=='s') s=nodes[i];
8.49 + if (d=='t') t=nodes[i];
8.50 + }
8.51 + break;
8.52 + case 'a':
8.53 + is >> i >> j >> cap;
8.54 + getline(is, str);
8.55 + typename Graph::Edge e=G.addEdge(nodes[i], nodes[j]);
8.56 + capacity.update();
8.57 + capacity.set(e, cap);
8.58 + break;
8.59 + }
8.60 + }
8.61 + }
8.62 +
8.63 +} //namespace hugo
8.64 +
8.65 +#endif //DIMACS_H
9.1 --- a/src/work/marci/edmonds_karp_demo.cc Thu Mar 11 23:31:13 2004 +0000
9.2 +++ b/src/work/marci/edmonds_karp_demo.cc Fri Mar 12 09:19:54 2004 +0000
9.3 @@ -1,9 +1,11 @@
9.4 +// -*- c++ -*-
9.5 #include <iostream>
9.6 #include <fstream>
9.7
9.8 -#include <list_graph.hh>
9.9 -#include <dimacs.hh>
9.10 -#include <edmonds_karp.hh>
9.11 +#include <list_graph.h>
9.12 +#include <smart_graph.h>
9.13 +#include <dimacs.h>
9.14 +#include <edmonds_karp.h>
9.15 #include <time_measure.h>
9.16 #include <graph_wrapper.h>
9.17
9.18 @@ -12,157 +14,160 @@
9.19 // Use a DIMACS max flow file as stdin.
9.20 // read_dimacs_demo < dimacs_max_flow_file
9.21
9.22 -/*
9.23 - struct Ize {
9.24 - };
9.25 +
9.26 +// struct Ize {
9.27 +// };
9.28
9.29 - struct Mize {
9.30 - Ize bumm;
9.31 - };
9.32 +// struct Mize {
9.33 +// Ize bumm;
9.34 +// };
9.35
9.36 - template <typename B>
9.37 - class Huha {
9.38 - public:
9.39 - int u;
9.40 - B brr;
9.41 - };
9.42 -*/
9.43 +// template <typename B>
9.44 +// class Huha {
9.45 +// public:
9.46 +// int u;
9.47 +// B brr;
9.48 +// };
9.49 +
9.50
9.51 int main(int, char **) {
9.52 - typedef ListGraph::NodeIt NodeIt;
9.53 - typedef ListGraph::EachEdgeIt EachEdgeIt;
9.54
9.55 -/*
9.56 - Mize mize[10];
9.57 - Mize bize[0];
9.58 - Mize zize;
9.59 - typedef Mize Tize[0];
9.60 + typedef ListGraph MutableGraph;
9.61
9.62 - std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
9.63 - std::cout << sizeof(bize) << std::endl;
9.64 + typedef SmartGraph Graph;
9.65 + typedef Graph::Node Node;
9.66 + typedef Graph::EdgeIt EdgeIt;
9.67
9.68
9.69 - Huha<Tize> k;
9.70 - std::cout << sizeof(k) << std::endl;
9.71 +// Mize mize[10];
9.72 +// Mize bize[0];
9.73 +// Mize zize;
9.74 +// typedef Mize Tize[0];
9.75
9.76 +// std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
9.77 +// std::cout << sizeof(bize) << std::endl;
9.78
9.79 - struct Bumm {
9.80 - //int a;
9.81 - bool b;
9.82 - };
9.83
9.84 - std::cout << sizeof(Bumm) << std::endl;
9.85 -*/
9.86 +// Huha<Tize> k;
9.87 +// std::cout << sizeof(k) << std::endl;
9.88
9.89 - ListGraph G;
9.90 - NodeIt s, t;
9.91 - ListGraph::EdgeMap<int> cap(G);
9.92 +
9.93 +// struct Bumm {
9.94 +// //int a;
9.95 +// bool b;
9.96 +// };
9.97 +
9.98 +// std::cout << sizeof(Bumm) << std::endl;
9.99 +
9.100 +
9.101 + Graph G;
9.102 + Node s, t;
9.103 + Graph::EdgeMap<int> cap(G);
9.104 readDimacsMaxFlow(std::cin, G, s, t, cap);
9.105 -/*
9.106 - typedef TrivGraphWrapper<ListGraph> TGW;
9.107 - TGW gw(G);
9.108 - TGW::EachNodeIt sw;
9.109 - gw.getFirst(sw);
9.110 - std::cout << "p1:" << gw.nodeNum() << std::endl;
9.111 - gw.erase(sw);
9.112 - std::cout << "p2:" << gw.nodeNum() << std::endl;
9.113
9.114 - typedef const ListGraph cLG;
9.115 - typedef TrivGraphWrapper<const cLG> CTGW;
9.116 - CTGW cgw(G);
9.117 - CTGW::EachNodeIt csw;
9.118 - cgw.getFirst(csw);
9.119 - std::cout << "p1:" << cgw.nodeNum() << std::endl;
9.120 - //cgw.erase(csw);
9.121 - std::cout << "p2:" << cgw.nodeNum() << std::endl;
9.122 -*/
9.123 +// typedef TrivGraphWrapper<Graph> TGW;
9.124 +// TGW gw(G);
9.125 +// TGW::NodeIt sw;
9.126 +// gw./*getF*/first(sw);
9.127 +// std::cout << "p1:" << gw.nodeNum() << std::endl;
9.128 +// gw.erase(sw);
9.129 +// std::cout << "p2:" << gw.nodeNum() << std::endl;
9.130 +
9.131 +// typedef const Graph cLG;
9.132 +// typedef TrivGraphWrapper<const cLG> CTGW;
9.133 +// CTGW cgw(G);
9.134 +// CTGW::NodeIt csw;
9.135 +// cgw./*getF*/first(csw);
9.136 +// std::cout << "p1:" << cgw.nodeNum() << std::endl;
9.137 +// //cgw.erase(csw);
9.138 +// std::cout << "p2:" << cgw.nodeNum() << std::endl;
9.139 +
9.140
9.141 {
9.142 - std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
9.143 - ListGraph::EdgeMap<int> flow(G); //0 flow
9.144 + std::cout << "SmartGraph..." << std::endl;
9.145 + std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
9.146 + Graph::EdgeMap<int> flow(G); //0 flow
9.147
9.148 - Timer ts;
9.149 - ts.reset();
9.150 - //double pre_time=currTime();
9.151 - MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
9.152 - //max_flow_test.augmentWithBlockingFlow<ListGraph>();
9.153 - int i=0;
9.154 - while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) {
9.155 -// for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
9.156 + Timer ts;
9.157 + ts.reset();
9.158 +
9.159 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
9.160 + //max_flow_test.augmentWithBlockingFlow<Graph>();
9.161 + int i=0;
9.162 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
9.163 +// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
9.164 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
9.165 // }
9.166 // std::cout<<std::endl;
9.167 - ++i;
9.168 - }
9.169 - //double post_time=currTime();
9.170 + ++i;
9.171 + }
9.172
9.173 - //std::cout << "maximum flow: "<< std::endl;
9.174 - //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
9.175 - // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
9.176 - //}
9.177 - //std::cout<<std::endl;
9.178 - std::cout << "elapsed time: " << ts << std::endl;
9.179 - std::cout << "number of augmentation phases: " << i << std::endl;
9.180 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
9.181 +// std::cout << "maximum flow: "<< std::endl;
9.182 +// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
9.183 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
9.184 +// }
9.185 +// std::cout<<std::endl;
9.186 + std::cout << "elapsed time: " << ts << std::endl;
9.187 + std::cout << "number of augmentation phases: " << i << std::endl;
9.188 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
9.189 }
9.190
9.191 {
9.192 - std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
9.193 - ListGraph::EdgeMap<int> flow(G); //0 flow
9.194 + std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
9.195 + Graph::EdgeMap<int> flow(G); //0 flow
9.196
9.197 - Timer ts;
9.198 - ts.reset();
9.199 - //double pre_time=currTime();
9.200 - MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
9.201 - //max_flow_test.augmentWithBlockingFlow<ListGraph>();
9.202 - int i=0;
9.203 - while (max_flow_test.augmentOnBlockingFlow2()) {
9.204 -// for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
9.205 + Timer ts;
9.206 + ts.reset();
9.207 +
9.208 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
9.209 + //max_flow_test.augmentWithBlockingFlow<Graph>();
9.210 + int i=0;
9.211 + while (max_flow_test.augmentOnBlockingFlow2()) {
9.212 +// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
9.213 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
9.214 // }
9.215 // std::cout<<std::endl;
9.216 - ++i;
9.217 - }
9.218 - //double post_time=currTime();
9.219 + ++i;
9.220 + }
9.221
9.222 - //std::cout << "maximum flow: "<< std::endl;
9.223 - //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
9.224 - // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
9.225 - //}
9.226 - //std::cout<<std::endl;
9.227 - std::cout << "elapsed time: " << ts << std::endl;
9.228 - std::cout << "number of augmentation phases: " << i << std::endl;
9.229 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
9.230 +// std::cout << "maximum flow: "<< std::endl;
9.231 +// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
9.232 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
9.233 +// }
9.234 +// std::cout<<std::endl;
9.235 + std::cout << "elapsed time: " << ts << std::endl;
9.236 + std::cout << "number of augmentation phases: " << i << std::endl;
9.237 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
9.238 }
9.239
9.240 {
9.241 - std::cout << "edmonds karp demo (shortest path augmentation)..." << std::endl;
9.242 - ListGraph::EdgeMap<int> flow(G); //0 flow
9.243 + std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
9.244 + Graph::EdgeMap<int> flow(G); //0 flow
9.245
9.246 - Timer ts;
9.247 - ts.reset();
9.248 - //double pre_time=currTime();
9.249 - MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
9.250 - //max_flow_test.augmentWithBlockingFlow<ListGraph>();
9.251 - int i=0;
9.252 - while (max_flow_test.augmentOnShortestPath()) {
9.253 -// for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
9.254 + Timer ts;
9.255 + ts.reset();
9.256 +
9.257 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
9.258 + //max_flow_test.augmentWithBlockingFlow<Graph>();
9.259 + int i=0;
9.260 + while (max_flow_test.augmentOnShortestPath()) {
9.261 +// for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
9.262 // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
9.263 // }
9.264 // std::cout<<std::endl;
9.265 - ++i;
9.266 + ++i;
9.267 + }
9.268 +
9.269 +// std::cout << "maximum flow: "<< std::endl;
9.270 +// for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
9.271 +// std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
9.272 +// }
9.273 +// std::cout<<std::endl;
9.274 + std::cout << "elapsed time: " << ts << std::endl;
9.275 + std::cout << "number of augmentation phases: " << i << std::endl;
9.276 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
9.277 }
9.278 - //double post_time=currTime();
9.279
9.280 - //std::cout << "maximum flow: "<< std::endl;
9.281 - //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
9.282 - // std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
9.283 - //}
9.284 - //std::cout<<std::endl;
9.285 - std::cout << "elapsed time: " << ts << std::endl;
9.286 - std::cout << "number of augmentation phases: " << i << std::endl;
9.287 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
9.288 - }
9.289
9.290 return 0;
9.291 }
10.1 --- a/src/work/marci/graph_wrapper.h Thu Mar 11 23:31:13 2004 +0000
10.2 +++ b/src/work/marci/graph_wrapper.h Fri Mar 12 09:19:54 2004 +0000
10.3 @@ -1,7 +1,9 @@
10.4 -// -*-mode: c++; -*-
10.5 +// -*- c++ -*-
10.6 #ifndef GRAPH_WRAPPER_H
10.7 #define GRAPH_WRAPPER_H
10.8
10.9 +#include <invalid.h>
10.10 +
10.11 namespace hugo {
10.12
10.13 template<typename Graph>
10.14 @@ -11,14 +13,14 @@
10.15 public:
10.16 typedef Graph BaseGraph;
10.17
10.18 + typedef typename Graph::Node Node;
10.19 typedef typename Graph::NodeIt NodeIt;
10.20 - typedef typename Graph::EachNodeIt EachNodeIt;
10.21
10.22 - typedef typename Graph::EdgeIt EdgeIt;
10.23 + typedef typename Graph::Edge Edge;
10.24 typedef typename Graph::OutEdgeIt OutEdgeIt;
10.25 typedef typename Graph::InEdgeIt InEdgeIt;
10.26 //typedef typename Graph::SymEdgeIt SymEdgeIt;
10.27 - typedef typename Graph::EachEdgeIt EachEdgeIt;
10.28 + typedef typename Graph::EdgeIt EdgeIt;
10.29
10.30 //TrivGraphWrapper() : graph(0) { }
10.31 TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
10.32 @@ -26,22 +28,22 @@
10.33 void setGraph(Graph& _graph) { graph = &_graph; }
10.34 Graph& getGraph() const { return (*graph); }
10.35
10.36 - template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
10.37 - template<typename I, typename P> I& getFirst(I& i, const P& p) const {
10.38 - return graph->getFirst(i, p); }
10.39 + template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
10.40 + template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
10.41 + return graph->/*getF*/first(i, p); }
10.42
10.43 template<typename I> I getNext(const I& i) const {
10.44 return graph->getNext(i); }
10.45 template<typename I> I& next(I &i) const { return graph->next(i); }
10.46
10.47 template< typename It > It first() const {
10.48 - It e; getFirst(e); return e; }
10.49 + It e; /*getF*/first(e); return e; }
10.50
10.51 - template< typename It > It first(const NodeIt& v) const {
10.52 - It e; getFirst(e, v); return e; }
10.53 + template< typename It > It first(const Node& v) const {
10.54 + It e; /*getF*/first(e, v); return e; }
10.55
10.56 - NodeIt head(const EdgeIt& e) const { return graph->head(e); }
10.57 - NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
10.58 + Node head(const Edge& e) const { return graph->head(e); }
10.59 + Node tail(const Edge& e) const { return graph->tail(e); }
10.60
10.61 template<typename I> bool valid(const I& i) const
10.62 { return graph->valid(i); }
10.63 @@ -52,13 +54,13 @@
10.64 int nodeNum() const { return graph->nodeNum(); }
10.65 int edgeNum() const { return graph->edgeNum(); }
10.66
10.67 - template<typename I> NodeIt aNode(const I& e) const {
10.68 + template<typename I> Node aNode(const I& e) const {
10.69 return graph->aNode(e); }
10.70 - template<typename I> NodeIt bNode(const I& e) const {
10.71 + template<typename I> Node bNode(const I& e) const {
10.72 return graph->bNode(e); }
10.73
10.74 - NodeIt addNode() const { return graph->addNode(); }
10.75 - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
10.76 + Node addNode() const { return graph->addNode(); }
10.77 + Edge addEdge(const Node& tail, const Node& head) const {
10.78 return graph->addEdge(tail, head); }
10.79
10.80 template<typename I> void erase(const I& i) const { graph->erase(i); }
10.81 @@ -90,14 +92,14 @@
10.82 public:
10.83 typedef Graph BaseGraph;
10.84
10.85 - typedef typename Graph::NodeIt NodeIt;
10.86 - typedef typename Graph::EachNodeIt EachNodeIt;
10.87 + typedef typename Graph::Node Node;
10.88 + typedef typename Graph::NodeIt NodeIt;
10.89
10.90 - typedef typename Graph::EdgeIt EdgeIt;
10.91 + typedef typename Graph::Edge Edge;
10.92 typedef typename Graph::OutEdgeIt InEdgeIt;
10.93 typedef typename Graph::InEdgeIt OutEdgeIt;
10.94 //typedef typename Graph::SymEdgeIt SymEdgeIt;
10.95 - typedef typename Graph::EachEdgeIt EachEdgeIt;
10.96 + typedef typename Graph::EdgeIt EdgeIt;
10.97
10.98 //RevGraphWrapper() : graph(0) { }
10.99 RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
10.100 @@ -105,22 +107,22 @@
10.101 void setGraph(Graph& _graph) { graph = &_graph; }
10.102 Graph& getGraph() const { return (*graph); }
10.103
10.104 - template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
10.105 - template<typename I, typename P> I& getFirst(I& i, const P& p) const {
10.106 - return graph->getFirst(i, p); }
10.107 + template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
10.108 + template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
10.109 + return graph->/*getF*/first(i, p); }
10.110
10.111 template<typename I> I getNext(const I& i) const {
10.112 return graph->getNext(i); }
10.113 template<typename I> I& next(I &i) const { return graph->next(i); }
10.114
10.115 template< typename It > It first() const {
10.116 - It e; getFirst(e); return e; }
10.117 + It e; /*getF*/first(e); return e; }
10.118
10.119 - template< typename It > It first(const NodeIt& v) const {
10.120 - It e; getFirst(e, v); return e; }
10.121 + template< typename It > It first(const Node& v) const {
10.122 + It e; /*getF*/first(e, v); return e; }
10.123
10.124 - NodeIt head(const EdgeIt& e) const { return graph->tail(e); }
10.125 - NodeIt tail(const EdgeIt& e) const { return graph->head(e); }
10.126 + Node head(const Edge& e) const { return graph->tail(e); }
10.127 + Node tail(const Edge& e) const { return graph->head(e); }
10.128
10.129 template<typename I> bool valid(const I& i) const
10.130 { return graph->valid(i); }
10.131 @@ -128,13 +130,13 @@
10.132 //template<typename I> void setInvalid(const I &i);
10.133 //{ return graph->setInvalid(i); }
10.134
10.135 - template<typename I> NodeIt aNode(const I& e) const {
10.136 + template<typename I> Node aNode(const I& e) const {
10.137 return graph->aNode(e); }
10.138 - template<typename I> NodeIt bNode(const I& e) const {
10.139 + template<typename I> Node bNode(const I& e) const {
10.140 return graph->bNode(e); }
10.141
10.142 - NodeIt addNode() const { return graph->addNode(); }
10.143 - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
10.144 + Node addNode() const { return graph->addNode(); }
10.145 + Edge addEdge(const Node& tail, const Node& head) const {
10.146 return graph->addEdge(tail, head); }
10.147
10.148 int nodeNum() const { return graph->nodeNum(); }
10.149 @@ -169,17 +171,17 @@
10.150 public:
10.151 typedef Graph BaseGraph;
10.152
10.153 + typedef typename Graph::Node Node;
10.154 typedef typename Graph::NodeIt NodeIt;
10.155 - typedef typename Graph::EachNodeIt EachNodeIt;
10.156
10.157 - //typedef typename Graph::EdgeIt EdgeIt;
10.158 + //typedef typename Graph::Edge Edge;
10.159 //typedef typename Graph::OutEdgeIt OutEdgeIt;
10.160 //typedef typename Graph::InEdgeIt InEdgeIt;
10.161 //typedef typename Graph::SymEdgeIt SymEdgeIt;
10.162 - //typedef typename Graph::EachEdgeIt EachEdgeIt;
10.163 + //typedef typename Graph::EdgeIt EdgeIt;
10.164
10.165 //private:
10.166 - typedef typename Graph::EdgeIt GraphEdgeIt;
10.167 + typedef typename Graph::Edge GraphEdge;
10.168 typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
10.169 typedef typename Graph::InEdgeIt GraphInEdgeIt;
10.170 //public:
10.171 @@ -190,48 +192,63 @@
10.172 void setGraph(Graph& _graph) { graph = &_graph; }
10.173 Graph& getGraph() const { return (*graph); }
10.174
10.175 - class EdgeIt {
10.176 + class Edge {
10.177 friend class UndirGraphWrapper<Graph>;
10.178 bool out_or_in; //true iff out
10.179 GraphOutEdgeIt out;
10.180 GraphInEdgeIt in;
10.181 public:
10.182 - EdgeIt() : out_or_in(true), out(), in() { }
10.183 - operator GraphEdgeIt() const {
10.184 + Edge() : out_or_in(), out(), in() { }
10.185 + Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
10.186 + operator GraphEdge() const {
10.187 if (out_or_in) return(out); else return(in);
10.188 }
10.189 + friend bool operator==(const Edge& u, const Edge& v) {
10.190 + if (v.out_or_in)
10.191 + return (u.out_or_in && u.out==v.out);
10.192 + else
10.193 + return (!u.out_or_in && u.in==v.in);
10.194 + }
10.195 + friend bool operator!=(const Edge& u, const Edge& v) {
10.196 + if (v.out_or_in)
10.197 + return (!u.out_or_in || u.out!=v.out);
10.198 + else
10.199 + return (u.out_or_in || u.in!=v.in);
10.200 + }
10.201 };
10.202
10.203 - class OutEdgeIt : public EdgeIt {
10.204 + class OutEdgeIt : public Edge {
10.205 friend class UndirGraphWrapper<Graph>;
10.206 public:
10.207 - OutEdgeIt() : EdgeIt() { }
10.208 - OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() {
10.209 - _G.graph->getFirst(out, n);
10.210 + OutEdgeIt() : Edge() { }
10.211 + OutEdgeIt(const Invalid& i) : Edge(i) { }
10.212 + OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() {
10.213 + out_or_in=true;
10.214 + _G.graph->/*getF*/first(out, n);
10.215 if (!(_G.graph->valid(out))) {
10.216 out_or_in=false;
10.217 - _G.graph->getFirst(in, n);
10.218 + _G.graph->/*getF*/first(in, n);
10.219 }
10.220 }
10.221 };
10.222
10.223 - OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
10.224 + OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
10.225 e.out_or_in=true;
10.226 - graph->getFirst(e.out, n);
10.227 + graph->/*getF*/first(e.out, n);
10.228 if (!(graph->valid(e.out))) {
10.229 e.out_or_in=false;
10.230 - graph->getFirst(e.in, n);
10.231 + graph->/*getF*/first(e.in, n);
10.232 }
10.233 return e;
10.234 }
10.235
10.236 OutEdgeIt& next(OutEdgeIt& e) const {
10.237 if (e.out_or_in) {
10.238 - NodeIt n=graph->tail(e.out);
10.239 + Node n=graph->tail(e.out);
10.240 graph->next(e.out);
10.241 if (!graph->valid(e.out)) {
10.242 e.out_or_in=false;
10.243 - graph->getFirst(e.in, n);
10.244 + graph->/*getF*/first(e.in, n);
10.245 }
10.246 } else {
10.247 graph->next(e.in);
10.248 @@ -239,29 +256,29 @@
10.249 return e;
10.250 }
10.251
10.252 - NodeIt aNode(const OutEdgeIt& e) const {
10.253 + Node aNode(const OutEdgeIt& e) const {
10.254 if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
10.255 - NodeIt bNode(const OutEdgeIt& e) const {
10.256 + Node bNode(const OutEdgeIt& e) const {
10.257 if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
10.258
10.259 typedef OutEdgeIt InEdgeIt;
10.260
10.261 - template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
10.262 -// template<typename I, typename P> I& getFirst(I& i, const P& p) const {
10.263 -// return graph->getFirst(i, p); }
10.264 + template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
10.265 +// template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
10.266 +// return graph->/*getF*/first(i, p); }
10.267
10.268 template<typename I> I getNext(const I& i) const {
10.269 return graph->getNext(i); }
10.270 template<typename I> I& next(I &i) const { return graph->next(i); }
10.271
10.272 template< typename It > It first() const {
10.273 - It e; getFirst(e); return e; }
10.274 + It e; /*getF*/first(e); return e; }
10.275
10.276 - template< typename It > It first(const NodeIt& v) const {
10.277 - It e; getFirst(e, v); return e; }
10.278 + template< typename It > It first(const Node& v) const {
10.279 + It e; /*getF*/first(e, v); return e; }
10.280
10.281 - NodeIt head(const EdgeIt& e) const { return graph->head(e); }
10.282 - NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
10.283 + Node head(const Edge& e) const { return graph->head(e); }
10.284 + Node tail(const Edge& e) const { return graph->tail(e); }
10.285
10.286 template<typename I> bool valid(const I& i) const
10.287 { return graph->valid(i); }
10.288 @@ -272,13 +289,13 @@
10.289 int nodeNum() const { return graph->nodeNum(); }
10.290 int edgeNum() const { return graph->edgeNum(); }
10.291
10.292 -// template<typename I> NodeIt aNode(const I& e) const {
10.293 +// template<typename I> Node aNode(const I& e) const {
10.294 // return graph->aNode(e); }
10.295 -// template<typename I> NodeIt bNode(const I& e) const {
10.296 +// template<typename I> Node bNode(const I& e) const {
10.297 // return graph->bNode(e); }
10.298
10.299 - NodeIt addNode() const { return graph->addNode(); }
10.300 - EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
10.301 + Node addNode() const { return graph->addNode(); }
10.302 + Edge addEdge(const Node& tail, const Node& head) const {
10.303 return graph->addEdge(tail, head); }
10.304
10.305 template<typename I> void erase(const I& i) const { graph->erase(i); }
10.306 @@ -312,10 +329,10 @@
10.307 // public:
10.308 // typedef Graph BaseGraph;
10.309
10.310 +// typedef typename Graph::Node Node;
10.311 +// typedef typename Graph::Edge Edge;
10.312 +
10.313 // typedef typename Graph::NodeIt NodeIt;
10.314 -// typedef typename Graph::EdgeIt EdgeIt;
10.315 -
10.316 -// typedef typename Graph::EachNodeIt EachNodeIt;
10.317
10.318 // //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
10.319 // //iranyitatlant, ami van
10.320 @@ -323,29 +340,29 @@
10.321 // typedef typename Graph::OutEdgeIt SymEdgeIt;
10.322 // //typedef typename Graph::InEdgeIt SymEdgeIt;
10.323 // //typedef typename Graph::SymEdgeIt SymEdgeIt;
10.324 -// typedef typename Graph::EachEdgeIt EachEdgeIt;
10.325 +// typedef typename Graph::EdgeIt EdgeIt;
10.326
10.327 // int nodeNum() const { return graph->nodeNum(); }
10.328 // int edgeNum() const { return graph->edgeNum(); }
10.329
10.330 -// template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
10.331 -// template<typename I, typename P> I& getFirst(I& i, const P& p) const {
10.332 -// return graph->getFirst(i, p); }
10.333 +// template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
10.334 +// template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
10.335 +// return graph->/*getF*/first(i, p); }
10.336 // //template<typename I> I next(const I i); { return graph->goNext(i); }
10.337 // //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
10.338
10.339 // template< typename It > It first() const {
10.340 -// It e; getFirst(e); return e; }
10.341 +// It e; /*getF*/first(e); return e; }
10.342
10.343 -// template< typename It > It first(NodeIt v) const {
10.344 -// It e; getFirst(e, v); return e; }
10.345 +// template< typename It > It first(Node v) const {
10.346 +// It e; /*getF*/first(e, v); return e; }
10.347
10.348 -// NodeIt head(const EdgeIt& e) const { return graph->head(e); }
10.349 -// NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
10.350 +// Node head(const Edge& e) const { return graph->head(e); }
10.351 +// Node tail(const Edge& e) const { return graph->tail(e); }
10.352
10.353 -// template<typename I> NodeIt aNode(const I& e) const {
10.354 +// template<typename I> Node aNode(const I& e) const {
10.355 // return graph->aNode(e); }
10.356 -// template<typename I> NodeIt bNode(const I& e) const {
10.357 +// template<typename I> Node bNode(const I& e) const {
10.358 // return graph->bNode(e); }
10.359
10.360 // //template<typename I> bool valid(const I i);
10.361 @@ -354,8 +371,8 @@
10.362 // //template<typename I> void setInvalid(const I &i);
10.363 // //{ return graph->setInvalid(i); }
10.364
10.365 -// NodeIt addNode() { return graph->addNode(); }
10.366 -// EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
10.367 +// Node addNode() { return graph->addNode(); }
10.368 +// Edge addEdge(const Node& tail, const Node& head) {
10.369 // return graph->addEdge(tail, head); }
10.370
10.371 // template<typename I> void erase(const I& i) { graph->erase(i); }
10.372 @@ -377,192 +394,207 @@
10.373 class ResGraphWrapper {
10.374 public:
10.375 typedef Graph BaseGraph;
10.376 + typedef typename Graph::Node Node;
10.377 typedef typename Graph::NodeIt NodeIt;
10.378 - typedef typename Graph::EachNodeIt EachNodeIt;
10.379 private:
10.380 typedef typename Graph::OutEdgeIt OldOutEdgeIt;
10.381 typedef typename Graph::InEdgeIt OldInEdgeIt;
10.382 - const Graph* G;
10.383 + const Graph* graph;
10.384 FlowMap* flow;
10.385 const CapacityMap* capacity;
10.386 public:
10.387
10.388 ResGraphWrapper(const Graph& _G, FlowMap& _flow,
10.389 const CapacityMap& _capacity) :
10.390 - G(&_G), flow(&_flow), capacity(&_capacity) { }
10.391 -// ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
10.392 -// G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
10.393 + graph(&_G), flow(&_flow), capacity(&_capacity) { }
10.394
10.395 void setGraph(const Graph& _graph) { graph = &_graph; }
10.396 - const Graph& getGraph() const { return (*G); }
10.397 + const Graph& getGraph() const { return (*graph); }
10.398
10.399 - class EdgeIt;
10.400 + class Edge;
10.401 class OutEdgeIt;
10.402 - friend class EdgeIt;
10.403 + friend class Edge;
10.404 friend class OutEdgeIt;
10.405
10.406 - class EdgeIt {
10.407 + class Edge {
10.408 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
10.409 protected:
10.410 bool out_or_in; //true, iff out
10.411 OldOutEdgeIt out;
10.412 OldInEdgeIt in;
10.413 public:
10.414 - EdgeIt() : out_or_in(true) { }
10.415 + Edge() : out_or_in(true) { }
10.416 + Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
10.417 // bool valid() const {
10.418 // return out_or_in && out.valid() || in.valid(); }
10.419 + friend bool operator==(const Edge& u, const Edge& v) {
10.420 + if (v.out_or_in)
10.421 + return (u.out_or_in && u.out==v.out);
10.422 + else
10.423 + return (!u.out_or_in && u.in==v.in);
10.424 + }
10.425 + friend bool operator!=(const Edge& u, const Edge& v) {
10.426 + if (v.out_or_in)
10.427 + return (!u.out_or_in || u.out!=v.out);
10.428 + else
10.429 + return (u.out_or_in || u.in!=v.in);
10.430 + }
10.431 };
10.432
10.433
10.434 - class OutEdgeIt : public EdgeIt {
10.435 + class OutEdgeIt : public Edge {
10.436 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
10.437 public:
10.438 OutEdgeIt() { }
10.439 //FIXME
10.440 - OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { }
10.441 + OutEdgeIt(const Edge& e) : Edge(e) { }
10.442 + OutEdgeIt(const Invalid& i) : Edge(i) { }
10.443 private:
10.444 - OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, NodeIt v) : EdgeIt() {
10.445 - resG.G->getFirst(out, v);
10.446 - while( out.valid() && !(resG.free(out)>0) ) { ++out; }
10.447 - if (!out.valid()) {
10.448 + OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
10.449 + resG.graph->/*getF*/first(out, v);
10.450 + while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
10.451 + if (!resG.graph->valid(out)) {
10.452 out_or_in=0;
10.453 - resG.G->getFirst(in, v);
10.454 - while( in.valid() && !(resG.free(in)>0) ) { ++in; }
10.455 + resG.graph->/*getF*/first(in, v);
10.456 + while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
10.457 }
10.458 }
10.459 // public:
10.460 // OutEdgeIt& operator++() {
10.461 // if (out_or_in) {
10.462 -// NodeIt v=/*resG->*/G->aNode(out);
10.463 +// Node v=/*resG->*/G->aNode(out);
10.464 // ++out;
10.465 -// while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
10.466 +// while( out.valid() && !(Edge::free()>0) ) { ++out; }
10.467 // if (!out.valid()) {
10.468 // out_or_in=0;
10.469 -// G->getFirst(in, v);
10.470 -// while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
10.471 +// G->/*getF*/first(in, v);
10.472 +// while( in.valid() && !(Edge::free()>0) ) { ++in; }
10.473 // }
10.474 // } else {
10.475 // ++in;
10.476 -// while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
10.477 +// while( in.valid() && !(Edge::free()>0) ) { ++in; }
10.478 // }
10.479 // return *this;
10.480 // }
10.481 };
10.482
10.483 - class EachEdgeIt : public EdgeIt {
10.484 + class EdgeIt : public Edge {
10.485 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
10.486 - typename Graph::EachNodeIt v;
10.487 + typename Graph::NodeIt v;
10.488 public:
10.489 - EachEdgeIt() { }
10.490 - //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
10.491 - EachEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : EdgeIt() {
10.492 - resG.G->getFirst(v);
10.493 - if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt();
10.494 - while (out.valid() && !(resG.free(out)>0) ) { ++out; }
10.495 - while (v.valid() && !out.valid()) {
10.496 - ++v;
10.497 - if (v.valid()) resG.G->getFirst(out, v);
10.498 - while (out.valid() && !(resG.free(out)>0) ) { ++out; }
10.499 + EdgeIt() { }
10.500 + //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
10.501 + EdgeIt(const Invalid& i) : Edge(i) { }
10.502 + EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
10.503 + resG.graph->/*getF*/first(v);
10.504 + if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); else out=OldOutEdgeIt(INVALID);
10.505 + while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
10.506 + while (resG.graph->valid(v) && !resG.graph->valid(out)) {
10.507 + resG.graph->next(v);
10.508 + if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v);
10.509 + while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
10.510 }
10.511 - if (!out.valid()) {
10.512 + if (!resG.graph->valid(out)) {
10.513 out_or_in=0;
10.514 - resG.G->getFirst(v);
10.515 - if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt();
10.516 - while (in.valid() && !(resG.free(in)>0) ) { ++in; }
10.517 - while (v.valid() && !in.valid()) {
10.518 - ++v;
10.519 - if (v.valid()) resG.G->getFirst(in, v);
10.520 - while (in.valid() && !(resG.free(in)>0) ) { ++in; }
10.521 + resG.graph->/*getF*/first(v);
10.522 + if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); else in=OldInEdgeIt(INVALID);
10.523 + while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
10.524 + while (resG.graph->valid(v) && !resG.graph->valid(in)) {
10.525 + resG.graph->next(v);
10.526 + if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v);
10.527 + while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
10.528 }
10.529 }
10.530 }
10.531 -// EachEdgeIt& operator++() {
10.532 +// EdgeIt& operator++() {
10.533 // if (out_or_in) {
10.534 // ++out;
10.535 -// while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
10.536 +// while (out.valid() && !(Edge::free()>0) ) { ++out; }
10.537 // while (v.valid() && !out.valid()) {
10.538 // ++v;
10.539 -// if (v.valid()) G->getFirst(out, v);
10.540 -// while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
10.541 +// if (v.valid()) G->/*getF*/first(out, v);
10.542 +// while (out.valid() && !(Edge::free()>0) ) { ++out; }
10.543 // }
10.544 // if (!out.valid()) {
10.545 // out_or_in=0;
10.546 -// G->getFirst(v);
10.547 -// if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
10.548 -// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
10.549 +// G->/*getF*/first(v);
10.550 +// if (v.valid()) G->/*getF*/first(in, v); else in=OldInEdgeIt();
10.551 +// while (in.valid() && !(Edge::free()>0) ) { ++in; }
10.552 // while (v.valid() && !in.valid()) {
10.553 // ++v;
10.554 -// if (v.valid()) G->getFirst(in, v);
10.555 -// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
10.556 +// if (v.valid()) G->/*getF*/first(in, v);
10.557 +// while (in.valid() && !(Edge::free()>0) ) { ++in; }
10.558 // }
10.559 // }
10.560 // } else {
10.561 // ++in;
10.562 -// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
10.563 +// while (in.valid() && !(Edge::free()>0) ) { ++in; }
10.564 // while (v.valid() && !in.valid()) {
10.565 // ++v;
10.566 -// if (v.valid()) G->getFirst(in, v);
10.567 -// while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
10.568 +// if (v.valid()) G->/*getF*/first(in, v);
10.569 +// while (in.valid() && !(Edge::free()>0) ) { ++in; }
10.570 // }
10.571 // }
10.572 // return *this;
10.573 // }
10.574 };
10.575
10.576 - EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); }
10.577 - OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const {
10.578 + NodeIt& /*getF*/first(NodeIt& v) const { return graph->/*getF*/first(v); }
10.579 + OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const {
10.580 e=OutEdgeIt(*this, v);
10.581 + return e;
10.582 }
10.583 - EachEdgeIt& getFirst(EachEdgeIt& e) const {
10.584 - e=EachEdgeIt(*this);
10.585 + EdgeIt& /*getF*/first(EdgeIt& e) const {
10.586 + e=EdgeIt(*this);
10.587 + return e;
10.588 }
10.589
10.590 - EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
10.591 + NodeIt& next(NodeIt& n) const { return graph->next(n); }
10.592
10.593 OutEdgeIt& next(OutEdgeIt& e) const {
10.594 if (e.out_or_in) {
10.595 - NodeIt v=G->aNode(e.out);
10.596 - ++(e.out);
10.597 - while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
10.598 - if (!G->valid(e.out)) {
10.599 + Node v=graph->aNode(e.out);
10.600 + graph->next(e.out);
10.601 + while( graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
10.602 + if (!graph->valid(e.out)) {
10.603 e.out_or_in=0;
10.604 - G->getFirst(e.in, v);
10.605 - while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
10.606 + graph->/*getF*/first(e.in, v);
10.607 + while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
10.608 }
10.609 } else {
10.610 - ++(e.in);
10.611 - while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
10.612 + graph->next(e.in);
10.613 + while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
10.614 }
10.615 return e;
10.616 }
10.617
10.618 - EachEdgeIt& next(EachEdgeIt& e) const {
10.619 + EdgeIt& next(EdgeIt& e) const {
10.620 if (e.out_or_in) {
10.621 - ++(e.out);
10.622 - while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
10.623 - while (G->valid(e.v) && !G->valid(e.out)) {
10.624 - ++(e.v);
10.625 - if (G->valid(e.v)) G->getFirst(e.out, e.v);
10.626 - while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
10.627 + graph->next(e.out);
10.628 + while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
10.629 + while (graph->valid(e.v) && !graph->valid(e.out)) {
10.630 + graph->next(e.v);
10.631 + if (graph->valid(e.v)) graph->/*getF*/first(e.out, e.v);
10.632 + while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
10.633 }
10.634 - if (!G->valid(e.out)) {
10.635 + if (!graph->valid(e.out)) {
10.636 e.out_or_in=0;
10.637 - G->getFirst(e.v);
10.638 - if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
10.639 - while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
10.640 - while (G->valid(e.v) && !G->valid(e.in)) {
10.641 - ++(e.v);
10.642 - if (G->valid(e.v)) G->getFirst(e.in, e.v);
10.643 - while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
10.644 + graph->/*getF*/first(e.v);
10.645 + if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); else e.in=OldInEdgeIt(INVALID);
10.646 + while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
10.647 + while (graph->valid(e.v) && !graph->valid(e.in)) {
10.648 + graph->next(e.v);
10.649 + if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v);
10.650 + while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
10.651 }
10.652 }
10.653 } else {
10.654 - ++(e.in);
10.655 - while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
10.656 - while (G->valid(e.v) && !G->valid(e.in)) {
10.657 - ++(e.v);
10.658 - if (G->valid(e.v)) G->getFirst(e.in, e.v);
10.659 - while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
10.660 + graph->next(e.in);
10.661 + while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
10.662 + while (graph->valid(e.v) && !graph->valid(e.in)) {
10.663 + graph->next(e.v);
10.664 + if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v);
10.665 + while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
10.666 }
10.667 }
10.668 return e;
10.669 @@ -572,41 +604,41 @@
10.670 template< typename It >
10.671 It first() const {
10.672 It e;
10.673 - getFirst(e);
10.674 + /*getF*/first(e);
10.675 return e;
10.676 }
10.677
10.678 template< typename It >
10.679 - It first(NodeIt v) const {
10.680 + It first(Node v) const {
10.681 It e;
10.682 - getFirst(e, v);
10.683 + /*getF*/first(e, v);
10.684 return e;
10.685 }
10.686
10.687 - NodeIt tail(EdgeIt e) const {
10.688 - return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
10.689 - NodeIt head(EdgeIt e) const {
10.690 - return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
10.691 + Node tail(Edge e) const {
10.692 + return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
10.693 + Node head(Edge e) const {
10.694 + return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
10.695
10.696 - NodeIt aNode(OutEdgeIt e) const {
10.697 - return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
10.698 - NodeIt bNode(OutEdgeIt e) const {
10.699 - return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
10.700 + Node aNode(OutEdgeIt e) const {
10.701 + return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
10.702 + Node bNode(OutEdgeIt e) const {
10.703 + return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
10.704
10.705 - int id(NodeIt v) const { return G->id(v); }
10.706 + int id(Node v) const { return graph->id(v); }
10.707
10.708 - bool valid(NodeIt n) const { return G->valid(n); }
10.709 - bool valid(EdgeIt e) const {
10.710 - return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
10.711 + bool valid(Node n) const { return graph->valid(n); }
10.712 + bool valid(Edge e) const {
10.713 + return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
10.714
10.715 - void augment(const EdgeIt& e, Number a) const {
10.716 + void augment(const Edge& e, Number a) const {
10.717 if (e.out_or_in)
10.718 flow->set(e.out, flow->get(e.out)+a);
10.719 else
10.720 flow->set(e.in, flow->get(e.in)-a);
10.721 }
10.722
10.723 - Number free(const EdgeIt& e) const {
10.724 + Number free(const Edge& e) const {
10.725 if (e.out_or_in)
10.726 return (capacity->get(e.out)-flow->get(e.out));
10.727 else
10.728 @@ -633,10 +665,10 @@
10.729 // class NodeMap {
10.730 // typename Graph::NodeMap<T> node_map;
10.731 // public:
10.732 -// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
10.733 -// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
10.734 -// void set(NodeIt nit, T a) { node_map.set(nit, a); }
10.735 -// T get(NodeIt nit) const { return node_map.get(nit); }
10.736 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
10.737 +// NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
10.738 +// void set(Node nit, T a) { node_map.set(nit, a); }
10.739 +// T get(Node nit) const { return node_map.get(nit); }
10.740 // };
10.741
10.742 template <typename T>
10.743 @@ -645,13 +677,13 @@
10.744 public:
10.745 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { }
10.746 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { }
10.747 - void set(EdgeIt e, T a) {
10.748 + void set(Edge e, T a) {
10.749 if (e.out_or_in)
10.750 forward_map.set(e.out, a);
10.751 else
10.752 backward_map.set(e.in, a);
10.753 }
10.754 - T get(EdgeIt e) {
10.755 + T get(Edge e) {
10.756 if (e.out_or_in)
10.757 return forward_map.get(e.out);
10.758 else
10.759 @@ -670,9 +702,9 @@
10.760 const CapacityMap& _capacity) :
10.761 ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
10.762 first_out_edges(*this) /*, dist(*this)*/ {
10.763 - for(EachNodeIt n=this->template first<EachNodeIt>(); this->valid(n); this->next(n)) {
10.764 + for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
10.765 OutEdgeIt e;
10.766 - ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
10.767 + ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n);
10.768 first_out_edges.set(n, e);
10.769 }
10.770 }
10.771 @@ -685,49 +717,49 @@
10.772
10.773 //typedef Graph BaseGraph;
10.774
10.775 + //typedef typename Graph::Node Node;
10.776 //typedef typename Graph::NodeIt NodeIt;
10.777 - //typedef typename Graph::EachNodeIt EachNodeIt;
10.778
10.779 - //typedef typename Graph::EdgeIt EdgeIt;
10.780 + //typedef typename Graph::Edge Edge;
10.781 //typedef typename Graph::OutEdgeIt OutEdgeIt;
10.782 //typedef typename Graph::InEdgeIt InEdgeIt;
10.783 //typedef typename Graph::SymEdgeIt SymEdgeIt;
10.784 - //typedef typename Graph::EachEdgeIt EachEdgeIt;
10.785 + //typedef typename Graph::EdgeIt EdgeIt;
10.786
10.787 + typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
10.788 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
10.789 - typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
10.790
10.791 - typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
10.792 + typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
10.793 typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
10.794 //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
10.795 //typedef typename Graph::SymEdgeIt SymEdgeIt;
10.796 - //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
10.797 + //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
10.798
10.799 - EachNodeIt& getFirst(EachNodeIt& n) const {
10.800 - return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
10.801 + NodeIt& /*getF*/first(NodeIt& n) const {
10.802 + return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n);
10.803 }
10.804
10.805 - OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
10.806 + OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
10.807 e=first_out_edges.get(n);
10.808 return e;
10.809 }
10.810
10.811 - //ROSSZ template<typename I> I& getFirst(I& i) const { return getFirst(i); }
10.812 - //ROSSZ template<typename I, typename P> I& getFirst(I& i, const P& p) const {
10.813 - // return getFirst(i, p); }
10.814 + //ROSSZ template<typename I> I& /*getF*/first(I& i) const { return /*getF*/first(i); }
10.815 + //ROSSZ template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
10.816 + // return /*getF*/first(i, p); }
10.817
10.818 //template<typename I> I getNext(const I& i) const {
10.819 // return graph->getNext(i); }
10.820 //template<typename I> I& next(I &i) const { return graph->next(i); }
10.821
10.822 template< typename It > It first() const {
10.823 - It e; getFirst(e); return e; }
10.824 + It e; /*getF*/first(e); return e; }
10.825
10.826 - template< typename It > It first(const NodeIt& v) const {
10.827 - It e; getFirst(e, v); return e; }
10.828 + template< typename It > It first(const Node& v) const {
10.829 + It e; /*getF*/first(e, v); return e; }
10.830
10.831 - //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
10.832 - //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
10.833 + //Node head(const Edge& e) const { return graph->head(e); }
10.834 + //Node tail(const Edge& e) const { return graph->tail(e); }
10.835
10.836 //template<typename I> bool valid(const I& i) const
10.837 // { return graph->valid(i); }
10.838 @@ -735,19 +767,19 @@
10.839 //int nodeNum() const { return graph->nodeNum(); }
10.840 //int edgeNum() const { return graph->edgeNum(); }
10.841
10.842 - //template<typename I> NodeIt aNode(const I& e) const {
10.843 + //template<typename I> Node aNode(const I& e) const {
10.844 // return graph->aNode(e); }
10.845 - //template<typename I> NodeIt bNode(const I& e) const {
10.846 + //template<typename I> Node bNode(const I& e) const {
10.847 // return graph->bNode(e); }
10.848
10.849 - //NodeIt addNode() const { return graph->addNode(); }
10.850 - //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
10.851 + //Node addNode() const { return graph->addNode(); }
10.852 + //Edge addEdge(const Node& tail, const Node& head) const {
10.853 // return graph->addEdge(tail, head); }
10.854
10.855 //void erase(const OutEdgeIt& e) {
10.856 // first_out_edge(this->tail(e))=e;
10.857 //}
10.858 - void erase(const EdgeIt& e) {
10.859 + void erase(const Edge& e) {
10.860 OutEdgeIt f(e);
10.861 next(f);
10.862 first_out_edges.set(this->tail(e), f);
10.863 @@ -785,14 +817,14 @@
10.864 public:
10.865 //typedef Graph BaseGraph;
10.866
10.867 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Node Node;
10.868 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
10.869 - typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
10.870
10.871 - typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
10.872 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::Edge Edge;
10.873 typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
10.874 //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
10.875 //typedef typename Graph::SymEdgeIt SymEdgeIt;
10.876 - typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
10.877 + typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
10.878
10.879 //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
10.880
10.881 @@ -802,14 +834,14 @@
10.882 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) {
10.883 }
10.884
10.885 - OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
10.886 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
10.887 + OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
10.888 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n);
10.889 while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))
10.890 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
10.891 return e;
10.892 }
10.893
10.894 - EachNodeIt& next(EachNodeIt& e) const {
10.895 + NodeIt& next(NodeIt& e) const {
10.896 return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
10.897 }
10.898
10.899 @@ -820,11 +852,11 @@
10.900 return e;
10.901 }
10.902
10.903 - EachNodeIt& getFirst(EachNodeIt& n) const {
10.904 - return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
10.905 + NodeIt& /*getF*/first(NodeIt& n) const {
10.906 + return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n);
10.907 }
10.908
10.909 - void erase(const EdgeIt& e) {
10.910 + void erase(const Edge& e) {
10.911 OutEdgeIt f(e);
10.912 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
10.913 while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f))))
10.914 @@ -838,22 +870,22 @@
10.915 //void setGraph(Graph& _graph) { graph = &_graph; }
10.916 //Graph& getGraph() const { return (*graph); }
10.917
10.918 - //template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
10.919 - //template<typename I, typename P> I& getFirst(I& i, const P& p) const {
10.920 - // return graph->getFirst(i, p); }
10.921 + //template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
10.922 + //template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
10.923 + // return graph->/*getF*/first(i, p); }
10.924
10.925 //template<typename I> I getNext(const I& i) const {
10.926 // return graph->getNext(i); }
10.927 //template<typename I> I& next(I &i) const { return graph->next(i); }
10.928
10.929 template< typename It > It first() const {
10.930 - It e; getFirst(e); return e; }
10.931 + It e; /*getF*/first(e); return e; }
10.932
10.933 - template< typename It > It first(const NodeIt& v) const {
10.934 - It e; getFirst(e, v); return e; }
10.935 + template< typename It > It first(const Node& v) const {
10.936 + It e; /*getF*/first(e, v); return e; }
10.937
10.938 - //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
10.939 - //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
10.940 + //Node head(const Edge& e) const { return graph->head(e); }
10.941 + //Node tail(const Edge& e) const { return graph->tail(e); }
10.942
10.943 //template<typename I> bool valid(const I& i) const
10.944 // { return graph->valid(i); }
10.945 @@ -864,13 +896,13 @@
10.946 //int nodeNum() const { return graph->nodeNum(); }
10.947 //int edgeNum() const { return graph->edgeNum(); }
10.948
10.949 - //template<typename I> NodeIt aNode(const I& e) const {
10.950 + //template<typename I> Node aNode(const I& e) const {
10.951 // return graph->aNode(e); }
10.952 - //template<typename I> NodeIt bNode(const I& e) const {
10.953 + //template<typename I> Node bNode(const I& e) const {
10.954 // return graph->bNode(e); }
10.955
10.956 - //NodeIt addNode() const { return graph->addNode(); }
10.957 - //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
10.958 + //Node addNode() const { return graph->addNode(); }
10.959 + //Edge addEdge(const Node& tail, const Node& head) const {
10.960 // return graph->addEdge(tail, head); }
10.961
10.962 //template<typename I> void erase(const I& i) const { graph->erase(i); }
10.963 @@ -909,45 +941,45 @@
10.964 // public:
10.965 // typedef Graph BaseGraph;
10.966
10.967 +// typedef typename Graph::Node Node;
10.968 +// typedef typename Graph::Edge Edge;
10.969 +
10.970 // typedef typename Graph::NodeIt NodeIt;
10.971 -// typedef typename Graph::EdgeIt EdgeIt;
10.972 -
10.973 -// typedef typename Graph::EachNodeIt EachNodeIt;
10.974
10.975 // class OutEdgeIt {
10.976 // public:
10.977 -// //Graph::NodeIt n;
10.978 +// //Graph::Node n;
10.979 // bool out_or_in;
10.980 // typename Graph::OutEdgeIt o;
10.981 // typename Graph::InEdgeIt i;
10.982 // };
10.983 // class InEdgeIt {
10.984 // public:
10.985 -// //Graph::NodeIt n;
10.986 +// //Graph::Node n;
10.987 // bool out_or_in;
10.988 // typename Graph::OutEdgeIt o;
10.989 // typename Graph::InEdgeIt i;
10.990 // };
10.991 // typedef typename Graph::SymEdgeIt SymEdgeIt;
10.992 -// typedef typename Graph::EachEdgeIt EachEdgeIt;
10.993 +// typedef typename Graph::EdgeIt EdgeIt;
10.994
10.995 // int nodeNum() const { return graph->nodeNum(); }
10.996 // int edgeNum() const { return graph->edgeNum(); }
10.997
10.998 -// NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
10.999 +// Node& /*getF*/first(Node& n) const { return graph->/*getF*/first(n); }
10.1000
10.1001 -// // EachEdge and SymEdge is missing!!!!
10.1002 -// // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
10.1003 +// // Edge and SymEdge is missing!!!!
10.1004 +// // Edge <-> In/OutEdgeIt conversion is missing!!!!
10.1005
10.1006 // //FIXME
10.1007 -// OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
10.1008 +// OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const
10.1009 // {
10.1010 // e.n=n;
10.1011 -// graph->getFirst(e.o,n);
10.1012 +// graph->/*getF*/first(e.o,n);
10.1013 // while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
10.1014 // graph->goNext(e.o);
10.1015 // if(!graph->valid(e.o)) {
10.1016 -// graph->getFirst(e.i,n);
10.1017 +// graph->/*getF*/first(e.i,n);
10.1018 // while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
10.1019 // graph->goNext(e.i);
10.1020 // }
10.1021 @@ -960,7 +992,7 @@
10.1022 // while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
10.1023 // graph->goNext(e.o);
10.1024 // if(graph->valid(e.o)) return e;
10.1025 -// else graph->getFirst(e.i,e.n);
10.1026 +// else graph->/*getF*/first(e.i,e.n);
10.1027 // }
10.1028 // else {
10.1029 // while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
10.1030 @@ -973,14 +1005,14 @@
10.1031 // //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
10.1032
10.1033 // //FIXME
10.1034 -// InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
10.1035 +// InEdgeIt& /*getF*/first(InEdgeIt& e, const Node& n) const
10.1036 // {
10.1037 // e.n=n;
10.1038 -// graph->getFirst(e.i,n);
10.1039 +// graph->/*getF*/first(e.i,n);
10.1040 // while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
10.1041 // graph->goNext(e.i);
10.1042 // if(!graph->valid(e.i)) {
10.1043 -// graph->getFirst(e.o,n);
10.1044 +// graph->/*getF*/first(e.o,n);
10.1045 // while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
10.1046 // graph->goNext(e.o);
10.1047 // }
10.1048 @@ -993,7 +1025,7 @@
10.1049 // while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
10.1050 // graph->goNext(e.i);
10.1051 // if(graph->valid(e.i)) return e;
10.1052 -// else graph->getFirst(e.o,e.n);
10.1053 +// else graph->/*getF*/first(e.o,e.n);
10.1054 // }
10.1055 // else {
10.1056 // while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
10.1057 @@ -1009,17 +1041,17 @@
10.1058 // //template<typename I> I next(const I i); { return graph->goNext(i); }
10.1059
10.1060 // template< typename It > It first() const {
10.1061 -// It e; getFirst(e); return e; }
10.1062 +// It e; /*getF*/first(e); return e; }
10.1063
10.1064 -// template< typename It > It first(NodeIt v) const {
10.1065 -// It e; getFirst(e, v); return e; }
10.1066 +// template< typename It > It first(Node v) const {
10.1067 +// It e; /*getF*/first(e, v); return e; }
10.1068
10.1069 -// NodeIt head(const EdgeIt& e) const { return graph->head(e); }
10.1070 -// NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
10.1071 +// Node head(const Edge& e) const { return graph->head(e); }
10.1072 +// Node tail(const Edge& e) const { return graph->tail(e); }
10.1073
10.1074 -// template<typename I> NodeIt aNode(const I& e) const {
10.1075 +// template<typename I> Node aNode(const I& e) const {
10.1076 // return graph->aNode(e); }
10.1077 -// template<typename I> NodeIt bNode(const I& e) const {
10.1078 +// template<typename I> Node bNode(const I& e) const {
10.1079 // return graph->bNode(e); }
10.1080
10.1081 // //template<typename I> bool valid(const I i);
10.1082 @@ -1028,8 +1060,8 @@
10.1083 // //template<typename I> void setInvalid(const I &i);
10.1084 // //{ return graph->setInvalid(i); }
10.1085
10.1086 -// NodeIt addNode() { return graph->addNode(); }
10.1087 -// EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
10.1088 +// Node addNode() { return graph->addNode(); }
10.1089 +// Edge addEdge(const Node& tail, const Node& head) {
10.1090 // return graph->addEdge(tail, head); }
10.1091
10.1092 // template<typename I> void erase(const I& i) { graph->erase(i); }
11.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
11.2 +++ b/src/work/marci/lg_vs_sg.cc Fri Mar 12 09:19:54 2004 +0000
11.3 @@ -0,0 +1,147 @@
11.4 +// -*- c++ -*-
11.5 +#include <iostream>
11.6 +#include <fstream>
11.7 +#include <string>
11.8 +
11.9 +#include <list_graph.h>
11.10 +#include <smart_graph.h>
11.11 +#include <dimacs.h>
11.12 +#include <edmonds_karp.h>
11.13 +#include <time_measure.h>
11.14 +#include <graph_wrapper.h>
11.15 +
11.16 +using namespace hugo;
11.17 +
11.18 +// Use a DIMACS max flow file as stdin.
11.19 +// read_dimacs_demo dimacs_max_flow_file
11.20 +
11.21 +int main(int, char** argv) {
11.22 +
11.23 + std::string in=argv[1];
11.24 + typedef ListGraph MutableGraph;
11.25 +
11.26 + {
11.27 + typedef ListGraph Graph;
11.28 + typedef Graph::Node Node;
11.29 + typedef Graph::EdgeIt EdgeIt;
11.30 +
11.31 + Graph G;
11.32 + Node s, t;
11.33 + Graph::EdgeMap<int> cap(G);
11.34 + std::ifstream ins(in.c_str());
11.35 + readDimacsMaxFlow(ins, G, s, t, cap);
11.36 +
11.37 + {
11.38 + std::cout << "ListGraph..." << std::endl;
11.39 + std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
11.40 + Graph::EdgeMap<int> flow(G); //0 flow
11.41 +
11.42 + Timer ts;
11.43 + ts.reset();
11.44 +
11.45 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
11.46 + int i=0;
11.47 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
11.48 +
11.49 + std::cout << "elapsed time: " << ts << std::endl;
11.50 + std::cout << "number of augmentation phases: " << i << std::endl;
11.51 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
11.52 + }
11.53 +
11.54 + {
11.55 + std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
11.56 + Graph::EdgeMap<int> flow(G); //0 flow
11.57 +
11.58 + Timer ts;
11.59 + ts.reset();
11.60 +
11.61 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
11.62 + int i=0;
11.63 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
11.64 +
11.65 + std::cout << "elapsed time: " << ts << std::endl;
11.66 + std::cout << "number of augmentation phases: " << i << std::endl;
11.67 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
11.68 + }
11.69 +
11.70 + {
11.71 + std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
11.72 + Graph::EdgeMap<int> flow(G); //0 flow
11.73 +
11.74 + Timer ts;
11.75 + ts.reset();
11.76 +
11.77 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
11.78 + int i=0;
11.79 + while (max_flow_test.augmentOnShortestPath()) { ++i; }
11.80 +
11.81 + std::cout << "elapsed time: " << ts << std::endl;
11.82 + std::cout << "number of augmentation phases: " << i << std::endl;
11.83 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
11.84 + }
11.85 + }
11.86 +
11.87 +
11.88 + {
11.89 + typedef SmartGraph Graph;
11.90 + typedef Graph::Node Node;
11.91 + typedef Graph::EdgeIt EdgeIt;
11.92 +
11.93 + Graph G;
11.94 + Node s, t;
11.95 + Graph::EdgeMap<int> cap(G);
11.96 + std::ifstream ins(in.c_str());
11.97 + readDimacsMaxFlow(ins, G, s, t, cap);
11.98 +
11.99 + {
11.100 + std::cout << "SmartGraph..." << std::endl;
11.101 + std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
11.102 + Graph::EdgeMap<int> flow(G); //0 flow
11.103 +
11.104 + Timer ts;
11.105 + ts.reset();
11.106 +
11.107 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
11.108 + int i=0;
11.109 + while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
11.110 +
11.111 + std::cout << "elapsed time: " << ts << std::endl;
11.112 + std::cout << "number of augmentation phases: " << i << std::endl;
11.113 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
11.114 + }
11.115 +
11.116 + {
11.117 + std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
11.118 + Graph::EdgeMap<int> flow(G); //0 flow
11.119 +
11.120 + Timer ts;
11.121 + ts.reset();
11.122 +
11.123 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
11.124 + int i=0;
11.125 + while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
11.126 +
11.127 + std::cout << "elapsed time: " << ts << std::endl;
11.128 + std::cout << "number of augmentation phases: " << i << std::endl;
11.129 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
11.130 + }
11.131 +
11.132 + {
11.133 + std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
11.134 + Graph::EdgeMap<int> flow(G); //0 flow
11.135 +
11.136 + Timer ts;
11.137 + ts.reset();
11.138 +
11.139 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
11.140 + int i=0;
11.141 + while (max_flow_test.augmentOnShortestPath()) { ++i; }
11.142 +
11.143 + std::cout << "elapsed time: " << ts << std::endl;
11.144 + std::cout << "number of augmentation phases: " << i << std::endl;
11.145 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
11.146 + }
11.147 + }
11.148 +
11.149 + return 0;
11.150 +}
12.1 --- a/src/work/marci/makefile Thu Mar 11 23:31:13 2004 +0000
12.2 +++ b/src/work/marci/makefile Fri Mar 12 09:19:54 2004 +0000
12.3 @@ -1,10 +1,10 @@
12.4 CXX3 = g++-3.0
12.5 CXX2 = g++-2.95
12.6 CXX3.3 = g++
12.7 -CXXFLAGS = -W -Wall -ansi -pedantic
12.8 +CXXFLAGS = -W -Wall -ansi -pedantic -I. -I.. -I../alpar
12.9 LEDAROOT ?= /ledasrc/LEDA-4.1
12.10
12.11 -BINARIES = edmonds_karp_demo edmonds_karp_demo_alpar preflow_demo_leda preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos
12.12 +BINARIES = edmonds_karp_demo edmonds_karp_demo_alpar preflow_demo_leda preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos lg_vs_sg
12.13
12.14 all: $(BINARIES)
12.15
12.16 @@ -16,8 +16,11 @@
12.17 sinclude .depend
12.18
12.19 edmonds_karp_demo:
12.20 - $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
12.21 - $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo_prof.cc
12.22 + $(CXX3) $(CXXFLAGS) -g -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
12.23 + $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo.cc
12.24 +
12.25 +lg_vs_sg:
12.26 + $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o lg_vs_sg lg_vs_sg.cc
12.27
12.28 edmonds_karp_demo_alpar:
12.29 $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../alpar -o edmonds_karp_demo_alpar edmonds_karp_demo_alpar.cc