1.1 --- a/src/work/marci/bipartite_graph_wrapper_test.cc Thu Apr 22 20:36:21 2004 +0000
1.2 +++ b/src/work/marci/bipartite_graph_wrapper_test.cc Fri Apr 23 07:41:48 2004 +0000
1.3 @@ -10,6 +10,8 @@
1.4 #include <for_each_macros.h>
1.5 #include <bfs_iterator.h>
1.6 #include <graph_wrapper.h>
1.7 +#include <maps.h>
1.8 +#include <edmonds_karp.h>
1.9
1.10 using namespace hugo;
1.11
1.12 @@ -41,44 +43,35 @@
1.13 FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
1.14 std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
1.15 }
1.16 -// Graph::NodeMap<OutEdgeIt> pred(G);
1.17 -// Timer ts;
1.18 -// {
1.19 -// ts.reset();
1.20 -// Graph::NodeMap<bool> reached(G);
1.21 -// reached.set(s, true);
1.22 -// pred.set(s, INVALID);
1.23 -// std::queue<Node> bfs_queue;
1.24 -// bfs_queue.push(t);
1.25 -// while (!bfs_queue.empty()) {
1.26 -// Node v=bfs_queue.front();
1.27 -// bfs_queue.pop();
1.28 -// OutEdgeIt e;
1.29 -// for(G.first(e,v); G.valid(e); G.next(e)) {
1.30 -// Node w=G.head(e);
1.31 -// if (!reached[w]) {
1.32 -// bfs_queue.push(w);
1.33 -// reached.set(w, true);
1.34 -// pred.set(w, e);
1.35 -// }
1.36 -// }
1.37 -// }
1.38
1.39 -// std::cout << ts << std::endl;
1.40 -// }
1.41 + BGW::NodeMap<int> dbyj(bgw);
1.42 + BGW::EdgeMap<int> dbyxcj(bgw);
1.43
1.44 -// {
1.45 -// ts.reset();
1.46 -// BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
1.47 -// bfs.pushAndSetReached(s);
1.48 -// pred.set(s, INVALID);
1.49 -// while (!bfs.finished()) {
1.50 -// ++bfs;
1.51 -// if (G.valid(bfs) && bfs.isBNodeNewlyReached())
1.52 -// pred.set(bfs.bNode(), bfs);
1.53 -// }
1.54 -// std::cout << ts << std::endl;
1.55 -// }
1.56 + typedef stGraphWrapper<BGW> stGW;
1.57 + stGW stgw(bgw);
1.58 + ConstMap<stGW::Edge, int> const1map(1);
1.59 + stGW::NodeMap<int> ize(stgw);
1.60 + stGW::EdgeMap<int> flow(stgw);
1.61 +
1.62 + BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
1.63 + Graph::NodeIt si;
1.64 + Graph::Node s;
1.65 + s=g.first(si);
1.66 + bfs.pushAndSetReached(BGW::Node(s));
1.67 + while (!bfs.finished()) ++bfs;
1.68 +
1.69 + BGW::EdgeMap<bool> cap(bgw);
1.70 + BGW::EdgeMap<bool> flow1(bgw);
1.71 +
1.72 + typedef ResGraphWrapper< BGW, int, BGW::EdgeMap<bool>, BGW::EdgeMap<bool> >
1.73 + RBGW;
1.74 + RBGW rbgw(bgw, cap, flow1);
1.75 + RBGW::NodeMap<int> u(rbgw);
1.76 +
1.77 +
1.78 + MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> >
1.79 + max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
1.80 + max_flow_test.augmentOnShortestPath();
1.81
1.82 return 0;
1.83 }
2.1 --- a/src/work/marci/graph_wrapper.h Thu Apr 22 20:36:21 2004 +0000
2.2 +++ b/src/work/marci/graph_wrapper.h Fri Apr 23 07:41:48 2004 +0000
2.3 @@ -156,10 +156,10 @@
2.4 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
2.5 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
2.6
2.7 + Node tail(const Edge& e) const {
2.8 + return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
2.9 Node head(const Edge& e) const {
2.10 return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
2.11 - Node tail(const Edge& e) const {
2.12 - return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
2.13
2.14 bool valid(const Node& n) const {
2.15 return graph->valid(static_cast<typename Graph::Node>(n)); }
2.16 @@ -221,10 +221,10 @@
2.17 class OutEdgeIt {
2.18 friend class GraphWrapper<Graph>;
2.19 friend class RevGraphWrapper<Graph>;
2.20 - typename Graph::OutEdgeIt e;
2.21 + typename Graph::InEdgeIt e;
2.22 public:
2.23 OutEdgeIt() { }
2.24 - OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
2.25 + OutEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
2.26 OutEdgeIt(const Invalid& i) : e(i) { }
2.27 OutEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
2.28 e(*(_G.graph), typename Graph::Node(_n)) { }
2.29 @@ -233,10 +233,10 @@
2.30 class InEdgeIt {
2.31 friend class GraphWrapper<Graph>;
2.32 friend class RevGraphWrapper<Graph>;
2.33 - typename Graph::InEdgeIt e;
2.34 + typename Graph::OutEdgeIt e;
2.35 public:
2.36 InEdgeIt() { }
2.37 - InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
2.38 + InEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
2.39 InEdgeIt(const Invalid& i) : e(i) { }
2.40 InEdgeIt(const RevGraphWrapper<Graph>& _G, const Node& _n) :
2.41 e(*(_G.graph), typename Graph::Node(_n)) { }
2.42 @@ -259,6 +259,12 @@
2.43 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
2.44 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
2.45 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
2.46 +
2.47 + Node tail(const Edge& e) const {
2.48 + return GraphWrapper<Graph>::head(e); }
2.49 + Node head(const Edge& e) const {
2.50 + return GraphWrapper<Graph>::tail(e); }
2.51 +
2.52 };
2.53
2.54 /// Wrapper for hiding nodes and edges from a graph.
2.55 @@ -883,6 +889,9 @@
2.56 SFalseTTrueMap* s_false_t_true_map;
2.57
2.58 public:
2.59 + static const bool S_CLASS=false;
2.60 + static const bool T_CLASS=true;
2.61 +
2.62 BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
2.63 : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {
2.64 }
2.65 @@ -890,35 +899,46 @@
2.66 //using GraphWrapper<Graph>::NodeIt;
2.67 typedef typename GraphWrapper<Graph>::Edge Edge;
2.68 //using GraphWrapper<Graph>::EdgeIt;
2.69 - class SNodeIt {
2.70 + class ClassNodeIt {
2.71 Node n;
2.72 public:
2.73 - SNodeIt() { }
2.74 - SNodeIt(const Invalid& i) : n(i) { }
2.75 - SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
2.76 - _G.s_false_t_true_map->first(n, false);
2.77 + ClassNodeIt() { }
2.78 + ClassNodeIt(const Invalid& i) : n(i) { }
2.79 + ClassNodeIt(const BipartiteGraphWrapper<Graph>& _G, bool _class) {
2.80 + _G.s_false_t_true_map->first(n, _class);
2.81 }
2.82 operator Node() const { return n; }
2.83 };
2.84 - class TNodeIt {
2.85 - Node n;
2.86 - public:
2.87 - TNodeIt() { }
2.88 - TNodeIt(const Invalid& i) : n(i) { }
2.89 - TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
2.90 - _G.s_false_t_true_map->first(n, true);
2.91 - }
2.92 - operator Node() const { return n; }
2.93 - };
2.94 +// class SNodeIt {
2.95 +// Node n;
2.96 +// public:
2.97 +// SNodeIt() { }
2.98 +// SNodeIt(const Invalid& i) : n(i) { }
2.99 +// SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
2.100 +// _G.s_false_t_true_map->first(n, false);
2.101 +// }
2.102 +// operator Node() const { return n; }
2.103 +// };
2.104 +// class TNodeIt {
2.105 +// Node n;
2.106 +// public:
2.107 +// TNodeIt() { }
2.108 +// TNodeIt(const Invalid& i) : n(i) { }
2.109 +// TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
2.110 +// _G.s_false_t_true_map->first(n, true);
2.111 +// }
2.112 +// operator Node() const { return n; }
2.113 +// };
2.114 class OutEdgeIt {
2.115 public:
2.116 +
2.117 typename Graph::OutEdgeIt e;
2.118 public:
2.119 OutEdgeIt() { }
2.120 OutEdgeIt(const Invalid& i) : e(i) { }
2.121 OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
2.122 if (!(*(_G.s_false_t_true_map))[_n])
2.123 - e=OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
2.124 + e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
2.125 else
2.126 e=INVALID;
2.127 }
2.128 @@ -932,7 +952,7 @@
2.129 InEdgeIt(const Invalid& i) : e(i) { }
2.130 InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
2.131 if ((*(_G.s_false_t_true_map))[_n])
2.132 - e=InEdgeIt(*(_G.graph), typename Graph::Node(_n));
2.133 + e=typename Graph::InEdgeIt(*(_G.graph), typename Graph::Node(_n));
2.134 else
2.135 e=INVALID;
2.136 }
2.137 @@ -940,16 +960,29 @@
2.138 };
2.139
2.140 using GraphWrapper<Graph>::first;
2.141 - SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
2.142 - TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
2.143 + ClassNodeIt& first(ClassNodeIt& n, bool _class) const {
2.144 + n=SNodeIt(*this, _class) ; return n; }
2.145 +// SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
2.146 +// TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
2.147 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
2.148 + i=OutEdgeIt(*this, p); return i;
2.149 + }
2.150 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
2.151 + i=InEdgeIt(*this, p); return i;
2.152 + }
2.153
2.154 using GraphWrapper<Graph>::next;
2.155 - SNodeIt& next(SNodeIt& n) const {
2.156 + ClassNodeIt& next(ClassNodeIt& n) const {
2.157 this->s_false_t_true_map->next(n); return n;
2.158 }
2.159 - TNodeIt& next(TNodeIt& n) const {
2.160 - this->s_false_t_true_map->next(n); return n;
2.161 - }
2.162 +// SNodeIt& next(SNodeIt& n) const {
2.163 +// this->s_false_t_true_map->next(n); return n;
2.164 +// }
2.165 +// TNodeIt& next(TNodeIt& n) const {
2.166 +// this->s_false_t_true_map->next(n); return n;
2.167 +// }
2.168 + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
2.169 + InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
2.170
2.171 Node tail(const Edge& e) {
2.172 if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
2.173 @@ -976,186 +1009,473 @@
2.174 Node bNode(const InEdgeIt& e) const {
2.175 return Node(this->graph->bNode(e.e));
2.176 }
2.177 +
2.178 + bool inSClass(const Node& n) const {
2.179 + return !(this->s_false_t_true_map[n]);
2.180 + }
2.181 + bool inTClass(const Node& n) const {
2.182 + return (this->s_false_t_true_map[n]);
2.183 + }
2.184 };
2.185
2.186
2.187 + /// experimentral, do not try it.
2.188 + /// It eats a bipartite graph, oriented from S to T.
2.189 + /// Such one can be made e.g. by the above wrapper.
2.190 + template<typename Graph>
2.191 + class stGraphWrapper : public GraphWrapper<Graph> {
2.192 + public:
2.193 + class Node;
2.194 +//GN, int
2.195 +//0 normalis, 1 s, 2, true, ez az iteralasi sorrend,
2.196 +//es a vege a false azaz (invalid, 3)
2.197 + class NodeIt;
2.198 +//GNI, int
2.199 + class Edge;
2.200 +//GE, int, GN
2.201 +//0 normalis, 1 s->vmi, 2 vmi->t, ez a sorrend,
2.202 +//invalid: (invalid, 3, invalid)
2.203 + class OutEdgeIt;
2.204 +//GO, int, GNI
2.205 +//normalis pontbol (first, 0, invalid), ..., (invalid, 2, vmi), ... (invalid, 3, invalid)
2.206 +//s-bol (invalid, 1, first), ... (invalid, 3, invalid)
2.207 +//t-bol (invalid, 3, invalid)
2.208 + class InEdgeIt;
2.209 +//GI, int, GNI
2.210 +//normalis pontbol (first, 0, invalid), ..., (invalid, 1, vmi), ... (invalid, 3, invalid)
2.211 +//s-be (invalid, 3, invalid)
2.212 +//t-be (invalid, 2, first), ... (invalid, 3, invalid)
2.213 + class EdgeIt;
2.214 +//(first, 0, invalid) ...
2.215 +//(invalid, 1, vmi)
2.216 +//(invalid, 2, vmi)
2.217 +//invalid, 3, invalid)
2.218 + template <typename T> class NodeMap;
2.219 + template <typename T> class EdgeMap;
2.220
2.221 -// /// experimentral, do not try it.
2.222 -// template<typename Graph>
2.223 -// class stGraphWrapper : public GraphWrapper<Graph> {
2.224 -// public:
2.225 -// class Node;
2.226 -// class NodeIt;
2.227 -// class Edge;
2.228 -// class OutEdgeIt;
2.229 -// class InEdgeIt;
2.230 -// class EdgeIt;
2.231 +// template <typename T> friend class NodeMap;
2.232 +// template <typename T> friend class EdgeMap;
2.233
2.234 -// const Node s;
2.235 -// const Node t;
2.236 + const Node S_NODE;
2.237 + const Node T_NODE;
2.238
2.239 -// stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph),
2.240 -// s(INVALID, 1), t(INVALID, 2) { }
2.241 + static const bool S_CLASS=false;
2.242 + static const bool T_CLASS=true;
2.243
2.244 -// class Node : public Graph::Node {
2.245 -// friend class GraphWrapper<Graph>;
2.246 -// friend class stGraphWrapper<Graph>;
2.247 -// protected:
2.248 -// int spec; //0 if real node, 1 iff s, 2 iff t
2.249 -// public:
2.250 -// Node() { }
2.251 -// Node(const typename Graph::Node& _n, int _spec=0) :
2.252 -// Graph::Node(_n), spec(_spec) { }
2.253 -// Node(const Invalid& i) : Graph::Node(i), spec(2) { }
2.254 -// //invalid: (invalid, 2);
2.255 -// };
2.256 + stGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) ,
2.257 + S_NODE(INVALID, 1),
2.258 + T_NODE(INVALID, 2) { }
2.259
2.260 -// class NodeIt {
2.261 -// friend class GraphWrapper<Graph>;
2.262 -// friend class stGraphWrapper<Graph>;
2.263 -// typename Graph::NodeIt n;
2.264 -// int spec;
2.265 -// public:
2.266 -// NodeIt() { }
2.267 -// NodeIt(const typename Graph::NodeIt& _n, int _spec=0) :
2.268 -// n(_n), spec(_spec) { }
2.269 -// NodeIt(const Invalid& i) : n(i), spec(2) { }
2.270 -// NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
2.271 -// if (!_G->valid(n)) spec=1;
2.272 -// }
2.273 -// operator Node() const { return Node(n, spec); }
2.274 -// };
2.275 -// // typedef typename Graph::Edge Edge;
2.276 -// class Edge : public Graph::Edge {
2.277 -// friend class GraphWrapper<Graph>;
2.278 -// friend class stGraphWrapper<Graph>;
2.279 -// Node tail_spec;
2.280 -// Node head_spec;
2.281 -// public:
2.282 -// Edge() { }
2.283 -// Edge(const typename Graph::Edge& _e) :
2.284 -// Graph::Edge(_e), tail_spec(i, 0), head_spec(i, 0) {
2.285 -// //a tail-t es a head-et real node-ra csinaljuk
2.286 -// }
2.287 -// Edge(const Invalid& i) : Graph::Edge(i), tail_spec(i), head_spec(i) { }
2.288 -// };
2.289 -// class OutEdgeIt {
2.290 -// friend class GraphWrapper<Graph>;
2.291 -// friend class stGraphWrapper<Graph>;
2.292 -// typename Graph::OutEdgeIt e;
2.293 -// Node tail_spec;
2.294 -// Node head_spec;
2.295 -// public:
2.296 -// OutEdgeIt() { }
2.297 -// OutEdgeIt(const typename Graph::OutEdgeIt& _e) :
2.298 -// e(_e), tail_spec(i, 0), head_spec(i, 0) {
2.299 -// //a tail-t es a head-et real node-ra csinaljuk
2.300 -// }
2.301 -// OutEdgeIt(const Invalid& i) : e(i), tail_spec(i), head_spec(i) { }
2.302 -// //invalid: (barmi, 0, 2)
2.303 -// OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
2.304 -// switch (_n.spec) {
2.305 -// case 0 :
2.306 -// e=typename Graph::OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
2.307 -// _tail.spec=0;
2.308 -// _head.spec=0;
2.309 -// if (!_G.graph->valid(e)) spec=1;
2.310 -// break;
2.311 -// case 1:
2.312 -// e=INVALID;
2.313 -// _tail.spec=1;
2.314 -// _head(_G.graph->first(typename Graph::NodeIt()));
2.315 -// if _head.spec==1
2.316 -// break;
2.317 -// };
2.318 -
2.319 -// }
2.320 -// operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.321 -// };
2.322 -// class InEdgeIt {
2.323 -// friend class GraphWrapper<Graph>;
2.324 -// typename Graph::InEdgeIt e;
2.325 -// public:
2.326 -// InEdgeIt() { }
2.327 -// InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
2.328 -// InEdgeIt(const Invalid& i) : e(i) { }
2.329 -// InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
2.330 -// e(*(_G.graph), typename Graph::Node(_n)) { }
2.331 -// operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.332 -// };
2.333 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
2.334 -// class EdgeIt {
2.335 -// friend class GraphWrapper<Graph>;
2.336 -// typename Graph::EdgeIt e;
2.337 -// public:
2.338 -// EdgeIt() { }
2.339 -// EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
2.340 -// EdgeIt(const Invalid& i) : e(i) { }
2.341 -// EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
2.342 -// operator Edge() const { return Edge(typename Graph::Edge(e)); }
2.343 -// };
2.344 + class Node : public Graph::Node {
2.345 + protected:
2.346 + friend class GraphWrapper<Graph>;
2.347 + friend class stGraphWrapper<Graph>;
2.348 + template <typename T> friend class stGraphWrapper<Graph>::NodeMap;
2.349 + int spec;
2.350 + public:
2.351 + Node() { }
2.352 + Node(const typename Graph::Node& _n, int _spec=0) :
2.353 + Graph::Node(_n), spec(_spec) { }
2.354 + Node(const Invalid& i) : Graph::Node(i), spec(3) { }
2.355 + friend bool operator==(const Node& u, const Node& v) {
2.356 + return (u.spec==v.spec &&
2.357 + static_cast<typename Graph::Node>(u)==
2.358 + static_cast<typename Graph::Node>(v));
2.359 + }
2.360 + friend bool operator!=(const Node& u, const Node& v) {
2.361 + return (v.spec!=u.spec ||
2.362 + static_cast<typename Graph::Node>(u)!=
2.363 + static_cast<typename Graph::Node>(v));
2.364 + }
2.365 + int getSpec() const { return spec; }
2.366 + };
2.367 + class NodeIt {
2.368 + friend class GraphWrapper<Graph>;
2.369 + friend class stGraphWrapper<Graph>;
2.370 + typename Graph::NodeIt n;
2.371 + int spec;
2.372 + public:
2.373 + NodeIt() { }
2.374 + NodeIt(const typename Graph::NodeIt& _n, int _spec) :
2.375 + n(_n), spec(_spec) { }
2.376 + NodeIt(const Invalid& i) : n(i), spec(3) { }
2.377 + NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) {
2.378 + if (!_G->valid(n)) spec=1;
2.379 + }
2.380 + operator Node() const { return Node(n, spec); }
2.381 + };
2.382 + class Edge : public Graph::Edge {
2.383 + friend class GraphWrapper<Graph>;
2.384 + friend class stGraphWrapper<Graph>;
2.385 + template <typename T> friend class stGraphWrapper<Graph>::EdgeMap;
2.386 + int spec;
2.387 + typename Graph::Node n;
2.388 + public:
2.389 + Edge() { }
2.390 + Edge(const typename Graph::Edge& _e, int _spec,
2.391 + const typename Graph::Node& _n) :
2.392 + Graph::Edge(_e), spec(_spec), n(_n) {
2.393 + }
2.394 + Edge(const Invalid& i) : Graph::Edge(i), spec(3), n(i) { }
2.395 + friend bool operator==(const Edge& u, const Edge& v) {
2.396 + return (u.spec==v.spec &&
2.397 + static_cast<typename Graph::Edge>(u)==
2.398 + static_cast<typename Graph::Edge>(v) &&
2.399 + u.n==v.n);
2.400 + }
2.401 + friend bool operator!=(const Edge& u, const Edge& v) {
2.402 + return (v.spec!=u.spec ||
2.403 + static_cast<typename Graph::Edge>(u)!=
2.404 + static_cast<typename Graph::Edge>(v) ||
2.405 + u.n!=v.n);
2.406 + }
2.407 + int getSpec() const { return spec; }
2.408 + };
2.409 + class OutEdgeIt {
2.410 + friend class GraphWrapper<Graph>;
2.411 + friend class stGraphWrapper<Graph>;
2.412 + typename Graph::OutEdgeIt e;
2.413 + int spec;
2.414 + typename Graph::ClassNodeIt n;
2.415 + public:
2.416 + OutEdgeIt() { }
2.417 + OutEdgeIt(const typename Graph::OutEdgeIt& _e, int _spec,
2.418 + const typename Graph::ClassNodeIt& _n) :
2.419 + e(_e), spec(_spec), n(_n) {
2.420 + }
2.421 + OutEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
2.422 + OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
2.423 + switch (_n.spec) {
2.424 + case 0 :
2.425 + if (_G.graph->inSClass) { //S, van normalis kiel
2.426 + e=typename Graph::OutEdgeIt(*(_G.graph),
2.427 + typename Graph::Node(_n));
2.428 + spec=0;
2.429 + n=INVALID;
2.430 + if (!_G.graph->valid(e)) spec=3;
2.431 + } else { //T, specko kiel van
2.432 + e=INVALID;
2.433 + spec=2;
2.434 + n=_n;
2.435 + }
2.436 + break;
2.437 + case 1:
2.438 + e=INVALID;
2.439 + spec=1;
2.440 + _G.graph->first(n, S_CLASS); //s->vmi;
2.441 + if (!_G.graph->valid(n)) spec=3; //Ha S ures
2.442 + break;
2.443 + case 2:
2.444 + e=INVALID;
2.445 + spec=3;
2.446 + n=INVALID;
2.447 + break;
2.448 + }
2.449 + }
2.450 + operator Edge() const { return Edge(e, spec, n); }
2.451 + };
2.452 + class InEdgeIt {
2.453 + friend class GraphWrapper<Graph>;
2.454 + friend class stGraphWrapper<Graph>;
2.455 + typename Graph::InEdgeIt e;
2.456 + int spec;
2.457 + typename Graph::ClassNodeIt n;
2.458 + public:
2.459 + InEdgeIt() { }
2.460 + InEdgeIt(const typename Graph::InEdgeIt& _e, int _spec,
2.461 + const typename Graph::ClassNodeIt& _n) :
2.462 + e(_e), spec(_spec), n(_n) {
2.463 + }
2.464 + InEdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
2.465 + InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) {
2.466 + switch (_n.spec) {
2.467 + case 0 :
2.468 + if (_G.graph->inTClass) { //T, van normalis beel
2.469 + e=typename Graph::InEdgeIt(*(_G.graph),
2.470 + typename Graph::Node(_n));
2.471 + spec=0;
2.472 + n=INVALID;
2.473 + if (!_G.graph->valid(e)) spec=3;
2.474 + } else { //S, specko beel van
2.475 + e=INVALID;
2.476 + spec=1;
2.477 + n=_n;
2.478 + }
2.479 + break;
2.480 + case 1:
2.481 + e=INVALID;
2.482 + spec=3;
2.483 + n=INVALID;
2.484 + case 2:
2.485 + e=INVALID;
2.486 + spec=1;
2.487 + _G.graph->first(n, T_CLASS); //vmi->t;
2.488 + if (!_G.graph->valid(n)) spec=3; //Ha T ures
2.489 + break;
2.490 + }
2.491 + }
2.492 + operator Edge() const { return Edge(e, spec, n); }
2.493 + };
2.494 + class EdgeIt {
2.495 + friend class GraphWrapper<Graph>;
2.496 + friend class stGraphWrapper<Graph>;
2.497 + typename Graph::EdgeIt e;
2.498 + int spec;
2.499 + typename Graph::ClassNodeIt n;
2.500 + public:
2.501 + EdgeIt() { }
2.502 + EdgeIt(const typename Graph::EdgeIt& _e, int _spec,
2.503 + const typename Graph::ClassNodeIt& _n) :
2.504 + e(_e), spec(_spec), n(_n) { }
2.505 + EdgeIt(const Invalid& i) : e(i), spec(3), n(i) { }
2.506 + EdgeIt(const GraphWrapper<Graph>& _G) :
2.507 + e(*(_G.graph)), spec(0), n(INVALID) {
2.508 + if (!_G.graph->valid(e)) {
2.509 + spec=1;
2.510 + _G.graph->first(n, S_CLASS);
2.511 + if (!_G.graph->valid(n)) { //Ha S ures
2.512 + spec=2;
2.513 + _G.graph->first(n, T_CLASS);
2.514 + if (!_G.graph->valid(n)) { //Ha T ures
2.515 + spec=3;
2.516 + }
2.517 + }
2.518 + }
2.519 + }
2.520 + operator Edge() const { return Edge(e, spec, n); }
2.521 + };
2.522
2.523 -// NodeIt& first(NodeIt& i) const {
2.524 -// i=NodeIt(*this); return i;
2.525 -// }
2.526 -// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
2.527 -// i=OutEdgeIt(*this, p); return i;
2.528 -// }
2.529 -// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
2.530 -// i=InEdgeIt(*this, p); return i;
2.531 -// }
2.532 -// EdgeIt& first(EdgeIt& i) const {
2.533 -// i=EdgeIt(*this); return i;
2.534 -// }
2.535 + NodeIt& first(NodeIt& i) const {
2.536 + i=NodeIt(*this); return i;
2.537 + }
2.538 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
2.539 + i=OutEdgeIt(*this, p); return i;
2.540 + }
2.541 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
2.542 + i=InEdgeIt(*this, p); return i;
2.543 + }
2.544 + EdgeIt& first(EdgeIt& i) const {
2.545 + i=EdgeIt(*this); return i;
2.546 + }
2.547
2.548 -// NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
2.549 -// OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
2.550 -// InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
2.551 -// EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
2.552 + NodeIt& next(NodeIt& i) const {
2.553 + switch (i.spec) {
2.554 + case 0:
2.555 + graph->next(i.n);
2.556 + if (!graph->valid(i.n)) {
2.557 + i.spec=1;
2.558 + }
2.559 + break;
2.560 + case 1:
2.561 + i.spec=2;
2.562 + break;
2.563 + case 2:
2.564 + i.spec=3;
2.565 + break;
2.566 + }
2.567 + return i;
2.568 + }
2.569 + OutEdgeIt& next(OutEdgeIt& i) const {
2.570 + switch (i.spec) {
2.571 + case 0: //normal edge
2.572 + typename Graph::Node v=graph->aNode(i.e);
2.573 + graph->next(i.e);
2.574 + if (!graph->valid(i.e)) { //Az igazi elek vegere ertunk
2.575 + if (graph->inSClass(v)) { //S, nincs kiel
2.576 + i.spec=3;
2.577 + i.n=INVALID;
2.578 + } else { //T, van kiel
2.579 + i.spec=2;
2.580 + i.n=v;
2.581 + }
2.582 + }
2.583 + break;
2.584 + case 1: //s->vmi
2.585 + graph->next(i.n);
2.586 + if (!graph->valid(i.n)) i.spec=3;
2.587 + break;
2.588 + case 2: //vmi->t
2.589 + i.spec=3;
2.590 + i.n=INVALID;
2.591 + break;
2.592 + }
2.593 + return i;
2.594 + }
2.595 + InEdgeIt& next(InEdgeIt& i) const {
2.596 + switch (i.spec) {
2.597 + case 0: //normal edge
2.598 + typename Graph::Node v=graph->aNode(i.e);
2.599 + graph->next(i.e);
2.600 + if (!graph->valid(i.e)) { //Az igazi elek vegere ertunk
2.601 + if (graph->inTClass(v)) { //S, nincs beel
2.602 + i.spec=3;
2.603 + i.n=INVALID;
2.604 + } else { //S, van beel
2.605 + i.spec=1;
2.606 + i.n=v;
2.607 + }
2.608 + }
2.609 + break;
2.610 + case 1: //s->vmi
2.611 + i.spec=3;
2.612 + i.n=INVALID;
2.613 + break;
2.614 + case 2: //vmi->t
2.615 + graph->next(i.n);
2.616 + if (!graph->valid(i.n)) i.spec=3;
2.617 + break;
2.618 + }
2.619 + return i;
2.620 + }
2.621
2.622 -// Node head(const Edge& e) const {
2.623 -// return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
2.624 -// Node tail(const Edge& e) const {
2.625 -// return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
2.626 + EdgeIt& next(EdgeIt& i) const {
2.627 + switch (i.spec) {
2.628 + case 0:
2.629 + graph->next(i.e);
2.630 + if (!graph->valid(i.e)) {
2.631 + i.spec=1;
2.632 + graph->first(n, S_CLASS);
2.633 + if (!graph->valid(i.n)) {
2.634 + i.spec=2;
2.635 + graph->first(n, T_CLASS);
2.636 + if (!graph->valid(i.n)) spec=3;
2.637 + }
2.638 + }
2.639 + break;
2.640 + case 1:
2.641 + graph->next(i.n);
2.642 + if (!graph->valid(i.n)) {
2.643 + i.spec=2;
2.644 + graph->first(n, T_CLASS);
2.645 + if (!graph->valid(i.n)) spec=3;
2.646 + }
2.647 + break;
2.648 + case 2:
2.649 + graph->next(i.n);
2.650 + if (!graph->valid(i.n)) i.spec=3;
2.651 + break;
2.652 + }
2.653 + return i;
2.654 + }
2.655
2.656 -// bool valid(const Node& n) const {
2.657 -// return graph->valid(static_cast<typename Graph::Node>(n)); }
2.658 -// bool valid(const Edge& e) const {
2.659 -// return graph->valid(static_cast<typename Graph::Edge>(e)); }
2.660 + Node tail(const Edge& e) const {
2.661 + switch (e.spec) {
2.662 + case 0:
2.663 + return Node(graph->tail(e));
2.664 + break;
2.665 + case 1:
2.666 + return S_NODE;
2.667 + break;
2.668 + case 2:
2.669 + return Node(e.n);
2.670 + break;
2.671 + }
2.672 + }
2.673 + Node head(const Edge& e) const {
2.674 + switch (e.spec) {
2.675 + case 0:
2.676 + return Node(graph->head(e));
2.677 + break;
2.678 + case 1:
2.679 + return Node(e.n);
2.680 + break;
2.681 + case 2:
2.682 + return T_NODE;
2.683 + break;
2.684 + }
2.685 + }
2.686
2.687 -// int nodeNum() const { return graph->nodeNum(); }
2.688 -// int edgeNum() const { return graph->edgeNum(); }
2.689 + bool valid(const Node& n) const { return (n.spec<3); }
2.690 + bool valid(const Edge& e) const { return (e.spec<3); }
2.691 +
2.692 +// int nodeNum() const { return graph->nodeNum(); }
2.693 +// int edgeNum() const { return graph->edgeNum(); }
2.694
2.695 -// Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
2.696 -// Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
2.697 -// Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
2.698 -// Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
2.699 + Node aNode(const OutEdgeIt& e) const { return tail(e); }
2.700 + Node aNode(const InEdgeIt& e) const { return head(e); }
2.701 + Node bNode(const OutEdgeIt& e) const { return head(e); }
2.702 + Node bNode(const InEdgeIt& e) const { return tail(e); }
2.703
2.704 -// Node addNode() const { return Node(graph->addNode()); }
2.705 -// Edge addEdge(const Node& tail, const Node& head) const {
2.706 -// return Edge(graph->addEdge(tail, head)); }
2.707 +// Node addNode() const { return Node(graph->addNode()); }
2.708 +// Edge addEdge(const Node& tail, const Node& head) const {
2.709 +// return Edge(graph->addEdge(tail, head)); }
2.710
2.711 -// void erase(const Node& i) const { graph->erase(i); }
2.712 -// void erase(const Edge& i) const { graph->erase(i); }
2.713 +// void erase(const Node& i) const { graph->erase(i); }
2.714 +// void erase(const Edge& i) const { graph->erase(i); }
2.715
2.716 -// void clear() const { graph->clear(); }
2.717 +// void clear() const { graph->clear(); }
2.718
2.719 -// template<typename T> class NodeMap : public Graph::NodeMap<T> {
2.720 -// public:
2.721 -// NodeMap(const GraphWrapper<Graph>& _G) :
2.722 -// Graph::NodeMap<T>(*(_G.graph)) { }
2.723 -// NodeMap(const GraphWrapper<Graph>& _G, T a) :
2.724 -// Graph::NodeMap<T>(*(_G.graph), a) { }
2.725 -// };
2.726 + template<typename T> class NodeMap : public GraphWrapper<Graph>::NodeMap<T> {
2.727 + T s_value, t_value;
2.728 + public:
2.729 + NodeMap(const stGraphWrapper<Graph>& _G) :
2.730 + GraphWrapper<Graph>::NodeMap<T>(_G) { }
2.731 + NodeMap(const stGraphWrapper<Graph>& _G, T a) :
2.732 + GraphWrapper<Graph>::NodeMap<T>(_G, a), s_value(a), t_value(a) { }
2.733 + T operator[](const Node& n) const {
2.734 + switch (n.spec) {
2.735 + case 0:
2.736 + return (*this)[n];
2.737 + break;
2.738 + case 1:
2.739 + return s_value;
2.740 + break;
2.741 + case 2:
2.742 + return t_value;
2.743 + break;
2.744 + }
2.745 + }
2.746 + void set(const Node& n, T t) {
2.747 + switch (n.spec) {
2.748 + case 0:
2.749 + GraphWrapper<Graph>::NodeMap<T>::set(n, t);
2.750 + break;
2.751 + case 1:
2.752 + s_value=t;
2.753 + break;
2.754 + case 2:
2.755 + t_value=t;
2.756 + break;
2.757 + }
2.758 + }
2.759 + };
2.760
2.761 -// template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
2.762 -// public:
2.763 -// EdgeMap(const GraphWrapper<Graph>& _G) :
2.764 -// Graph::EdgeMap<T>(*(_G.graph)) { }
2.765 -// EdgeMap(const GraphWrapper<Graph>& _G, T a) :
2.766 -// Graph::EdgeMap<T>(*(_G.graph), a) { }
2.767 -// };
2.768 -// };
2.769 + template<typename T> class EdgeMap : public GraphWrapper<Graph>::EdgeMap<T> {
2.770 + typename GraphWrapper<Graph>::NodeMap<T> node_value;
2.771 + public:
2.772 + EdgeMap(const stGraphWrapper<Graph>& _G) :
2.773 + GraphWrapper<Graph>::EdgeMap<T>(_G), node_value(_G) { }
2.774 + EdgeMap(const stGraphWrapper<Graph>& _G, T a) :
2.775 + GraphWrapper<Graph>::EdgeMap<T>(_G, a), node_value(_G, a) { }
2.776 + T operator[](const Edge& e) const {
2.777 + switch (e.spec) {
2.778 + case 0:
2.779 + return (*this)[e];
2.780 + break;
2.781 + case 1:
2.782 + return node_value[e.n];
2.783 + break;
2.784 + case 2:
2.785 + return node_value[e.n];
2.786 + break;
2.787 + }
2.788 + }
2.789 + void set(const Edge& e, T t) {
2.790 + switch (e.spec) {
2.791 + case 0:
2.792 + GraphWrapper<Graph>::set(e, t);
2.793 + break;
2.794 + case 1:
2.795 + node_value.set(e, t);
2.796 + break;
2.797 + case 2:
2.798 + node_value.set(e, t);
2.799 + break;
2.800 + }
2.801 + }
2.802 + };
2.803 + };
2.804 +
2.805
2.806 } //namespace hugo
2.807
3.1 --- a/src/work/marci/lg_vs_sg.cc Thu Apr 22 20:36:21 2004 +0000
3.2 +++ b/src/work/marci/lg_vs_sg.cc Fri Apr 23 07:41:48 2004 +0000
3.3 @@ -35,7 +35,7 @@
3.4 Timer ts;
3.5 Graph::EdgeMap<int> flow(G); //0 flow
3.6 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.7 - pre_flow_test(G, s, t, cap, flow);
3.8 + pre_flow_test(G, s, t, cap, flow, true);
3.9 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.10 max_flow_test(G, s, t, cap, flow);
3.11
3.12 @@ -109,7 +109,7 @@
3.13 Timer ts;
3.14 Graph::EdgeMap<int> flow(G); //0 flow
3.15 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.16 - pre_flow_test(G, s, t, cap, flow);
3.17 + pre_flow_test(G, s, t, cap, flow, true);
3.18 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.19 max_flow_test(G, s, t, cap, flow);
3.20