1.1 --- a/src/work/marci/lp/max_flow_by_lp.cc Mon Nov 29 16:11:51 2004 +0000
1.2 +++ b/src/work/marci/lp/max_flow_by_lp.cc Mon Nov 29 17:55:46 2004 +0000
1.3 @@ -21,7 +21,7 @@
1.4 int main(int, char **) {
1.5
1.6 typedef ListGraph MutableGraph;
1.7 - typedef SmartGraph Graph;
1.8 + typedef ListGraph Graph;
1.9 typedef Graph::Node Node;
1.10 typedef Graph::Edge Edge;
1.11 typedef Graph::EdgeIt EdgeIt;
1.12 @@ -178,6 +178,7 @@
1.13
1.14 MinCostGenFlow<Graph, int, Excess, LCap>
1.15 min_cost(g, excess, lcap, cap, flow, cost);
1.16 + min_cost.feasible();
1.17 min_cost.run();
1.18
1.19 std::cout << "elapsed time: " << ts << std::endl;
2.1 --- a/src/work/marci/lp/min_cost_gen_flow.h Mon Nov 29 16:11:51 2004 +0000
2.2 +++ b/src/work/marci/lp/min_cost_gen_flow.h Mon Nov 29 17:55:46 2004 +0000
2.3 @@ -1,17 +1,18 @@
2.4 // -*- c++ -*-
2.5 #ifndef LEMON_MIN_COST_GEN_FLOW_H
2.6 #define LEMON_MIN_COST_GEN_FLOW_H
2.7 -//#include <iostream>
2.8 +#include <iostream>
2.9 //#include <fstream>
2.10
2.11 -//#include <lemon/smart_graph.h>
2.12 -//#include <lemon/list_graph.h>
2.13 +#include <lemon/smart_graph.h>
2.14 +#include <lemon/list_graph.h>
2.15 //#include <lemon/dimacs.h>
2.16 //#include <lemon/time_measure.h>
2.17 //#include <graph_wrapper.h>
2.18 -//#include <lemon/preflow.h>
2.19 +#include <lemon/preflow.h>
2.20 //#include <augmenting_flow.h>
2.21 //#include <preflow_res.h>
2.22 +#include <../merge_node_graph_wrapper.h>
2.23 #include <lemon/../work/marci/lp/lp_solver_wrapper.h>
2.24
2.25 namespace lemon {
2.26 @@ -51,6 +52,71 @@
2.27 const CostMap& _cost) :
2.28 g(_g), excess(_excess), lcapacity(_lcapacity),
2.29 capacity(_capacity), flow(_flow), cost(_cost) { }
2.30 + bool feasible() {
2.31 + // std::cout << "making new vertices..." << std::endl;
2.32 + typedef ListGraph Graph2;
2.33 + Graph2 g2;
2.34 + typedef MergeEdgeGraphWrapper<const Graph, Graph2> GW;
2.35 + // std::cout << "merging..." << std::endl;
2.36 + GW gw(g, g2);
2.37 + typename GW::Node s(INVALID, g2.addNode(), true);
2.38 + typename GW::Node t(INVALID, g2.addNode(), true);
2.39 + typedef SmartGraph Graph3;
2.40 + // std::cout << "making extender graph..." << std::endl;
2.41 + typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW;
2.42 +// {
2.43 +// checkConcept<StaticGraph, GWW>();
2.44 +// }
2.45 + GWW gww(gw);
2.46 + typedef AugmentingGraphWrapper<GW, GWW> GWWW;
2.47 + GWWW gwww(gw, gww);
2.48 +
2.49 + // std::cout << "making new edges..." << std::endl;
2.50 + typename GWWW::template EdgeMap<Num> translated_cap(gwww);
2.51 +
2.52 + for (typename GW::EdgeIt e(gw); e!=INVALID; ++e)
2.53 + translated_cap.set(typename GWWW::Edge(e,INVALID,false),
2.54 + capacity[e]-lcapacity[e]);
2.55 +
2.56 + Num expected=0;
2.57 +
2.58 + // std::cout << "making new edges 2..." << std::endl;
2.59 + for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
2.60 + Num a=0;
2.61 + for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
2.62 + a+=lcapacity[e];
2.63 + for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
2.64 + a-=lcapacity[e];
2.65 + if (excess[n]>a) {
2.66 + typename GWW::Edge e=
2.67 + gww.addEdge(typename GW::Node(n,INVALID,false), t);
2.68 + translated_cap.set(typename GWWW::Edge(INVALID, e, true),
2.69 + excess[n]-a);
2.70 + }
2.71 + if (excess[n]<a) {
2.72 + typename GWW::Edge e=
2.73 + gww.addEdge(s, typename GW::Node(n,INVALID,false));
2.74 + translated_cap.set(typename GWWW::Edge(INVALID, e, true),
2.75 + a-excess[n]);
2.76 + expected+=a-excess[n];
2.77 + }
2.78 + }
2.79 +
2.80 + // std::cout << "preflow..." << std::endl;
2.81 + typename GWWW::template EdgeMap<Num> translated_flow(gwww, 0);
2.82 + Preflow<GWWW, Num> preflow(gwww, s, t,
2.83 + translated_cap, translated_flow);
2.84 + preflow.run();
2.85 + // std::cout << "fv: " << preflow.flowValue() << std::endl;
2.86 + // std::cout << "expected: " << expected << std::endl;
2.87 +
2.88 + for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
2.89 + typename GW::Edge ew(e, INVALID, false);
2.90 + typename GWWW::Edge ewww(ew, INVALID, false);
2.91 + flow.set(e, translated_flow[ewww]+lcapacity[e]);
2.92 + }
2.93 + return (expected>=preflow.flowValue());
2.94 + }
2.95 void run() {
2.96 LPSolverWrapper lp;
2.97 lp.setMinimize();
3.1 --- a/src/work/marci/merge_node_graph_wrapper.h Mon Nov 29 16:11:51 2004 +0000
3.2 +++ b/src/work/marci/merge_node_graph_wrapper.h Mon Nov 29 17:55:46 2004 +0000
3.3 @@ -40,13 +40,8 @@
3.4 };
3.5
3.6
3.7 - /*! A graph wrapper base class
3.8 - for merging the node-set of two node-disjoint graphs
3.9 - into the node-set of one graph.
3.10 - Generic implementation for unrelated _Graph1::Node and _Graph2::Node.
3.11 - */
3.12 template <typename _Graph1, typename _Graph2, typename Enable=void>
3.13 - class MergeNodeGraphWrapperBase :
3.14 + class MergeNodeGraphWrapperBaseBase :
3.15 public P1<_Graph1>, public P2<_Graph2> {
3.16 public:
3.17 static void printNode() { std::cout << "node: generic" << std::endl; }
3.18 @@ -57,13 +52,11 @@
3.19 typedef typename Parent1::Node Graph1Node;
3.20 typedef typename Parent2::Node Graph2Node;
3.21 protected:
3.22 - MergeNodeGraphWrapperBase() { }
3.23 + MergeNodeGraphWrapperBaseBase() { }
3.24 public:
3.25 - template <typename _Value> class NodeMap;
3.26
3.27 class Node : public Graph1Node, public Graph2Node {
3.28 - friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
3.29 - template <typename _Value> friend class NodeMap;
3.30 + friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
3.31 protected:
3.32 bool backward; //true, iff backward
3.33 public:
3.34 @@ -88,79 +81,15 @@
3.35 }
3.36 };
3.37
3.38 - //typedef void Edge;
3.39 - class Edge { };
3.40 -
3.41 - void first(Node& i) const {
3.42 - Parent1::graph->first(*static_cast<Graph1Node*>(&i));
3.43 - i.backward=false;
3.44 - if (*static_cast<Graph1Node*>(&i)==INVALID) {
3.45 - Parent2::graph->first(*static_cast<Graph2Node*>(&i));
3.46 - i.backward=true;
3.47 - }
3.48 - }
3.49 - void next(Node& i) const {
3.50 - if (!(i.backward)) {
3.51 - Parent1::graph->next(*static_cast<Graph1Node*>(&i));
3.52 - if (*static_cast<Graph1Node*>(&i)==INVALID) {
3.53 - Parent2::graph->first(*static_cast<Graph2Node*>(&i));
3.54 - i.backward=true;
3.55 - }
3.56 - } else {
3.57 - Parent2::graph->next(*static_cast<Graph2Node*>(&i));
3.58 - }
3.59 - }
3.60 -
3.61 - int id(const Node& n) const {
3.62 - if (!n.backward)
3.63 - return this->Parent1::graph->id(n);
3.64 - else
3.65 - return this->Parent2::graph->id(n);
3.66 - }
3.67 -
3.68 - template <typename _Value>
3.69 - class NodeMap {
3.70 - protected:
3.71 - typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
3.72 - typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
3.73 - ParentMap1 forward_map;
3.74 - ParentMap2 backward_map;
3.75 - public:
3.76 - typedef _Value Value;
3.77 - typedef Node Key;
3.78 - NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
3.79 - forward_map(*(gw.Parent1::graph)),
3.80 - backward_map(*(gw.Parent2::graph)) { }
3.81 - NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
3.82 - const _Value& value) :
3.83 - forward_map(*(gw.Parent1::graph), value),
3.84 - backward_map(*(gw.Parent2::graph), value) { }
3.85 - _Value operator[](const Node& n) const {
3.86 - if (!n.backward)
3.87 - return forward_map[n];
3.88 - else
3.89 - return backward_map[n];
3.90 - }
3.91 - void set(const Node& n, const _Value& value) {
3.92 - if (!n.backward)
3.93 - forward_map.set(n, value);
3.94 - else
3.95 - backward_map.set(n, value);
3.96 - }
3.97 -// using ParentMap1::operator[];
3.98 -// using ParentMap2::operator[];
3.99 - };
3.100 -
3.101 + static bool forward(const Node& n) { return !n.backward; }
3.102 + static bool backward(const Node& n) { return n.backward; }
3.103 + static void setForward(Node& n) { n.backward=false; }
3.104 + static void setBackward(Node& n) { n.backward=true; }
3.105 };
3.106
3.107
3.108 - /*! A graph wrapper base class
3.109 - for merging the node-set of two node-disjoint graphs
3.110 - into the node-set of one graph.
3.111 - Specialization for the case when _Graph1::Node are the same _Graph2::Node.
3.112 - */
3.113 template <typename _Graph1, typename _Graph2>
3.114 - class MergeNodeGraphWrapperBase<
3.115 + class MergeNodeGraphWrapperBaseBase<
3.116 _Graph1, _Graph2, typename boost::enable_if<
3.117 boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
3.118 public P1<_Graph1>, public P2<_Graph2> {
3.119 @@ -173,13 +102,11 @@
3.120 typedef typename Parent1::Node Graph1Node;
3.121 typedef typename Parent2::Node Graph2Node;
3.122 protected:
3.123 - MergeNodeGraphWrapperBase() { }
3.124 + MergeNodeGraphWrapperBaseBase() { }
3.125 public:
3.126 - template <typename _Value> class NodeMap;
3.127
3.128 class Node : public Graph1Node {
3.129 - friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
3.130 - template <typename _Value> friend class NodeMap;
3.131 + friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
3.132 protected:
3.133 bool backward; //true, iff backward
3.134 public:
3.135 @@ -189,7 +116,7 @@
3.136 /// original one, otherwise its oppositely directed pair is obtained.
3.137 Node(const Graph1Node& n1,
3.138 const Graph2Node& n2, bool _backward) :
3.139 - Graph1Node(!backward ? n1 : n2), backward(_backward) { }
3.140 + Graph1Node(!_backward ? n1 : n2), backward(_backward) { }
3.141 Node(Invalid i) : Graph1Node(i), backward(true) { }
3.142 bool operator==(const Node& v) const {
3.143 return (backward==v.backward &&
3.144 @@ -200,80 +127,15 @@
3.145 }
3.146 };
3.147
3.148 - //typedef void Edge;
3.149 - class Edge { };
3.150 -
3.151 - void first(Node& i) const {
3.152 - Parent1::graph->first(*static_cast<Graph1Node*>(&i));
3.153 - i.backward=false;
3.154 - if (*static_cast<Graph1Node*>(&i)==INVALID) {
3.155 - Parent2::graph->first(*static_cast<Graph1Node*>(&i));
3.156 - i.backward=true;
3.157 - }
3.158 - }
3.159 - void next(Node& i) const {
3.160 - if (!(i.backward)) {
3.161 - Parent1::graph->next(*static_cast<Graph1Node*>(&i));
3.162 - if (*static_cast<Graph1Node*>(&i)==INVALID) {
3.163 - Parent2::graph->first(*static_cast<Graph1Node*>(&i));
3.164 - i.backward=true;
3.165 - }
3.166 - } else {
3.167 - Parent2::graph->next(*static_cast<Graph1Node*>(&i));
3.168 - }
3.169 - }
3.170 -
3.171 - int id(const Node& n) const {
3.172 - if (!n.backward)
3.173 - return this->Parent1::graph->id(n);
3.174 - else
3.175 - return this->Parent2::graph->id(n);
3.176 - }
3.177 -
3.178 - template <typename _Value>
3.179 - class NodeMap {
3.180 - protected:
3.181 - typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
3.182 - typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
3.183 - ParentMap1 forward_map;
3.184 - ParentMap2 backward_map;
3.185 - public:
3.186 - typedef _Value Value;
3.187 - typedef Node Key;
3.188 - NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
3.189 - forward_map(*(gw.Parent1::graph)),
3.190 - backward_map(*(gw.Parent2::graph)) { }
3.191 - NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
3.192 - const _Value& value) :
3.193 - forward_map(*(gw.Parent1::graph), value),
3.194 - backward_map(*(gw.Parent2::graph), value) { }
3.195 - _Value operator[](const Node& n) const {
3.196 - if (!n.backward)
3.197 - return forward_map[n];
3.198 - else
3.199 - return backward_map[n];
3.200 - }
3.201 - void set(const Node& n, const _Value& value) {
3.202 - if (!n.backward)
3.203 - forward_map.set(n, value);
3.204 - else
3.205 - backward_map.set(n, value);
3.206 - }
3.207 -// using ParentMap1::operator[];
3.208 -// using ParentMap2::operator[];
3.209 - };
3.210 -
3.211 + static bool forward(const Node& n) { return !n.backward; }
3.212 + static bool backward(const Node& n) { return n.backward; }
3.213 + static void setForward(Node& n) { n.backward=false; }
3.214 + static void setBackward(Node& n) { n.backward=true; }
3.215 };
3.216
3.217
3.218 - /*! A graph wrapper base class
3.219 - for merging the node-set of two node-disjoint graphs
3.220 - into the node-set of one graph.
3.221 - Specialization for the case when
3.222 - _Graph1::Node is a base class and _Graph2::Node is derived from it.
3.223 - */
3.224 template <typename _Graph1, typename _Graph2>
3.225 - class MergeNodeGraphWrapperBase<
3.226 + class MergeNodeGraphWrapperBaseBase<
3.227 _Graph1, _Graph2, typename boost::enable_if<
3.228 boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> :
3.229 public P1<_Graph1>, public P2<_Graph2> {
3.230 @@ -286,13 +148,11 @@
3.231 typedef typename Parent1::Node Graph1Node;
3.232 typedef typename Parent2::Node Graph2Node;
3.233 protected:
3.234 - MergeNodeGraphWrapperBase() { }
3.235 + MergeNodeGraphWrapperBaseBase() { }
3.236 public:
3.237 - template <typename _Value> class NodeMap;
3.238
3.239 class Node : public Graph2Node {
3.240 - friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
3.241 - template <typename _Value> friend class NodeMap;
3.242 + friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
3.243 protected:
3.244 bool backward; //true, iff backward
3.245 public:
3.246 @@ -319,80 +179,15 @@
3.247 }
3.248 };
3.249
3.250 - //typedef void Edge;
3.251 - class Edge { };
3.252 -
3.253 - void first(Node& i) const {
3.254 - Parent1::graph->first(*static_cast<Graph1Node*>(&i));
3.255 - i.backward=false;
3.256 - if (*static_cast<Graph1Node*>(&i)==INVALID) {
3.257 - Parent2::graph->first(*static_cast<Graph2Node*>(&i));
3.258 - i.backward=true;
3.259 - }
3.260 - }
3.261 - void next(Node& i) const {
3.262 - if (!(i.backward)) {
3.263 - Parent1::graph->next(*static_cast<Graph1Node*>(&i));
3.264 - if (*static_cast<Graph1Node*>(&i)==INVALID) {
3.265 - Parent2::graph->first(*static_cast<Graph2Node*>(&i));
3.266 - i.backward=true;
3.267 - }
3.268 - } else {
3.269 - Parent2::graph->next(*static_cast<Graph2Node*>(&i));
3.270 - }
3.271 - }
3.272 + static bool forward(const Node& n) { return !n.backward; }
3.273 + static bool backward(const Node& n) { return n.backward; }
3.274 + static void setForward(Node& n) { n.backward=false; }
3.275 + static void setBackward(Node& n) { n.backward=true; }
3.276 + };
3.277 +
3.278
3.279 - int id(const Node& n) const {
3.280 - if (!n.backward)
3.281 - return this->Parent1::graph->id(n);
3.282 - else
3.283 - return this->Parent2::graph->id(n);
3.284 - }
3.285 -
3.286 - template <typename _Value>
3.287 - class NodeMap {
3.288 - protected:
3.289 - typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
3.290 - typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
3.291 - ParentMap1 forward_map;
3.292 - ParentMap2 backward_map;
3.293 - public:
3.294 - typedef _Value Value;
3.295 - typedef Node Key;
3.296 - NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
3.297 - forward_map(*(gw.Parent1::graph)),
3.298 - backward_map(*(gw.Parent2::graph)) { }
3.299 - NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
3.300 - const _Value& value) :
3.301 - forward_map(*(gw.Parent1::graph), value),
3.302 - backward_map(*(gw.Parent2::graph), value) { }
3.303 - _Value operator[](const Node& n) const {
3.304 - if (!n.backward)
3.305 - return forward_map[n];
3.306 - else
3.307 - return backward_map[n];
3.308 - }
3.309 - void set(const Node& n, const _Value& value) {
3.310 - if (!n.backward)
3.311 - forward_map.set(n, value);
3.312 - else
3.313 - backward_map.set(n, value);
3.314 - }
3.315 -// using ParentMap1::operator[];
3.316 -// using ParentMap2::operator[];
3.317 - };
3.318 -
3.319 - };
3.320 -
3.321 -
3.322 - /*! A graph wrapper base class
3.323 - for merging the node-set of two node-disjoint graphs
3.324 - into the node-set of one graph.
3.325 - Specialized implementaton for the case when _Graph1::Node is derived
3.326 - from _Graph2::Node.
3.327 - */
3.328 template <typename _Graph1, typename _Graph2>
3.329 - class MergeNodeGraphWrapperBase<
3.330 + class MergeNodeGraphWrapperBaseBase<
3.331 _Graph1, _Graph2, typename boost::enable_if<
3.332 boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> :
3.333 public P1<_Graph1>, public P2<_Graph2> {
3.334 @@ -405,13 +200,11 @@
3.335 typedef typename Parent1::Node Graph1Node;
3.336 typedef typename Parent2::Node Graph2Node;
3.337 protected:
3.338 - MergeNodeGraphWrapperBase() { }
3.339 + MergeNodeGraphWrapperBaseBase() { }
3.340 public:
3.341 - template <typename _Value> class NodeMap;
3.342
3.343 class Node : public Graph1Node {
3.344 - friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
3.345 - template <typename _Value> friend class NodeMap;
3.346 + friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
3.347 protected:
3.348 bool backward; //true, iff backward
3.349 public:
3.350 @@ -438,23 +231,42 @@
3.351 }
3.352 };
3.353
3.354 - //typedef void Edge;
3.355 + static bool forward(const Node& n) { return !n.backward; }
3.356 + static bool backward(const Node& n) { return n.backward; }
3.357 + static void setForward(Node& n) { n.backward=false; }
3.358 + static void setBackward(Node& n) { n.backward=true; }
3.359 + };
3.360 +
3.361 +
3.362 + template <typename _Graph1, typename _Graph2>
3.363 + class MergeNodeGraphWrapperBase :
3.364 + public MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> {
3.365 + public:
3.366 + typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
3.367 + typedef _Graph1 Graph1;
3.368 + typedef _Graph2 Graph2;
3.369 + typedef P1<_Graph1> Parent1;
3.370 + typedef P2<_Graph2> Parent2;
3.371 + typedef typename Parent1::Node Graph1Node;
3.372 + typedef typename Parent2::Node Graph2Node;
3.373 +
3.374 + typedef typename Parent::Node Node;
3.375 class Edge { };
3.376
3.377 void first(Node& i) const {
3.378 Parent1::graph->first(*static_cast<Graph1Node*>(&i));
3.379 - i.backward=false;
3.380 + this->setForward(i);
3.381 if (*static_cast<Graph1Node*>(&i)==INVALID) {
3.382 Parent2::graph->first(*static_cast<Graph2Node*>(&i));
3.383 - i.backward=true;
3.384 + this->setBackward(i);
3.385 }
3.386 }
3.387 void next(Node& i) const {
3.388 - if (!(i.backward)) {
3.389 + if (this->forward(i)) {
3.390 Parent1::graph->next(*static_cast<Graph1Node*>(&i));
3.391 if (*static_cast<Graph1Node*>(&i)==INVALID) {
3.392 Parent2::graph->first(*static_cast<Graph2Node*>(&i));
3.393 - i.backward=true;
3.394 + this->setBackward(i);
3.395 }
3.396 } else {
3.397 Parent2::graph->next(*static_cast<Graph2Node*>(&i));
3.398 @@ -462,7 +274,7 @@
3.399 }
3.400
3.401 int id(const Node& n) const {
3.402 - if (!n.backward)
3.403 + if (this->forward(n))
3.404 return this->Parent1::graph->id(n);
3.405 else
3.406 return this->Parent2::graph->id(n);
3.407 @@ -486,13 +298,13 @@
3.408 forward_map(*(gw.Parent1::graph), value),
3.409 backward_map(*(gw.Parent2::graph), value) { }
3.410 _Value operator[](const Node& n) const {
3.411 - if (!n.backward)
3.412 + if (Parent::forward(n))
3.413 return forward_map[n];
3.414 else
3.415 return backward_map[n];
3.416 }
3.417 void set(const Node& n, const _Value& value) {
3.418 - if (!n.backward)
3.419 + if (Parent::forward(n))
3.420 forward_map.set(n, value);
3.421 else
3.422 backward_map.set(n, value);
3.423 @@ -505,11 +317,24 @@
3.424
3.425
3.426 /*! A graph wrapper class
3.427 - fors merging the node-set of two node-disjoint graphs
3.428 - into one node-set. It does not satisfy
3.429 + for merging the node-set of two node-disjoint graphs
3.430 + into the node-set of one graph.
3.431 + Different implementations are according to the relation of
3.432 + _Graph1::Node and _Graph2::Node.
3.433 + If _Graph1::Node and _Graph2::Node are unrelated, then
3.434 + MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
3.435 + is derived from both.
3.436 + If _Graph1::Node and _Graph2::Node are the same type, then
3.437 + MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
3.438 + is derived from _Graph1::Node.
3.439 + If one of _Graph1::Node and _Graph2::Node
3.440 + is derived from the other one, then
3.441 + MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
3.442 + is derived from the derived type.
3.443 + It does not satisfy
3.444 StaticGraph concept as it has no edge-set which
3.445 works together with the node-set.
3.446 - */
3.447 + */
3.448 template <typename _Graph1, typename _Graph2>
3.449 class MergeNodeGraphWrapper : public
3.450 IterableGraphExtender<MergeNodeGraphWrapperBase<_Graph1, _Graph2> > {
3.451 @@ -582,6 +407,11 @@
3.452 }
3.453 };
3.454
3.455 + using Parent::forward;
3.456 + using Parent::backward;
3.457 + bool forward(const Edge& e) const { return !e.backward; }
3.458 + bool backward(const Edge& e) const { return e.backward; }
3.459 +
3.460 using Parent::first;
3.461 void first(Edge& i) const {
3.462 Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
3.463 @@ -592,17 +422,25 @@
3.464 }
3.465 }
3.466 void firstIn(Edge& i, const Node& n) const {
3.467 - Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
3.468 - i.backward=false;
3.469 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.470 + if (!backward(n)) {
3.471 + Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
3.472 + if (*static_cast<Graph1Edge*>(&i)==INVALID)
3.473 + i=INVALID;
3.474 + else
3.475 + i.backward=false;
3.476 + } else {
3.477 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
3.478 i.backward=true;
3.479 }
3.480 }
3.481 void firstOut(Edge& i, const Node& n) const {
3.482 - Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
3.483 - i.backward=false;
3.484 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.485 + if (!backward(n)) {
3.486 + Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
3.487 + if (*static_cast<Graph1Edge*>(&i)==INVALID)
3.488 + i=INVALID;
3.489 + else
3.490 + i.backward=false;
3.491 + } else {
3.492 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
3.493 i.backward=true;
3.494 }
3.495 @@ -623,10 +461,7 @@
3.496 void nextIn(Edge& i) const {
3.497 if (!(i.backward)) {
3.498 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
3.499 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.500 - Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
3.501 - i.backward=true;
3.502 - }
3.503 + if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
3.504 } else {
3.505 Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
3.506 }
3.507 @@ -634,10 +469,7 @@
3.508 void nextOut(Edge& i) const {
3.509 if (!(i.backward)) {
3.510 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
3.511 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.512 - Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
3.513 - i.backward=true;
3.514 - }
3.515 + if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
3.516 } else {
3.517 Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
3.518 }
3.519 @@ -749,7 +581,7 @@
3.520 /// original one, otherwise its oppositely directed pair is obtained.
3.521 Edge(const Graph1Edge& n1,
3.522 const Graph2Edge& n2, bool _backward) :
3.523 - Graph1Edge(!backward ? n1 : n2), backward(_backward) { }
3.524 + Graph1Edge(!_backward ? n1 : n2), backward(_backward) { }
3.525 Edge(Invalid i) : Graph1Edge(i), backward(true) { }
3.526 bool operator==(const Edge& v) const {
3.527 return (backward==v.backward &&
3.528 @@ -760,6 +592,11 @@
3.529 }
3.530 };
3.531
3.532 + using Parent::forward;
3.533 + using Parent::backward;
3.534 + bool forward(const Edge& e) const { return !e.backward; }
3.535 + bool backward(const Edge& e) const { return e.backward; }
3.536 +
3.537 using Parent::first;
3.538 void first(Edge& i) const {
3.539 Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
3.540 @@ -770,17 +607,25 @@
3.541 }
3.542 }
3.543 void firstIn(Edge& i, const Node& n) const {
3.544 - Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
3.545 - i.backward=false;
3.546 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.547 + if (!backward(n)) {
3.548 + Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
3.549 + if (*static_cast<Graph1Edge*>(&i)==INVALID)
3.550 + i=INVALID;
3.551 + else
3.552 + i.backward=false;
3.553 + } else {
3.554 Parent2::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
3.555 i.backward=true;
3.556 }
3.557 }
3.558 void firstOut(Edge& i, const Node& n) const {
3.559 - Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
3.560 - i.backward=false;
3.561 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.562 + if (!backward(n)) {
3.563 + Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
3.564 + if (*static_cast<Graph1Edge*>(&i)==INVALID)
3.565 + i=INVALID;
3.566 + else
3.567 + i.backward=false;
3.568 + } else {
3.569 Parent2::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
3.570 i.backward=true;
3.571 }
3.572 @@ -801,10 +646,7 @@
3.573 void nextIn(Edge& i) const {
3.574 if (!(i.backward)) {
3.575 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
3.576 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.577 - Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
3.578 - i.backward=true;
3.579 - }
3.580 + if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
3.581 } else {
3.582 Parent2::graph->nextIn(*static_cast<Graph1Edge*>(&i));
3.583 }
3.584 @@ -812,10 +654,7 @@
3.585 void nextOut(Edge& i) const {
3.586 if (!(i.backward)) {
3.587 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
3.588 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.589 - Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
3.590 - i.backward=true;
3.591 - }
3.592 + if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
3.593 } else {
3.594 Parent2::graph->nextOut(*static_cast<Graph1Edge*>(&i));
3.595 }
3.596 @@ -945,6 +784,11 @@
3.597 }
3.598 };
3.599
3.600 + using Parent::forward;
3.601 + using Parent::backward;
3.602 + bool forward(const Edge& e) const { return !e.backward; }
3.603 + bool backward(const Edge& e) const { return e.backward; }
3.604 +
3.605 using Parent::first;
3.606 void first(Edge& i) const {
3.607 Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
3.608 @@ -955,17 +799,25 @@
3.609 }
3.610 }
3.611 void firstIn(Edge& i, const Node& n) const {
3.612 - Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
3.613 - i.backward=false;
3.614 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.615 + if (!backward(n)) {
3.616 + Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
3.617 + if (*static_cast<Graph1Edge*>(&i)==INVALID)
3.618 + i=INVALID;
3.619 + else
3.620 + i.backward=false;
3.621 + } else {
3.622 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
3.623 i.backward=true;
3.624 }
3.625 }
3.626 void firstOut(Edge& i, const Node& n) const {
3.627 - Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
3.628 - i.backward=false;
3.629 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.630 + if (!backward(n)) {
3.631 + Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
3.632 + if (*static_cast<Graph1Edge*>(&i)==INVALID)
3.633 + i=INVALID;
3.634 + else
3.635 + i.backward=false;
3.636 + } else {
3.637 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
3.638 i.backward=true;
3.639 }
3.640 @@ -986,10 +838,7 @@
3.641 void nextIn(Edge& i) const {
3.642 if (!(i.backward)) {
3.643 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
3.644 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.645 - Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
3.646 - i.backward=true;
3.647 - }
3.648 + if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
3.649 } else {
3.650 Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
3.651 }
3.652 @@ -997,10 +846,7 @@
3.653 void nextOut(Edge& i) const {
3.654 if (!(i.backward)) {
3.655 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
3.656 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.657 - Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
3.658 - i.backward=true;
3.659 - }
3.660 + if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
3.661 } else {
3.662 Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
3.663 }
3.664 @@ -1129,6 +975,11 @@
3.665 }
3.666 };
3.667
3.668 + using Parent::forward;
3.669 + using Parent::backward;
3.670 + bool forward(const Edge& e) const { return !e.backward; }
3.671 + bool backward(const Edge& e) const { return e.backward; }
3.672 +
3.673 using Parent::first;
3.674 void first(Edge& i) const {
3.675 Parent1::graph->first(*static_cast<Graph1Edge*>(&i));
3.676 @@ -1139,17 +990,25 @@
3.677 }
3.678 }
3.679 void firstIn(Edge& i, const Node& n) const {
3.680 - Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
3.681 - i.backward=false;
3.682 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.683 + if (!backward(n)) {
3.684 + Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
3.685 + if (*static_cast<Graph1Edge*>(&i)==INVALID)
3.686 + i=INVALID;
3.687 + else
3.688 + i.backward=false;
3.689 + } else {
3.690 Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
3.691 i.backward=true;
3.692 }
3.693 }
3.694 void firstOut(Edge& i, const Node& n) const {
3.695 - Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
3.696 - i.backward=false;
3.697 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.698 + if (!backward(n)) {
3.699 + Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
3.700 + if (*static_cast<Graph1Edge*>(&i)==INVALID)
3.701 + i=INVALID;
3.702 + else
3.703 + i.backward=false;
3.704 + } else {
3.705 Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
3.706 i.backward=true;
3.707 }
3.708 @@ -1170,10 +1029,7 @@
3.709 void nextIn(Edge& i) const {
3.710 if (!(i.backward)) {
3.711 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
3.712 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.713 - Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
3.714 - i.backward=true;
3.715 - }
3.716 + if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
3.717 } else {
3.718 Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
3.719 }
3.720 @@ -1181,10 +1037,7 @@
3.721 void nextOut(Edge& i) const {
3.722 if (!(i.backward)) {
3.723 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
3.724 - if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.725 - Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
3.726 - i.backward=true;
3.727 - }
3.728 + if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
3.729 } else {
3.730 Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
3.731 }
3.732 @@ -1347,6 +1200,14 @@
3.733
3.734 int edgeNum() const { return edge_set_graph->edgeNum(); }
3.735
3.736 +// NNode addOldNode() {
3.737 +// return Parent::addNode();
3.738 +// }
3.739 +
3.740 +// ENode addNewNode() {
3.741 +// return edge_set_graph->addNode();
3.742 +// }
3.743 +
3.744 Edge addEdge(const Node& u, const Node& v) {
3.745 return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
3.746 }
3.747 @@ -1392,7 +1253,7 @@
3.748 typedef _Graph Graph;
3.749 typedef _EdgeSetGraph EdgeSetGraph;
3.750 typedef IterableGraphExtender<
3.751 - NewEdgeSetGraphWrapper<_Graph, _EdgeSetGraph> > Parent;
3.752 + NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
3.753 protected:
3.754 NewEdgeSetGraphWrapper() { }
3.755 public:
3.756 @@ -1409,6 +1270,51 @@
3.757 }
3.758 };
3.759
3.760 + /*! A graph wrapper class for the following functionality.
3.761 + The same as NewEdgeSetGrapWrapper, but the bijection and the graph of
3.762 + new edges is andled inthe class.
3.763 + */
3.764 + template <typename _Graph, typename _EdgeSetGraph>
3.765 + class NewEdgeSetGraphWrapper2 :
3.766 + public IterableGraphExtender<
3.767 + NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
3.768 + public:
3.769 + typedef _Graph Graph;
3.770 + typedef _EdgeSetGraph EdgeSetGraph;
3.771 + typedef IterableGraphExtender<
3.772 + NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
3.773 + protected:
3.774 + _EdgeSetGraph _edge_set_graph;
3.775 + typename Graph::template NodeMap<typename EdgeSetGraph::Node> _e_node;
3.776 + typename EdgeSetGraph::template NodeMap<typename Graph::Node> _n_node;
3.777 + NewEdgeSetGraphWrapper2() { }
3.778 + public:
3.779 + typedef typename Graph::Node Node;
3.780 + // typedef typename Parent::Edge Edge;
3.781 +
3.782 + NewEdgeSetGraphWrapper2(_Graph& _graph) :
3.783 + _edge_set_graph(),
3.784 + _e_node(_graph), _n_node(_edge_set_graph) {
3.785 + setGraph(_graph);
3.786 + setEdgeSetGraph(_edge_set_graph);
3.787 + setNodeMap(_n_node); setENodeMap(_e_node);
3.788 + Node n;
3.789 + for (this->first(n); n!=INVALID; this->next(n)) {
3.790 + typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
3.791 + _e_node.set(n, e);
3.792 + _n_node.set(e, n);
3.793 + }
3.794 + }
3.795 +
3.796 +// Node addNode() {
3.797 +// Node n=(*this).Parent::addNode();
3.798 +// typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
3.799 +// _e_node.set(n, e);
3.800 +// _n_node.set(e, n);
3.801 +// return n;
3.802 +// }
3.803 +
3.804 + };
3.805
3.806 /*! A graph wrapper base class
3.807 for merging graphs of type _Graph1 and _Graph2
3.808 @@ -1417,6 +1323,9 @@
3.809 into one graph.
3.810 In an other point of view, _Graph1 is extended with
3.811 the edge-set of _Graph2.
3.812 + \warning we need specialize dimplementations
3.813 + \todo we need specialize dimplementations
3.814 + \bug we need specialize dimplementations
3.815 */
3.816 template <typename _Graph1, typename _Graph2, typename Enable=void>
3.817 class AugmentingGraphWrapperBase :
3.818 @@ -1506,9 +1415,10 @@
3.819 }
3.820 void nextIn(Edge& i) const {
3.821 if (!(i.backward)) {
3.822 + Node n=target(i);
3.823 Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
3.824 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.825 - graph2->first(*static_cast<Graph2Edge*>(&i));
3.826 + graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
3.827 i.backward=true;
3.828 }
3.829 } else {
3.830 @@ -1517,9 +1427,10 @@
3.831 }
3.832 void nextOut(Edge& i) const {
3.833 if (!(i.backward)) {
3.834 + Node n=source(i);
3.835 Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
3.836 if (*static_cast<Graph1Edge*>(&i)==INVALID) {
3.837 - graph2->first(*static_cast<Graph2Edge*>(&i));
3.838 + graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
3.839 i.backward=true;
3.840 }
3.841 } else {
4.1 --- a/src/work/marci/merge_node_graph_wrapper_test.cc Mon Nov 29 16:11:51 2004 +0000
4.2 +++ b/src/work/marci/merge_node_graph_wrapper_test.cc Mon Nov 29 17:55:46 2004 +0000
4.3 @@ -4,6 +4,7 @@
4.4 #include <lemon/list_graph.h>
4.5 #include <lemon/smart_graph.h>
4.6 #include <lemon/dimacs.h>
4.7 +#include <lemon/preflow.h>
4.8 #include <lemon/full_graph.h>
4.9 #include <merge_node_graph_wrapper.h>
4.10
4.11 @@ -26,66 +27,152 @@
4.12 void printGraph(const Graph& g) {
4.13 cout << " nodes:" << endl;
4.14 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
4.15 - cout << " " << g.id(n) << endl;
4.16 + cout << " " << g.id(n) << ": out edges:" << endl;
4.17 + for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
4.18 + cout << " " << g.id(g.source(e)) << "->" << g.id(g.target(e)) << endl;
4.19 }
4.20 cout << " edges:" << endl;
4.21 - for (typename Graph::EdgeIt n(g); n!=INVALID; ++n) {
4.22 - cout << " " << g.id(n) << ": "
4.23 - << g.id(g.source(n)) << "->" << g.id(g.target(n)) << endl;
4.24 + for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
4.25 + cout << " " << g.id(e) << ": "
4.26 + << g.id(g.source(e)) << "->" << g.id(g.target(e)) << endl;
4.27 }
4.28 }
4.29
4.30 int main() {
4.31 {
4.32 cout << "FIRST TEST" << endl;
4.33 - typedef SmartGraph Graph1;
4.34 + //typedef SmartGraph Graph1;
4.35 + typedef ListGraph Graph1;
4.36 typedef ListGraph Graph2;
4.37 + typedef SmartGraph Graph3;
4.38
4.39 - {
4.40 - checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >();
4.41 - MergeEdgeGraphWrapper<Graph1, Graph2>::printNode();
4.42 - MergeEdgeGraphWrapper<Graph1, Graph2>::printEdge();
4.43 - checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph1> >();
4.44 - MergeEdgeGraphWrapper<Graph1, Graph1>::printNode();
4.45 - MergeEdgeGraphWrapper<Graph1, Graph1>::printEdge();
4.46 - typedef ResGraphWrapper<Graph1, int,
4.47 - ConstMap<Graph1, int>, ConstMap<Graph1, int> > Graph4;
4.48 - checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph4> >();
4.49 - MergeEdgeGraphWrapper<Graph1, Graph4>::printNode();
4.50 - MergeEdgeGraphWrapper<Graph1, Graph4>::printEdge();
4.51 - checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph4, Graph1> >();
4.52 - MergeEdgeGraphWrapper<Graph4, Graph1>::printNode();
4.53 - MergeEdgeGraphWrapper<Graph4, Graph1>::printEdge();
4.54 - }
4.55 +// {
4.56 +// checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >();
4.57 +// MergeEdgeGraphWrapper<Graph1, Graph2>::printNode();
4.58 +// MergeEdgeGraphWrapper<Graph1, Graph2>::printEdge();
4.59 +// checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph1> >();
4.60 +// MergeEdgeGraphWrapper<Graph1, Graph1>::printNode();
4.61 +// MergeEdgeGraphWrapper<Graph1, Graph1>::printEdge();
4.62 +// typedef ResGraphWrapper<Graph1, int,
4.63 +// ConstMap<Graph1, int>, ConstMap<Graph1, int> > Graph4;
4.64 +// checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph4> >();
4.65 +// MergeEdgeGraphWrapper<Graph1, Graph4>::printNode();
4.66 +// MergeEdgeGraphWrapper<Graph1, Graph4>::printEdge();
4.67 +// checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph4, Graph1> >();
4.68 +// MergeEdgeGraphWrapper<Graph4, Graph1>::printNode();
4.69 +// MergeEdgeGraphWrapper<Graph4, Graph1>::printEdge();
4.70 +// }
4.71
4.72 Graph1 g1;
4.73 Graph2 g2;
4.74 typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
4.75 GW gw(g1, g2);
4.76 + Graph1::Node s1, t1;
4.77 + Graph2::Node s2, t2;
4.78 + Graph1::EdgeMap<int> cap1(g1);
4.79 + Graph2::EdgeMap<int> cap2(g2);
4.80
4.81 std::ifstream f1("graph1.dim");
4.82 std::ifstream f2("graph2.dim");
4.83 readDimacs(f1, g1);
4.84 readDimacs(f2, g2);
4.85 +
4.86 +// GW::NodeMap<int> ize(gw, 8);
4.87 +// for (GW::NodeIt n(gw); n!=INVALID; ++n) ize.set(n, 9);
4.88 +// GW::EdgeMap<int> mize(gw, 8);
4.89 +// for (GW::EdgeIt n(gw); n!=INVALID; ++n) mize.set(n, 7);
4.90 +
4.91 +// std::ifstream f1("flow-1.dim");
4.92 +// std::ifstream f2("flow2.dim");
4.93 +// readDimacs(f1, g1, cap1, s1, t1);
4.94 +// readDimacs(f2, g2, cap2, s2, t2);
4.95
4.96 - cout << "1st graph" << endl;
4.97 - printGraph(g1);
4.98 +// GW::EdgeMap<int> cap(gw);
4.99 +// for (GW::EdgeIt e(gw); e!=INVALID; ++e) {
4.100 +// if (gw.forward(e)) cap.set(e, cap1[e]);
4.101 +// if (gw.backward(e)) cap.set(e, cap2[e]);
4.102 +// }
4.103
4.104 - cout << "2nd graph" << endl;
4.105 - printGraph(g2);
4.106 +// {
4.107 +// GW::EdgeMap<int> flow(gw, 0);
4.108 +// Preflow<GW, int> preflow(gw, GW::Node(s1, INVALID, false),
4.109 +// GW::Node(t1, INVALID, false), cap, flow);
4.110 +// preflow.run();
4.111 +// std::cout << "s1->t1: " << preflow.flowValue() << std::endl;
4.112 +// }
4.113 +// {
4.114 +// GW::EdgeMap<int> flow(gw, 0);
4.115 +// Preflow<GW, int> preflow(gw, GW::Node(INVALID, s2, true),
4.116 +// GW::Node(INVALID, t2, true), cap, flow);
4.117 +// preflow.run();
4.118 +// std::cout << "s2->t2: " << preflow.flowValue() << std::endl;
4.119 +// }
4.120 +// {
4.121 +// GW::EdgeMap<int> flow(gw, 0);
4.122 +// Preflow<GW, int> preflow(gw, GW::Node(s1, INVALID, false),
4.123 +// GW::Node(INVALID, t2, true), cap, flow);
4.124 +// preflow.run();
4.125 +// std::cout << "s1->t2: " << preflow.flowValue() << std::endl;
4.126 +// }
4.127 +// {
4.128 +// GW::EdgeMap<int> flow(gw, 0);
4.129 +// Preflow<GW, int> preflow(gw, GW::Node(INVALID, s2, true),
4.130 +// GW::Node(s1, INVALID, false), cap, flow);
4.131 +// preflow.run();
4.132 +// std::cout << "s2->t1: " << preflow.flowValue() << std::endl;
4.133 +// }
4.134 + cout << "1st graph" << endl;
4.135 + printGraph(g1);
4.136
4.137 - cout << "merged graph" << endl;
4.138 - printGraph(gw);
4.139 + cout << "2nd graph" << endl;
4.140 + printGraph(g2);
4.141
4.142 + cout << "merged graph" << endl;
4.143 + printGraph(gw);
4.144 +
4.145 +// for (GW::NodeIt n(gw); n!=INVALID; ++n)
4.146 +// std::cout << ize[n] << std::endl;
4.147 +// for (GW::EdgeIt n(gw); n!=INVALID; ++n)
4.148 +// std::cout << mize[n] << std::endl;
4.149 +
4.150 + typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW;
4.151 +// {
4.152 +// checkConcept<StaticGraph, GWW>();
4.153 +// }
4.154 +
4.155 + GWW gww(gw);
4.156 +
4.157 + cout << "new edges graph" << endl;
4.158 + printGraph(gww);
4.159 +
4.160 + GWW::NodeIt n(gww);
4.161 + GWW::Node n1=n;
4.162 + ++n;
4.163 + GWW::Node n2=n;
4.164 + gww.addEdge(n1, n2);
4.165 + // gww.addNode();
4.166 + // gww.addNode();
4.167 +
4.168 + cout << "new edges graph" << endl;
4.169 + printGraph(gww);
4.170 +
4.171 + typedef AugmentingGraphWrapper<GW, GWW> GWWW;
4.172 + // {
4.173 + // checkConcept<StaticGraph, GWWW>();
4.174 + // }
4.175 + GWWW gwww(gw, gww);
4.176 +
4.177 + cout << "fully merged graph" << endl;
4.178 + printGraph(gwww);
4.179 }
4.180
4.181
4.182 {
4.183 cout << "SECOND TEST" << endl;
4.184 typedef SmartGraph Graph1;
4.185 - {
4.186 - checkConcept<StaticGraph, Graph1>();
4.187 - }
4.188 +// {
4.189 +// checkConcept<StaticGraph, Graph1>();
4.190 +// }
4.191
4.192 Graph1 g1;
4.193
4.194 @@ -93,16 +180,16 @@
4.195 ConstMap<FullGraph::Edge, bool> const_false_map(false);
4.196 typedef EdgeSubGraphWrapper<FullGraph, ConstMap<FullGraph::Edge, bool> >
4.197 Graph2;
4.198 - {
4.199 - checkConcept<StaticGraph, Graph2>();
4.200 - }
4.201 +// {
4.202 +// checkConcept<StaticGraph, Graph2>();
4.203 +// }
4.204
4.205 Graph2 g2(pre_g2, const_false_map);
4.206
4.207 typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
4.208 - {
4.209 - checkConcept<StaticGraph, GW>();
4.210 - }
4.211 +// {
4.212 +// checkConcept<StaticGraph, GW>();
4.213 +// }
4.214 GW gw(g1, g2);
4.215 GW::Node sw;
4.216 GW::Node tw;
4.217 @@ -137,9 +224,9 @@
4.218 }
4.219
4.220 typedef NewEdgeSetGraphWrapper<GW, Graph3> GWW;
4.221 - {
4.222 - checkConcept<StaticGraph, GWW>();
4.223 - }
4.224 +// {
4.225 +// checkConcept<StaticGraph, GWW>();
4.226 +// }
4.227
4.228 GWW gww(gw, g3, gwn, g3n);
4.229
4.230 @@ -158,9 +245,9 @@
4.231 printGraph(gww);
4.232
4.233 typedef AugmentingGraphWrapper<GW, GWW> GWWW;
4.234 - {
4.235 - checkConcept<StaticGraph, GWWW>();
4.236 - }
4.237 +// {
4.238 +// checkConcept<StaticGraph, GWWW>();
4.239 +// }
4.240 GWWW gwww(gw, gww);
4.241
4.242 cout << "new edges merged into the original graph" << endl;