Changeset 317:6e6db1c49bc1 in lemon-0.x for src/work/marci/graph_wrapper.h
- Timestamp:
- 04/13/04 22:35:47 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@435
- File:
-
- 1 edited
-
src/work/marci/graph_wrapper.h (modified) (24 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/graph_wrapper.h
r312 r317 6 6 7 7 namespace hugo { 8 9 // template<typename Graph>10 // class TrivGraphWrapper {11 // protected:12 // Graph* graph;13 14 // public:15 // // typedef Graph BaseGraph;16 // typedef Graph ParentGraph;17 18 // // TrivGraphWrapper() : graph(0) { }19 // TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }20 // // void setGraph(Graph& _graph) { graph = &_graph; }21 // // Graph& getGraph() const { return *graph; }22 23 // typedef typename Graph::Node Node;24 // class NodeIt : public Graph::NodeIt {25 // public:26 // NodeIt() { }27 // NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }28 // NodeIt(const Invalid& i) : Graph::NodeIt(i) { }29 // NodeIt(const TrivGraphWrapper<Graph>& _G) :30 // Graph::NodeIt(*(_G.graph)) { }31 // };32 // typedef typename Graph::Edge Edge;33 // class OutEdgeIt : public Graph::OutEdgeIt {34 // public:35 // OutEdgeIt() { }36 // OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }37 // OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }38 // OutEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :39 // Graph::OutEdgeIt(*(_G.graph), n) { }40 // };41 // class InEdgeIt : public Graph::InEdgeIt {42 // public:43 // InEdgeIt() { }44 // InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }45 // InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }46 // InEdgeIt(const TrivGraphWrapper<Graph>& _G, const Node& n) :47 // Graph::InEdgeIt(*(_G.graph), n) { }48 // };49 // //typedef typename Graph::SymEdgeIt SymEdgeIt;50 // class EdgeIt : public Graph::EdgeIt {51 // public:52 // EdgeIt() { }53 // EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }54 // EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }55 // EdgeIt(const TrivGraphWrapper<Graph>& _G) :56 // Graph::EdgeIt(*(_G.graph)) { }57 // };58 59 // NodeIt& first(NodeIt& i) const {60 // i=NodeIt(*this);61 // return i;62 // }63 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {64 // i=OutEdgeIt(*this, p);65 // return i;66 // }67 // InEdgeIt& first(InEdgeIt& i, const Node& p) const {68 // i=InEdgeIt(*this, p);69 // return i;70 // }71 // EdgeIt& first(EdgeIt& i) const {72 // i=EdgeIt(*this);73 // return i;74 // }75 // // template<typename I> I& first(I& i) const {76 // // i=I(*this);77 // // return i;78 // // }79 // // template<typename I, typename P> I& first(I& i, const P& p) const {80 // // i=I(*this, p);81 // // return i;82 // // }83 84 // // template<typename I> I getNext(const I& i) const {85 // // return graph->getNext(i); }86 87 // NodeIt& next(NodeIt& i) const { graph->next(i); return i; }88 // OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }89 // InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }90 // EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }91 // // template<typename I> I& next(I &i) const { graph->next(i); return i; }92 // template< typename It > It first() const {93 // It e; this->first(e); return e; }94 95 // template< typename It > It first(const Node& v) const {96 // It e; this->first(e, v); return e; }97 98 // Node head(const Edge& e) const { return graph->head(e); }99 // Node tail(const Edge& e) const { return graph->tail(e); }100 101 // template<typename I> bool valid(const I& i) const {102 // return graph->valid(i); }103 104 // //template<typename I> void setInvalid(const I &i);105 // //{ return graph->setInvalid(i); }106 107 // int nodeNum() const { return graph->nodeNum(); }108 // int edgeNum() const { return graph->edgeNum(); }109 110 // template<typename I> Node aNode(const I& e) const {111 // return graph->aNode(e); }112 // template<typename I> Node bNode(const I& e) const {113 // return graph->bNode(e); }114 115 // Node addNode() const { return graph->addNode(); }116 // Edge addEdge(const Node& tail, const Node& head) const {117 // return graph->addEdge(tail, head); }118 119 // template<typename I> void erase(const I& i) const { graph->erase(i); }120 121 // void clear() const { graph->clear(); }122 123 // template<typename T> class NodeMap : public Graph::NodeMap<T> {124 // public:125 // NodeMap(const TrivGraphWrapper<Graph>& _G) :126 // Graph::NodeMap<T>(*(_G.graph)) { }127 // NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :128 // Graph::NodeMap<T>(*(_G.graph), a) { }129 // };130 131 // template<typename T> class EdgeMap : public Graph::EdgeMap<T> {132 // public:133 // EdgeMap(const TrivGraphWrapper<Graph>& _G) :134 // Graph::EdgeMap<T>(*(_G.graph)) { }135 // EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :136 // Graph::EdgeMap<T>(*(_G.graph), a) { }137 // };138 139 // // template<typename Map, typename T> class NodeMapWrapper {140 // // protected:141 // // Map* map;142 // // public:143 // // NodeMapWrapper(Map& _map) : map(&_map) { }144 // // void set(Node n, T a) { map->set(n, a); }145 // // T get(Node n) const { return map->get(n); }146 // // };147 148 // // template<typename Map, typename T> class EdgeMapWrapper {149 // // protected:150 // // Map* map;151 // // public:152 // // EdgeMapWrapper(Map& _map) : map(&_map) { }153 // // void set(Edge n, T a) { map->set(n, a); }154 // // T get(Edge n) const { return map->get(n); }155 // // };156 // };157 158 8 159 9 template<typename Graph> … … 171 21 // Graph& getGraph() const { return *graph; } 172 22 173 typedef typename Graph::Node Node;174 class Node It : public Graph::NodeIt {175 typedef typename Graph::NodeIt GraphNodeIt;23 // typedef typename Graph::Node Node; 24 class Node : public Graph::Node { 25 friend class GraphWrapper<Graph>; 176 26 public: 27 Node() { } 28 Node(const typename Graph::Node& _n) : Graph::Node(_n) { } 29 Node(const Invalid& i) : Graph::Node(i) { } 30 }; 31 class NodeIt { 32 friend class GraphWrapper<Graph>; 33 typename Graph::NodeIt n; 34 public: 177 35 NodeIt() { } 178 NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } 179 NodeIt(const Invalid& i) : Graph::NodeIt(i) { } 180 NodeIt(const GraphWrapper<Graph>& _G) : 181 Graph::NodeIt(*(_G.graph)) { } 182 // operator Node() const { 183 // std::cout << "ize" << std::endl; 184 // return Node(this->GraphNodeIt); 185 // } 36 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } 37 NodeIt(const Invalid& i) : n(i) { } 38 NodeIt(const GraphWrapper<Graph>& _G) : n(*(_G.graph)) { } 39 operator Node() const { return Node(typename Graph::Node(n)); } 186 40 }; 187 typedef typename Graph::Edge Edge; 188 class OutEdgeIt : public Graph::OutEdgeIt { 189 typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 41 // class Node : public Graph::Node { 42 // public: 43 // Node() { } 44 // Node(const typename Graph::Node& n) : Graph::Node(n) { } 45 // Node(const Invalid& i) : Graph::Node(i) { } 46 // }; 47 // class NodeIt : public Graph::NodeIt { 48 // typedef typename Graph::NodeIt GraphNodeIt; 49 // public: 50 // NodeIt() { } 51 // NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } 52 // NodeIt(const Invalid& i) : Graph::NodeIt(i) { } 53 // NodeIt(const GraphWrapper<Graph>& _G) : 54 // Graph::NodeIt(*(_G.graph)) { } 55 // operator Node() const { 56 // return Node(typename Graph::Node( 57 // static_cast<typename Graph::NodeIt>(*this) 58 // )); 59 // } 60 // }; 61 // typedef typename Graph::Edge Edge; 62 class Edge : public Graph::Edge { 63 friend class GraphWrapper<Graph>; 64 public: 65 Edge() { } 66 Edge(const typename Graph::Edge& _e) : Graph::Edge(_e) { } 67 Edge(const Invalid& i) : Graph::Edge(i) { } 68 }; 69 class OutEdgeIt { 70 friend class GraphWrapper<Graph>; 71 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 72 typename Graph::OutEdgeIt e; 190 73 public: 191 74 OutEdgeIt() { } 192 OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } 193 OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } 194 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) : 195 Graph::OutEdgeIt(*(_G.graph), n) { } 196 // operator Edge() const { 197 // std::cout << "ize" << std::endl; 198 // return Edge(this->GraphOutEdgeIt); 199 // } 75 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } 76 OutEdgeIt(const Invalid& i) : e(i) { } 77 OutEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 78 e(*(_G.graph), typename Graph::Node(_n)) { } 79 operator Edge() const { return Edge(typename Graph::Edge(e)); } 200 80 }; 201 class InEdgeIt : public Graph::InEdgeIt { 202 typedef typename Graph::InEdgeIt GraphInEdgeIt; 81 class InEdgeIt { 82 friend class GraphWrapper<Graph>; 83 // typedef typename Graph::InEdgeIt GraphInEdgeIt; 84 typename Graph::InEdgeIt e; 203 85 public: 204 86 InEdgeIt() { } 205 InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } 206 InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } 207 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& n) : 208 Graph::InEdgeIt(*(_G.graph), n) { } 209 // operator Edge() const { 210 // std::cout << "ize" << std::endl; 211 // return Edge(this->InOutEdgeIt); 212 // } 87 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } 88 InEdgeIt(const Invalid& i) : e(i) { } 89 InEdgeIt(const GraphWrapper<Graph>& _G, const Node& _n) : 90 e(*(_G.graph), typename Graph::Node(_n)) { } 91 operator Edge() const { return Edge(typename Graph::Edge(e)); } 213 92 }; 214 93 //typedef typename Graph::SymEdgeIt SymEdgeIt; 215 class EdgeIt : public Graph::EdgeIt { 216 typedef typename Graph::EdgeIt GraphEdgeIt; 94 class EdgeIt { 95 friend class GraphWrapper<Graph>; 96 // typedef typename Graph::EdgeIt GraphEdgeIt; 97 typename Graph::EdgeIt e; 217 98 public: 218 99 EdgeIt() { } 219 EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } 220 EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } 221 EdgeIt(const GraphWrapper<Graph>& _G) : 222 Graph::EdgeIt(*(_G.graph)) { } 223 // operator Edge() const { 224 // std::cout << "ize" << std::endl; 225 // return Edge(this->GraphEdgeIt); 226 // } 100 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } 101 EdgeIt(const Invalid& i) : e(i) { } 102 EdgeIt(const GraphWrapper<Graph>& _G) : e(*(_G.graph)) { } 103 operator Edge() const { return Edge(typename Graph::Edge(e)); } 227 104 }; 228 105 229 106 NodeIt& first(NodeIt& i) const { 230 i=NodeIt(*this); 231 return i; 107 i=NodeIt(*this); return i; 232 108 } 233 109 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 234 i=OutEdgeIt(*this, p); 235 return i; 110 i=OutEdgeIt(*this, p); return i; 236 111 } 237 112 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 238 i=InEdgeIt(*this, p); 239 return i; 113 i=InEdgeIt(*this, p); return i; 240 114 } 241 115 EdgeIt& first(EdgeIt& i) const { 242 i=EdgeIt(*this); 243 return i; 116 i=EdgeIt(*this); return i; 244 117 } 245 118 // template<typename I> I& first(I& i) const { … … 255 128 // return gw.getNext(i); } 256 129 257 NodeIt& next(NodeIt& i) const { graph->next(i ); return i; }258 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i ); return i; }259 InEdgeIt& next(InEdgeIt& i) const { graph->next(i ); return i; }260 EdgeIt& next(EdgeIt& i) const { graph->next(i ); return i; }130 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } 131 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } 132 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } 133 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } 261 134 // template<typename I> I& next(I &i) const { graph->next(i); return i; } 262 135 template< typename It > It first() const { … … 266 139 It e; this->first(e, v); return e; } 267 140 268 Node head(const Edge& e) const { return graph->head(e); } 269 Node tail(const Edge& e) const { return graph->tail(e); } 141 Node head(const Edge& e) const { 142 return Node(graph->head(static_cast<typename Graph::Edge>(e))); } 143 Node tail(const Edge& e) const { 144 return Node(graph->tail(static_cast<typename Graph::Edge>(e))); } 270 145 // Node tail(const OutEdgeIt& e) const { return graph->tail(Edge(e)); } 271 146 272 template<typename I> bool valid(const I& i) const { 273 return graph->valid(i); } 147 bool valid(const Node& n) const { 148 return graph->valid(static_cast<typename Graph::Node>(n)); } 149 bool valid(const Edge& e) const { 150 return graph->valid(static_cast<typename Graph::Edge>(e)); } 151 // template<typename I> bool valid(const I& i) const { 152 // return graph->valid(i); } 274 153 275 154 //template<typename I> void setInvalid(const I &i); … … 279 158 int edgeNum() const { return graph->edgeNum(); } 280 159 281 template<typename I> Node aNode(const I& e) const { 282 return graph->aNode(e); } 283 template<typename I> Node bNode(const I& e) const { 284 return graph->bNode(e); } 285 286 Node addNode() const { return graph->addNode(); } 160 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } 161 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } 162 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } 163 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } 164 // template<typename I> Node aNode(const I& e) const { 165 // return Node(graph->aNode(e.e)); } 166 // template<typename I> Node bNode(const I& e) const { 167 // return Node(graph->bNode(e.e)); } 168 169 Node addNode() const { return Node(graph->addNode()); } 287 170 Edge addEdge(const Node& tail, const Node& head) const { 288 return graph->addEdge(tail, head); } 289 290 template<typename I> void erase(const I& i) const { graph->erase(i); } 171 return Edge(graph->addEdge(tail, head)); } 172 173 void erase(const Node& i) const { graph->erase(i); } 174 void erase(const Edge& i) const { graph->erase(i); } 175 // template<typename I> void erase(const I& i) const { graph->erase(i); } 291 176 292 177 void clear() const { graph->clear(); } … … 298 183 NodeMap(const GraphWrapper<Graph>& _G, T a) : 299 184 Graph::NodeMap<T>(*(_G.graph), a) { } 185 // T operator[](const Node& n) const { 186 // return Graph::NodeMap<T>::operator[](n); 187 // } 300 188 }; 301 189 … … 430 318 edge_filter_map(&_edge_filter_map) { } 431 319 432 433 typedef typename Graph::Node Node; 434 class NodeIt : public Graph::NodeIt { 435 // typedef typename Graph::NodeIt GraphNodeIt; 436 public: 320 typedef typename GraphWrapper<Graph>::Node Node; 321 class NodeIt { 322 friend class GraphWrapper<Graph>; 323 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 324 typename Graph::NodeIt n; 325 public: 437 326 NodeIt() { } 438 NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }439 NodeIt(const Invalid& i) : Graph::NodeIt(i) { }327 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } 328 NodeIt(const Invalid& i) : n(i) { } 440 329 NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 441 Graph::NodeIt(*(_G.graph)) { 442 while (_G.graph->valid((*this)/*.GraphNodeIt*/) && 443 !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) 444 _G.graph->next((*this)/*.GraphNodeIt*/); 330 n(*(_G.graph)) { 331 while (_G.graph->valid(n) && !(*(_G.node_filter_map))[n]) 332 _G.graph->next(n); 445 333 } 334 operator Node() const { return Node(typename Graph::Node(n)); } 446 335 }; 447 typedef typename Graph::Edge Edge; 448 class OutEdgeIt : public Graph::OutEdgeIt { 336 // class NodeIt : public Graph::NodeIt { 337 // // typedef typename Graph::NodeIt GraphNodeIt; 338 // public: 339 // NodeIt() { } 340 // NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } 341 // NodeIt(const Invalid& i) : Graph::NodeIt(i) { } 342 // NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 343 // Graph::NodeIt(*(_G.graph)) { 344 // while (_G.graph->valid((*this)/*.GraphNodeIt*/) && 345 // !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) 346 // _G.graph->next((*this)/*.GraphNodeIt*/); 347 // } 348 // }; 349 typedef typename GraphWrapper<Graph>::Edge Edge; 350 class OutEdgeIt { 351 friend class GraphWrapper<Graph>; 352 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 449 353 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 354 typename Graph::OutEdgeIt e; 450 355 public: 451 356 OutEdgeIt() { } 452 OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } 453 OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } 454 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& 455 _G, const Node& n) : 456 Graph::OutEdgeIt(*(_G.graph), n) { 457 while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && 458 !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) 459 _G.graph->next((*this)/*.GraphOutEdgeIt*/); 357 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } 358 OutEdgeIt(const Invalid& i) : e(i) { } 359 OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 360 const Node& _n) : 361 e(*(_G.graph), typename Graph::Node(_n)) { 362 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 363 _G.graph->next(e); 460 364 } 365 operator Edge() const { return Edge(typename Graph::Edge(e)); } 461 366 }; 462 class InEdgeIt : public Graph::InEdgeIt { 367 class InEdgeIt { 368 friend class GraphWrapper<Graph>; 369 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 463 370 // typedef typename Graph::InEdgeIt GraphInEdgeIt; 371 typename Graph::InEdgeIt e; 464 372 public: 465 373 InEdgeIt() { } 466 InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }467 InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }374 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } 375 InEdgeIt(const Invalid& i) : e(i) { } 468 376 InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 469 const Node& n) : 470 Graph::InEdgeIt(*(_G.graph), n) { 471 while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && 472 !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) 473 _G.graph->next((*this)/*.GraphInEdgeIt*/); 377 const Node& _n) : 378 e(*(_G.graph), typename Graph::Node(_n)) { 379 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 380 _G.graph->next(e); 474 381 } 382 operator Edge() const { return Edge(typename Graph::Edge(e)); } 475 383 }; 476 // //typedef typename Graph::SymEdgeIt SymEdgeIt; 477 class EdgeIt : public Graph::EdgeIt { 384 //typedef typename Graph::SymEdgeIt SymEdgeIt; 385 class EdgeIt { 386 friend class GraphWrapper<Graph>; 387 friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>; 478 388 // typedef typename Graph::EdgeIt GraphEdgeIt; 389 typename Graph::EdgeIt e; 479 390 public: 480 391 EdgeIt() { } 481 EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }482 EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }392 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } 393 EdgeIt(const Invalid& i) : e(i) { } 483 394 EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 484 Graph::EdgeIt(*(_G.graph)) { 485 while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && 486 !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) 487 _G.graph->next((*this)/*.GraphEdgeIt*/); 395 e(*(_G.graph)) { 396 while (_G.graph->valid(e) && !(*(_G.edge_filter_map))[e]) 397 _G.graph->next(e); 488 398 } 399 operator Edge() const { return Edge(typename Graph::Edge(e)); } 489 400 }; 401 // operator Edge() const { return Edge(typename Graph::Edge(e)); } 402 // }; 403 // class OutEdgeIt : public Graph::OutEdgeIt { 404 // // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 405 // public: 406 // OutEdgeIt() { } 407 // OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } 408 // OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } 409 // OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& 410 // _G, const Node& n) : 411 // Graph::OutEdgeIt(*(_G.graph), n) { 412 // while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && 413 // !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) 414 // _G.graph->next((*this)/*.GraphOutEdgeIt*/); 415 // } 416 // }; 417 // class InEdgeIt : public Graph::InEdgeIt { 418 // // typedef typename Graph::InEdgeIt GraphInEdgeIt; 419 // public: 420 // InEdgeIt() { } 421 // InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } 422 // InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } 423 // InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 424 // const Node& n) : 425 // Graph::InEdgeIt(*(_G.graph), n) { 426 // while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && 427 // !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) 428 // _G.graph->next((*this)/*.GraphInEdgeIt*/); 429 // } 430 // }; 431 // // //typedef typename Graph::SymEdgeIt SymEdgeIt; 432 // class EdgeIt : public Graph::EdgeIt { 433 // // typedef typename Graph::EdgeIt GraphEdgeIt; 434 // public: 435 // EdgeIt() { } 436 // EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } 437 // EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } 438 // EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 439 // Graph::EdgeIt(*(_G.graph)) { 440 // while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && 441 // !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) 442 // _G.graph->next((*this)/*.GraphEdgeIt*/); 443 // } 444 // }; 490 445 491 NodeIt& first(NodeIt& i) const { 492 i=NodeIt(*this); 493 return i; 494 } 495 OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { 496 i=OutEdgeIt(*this, n); 497 return i; 498 } 499 InEdgeIt& first(InEdgeIt& i, const Node& n) const { 500 i=InEdgeIt(*this, n); 501 return i; 502 } 503 EdgeIt& first(EdgeIt& i) const { 504 i=EdgeIt(*this); 505 return i; 446 447 NodeIt& first(NodeIt& i) const { 448 i=NodeIt(*this); return i; 449 } 450 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 451 i=OutEdgeIt(*this, p); return i; 452 } 453 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 454 i=InEdgeIt(*this, p); return i; 455 } 456 EdgeIt& first(EdgeIt& i) const { 457 i=EdgeIt(*this); return i; 506 458 } 507 459 … … 520 472 521 473 NodeIt& next(NodeIt& i) const { 522 graph->next(i );523 while (graph->valid(i) && !(*node_filter_map)[i ]) { graph->next(i); }474 graph->next(i.n); 475 while (graph->valid(i) && !(*node_filter_map)[i.n]) { graph->next(i.n); } 524 476 return i; 525 477 } 526 478 OutEdgeIt& next(OutEdgeIt& i) const { 527 graph->next(i );528 while (graph->valid(i) && !(*edge_filter_map)[i ]) { graph->next(i); }479 graph->next(i.e); 480 while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } 529 481 return i; 530 482 } 531 483 InEdgeIt& next(InEdgeIt& i) const { 532 graph->next(i );533 while (graph->valid(i) && !(*edge_filter_map)[i ]) { graph->next(i); }484 graph->next(i.e); 485 while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } 534 486 return i; 535 487 } 536 488 EdgeIt& next(EdgeIt& i) const { 537 graph->next(i );538 while (graph->valid(i) && !(*edge_filter_map)[i ]) { graph->next(i); }489 graph->next(i.e); 490 while (graph->valid(i) && !(*edge_filter_map)[i.e]) { graph->next(i.e); } 539 491 return i; 540 492 } 541 493 494 495 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } 496 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } 497 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } 498 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } 499 542 500 //template<typename I> I getNext(const I& i) const { 543 501 // return gw.getNext(i); … … 556 514 It e; this->first(e, v); return e; } 557 515 }; 516 517 // //Subgraph on the same node-set and partial edge-set 518 // template<typename Graph, typename NodeFilterMap, 519 // typename EdgeFilterMap> 520 // class SubGraphWrapper : public GraphWrapper<Graph> { 521 // protected: 522 // NodeFilterMap* node_filter_map; 523 // EdgeFilterMap* edge_filter_map; 524 // public: 525 // // SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { } 526 // SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map, 527 // EdgeFilterMap& _edge_filter_map) : 528 // GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map), 529 // edge_filter_map(&_edge_filter_map) { } 530 531 532 // typedef typename Graph::Node Node; 533 // class NodeIt : public Graph::NodeIt { 534 // // typedef typename Graph::NodeIt GraphNodeIt; 535 // public: 536 // NodeIt() { } 537 // NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } 538 // NodeIt(const Invalid& i) : Graph::NodeIt(i) { } 539 // NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 540 // Graph::NodeIt(*(_G.graph)) { 541 // while (_G.graph->valid((*this)/*.GraphNodeIt*/) && 542 // !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/]) 543 // _G.graph->next((*this)/*.GraphNodeIt*/); 544 // } 545 // }; 546 // typedef typename Graph::Edge Edge; 547 // class OutEdgeIt : public Graph::OutEdgeIt { 548 // // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 549 // public: 550 // OutEdgeIt() { } 551 // OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } 552 // OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } 553 // OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& 554 // _G, const Node& n) : 555 // Graph::OutEdgeIt(*(_G.graph), n) { 556 // while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) && 557 // !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/]) 558 // _G.graph->next((*this)/*.GraphOutEdgeIt*/); 559 // } 560 // }; 561 // class InEdgeIt : public Graph::InEdgeIt { 562 // // typedef typename Graph::InEdgeIt GraphInEdgeIt; 563 // public: 564 // InEdgeIt() { } 565 // InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } 566 // InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } 567 // InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G, 568 // const Node& n) : 569 // Graph::InEdgeIt(*(_G.graph), n) { 570 // while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) && 571 // !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/]) 572 // _G.graph->next((*this)/*.GraphInEdgeIt*/); 573 // } 574 // }; 575 // // //typedef typename Graph::SymEdgeIt SymEdgeIt; 576 // class EdgeIt : public Graph::EdgeIt { 577 // // typedef typename Graph::EdgeIt GraphEdgeIt; 578 // public: 579 // EdgeIt() { } 580 // EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } 581 // EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } 582 // EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) : 583 // Graph::EdgeIt(*(_G.graph)) { 584 // while (_G.graph->valid((*this)/*.GraphEdgeIt*/) && 585 // !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/]) 586 // _G.graph->next((*this)/*.GraphEdgeIt*/); 587 // } 588 // }; 589 590 // NodeIt& first(NodeIt& i) const { 591 // i=NodeIt(*this); 592 // return i; 593 // } 594 // OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { 595 // i=OutEdgeIt(*this, n); 596 // return i; 597 // } 598 // InEdgeIt& first(InEdgeIt& i, const Node& n) const { 599 // i=InEdgeIt(*this, n); 600 // return i; 601 // } 602 // EdgeIt& first(EdgeIt& i) const { 603 // i=EdgeIt(*this); 604 // return i; 605 // } 606 607 // // template<typename I> I& first(I& i) const { 608 // // graph->first(i); 609 // // //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } 610 // // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } 611 // // return i; 612 // // } 613 // // template<typename I, typename P> I& first(I& i, const P& p) const { 614 // // graph->first(i, p); 615 // // // while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); } 616 // // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } 617 // // return i; 618 // // } 619 620 // NodeIt& next(NodeIt& i) const { 621 // graph->next(i); 622 // while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); } 623 // return i; 624 // } 625 // OutEdgeIt& next(OutEdgeIt& i) const { 626 // graph->next(i); 627 // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } 628 // return i; 629 // } 630 // InEdgeIt& next(InEdgeIt& i) const { 631 // graph->next(i); 632 // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } 633 // return i; 634 // } 635 // EdgeIt& next(EdgeIt& i) const { 636 // graph->next(i); 637 // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } 638 // return i; 639 // } 640 641 // //template<typename I> I getNext(const I& i) const { 642 // // return gw.getNext(i); 643 // //} 644 // // template<typename I> I& next(I &i) const { 645 // // graph->next(i); 646 // // // while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); } 647 // // while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); } 648 // // return i; 649 // // } 650 651 // template< typename It > It first() const { 652 // It e; this->first(e); return e; } 653 654 // template< typename It > It first(const Node& v) const { 655 // It e; this->first(e, v); return e; } 656 // }; 558 657 559 658 // template<typename GraphWrapper> … … 719 818 template<typename Graph> 720 819 class UndirGraphWrapper : public GraphWrapper<Graph> { 721 protected:722 typedef typename Graph::Edge GraphEdge;723 typedef typename Graph::OutEdgeIt GraphOutEdgeIt;724 typedef typename Graph::InEdgeIt GraphInEdgeIt;820 // protected: 821 // typedef typename Graph::Edge GraphEdge; 822 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 823 // typedef typename Graph::InEdgeIt GraphInEdgeIt; 725 824 public: 726 825 typedef typename GraphWrapper<Graph>::Node Node; 727 826 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 827 typedef typename GraphWrapper<Graph>::Edge Edge; 828 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt; 728 829 729 830 // UndirGraphWrapper() : GraphWrapper<Graph>() { } 730 831 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 731 832 732 class Edge { 833 834 // class Edge { 835 // friend class UndirGraphWrapper<Graph>; 836 // protected: 837 // bool out_or_in; //true iff out 838 // GraphOutEdgeIt out; 839 // GraphInEdgeIt in; 840 // public: 841 // Edge() : out_or_in(), out(), in() { } 842 // Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } 843 // operator GraphEdge() const { 844 // if (out_or_in) return(out); else return(in); 845 // } 846 // //FIXME 847 // //2 edges are equal if they "refer" to the same physical edge 848 // //is it good? 849 // friend bool operator==(const Edge& u, const Edge& v) { 850 // if (v.out_or_in) 851 // if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in); 852 // //return (u.out_or_in && u.out==v.out); 853 // else 854 // if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in); 855 // //return (!u.out_or_in && u.in==v.in); 856 // } 857 // friend bool operator!=(const Edge& u, const Edge& v) { 858 // if (v.out_or_in) 859 // if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in); 860 // //return (!u.out_or_in || u.out!=v.out); 861 // else 862 // if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in); 863 // //return (u.out_or_in || u.in!=v.in); 864 // } 865 // }; 866 867 class OutEdgeIt { 733 868 friend class UndirGraphWrapper<Graph>; 734 protected:735 869 bool out_or_in; //true iff out 736 GraphOutEdgeIt out;737 GraphInEdgeIt in;870 typename Graph::OutEdgeIt out; 871 typename Graph::InEdgeIt in; 738 872 public: 739 Edge() : out_or_in(), out(), in() { } 740 Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } 741 operator GraphEdge() const { 742 if (out_or_in) return(out); else return(in); 743 } 744 //FIXME 745 //2 edges are equal if they "refer" to the same physical edge 746 //is it good? 747 friend bool operator==(const Edge& u, const Edge& v) { 748 if (v.out_or_in) 749 if (u.out_or_in) return (u.out==v.out); else return (u.out==v.in); 750 //return (u.out_or_in && u.out==v.out); 751 else 752 if (u.out_or_in) return (u.out==v.in); else return (u.in==v.in); 753 //return (!u.out_or_in && u.in==v.in); 873 OutEdgeIt() { } 874 OutEdgeIt(const Invalid& i) : Edge(i) { } 875 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) { 876 out_or_in=true; _G.graph->first(out, _n); 877 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); } 754 878 } 755 friend bool operator!=(const Edge& u, const Edge& v) { 756 if (v.out_or_in) 757 if (u.out_or_in) return (u.out!=v.out); else return (u.out!=v.in); 758 //return (!u.out_or_in || u.out!=v.out); 759 else 760 if (u.out_or_in) return (u.out!=v.in); else return (u.in!=v.in); 761 //return (u.out_or_in || u.in!=v.in); 762 } 763 }; 764 765 class OutEdgeIt : public Edge { 766 friend class UndirGraphWrapper<Graph>; 767 public: 768 OutEdgeIt() : Edge() { } 769 OutEdgeIt(const Invalid& i) : Edge(i) { } 770 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n) 771 : Edge() { 772 out_or_in=true; _G.graph->first(out, n); 773 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); } 879 operator Edge() const { 880 if (out_or_in) return Edge(out); else return Edge(in); 774 881 } 775 882 }; 776 883 // class OutEdgeIt : public Edge { 884 // friend class UndirGraphWrapper<Graph>; 885 // public: 886 // OutEdgeIt() : Edge() { } 887 // OutEdgeIt(const Invalid& i) : Edge(i) { } 888 // OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& n) 889 // : Edge() { 890 // out_or_in=true; _G.graph->first(out, n); 891 // if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, n); } 892 // } 893 // }; 894 895 //FIXME InEdgeIt 777 896 typedef OutEdgeIt InEdgeIt; 778 897 779 class EdgeIt : public Edge { 780 friend class UndirGraphWrapper<Graph>; 781 protected: 782 NodeIt v; 783 public: 784 EdgeIt() : Edge() { } 785 EdgeIt(const Invalid& i) : Edge(i) { } 786 EdgeIt(const UndirGraphWrapper<Graph>& _G) 787 : Edge() { 788 out_or_in=true; 789 //Node v; 790 _G.first(v); 791 if (_G.valid(v)) _G.graph->first(out); else out=INVALID; 792 while (_G.valid(v) && !_G.graph->valid(out)) { 793 _G.graph->next(v); 794 if (_G.valid(v)) _G.graph->first(out); 795 } 796 } 797 }; 798 799 OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { 800 e.out_or_in=true; graph->first(e.out, n); 801 if (!(graph->valid(e.out))) { e.out_or_in=false; graph->first(e.in, n); } 802 return e; 803 } 804 805 EdgeIt& first(EdgeIt& e) const { 806 e.out_or_in=true; 807 //NodeIt v; 808 first(e.v); 809 if (valid(e.v)) graph->first(e.out, e.v); else e.out=INVALID; 810 while (valid(e.v) && !graph->valid(e.out)) { 811 graph->next(e.v); 812 if (valid(e.v)) graph->first(e.out, e.v); 813 } 814 return e; 898 // class EdgeIt : public Edge { 899 // friend class UndirGraphWrapper<Graph>; 900 // protected: 901 // NodeIt v; 902 // public: 903 // EdgeIt() : Edge() { } 904 // EdgeIt(const Invalid& i) : Edge(i) { } 905 // EdgeIt(const UndirGraphWrapper<Graph>& _G) 906 // : Edge() { 907 // out_or_in=true; 908 // //Node v; 909 // _G.first(v); 910 // if (_G.valid(v)) _G.graph->first(out); else out=INVALID; 911 // while (_G.valid(v) && !_G.graph->valid(out)) { 912 // _G.graph->next(v); 913 // if (_G.valid(v)) _G.graph->first(out); 914 // } 915 // } 916 // }; 917 918 NodeIt& first(NodeIt& i) const { 919 i=NodeIt(*this); return i; 920 } 921 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 922 i=OutEdgeIt(*this, p); return i; 923 } 924 //FIXME 925 // InEdgeIt& first(InEdgeIt& i, const Node& p) const { 926 // i=InEdgeIt(*this, p); return i; 927 // } 928 EdgeIt& first(EdgeIt& i) const { 929 i=EdgeIt(*this); return i; 815 930 } 816 931 … … 819 934 graph->first(i, p); return i; } 820 935 936 NodeIt& next(NodeIt& n) const { 937 GraphWrapper<Graph>::next(n); 938 return n; 939 } 821 940 OutEdgeIt& next(OutEdgeIt& e) const { 822 941 if (e.out_or_in) { 823 Node n=graph->tail(e.out);942 typename Graph::Node n=graph->tail(e.out); 824 943 graph->next(e.out); 825 944 if (!graph->valid(e.out)) { e.out_or_in=false; graph->first(e.in, n); } … … 829 948 return e; 830 949 } 831 950 //FIXME InEdgeIt 832 951 EdgeIt& next(EdgeIt& e) const { 833 //NodeIt v=tail(e); 834 graph->next(e.out); 835 while (valid(e.v) && !graph->valid(e.out)) { 836 next(e.v); 837 if (valid(e.v)) graph->first(e.out, e.v); 838 } 952 GraphWrapper<Graph>::next(n); 953 // graph->next(e.e); 839 954 return e; 840 955 } 841 956 842 template<typename I> I& next(I &i) const { graph->next(i); return i; }957 // template<typename I> I& next(I &i) const { graph->next(i); return i; } 843 958 // template<typename I> I getNext(const I& i) const { return gw.getNext(i); } 844 959 … … 969 1084 970 1085 1086 1087 971 1088 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> 972 1089 class ResGraphWrapper : public GraphWrapper<Graph> { 973 1090 protected: 974 typedef typename Graph::OutEdgeIt GraphOutEdgeIt;975 typedef typename Graph::InEdgeIt GraphInEdgeIt;976 typedef typename Graph::Edge GraphEdge;1091 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 1092 // typedef typename Graph::InEdgeIt GraphInEdgeIt; 1093 // typedef typename Graph::Edge GraphEdge; 977 1094 FlowMap* flow; 978 1095 const CapacityMap* capacity; … … 990 1107 typedef typename GraphWrapper<Graph>::Node Node; 991 1108 typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 992 class Edge {1109 class Edge : public Graph::Edge { 993 1110 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 994 1111 protected: 995 bool out_or_in; //true, iff out 996 GraphOutEdgeIt out; 997 GraphInEdgeIt in; 1112 bool forward; //true, iff forward 1113 // typename Graph::Edge e; 998 1114 public: 999 Edge() : out_or_in(true) { } 1000 Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } 1001 // bool valid() const { 1002 // return out_or_in && out.valid() || in.valid(); } 1115 Edge() { } 1116 Edge(const typename Graph::Edge& _e, bool _forward) : 1117 Graph::Edge(_e), forward(_forward) { } 1118 Edge(const Invalid& i) : Graph::Edge(i), forward(false) { } 1119 //the unique invalid iterator 1003 1120 friend bool operator==(const Edge& u, const Edge& v) { 1004 if (v.out_or_in) 1005 return (u.out_or_in && u.out==v.out); 1006 else 1007 return (!u.out_or_in && u.in==v.in); 1121 return (v.forward==u.forward && 1122 static_cast<typename Graph::Edge>(u)== 1123 static_cast<typename Graph::Edge>(v)); 1008 1124 } 1009 1125 friend bool operator!=(const Edge& u, const Edge& v) { 1010 if (v.out_or_in) 1011 return (!u.out_or_in || u.out!=v.out); 1012 else 1013 return (u.out_or_in || u.in!=v.in); 1126 return (v.forward!=u.forward || 1127 static_cast<typename Graph::Edge>(u)!= 1128 static_cast<typename Graph::Edge>(v)); 1014 1129 } 1015 operator GraphEdge() const {1016 if (out_or_in) return(out); else return(in);1017 }1018 1130 }; 1019 class OutEdgeIt : public Edge { 1131 // class Edge { 1132 // friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 1133 // protected: 1134 // bool out_or_in; //true, iff out 1135 // GraphOutEdgeIt out; 1136 // GraphInEdgeIt in; 1137 // public: 1138 // Edge() : out_or_in(true) { } 1139 // Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } 1140 // // bool valid() const { 1141 // // return out_or_in && out.valid() || in.valid(); } 1142 // friend bool operator==(const Edge& u, const Edge& v) { 1143 // if (v.out_or_in) 1144 // return (u.out_or_in && u.out==v.out); 1145 // else 1146 // return (!u.out_or_in && u.in==v.in); 1147 // } 1148 // friend bool operator!=(const Edge& u, const Edge& v) { 1149 // if (v.out_or_in) 1150 // return (!u.out_or_in || u.out!=v.out); 1151 // else 1152 // return (u.out_or_in || u.in!=v.in); 1153 // } 1154 // operator GraphEdge() const { 1155 // if (out_or_in) return(out); else return(in); 1156 // } 1157 // }; 1158 class OutEdgeIt { 1020 1159 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 1160 protected: 1161 typename Graph::OutEdgeIt out; 1162 typename Graph::InEdgeIt in; 1163 bool forward; 1021 1164 public: 1022 1165 OutEdgeIt() { } 1023 1166 //FIXME 1024 OutEdgeIt(const Edge& e) : Edge(e) { } 1025 OutEdgeIt(const Invalid& i) : Edge(i) { } 1026 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { 1167 // OutEdgeIt(const Edge& e) : Edge(e) { } 1168 OutEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } 1169 //the unique invalid iterator 1170 OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) { 1171 forward=true; 1027 1172 resG.graph->first(out, v); 1028 while( resG.graph->valid(out) && !(resG.resCap( out)>0) ) { resG.graph->next(out); }1173 while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); } 1029 1174 if (!resG.graph->valid(out)) { 1030 out_or_in=0;1175 forward=false; 1031 1176 resG.graph->first(in, v); 1032 while( resG.graph->valid(in) && !(resG.resCap( in)>0) ) { resG.graph->next(in); }1177 while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); } 1033 1178 } 1034 1179 } 1180 operator Edge() const { 1181 // Edge e; 1182 // e.forward=this->forward; 1183 // if (this->forward) e=out; else e=in; 1184 // return e; 1185 if (this->forward) 1186 return Edge(out, this->forward); 1187 else 1188 return Edge(in, this->forward); 1189 } 1190 }; 1191 // class OutEdgeIt : public Edge { 1192 // friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 1193 // public: 1194 // OutEdgeIt() { } 1195 // //FIXME 1196 // OutEdgeIt(const Edge& e) : Edge(e) { } 1197 // OutEdgeIt(const Invalid& i) : Edge(i) { } 1198 // OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { 1199 // resG.graph->first(out, v); 1200 // while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } 1201 // if (!resG.graph->valid(out)) { 1202 // out_or_in=0; 1203 // resG.graph->first(in, v); 1204 // while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } 1205 // } 1206 // } 1035 1207 // public: 1036 1208 // OutEdgeIt& operator++() { … … 1050 1222 // return *this; 1051 1223 // } 1052 };1224 // }; 1053 1225 1054 1226 //FIXME This is just for having InEdgeIt 1055 1227 // class InEdgeIt : public Edge { }; 1056 1228 1057 class EdgeIt : public Edge{1229 class InEdgeIt { 1058 1230 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 1059 NodeIt v; 1231 protected: 1232 typename Graph::OutEdgeIt out; 1233 typename Graph::InEdgeIt in; 1234 bool forward; 1235 public: 1236 InEdgeIt() { } 1237 //FIXME 1238 // OutEdgeIt(const Edge& e) : Edge(e) { } 1239 InEdgeIt(const Invalid& i) : out(i), in(i), forward(false) { } 1240 //the unique invalid iterator 1241 InEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) { 1242 forward=true; 1243 resG.graph->first(in, v); 1244 while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); } 1245 if (!resG.graph->valid(in)) { 1246 forward=false; 1247 resG.graph->first(out, v); 1248 while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); } 1249 } 1250 } 1251 operator Edge() const { 1252 // Edge e; 1253 // e.forward=this->forward; 1254 // if (this->forward) e=out; else e=in; 1255 // return e; 1256 if (this->forward) 1257 return Edge(in, this->forward); 1258 else 1259 return Edge(out, this->forward); 1260 } 1261 }; 1262 1263 class EdgeIt { 1264 friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 1265 protected: 1266 typename Graph::EdgeIt e; 1267 bool forward; 1060 1268 public: 1061 1269 EdgeIt() { } 1062 //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } 1063 EdgeIt(const Invalid& i) : Edge(i) { } 1064 EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { 1065 resG.graph->first(v); 1066 if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; 1067 while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } 1068 while (resG.graph->valid(v) && !resG.graph->valid(out)) { 1069 resG.graph->next(v); 1070 if (resG.graph->valid(v)) resG.graph->first(out, v); 1071 while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } 1072 } 1073 if (!resG.graph->valid(out)) { 1074 out_or_in=0; 1075 resG.graph->first(v); 1076 if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; 1077 while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } 1078 while (resG.graph->valid(v) && !resG.graph->valid(in)) { 1079 resG.graph->next(v); 1080 if (resG.graph->valid(v)) resG.graph->first(in, v); 1081 while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } 1082 } 1270 EdgeIt(const Invalid& i) : e(i), forward(false) { } 1271 EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) { 1272 forward=true; 1273 resG.graph->first(e); 1274 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); 1275 if (!resG.graph->valid(e)) { 1276 forward=false; 1277 resG.graph->first(e); 1278 while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e); 1083 1279 } 1084 1280 } 1281 operator Edge() const { 1282 return Edge(e, this->forward); 1283 } 1284 }; 1285 // class EdgeIt : public Edge { 1286 // friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 1287 // NodeIt v; 1288 // public: 1289 // EdgeIt() { } 1290 // //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } 1291 // EdgeIt(const Invalid& i) : Edge(i) { } 1292 // EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { 1293 // resG.graph->first(v); 1294 // if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; 1295 // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } 1296 // while (resG.graph->valid(v) && !resG.graph->valid(out)) { 1297 // resG.graph->next(v); 1298 // if (resG.graph->valid(v)) resG.graph->first(out, v); 1299 // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } 1300 // } 1301 // if (!resG.graph->valid(out)) { 1302 // out_or_in=0; 1303 // resG.graph->first(v); 1304 // if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; 1305 // while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } 1306 // while (resG.graph->valid(v) && !resG.graph->valid(in)) { 1307 // resG.graph->next(v); 1308 // if (resG.graph->valid(v)) resG.graph->first(in, v); 1309 // while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } 1310 // } 1311 // } 1312 // } 1085 1313 // EdgeIt& operator++() { 1086 1314 // if (out_or_in) { … … 1114 1342 // return *this; 1115 1343 // } 1116 };1344 // }; 1117 1345 1118 1346 NodeIt& first(NodeIt& i) const { 1119 i=NodeIt(*this); 1120 return i; 1347 i=NodeIt(*this); return i; 1121 1348 } 1122 1349 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 1123 i=OutEdgeIt(*this, p); 1124 return i; 1125 } 1126 //FIXME Not yet implemented 1127 //InEdgeIt& first(InEdgeIt& i, const Node& p) const { 1128 //i=InEdgeIt(*this, p); 1129 // return i; 1130 //} 1131 EdgeIt& first(EdgeIt& e) const { 1132 e=EdgeIt(*this); 1133 return e; 1350 i=OutEdgeIt(*this, p); return i; 1351 } 1352 // FIXME not tested 1353 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 1354 i=InEdgeIt(*this, p); return i; 1355 } 1356 EdgeIt& first(EdgeIt& i) const { 1357 i=EdgeIt(*this); return i; 1134 1358 } 1135 1359 1136 NodeIt& next(NodeIt& n) const { graph->next(n); return n; }1360 NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; } 1137 1361 OutEdgeIt& next(OutEdgeIt& e) const { 1138 if (e. out_or_in) {1362 if (e.forward) { 1139 1363 Node v=graph->aNode(e.out); 1140 1364 graph->next(e.out); 1141 while( graph->valid(e.out) && !(resCap(e .out)>0) ) { graph->next(e.out); }1365 while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } 1142 1366 if (!graph->valid(e.out)) { 1143 e. out_or_in=0;1367 e.forward=false; 1144 1368 graph->first(e.in, v); 1145 while( graph->valid(e.in) && !(resCap(e .in)>0) ) { graph->next(e.in); }1369 while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } 1146 1370 } 1147 1371 } else { 1148 1372 graph->next(e.in); 1149 while( graph->valid(e.in) && !(resCap(e .in)>0) ) { graph->next(e.in); }1373 while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } 1150 1374 } 1151 1375 return e; 1152 1376 } 1153 //FIXME Not yet implemented 1154 //InEdgeIt& next(InEdgeIt& e) const { 1155 // return e; 1156 //} 1157 EdgeIt& next(EdgeIt& e) const { 1158 if (e.out_or_in) { 1377 // FIXME Not tested 1378 InEdgeIt& next(InEdgeIt& e) const { 1379 if (e.forward) { 1380 Node v=graph->aNode(e.in); 1381 graph->next(e.in); 1382 while( graph->valid(e.in) && !(resCap(e)>0) ) { graph->next(e.in); } 1383 if (!graph->valid(e.in)) { 1384 e.forward=false; 1385 graph->first(e.out, v); 1386 while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } 1387 } 1388 } else { 1159 1389 graph->next(e.out); 1160 while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } 1161 while (graph->valid(e.v) && !graph->valid(e.out)) { 1162 graph->next(e.v); 1163 if (graph->valid(e.v)) graph->first(e.out, e.v); 1164 while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } 1165 } 1166 if (!graph->valid(e.out)) { 1167 e.out_or_in=0; 1168 graph->first(e.v); 1169 if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; 1170 while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1171 while (graph->valid(e.v) && !graph->valid(e.in)) { 1172 graph->next(e.v); 1173 if (graph->valid(e.v)) graph->first(e.in, e.v); 1174 while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1175 } 1176 } 1177 } else { 1178 graph->next(e.in); 1179 while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1180 while (graph->valid(e.v) && !graph->valid(e.in)) { 1181 graph->next(e.v); 1182 if (graph->valid(e.v)) graph->first(e.in, e.v); 1183 while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1184 } 1390 while( graph->valid(e.out) && !(resCap(e)>0) ) { graph->next(e.out); } 1391 } 1392 return e; 1393 } 1394 EdgeIt& next(EdgeIt& e) const { 1395 if (e.forward) { 1396 graph->next(e.e); 1397 while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } 1398 if (!graph->valid(e.e)) { 1399 e.forward=false; 1400 graph->first(e.e); 1401 while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } 1185 1402 } 1186 return e; 1403 } else { 1404 graph->next(e.e); 1405 while( graph->valid(e.e) && !(resCap(e)>0) ) { graph->next(e.e); } 1187 1406 } 1407 return e; 1408 } 1409 // EdgeIt& next(EdgeIt& e) const { 1410 // if (e.out_or_in) { 1411 // graph->next(e.out); 1412 // while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } 1413 // while (graph->valid(e.v) && !graph->valid(e.out)) { 1414 // graph->next(e.v); 1415 // if (graph->valid(e.v)) graph->first(e.out, e.v); 1416 // while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } 1417 // } 1418 // if (!graph->valid(e.out)) { 1419 // e.out_or_in=0; 1420 // graph->first(e.v); 1421 // if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; 1422 // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1423 // while (graph->valid(e.v) && !graph->valid(e.in)) { 1424 // graph->next(e.v); 1425 // if (graph->valid(e.v)) graph->first(e.in, e.v); 1426 // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1427 // } 1428 // } 1429 // } else { 1430 // graph->next(e.in); 1431 // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1432 // while (graph->valid(e.v) && !graph->valid(e.in)) { 1433 // graph->next(e.v); 1434 // if (graph->valid(e.v)) graph->first(e.in, e.v); 1435 // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1436 // } 1437 // } 1438 // return e; 1439 // } 1188 1440 1189 1441 … … 1203 1455 1204 1456 Node tail(Edge e) const { 1205 return ((e. out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }1457 return ((e.forward) ? graph->tail(e) : graph->head(e)); } 1206 1458 Node head(Edge e) const { 1207 return ((e. out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }1459 return ((e.forward) ? graph->head(e) : graph->tail(e)); } 1208 1460 1209 1461 Node aNode(OutEdgeIt e) const { 1210 return ((e. out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); }1462 return ((e.forward) ? graph->aNode(e.out) : graph->aNode(e.in)); } 1211 1463 Node bNode(OutEdgeIt e) const { 1212 return ((e. out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); }1464 return ((e.forward) ? graph->bNode(e.out) : graph->bNode(e.in)); } 1213 1465 1214 1466 int nodeNum() const { return graph->nodeNum(); } … … 1217 1469 1218 1470 1219 int id(Node v) const { return graph->id(v); }1220 1221 bool valid(Node n) const { return graph->valid(n); }1471 // int id(Node v) const { return graph->id(v); } 1472 1473 bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); } 1222 1474 bool valid(Edge e) const { 1223 return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } 1475 return graph->valid(e); 1476 //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 1477 } 1224 1478 1225 1479 void augment(const Edge& e, Number a) const { 1226 if (e. out_or_in)1480 if (e.forward) 1227 1481 // flow->set(e.out, flow->get(e.out)+a); 1228 flow->set(e .out, (*flow)[e.out]+a);1482 flow->set(e, (*flow)[e]+a); 1229 1483 else 1230 1484 // flow->set(e.in, flow->get(e.in)-a); 1231 flow->set(e .in, (*flow)[e.in]-a);1485 flow->set(e, (*flow)[e]-a); 1232 1486 } 1233 1487 1234 1488 Number resCap(const Edge& e) const { 1235 if (e. out_or_in)1489 if (e.forward) 1236 1490 // return (capacity->get(e.out)-flow->get(e.out)); 1237 return ((*capacity)[e .out]-(*flow)[e.out]);1491 return ((*capacity)[e]-(*flow)[e]); 1238 1492 else 1239 1493 // return (flow->get(e.in)); 1240 return ((*flow)[e .in]);1241 } 1242 1243 Number resCap(GraphOutEdgeIt out) const {1244 // return (capacity->get(out)-flow->get(out));1245 return ((*capacity)[out]-(*flow)[out]);1246 }1247 1248 Number resCap(GraphInEdgeIt in) const {1249 // return (flow->get(in));1250 return ((*flow)[in]);1251 }1494 return ((*flow)[e]); 1495 } 1496 1497 // Number resCap(typename Graph::OutEdgeIt out) const { 1498 // // return (capacity->get(out)-flow->get(out)); 1499 // return ((*capacity)[out]-(*flow)[out]); 1500 // } 1501 1502 // Number resCap(typename Graph::InEdgeIt in) const { 1503 // // return (flow->get(in)); 1504 // return ((*flow)[in]); 1505 // } 1252 1506 1253 1507 // template<typename T> class NodeMap : public Graph::NodeMap<T> { … … 1276 1530 EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } 1277 1531 void set(Edge e, T a) { 1278 if (e. out_or_in)1532 if (e.forward) 1279 1533 forward_map.set(e.out, a); 1280 1534 else … … 1282 1536 } 1283 1537 T operator[](Edge e) const { 1284 if (e. out_or_in)1538 if (e.forward) 1285 1539 return forward_map[e.out]; 1286 1540 else … … 1296 1550 }; 1297 1551 1552 1553 1554 // template<typename Graph, typename Number, typename FlowMap, typename CapacityMap> 1555 // class ResGraphWrapper : public GraphWrapper<Graph> { 1556 // protected: 1557 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 1558 // typedef typename Graph::InEdgeIt GraphInEdgeIt; 1559 // typedef typename Graph::Edge GraphEdge; 1560 // FlowMap* flow; 1561 // const CapacityMap* capacity; 1562 // public: 1563 1564 // ResGraphWrapper(Graph& _graph, FlowMap& _flow, 1565 // const CapacityMap& _capacity) : 1566 // GraphWrapper<Graph>(_graph), flow(&_flow), capacity(&_capacity) { } 1567 1568 // class Edge; 1569 // class OutEdgeIt; 1570 // friend class Edge; 1571 // friend class OutEdgeIt; 1572 1573 // typedef typename GraphWrapper<Graph>::Node Node; 1574 // typedef typename GraphWrapper<Graph>::NodeIt NodeIt; 1575 // class Edge { 1576 // friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 1577 // protected: 1578 // bool out_or_in; //true, iff out 1579 // GraphOutEdgeIt out; 1580 // GraphInEdgeIt in; 1581 // public: 1582 // Edge() : out_or_in(true) { } 1583 // Edge(const Invalid& i) : out_or_in(false), out(), in(i) { } 1584 // // bool valid() const { 1585 // // return out_or_in && out.valid() || in.valid(); } 1586 // friend bool operator==(const Edge& u, const Edge& v) { 1587 // if (v.out_or_in) 1588 // return (u.out_or_in && u.out==v.out); 1589 // else 1590 // return (!u.out_or_in && u.in==v.in); 1591 // } 1592 // friend bool operator!=(const Edge& u, const Edge& v) { 1593 // if (v.out_or_in) 1594 // return (!u.out_or_in || u.out!=v.out); 1595 // else 1596 // return (u.out_or_in || u.in!=v.in); 1597 // } 1598 // operator GraphEdge() const { 1599 // if (out_or_in) return(out); else return(in); 1600 // } 1601 // }; 1602 // class OutEdgeIt : public Edge { 1603 // friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 1604 // public: 1605 // OutEdgeIt() { } 1606 // //FIXME 1607 // OutEdgeIt(const Edge& e) : Edge(e) { } 1608 // OutEdgeIt(const Invalid& i) : Edge(i) { } 1609 // OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() { 1610 // resG.graph->first(out, v); 1611 // while( resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } 1612 // if (!resG.graph->valid(out)) { 1613 // out_or_in=0; 1614 // resG.graph->first(in, v); 1615 // while( resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } 1616 // } 1617 // } 1618 // // public: 1619 // // OutEdgeIt& operator++() { 1620 // // if (out_or_in) { 1621 // // Node v=/*resG->*/G->aNode(out); 1622 // // ++out; 1623 // // while( out.valid() && !(Edge::resCap()>0) ) { ++out; } 1624 // // if (!out.valid()) { 1625 // // out_or_in=0; 1626 // // G->first(in, v); 1627 // // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } 1628 // // } 1629 // // } else { 1630 // // ++in; 1631 // // while( in.valid() && !(Edge::resCap()>0) ) { ++in; } 1632 // // } 1633 // // return *this; 1634 // // } 1635 // }; 1636 1637 // //FIXME This is just for having InEdgeIt 1638 // // class InEdgeIt : public Edge { }; 1639 1640 // class EdgeIt : public Edge { 1641 // friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>; 1642 // NodeIt v; 1643 // public: 1644 // EdgeIt() { } 1645 // //EdgeIt(const EdgeIt& e) : Edge(e), v(e.v) { } 1646 // EdgeIt(const Invalid& i) : Edge(i) { } 1647 // EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() { 1648 // resG.graph->first(v); 1649 // if (resG.graph->valid(v)) resG.graph->first(out, v); else out=INVALID; 1650 // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } 1651 // while (resG.graph->valid(v) && !resG.graph->valid(out)) { 1652 // resG.graph->next(v); 1653 // if (resG.graph->valid(v)) resG.graph->first(out, v); 1654 // while (resG.graph->valid(out) && !(resG.resCap(out)>0) ) { resG.graph->next(out); } 1655 // } 1656 // if (!resG.graph->valid(out)) { 1657 // out_or_in=0; 1658 // resG.graph->first(v); 1659 // if (resG.graph->valid(v)) resG.graph->first(in, v); else in=INVALID; 1660 // while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } 1661 // while (resG.graph->valid(v) && !resG.graph->valid(in)) { 1662 // resG.graph->next(v); 1663 // if (resG.graph->valid(v)) resG.graph->first(in, v); 1664 // while (resG.graph->valid(in) && !(resG.resCap(in)>0) ) { resG.graph->next(in); } 1665 // } 1666 // } 1667 // } 1668 // // EdgeIt& operator++() { 1669 // // if (out_or_in) { 1670 // // ++out; 1671 // // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } 1672 // // while (v.valid() && !out.valid()) { 1673 // // ++v; 1674 // // if (v.valid()) G->first(out, v); 1675 // // while (out.valid() && !(Edge::resCap()>0) ) { ++out; } 1676 // // } 1677 // // if (!out.valid()) { 1678 // // out_or_in=0; 1679 // // G->first(v); 1680 // // if (v.valid()) G->first(in, v); else in=GraphInEdgeIt(); 1681 // // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } 1682 // // while (v.valid() && !in.valid()) { 1683 // // ++v; 1684 // // if (v.valid()) G->first(in, v); 1685 // // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } 1686 // // } 1687 // // } 1688 // // } else { 1689 // // ++in; 1690 // // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } 1691 // // while (v.valid() && !in.valid()) { 1692 // // ++v; 1693 // // if (v.valid()) G->first(in, v); 1694 // // while (in.valid() && !(Edge::resCap()>0) ) { ++in; } 1695 // // } 1696 // // } 1697 // // return *this; 1698 // // } 1699 // }; 1700 1701 // NodeIt& first(NodeIt& i) const { 1702 // i=NodeIt(*this); 1703 // return i; 1704 // } 1705 // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 1706 // i=OutEdgeIt(*this, p); 1707 // return i; 1708 // } 1709 // //FIXME Not yet implemented 1710 // //InEdgeIt& first(InEdgeIt& i, const Node& p) const { 1711 // //i=InEdgeIt(*this, p); 1712 // // return i; 1713 // //} 1714 // EdgeIt& first(EdgeIt& e) const { 1715 // e=EdgeIt(*this); 1716 // return e; 1717 // } 1718 1719 // NodeIt& next(NodeIt& n) const { graph->next(n); return n; } 1720 // OutEdgeIt& next(OutEdgeIt& e) const { 1721 // if (e.out_or_in) { 1722 // Node v=graph->aNode(e.out); 1723 // graph->next(e.out); 1724 // while( graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } 1725 // if (!graph->valid(e.out)) { 1726 // e.out_or_in=0; 1727 // graph->first(e.in, v); 1728 // while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1729 // } 1730 // } else { 1731 // graph->next(e.in); 1732 // while( graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1733 // } 1734 // return e; 1735 // } 1736 // //FIXME Not yet implemented 1737 // //InEdgeIt& next(InEdgeIt& e) const { 1738 // // return e; 1739 // //} 1740 // EdgeIt& next(EdgeIt& e) const { 1741 // if (e.out_or_in) { 1742 // graph->next(e.out); 1743 // while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } 1744 // while (graph->valid(e.v) && !graph->valid(e.out)) { 1745 // graph->next(e.v); 1746 // if (graph->valid(e.v)) graph->first(e.out, e.v); 1747 // while (graph->valid(e.out) && !(resCap(e.out)>0) ) { graph->next(e.out); } 1748 // } 1749 // if (!graph->valid(e.out)) { 1750 // e.out_or_in=0; 1751 // graph->first(e.v); 1752 // if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=INVALID; 1753 // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1754 // while (graph->valid(e.v) && !graph->valid(e.in)) { 1755 // graph->next(e.v); 1756 // if (graph->valid(e.v)) graph->first(e.in, e.v); 1757 // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1758 // } 1759 // } 1760 // } else { 1761 // graph->next(e.in); 1762 // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1763 // while (graph->valid(e.v) && !graph->valid(e.in)) { 1764 // graph->next(e.v); 1765 // if (graph->valid(e.v)) graph->first(e.in, e.v); 1766 // while (graph->valid(e.in) && !(resCap(e.in)>0) ) { graph->next(e.in); } 1767 // } 1768 // } 1769 // return e; 1770 // } 1771 1772 1773 // template< typename It > 1774 // It first() const { 1775 // It e; 1776 // first(e); 1777 // return e; 1778 // } 1779 1780 // template< typename It > 1781 // It first(Node v) const { 1782 // It e; 1783 // first(e, v); 1784 // return e; 1785 // } 1786 1787 // Node tail(Edge e) const { 1788 // return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } 1789 // Node head(Edge e) const { 1790 // return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } 1791 1792 // Node aNode(OutEdgeIt e) const { 1793 // return ((e.out_or_in) ? graph->aNode(e.out) : graph->aNode(e.in)); } 1794 // Node bNode(OutEdgeIt e) const { 1795 // return ((e.out_or_in) ? graph->bNode(e.out) : graph->bNode(e.in)); } 1796 1797 // int nodeNum() const { return graph->nodeNum(); } 1798 // //FIXME 1799 // //int edgeNum() const { return graph->edgeNum(); } 1800 1801 1802 // int id(Node v) const { return graph->id(v); } 1803 1804 // bool valid(Node n) const { return graph->valid(n); } 1805 // bool valid(Edge e) const { 1806 // return e.out_or_in ? graph->valid(e.out) : graph->valid(e.in); } 1807 1808 // void augment(const Edge& e, Number a) const { 1809 // if (e.out_or_in) 1810 // // flow->set(e.out, flow->get(e.out)+a); 1811 // flow->set(e.out, (*flow)[e.out]+a); 1812 // else 1813 // // flow->set(e.in, flow->get(e.in)-a); 1814 // flow->set(e.in, (*flow)[e.in]-a); 1815 // } 1816 1817 // Number resCap(const Edge& e) const { 1818 // if (e.out_or_in) 1819 // // return (capacity->get(e.out)-flow->get(e.out)); 1820 // return ((*capacity)[e.out]-(*flow)[e.out]); 1821 // else 1822 // // return (flow->get(e.in)); 1823 // return ((*flow)[e.in]); 1824 // } 1825 1826 // Number resCap(GraphOutEdgeIt out) const { 1827 // // return (capacity->get(out)-flow->get(out)); 1828 // return ((*capacity)[out]-(*flow)[out]); 1829 // } 1830 1831 // Number resCap(GraphInEdgeIt in) const { 1832 // // return (flow->get(in)); 1833 // return ((*flow)[in]); 1834 // } 1835 1836 // // template<typename T> class NodeMap : public Graph::NodeMap<T> { 1837 // // public: 1838 // // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) 1839 // // : Graph::NodeMap<T>(_G.gw) { } 1840 // // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, 1841 // // T a) : Graph::NodeMap<T>(_G.gw, a) { } 1842 // // }; 1843 1844 // // template <typename T> 1845 // // class NodeMap { 1846 // // typename Graph::NodeMap<T> node_map; 1847 // // public: 1848 // // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.graph)) { } 1849 // // NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.graph), a) { } 1850 // // void set(Node nit, T a) { node_map.set(nit, a); } 1851 // // T get(Node nit) const { return node_map.get(nit); } 1852 // // }; 1853 1854 // template <typename T> 1855 // class EdgeMap { 1856 // typename Graph::EdgeMap<T> forward_map, backward_map; 1857 // public: 1858 // EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { } 1859 // EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { } 1860 // void set(Edge e, T a) { 1861 // if (e.out_or_in) 1862 // forward_map.set(e.out, a); 1863 // else 1864 // backward_map.set(e.in, a); 1865 // } 1866 // T operator[](Edge e) const { 1867 // if (e.out_or_in) 1868 // return forward_map[e.out]; 1869 // else 1870 // return backward_map[e.in]; 1871 // } 1872 // // T get(Edge e) const { 1873 // // if (e.out_or_in) 1874 // // return forward_map.get(e.out); 1875 // // else 1876 // // return backward_map.get(e.in); 1877 // // } 1878 // }; 1879 // }; 1880 1881 1298 1882 //ErasingFirstGraphWrapper for blocking flows 1299 1883 template<typename Graph, typename FirstOutEdgesMap> … … 1306 1890 GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 1307 1891 1308 typedef typename Graph::Node Node; 1309 class NodeIt : public Graph::NodeIt { 1310 public: 1892 typedef typename GraphWrapper<Graph>::Node Node; 1893 class NodeIt { 1894 friend class GraphWrapper<Graph>; 1895 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; 1896 typename Graph::NodeIt n; 1897 public: 1311 1898 NodeIt() { } 1312 NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }1313 NodeIt(const Invalid& i) : Graph::NodeIt(i) { }1899 NodeIt(const typename Graph::NodeIt& _n) : n(_n) { } 1900 NodeIt(const Invalid& i) : n(i) { } 1314 1901 NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 1315 Graph::NodeIt(*(_G.graph)) { } 1902 n(*(_G.graph)) { } 1903 operator Node() const { return Node(typename Graph::Node(n)); } 1316 1904 }; 1317 typedef typename Graph::Edge Edge; 1318 class OutEdgeIt : public Graph::OutEdgeIt { 1905 typedef typename GraphWrapper<Graph>::Edge Edge; 1906 class OutEdgeIt { 1907 friend class GraphWrapper<Graph>; 1908 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; 1909 // typedef typename Graph::OutEdgeIt GraphOutEdgeIt; 1910 typename Graph::OutEdgeIt e; 1319 1911 public: 1320 1912 OutEdgeIt() { } 1321 OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }1322 OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }1913 OutEdgeIt(const typename Graph::OutEdgeIt& _e) : e(_e) { } 1914 OutEdgeIt(const Invalid& i) : e(i) { } 1323 1915 OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 1324 const Node& n) : 1325 Graph::OutEdgeIt((*_G.first_out_edges)[n]) { } 1916 const Node& _n) : 1917 e((*_G.first_out_edges)[_n]) { } 1918 operator Edge() const { return Edge(typename Graph::Edge(e)); } 1326 1919 }; 1327 class InEdgeIt : public Graph::InEdgeIt { 1920 class InEdgeIt { 1921 friend class GraphWrapper<Graph>; 1922 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; 1923 // typedef typename Graph::InEdgeIt GraphInEdgeIt; 1924 typename Graph::InEdgeIt e; 1328 1925 public: 1329 1926 InEdgeIt() { } 1330 InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }1331 InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }1927 InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { } 1928 InEdgeIt(const Invalid& i) : e(i) { } 1332 1929 InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 1333 const Node& n) : 1334 Graph::InEdgeIt(*(_G.graph), n) { } 1930 const Node& _n) : 1931 e(*(_G.graph), typename Graph::Node(_n)) { } 1932 operator Edge() const { return Edge(typename Graph::Edge(e)); } 1335 1933 }; 1336 1934 //typedef typename Graph::SymEdgeIt SymEdgeIt; 1337 class EdgeIt : public Graph::EdgeIt { 1935 class EdgeIt { 1936 friend class GraphWrapper<Graph>; 1937 friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>; 1938 // typedef typename Graph::EdgeIt GraphEdgeIt; 1939 typename Graph::EdgeIt e; 1338 1940 public: 1339 1941 EdgeIt() { } 1340 EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }1341 EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }1942 EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { } 1943 EdgeIt(const Invalid& i) : e(i) { } 1342 1944 EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 1343 Graph::EdgeIt(*(_G.graph)) { } 1945 e(*(_G.graph)) { } 1946 operator Edge() const { return Edge(typename Graph::Edge(e)); } 1344 1947 }; 1345 1948 1346 NodeIt& first(NodeIt& i) const { 1347 i=NodeIt(*this); 1348 return i; 1349 } 1350 OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { 1351 i=OutEdgeIt(*this, n); 1352 // i=(*first_out_edges)[n]; 1353 return i; 1354 } 1355 InEdgeIt& first(InEdgeIt& i, const Node& n) const { 1356 i=InEdgeIt(*this, n); 1357 return i; 1358 } 1359 EdgeIt& first(EdgeIt& i) const { 1360 i=EdgeIt(*this); 1361 return i; 1949 NodeIt& first(NodeIt& i) const { 1950 i=NodeIt(*this); return i; 1951 } 1952 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 1953 i=OutEdgeIt(*this, p); return i; 1954 } 1955 InEdgeIt& first(InEdgeIt& i, const Node& p) const { 1956 i=InEdgeIt(*this, p); return i; 1957 } 1958 EdgeIt& first(EdgeIt& i) const { 1959 i=EdgeIt(*this); return i; 1362 1960 } 1363 1961 … … 1381 1979 1382 1980 1383 NodeIt& next(NodeIt& i) const { 1384 graph->next(i); 1385 return i; 1386 } 1387 OutEdgeIt& next(OutEdgeIt& i) const { 1388 graph->next(i); 1389 return i; 1390 } 1391 InEdgeIt& next(InEdgeIt& i) const { 1392 graph->next(i); 1393 return i; 1394 } 1395 EdgeIt& next(EdgeIt& i) const { 1396 graph->next(i); 1397 return i; 1398 } 1981 NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; } 1982 OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; } 1983 InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; } 1984 EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; } 1985 1986 Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); } 1987 Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); } 1988 Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); } 1989 Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); } 1399 1990 1400 1991 // template<typename I> I& next(I &i) const { … … 1412 2003 OutEdgeIt f=e; 1413 2004 this->next(f); 1414 first_out_edges->set(this->tail(e), f );2005 first_out_edges->set(this->tail(e), f.e); 1415 2006 } 1416 2007 }; 2008 2009 // //ErasingFirstGraphWrapper for blocking flows 2010 // template<typename Graph, typename FirstOutEdgesMap> 2011 // class ErasingFirstGraphWrapper : public GraphWrapper<Graph> { 2012 // protected: 2013 // FirstOutEdgesMap* first_out_edges; 2014 // public: 2015 // ErasingFirstGraphWrapper(Graph& _graph, 2016 // FirstOutEdgesMap& _first_out_edges) : 2017 // GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 2018 2019 // typedef typename Graph::Node Node; 2020 // class NodeIt : public Graph::NodeIt { 2021 // public: 2022 // NodeIt() { } 2023 // NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { } 2024 // NodeIt(const Invalid& i) : Graph::NodeIt(i) { } 2025 // NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 2026 // Graph::NodeIt(*(_G.graph)) { } 2027 // }; 2028 // typedef typename Graph::Edge Edge; 2029 // class OutEdgeIt : public Graph::OutEdgeIt { 2030 // public: 2031 // OutEdgeIt() { } 2032 // OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { } 2033 // OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { } 2034 // OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 2035 // const Node& n) : 2036 // Graph::OutEdgeIt((*_G.first_out_edges)[n]) { } 2037 // }; 2038 // class InEdgeIt : public Graph::InEdgeIt { 2039 // public: 2040 // InEdgeIt() { } 2041 // InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { } 2042 // InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { } 2043 // InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G, 2044 // const Node& n) : 2045 // Graph::InEdgeIt(*(_G.graph), n) { } 2046 // }; 2047 // //typedef typename Graph::SymEdgeIt SymEdgeIt; 2048 // class EdgeIt : public Graph::EdgeIt { 2049 // public: 2050 // EdgeIt() { } 2051 // EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { } 2052 // EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { } 2053 // EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) : 2054 // Graph::EdgeIt(*(_G.graph)) { } 2055 // }; 2056 2057 // NodeIt& first(NodeIt& i) const { 2058 // i=NodeIt(*this); 2059 // return i; 2060 // } 2061 // OutEdgeIt& first(OutEdgeIt& i, const Node& n) const { 2062 // i=OutEdgeIt(*this, n); 2063 // // i=(*first_out_edges)[n]; 2064 // return i; 2065 // } 2066 // InEdgeIt& first(InEdgeIt& i, const Node& n) const { 2067 // i=InEdgeIt(*this, n); 2068 // return i; 2069 // } 2070 // EdgeIt& first(EdgeIt& i) const { 2071 // i=EdgeIt(*this); 2072 // return i; 2073 // } 2074 2075 // // template<typename I> I& first(I& i) const { 2076 // // graph->first(i); 2077 // // return i; 2078 // // } 2079 // // OutEdgeIt& first(OutEdgeIt& e, const Node& n) const { 2080 // // // e=first_out_edges->get(n); 2081 // // e=(*first_out_edges)[n]; 2082 // // return e; 2083 // // } 2084 // // template<typename I, typename P> I& first(I& i, const P& p) const { 2085 // // graph->first(i, p); 2086 // // return i; 2087 // // } 2088 2089 // //template<typename I> I getNext(const I& i) const { 2090 // // return gw.getNext(i); 2091 // //} 2092 2093 2094 // NodeIt& next(NodeIt& i) const { 2095 // graph->next(i); 2096 // return i; 2097 // } 2098 // OutEdgeIt& next(OutEdgeIt& i) const { 2099 // graph->next(i); 2100 // return i; 2101 // } 2102 // InEdgeIt& next(InEdgeIt& i) const { 2103 // graph->next(i); 2104 // return i; 2105 // } 2106 // EdgeIt& next(EdgeIt& i) const { 2107 // graph->next(i); 2108 // return i; 2109 // } 2110 2111 // // template<typename I> I& next(I &i) const { 2112 // // graph->next(i); 2113 // // return i; 2114 // // } 2115 2116 // template< typename It > It first() const { 2117 // It e; this->first(e); return e; } 2118 2119 // template< typename It > It first(const Node& v) const { 2120 // It e; this->first(e, v); return e; } 2121 2122 // void erase(const OutEdgeIt& e) const { 2123 // OutEdgeIt f=e; 2124 // this->next(f); 2125 // first_out_edges->set(this->tail(e), f); 2126 // } 2127 // }; 2128 1417 2129 1418 2130 // // FIXME: comparison should be made better!!!
Note: See TracChangeset
for help on using the changeset viewer.
