1.1 --- a/src/work/marci/edmonds_karp.h Thu Apr 08 13:11:58 2004 +0000
1.2 +++ b/src/work/marci/edmonds_karp.h Tue Apr 13 20:35:47 2004 +0000
1.3 @@ -599,13 +599,19 @@
1.4 pred.set(s, INVALID);
1.5 //invalid iterators for sources
1.6
1.7 - typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
1.8 + typename ErasingResGW::NodeMap<Number> free1(erasing_res_graph);
1.9
1.10 - dfs.pushAndSetReached(s);
1.11 + dfs.pushAndSetReached(
1.12 + typename ErasingResGW::Node(
1.13 + typename FilterResGW::Node(
1.14 + typename ResGW::Node(s)
1.15 + )
1.16 + )
1.17 + );
1.18 while (!dfs.finished()) {
1.19 ++dfs;
1.20 if (erasing_res_graph.valid(
1.21 - /*typename ErasingResGW::OutEdgeIt*/(dfs)))
1.22 + typename ErasingResGW::OutEdgeIt(dfs)))
1.23 {
1.24 if (dfs.isBNodeNewlyReached()) {
1.25
1.26 @@ -614,9 +620,11 @@
1.27
1.28 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
1.29 if (erasing_res_graph.valid(pred[v])) {
1.30 - free.set(w, std::min(free[v], res_graph.resCap(dfs)));
1.31 + free1.set(w, std::min(free1[v], res_graph.resCap(
1.32 + typename ErasingResGW::OutEdgeIt(dfs))));
1.33 } else {
1.34 - free.set(w, res_graph.resCap(dfs));
1.35 + free1.set(w, res_graph.resCap(
1.36 + typename ErasingResGW::OutEdgeIt(dfs)));
1.37 }
1.38
1.39 if (w==t) {
1.40 @@ -631,8 +639,17 @@
1.41 }
1.42
1.43 if (__augment) {
1.44 - typename ErasingResGW::Node n=t;
1.45 - Number augment_value=free[n];
1.46 + typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
1.47 +// typename ResGW::NodeMap<Number> a(res_graph);
1.48 +// typename ResGW::Node b;
1.49 +// Number j=a[b];
1.50 +// typename FilterResGW::NodeMap<Number> a1(filter_res_graph);
1.51 +// typename FilterResGW::Node b1;
1.52 +// Number j1=a1[b1];
1.53 +// typename ErasingResGW::NodeMap<Number> a2(erasing_res_graph);
1.54 +// typename ErasingResGW::Node b2;
1.55 +// Number j2=a2[b2];
1.56 + Number augment_value=free1[n];
1.57 while (erasing_res_graph.valid(pred[n])) {
1.58 typename ErasingResGW::OutEdgeIt e=pred[n];
1.59 res_graph.augment(e, augment_value);
2.1 --- a/src/work/marci/edmonds_karp_demo.cc Thu Apr 08 13:11:58 2004 +0000
2.2 +++ b/src/work/marci/edmonds_karp_demo.cc Tue Apr 13 20:35:47 2004 +0000
2.3 @@ -35,8 +35,8 @@
2.4
2.5 typedef ListGraph MutableGraph;
2.6
2.7 - typedef SmartGraph Graph;
2.8 - //typedef ListGraph Graph;
2.9 +// typedef SmartGraph Graph;
2.10 + typedef ListGraph Graph;
2.11 typedef Graph::Node Node;
2.12 typedef Graph::EdgeIt EdgeIt;
2.13
2.14 @@ -67,23 +67,6 @@
2.15 Graph::EdgeMap<int> cap(G);
2.16 readDimacsMaxFlow(std::cin, G, s, t, cap);
2.17
2.18 -// typedef TrivGraphWrapper<Graph> TGW;
2.19 -// TGW gw(G);
2.20 -// TGW::NodeIt sw;
2.21 -// gw./*getF*/first(sw);
2.22 -// std::cout << "p1:" << gw.nodeNum() << std::endl;
2.23 -// gw.erase(sw);
2.24 -// std::cout << "p2:" << gw.nodeNum() << std::endl;
2.25 -
2.26 -// typedef const Graph cLG;
2.27 -// typedef TrivGraphWrapper<const cLG> CTGW;
2.28 -// CTGW cgw(G);
2.29 -// CTGW::NodeIt csw;
2.30 -// cgw./*getF*/first(csw);
2.31 -// std::cout << "p1:" << cgw.nodeNum() << std::endl;
2.32 -// //cgw.erase(csw);
2.33 -// std::cout << "p2:" << cgw.nodeNum() << std::endl;
2.34 -
2.35 {
2.36 std::cout << "preflow ..." << std::endl;
2.37 Graph::EdgeMap<int> flow(G); //0 flow
3.1 --- a/src/work/marci/graph_wrapper.h Thu Apr 08 13:11:58 2004 +0000
3.2 +++ b/src/work/marci/graph_wrapper.h Tue Apr 13 20:35:47 2004 +0000
3.3 @@ -6,156 +6,6 @@
3.4
3.5 namespace hugo {
3.6
3.7 -// template<typename Graph>
3.8 -// class TrivGraphWrapper {
3.9 -// protected:
3.10 -// Graph* graph;
3.11 -
3.12 -// public:
3.13 -// // typedef Graph BaseGraph;
3.14 -// typedef Graph ParentGraph;
3.15 -
3.16 -// // TrivGraphWrapper() : graph(0) { }
3.17 -// TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
3.18 -// // void setGraph(Graph& _graph) { graph = &_graph; }
3.19 -// // Graph& getGraph() const { return *graph; }
3.20 -
3.21 -// typedef typename Graph::Node Node;
3.22 -// class NodeIt : public Graph::NodeIt {
3.23 -// public:
3.24 -// NodeIt() { }
3.25 -// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
3.26 -// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
3.27 -// NodeIt(const TrivGraphWrapper<Graph>& _G) :
3.28 -// Graph::NodeIt(*(_G.graph)) { }
3.29 -// };
3.30 -// typedef typename Graph::Edge Edge;
3.31 -// class OutEdgeIt : public Graph::OutEdgeIt {
3.32 -// public:
3.33 -// OutEdgeIt() { }
3.34 -// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
3.35 -// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
3.36 -// OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
3.37 -// Graph::OutEdgeIt(*(_G.graph), n) { }
3.38 -// };
3.39 -// class InEdgeIt : public Graph::InEdgeIt {
3.40 -// public:
3.41 -// InEdgeIt() { }
3.42 -// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
3.43 -// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
3.44 -// InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :
3.45 -// Graph::InEdgeIt(*(_G.graph), n) { }
3.46 -// };
3.47 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.48 -// class EdgeIt : public Graph::EdgeIt {
3.49 -// public:
3.50 -// EdgeIt() { }
3.51 -// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
3.52 -// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
3.53 -// EdgeIt(const TrivGraphWrapper<Graph>& _G) :
3.54 -// Graph::EdgeIt(*(_G.graph)) { }
3.55 -// };
3.56 -
3.57 -// NodeIt& first(NodeIt& i) const {
3.58 -// i=NodeIt(*this);
3.59 -// return i;
3.60 -// }
3.61 -// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
3.62 -// i=OutEdgeIt(*this, p);
3.63 -// return i;
3.64 -// }
3.65 -// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
3.66 -// i=InEdgeIt(*this, p);
3.67 -// return i;
3.68 -// }
3.69 -// EdgeIt& first(EdgeIt& i) const {
3.70 -// i=EdgeIt(*this);
3.71 -// return i;
3.72 -// }
3.73 -// // template<typename I> I& first(I& i) const {
3.74 -// // i=I(*this);
3.75 -// // return i;
3.76 -// // }
3.77 -// // template<typename I, typename P> I& first(I& i, const P& p) const {
3.78 -// // i=I(*this, p);
3.79 -// // return i;
3.80 -// // }
3.81 -
3.82 -// // template<typename I> I getNext(const I& i) const {
3.83 -// // return graph->getNext(i); }
3.84 -
3.85 -// NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
3.86 -// OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
3.87 -// InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
3.88 -// EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }
3.89 -// // template<typename I> I& next(I &i) const { graph->next(i); return i; }
3.90 -// template< typename It > It first() const {
3.91 -// It e; this->first(e); return e; }
3.92 -
3.93 -// template< typename It > It first(const Node& v) const {
3.94 -// It e; this->first(e, v); return e; }
3.95 -
3.96 -// Node head(const Edge& e) const { return graph->head(e); }
3.97 -// Node tail(const Edge& e) const { return graph->tail(e); }
3.98 -
3.99 -// template<typename I> bool valid(const I& i) const {
3.100 -// return graph->valid(i); }
3.101 -
3.102 -// //template<typename I> void setInvalid(const I &i);
3.103 -// //{ return graph->setInvalid(i); }
3.104 -
3.105 -// int nodeNum() const { return graph->nodeNum(); }
3.106 -// int edgeNum() const { return graph->edgeNum(); }
3.107 -
3.108 -// template<typename I> Node aNode(const I& e) const {
3.109 -// return graph->aNode(e); }
3.110 -// template<typename I> Node bNode(const I& e) const {
3.111 -// return graph->bNode(e); }
3.112 -
3.113 -// Node addNode() const { return graph->addNode(); }
3.114 -// Edge addEdge(const Node& tail, const Node& head) const {
3.115 -// return graph->addEdge(tail, head); }
3.116 -
3.117 -// template<typename I> void erase(const I& i) const { graph->erase(i); }
3.118 -
3.119 -// void clear() const { graph->clear(); }
3.120 -
3.121 -// template<typename T> class NodeMap : public Graph::NodeMap<T> {
3.122 -// public:
3.123 -// NodeMap(const TrivGraphWrapper<Graph>& _G) :
3.124 -// Graph::NodeMap<T>(*(_G.graph)) { }
3.125 -// NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
3.126 -// Graph::NodeMap<T>(*(_G.graph), a) { }
3.127 -// };
3.128 -
3.129 -// template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
3.130 -// public:
3.131 -// EdgeMap(const TrivGraphWrapper<Graph>& _G) :
3.132 -// Graph::EdgeMap<T>(*(_G.graph)) { }
3.133 -// EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
3.134 -// Graph::EdgeMap<T>(*(_G.graph), a) { }
3.135 -// };
3.136 -
3.137 -// // template<typename Map, typename T> class NodeMapWrapper {
3.138 -// // protected:
3.139 -// // Map* map;
3.140 -// // public:
3.141 -// // NodeMapWrapper(Map& _map) : map(&_map) { }
3.142 -// // void set(Node n, T a) { map->set(n, a); }
3.143 -// // T get(Node n) const { return map->get(n); }
3.144 -// // };
3.145 -
3.146 -// // template<typename Map, typename T> class EdgeMapWrapper {
3.147 -// // protected:
3.148 -// // Map* map;
3.149 -// // public:
3.150 -// // EdgeMapWrapper(Map& _map) : map(&_map) { }
3.151 -// // void set(Edge n, T a) { map->set(n, a); }
3.152 -// // T get(Edge n) const { return map->get(n); }
3.153 -// // };
3.154 -// };
3.155 -
3.156 -
3.157 template<typename Graph>
3.158 class GraphWrapper {
3.159 protected:
3.160 @@ -170,77 +20,100 @@
3.161 // void setGraph(Graph& _graph) { graph=&_graph; }
3.162 // Graph& getGraph() const { return *graph; }
3.163
3.164 - typedef typename Graph::Node Node;
3.165 - class NodeIt : public Graph::NodeIt {
3.166 - typedef typename Graph::NodeIt GraphNodeIt;
3.167 +// typedef typename Graph::Node Node;
3.168 + class Node : public Graph::Node {
3.169 + friend class GraphWrapper<Graph>;
3.170 public:
3.171 + Node() { }
3.172 + Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
3.173 + Node(const Invalid& i) : Graph::Node(i) { }
3.174 + };
3.175 + class NodeIt {
3.176 + friend class GraphWrapper<Graph>;
3.177 + typename Graph::NodeIt n;
3.178 + public:
3.179 NodeIt() { }
3.180 - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
3.181 - NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
3.182 - NodeIt(const GraphWrapper<Graph>& _G) :
3.183 - Graph::NodeIt(*(_G.graph)) { }
3.184 -// operator Node() const {
3.185 -// std::cout << "ize" << std::endl;
3.186 -// return Node(this->GraphNodeIt);
3.187 -// }
3.188 + NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
3.189 + NodeIt(const Invalid& i) : n(i) { }
3.190 + NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { }
3.191 + operator Node() const { return Node(typename Graph::Node(n)); }
3.192 };
3.193 - typedef typename Graph::Edge Edge;
3.194 - class OutEdgeIt : public Graph::OutEdgeIt {
3.195 - typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
3.196 +// class Node : public Graph::Node {
3.197 +// public:
3.198 +// Node() { }
3.199 +// Node(const typename Graph::Node& n) : Graph::Node(n) { }
3.200 +// Node(const Invalid& i) : Graph::Node(i) { }
3.201 +// };
3.202 +// class NodeIt : public Graph::NodeIt {
3.203 +// typedef typename Graph::NodeIt GraphNodeIt;
3.204 +// public:
3.205 +// NodeIt() { }
3.206 +// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
3.207 +// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
3.208 +// NodeIt(const GraphWrapper<Graph>& _G) :
3.209 +// Graph::NodeIt(*(_G.graph)) { }
3.210 +// operator Node() const {
3.211 +// return Node(typename Graph::Node(
3.212 +// static_cast<typename Graph::NodeIt>(*this)
3.213 +// ));
3.214 +// }
3.215 +// };
3.216 +// typedef typename Graph::Edge Edge;
3.217 + class Edge : public Graph::Edge {
3.218 + friend class GraphWrapper<Graph>;
3.219 + public:
3.220 + Edge() { }
3.221 + Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { }
3.222 + Edge(const Invalid& i) : Graph::Edge(i) { }
3.223 + };
3.224 + class OutEdgeIt {
3.225 + friend class GraphWrapper<Graph>;
3.226 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
3.227 + typename Graph::OutEdgeIt e;
3.228 public:
3.229 OutEdgeIt() { }
3.230 - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
3.231 - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
3.232 - OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
3.233 - Graph::OutEdgeIt(*(_G.graph), n) { }
3.234 -// operator Edge() const {
3.235 -// std::cout << "ize" << std::endl;
3.236 -// return Edge(this->GraphOutEdgeIt);
3.237 -// }
3.238 + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
3.239 + OutEdgeIt(const Invalid& i) : e(i) { }
3.240 + OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
3.241 + e(*(_G.graph), typename Graph::Node(_n)) { }
3.242 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
3.243 };
3.244 - class InEdgeIt : public Graph::InEdgeIt {
3.245 - typedef typename Graph::InEdgeIt GraphInEdgeIt;
3.246 + class InEdgeIt {
3.247 + friend class GraphWrapper<Graph>;
3.248 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
3.249 + typename Graph::InEdgeIt e;
3.250 public:
3.251 InEdgeIt() { }
3.252 - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
3.253 - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
3.254 - InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) :
3.255 - Graph::InEdgeIt(*(_G.graph), n) { }
3.256 -// operator Edge() const {
3.257 -// std::cout << "ize" << std::endl;
3.258 -// return Edge(this->InOutEdgeIt);
3.259 -// }
3.260 + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
3.261 + InEdgeIt(const Invalid& i) : e(i) { }
3.262 + InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) :
3.263 + e(*(_G.graph), typename Graph::Node(_n)) { }
3.264 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
3.265 };
3.266 //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.267 - class EdgeIt : public Graph::EdgeIt {
3.268 - typedef typename Graph::EdgeIt GraphEdgeIt;
3.269 + class EdgeIt {
3.270 + friend class GraphWrapper<Graph>;
3.271 +// typedef typename Graph::EdgeIt GraphEdgeIt;
3.272 + typename Graph::EdgeIt e;
3.273 public:
3.274 EdgeIt() { }
3.275 - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
3.276 - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
3.277 - EdgeIt(const GraphWrapper<Graph>& _G) :
3.278 - Graph::EdgeIt(*(_G.graph)) { }
3.279 -// operator Edge() const {
3.280 -// std::cout << "ize" << std::endl;
3.281 -// return Edge(this->GraphEdgeIt);
3.282 -// }
3.283 + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
3.284 + EdgeIt(const Invalid& i) : e(i) { }
3.285 + EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { }
3.286 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
3.287 };
3.288
3.289 NodeIt& first(NodeIt& i) const {
3.290 - i=NodeIt(*this);
3.291 - return i;
3.292 + i=NodeIt(*this); return i;
3.293 }
3.294 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
3.295 - i=OutEdgeIt(*this, p);
3.296 - return i;
3.297 + i=OutEdgeIt(*this, p); return i;
3.298 }
3.299 InEdgeIt& first(InEdgeIt& i, const Node& p) const {
3.300 - i=InEdgeIt(*this, p);
3.301 - return i;
3.302 + i=InEdgeIt(*this, p); return i;
3.303 }
3.304 EdgeIt& first(EdgeIt& i) const {
3.305 - i=EdgeIt(*this);
3.306 - return i;
3.307 + i=EdgeIt(*this); return i;
3.308 }
3.309 // template<typename I> I& first(I& i) const {
3.310 // i=I(*this);
3.311 @@ -254,10 +127,10 @@
3.312 // template<typename I> I getNext(const I& i) const {
3.313 // return gw.getNext(i); }
3.314
3.315 - NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
3.316 - OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
3.317 - InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
3.318 - EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }
3.319 + NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
3.320 + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
3.321 + InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
3.322 + EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
3.323 // template<typename I> I& next(I &i) const { graph->next(i); return i; }
3.324 template< typename It > It first() const {
3.325 It e; this->first(e); return e; }
3.326 @@ -265,12 +138,18 @@
3.327 template< typename It > It first(const Node& v) const {
3.328 It e; this->first(e, v); return e; }
3.329
3.330 - Node head(const Edge& e) const { return graph->head(e); }
3.331 - Node tail(const Edge& e) const { return graph->tail(e); }
3.332 + Node head(const Edge& e) const {
3.333 + return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
3.334 + Node tail(const Edge& e) const {
3.335 + return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
3.336 // Node tail(const OutEdgeIt& e) const { return graph->tail(Edge(e)); }
3.337
3.338 - template<typename I> bool valid(const I& i) const {
3.339 - return graph->valid(i); }
3.340 + bool valid(const Node& n) const {
3.341 + return graph->valid(static_cast<typename Graph::Node>(n)); }
3.342 + bool valid(const Edge& e) const {
3.343 + return graph->valid(static_cast<typename Graph::Edge>(e)); }
3.344 +// template<typename I> bool valid(const I& i) const {
3.345 +// return graph->valid(i); }
3.346
3.347 //template<typename I> void setInvalid(const I &i);
3.348 //{ return graph->setInvalid(i); }
3.349 @@ -278,16 +157,22 @@
3.350 int nodeNum() const { return graph->nodeNum(); }
3.351 int edgeNum() const { return graph->edgeNum(); }
3.352
3.353 - template<typename I> Node aNode(const I& e) const {
3.354 - return graph->aNode(e); }
3.355 - template<typename I> Node bNode(const I& e) const {
3.356 - return graph->bNode(e); }
3.357 + Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
3.358 + Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
3.359 + Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
3.360 + Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
3.361 +// template<typename I> Node aNode(const I& e) const {
3.362 +// return Node(graph->aNode(e.e)); }
3.363 +// template<typename I> Node bNode(const I& e) const {
3.364 +// return Node(graph->bNode(e.e)); }
3.365
3.366 - Node addNode() const { return graph->addNode(); }
3.367 + Node addNode() const { return Node(graph->addNode()); }
3.368 Edge addEdge(const Node& tail, const Node& head) const {
3.369 - return graph->addEdge(tail, head); }
3.370 -
3.371 - template<typename I> void erase(const I& i) const { graph->erase(i); }
3.372 + return Edge(graph->addEdge(tail, head)); }
3.373 +
3.374 + void erase(const Node& i) const { graph->erase(i); }
3.375 + void erase(const Edge& i) const { graph->erase(i); }
3.376 +// template<typename I> void erase(const I& i) const { graph->erase(i); }
3.377
3.378 void clear() const { graph->clear(); }
3.379
3.380 @@ -297,6 +182,9 @@
3.381 Graph::NodeMap<T>(*(_G.graph)) { }
3.382 NodeMap(const GraphWrapper<Graph>& _G, T a) :
3.383 Graph::NodeMap<T>(*(_G.graph), a) { }
3.384 +// T operator[](const Node& n) const {
3.385 +// return Graph::NodeMap<T>::operator[](n);
3.386 +// }
3.387 };
3.388
3.389 template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
3.390 @@ -429,80 +317,144 @@
3.391 GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
3.392 edge_filter_map(&_edge_filter_map) { }
3.393
3.394 -
3.395 - typedef typename Graph::Node Node;
3.396 - class NodeIt : public Graph::NodeIt {
3.397 -// typedef typename Graph::NodeIt GraphNodeIt;
3.398 - public:
3.399 + typedef typename GraphWrapper<Graph>::Node Node;
3.400 + class NodeIt {
3.401 + friend class GraphWrapper<Graph>;
3.402 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
3.403 + typename Graph::NodeIt n;
3.404 + public:
3.405 NodeIt() { }
3.406 - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
3.407 - NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
3.408 + NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
3.409 + NodeIt(const Invalid& i) : n(i) { }
3.410 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
3.411 - Graph::NodeIt(*(_G.graph)) {
3.412 - while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
3.413 - !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
3.414 - _G.graph->next((*this)/*.GraphNodeIt*/);
3.415 + n(*(_G.graph)) {
3.416 + while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n])
3.417 + _G.graph->next(n);
3.418 }
3.419 + operator Node() const { return Node(typename Graph::Node(n)); }
3.420 };
3.421 - typedef typename Graph::Edge Edge;
3.422 - class OutEdgeIt : public Graph::OutEdgeIt {
3.423 +// class NodeIt : public Graph::NodeIt {
3.424 +// // typedef typename Graph::NodeIt GraphNodeIt;
3.425 +// public:
3.426 +// NodeIt() { }
3.427 +// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
3.428 +// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
3.429 +// NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
3.430 +// Graph::NodeIt(*(_G.graph)) {
3.431 +// while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
3.432 +// !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
3.433 +// _G.graph->next((*this)/*.GraphNodeIt*/);
3.434 +// }
3.435 +// };
3.436 + typedef typename GraphWrapper<Graph>::Edge Edge;
3.437 + class OutEdgeIt {
3.438 + friend class GraphWrapper<Graph>;
3.439 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
3.440 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
3.441 + typename Graph::OutEdgeIt e;
3.442 public:
3.443 OutEdgeIt() { }
3.444 - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
3.445 - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
3.446 - OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
3.447 - _G, const Node& n) :
3.448 - Graph::OutEdgeIt(*(_G.graph), n) {
3.449 - while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
3.450 - !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
3.451 - _G.graph->next((*this)/*.GraphOutEdgeIt*/);
3.452 + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
3.453 + OutEdgeIt(const Invalid& i) : e(i) { }
3.454 + OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
3.455 + const Node& _n) :
3.456 + e(*(_G.graph), typename Graph::Node(_n)) {
3.457 + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
3.458 + _G.graph->next(e);
3.459 }
3.460 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
3.461 };
3.462 - class InEdgeIt : public Graph::InEdgeIt {
3.463 + class InEdgeIt {
3.464 + friend class GraphWrapper<Graph>;
3.465 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
3.466 // typedef typename Graph::InEdgeIt GraphInEdgeIt;
3.467 + typename Graph::InEdgeIt e;
3.468 public:
3.469 InEdgeIt() { }
3.470 - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
3.471 - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
3.472 + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
3.473 + InEdgeIt(const Invalid& i) : e(i) { }
3.474 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
3.475 - const Node& n) :
3.476 - Graph::InEdgeIt(*(_G.graph), n) {
3.477 - while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
3.478 - !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
3.479 - _G.graph->next((*this)/*.GraphInEdgeIt*/);
3.480 + const Node& _n) :
3.481 + e(*(_G.graph), typename Graph::Node(_n)) {
3.482 + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
3.483 + _G.graph->next(e);
3.484 }
3.485 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
3.486 };
3.487 -// //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.488 - class EdgeIt : public Graph::EdgeIt {
3.489 + //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.490 + class EdgeIt {
3.491 + friend class GraphWrapper<Graph>;
3.492 + friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
3.493 // typedef typename Graph::EdgeIt GraphEdgeIt;
3.494 + typename Graph::EdgeIt e;
3.495 public:
3.496 EdgeIt() { }
3.497 - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
3.498 - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
3.499 + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
3.500 + EdgeIt(const Invalid& i) : e(i) { }
3.501 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
3.502 - Graph::EdgeIt(*(_G.graph)) {
3.503 - while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
3.504 - !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
3.505 - _G.graph->next((*this)/*.GraphEdgeIt*/);
3.506 + e(*(_G.graph)) {
3.507 + while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e])
3.508 + _G.graph->next(e);
3.509 }
3.510 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
3.511 };
3.512 +// operator Edge() const { return Edge(typename Graph::Edge(e)); }
3.513 +// };
3.514 +// class OutEdgeIt : public Graph::OutEdgeIt {
3.515 +// // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
3.516 +// public:
3.517 +// OutEdgeIt() { }
3.518 +// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
3.519 +// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
3.520 +// OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
3.521 +// _G, const Node& n) :
3.522 +// Graph::OutEdgeIt(*(_G.graph), n) {
3.523 +// while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
3.524 +// !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
3.525 +// _G.graph->next((*this)/*.GraphOutEdgeIt*/);
3.526 +// }
3.527 +// };
3.528 +// class InEdgeIt : public Graph::InEdgeIt {
3.529 +// // typedef typename Graph::InEdgeIt GraphInEdgeIt;
3.530 +// public:
3.531 +// InEdgeIt() { }
3.532 +// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
3.533 +// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
3.534 +// InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
3.535 +// const Node& n) :
3.536 +// Graph::InEdgeIt(*(_G.graph), n) {
3.537 +// while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
3.538 +// !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
3.539 +// _G.graph->next((*this)/*.GraphInEdgeIt*/);
3.540 +// }
3.541 +// };
3.542 +// // //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.543 +// class EdgeIt : public Graph::EdgeIt {
3.544 +// // typedef typename Graph::EdgeIt GraphEdgeIt;
3.545 +// public:
3.546 +// EdgeIt() { }
3.547 +// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
3.548 +// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
3.549 +// EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
3.550 +// Graph::EdgeIt(*(_G.graph)) {
3.551 +// while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
3.552 +// !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
3.553 +// _G.graph->next((*this)/*.GraphEdgeIt*/);
3.554 +// }
3.555 +// };
3.556
3.557 - NodeIt& first(NodeIt& i) const {
3.558 - i=NodeIt(*this);
3.559 - return i;
3.560 +
3.561 + NodeIt& first(NodeIt& i) const {
3.562 + i=NodeIt(*this); return i;
3.563 }
3.564 - OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
3.565 - i=OutEdgeIt(*this, n);
3.566 - return i;
3.567 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
3.568 + i=OutEdgeIt(*this, p); return i;
3.569 }
3.570 - InEdgeIt& first(InEdgeIt& i, const Node& n) const {
3.571 - i=InEdgeIt(*this, n);
3.572 - return i;
3.573 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
3.574 + i=InEdgeIt(*this, p); return i;
3.575 }
3.576 - EdgeIt& first(EdgeIt& i) const {
3.577 - i=EdgeIt(*this);
3.578 - return i;
3.579 + EdgeIt& first(EdgeIt& i) const {
3.580 + i=EdgeIt(*this); return i;
3.581 }
3.582
3.583 // template<typename I> I& first(I& i) const {
3.584 @@ -519,26 +471,32 @@
3.585 // }
3.586
3.587 NodeIt& next(NodeIt& i) const {
3.588 - graph->next(i);
3.589 - while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
3.590 + graph->next(i.n);
3.591 + while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); }
3.592 return i;
3.593 }
3.594 OutEdgeIt& next(OutEdgeIt& i) const {
3.595 - graph->next(i);
3.596 - while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
3.597 + graph->next(i.e);
3.598 + while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
3.599 return i;
3.600 }
3.601 InEdgeIt& next(InEdgeIt& i) const {
3.602 - graph->next(i);
3.603 - while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
3.604 + graph->next(i.e);
3.605 + while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
3.606 return i;
3.607 }
3.608 EdgeIt& next(EdgeIt& i) const {
3.609 - graph->next(i);
3.610 - while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
3.611 + graph->next(i.e);
3.612 + while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); }
3.613 return i;
3.614 }
3.615
3.616 +
3.617 + Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
3.618 + Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
3.619 + Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
3.620 + Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
3.621 +
3.622 //template<typename I> I getNext(const I& i) const {
3.623 // return gw.getNext(i);
3.624 //}
3.625 @@ -556,6 +514,147 @@
3.626 It e; this->first(e, v); return e; }
3.627 };
3.628
3.629 +// //Subgraph on the same node-set and partial edge-set
3.630 +// template<typename Graph, typename NodeFilterMap,
3.631 +// typename EdgeFilterMap>
3.632 +// class SubGraphWrapper : public GraphWrapper<Graph> {
3.633 +// protected:
3.634 +// NodeFilterMap* node_filter_map;
3.635 +// EdgeFilterMap* edge_filter_map;
3.636 +// public:
3.637 +// // SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
3.638 +// SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
3.639 +// EdgeFilterMap& _edge_filter_map) :
3.640 +// GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
3.641 +// edge_filter_map(&_edge_filter_map) { }
3.642 +
3.643 +
3.644 +// typedef typename Graph::Node Node;
3.645 +// class NodeIt : public Graph::NodeIt {
3.646 +// // typedef typename Graph::NodeIt GraphNodeIt;
3.647 +// public:
3.648 +// NodeIt() { }
3.649 +// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
3.650 +// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
3.651 +// NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
3.652 +// Graph::NodeIt(*(_G.graph)) {
3.653 +// while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
3.654 +// !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
3.655 +// _G.graph->next((*this)/*.GraphNodeIt*/);
3.656 +// }
3.657 +// };
3.658 +// typedef typename Graph::Edge Edge;
3.659 +// class OutEdgeIt : public Graph::OutEdgeIt {
3.660 +// // typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
3.661 +// public:
3.662 +// OutEdgeIt() { }
3.663 +// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
3.664 +// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
3.665 +// OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
3.666 +// _G, const Node& n) :
3.667 +// Graph::OutEdgeIt(*(_G.graph), n) {
3.668 +// while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
3.669 +// !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
3.670 +// _G.graph->next((*this)/*.GraphOutEdgeIt*/);
3.671 +// }
3.672 +// };
3.673 +// class InEdgeIt : public Graph::InEdgeIt {
3.674 +// // typedef typename Graph::InEdgeIt GraphInEdgeIt;
3.675 +// public:
3.676 +// InEdgeIt() { }
3.677 +// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
3.678 +// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
3.679 +// InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
3.680 +// const Node& n) :
3.681 +// Graph::InEdgeIt(*(_G.graph), n) {
3.682 +// while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
3.683 +// !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
3.684 +// _G.graph->next((*this)/*.GraphInEdgeIt*/);
3.685 +// }
3.686 +// };
3.687 +// // //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.688 +// class EdgeIt : public Graph::EdgeIt {
3.689 +// // typedef typename Graph::EdgeIt GraphEdgeIt;
3.690 +// public:
3.691 +// EdgeIt() { }
3.692 +// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
3.693 +// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
3.694 +// EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
3.695 +// Graph::EdgeIt(*(_G.graph)) {
3.696 +// while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
3.697 +// !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
3.698 +// _G.graph->next((*this)/*.GraphEdgeIt*/);
3.699 +// }
3.700 +// };
3.701 +
3.702 +// NodeIt& first(NodeIt& i) const {
3.703 +// i=NodeIt(*this);
3.704 +// return i;
3.705 +// }
3.706 +// OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
3.707 +// i=OutEdgeIt(*this, n);
3.708 +// return i;
3.709 +// }
3.710 +// InEdgeIt& first(InEdgeIt& i, const Node& n) const {
3.711 +// i=InEdgeIt(*this, n);
3.712 +// return i;
3.713 +// }
3.714 +// EdgeIt& first(EdgeIt& i) const {
3.715 +// i=EdgeIt(*this);
3.716 +// return i;
3.717 +// }
3.718 +
3.719 +// // template<typename I> I& first(I& i) const {
3.720 +// // graph->first(i);
3.721 +// // //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
3.722 +// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
3.723 +// // return i;
3.724 +// // }
3.725 +// // template<typename I, typename P> I& first(I& i, const P& p) const {
3.726 +// // graph->first(i, p);
3.727 +// // // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
3.728 +// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
3.729 +// // return i;
3.730 +// // }
3.731 +
3.732 +// NodeIt& next(NodeIt& i) const {
3.733 +// graph->next(i);
3.734 +// while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
3.735 +// return i;
3.736 +// }
3.737 +// OutEdgeIt& next(OutEdgeIt& i) const {
3.738 +// graph->next(i);
3.739 +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
3.740 +// return i;
3.741 +// }
3.742 +// InEdgeIt& next(InEdgeIt& i) const {
3.743 +// graph->next(i);
3.744 +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
3.745 +// return i;
3.746 +// }
3.747 +// EdgeIt& next(EdgeIt& i) const {
3.748 +// graph->next(i);
3.749 +// while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
3.750 +// return i;
3.751 +// }
3.752 +
3.753 +// //template<typename I> I getNext(const I& i) const {
3.754 +// // return gw.getNext(i);
3.755 +// //}
3.756 +// // template<typename I> I& next(I &i) const {
3.757 +// // graph->next(i);
3.758 +// // // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
3.759 +// // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
3.760 +// // return i;
3.761 +// // }
3.762 +
3.763 +// template< typename It > It first() const {
3.764 +// It e; this->first(e); return e; }
3.765 +
3.766 +// template< typename It > It first(const Node& v) const {
3.767 +// It e; this->first(e, v); return e; }
3.768 +// };
3.769 +
3.770 // template<typename GraphWrapper>
3.771 // class UndirGraphWrapper {
3.772 // protected:
3.773 @@ -718,109 +817,129 @@
3.774
3.775 template<typename Graph>
3.776 class UndirGraphWrapper : public GraphWrapper<Graph> {
3.777 - protected:
3.778 - typedef typename Graph::Edge GraphEdge;
3.779 - typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
3.780 - typedef typename Graph::InEdgeIt GraphInEdgeIt;
3.781 +// protected:
3.782 +// typedef typename Graph::Edge GraphEdge;
3.783 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
3.784 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
3.785 public:
3.786 typedef typename GraphWrapper<Graph>::Node Node;
3.787 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
3.788 + typedef typename GraphWrapper<Graph>::Edge Edge;
3.789 + typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
3.790
3.791 // UndirGraphWrapper() : GraphWrapper<Graph>() { }
3.792 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
3.793
3.794 - class Edge {
3.795 +
3.796 +// class Edge {
3.797 +// friend class UndirGraphWrapper<Graph>;
3.798 +// protected:
3.799 +// bool out_or_in; //true iff out
3.800 +// GraphOutEdgeIt out;
3.801 +// GraphInEdgeIt in;
3.802 +// public:
3.803 +// Edge() : out_or_in(), out(), in() { }
3.804 +// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
3.805 +// operator GraphEdge() const {
3.806 +// if (out_or_in) return(out); else return(in);
3.807 +// }
3.808 +// //FIXME
3.809 +// //2 edges are equal if they "refer" to the same physical edge
3.810 +// //is it good?
3.811 +// friend bool operator==(const Edge& u, const Edge& v) {
3.812 +// if (v.out_or_in)
3.813 +// if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
3.814 +// //return (u.out_or_in && u.out==v.out);
3.815 +// else
3.816 +// if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
3.817 +// //return (!u.out_or_in && u.in==v.in);
3.818 +// }
3.819 +// friend bool operator!=(const Edge& u, const Edge& v) {
3.820 +// if (v.out_or_in)
3.821 +// if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
3.822 +// //return (!u.out_or_in || u.out!=v.out);
3.823 +// else
3.824 +// if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
3.825 +// //return (u.out_or_in || u.in!=v.in);
3.826 +// }
3.827 +// };
3.828 +
3.829 + class OutEdgeIt {
3.830 friend class UndirGraphWrapper<Graph>;
3.831 - protected:
3.832 bool out_or_in; //true iff out
3.833 - GraphOutEdgeIt out;
3.834 - GraphInEdgeIt in;
3.835 + typename Graph::OutEdgeIt out;
3.836 + typename Graph::InEdgeIt in;
3.837 public:
3.838 - Edge() : out_or_in(), out(), in() { }
3.839 - Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
3.840 - operator GraphEdge() const {
3.841 - if (out_or_in) return(out); else return(in);
3.842 - }
3.843 -//FIXME
3.844 -//2 edges are equal if they "refer" to the same physical edge
3.845 -//is it good?
3.846 - friend bool operator==(const Edge& u, const Edge& v) {
3.847 - if (v.out_or_in)
3.848 - if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in);
3.849 - //return (u.out_or_in && u.out==v.out);
3.850 - else
3.851 - if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in);
3.852 - //return (!u.out_or_in && u.in==v.in);
3.853 + OutEdgeIt() { }
3.854 + OutEdgeIt(const Invalid& i) : Edge(i) { }
3.855 + OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
3.856 + out_or_in=true; _G.graph->first(out, _n);
3.857 + if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
3.858 }
3.859 - friend bool operator!=(const Edge& u, const Edge& v) {
3.860 - if (v.out_or_in)
3.861 - if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in);
3.862 - //return (!u.out_or_in || u.out!=v.out);
3.863 - else
3.864 - if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in);
3.865 - //return (u.out_or_in || u.in!=v.in);
3.866 - }
3.867 - };
3.868 -
3.869 - class OutEdgeIt : public Edge {
3.870 - friend class UndirGraphWrapper<Graph>;
3.871 - public:
3.872 - OutEdgeIt() : Edge() { }
3.873 - OutEdgeIt(const Invalid& i) : Edge(i) { }
3.874 - OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
3.875 - : Edge() {
3.876 - out_or_in=true; _G.graph->first(out, n);
3.877 - if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
3.878 + operator Edge() const {
3.879 + if (out_or_in) return Edge(out); else return Edge(in);
3.880 }
3.881 };
3.882 +// class OutEdgeIt : public Edge {
3.883 +// friend class UndirGraphWrapper<Graph>;
3.884 +// public:
3.885 +// OutEdgeIt() : Edge() { }
3.886 +// OutEdgeIt(const Invalid& i) : Edge(i) { }
3.887 +// OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n)
3.888 +// : Edge() {
3.889 +// out_or_in=true; _G.graph->first(out, n);
3.890 +// if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); }
3.891 +// }
3.892 +// };
3.893
3.894 +//FIXME InEdgeIt
3.895 typedef OutEdgeIt InEdgeIt;
3.896
3.897 - class EdgeIt : public Edge {
3.898 - friend class UndirGraphWrapper<Graph>;
3.899 - protected:
3.900 - NodeIt v;
3.901 - public:
3.902 - EdgeIt() : Edge() { }
3.903 - EdgeIt(const Invalid& i) : Edge(i) { }
3.904 - EdgeIt(const UndirGraphWrapper<Graph>& _G)
3.905 - : Edge() {
3.906 - out_or_in=true;
3.907 - //Node v;
3.908 - _G.first(v);
3.909 - if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
3.910 - while (_G.valid(v) && !_G.graph->valid(out)) {
3.911 - _G.graph->next(v);
3.912 - if (_G.valid(v)) _G.graph->first(out);
3.913 - }
3.914 - }
3.915 - };
3.916 +// class EdgeIt : public Edge {
3.917 +// friend class UndirGraphWrapper<Graph>;
3.918 +// protected:
3.919 +// NodeIt v;
3.920 +// public:
3.921 +// EdgeIt() : Edge() { }
3.922 +// EdgeIt(const Invalid& i) : Edge(i) { }
3.923 +// EdgeIt(const UndirGraphWrapper<Graph>& _G)
3.924 +// : Edge() {
3.925 +// out_or_in=true;
3.926 +// //Node v;
3.927 +// _G.first(v);
3.928 +// if (_G.valid(v)) _G.graph->first(out); else out=INVALID;
3.929 +// while (_G.valid(v) && !_G.graph->valid(out)) {
3.930 +// _G.graph->next(v);
3.931 +// if (_G.valid(v)) _G.graph->first(out);
3.932 +// }
3.933 +// }
3.934 +// };
3.935
3.936 - OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
3.937 - e.out_or_in=true; graph->first(e.out, n);
3.938 - if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); }
3.939 - return e;
3.940 + NodeIt& first(NodeIt& i) const {
3.941 + i=NodeIt(*this); return i;
3.942 }
3.943 -
3.944 - EdgeIt& first(EdgeIt& e) const {
3.945 - e.out_or_in=true;
3.946 - //NodeIt v;
3.947 - first(e.v);
3.948 - if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID;
3.949 - while (valid(e.v) && !graph->valid(e.out)) {
3.950 - graph->next(e.v);
3.951 - if (valid(e.v)) graph->first(e.out, e.v);
3.952 - }
3.953 - return e;
3.954 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
3.955 + i=OutEdgeIt(*this, p); return i;
3.956 + }
3.957 +//FIXME
3.958 +// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
3.959 +// i=InEdgeIt(*this, p); return i;
3.960 +// }
3.961 + EdgeIt& first(EdgeIt& i) const {
3.962 + i=EdgeIt(*this); return i;
3.963 }
3.964
3.965 template<typename I> I& first(I& i) const { graph->first(i); return i; }
3.966 template<typename I, typename P> I& first(I& i, const P& p) const {
3.967 graph->first(i, p); return i; }
3.968
3.969 + NodeIt& next(NodeIt& n) const {
3.970 + GraphWrapper<Graph>::next(n);
3.971 + return n;
3.972 + }
3.973 OutEdgeIt& next(OutEdgeIt& e) const {
3.974 if (e.out_or_in) {
3.975 - Node n=graph->tail(e.out);
3.976 + typename Graph::Node n=graph->tail(e.out);
3.977 graph->next(e.out);
3.978 if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); }
3.979 } else {
3.980 @@ -828,18 +947,14 @@
3.981 }
3.982 return e;
3.983 }
3.984 -
3.985 + //FIXME InEdgeIt
3.986 EdgeIt& next(EdgeIt& e) const {
3.987 - //NodeIt v=tail(e);
3.988 - graph->next(e.out);
3.989 - while (valid(e.v) && !graph->valid(e.out)) {
3.990 - next(e.v);
3.991 - if (valid(e.v)) graph->first(e.out, e.v);
3.992 - }
3.993 + GraphWrapper<Graph>::next(n);
3.994 +// graph->next(e.e);
3.995 return e;
3.996 }
3.997
3.998 - template<typename I> I& next(I &i) const { graph->next(i); return i; }
3.999 +// template<typename I> I& next(I &i) const { graph->next(i); return i; }
3.1000 // template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
3.1001
3.1002 template< typename It > It first() const {
3.1003 @@ -968,12 +1083,14 @@
3.1004 // };
3.1005
3.1006
3.1007 +
3.1008 +
3.1009 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.1010 class ResGraphWrapper : public GraphWrapper<Graph> {
3.1011 protected:
3.1012 - typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
3.1013 - typedef typename Graph::InEdgeIt GraphInEdgeIt;
3.1014 - typedef typename Graph::Edge GraphEdge;
3.1015 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
3.1016 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
3.1017 +// typedef typename Graph::Edge GraphEdge;
3.1018 FlowMap* flow;
3.1019 const CapacityMap* capacity;
3.1020 public:
3.1021 @@ -989,49 +1106,104 @@
3.1022
3.1023 typedef typename GraphWrapper<Graph>::Node Node;
3.1024 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
3.1025 - class Edge {
3.1026 + class Edge : public Graph::Edge {
3.1027 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.1028 protected:
3.1029 - bool out_or_in; //true, iff out
3.1030 - GraphOutEdgeIt out;
3.1031 - GraphInEdgeIt in;
3.1032 + bool forward; //true, iff forward
3.1033 +// typename Graph::Edge e;
3.1034 public:
3.1035 - Edge() : out_or_in(true) { }
3.1036 - Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
3.1037 -// bool valid() const {
3.1038 -// return out_or_in && out.valid() || in.valid(); }
3.1039 + Edge() { }
3.1040 + Edge(const typename Graph::Edge& _e, bool _forward) :
3.1041 + Graph::Edge(_e), forward(_forward) { }
3.1042 + Edge(const Invalid& i) : Graph::Edge(i), forward(false) { }
3.1043 +//the unique invalid iterator
3.1044 friend bool operator==(const Edge& u, const Edge& v) {
3.1045 - if (v.out_or_in)
3.1046 - return (u.out_or_in && u.out==v.out);
3.1047 - else
3.1048 - return (!u.out_or_in && u.in==v.in);
3.1049 + return (v.forward==u.forward &&
3.1050 + static_cast<typename Graph::Edge>(u)==
3.1051 + static_cast<typename Graph::Edge>(v));
3.1052 }
3.1053 friend bool operator!=(const Edge& u, const Edge& v) {
3.1054 - if (v.out_or_in)
3.1055 - return (!u.out_or_in || u.out!=v.out);
3.1056 - else
3.1057 - return (u.out_or_in || u.in!=v.in);
3.1058 + return (v.forward!=u.forward ||
3.1059 + static_cast<typename Graph::Edge>(u)!=
3.1060 + static_cast<typename Graph::Edge>(v));
3.1061 }
3.1062 - operator GraphEdge() const {
3.1063 - if (out_or_in) return(out); else return(in);
3.1064 - }
3.1065 };
3.1066 - class OutEdgeIt : public Edge {
3.1067 +// class Edge {
3.1068 +// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.1069 +// protected:
3.1070 +// bool out_or_in; //true, iff out
3.1071 +// GraphOutEdgeIt out;
3.1072 +// GraphInEdgeIt in;
3.1073 +// public:
3.1074 +// Edge() : out_or_in(true) { }
3.1075 +// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
3.1076 +// // bool valid() const {
3.1077 +// // return out_or_in && out.valid() || in.valid(); }
3.1078 +// friend bool operator==(const Edge& u, const Edge& v) {
3.1079 +// if (v.out_or_in)
3.1080 +// return (u.out_or_in && u.out==v.out);
3.1081 +// else
3.1082 +// return (!u.out_or_in && u.in==v.in);
3.1083 +// }
3.1084 +// friend bool operator!=(const Edge& u, const Edge& v) {
3.1085 +// if (v.out_or_in)
3.1086 +// return (!u.out_or_in || u.out!=v.out);
3.1087 +// else
3.1088 +// return (u.out_or_in || u.in!=v.in);
3.1089 +// }
3.1090 +// operator GraphEdge() const {
3.1091 +// if (out_or_in) return(out); else return(in);
3.1092 +// }
3.1093 +// };
3.1094 + class OutEdgeIt {
3.1095 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.1096 + protected:
3.1097 + typename Graph::OutEdgeIt out;
3.1098 + typename Graph::InEdgeIt in;
3.1099 + bool forward;
3.1100 public:
3.1101 OutEdgeIt() { }
3.1102 //FIXME
3.1103 - OutEdgeIt(const Edge& e) : Edge(e) { }
3.1104 - OutEdgeIt(const Invalid& i) : Edge(i) { }
3.1105 - OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
3.1106 +// OutEdgeIt(const Edge& e) : Edge(e) { }
3.1107 + OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
3.1108 +//the unique invalid iterator
3.1109 + OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
3.1110 + forward=true;
3.1111 resG.graph->first(out, v);
3.1112 - while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
3.1113 + while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
3.1114 if (!resG.graph->valid(out)) {
3.1115 - out_or_in=0;
3.1116 + forward=false;
3.1117 resG.graph->first(in, v);
3.1118 - while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
3.1119 + while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
3.1120 }
3.1121 }
3.1122 + operator Edge() const {
3.1123 +// Edge e;
3.1124 +// e.forward=this->forward;
3.1125 +// if (this->forward) e=out; else e=in;
3.1126 +// return e;
3.1127 + if (this->forward)
3.1128 + return Edge(out, this->forward);
3.1129 + else
3.1130 + return Edge(in, this->forward);
3.1131 + }
3.1132 + };
3.1133 +// class OutEdgeIt : public Edge {
3.1134 +// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.1135 +// public:
3.1136 +// OutEdgeIt() { }
3.1137 +// //FIXME
3.1138 +// OutEdgeIt(const Edge& e) : Edge(e) { }
3.1139 +// OutEdgeIt(const Invalid& i) : Edge(i) { }
3.1140 +// OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
3.1141 +// resG.graph->first(out, v);
3.1142 +// while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
3.1143 +// if (!resG.graph->valid(out)) {
3.1144 +// out_or_in=0;
3.1145 +// resG.graph->first(in, v);
3.1146 +// while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
3.1147 +// }
3.1148 +// }
3.1149 // public:
3.1150 // OutEdgeIt& operator++() {
3.1151 // if (out_or_in) {
3.1152 @@ -1049,39 +1221,95 @@
3.1153 // }
3.1154 // return *this;
3.1155 // }
3.1156 - };
3.1157 +// };
3.1158
3.1159 //FIXME This is just for having InEdgeIt
3.1160 // class InEdgeIt : public Edge { };
3.1161
3.1162 - class EdgeIt : public Edge {
3.1163 + class InEdgeIt {
3.1164 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.1165 - NodeIt v;
3.1166 + protected:
3.1167 + typename Graph::OutEdgeIt out;
3.1168 + typename Graph::InEdgeIt in;
3.1169 + bool forward;
3.1170 + public:
3.1171 + InEdgeIt() { }
3.1172 + //FIXME
3.1173 +// OutEdgeIt(const Edge& e) : Edge(e) { }
3.1174 + InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { }
3.1175 +//the unique invalid iterator
3.1176 + InEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) {
3.1177 + forward=true;
3.1178 + resG.graph->first(in, v);
3.1179 + while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
3.1180 + if (!resG.graph->valid(in)) {
3.1181 + forward=false;
3.1182 + resG.graph->first(out, v);
3.1183 + while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
3.1184 + }
3.1185 + }
3.1186 + operator Edge() const {
3.1187 +// Edge e;
3.1188 +// e.forward=this->forward;
3.1189 +// if (this->forward) e=out; else e=in;
3.1190 +// return e;
3.1191 + if (this->forward)
3.1192 + return Edge(in, this->forward);
3.1193 + else
3.1194 + return Edge(out, this->forward);
3.1195 + }
3.1196 + };
3.1197 +
3.1198 + class EdgeIt {
3.1199 + friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.1200 + protected:
3.1201 + typename Graph::EdgeIt e;
3.1202 + bool forward;
3.1203 public:
3.1204 EdgeIt() { }
3.1205 - //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
3.1206 - EdgeIt(const Invalid& i) : Edge(i) { }
3.1207 - EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
3.1208 - resG.graph->first(v);
3.1209 - if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
3.1210 - while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
3.1211 - while (resG.graph->valid(v) && !resG.graph->valid(out)) {
3.1212 - resG.graph->next(v);
3.1213 - if (resG.graph->valid(v)) resG.graph->first(out, v);
3.1214 - while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
3.1215 - }
3.1216 - if (!resG.graph->valid(out)) {
3.1217 - out_or_in=0;
3.1218 - resG.graph->first(v);
3.1219 - if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
3.1220 - while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
3.1221 - while (resG.graph->valid(v) && !resG.graph->valid(in)) {
3.1222 - resG.graph->next(v);
3.1223 - if (resG.graph->valid(v)) resG.graph->first(in, v);
3.1224 - while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
3.1225 - }
3.1226 + EdgeIt(const Invalid& i) : e(i), forward(false) { }
3.1227 + EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) {
3.1228 + forward=true;
3.1229 + resG.graph->first(e);
3.1230 + while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
3.1231 + if (!resG.graph->valid(e)) {
3.1232 + forward=false;
3.1233 + resG.graph->first(e);
3.1234 + while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
3.1235 }
3.1236 }
3.1237 + operator Edge() const {
3.1238 + return Edge(e, this->forward);
3.1239 + }
3.1240 + };
3.1241 +// class EdgeIt : public Edge {
3.1242 +// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.1243 +// NodeIt v;
3.1244 +// public:
3.1245 +// EdgeIt() { }
3.1246 +// //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
3.1247 +// EdgeIt(const Invalid& i) : Edge(i) { }
3.1248 +// EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
3.1249 +// resG.graph->first(v);
3.1250 +// if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
3.1251 +// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
3.1252 +// while (resG.graph->valid(v) && !resG.graph->valid(out)) {
3.1253 +// resG.graph->next(v);
3.1254 +// if (resG.graph->valid(v)) resG.graph->first(out, v);
3.1255 +// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
3.1256 +// }
3.1257 +// if (!resG.graph->valid(out)) {
3.1258 +// out_or_in=0;
3.1259 +// resG.graph->first(v);
3.1260 +// if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
3.1261 +// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
3.1262 +// while (resG.graph->valid(v) && !resG.graph->valid(in)) {
3.1263 +// resG.graph->next(v);
3.1264 +// if (resG.graph->valid(v)) resG.graph->first(in, v);
3.1265 +// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
3.1266 +// }
3.1267 +// }
3.1268 +// }
3.1269 // EdgeIt& operator++() {
3.1270 // if (out_or_in) {
3.1271 // ++out;
3.1272 @@ -1113,78 +1341,102 @@
3.1273 // }
3.1274 // return *this;
3.1275 // }
3.1276 - };
3.1277 +// };
3.1278
3.1279 NodeIt& first(NodeIt& i) const {
3.1280 - i=NodeIt(*this);
3.1281 - return i;
3.1282 + i=NodeIt(*this); return i;
3.1283 }
3.1284 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
3.1285 - i=OutEdgeIt(*this, p);
3.1286 - return i;
3.1287 + i=OutEdgeIt(*this, p); return i;
3.1288 }
3.1289 - //FIXME Not yet implemented
3.1290 - //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
3.1291 - //i=InEdgeIt(*this, p);
3.1292 - // return i;
3.1293 - //}
3.1294 - EdgeIt& first(EdgeIt& e) const {
3.1295 - e=EdgeIt(*this);
3.1296 - return e;
3.1297 +// FIXME not tested
3.1298 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
3.1299 + i=InEdgeIt(*this, p); return i;
3.1300 + }
3.1301 + EdgeIt& first(EdgeIt& i) const {
3.1302 + i=EdgeIt(*this); return i;
3.1303 }
3.1304
3.1305 - NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
3.1306 + NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
3.1307 OutEdgeIt& next(OutEdgeIt& e) const {
3.1308 - if (e.out_or_in) {
3.1309 + if (e.forward) {
3.1310 Node v=graph->aNode(e.out);
3.1311 graph->next(e.out);
3.1312 - while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
3.1313 + while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
3.1314 if (!graph->valid(e.out)) {
3.1315 - e.out_or_in=0;
3.1316 + e.forward=false;
3.1317 graph->first(e.in, v);
3.1318 - while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1319 + while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
3.1320 }
3.1321 } else {
3.1322 graph->next(e.in);
3.1323 - while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1324 + while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
3.1325 }
3.1326 return e;
3.1327 }
3.1328 - //FIXME Not yet implemented
3.1329 - //InEdgeIt& next(InEdgeIt& e) const {
3.1330 - // return e;
3.1331 - //}
3.1332 - EdgeIt& next(EdgeIt& e) const {
3.1333 - if (e.out_or_in) {
3.1334 +// FIXME Not tested
3.1335 + InEdgeIt& next(InEdgeIt& e) const {
3.1336 + if (e.forward) {
3.1337 + Node v=graph->aNode(e.in);
3.1338 + graph->next(e.in);
3.1339 + while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); }
3.1340 + if (!graph->valid(e.in)) {
3.1341 + e.forward=false;
3.1342 + graph->first(e.out, v);
3.1343 + while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
3.1344 + }
3.1345 + } else {
3.1346 graph->next(e.out);
3.1347 - while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
3.1348 - while (graph->valid(e.v) && !graph->valid(e.out)) {
3.1349 - graph->next(e.v);
3.1350 - if (graph->valid(e.v)) graph->first(e.out, e.v);
3.1351 - while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
3.1352 - }
3.1353 - if (!graph->valid(e.out)) {
3.1354 - e.out_or_in=0;
3.1355 - graph->first(e.v);
3.1356 - if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
3.1357 - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1358 - while (graph->valid(e.v) && !graph->valid(e.in)) {
3.1359 - graph->next(e.v);
3.1360 - if (graph->valid(e.v)) graph->first(e.in, e.v);
3.1361 - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1362 - }
3.1363 - }
3.1364 - } else {
3.1365 - graph->next(e.in);
3.1366 - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1367 - while (graph->valid(e.v) && !graph->valid(e.in)) {
3.1368 - graph->next(e.v);
3.1369 - if (graph->valid(e.v)) graph->first(e.in, e.v);
3.1370 - while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1371 - }
3.1372 + while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); }
3.1373 + }
3.1374 + return e;
3.1375 + }
3.1376 + EdgeIt& next(EdgeIt& e) const {
3.1377 + if (e.forward) {
3.1378 + graph->next(e.e);
3.1379 + while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
3.1380 + if (!graph->valid(e.e)) {
3.1381 + e.forward=false;
3.1382 + graph->first(e.e);
3.1383 + while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
3.1384 }
3.1385 - return e;
3.1386 + } else {
3.1387 + graph->next(e.e);
3.1388 + while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); }
3.1389 }
3.1390 + return e;
3.1391 + }
3.1392 +// EdgeIt& next(EdgeIt& e) const {
3.1393 +// if (e.out_or_in) {
3.1394 +// graph->next(e.out);
3.1395 +// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
3.1396 +// while (graph->valid(e.v) && !graph->valid(e.out)) {
3.1397 +// graph->next(e.v);
3.1398 +// if (graph->valid(e.v)) graph->first(e.out, e.v);
3.1399 +// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
3.1400 +// }
3.1401 +// if (!graph->valid(e.out)) {
3.1402 +// e.out_or_in=0;
3.1403 +// graph->first(e.v);
3.1404 +// if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
3.1405 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1406 +// while (graph->valid(e.v) && !graph->valid(e.in)) {
3.1407 +// graph->next(e.v);
3.1408 +// if (graph->valid(e.v)) graph->first(e.in, e.v);
3.1409 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1410 +// }
3.1411 +// }
3.1412 +// } else {
3.1413 +// graph->next(e.in);
3.1414 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1415 +// while (graph->valid(e.v) && !graph->valid(e.in)) {
3.1416 +// graph->next(e.v);
3.1417 +// if (graph->valid(e.v)) graph->first(e.in, e.v);
3.1418 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1419 +// }
3.1420 +// }
3.1421 +// return e;
3.1422 +// }
3.1423
3.1424
3.1425 template< typename It >
3.1426 @@ -1202,53 +1454,55 @@
3.1427 }
3.1428
3.1429 Node tail(Edge e) const {
3.1430 - return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
3.1431 + return ((e.forward) ? graph->tail(e) : graph->head(e)); }
3.1432 Node head(Edge e) const {
3.1433 - return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
3.1434 + return ((e.forward) ? graph->head(e) : graph->tail(e)); }
3.1435
3.1436 Node aNode(OutEdgeIt e) const {
3.1437 - return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
3.1438 + return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); }
3.1439 Node bNode(OutEdgeIt e) const {
3.1440 - return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
3.1441 + return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); }
3.1442
3.1443 int nodeNum() const { return graph->nodeNum(); }
3.1444 //FIXME
3.1445 //int edgeNum() const { return graph->edgeNum(); }
3.1446
3.1447
3.1448 - int id(Node v) const { return graph->id(v); }
3.1449 +// int id(Node v) const { return graph->id(v); }
3.1450
3.1451 - bool valid(Node n) const { return graph->valid(n); }
3.1452 + bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
3.1453 bool valid(Edge e) const {
3.1454 - return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
3.1455 + return graph->valid(e);
3.1456 + //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
3.1457 + }
3.1458
3.1459 void augment(const Edge& e, Number a) const {
3.1460 - if (e.out_or_in)
3.1461 + if (e.forward)
3.1462 // flow->set(e.out, flow->get(e.out)+a);
3.1463 - flow->set(e.out, (*flow)[e.out]+a);
3.1464 + flow->set(e, (*flow)[e]+a);
3.1465 else
3.1466 // flow->set(e.in, flow->get(e.in)-a);
3.1467 - flow->set(e.in, (*flow)[e.in]-a);
3.1468 + flow->set(e, (*flow)[e]-a);
3.1469 }
3.1470
3.1471 Number resCap(const Edge& e) const {
3.1472 - if (e.out_or_in)
3.1473 + if (e.forward)
3.1474 // return (capacity->get(e.out)-flow->get(e.out));
3.1475 - return ((*capacity)[e.out]-(*flow)[e.out]);
3.1476 + return ((*capacity)[e]-(*flow)[e]);
3.1477 else
3.1478 // return (flow->get(e.in));
3.1479 - return ((*flow)[e.in]);
3.1480 + return ((*flow)[e]);
3.1481 }
3.1482
3.1483 - Number resCap(GraphOutEdgeIt out) const {
3.1484 -// return (capacity->get(out)-flow->get(out));
3.1485 - return ((*capacity)[out]-(*flow)[out]);
3.1486 - }
3.1487 +// Number resCap(typename Graph::OutEdgeIt out) const {
3.1488 +// // return (capacity->get(out)-flow->get(out));
3.1489 +// return ((*capacity)[out]-(*flow)[out]);
3.1490 +// }
3.1491
3.1492 - Number resCap(GraphInEdgeIt in) const {
3.1493 -// return (flow->get(in));
3.1494 - return ((*flow)[in]);
3.1495 - }
3.1496 +// Number resCap(typename Graph::InEdgeIt in) const {
3.1497 +// // return (flow->get(in));
3.1498 +// return ((*flow)[in]);
3.1499 +// }
3.1500
3.1501 // template<typename T> class NodeMap : public Graph::NodeMap<T> {
3.1502 // public:
3.1503 @@ -1275,13 +1529,13 @@
3.1504 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
3.1505 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
3.1506 void set(Edge e, T a) {
3.1507 - if (e.out_or_in)
3.1508 + if (e.forward)
3.1509 forward_map.set(e.out, a);
3.1510 else
3.1511 backward_map.set(e.in, a);
3.1512 }
3.1513 T operator[](Edge e) const {
3.1514 - if (e.out_or_in)
3.1515 + if (e.forward)
3.1516 return forward_map[e.out];
3.1517 else
3.1518 return backward_map[e.in];
3.1519 @@ -1295,6 +1549,336 @@
3.1520 };
3.1521 };
3.1522
3.1523 +
3.1524 +
3.1525 +// template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
3.1526 +// class ResGraphWrapper : public GraphWrapper<Graph> {
3.1527 +// protected:
3.1528 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
3.1529 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
3.1530 +// typedef typename Graph::Edge GraphEdge;
3.1531 +// FlowMap* flow;
3.1532 +// const CapacityMap* capacity;
3.1533 +// public:
3.1534 +
3.1535 +// ResGraphWrapper(Graph& _graph, FlowMap& _flow,
3.1536 +// const CapacityMap& _capacity) :
3.1537 +// GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { }
3.1538 +
3.1539 +// class Edge;
3.1540 +// class OutEdgeIt;
3.1541 +// friend class Edge;
3.1542 +// friend class OutEdgeIt;
3.1543 +
3.1544 +// typedef typename GraphWrapper<Graph>::Node Node;
3.1545 +// typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
3.1546 +// class Edge {
3.1547 +// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.1548 +// protected:
3.1549 +// bool out_or_in; //true, iff out
3.1550 +// GraphOutEdgeIt out;
3.1551 +// GraphInEdgeIt in;
3.1552 +// public:
3.1553 +// Edge() : out_or_in(true) { }
3.1554 +// Edge(const Invalid& i) : out_or_in(false), out(), in(i) { }
3.1555 +// // bool valid() const {
3.1556 +// // return out_or_in && out.valid() || in.valid(); }
3.1557 +// friend bool operator==(const Edge& u, const Edge& v) {
3.1558 +// if (v.out_or_in)
3.1559 +// return (u.out_or_in && u.out==v.out);
3.1560 +// else
3.1561 +// return (!u.out_or_in && u.in==v.in);
3.1562 +// }
3.1563 +// friend bool operator!=(const Edge& u, const Edge& v) {
3.1564 +// if (v.out_or_in)
3.1565 +// return (!u.out_or_in || u.out!=v.out);
3.1566 +// else
3.1567 +// return (u.out_or_in || u.in!=v.in);
3.1568 +// }
3.1569 +// operator GraphEdge() const {
3.1570 +// if (out_or_in) return(out); else return(in);
3.1571 +// }
3.1572 +// };
3.1573 +// class OutEdgeIt : public Edge {
3.1574 +// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.1575 +// public:
3.1576 +// OutEdgeIt() { }
3.1577 +// //FIXME
3.1578 +// OutEdgeIt(const Edge& e) : Edge(e) { }
3.1579 +// OutEdgeIt(const Invalid& i) : Edge(i) { }
3.1580 +// OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
3.1581 +// resG.graph->first(out, v);
3.1582 +// while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
3.1583 +// if (!resG.graph->valid(out)) {
3.1584 +// out_or_in=0;
3.1585 +// resG.graph->first(in, v);
3.1586 +// while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
3.1587 +// }
3.1588 +// }
3.1589 +// // public:
3.1590 +// // OutEdgeIt& operator++() {
3.1591 +// // if (out_or_in) {
3.1592 +// // Node v=/*resG->*/G->aNode(out);
3.1593 +// // ++out;
3.1594 +// // while( out.valid() && !(Edge::resCap()>0) ) { ++out; }
3.1595 +// // if (!out.valid()) {
3.1596 +// // out_or_in=0;
3.1597 +// // G->first(in, v);
3.1598 +// // while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
3.1599 +// // }
3.1600 +// // } else {
3.1601 +// // ++in;
3.1602 +// // while( in.valid() && !(Edge::resCap()>0) ) { ++in; }
3.1603 +// // }
3.1604 +// // return *this;
3.1605 +// // }
3.1606 +// };
3.1607 +
3.1608 +// //FIXME This is just for having InEdgeIt
3.1609 +// // class InEdgeIt : public Edge { };
3.1610 +
3.1611 +// class EdgeIt : public Edge {
3.1612 +// friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
3.1613 +// NodeIt v;
3.1614 +// public:
3.1615 +// EdgeIt() { }
3.1616 +// //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { }
3.1617 +// EdgeIt(const Invalid& i) : Edge(i) { }
3.1618 +// EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
3.1619 +// resG.graph->first(v);
3.1620 +// if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID;
3.1621 +// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
3.1622 +// while (resG.graph->valid(v) && !resG.graph->valid(out)) {
3.1623 +// resG.graph->next(v);
3.1624 +// if (resG.graph->valid(v)) resG.graph->first(out, v);
3.1625 +// while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); }
3.1626 +// }
3.1627 +// if (!resG.graph->valid(out)) {
3.1628 +// out_or_in=0;
3.1629 +// resG.graph->first(v);
3.1630 +// if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID;
3.1631 +// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
3.1632 +// while (resG.graph->valid(v) && !resG.graph->valid(in)) {
3.1633 +// resG.graph->next(v);
3.1634 +// if (resG.graph->valid(v)) resG.graph->first(in, v);
3.1635 +// while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); }
3.1636 +// }
3.1637 +// }
3.1638 +// }
3.1639 +// // EdgeIt& operator++() {
3.1640 +// // if (out_or_in) {
3.1641 +// // ++out;
3.1642 +// // while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
3.1643 +// // while (v.valid() && !out.valid()) {
3.1644 +// // ++v;
3.1645 +// // if (v.valid()) G->first(out, v);
3.1646 +// // while (out.valid() && !(Edge::resCap()>0) ) { ++out; }
3.1647 +// // }
3.1648 +// // if (!out.valid()) {
3.1649 +// // out_or_in=0;
3.1650 +// // G->first(v);
3.1651 +// // if (v.valid()) G->first(in, v); else in=GraphInEdgeIt();
3.1652 +// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
3.1653 +// // while (v.valid() && !in.valid()) {
3.1654 +// // ++v;
3.1655 +// // if (v.valid()) G->first(in, v);
3.1656 +// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
3.1657 +// // }
3.1658 +// // }
3.1659 +// // } else {
3.1660 +// // ++in;
3.1661 +// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
3.1662 +// // while (v.valid() && !in.valid()) {
3.1663 +// // ++v;
3.1664 +// // if (v.valid()) G->first(in, v);
3.1665 +// // while (in.valid() && !(Edge::resCap()>0) ) { ++in; }
3.1666 +// // }
3.1667 +// // }
3.1668 +// // return *this;
3.1669 +// // }
3.1670 +// };
3.1671 +
3.1672 +// NodeIt& first(NodeIt& i) const {
3.1673 +// i=NodeIt(*this);
3.1674 +// return i;
3.1675 +// }
3.1676 +// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
3.1677 +// i=OutEdgeIt(*this, p);
3.1678 +// return i;
3.1679 +// }
3.1680 +// //FIXME Not yet implemented
3.1681 +// //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
3.1682 +// //i=InEdgeIt(*this, p);
3.1683 +// // return i;
3.1684 +// //}
3.1685 +// EdgeIt& first(EdgeIt& e) const {
3.1686 +// e=EdgeIt(*this);
3.1687 +// return e;
3.1688 +// }
3.1689 +
3.1690 +// NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
3.1691 +// OutEdgeIt& next(OutEdgeIt& e) const {
3.1692 +// if (e.out_or_in) {
3.1693 +// Node v=graph->aNode(e.out);
3.1694 +// graph->next(e.out);
3.1695 +// while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
3.1696 +// if (!graph->valid(e.out)) {
3.1697 +// e.out_or_in=0;
3.1698 +// graph->first(e.in, v);
3.1699 +// while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1700 +// }
3.1701 +// } else {
3.1702 +// graph->next(e.in);
3.1703 +// while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1704 +// }
3.1705 +// return e;
3.1706 +// }
3.1707 +// //FIXME Not yet implemented
3.1708 +// //InEdgeIt& next(InEdgeIt& e) const {
3.1709 +// // return e;
3.1710 +// //}
3.1711 +// EdgeIt& next(EdgeIt& e) const {
3.1712 +// if (e.out_or_in) {
3.1713 +// graph->next(e.out);
3.1714 +// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
3.1715 +// while (graph->valid(e.v) && !graph->valid(e.out)) {
3.1716 +// graph->next(e.v);
3.1717 +// if (graph->valid(e.v)) graph->first(e.out, e.v);
3.1718 +// while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); }
3.1719 +// }
3.1720 +// if (!graph->valid(e.out)) {
3.1721 +// e.out_or_in=0;
3.1722 +// graph->first(e.v);
3.1723 +// if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID;
3.1724 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1725 +// while (graph->valid(e.v) && !graph->valid(e.in)) {
3.1726 +// graph->next(e.v);
3.1727 +// if (graph->valid(e.v)) graph->first(e.in, e.v);
3.1728 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1729 +// }
3.1730 +// }
3.1731 +// } else {
3.1732 +// graph->next(e.in);
3.1733 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1734 +// while (graph->valid(e.v) && !graph->valid(e.in)) {
3.1735 +// graph->next(e.v);
3.1736 +// if (graph->valid(e.v)) graph->first(e.in, e.v);
3.1737 +// while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); }
3.1738 +// }
3.1739 +// }
3.1740 +// return e;
3.1741 +// }
3.1742 +
3.1743 +
3.1744 +// template< typename It >
3.1745 +// It first() const {
3.1746 +// It e;
3.1747 +// first(e);
3.1748 +// return e;
3.1749 +// }
3.1750 +
3.1751 +// template< typename It >
3.1752 +// It first(Node v) const {
3.1753 +// It e;
3.1754 +// first(e, v);
3.1755 +// return e;
3.1756 +// }
3.1757 +
3.1758 +// Node tail(Edge e) const {
3.1759 +// return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
3.1760 +// Node head(Edge e) const {
3.1761 +// return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
3.1762 +
3.1763 +// Node aNode(OutEdgeIt e) const {
3.1764 +// return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }
3.1765 +// Node bNode(OutEdgeIt e) const {
3.1766 +// return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }
3.1767 +
3.1768 +// int nodeNum() const { return graph->nodeNum(); }
3.1769 +// //FIXME
3.1770 +// //int edgeNum() const { return graph->edgeNum(); }
3.1771 +
3.1772 +
3.1773 +// int id(Node v) const { return graph->id(v); }
3.1774 +
3.1775 +// bool valid(Node n) const { return graph->valid(n); }
3.1776 +// bool valid(Edge e) const {
3.1777 +// return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); }
3.1778 +
3.1779 +// void augment(const Edge& e, Number a) const {
3.1780 +// if (e.out_or_in)
3.1781 +// // flow->set(e.out, flow->get(e.out)+a);
3.1782 +// flow->set(e.out, (*flow)[e.out]+a);
3.1783 +// else
3.1784 +// // flow->set(e.in, flow->get(e.in)-a);
3.1785 +// flow->set(e.in, (*flow)[e.in]-a);
3.1786 +// }
3.1787 +
3.1788 +// Number resCap(const Edge& e) const {
3.1789 +// if (e.out_or_in)
3.1790 +// // return (capacity->get(e.out)-flow->get(e.out));
3.1791 +// return ((*capacity)[e.out]-(*flow)[e.out]);
3.1792 +// else
3.1793 +// // return (flow->get(e.in));
3.1794 +// return ((*flow)[e.in]);
3.1795 +// }
3.1796 +
3.1797 +// Number resCap(GraphOutEdgeIt out) const {
3.1798 +// // return (capacity->get(out)-flow->get(out));
3.1799 +// return ((*capacity)[out]-(*flow)[out]);
3.1800 +// }
3.1801 +
3.1802 +// Number resCap(GraphInEdgeIt in) const {
3.1803 +// // return (flow->get(in));
3.1804 +// return ((*flow)[in]);
3.1805 +// }
3.1806 +
3.1807 +// // template<typename T> class NodeMap : public Graph::NodeMap<T> {
3.1808 +// // public:
3.1809 +// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
3.1810 +// // : Graph::NodeMap<T>(_G.gw) { }
3.1811 +// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
3.1812 +// // T a) : Graph::NodeMap<T>(_G.gw, a) { }
3.1813 +// // };
3.1814 +
3.1815 +// // template <typename T>
3.1816 +// // class NodeMap {
3.1817 +// // typename Graph::NodeMap<T> node_map;
3.1818 +// // public:
3.1819 +// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { }
3.1820 +// // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { }
3.1821 +// // void set(Node nit, T a) { node_map.set(nit, a); }
3.1822 +// // T get(Node nit) const { return node_map.get(nit); }
3.1823 +// // };
3.1824 +
3.1825 +// template <typename T>
3.1826 +// class EdgeMap {
3.1827 +// typename Graph::EdgeMap<T> forward_map, backward_map;
3.1828 +// public:
3.1829 +// EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
3.1830 +// EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
3.1831 +// void set(Edge e, T a) {
3.1832 +// if (e.out_or_in)
3.1833 +// forward_map.set(e.out, a);
3.1834 +// else
3.1835 +// backward_map.set(e.in, a);
3.1836 +// }
3.1837 +// T operator[](Edge e) const {
3.1838 +// if (e.out_or_in)
3.1839 +// return forward_map[e.out];
3.1840 +// else
3.1841 +// return backward_map[e.in];
3.1842 +// }
3.1843 +// // T get(Edge e) const {
3.1844 +// // if (e.out_or_in)
3.1845 +// // return forward_map.get(e.out);
3.1846 +// // else
3.1847 +// // return backward_map.get(e.in);
3.1848 +// // }
3.1849 +// };
3.1850 +// };
3.1851 +
3.1852 +
3.1853 //ErasingFirstGraphWrapper for blocking flows
3.1854 template<typename Graph, typename FirstOutEdgesMap>
3.1855 class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
3.1856 @@ -1305,60 +1889,74 @@
3.1857 FirstOutEdgesMap& _first_out_edges) :
3.1858 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
3.1859
3.1860 - typedef typename Graph::Node Node;
3.1861 - class NodeIt : public Graph::NodeIt {
3.1862 - public:
3.1863 + typedef typename GraphWrapper<Graph>::Node Node;
3.1864 + class NodeIt {
3.1865 + friend class GraphWrapper<Graph>;
3.1866 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
3.1867 + typename Graph::NodeIt n;
3.1868 + public:
3.1869 NodeIt() { }
3.1870 - NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
3.1871 - NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
3.1872 + NodeIt(const typename Graph::NodeIt& _n) : n(_n) { }
3.1873 + NodeIt(const Invalid& i) : n(i) { }
3.1874 NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
3.1875 - Graph::NodeIt(*(_G.graph)) { }
3.1876 + n(*(_G.graph)) { }
3.1877 + operator Node() const { return Node(typename Graph::Node(n)); }
3.1878 };
3.1879 - typedef typename Graph::Edge Edge;
3.1880 - class OutEdgeIt : public Graph::OutEdgeIt {
3.1881 + typedef typename GraphWrapper<Graph>::Edge Edge;
3.1882 + class OutEdgeIt {
3.1883 + friend class GraphWrapper<Graph>;
3.1884 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
3.1885 +// typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
3.1886 + typename Graph::OutEdgeIt e;
3.1887 public:
3.1888 OutEdgeIt() { }
3.1889 - OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
3.1890 - OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
3.1891 + OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { }
3.1892 + OutEdgeIt(const Invalid& i) : e(i) { }
3.1893 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
3.1894 - const Node& n) :
3.1895 - Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
3.1896 + const Node& _n) :
3.1897 + e((*_G.first_out_edges)[_n]) { }
3.1898 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
3.1899 };
3.1900 - class InEdgeIt : public Graph::InEdgeIt {
3.1901 + class InEdgeIt {
3.1902 + friend class GraphWrapper<Graph>;
3.1903 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
3.1904 +// typedef typename Graph::InEdgeIt GraphInEdgeIt;
3.1905 + typename Graph::InEdgeIt e;
3.1906 public:
3.1907 InEdgeIt() { }
3.1908 - InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
3.1909 - InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
3.1910 + InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
3.1911 + InEdgeIt(const Invalid& i) : e(i) { }
3.1912 InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
3.1913 - const Node& n) :
3.1914 - Graph::InEdgeIt(*(_G.graph), n) { }
3.1915 + const Node& _n) :
3.1916 + e(*(_G.graph), typename Graph::Node(_n)) { }
3.1917 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
3.1918 };
3.1919 //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.1920 - class EdgeIt : public Graph::EdgeIt {
3.1921 + class EdgeIt {
3.1922 + friend class GraphWrapper<Graph>;
3.1923 + friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
3.1924 +// typedef typename Graph::EdgeIt GraphEdgeIt;
3.1925 + typename Graph::EdgeIt e;
3.1926 public:
3.1927 EdgeIt() { }
3.1928 - EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
3.1929 - EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
3.1930 + EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
3.1931 + EdgeIt(const Invalid& i) : e(i) { }
3.1932 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
3.1933 - Graph::EdgeIt(*(_G.graph)) { }
3.1934 + e(*(_G.graph)) { }
3.1935 + operator Edge() const { return Edge(typename Graph::Edge(e)); }
3.1936 };
3.1937
3.1938 - NodeIt& first(NodeIt& i) const {
3.1939 - i=NodeIt(*this);
3.1940 - return i;
3.1941 + NodeIt& first(NodeIt& i) const {
3.1942 + i=NodeIt(*this); return i;
3.1943 }
3.1944 - OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
3.1945 - i=OutEdgeIt(*this, n);
3.1946 -// i=(*first_out_edges)[n];
3.1947 - return i;
3.1948 + OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
3.1949 + i=OutEdgeIt(*this, p); return i;
3.1950 }
3.1951 - InEdgeIt& first(InEdgeIt& i, const Node& n) const {
3.1952 - i=InEdgeIt(*this, n);
3.1953 - return i;
3.1954 + InEdgeIt& first(InEdgeIt& i, const Node& p) const {
3.1955 + i=InEdgeIt(*this, p); return i;
3.1956 }
3.1957 - EdgeIt& first(EdgeIt& i) const {
3.1958 - i=EdgeIt(*this);
3.1959 - return i;
3.1960 + EdgeIt& first(EdgeIt& i) const {
3.1961 + i=EdgeIt(*this); return i;
3.1962 }
3.1963
3.1964 // template<typename I> I& first(I& i) const {
3.1965 @@ -1380,22 +1978,15 @@
3.1966 //}
3.1967
3.1968
3.1969 - NodeIt& next(NodeIt& i) const {
3.1970 - graph->next(i);
3.1971 - return i;
3.1972 - }
3.1973 - OutEdgeIt& next(OutEdgeIt& i) const {
3.1974 - graph->next(i);
3.1975 - return i;
3.1976 - }
3.1977 - InEdgeIt& next(InEdgeIt& i) const {
3.1978 - graph->next(i);
3.1979 - return i;
3.1980 - }
3.1981 - EdgeIt& next(EdgeIt& i) const {
3.1982 - graph->next(i);
3.1983 - return i;
3.1984 - }
3.1985 + NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
3.1986 + OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
3.1987 + InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
3.1988 + EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }
3.1989 +
3.1990 + Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
3.1991 + Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
3.1992 + Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
3.1993 + Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
3.1994
3.1995 // template<typename I> I& next(I &i) const {
3.1996 // graph->next(i);
3.1997 @@ -1411,10 +2002,131 @@
3.1998 void erase(const OutEdgeIt& e) const {
3.1999 OutEdgeIt f=e;
3.2000 this->next(f);
3.2001 - first_out_edges->set(this->tail(e), f);
3.2002 + first_out_edges->set(this->tail(e), f.e);
3.2003 }
3.2004 };
3.2005
3.2006 +// //ErasingFirstGraphWrapper for blocking flows
3.2007 +// template<typename Graph, typename FirstOutEdgesMap>
3.2008 +// class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
3.2009 +// protected:
3.2010 +// FirstOutEdgesMap* first_out_edges;
3.2011 +// public:
3.2012 +// ErasingFirstGraphWrapper(Graph& _graph,
3.2013 +// FirstOutEdgesMap& _first_out_edges) :
3.2014 +// GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
3.2015 +
3.2016 +// typedef typename Graph::Node Node;
3.2017 +// class NodeIt : public Graph::NodeIt {
3.2018 +// public:
3.2019 +// NodeIt() { }
3.2020 +// NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
3.2021 +// NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
3.2022 +// NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
3.2023 +// Graph::NodeIt(*(_G.graph)) { }
3.2024 +// };
3.2025 +// typedef typename Graph::Edge Edge;
3.2026 +// class OutEdgeIt : public Graph::OutEdgeIt {
3.2027 +// public:
3.2028 +// OutEdgeIt() { }
3.2029 +// OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
3.2030 +// OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
3.2031 +// OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
3.2032 +// const Node& n) :
3.2033 +// Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
3.2034 +// };
3.2035 +// class InEdgeIt : public Graph::InEdgeIt {
3.2036 +// public:
3.2037 +// InEdgeIt() { }
3.2038 +// InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
3.2039 +// InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
3.2040 +// InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
3.2041 +// const Node& n) :
3.2042 +// Graph::InEdgeIt(*(_G.graph), n) { }
3.2043 +// };
3.2044 +// //typedef typename Graph::SymEdgeIt SymEdgeIt;
3.2045 +// class EdgeIt : public Graph::EdgeIt {
3.2046 +// public:
3.2047 +// EdgeIt() { }
3.2048 +// EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
3.2049 +// EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
3.2050 +// EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
3.2051 +// Graph::EdgeIt(*(_G.graph)) { }
3.2052 +// };
3.2053 +
3.2054 +// NodeIt& first(NodeIt& i) const {
3.2055 +// i=NodeIt(*this);
3.2056 +// return i;
3.2057 +// }
3.2058 +// OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
3.2059 +// i=OutEdgeIt(*this, n);
3.2060 +// // i=(*first_out_edges)[n];
3.2061 +// return i;
3.2062 +// }
3.2063 +// InEdgeIt& first(InEdgeIt& i, const Node& n) const {
3.2064 +// i=InEdgeIt(*this, n);
3.2065 +// return i;
3.2066 +// }
3.2067 +// EdgeIt& first(EdgeIt& i) const {
3.2068 +// i=EdgeIt(*this);
3.2069 +// return i;
3.2070 +// }
3.2071 +
3.2072 +// // template<typename I> I& first(I& i) const {
3.2073 +// // graph->first(i);
3.2074 +// // return i;
3.2075 +// // }
3.2076 +// // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
3.2077 +// // // e=first_out_edges->get(n);
3.2078 +// // e=(*first_out_edges)[n];
3.2079 +// // return e;
3.2080 +// // }
3.2081 +// // template<typename I, typename P> I& first(I& i, const P& p) const {
3.2082 +// // graph->first(i, p);
3.2083 +// // return i;
3.2084 +// // }
3.2085 +
3.2086 +// //template<typename I> I getNext(const I& i) const {
3.2087 +// // return gw.getNext(i);
3.2088 +// //}
3.2089 +
3.2090 +
3.2091 +// NodeIt& next(NodeIt& i) const {
3.2092 +// graph->next(i);
3.2093 +// return i;
3.2094 +// }
3.2095 +// OutEdgeIt& next(OutEdgeIt& i) const {
3.2096 +// graph->next(i);
3.2097 +// return i;
3.2098 +// }
3.2099 +// InEdgeIt& next(InEdgeIt& i) const {
3.2100 +// graph->next(i);
3.2101 +// return i;
3.2102 +// }
3.2103 +// EdgeIt& next(EdgeIt& i) const {
3.2104 +// graph->next(i);
3.2105 +// return i;
3.2106 +// }
3.2107 +
3.2108 +// // template<typename I> I& next(I &i) const {
3.2109 +// // graph->next(i);
3.2110 +// // return i;
3.2111 +// // }
3.2112 +
3.2113 +// template< typename It > It first() const {
3.2114 +// It e; this->first(e); return e; }
3.2115 +
3.2116 +// template< typename It > It first(const Node& v) const {
3.2117 +// It e; this->first(e, v); return e; }
3.2118 +
3.2119 +// void erase(const OutEdgeIt& e) const {
3.2120 +// OutEdgeIt f=e;
3.2121 +// this->next(f);
3.2122 +// first_out_edges->set(this->tail(e), f);
3.2123 +// }
3.2124 +// };
3.2125 +
3.2126 +
3.2127 // // FIXME: comparison should be made better!!!
3.2128 // template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
3.2129 // class ResGraphWrapper
4.1 --- a/src/work/marci/iterator_bfs_demo.cc Thu Apr 08 13:11:58 2004 +0000
4.2 +++ b/src/work/marci/iterator_bfs_demo.cc Tue Apr 13 20:35:47 2004 +0000
4.3 @@ -168,7 +168,7 @@
4.4
4.5 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
4.6 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
4.7 - cout << node_name[n] << ": ";
4.8 + cout << node_name[GW::Node(n)] << ": ";
4.9 cout << "out edges: ";
4.10 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
4.11 cout << edge_name[e] << " ";
4.12 @@ -183,8 +183,8 @@
4.13 bfs.pushAndSetReached(t);
4.14 while (!bfs.finished()) {
4.15 //cout << "edge: ";
4.16 - if (gw.valid(bfs)) {
4.17 - cout << edge_name[bfs] << /*endl*/", " <<
4.18 + if (gw.valid(GW::OutEdgeIt(bfs))) {
4.19 + cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<
4.20 node_name[gw.aNode(bfs)] <<
4.21 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
4.22 node_name[gw.bNode(bfs)] <<
4.23 @@ -217,8 +217,8 @@
4.24 while (!dfs.finished()) {
4.25 ++dfs;
4.26 //cout << "edge: ";
4.27 - if (gw.valid(dfs)) {
4.28 - cout << edge_name[dfs] << /*endl*/", " <<
4.29 + if (gw.valid(GW::OutEdgeIt(dfs))) {
4.30 + cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<
4.31 node_name[gw.aNode(dfs)] <<
4.32 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
4.33 node_name[gw.bNode(dfs)] <<
4.34 @@ -236,7 +236,6 @@
4.35 }
4.36
4.37 {
4.38 - //typedef UndirGraphWrapper<const Graph> GW;
4.39 typedef UndirGraphWrapper<const Graph> GW;
4.40 GW gw(G);
4.41
4.42 @@ -244,7 +243,7 @@
4.43
4.44 cout << "bfs and dfs iterator demo on the undirected graph" << endl;
4.45 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
4.46 - cout << node_name[n] << ": ";
4.47 + cout << node_name[GW::Node(n)] << ": ";
4.48 cout << "out edges: ";
4.49 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
4.50 cout << edge_name[e] << " ";
5.1 --- a/src/work/marci/makefile Thu Apr 08 13:11:58 2004 +0000
5.2 +++ b/src/work/marci/makefile Tue Apr 13 20:35:47 2004 +0000
5.3 @@ -9,7 +9,7 @@
5.4 BOOSTROOT ?= /home/marci/boost
5.5 INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
5.6 LEDAINCLUDE ?= -I$(LEDAROOT)/incl
5.7 -CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) #-ansi -pedantic
5.8 +CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30
5.9
5.10 LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
5.11 BINARIES = edmonds_karp_demo iterator_bfs_demo