Changeset 416:76287c8caa26 in lemon-1.2 for lemon
- Timestamp:
- 11/30/08 19:18:32 (16 years ago)
- Branch:
- default
- Phase:
- public
- Location:
- lemon
- Files:
-
- 1 deleted
- 3 edited
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r414 r416 17 17 18 18 lemon_HEADERS += \ 19 lemon/adaptors.h \ 19 20 lemon/arg_parser.h \ 20 21 lemon/assert.h \ -
lemon/adaptors.h
r415 r416 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 17 17 */ 18 18 19 #ifndef LEMON_ DIGRAPH_ADAPTOR_H20 #define LEMON_ DIGRAPH_ADAPTOR_H21 22 /// \ingroup graph_adaptors23 /// \file24 /// \brief Several digraph adaptors.19 #ifndef LEMON_ADAPTORS_H 20 #define LEMON_ADAPTORS_H 21 22 /// \ingroup graph_adaptors 23 /// \file 24 /// \brief Several graph adaptors 25 25 /// 26 /// This file contains several useful digraph adaptor classes.26 /// This file contains several useful adaptors for digraphs and graphs. 27 27 28 28 #include <lemon/core.h> … … 30 30 #include <lemon/bits/variant.h> 31 31 32 #include <lemon/bits/base_extender.h>33 32 #include <lemon/bits/graph_adaptor_extender.h> 34 #include <lemon/bits/graph_extender.h>35 33 #include <lemon/tolerance.h> 36 34 … … 56 54 typedef typename Digraph::Node Node; 57 55 typedef typename Digraph::Arc Arc; 58 56 59 57 void first(Node& i) const { _digraph->first(i); } 60 58 void first(Arc& i) const { _digraph->first(i); } … … 72 70 typedef NodeNumTagIndicator<Digraph> NodeNumTag; 73 71 int nodeNum() const { return _digraph->nodeNum(); } 74 72 75 73 typedef EdgeNumTagIndicator<Digraph> EdgeNumTag; 76 74 int arcNum() const { return _digraph->arcNum(); } … … 80 78 return _digraph->findArc(u, v, prev); 81 79 } 82 80 83 81 Node addNode() { return _digraph->addNode(); } 84 82 Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); } … … 86 84 void erase(const Node& n) const { _digraph->erase(n); } 87 85 void erase(const Arc& a) const { _digraph->erase(a); } 88 86 89 87 void clear() const { _digraph->clear(); } 90 88 91 89 int id(const Node& n) const { return _digraph->id(n); } 92 90 int id(const Arc& a) const { return _digraph->id(a); } … … 99 97 100 98 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier; 101 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 99 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 102 100 103 101 typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier; 104 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); } 105 102 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); } 103 106 104 template <typename _Value> 107 105 class NodeMap : public Digraph::template NodeMap<_Value> { … … 110 108 typedef typename Digraph::template NodeMap<_Value> Parent; 111 109 112 explicit NodeMap(const Adaptor& adaptor) 113 110 explicit NodeMap(const Adaptor& adaptor) 111 : Parent(*adaptor._digraph) {} 114 112 115 113 NodeMap(const Adaptor& adaptor, const _Value& value) 116 114 : Parent(*adaptor._digraph, value) { } 117 115 118 116 private: … … 126 124 return *this; 127 125 } 128 126 129 127 }; 130 128 … … 132 130 class ArcMap : public Digraph::template ArcMap<_Value> { 133 131 public: 134 132 135 133 typedef typename Digraph::template ArcMap<_Value> Parent; 136 137 explicit ArcMap(const Adaptor& adaptor) 138 134 135 explicit ArcMap(const Adaptor& adaptor) 136 : Parent(*adaptor._digraph) {} 139 137 140 138 ArcMap(const Adaptor& adaptor, const _Value& value) 141 139 : Parent(*adaptor._digraph, value) {} 142 140 143 141 private: … … 156 154 }; 157 155 156 template<typename _Graph> 157 class GraphAdaptorBase { 158 public: 159 typedef _Graph Graph; 160 typedef Graph ParentGraph; 161 162 protected: 163 Graph* _graph; 164 165 GraphAdaptorBase() : _graph(0) {} 166 167 void setGraph(Graph& graph) { _graph = &graph; } 168 169 public: 170 GraphAdaptorBase(Graph& graph) : _graph(&graph) {} 171 172 typedef typename Graph::Node Node; 173 typedef typename Graph::Arc Arc; 174 typedef typename Graph::Edge Edge; 175 176 void first(Node& i) const { _graph->first(i); } 177 void first(Arc& i) const { _graph->first(i); } 178 void first(Edge& i) const { _graph->first(i); } 179 void firstIn(Arc& i, const Node& n) const { _graph->firstIn(i, n); } 180 void firstOut(Arc& i, const Node& n ) const { _graph->firstOut(i, n); } 181 void firstInc(Edge &i, bool &d, const Node &n) const { 182 _graph->firstInc(i, d, n); 183 } 184 185 void next(Node& i) const { _graph->next(i); } 186 void next(Arc& i) const { _graph->next(i); } 187 void next(Edge& i) const { _graph->next(i); } 188 void nextIn(Arc& i) const { _graph->nextIn(i); } 189 void nextOut(Arc& i) const { _graph->nextOut(i); } 190 void nextInc(Edge &i, bool &d) const { _graph->nextInc(i, d); } 191 192 Node u(const Edge& e) const { return _graph->u(e); } 193 Node v(const Edge& e) const { return _graph->v(e); } 194 195 Node source(const Arc& a) const { return _graph->source(a); } 196 Node target(const Arc& a) const { return _graph->target(a); } 197 198 typedef NodeNumTagIndicator<Graph> NodeNumTag; 199 int nodeNum() const { return _graph->nodeNum(); } 200 201 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; 202 int arcNum() const { return _graph->arcNum(); } 203 int edgeNum() const { return _graph->edgeNum(); } 204 205 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 206 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) { 207 return _graph->findArc(u, v, prev); 208 } 209 Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) { 210 return _graph->findEdge(u, v, prev); 211 } 212 213 Node addNode() { return _graph->addNode(); } 214 Edge addEdge(const Node& u, const Node& v) { return _graph->addEdge(u, v); } 215 216 void erase(const Node& i) { _graph->erase(i); } 217 void erase(const Edge& i) { _graph->erase(i); } 218 219 void clear() { _graph->clear(); } 220 221 bool direction(const Arc& a) const { return _graph->direction(a); } 222 Arc direct(const Edge& e, bool d) const { return _graph->direct(e, d); } 223 224 int id(const Node& v) const { return _graph->id(v); } 225 int id(const Arc& a) const { return _graph->id(a); } 226 int id(const Edge& e) const { return _graph->id(e); } 227 228 Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); } 229 Arc arcFromId(int ix) const { return _graph->arcFromId(ix); } 230 Edge edgeFromId(int ix) const { return _graph->edgeFromId(ix); } 231 232 int maxNodeId() const { return _graph->maxNodeId(); } 233 int maxArcId() const { return _graph->maxArcId(); } 234 int maxEdgeId() const { return _graph->maxEdgeId(); } 235 236 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; 237 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 238 239 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier; 240 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 241 242 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier; 243 EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); } 244 245 template <typename _Value> 246 class NodeMap : public Graph::template NodeMap<_Value> { 247 public: 248 typedef typename Graph::template NodeMap<_Value> Parent; 249 explicit NodeMap(const GraphAdaptorBase<Graph>& adapter) 250 : Parent(*adapter._graph) {} 251 NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) 252 : Parent(*adapter._graph, value) {} 253 254 private: 255 NodeMap& operator=(const NodeMap& cmap) { 256 return operator=<NodeMap>(cmap); 257 } 258 259 template <typename CMap> 260 NodeMap& operator=(const CMap& cmap) { 261 Parent::operator=(cmap); 262 return *this; 263 } 264 265 }; 266 267 template <typename _Value> 268 class ArcMap : public Graph::template ArcMap<_Value> { 269 public: 270 typedef typename Graph::template ArcMap<_Value> Parent; 271 explicit ArcMap(const GraphAdaptorBase<Graph>& adapter) 272 : Parent(*adapter._graph) {} 273 ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) 274 : Parent(*adapter._graph, value) {} 275 276 private: 277 ArcMap& operator=(const ArcMap& cmap) { 278 return operator=<ArcMap>(cmap); 279 } 280 281 template <typename CMap> 282 ArcMap& operator=(const CMap& cmap) { 283 Parent::operator=(cmap); 284 return *this; 285 } 286 }; 287 288 template <typename _Value> 289 class EdgeMap : public Graph::template EdgeMap<_Value> { 290 public: 291 typedef typename Graph::template EdgeMap<_Value> Parent; 292 explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter) 293 : Parent(*adapter._graph) {} 294 EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) 295 : Parent(*adapter._graph, value) {} 296 297 private: 298 EdgeMap& operator=(const EdgeMap& cmap) { 299 return operator=<EdgeMap>(cmap); 300 } 301 302 template <typename CMap> 303 EdgeMap& operator=(const CMap& cmap) { 304 Parent::operator=(cmap); 305 return *this; 306 } 307 }; 308 309 }; 158 310 159 311 template <typename _Digraph> 160 class Rev DigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {312 class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> { 161 313 public: 162 314 typedef _Digraph Digraph; 163 315 typedef DigraphAdaptorBase<_Digraph> Parent; 164 316 protected: 165 Rev DigraphAdaptorBase() : Parent() { }317 ReverseDigraphBase() : Parent() { } 166 318 public: 167 319 typedef typename Parent::Node Node; … … 177 329 Node target(const Arc& a) const { return Parent::source(a); } 178 330 331 Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); } 332 179 333 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 180 Arc findArc(const Node& u, const Node& v, 181 334 Arc findArc(const Node& u, const Node& v, 335 const Arc& prev = INVALID) { 182 336 return Parent::findArc(v, u, prev); 183 337 } 184 338 185 339 }; 186 187 188 ///\ingroup graph_adaptors 189 /// 190 ///\brief A digraph adaptor which reverses the orientation of the arcs. 191 /// 192 /// If \c g is defined as 193 ///\code 194 /// ListDigraph dg; 195 ///\endcode 196 /// then 197 ///\code 198 /// RevDigraphAdaptor<ListDigraph> dga(dg); 199 ///\endcode 200 /// implements the digraph obtained from \c dg by 201 /// reversing the orientation of its arcs. 202 /// 203 /// A good example of using RevDigraphAdaptor is to decide whether 204 /// the directed graph is strongly connected or not. The digraph is 205 /// strongly connected iff each node is reachable from one node and 206 /// this node is reachable from the others. Instead of this 207 /// condition we use a slightly different, from one node each node 208 /// is reachable both in the digraph and the reversed digraph. Now 209 /// this condition can be checked with the Dfs algorithm and the 210 /// RevDigraphAdaptor class. 211 /// 212 /// The implementation: 213 ///\code 214 /// bool stronglyConnected(const Digraph& digraph) { 215 /// if (NodeIt(digraph) == INVALID) return true; 216 /// Dfs<Digraph> dfs(digraph); 217 /// dfs.run(NodeIt(digraph)); 218 /// for (NodeIt it(digraph); it != INVALID; ++it) { 219 /// if (!dfs.reached(it)) { 220 /// return false; 221 /// } 222 /// } 223 /// typedef RevDigraphAdaptor<const Digraph> RDigraph; 224 /// RDigraph rdigraph(digraph); 225 /// DfsVisit<RDigraph> rdfs(rdigraph); 226 /// rdfs.run(NodeIt(digraph)); 227 /// for (NodeIt it(digraph); it != INVALID; ++it) { 228 /// if (!rdfs.reached(it)) { 229 /// return false; 230 /// } 231 /// } 232 /// return true; 233 /// } 234 ///\endcode 340 341 /// \ingroup graph_adaptors 342 /// 343 /// \brief A digraph adaptor which reverses the orientation of the arcs. 344 /// 345 /// ReverseDigraph reverses the arcs in the adapted digraph. The 346 /// SubDigraph is conform to the \ref concepts::Digraph 347 /// "Digraph concept". 348 /// 349 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 350 /// "Digraph concept". The type can be specified to be const. 235 351 template<typename _Digraph> 236 class Rev DigraphAdaptor :237 public DigraphAdaptorExtender<Rev DigraphAdaptorBase<_Digraph> > {352 class ReverseDigraph : 353 public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > { 238 354 public: 239 355 typedef _Digraph Digraph; 240 356 typedef DigraphAdaptorExtender< 241 Rev DigraphAdaptorBase<_Digraph> > Parent;357 ReverseDigraphBase<_Digraph> > Parent; 242 358 protected: 243 Rev DigraphAdaptor() { }359 ReverseDigraph() { } 244 360 public: 245 361 246 362 /// \brief Constructor 247 363 /// 248 /// Creates a reverse graph adaptor for the given digraph249 explicit Rev DigraphAdaptor(Digraph& digraph) {250 Parent::setDigraph(digraph); 364 /// Creates a reverse digraph adaptor for the given digraph 365 explicit ReverseDigraph(Digraph& digraph) { 366 Parent::setDigraph(digraph); 251 367 } 252 368 }; … … 256 372 /// Just gives back a reverse digraph adaptor 257 373 template<typename Digraph> 258 RevDigraphAdaptor<const Digraph> 259 revDigraphAdaptor(const Digraph& digraph) { 260 return RevDigraphAdaptor<const Digraph>(digraph); 374 ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) { 375 return ReverseDigraph<const Digraph>(digraph); 261 376 } 262 377 263 template <typename _Digraph, typename _NodeFilterMap, 264 typename _ArcFilterMap, boolchecked = true>265 class SubDigraph AdaptorBase : public DigraphAdaptorBase<_Digraph> {378 template <typename _Digraph, typename _NodeFilterMap, 379 typename _ArcFilterMap, bool _checked = true> 380 class SubDigraphBase : public DigraphAdaptorBase<_Digraph> { 266 381 public: 267 382 typedef _Digraph Digraph; … … 269 384 typedef _ArcFilterMap ArcFilterMap; 270 385 271 typedef SubDigraph AdaptorBase Adaptor;386 typedef SubDigraphBase Adaptor; 272 387 typedef DigraphAdaptorBase<_Digraph> Parent; 273 388 protected: 274 389 NodeFilterMap* _node_filter; 275 390 ArcFilterMap* _arc_filter; 276 SubDigraph AdaptorBase()391 SubDigraphBase() 277 392 : Parent(), _node_filter(0), _arc_filter(0) { } 278 393 … … 289 404 typedef typename Parent::Arc Arc; 290 405 291 void first(Node& i) const { 292 Parent::first(i); 293 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); 294 } 295 296 void first(Arc& i) const { 297 Parent::first(i); 298 while (i != INVALID && (!(*_arc_filter)[i] 299 || !(*_node_filter)[Parent::source(i)] 300 || !(*_node_filter)[Parent::target(i)])) Parent::next(i); 301 } 302 303 void firstIn(Arc& i, const Node& n) const { 304 Parent::firstIn(i, n); 305 while (i != INVALID && (!(*_arc_filter)[i] 306 || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i); 307 } 308 309 void firstOut(Arc& i, const Node& n) const { 310 Parent::firstOut(i, n); 311 while (i != INVALID && (!(*_arc_filter)[i] 312 || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i); 313 } 314 315 void next(Node& i) const { 316 Parent::next(i); 317 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); 318 } 319 320 void next(Arc& i) const { 321 Parent::next(i); 322 while (i != INVALID && (!(*_arc_filter)[i] 323 || !(*_node_filter)[Parent::source(i)] 324 || !(*_node_filter)[Parent::target(i)])) Parent::next(i); 325 } 326 327 void nextIn(Arc& i) const { 328 Parent::nextIn(i); 329 while (i != INVALID && (!(*_arc_filter)[i] 330 || !(*_node_filter)[Parent::source(i)])) Parent::nextIn(i); 331 } 332 333 void nextOut(Arc& i) const { 334 Parent::nextOut(i); 335 while (i != INVALID && (!(*_arc_filter)[i] 336 || !(*_node_filter)[Parent::target(i)])) Parent::nextOut(i); 406 void first(Node& i) const { 407 Parent::first(i); 408 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); 409 } 410 411 void first(Arc& i) const { 412 Parent::first(i); 413 while (i != INVALID && (!(*_arc_filter)[i] 414 || !(*_node_filter)[Parent::source(i)] 415 || !(*_node_filter)[Parent::target(i)])) 416 Parent::next(i); 417 } 418 419 void firstIn(Arc& i, const Node& n) const { 420 Parent::firstIn(i, n); 421 while (i != INVALID && (!(*_arc_filter)[i] 422 || !(*_node_filter)[Parent::source(i)])) 423 Parent::nextIn(i); 424 } 425 426 void firstOut(Arc& i, const Node& n) const { 427 Parent::firstOut(i, n); 428 while (i != INVALID && (!(*_arc_filter)[i] 429 || !(*_node_filter)[Parent::target(i)])) 430 Parent::nextOut(i); 431 } 432 433 void next(Node& i) const { 434 Parent::next(i); 435 while (i != INVALID && !(*_node_filter)[i]) Parent::next(i); 436 } 437 438 void next(Arc& i) const { 439 Parent::next(i); 440 while (i != INVALID && (!(*_arc_filter)[i] 441 || !(*_node_filter)[Parent::source(i)] 442 || !(*_node_filter)[Parent::target(i)])) 443 Parent::next(i); 444 } 445 446 void nextIn(Arc& i) const { 447 Parent::nextIn(i); 448 while (i != INVALID && (!(*_arc_filter)[i] 449 || !(*_node_filter)[Parent::source(i)])) 450 Parent::nextIn(i); 451 } 452 453 void nextOut(Arc& i) const { 454 Parent::nextOut(i); 455 while (i != INVALID && (!(*_arc_filter)[i] 456 || !(*_node_filter)[Parent::target(i)])) 457 Parent::nextOut(i); 337 458 } 338 459 … … 350 471 351 472 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 352 Arc findArc(const Node& source, const Node& target, 353 473 Arc findArc(const Node& source, const Node& target, 474 const Arc& prev = INVALID) { 354 475 if (!(*_node_filter)[source] || !(*_node_filter)[target]) { 355 476 return INVALID; … … 363 484 364 485 template <typename _Value> 365 class NodeMap : public SubMapExtender<Adaptor, 366 486 class NodeMap : public SubMapExtender<Adaptor, 487 typename Parent::template NodeMap<_Value> > { 367 488 public: 368 489 typedef _Value Value; 369 490 typedef SubMapExtender<Adaptor, typename Parent:: 370 491 template NodeMap<Value> > MapParent; 371 372 NodeMap(const Adaptor& adaptor) 373 374 NodeMap(const Adaptor& adaptor, const Value& value) 375 376 492 493 NodeMap(const Adaptor& adaptor) 494 : MapParent(adaptor) {} 495 NodeMap(const Adaptor& adaptor, const Value& value) 496 : MapParent(adaptor, value) {} 497 377 498 private: 378 499 NodeMap& operator=(const NodeMap& cmap) { 379 380 } 381 500 return operator=<NodeMap>(cmap); 501 } 502 382 503 template <typename CMap> 383 504 NodeMap& operator=(const CMap& cmap) { 384 505 MapParent::operator=(cmap); 385 506 return *this; 386 507 } 387 508 }; 388 509 389 510 template <typename _Value> 390 class ArcMap : public SubMapExtender<Adaptor, 391 511 class ArcMap : public SubMapExtender<Adaptor, 512 typename Parent::template ArcMap<_Value> > { 392 513 public: 393 514 typedef _Value Value; 394 515 typedef SubMapExtender<Adaptor, typename Parent:: 395 516 template ArcMap<Value> > MapParent; 396 397 ArcMap(const Adaptor& adaptor) 398 399 ArcMap(const Adaptor& adaptor, const Value& value) 400 401 517 518 ArcMap(const Adaptor& adaptor) 519 : MapParent(adaptor) {} 520 ArcMap(const Adaptor& adaptor, const Value& value) 521 : MapParent(adaptor, value) {} 522 402 523 private: 403 524 ArcMap& operator=(const ArcMap& cmap) { 404 405 } 406 525 return operator=<ArcMap>(cmap); 526 } 527 407 528 template <typename CMap> 408 529 ArcMap& operator=(const CMap& cmap) { 409 530 MapParent::operator=(cmap); 410 531 return *this; 411 532 } 412 533 }; … … 415 536 416 537 template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap> 417 class SubDigraph AdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false>538 class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false> 418 539 : public DigraphAdaptorBase<_Digraph> { 419 540 public: … … 422 543 typedef _ArcFilterMap ArcFilterMap; 423 544 424 typedef SubDigraph AdaptorBase Adaptor;545 typedef SubDigraphBase Adaptor; 425 546 typedef DigraphAdaptorBase<Digraph> Parent; 426 547 protected: 427 548 NodeFilterMap* _node_filter; 428 549 ArcFilterMap* _arc_filter; 429 SubDigraph AdaptorBase()550 SubDigraphBase() 430 551 : Parent(), _node_filter(0), _arc_filter(0) { } 431 552 … … 442 563 typedef typename Parent::Arc Arc; 443 564 444 void first(Node& i) const { 445 Parent::first(i); 446 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 447 } 448 449 void first(Arc& i) const { 450 Parent::first(i); 451 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 452 } 453 454 void firstIn(Arc& i, const Node& n) const { 455 Parent::firstIn(i, n); 456 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 457 } 458 459 void firstOut(Arc& i, const Node& n) const { 460 Parent::firstOut(i, n); 461 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 462 } 463 464 void next(Node& i) const { 465 Parent::next(i); 466 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 467 } 468 void next(Arc& i) const { 469 Parent::next(i); 470 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 471 } 472 void nextIn(Arc& i) const { 473 Parent::nextIn(i); 474 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 475 } 476 477 void nextOut(Arc& i) const { 478 Parent::nextOut(i); 479 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 565 void first(Node& i) const { 566 Parent::first(i); 567 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 568 } 569 570 void first(Arc& i) const { 571 Parent::first(i); 572 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 573 } 574 575 void firstIn(Arc& i, const Node& n) const { 576 Parent::firstIn(i, n); 577 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 578 } 579 580 void firstOut(Arc& i, const Node& n) const { 581 Parent::firstOut(i, n); 582 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 583 } 584 585 void next(Node& i) const { 586 Parent::next(i); 587 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 588 } 589 void next(Arc& i) const { 590 Parent::next(i); 591 while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i); 592 } 593 void nextIn(Arc& i) const { 594 Parent::nextIn(i); 595 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i); 596 } 597 598 void nextOut(Arc& i) const { 599 Parent::nextOut(i); 600 while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextOut(i); 480 601 } 481 602 … … 493 614 494 615 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 495 Arc findArc(const Node& source, const Node& target, 496 616 Arc findArc(const Node& source, const Node& target, 617 const Arc& prev = INVALID) { 497 618 if (!(*_node_filter)[source] || !(*_node_filter)[target]) { 498 619 return INVALID; … … 506 627 507 628 template <typename _Value> 508 class NodeMap : public SubMapExtender<Adaptor, 509 629 class NodeMap : public SubMapExtender<Adaptor, 630 typename Parent::template NodeMap<_Value> > { 510 631 public: 511 632 typedef _Value Value; 512 633 typedef SubMapExtender<Adaptor, typename Parent:: 513 634 template NodeMap<Value> > MapParent; 514 515 NodeMap(const Adaptor& adaptor) 516 517 NodeMap(const Adaptor& adaptor, const Value& value) 518 519 635 636 NodeMap(const Adaptor& adaptor) 637 : MapParent(adaptor) {} 638 NodeMap(const Adaptor& adaptor, const Value& value) 639 : MapParent(adaptor, value) {} 640 520 641 private: 521 642 NodeMap& operator=(const NodeMap& cmap) { 522 523 } 524 643 return operator=<NodeMap>(cmap); 644 } 645 525 646 template <typename CMap> 526 647 NodeMap& operator=(const CMap& cmap) { 527 648 MapParent::operator=(cmap); 528 649 return *this; 529 650 } 530 651 }; 531 652 532 653 template <typename _Value> 533 class ArcMap : public SubMapExtender<Adaptor, 534 654 class ArcMap : public SubMapExtender<Adaptor, 655 typename Parent::template ArcMap<_Value> > { 535 656 public: 536 657 typedef _Value Value; 537 658 typedef SubMapExtender<Adaptor, typename Parent:: 538 659 template ArcMap<Value> > MapParent; 539 540 ArcMap(const Adaptor& adaptor) 541 542 ArcMap(const Adaptor& adaptor, const Value& value) 543 544 660 661 ArcMap(const Adaptor& adaptor) 662 : MapParent(adaptor) {} 663 ArcMap(const Adaptor& adaptor, const Value& value) 664 : MapParent(adaptor, value) {} 665 545 666 private: 546 667 ArcMap& operator=(const ArcMap& cmap) { 547 548 } 549 668 return operator=<ArcMap>(cmap); 669 } 670 550 671 template <typename CMap> 551 672 ArcMap& operator=(const CMap& cmap) { 552 673 MapParent::operator=(cmap); 553 674 return *this; 554 675 } 555 676 }; … … 559 680 /// \ingroup graph_adaptors 560 681 /// 561 /// \brief A digraph adaptor for hiding nodes and arcs from a digraph. 562 /// 563 /// SubDigraphAdaptor shows the digraph with filtered node-set and 564 /// arc-set. If the \c checked parameter is true then it filters the arc-set 565 /// respect to the source and target. 566 /// 567 /// If the \c checked template parameter is false then the 568 /// node-iterator cares only the filter on the node-set, and the 569 /// arc-iterator cares only the filter on the arc-set. Therefore 570 /// the arc-map have to filter all arcs which's source or target is 571 /// filtered by the node-filter. 572 ///\code 573 /// typedef ListDigraph Digraph; 574 /// DIGRAPH_TYPEDEFS(Digraph); 575 /// Digraph g; 576 /// Node u=g.addNode(); //node of id 0 577 /// Node v=g.addNode(); //node of id 1 578 /// Arc a=g.addArc(u, v); //arc of id 0 579 /// Arc f=g.addArc(v, u); //arc of id 1 580 /// BoolNodeMap nm(g, true); 581 /// nm.set(u, false); 582 /// BoolArcMap am(g, true); 583 /// am.set(a, false); 584 /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubDGA; 585 /// SubDGA ga(g, nm, am); 586 /// for (SubDGA::NodeIt n(ga); n!=INVALID; ++n) 587 /// std::cout << g.id(n) << std::endl; 588 /// for (SubDGA::ArcIt a(ga); a!=INVALID; ++a) 589 /// std::cout << g.id(a) << std::endl; 590 ///\endcode 591 /// The output of the above code is the following. 592 ///\code 593 /// 1 594 /// 1 595 ///\endcode 596 /// Note that \c n is of type \c SubDGA::NodeIt, but it can be converted to 597 /// \c Digraph::Node that is why \c g.id(n) can be applied. 598 /// 599 /// For other examples see also the documentation of 600 /// NodeSubDigraphAdaptor and ArcSubDigraphAdaptor. 601 template<typename _Digraph, 602 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 603 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>, 604 bool checked = true> 605 class SubDigraphAdaptor : 606 public DigraphAdaptorExtender< 607 SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, checked> > { 682 /// \brief An adaptor for hiding nodes and arcs in a digraph 683 /// 684 /// SubDigraph hides nodes and arcs in a digraph. A bool node map 685 /// and a bool arc map must be specified, which define the filters 686 /// for nodes and arcs. Just the nodes and arcs with true value are 687 /// shown in the subdigraph. The SubDigraph is conform to the \ref 688 /// concepts::Digraph "Digraph concept". If the \c _checked parameter 689 /// is true, then the arcs incident to filtered nodes are also 690 /// filtered out. 691 /// 692 /// \tparam _Digraph It must be conform to the \ref 693 /// concepts::Digraph "Digraph concept". The type can be specified 694 /// to const. 695 /// \tparam _NodeFilterMap A bool valued node map of the the adapted digraph. 696 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted digraph. 697 /// \tparam _checked If the parameter is false then the arc filtering 698 /// is not checked with respect to node filter. Otherwise, each arc 699 /// is automatically filtered, which is incident to a filtered node. 700 /// 701 /// \see FilterNodes 702 /// \see FilterArcs 703 template<typename _Digraph, 704 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 705 typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>, 706 bool _checked = true> 707 class SubDigraph 708 : public DigraphAdaptorExtender< 709 SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, _checked> > { 608 710 public: 609 711 typedef _Digraph Digraph; … … 612 714 613 715 typedef DigraphAdaptorExtender< 614 SubDigraph AdaptorBase<Digraph, NodeFilterMap, ArcFilterMap,checked> >716 SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> > 615 717 Parent; 616 718 … … 619 721 620 722 protected: 621 SubDigraph Adaptor() { }723 SubDigraph() { } 622 724 public: 623 725 624 726 /// \brief Constructor 625 727 /// 626 /// Creates a sub -digraph-adaptorfor the given digraph with728 /// Creates a subdigraph for the given digraph with 627 729 /// given node and arc map filters. 628 SubDigraph Adaptor(Digraph& digraph, NodeFilterMap& node_filter,629 ArcFilterMap& arc_filter) { 730 SubDigraph(Digraph& digraph, NodeFilterMap& node_filter, 731 ArcFilterMap& arc_filter) { 630 732 setDigraph(digraph); 631 733 setNodeFilterMap(node_filter); … … 635 737 /// \brief Hides the node of the graph 636 738 /// 637 /// This function hides \c n in the digraph, i.e. the iteration 638 /// jumps over it. This is done by simply setting the value of \c n 739 /// This function hides \c n in the digraph, i.e. the iteration 740 /// jumps over it. This is done by simply setting the value of \c n 639 741 /// to be false in the corresponding node-map. 640 742 void hide(const Node& n) const { Parent::hide(n); } … … 642 744 /// \brief Hides the arc of the graph 643 745 /// 644 /// This function hides \c a in the digraph, i.e. the iteration 746 /// This function hides \c a in the digraph, i.e. the iteration 645 747 /// jumps over it. This is done by simply setting the value of \c a 646 748 /// to be false in the corresponding arc-map. … … 649 751 /// \brief Unhides the node of the graph 650 752 /// 651 /// The value of \c n is set to be true in the node-map which stores 652 /// hide information. If \c n was hidden previuosly, then it is shown 753 /// The value of \c n is set to be true in the node-map which stores 754 /// hide information. If \c n was hidden previuosly, then it is shown 653 755 /// again 654 756 void unHide(const Node& n) const { Parent::unHide(n); } … … 656 758 /// \brief Unhides the arc of the graph 657 759 /// 658 /// The value of \c a is set to be true in the arc-map which stores 659 /// hide information. If \c a was hidden previuosly, then it is shown 760 /// The value of \c a is set to be true in the arc-map which stores 761 /// hide information. If \c a was hidden previuosly, then it is shown 660 762 /// again 661 763 void unHide(const Arc& a) const { Parent::unHide(a); } … … 675 777 }; 676 778 677 /// \brief Just gives back a sub -digraph-adaptor678 /// 679 /// Just gives back a sub -digraph-adaptor779 /// \brief Just gives back a subdigraph 780 /// 781 /// Just gives back a subdigraph 680 782 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 681 SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap> 682 subDigraphAdaptor(const Digraph& digraph, 683 NodeFilterMap& nfm, ArcFilterMap& afm) { 684 return SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap> 783 SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> 784 subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) { 785 return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> 685 786 (digraph, nfm, afm); 686 787 } 687 788 688 789 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 689 SubDigraph Adaptor<const Digraph, const NodeFilterMap, ArcFilterMap>690 subDigraph Adaptor(const Digraph& digraph,691 692 return SubDigraph Adaptor<const Digraph, const NodeFilterMap, ArcFilterMap>790 SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap> 791 subDigraph(const Digraph& digraph, 792 const NodeFilterMap& nfm, ArcFilterMap& afm) { 793 return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap> 693 794 (digraph, nfm, afm); 694 795 } 695 796 696 797 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 697 SubDigraph Adaptor<const Digraph, NodeFilterMap, const ArcFilterMap>698 subDigraph Adaptor(const Digraph& digraph,699 NodeFilterMap& nfm,ArcFilterMap& afm) {700 return SubDigraph Adaptor<const Digraph, NodeFilterMap, const ArcFilterMap>798 SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap> 799 subDigraph(const Digraph& digraph, 800 NodeFilterMap& nfm, const ArcFilterMap& afm) { 801 return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap> 701 802 (digraph, nfm, afm); 702 803 } 703 804 704 805 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 705 SubDigraph Adaptor<const Digraph, const NodeFilterMap, const ArcFilterMap>706 subDigraph Adaptor(const Digraph& digraph,707 NodeFilterMap& nfm,ArcFilterMap& afm) {708 return SubDigraph Adaptor<const Digraph, const NodeFilterMap,806 SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap> 807 subDigraph(const Digraph& digraph, 808 const NodeFilterMap& nfm, const ArcFilterMap& afm) { 809 return SubDigraph<const Digraph, const NodeFilterMap, 709 810 const ArcFilterMap>(digraph, nfm, afm); 710 711 811 } 712 812 713 813 714 715 ///\ingroup graph_adaptors 716 /// 717 ///\brief An adaptor for hiding nodes from a digraph. 718 /// 719 ///An adaptor for hiding nodes from a digraph. This adaptor 720 ///specializes SubDigraphAdaptor in the way that only the node-set 721 ///can be filtered. In usual case the checked parameter is true, we 722 ///get the induced subgraph. But if the checked parameter is false 723 ///then we can filter only isolated nodes. 724 template<typename _Digraph, 725 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 726 bool checked = true> 727 class NodeSubDigraphAdaptor : 728 public SubDigraphAdaptor<_Digraph, _NodeFilterMap, 729 ConstMap<typename _Digraph::Arc, bool>, checked> { 814 template <typename _Graph, typename NodeFilterMap, 815 typename EdgeFilterMap, bool _checked = true> 816 class SubGraphBase : public GraphAdaptorBase<_Graph> { 817 public: 818 typedef _Graph Graph; 819 typedef SubGraphBase Adaptor; 820 typedef GraphAdaptorBase<_Graph> Parent; 821 protected: 822 823 NodeFilterMap* _node_filter_map; 824 EdgeFilterMap* _edge_filter_map; 825 826 SubGraphBase() 827 : Parent(), _node_filter_map(0), _edge_filter_map(0) { } 828 829 void setNodeFilterMap(NodeFilterMap& node_filter_map) { 830 _node_filter_map=&node_filter_map; 831 } 832 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) { 833 _edge_filter_map=&edge_filter_map; 834 } 835 836 public: 837 838 typedef typename Parent::Node Node; 839 typedef typename Parent::Arc Arc; 840 typedef typename Parent::Edge Edge; 841 842 void first(Node& i) const { 843 Parent::first(i); 844 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 845 } 846 847 void first(Arc& i) const { 848 Parent::first(i); 849 while (i!=INVALID && (!(*_edge_filter_map)[i] 850 || !(*_node_filter_map)[Parent::source(i)] 851 || !(*_node_filter_map)[Parent::target(i)])) 852 Parent::next(i); 853 } 854 855 void first(Edge& i) const { 856 Parent::first(i); 857 while (i!=INVALID && (!(*_edge_filter_map)[i] 858 || !(*_node_filter_map)[Parent::u(i)] 859 || !(*_node_filter_map)[Parent::v(i)])) 860 Parent::next(i); 861 } 862 863 void firstIn(Arc& i, const Node& n) const { 864 Parent::firstIn(i, n); 865 while (i!=INVALID && (!(*_edge_filter_map)[i] 866 || !(*_node_filter_map)[Parent::source(i)])) 867 Parent::nextIn(i); 868 } 869 870 void firstOut(Arc& i, const Node& n) const { 871 Parent::firstOut(i, n); 872 while (i!=INVALID && (!(*_edge_filter_map)[i] 873 || !(*_node_filter_map)[Parent::target(i)])) 874 Parent::nextOut(i); 875 } 876 877 void firstInc(Edge& i, bool& d, const Node& n) const { 878 Parent::firstInc(i, d, n); 879 while (i!=INVALID && (!(*_edge_filter_map)[i] 880 || !(*_node_filter_map)[Parent::u(i)] 881 || !(*_node_filter_map)[Parent::v(i)])) 882 Parent::nextInc(i, d); 883 } 884 885 void next(Node& i) const { 886 Parent::next(i); 887 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 888 } 889 890 void next(Arc& i) const { 891 Parent::next(i); 892 while (i!=INVALID && (!(*_edge_filter_map)[i] 893 || !(*_node_filter_map)[Parent::source(i)] 894 || !(*_node_filter_map)[Parent::target(i)])) 895 Parent::next(i); 896 } 897 898 void next(Edge& i) const { 899 Parent::next(i); 900 while (i!=INVALID && (!(*_edge_filter_map)[i] 901 || !(*_node_filter_map)[Parent::u(i)] 902 || !(*_node_filter_map)[Parent::v(i)])) 903 Parent::next(i); 904 } 905 906 void nextIn(Arc& i) const { 907 Parent::nextIn(i); 908 while (i!=INVALID && (!(*_edge_filter_map)[i] 909 || !(*_node_filter_map)[Parent::source(i)])) 910 Parent::nextIn(i); 911 } 912 913 void nextOut(Arc& i) const { 914 Parent::nextOut(i); 915 while (i!=INVALID && (!(*_edge_filter_map)[i] 916 || !(*_node_filter_map)[Parent::target(i)])) 917 Parent::nextOut(i); 918 } 919 920 void nextInc(Edge& i, bool& d) const { 921 Parent::nextInc(i, d); 922 while (i!=INVALID && (!(*_edge_filter_map)[i] 923 || !(*_node_filter_map)[Parent::u(i)] 924 || !(*_node_filter_map)[Parent::v(i)])) 925 Parent::nextInc(i, d); 926 } 927 928 void hide(const Node& n) const { _node_filter_map->set(n, false); } 929 void hide(const Edge& e) const { _edge_filter_map->set(e, false); } 930 931 void unHide(const Node& n) const { _node_filter_map->set(n, true); } 932 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } 933 934 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } 935 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } 936 937 typedef False NodeNumTag; 938 typedef False EdgeNumTag; 939 940 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 941 Arc findArc(const Node& u, const Node& v, 942 const Arc& prev = INVALID) { 943 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { 944 return INVALID; 945 } 946 Arc arc = Parent::findArc(u, v, prev); 947 while (arc != INVALID && !(*_edge_filter_map)[arc]) { 948 arc = Parent::findArc(u, v, arc); 949 } 950 return arc; 951 } 952 Edge findEdge(const Node& u, const Node& v, 953 const Edge& prev = INVALID) { 954 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { 955 return INVALID; 956 } 957 Edge edge = Parent::findEdge(u, v, prev); 958 while (edge != INVALID && !(*_edge_filter_map)[edge]) { 959 edge = Parent::findEdge(u, v, edge); 960 } 961 return edge; 962 } 963 964 template <typename _Value> 965 class NodeMap : public SubMapExtender<Adaptor, 966 typename Parent::template NodeMap<_Value> > { 967 public: 968 typedef _Value Value; 969 typedef SubMapExtender<Adaptor, typename Parent:: 970 template NodeMap<Value> > MapParent; 971 972 NodeMap(const Adaptor& adaptor) 973 : MapParent(adaptor) {} 974 NodeMap(const Adaptor& adaptor, const Value& value) 975 : MapParent(adaptor, value) {} 976 977 private: 978 NodeMap& operator=(const NodeMap& cmap) { 979 return operator=<NodeMap>(cmap); 980 } 981 982 template <typename CMap> 983 NodeMap& operator=(const CMap& cmap) { 984 MapParent::operator=(cmap); 985 return *this; 986 } 987 }; 988 989 template <typename _Value> 990 class ArcMap : public SubMapExtender<Adaptor, 991 typename Parent::template ArcMap<_Value> > { 992 public: 993 typedef _Value Value; 994 typedef SubMapExtender<Adaptor, typename Parent:: 995 template ArcMap<Value> > MapParent; 996 997 ArcMap(const Adaptor& adaptor) 998 : MapParent(adaptor) {} 999 ArcMap(const Adaptor& adaptor, const Value& value) 1000 : MapParent(adaptor, value) {} 1001 1002 private: 1003 ArcMap& operator=(const ArcMap& cmap) { 1004 return operator=<ArcMap>(cmap); 1005 } 1006 1007 template <typename CMap> 1008 ArcMap& operator=(const CMap& cmap) { 1009 MapParent::operator=(cmap); 1010 return *this; 1011 } 1012 }; 1013 1014 template <typename _Value> 1015 class EdgeMap : public SubMapExtender<Adaptor, 1016 typename Parent::template EdgeMap<_Value> > { 1017 public: 1018 typedef _Value Value; 1019 typedef SubMapExtender<Adaptor, typename Parent:: 1020 template EdgeMap<Value> > MapParent; 1021 1022 EdgeMap(const Adaptor& adaptor) 1023 : MapParent(adaptor) {} 1024 1025 EdgeMap(const Adaptor& adaptor, const Value& value) 1026 : MapParent(adaptor, value) {} 1027 1028 private: 1029 EdgeMap& operator=(const EdgeMap& cmap) { 1030 return operator=<EdgeMap>(cmap); 1031 } 1032 1033 template <typename CMap> 1034 EdgeMap& operator=(const CMap& cmap) { 1035 MapParent::operator=(cmap); 1036 return *this; 1037 } 1038 }; 1039 1040 }; 1041 1042 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> 1043 class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 1044 : public GraphAdaptorBase<_Graph> { 1045 public: 1046 typedef _Graph Graph; 1047 typedef SubGraphBase Adaptor; 1048 typedef GraphAdaptorBase<_Graph> Parent; 1049 protected: 1050 NodeFilterMap* _node_filter_map; 1051 EdgeFilterMap* _edge_filter_map; 1052 SubGraphBase() : Parent(), 1053 _node_filter_map(0), _edge_filter_map(0) { } 1054 1055 void setNodeFilterMap(NodeFilterMap& node_filter_map) { 1056 _node_filter_map=&node_filter_map; 1057 } 1058 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) { 1059 _edge_filter_map=&edge_filter_map; 1060 } 1061 1062 public: 1063 1064 typedef typename Parent::Node Node; 1065 typedef typename Parent::Arc Arc; 1066 typedef typename Parent::Edge Edge; 1067 1068 void first(Node& i) const { 1069 Parent::first(i); 1070 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 1071 } 1072 1073 void first(Arc& i) const { 1074 Parent::first(i); 1075 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 1076 } 1077 1078 void first(Edge& i) const { 1079 Parent::first(i); 1080 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 1081 } 1082 1083 void firstIn(Arc& i, const Node& n) const { 1084 Parent::firstIn(i, n); 1085 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); 1086 } 1087 1088 void firstOut(Arc& i, const Node& n) const { 1089 Parent::firstOut(i, n); 1090 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); 1091 } 1092 1093 void firstInc(Edge& i, bool& d, const Node& n) const { 1094 Parent::firstInc(i, d, n); 1095 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); 1096 } 1097 1098 void next(Node& i) const { 1099 Parent::next(i); 1100 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 1101 } 1102 void next(Arc& i) const { 1103 Parent::next(i); 1104 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 1105 } 1106 void next(Edge& i) const { 1107 Parent::next(i); 1108 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 1109 } 1110 void nextIn(Arc& i) const { 1111 Parent::nextIn(i); 1112 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); 1113 } 1114 1115 void nextOut(Arc& i) const { 1116 Parent::nextOut(i); 1117 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); 1118 } 1119 void nextInc(Edge& i, bool& d) const { 1120 Parent::nextInc(i, d); 1121 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); 1122 } 1123 1124 void hide(const Node& n) const { _node_filter_map->set(n, false); } 1125 void hide(const Edge& e) const { _edge_filter_map->set(e, false); } 1126 1127 void unHide(const Node& n) const { _node_filter_map->set(n, true); } 1128 void unHide(const Edge& e) const { _edge_filter_map->set(e, true); } 1129 1130 bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; } 1131 bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; } 1132 1133 typedef False NodeNumTag; 1134 typedef False EdgeNumTag; 1135 1136 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 1137 Arc findArc(const Node& u, const Node& v, 1138 const Arc& prev = INVALID) { 1139 Arc arc = Parent::findArc(u, v, prev); 1140 while (arc != INVALID && !(*_edge_filter_map)[arc]) { 1141 arc = Parent::findArc(u, v, arc); 1142 } 1143 return arc; 1144 } 1145 Edge findEdge(const Node& u, const Node& v, 1146 const Edge& prev = INVALID) { 1147 Edge edge = Parent::findEdge(u, v, prev); 1148 while (edge != INVALID && !(*_edge_filter_map)[edge]) { 1149 edge = Parent::findEdge(u, v, edge); 1150 } 1151 return edge; 1152 } 1153 1154 template <typename _Value> 1155 class NodeMap : public SubMapExtender<Adaptor, 1156 typename Parent::template NodeMap<_Value> > { 1157 public: 1158 typedef _Value Value; 1159 typedef SubMapExtender<Adaptor, typename Parent:: 1160 template NodeMap<Value> > MapParent; 1161 1162 NodeMap(const Adaptor& adaptor) 1163 : MapParent(adaptor) {} 1164 NodeMap(const Adaptor& adaptor, const Value& value) 1165 : MapParent(adaptor, value) {} 1166 1167 private: 1168 NodeMap& operator=(const NodeMap& cmap) { 1169 return operator=<NodeMap>(cmap); 1170 } 1171 1172 template <typename CMap> 1173 NodeMap& operator=(const CMap& cmap) { 1174 MapParent::operator=(cmap); 1175 return *this; 1176 } 1177 }; 1178 1179 template <typename _Value> 1180 class ArcMap : public SubMapExtender<Adaptor, 1181 typename Parent::template ArcMap<_Value> > { 1182 public: 1183 typedef _Value Value; 1184 typedef SubMapExtender<Adaptor, typename Parent:: 1185 template ArcMap<Value> > MapParent; 1186 1187 ArcMap(const Adaptor& adaptor) 1188 : MapParent(adaptor) {} 1189 ArcMap(const Adaptor& adaptor, const Value& value) 1190 : MapParent(adaptor, value) {} 1191 1192 private: 1193 ArcMap& operator=(const ArcMap& cmap) { 1194 return operator=<ArcMap>(cmap); 1195 } 1196 1197 template <typename CMap> 1198 ArcMap& operator=(const CMap& cmap) { 1199 MapParent::operator=(cmap); 1200 return *this; 1201 } 1202 }; 1203 1204 template <typename _Value> 1205 class EdgeMap : public SubMapExtender<Adaptor, 1206 typename Parent::template EdgeMap<_Value> > { 1207 public: 1208 typedef _Value Value; 1209 typedef SubMapExtender<Adaptor, typename Parent:: 1210 template EdgeMap<Value> > MapParent; 1211 1212 EdgeMap(const Adaptor& adaptor) 1213 : MapParent(adaptor) {} 1214 1215 EdgeMap(const Adaptor& adaptor, const _Value& value) 1216 : MapParent(adaptor, value) {} 1217 1218 private: 1219 EdgeMap& operator=(const EdgeMap& cmap) { 1220 return operator=<EdgeMap>(cmap); 1221 } 1222 1223 template <typename CMap> 1224 EdgeMap& operator=(const CMap& cmap) { 1225 MapParent::operator=(cmap); 1226 return *this; 1227 } 1228 }; 1229 1230 }; 1231 1232 /// \ingroup graph_adaptors 1233 /// 1234 /// \brief A graph adaptor for hiding nodes and edges in an 1235 /// undirected graph. 1236 /// 1237 /// SubGraph hides nodes and edges in a graph. A bool node map and a 1238 /// bool edge map must be specified, which define the filters for 1239 /// nodes and edges. Just the nodes and edges with true value are 1240 /// shown in the subgraph. The SubGraph is conform to the \ref 1241 /// concepts::Graph "Graph concept". If the \c _checked parameter is 1242 /// true, then the edges incident to filtered nodes are also 1243 /// filtered out. 1244 /// 1245 /// \tparam _Graph It must be conform to the \ref 1246 /// concepts::Graph "Graph concept". The type can be specified 1247 /// to const. 1248 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. 1249 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted graph. 1250 /// \tparam _checked If the parameter is false then the edge filtering 1251 /// is not checked with respect to node filter. Otherwise, each edge 1252 /// is automatically filtered, which is incident to a filtered node. 1253 /// 1254 /// \see FilterNodes 1255 /// \see FilterEdges 1256 template<typename _Graph, typename NodeFilterMap, 1257 typename EdgeFilterMap, bool _checked = true> 1258 class SubGraph 1259 : public GraphAdaptorExtender< 1260 SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, _checked> > { 1261 public: 1262 typedef _Graph Graph; 1263 typedef GraphAdaptorExtender< 1264 SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; 1265 1266 typedef typename Parent::Node Node; 1267 typedef typename Parent::Edge Edge; 1268 1269 protected: 1270 SubGraph() { } 1271 public: 1272 1273 /// \brief Constructor 1274 /// 1275 /// Creates a subgraph for the given graph with given node and 1276 /// edge map filters. 1277 SubGraph(Graph& _graph, NodeFilterMap& node_filter_map, 1278 EdgeFilterMap& edge_filter_map) { 1279 setGraph(_graph); 1280 setNodeFilterMap(node_filter_map); 1281 setEdgeFilterMap(edge_filter_map); 1282 } 1283 1284 /// \brief Hides the node of the graph 1285 /// 1286 /// This function hides \c n in the graph, i.e. the iteration 1287 /// jumps over it. This is done by simply setting the value of \c n 1288 /// to be false in the corresponding node-map. 1289 void hide(const Node& n) const { Parent::hide(n); } 1290 1291 /// \brief Hides the edge of the graph 1292 /// 1293 /// This function hides \c e in the graph, i.e. the iteration 1294 /// jumps over it. This is done by simply setting the value of \c e 1295 /// to be false in the corresponding edge-map. 1296 void hide(const Edge& e) const { Parent::hide(e); } 1297 1298 /// \brief Unhides the node of the graph 1299 /// 1300 /// The value of \c n is set to be true in the node-map which stores 1301 /// hide information. If \c n was hidden previuosly, then it is shown 1302 /// again 1303 void unHide(const Node& n) const { Parent::unHide(n); } 1304 1305 /// \brief Unhides the edge of the graph 1306 /// 1307 /// The value of \c e is set to be true in the edge-map which stores 1308 /// hide information. If \c e was hidden previuosly, then it is shown 1309 /// again 1310 void unHide(const Edge& e) const { Parent::unHide(e); } 1311 1312 /// \brief Returns true if \c n is hidden. 1313 /// 1314 /// Returns true if \c n is hidden. 1315 /// 1316 bool hidden(const Node& n) const { return Parent::hidden(n); } 1317 1318 /// \brief Returns true if \c e is hidden. 1319 /// 1320 /// Returns true if \c e is hidden. 1321 /// 1322 bool hidden(const Edge& e) const { return Parent::hidden(e); } 1323 }; 1324 1325 /// \brief Just gives back a subgraph 1326 /// 1327 /// Just gives back a subgraph 1328 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1329 SubGraph<const Graph, NodeFilterMap, ArcFilterMap> 1330 subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) { 1331 return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm); 1332 } 1333 1334 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1335 SubGraph<const Graph, const NodeFilterMap, ArcFilterMap> 1336 subGraph(const Graph& graph, 1337 const NodeFilterMap& nfm, ArcFilterMap& efm) { 1338 return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap> 1339 (graph, nfm, efm); 1340 } 1341 1342 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1343 SubGraph<const Graph, NodeFilterMap, const ArcFilterMap> 1344 subGraph(const Graph& graph, 1345 NodeFilterMap& nfm, const ArcFilterMap& efm) { 1346 return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap> 1347 (graph, nfm, efm); 1348 } 1349 1350 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1351 SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap> 1352 subGraph(const Graph& graph, 1353 const NodeFilterMap& nfm, const ArcFilterMap& efm) { 1354 return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap> 1355 (graph, nfm, efm); 1356 } 1357 1358 /// \ingroup graph_adaptors 1359 /// 1360 /// \brief An adaptor for hiding nodes from a digraph or a graph. 1361 /// 1362 /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool 1363 /// node map must be specified, which defines the filters for 1364 /// nodes. Just the unfiltered nodes and the arcs or edges incident 1365 /// to unfiltered nodes are shown in the subdigraph or subgraph. The 1366 /// FilterNodes is conform to the \ref concepts::Digraph 1367 /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending 1368 /// on the \c _Digraph template parameter. If the \c _checked 1369 /// parameter is true, then the arc or edges incident to filtered nodes 1370 /// are also filtered out. 1371 /// 1372 /// \tparam _Digraph It must be conform to the \ref 1373 /// concepts::Digraph "Digraph concept" or \ref concepts::Graph 1374 /// "Graph concept". The type can be specified to be const. 1375 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. 1376 /// \tparam _checked If the parameter is false then the arc or edge 1377 /// filtering is not checked with respect to node filter. In this 1378 /// case just isolated nodes can be filtered out from the 1379 /// graph. 1380 #ifdef DOXYGEN 1381 template<typename _Digraph, 1382 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 1383 bool _checked = true> 1384 #else 1385 template<typename _Digraph, 1386 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 1387 bool _checked = true, 1388 typename Enable = void> 1389 #endif 1390 class FilterNodes 1391 : public SubDigraph<_Digraph, _NodeFilterMap, 1392 ConstMap<typename _Digraph::Arc, bool>, _checked> { 730 1393 public: 731 1394 … … 733 1396 typedef _NodeFilterMap NodeFilterMap; 734 1397 735 typedef SubDigraph Adaptor<Digraph, NodeFilterMap,736 ConstMap<typename Digraph::Arc, bool>, checked> 1398 typedef SubDigraph<Digraph, NodeFilterMap, 1399 ConstMap<typename Digraph::Arc, bool>, _checked> 737 1400 Parent; 738 1401 … … 742 1405 ConstMap<typename Digraph::Arc, bool> const_true_map; 743 1406 744 NodeSubDigraphAdaptor() : const_true_map(true) {1407 FilterNodes() : const_true_map(true) { 745 1408 Parent::setArcFilterMap(const_true_map); 746 1409 } … … 750 1413 /// \brief Constructor 751 1414 /// 752 /// Creates a node-sub-digraph-adaptor for the given digraph with753 /// given node map filter.754 NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) :755 Parent(), const_true_map(true) { 1415 /// Creates an adaptor for the given digraph or graph with 1416 /// given node filter map. 1417 FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) : 1418 Parent(), const_true_map(true) { 756 1419 Parent::setDigraph(_digraph); 757 1420 Parent::setNodeFilterMap(node_filter); … … 761 1424 /// \brief Hides the node of the graph 762 1425 /// 763 /// This function hides \c n in the digraph , i.e. the iteration764 /// jumps over it. This is done by simply setting the value of \c n 765 /// to be false in the corresponding node -map.1426 /// This function hides \c n in the digraph or graph, i.e. the iteration 1427 /// jumps over it. This is done by simply setting the value of \c n 1428 /// to be false in the corresponding node map. 766 1429 void hide(const Node& n) const { Parent::hide(n); } 767 1430 768 1431 /// \brief Unhides the node of the graph 769 1432 /// 770 /// The value of \c n is set to be true in the node-map which stores 771 /// hide information. If \c n was hidden previuosly, then it is shown 1433 /// The value of \c n is set to be true in the node-map which stores 1434 /// hide information. If \c n was hidden previuosly, then it is shown 772 1435 /// again 773 1436 void unHide(const Node& n) const { Parent::unHide(n); } … … 781 1444 }; 782 1445 783 784 /// \brief Just gives back a node-sub-digraph adaptor 785 /// 786 /// Just gives back a node-sub-digraph adaptor 1446 template<typename _Graph, typename _NodeFilterMap, bool _checked> 1447 class FilterNodes<_Graph, _NodeFilterMap, _checked, 1448 typename enable_if<UndirectedTagIndicator<_Graph> >::type> 1449 : public SubGraph<_Graph, _NodeFilterMap, 1450 ConstMap<typename _Graph::Edge, bool>, _checked> { 1451 public: 1452 typedef _Graph Graph; 1453 typedef _NodeFilterMap NodeFilterMap; 1454 typedef SubGraph<Graph, NodeFilterMap, 1455 ConstMap<typename Graph::Edge, bool> > Parent; 1456 1457 typedef typename Parent::Node Node; 1458 protected: 1459 ConstMap<typename Graph::Edge, bool> const_true_map; 1460 1461 FilterNodes() : const_true_map(true) { 1462 Parent::setEdgeFilterMap(const_true_map); 1463 } 1464 1465 public: 1466 1467 FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) : 1468 Parent(), const_true_map(true) { 1469 Parent::setGraph(_graph); 1470 Parent::setNodeFilterMap(node_filter_map); 1471 Parent::setEdgeFilterMap(const_true_map); 1472 } 1473 1474 void hide(const Node& n) const { Parent::hide(n); } 1475 void unHide(const Node& n) const { Parent::unHide(n); } 1476 bool hidden(const Node& n) const { return Parent::hidden(n); } 1477 1478 }; 1479 1480 1481 /// \brief Just gives back a FilterNodes adaptor 1482 /// 1483 /// Just gives back a FilterNodes adaptor 787 1484 template<typename Digraph, typename NodeFilterMap> 788 NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>789 nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {790 return NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>(digraph, nfm);1485 FilterNodes<const Digraph, NodeFilterMap> 1486 filterNodes(const Digraph& digraph, NodeFilterMap& nfm) { 1487 return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm); 791 1488 } 792 1489 793 1490 template<typename Digraph, typename NodeFilterMap> 794 NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap> 795 nodeSubDigraphAdaptor(const Digraph& digraph, const NodeFilterMap& nfm) { 796 return NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap> 797 (digraph, nfm); 1491 FilterNodes<const Digraph, const NodeFilterMap> 1492 filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) { 1493 return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm); 798 1494 } 799 1495 800 ///\ingroup graph_adaptors 801 /// 802 ///\brief An adaptor for hiding arcs from a digraph. 803 /// 804 ///An adaptor for hiding arcs from a digraph. This adaptor 805 ///specializes SubDigraphAdaptor in the way that only the arc-set 806 ///can be filtered. The usefulness of this adaptor is demonstrated 807 ///in the problem of searching a maximum number of arc-disjoint 808 ///shortest paths between two nodes \c s and \c t. Shortest here 809 ///means being shortest with respect to non-negative 810 ///arc-lengths. Note that the comprehension of the presented 811 ///solution need's some elementary knowledge from combinatorial 812 ///optimization. 813 /// 814 ///If a single shortest path is to be searched between \c s and \c 815 ///t, then this can be done easily by applying the Dijkstra 816 ///algorithm. What happens, if a maximum number of arc-disjoint 817 ///shortest paths is to be computed. It can be proved that an arc 818 ///can be in a shortest path if and only if it is tight with respect 819 ///to the potential function computed by Dijkstra. Moreover, any 820 ///path containing only such arcs is a shortest one. Thus we have 821 ///to compute a maximum number of arc-disjoint paths between \c s 822 ///and \c t in the digraph which has arc-set all the tight arcs. The 823 ///computation will be demonstrated on the following digraph, which 824 ///is read from the dimacs file \c sub_digraph_adaptor_demo.dim. 825 ///The full source code is available in \ref 826 ///sub_digraph_adaptor_demo.cc. If you are interested in more demo 827 ///programs, you can use \ref dim_to_dot.cc to generate .dot files 828 ///from dimacs files. The .dot file of the following figure was 829 ///generated by the demo program \ref dim_to_dot.cc. 830 /// 831 ///\dot 832 ///digraph lemon_dot_example { 833 ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 834 ///n0 [ label="0 (s)" ]; 835 ///n1 [ label="1" ]; 836 ///n2 [ label="2" ]; 837 ///n3 [ label="3" ]; 838 ///n4 [ label="4" ]; 839 ///n5 [ label="5" ]; 840 ///n6 [ label="6 (t)" ]; 841 ///arc [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 842 ///n5 -> n6 [ label="9, length:4" ]; 843 ///n4 -> n6 [ label="8, length:2" ]; 844 ///n3 -> n5 [ label="7, length:1" ]; 845 ///n2 -> n5 [ label="6, length:3" ]; 846 ///n2 -> n6 [ label="5, length:5" ]; 847 ///n2 -> n4 [ label="4, length:2" ]; 848 ///n1 -> n4 [ label="3, length:3" ]; 849 ///n0 -> n3 [ label="2, length:1" ]; 850 ///n0 -> n2 [ label="1, length:2" ]; 851 ///n0 -> n1 [ label="0, length:3" ]; 852 ///} 853 ///\enddot 854 /// 855 ///\code 856 ///Digraph g; 857 ///Node s, t; 858 ///LengthMap length(g); 859 /// 860 ///readDimacs(std::cin, g, length, s, t); 861 /// 862 ///cout << "arcs with lengths (of form id, source--length->target): " << endl; 863 ///for(ArcIt e(g); e!=INVALID; ++e) 864 /// cout << g.id(e) << ", " << g.id(g.source(e)) << "--" 865 /// << length[e] << "->" << g.id(g.target(e)) << endl; 866 /// 867 ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; 868 ///\endcode 869 ///Next, the potential function is computed with Dijkstra. 870 ///\code 871 ///typedef Dijkstra<Digraph, LengthMap> Dijkstra; 872 ///Dijkstra dijkstra(g, length); 873 ///dijkstra.run(s); 874 ///\endcode 875 ///Next, we consrtruct a map which filters the arc-set to the tight arcs. 876 ///\code 877 ///typedef TightArcFilterMap<Digraph, const Dijkstra::DistMap, LengthMap> 878 /// TightArcFilter; 879 ///TightArcFilter tight_arc_filter(g, dijkstra.distMap(), length); 880 /// 881 ///typedef ArcSubDigraphAdaptor<Digraph, TightArcFilter> SubGA; 882 ///SubGA ga(g, tight_arc_filter); 883 ///\endcode 884 ///Then, the maximum nimber of arc-disjoint \c s-\c t paths are computed 885 ///with a max flow algorithm Preflow. 886 ///\code 887 ///ConstMap<Arc, int> const_1_map(1); 888 ///Digraph::ArcMap<int> flow(g, 0); 889 /// 890 ///Preflow<SubGA, ConstMap<Arc, int>, Digraph::ArcMap<int> > 891 /// preflow(ga, const_1_map, s, t); 892 ///preflow.run(); 893 ///\endcode 894 ///Last, the output is: 895 ///\code 896 ///cout << "maximum number of arc-disjoint shortest path: " 897 /// << preflow.flowValue() << endl; 898 ///cout << "arcs of the maximum number of arc-disjoint shortest s-t paths: " 899 /// << endl; 900 ///for(ArcIt e(g); e!=INVALID; ++e) 901 /// if (preflow.flow(e)) 902 /// cout << " " << g.id(g.source(e)) << "--" 903 /// << length[e] << "->" << g.id(g.target(e)) << endl; 904 ///\endcode 905 ///The program has the following (expected :-)) output: 906 ///\code 907 ///arcs with lengths (of form id, source--length->target): 908 /// 9, 5--4->6 909 /// 8, 4--2->6 910 /// 7, 3--1->5 911 /// 6, 2--3->5 912 /// 5, 2--5->6 913 /// 4, 2--2->4 914 /// 3, 1--3->4 915 /// 2, 0--1->3 916 /// 1, 0--2->2 917 /// 0, 0--3->1 918 ///s: 0 t: 6 919 ///maximum number of arc-disjoint shortest path: 2 920 ///arcs of the maximum number of arc-disjoint shortest s-t paths: 921 /// 9, 5--4->6 922 /// 8, 4--2->6 923 /// 7, 3--1->5 924 /// 4, 2--2->4 925 /// 2, 0--1->3 926 /// 1, 0--2->2 927 ///\endcode 1496 /// \ingroup graph_adaptors 1497 /// 1498 /// \brief An adaptor for hiding arcs from a digraph. 1499 /// 1500 /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must 1501 /// be specified, which defines the filters for arcs. Just the 1502 /// unfiltered arcs are shown in the subdigraph. The FilterArcs is 1503 /// conform to the \ref concepts::Digraph "Digraph concept". 1504 /// 1505 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 1506 /// "Digraph concept". The type can be specified to be const. 1507 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted 1508 /// graph. 928 1509 template<typename _Digraph, typename _ArcFilterMap> 929 class ArcSubDigraphAdaptor :930 public SubDigraph Adaptor<_Digraph, ConstMap<typename _Digraph::Node, bool>,931 1510 class FilterArcs : 1511 public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>, 1512 _ArcFilterMap, false> { 932 1513 public: 933 1514 typedef _Digraph Digraph; 934 1515 typedef _ArcFilterMap ArcFilterMap; 935 1516 936 typedef SubDigraph Adaptor<Digraph, ConstMap<typename Digraph::Node, bool>,937 1517 typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>, 1518 ArcFilterMap, false> Parent; 938 1519 939 1520 typedef typename Parent::Arc Arc; … … 942 1523 ConstMap<typename Digraph::Node, bool> const_true_map; 943 1524 944 ArcSubDigraphAdaptor() : const_true_map(true) {1525 FilterArcs() : const_true_map(true) { 945 1526 Parent::setNodeFilterMap(const_true_map); 946 1527 } … … 950 1531 /// \brief Constructor 951 1532 /// 952 /// Creates a arc-sub-digraph-adaptor for the given digraph with1533 /// Creates a FilterArcs adaptor for the given graph with 953 1534 /// given arc map filter. 954 ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter)955 : Parent(), const_true_map(true) { 1535 FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter) 1536 : Parent(), const_true_map(true) { 956 1537 Parent::setDigraph(digraph); 957 1538 Parent::setNodeFilterMap(const_true_map); … … 961 1542 /// \brief Hides the arc of the graph 962 1543 /// 963 /// This function hides \c a in the digraph, i.e. the iteration1544 /// This function hides \c a in the graph, i.e. the iteration 964 1545 /// jumps over it. This is done by simply setting the value of \c a 965 /// to be false in the corresponding arc -map.1546 /// to be false in the corresponding arc map. 966 1547 void hide(const Arc& a) const { Parent::hide(a); } 967 1548 968 1549 /// \brief Unhides the arc of the graph 969 1550 /// 970 /// The value of \c a is set to be true in the arc-map which stores 971 /// hide information. If \c a was hidden previuosly, then it is shown 1551 /// The value of \c a is set to be true in the arc-map which stores 1552 /// hide information. If \c a was hidden previuosly, then it is shown 972 1553 /// again 973 1554 void unHide(const Arc& a) const { Parent::unHide(a); } … … 981 1562 }; 982 1563 983 /// \brief Just gives back an arc-sub-digraphadaptor984 /// 985 /// Just gives back an arc-sub-digraphadaptor1564 /// \brief Just gives back an FilterArcs adaptor 1565 /// 1566 /// Just gives back an FilterArcs adaptor 986 1567 template<typename Digraph, typename ArcFilterMap> 987 ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>988 arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {989 return ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>(digraph, afm);1568 FilterArcs<const Digraph, ArcFilterMap> 1569 filterArcs(const Digraph& digraph, ArcFilterMap& afm) { 1570 return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm); 990 1571 } 991 1572 992 1573 template<typename Digraph, typename ArcFilterMap> 993 ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap> 994 arcSubDigraphAdaptor(const Digraph& digraph, const ArcFilterMap& afm) { 995 return ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap> 996 (digraph, afm); 1574 FilterArcs<const Digraph, const ArcFilterMap> 1575 filterArcs(const Digraph& digraph, const ArcFilterMap& afm) { 1576 return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm); 997 1577 } 998 1578 1579 /// \ingroup graph_adaptors 1580 /// 1581 /// \brief An adaptor for hiding edges from a graph. 1582 /// 1583 /// FilterEdges adaptor hides edges in a digraph. A bool edge map must 1584 /// be specified, which defines the filters for edges. Just the 1585 /// unfiltered edges are shown in the subdigraph. The FilterEdges is 1586 /// conform to the \ref concepts::Graph "Graph concept". 1587 /// 1588 /// \tparam _Graph It must be conform to the \ref concepts::Graph 1589 /// "Graph concept". The type can be specified to be const. 1590 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted 1591 /// graph. 1592 template<typename _Graph, typename _EdgeFilterMap> 1593 class FilterEdges : 1594 public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>, 1595 _EdgeFilterMap, false> { 1596 public: 1597 typedef _Graph Graph; 1598 typedef _EdgeFilterMap EdgeFilterMap; 1599 typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>, 1600 EdgeFilterMap, false> Parent; 1601 typedef typename Parent::Edge Edge; 1602 protected: 1603 ConstMap<typename Graph::Node, bool> const_true_map; 1604 1605 FilterEdges() : const_true_map(true) { 1606 Parent::setNodeFilterMap(const_true_map); 1607 } 1608 1609 public: 1610 1611 /// \brief Constructor 1612 /// 1613 /// Creates a FilterEdges adaptor for the given graph with 1614 /// given edge map filters. 1615 FilterEdges(Graph& _graph, EdgeFilterMap& edge_filter_map) : 1616 Parent(), const_true_map(true) { 1617 Parent::setGraph(_graph); 1618 Parent::setNodeFilterMap(const_true_map); 1619 Parent::setEdgeFilterMap(edge_filter_map); 1620 } 1621 1622 /// \brief Hides the edge of the graph 1623 /// 1624 /// This function hides \c e in the graph, i.e. the iteration 1625 /// jumps over it. This is done by simply setting the value of \c e 1626 /// to be false in the corresponding edge-map. 1627 void hide(const Edge& e) const { Parent::hide(e); } 1628 1629 /// \brief Unhides the edge of the graph 1630 /// 1631 /// The value of \c e is set to be true in the edge-map which stores 1632 /// hide information. If \c e was hidden previuosly, then it is shown 1633 /// again 1634 void unHide(const Edge& e) const { Parent::unHide(e); } 1635 1636 /// \brief Returns true if \c e is hidden. 1637 /// 1638 /// Returns true if \c e is hidden. 1639 /// 1640 bool hidden(const Edge& e) const { return Parent::hidden(e); } 1641 1642 }; 1643 1644 /// \brief Just gives back a FilterEdges adaptor 1645 /// 1646 /// Just gives back a FilterEdges adaptor 1647 template<typename Graph, typename EdgeFilterMap> 1648 FilterEdges<const Graph, EdgeFilterMap> 1649 filterEdges(const Graph& graph, EdgeFilterMap& efm) { 1650 return FilterEdges<const Graph, EdgeFilterMap>(graph, efm); 1651 } 1652 1653 template<typename Graph, typename EdgeFilterMap> 1654 FilterEdges<const Graph, const EdgeFilterMap> 1655 filterEdges(const Graph& graph, const EdgeFilterMap& efm) { 1656 return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm); 1657 } 1658 999 1659 template <typename _Digraph> 1000 class Undir DigraphAdaptorBase {1660 class UndirectorBase { 1001 1661 public: 1002 1662 typedef _Digraph Digraph; 1003 typedef Undir DigraphAdaptorBase Adaptor;1663 typedef UndirectorBase Adaptor; 1004 1664 1005 1665 typedef True UndirectedTag; … … 1009 1669 1010 1670 class Arc : public Edge { 1011 friend class Undir DigraphAdaptorBase;1671 friend class UndirectorBase; 1012 1672 protected: 1013 1673 bool _forward; … … 1022 1682 1023 1683 bool operator==(const Arc &other) const { 1024 return _forward == other._forward && 1025 1684 return _forward == other._forward && 1685 static_cast<const Edge&>(*this) == static_cast<const Edge&>(other); 1026 1686 } 1027 1687 bool operator!=(const Arc &other) const { 1028 return _forward != other._forward || 1029 1688 return _forward != other._forward || 1689 static_cast<const Edge&>(*this) != static_cast<const Edge&>(other); 1030 1690 } 1031 1691 bool operator<(const Arc &other) const { 1032 1033 1034 1692 return _forward < other._forward || 1693 (_forward == other._forward && 1694 static_cast<const Edge&>(*this) < static_cast<const Edge&>(other)); 1035 1695 } 1036 1696 }; … … 1053 1713 void next(Arc& a) const { 1054 1714 if (a._forward) { 1055 1715 a._forward = false; 1056 1716 } else { 1057 1058 1717 _digraph->next(a); 1718 a._forward = true; 1059 1719 } 1060 1720 } … … 1071 1731 _digraph->firstIn(a, n); 1072 1732 if( static_cast<const Edge&>(a) != INVALID ) { 1073 1733 a._forward = false; 1074 1734 } else { 1075 1076 1735 _digraph->firstOut(a, n); 1736 a._forward = true; 1077 1737 } 1078 1738 } 1079 1739 void nextOut(Arc &a) const { 1080 1740 if (!a._forward) { 1081 1082 1083 1084 1085 1086 1741 Node n = _digraph->target(a); 1742 _digraph->nextIn(a); 1743 if (static_cast<const Edge&>(a) == INVALID ) { 1744 _digraph->firstOut(a, n); 1745 a._forward = true; 1746 } 1087 1747 } 1088 1748 else { 1089 1749 _digraph->nextOut(a); 1090 1750 } 1091 1751 } … … 1094 1754 _digraph->firstOut(a, n); 1095 1755 if (static_cast<const Edge&>(a) != INVALID ) { 1096 1756 a._forward = false; 1097 1757 } else { 1098 1099 1758 _digraph->firstIn(a, n); 1759 a._forward = true; 1100 1760 } 1101 1761 } 1102 1762 void nextIn(Arc &a) const { 1103 1763 if (!a._forward) { 1104 1105 1106 1107 1108 1109 1764 Node n = _digraph->source(a); 1765 _digraph->nextOut(a); 1766 if( static_cast<const Edge&>(a) == INVALID ) { 1767 _digraph->firstIn(a, n); 1768 a._forward = true; 1769 } 1110 1770 } 1111 1771 else { 1112 1772 _digraph->nextIn(a); 1113 1773 } 1114 1774 } … … 1124 1784 void nextInc(Edge &e, bool &d) const { 1125 1785 if (d) { 1126 1127 1128 1129 1130 1786 Node s = _digraph->source(e); 1787 _digraph->nextOut(e); 1788 if (e != INVALID) return; 1789 d = false; 1790 _digraph->firstIn(e, s); 1131 1791 } else { 1132 1792 _digraph->nextIn(e); 1133 1793 } 1134 1794 } … … 1176 1836 1177 1837 Node addNode() { return _digraph->addNode(); } 1178 Edge addEdge(const Node& u, const Node& v) { 1179 return _digraph->addArc(u, v); 1838 Edge addEdge(const Node& u, const Node& v) { 1839 return _digraph->addArc(u, v); 1180 1840 } 1181 1841 1182 1842 void erase(const Node& i) { _digraph->erase(i); } 1183 1843 void erase(const Edge& i) { _digraph->erase(i); } 1184 1844 1185 1845 void clear() { _digraph->clear(); } 1186 1846 … … 1194 1854 Arc findArc(Node s, Node t, Arc p = INVALID) const { 1195 1855 if (p == INVALID) { 1196 1197 1198 1199 1856 Edge arc = _digraph->findArc(s, t); 1857 if (arc != INVALID) return direct(arc, true); 1858 arc = _digraph->findArc(t, s); 1859 if (arc != INVALID) return direct(arc, false); 1200 1860 } else if (direction(p)) { 1201 1202 1203 1204 if (arc != INVALID) return direct(arc, false); 1861 Edge arc = _digraph->findArc(s, t, p); 1862 if (arc != INVALID) return direct(arc, true); 1863 arc = _digraph->findArc(t, s); 1864 if (arc != INVALID) return direct(arc, false); 1205 1865 } else { 1206 1207 if (arc != INVALID) return direct(arc, false); 1866 Edge arc = _digraph->findArc(t, s, p); 1867 if (arc != INVALID) return direct(arc, false); 1208 1868 } 1209 1869 return INVALID; … … 1221 1881 if (arc != INVALID) return arc; 1222 1882 arc = _digraph->findArc(t, s); 1223 if (arc != INVALID) return arc; 1883 if (arc != INVALID) return arc; 1224 1884 } else { 1225 1885 Edge arc = _digraph->findArc(t, s, p); 1226 if (arc != INVALID) return arc; 1886 if (arc != INVALID) return arc; 1227 1887 } 1228 1888 } else { … … 1233 1893 1234 1894 private: 1235 1895 1236 1896 template <typename _Value> 1237 1897 class ArcMapBase { 1238 1898 private: 1239 1899 1240 1900 typedef typename Digraph::template ArcMap<_Value> MapImpl; 1241 1901 1242 1902 public: 1243 1903 … … 1246 1906 typedef _Value Value; 1247 1907 typedef Arc Key; 1248 1908 1249 1909 ArcMapBase(const Adaptor& adaptor) : 1250 1251 1252 ArcMapBase(const Adaptor& adaptor, const Value& v) 1910 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} 1911 1912 ArcMapBase(const Adaptor& adaptor, const Value& v) 1253 1913 : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {} 1254 1255 void set(const Arc& a, const Value& v) { 1256 if (direction(a)) { 1257 _forward.set(a, v); 1258 } else { 1259 _backward.set(a, v); 1260 } 1261 } 1262 1263 typename MapTraits<MapImpl>::ConstReturnValue 1264 operator[](const Arc& a) const { 1265 if (direction(a)) { 1266 return _forward[a]; 1267 } else { 1268 return _backward[a]; 1914 1915 void set(const Arc& a, const Value& v) { 1916 if (direction(a)) { 1917 _forward.set(a, v); 1918 } else { 1919 _backward.set(a, v); 1269 1920 } 1270 1921 } 1271 1922 1272 typename MapTraits<MapImpl>:: ReturnValue1273 operator[](const Arc& a) {1274 1275 return _forward[a]; 1276 } else { 1277 return _backward[a]; 1923 typename MapTraits<MapImpl>::ConstReturnValue 1924 operator[](const Arc& a) const { 1925 if (direction(a)) { 1926 return _forward[a]; 1927 } else { 1928 return _backward[a]; 1278 1929 } 1279 1930 } 1280 1931 1932 typename MapTraits<MapImpl>::ReturnValue 1933 operator[](const Arc& a) { 1934 if (direction(a)) { 1935 return _forward[a]; 1936 } else { 1937 return _backward[a]; 1938 } 1939 } 1940 1281 1941 protected: 1282 1942 1283 MapImpl _forward, _backward; 1943 MapImpl _forward, _backward; 1284 1944 1285 1945 }; … … 1294 1954 typedef typename Digraph::template NodeMap<Value> Parent; 1295 1955 1296 explicit NodeMap(const Adaptor& adaptor) 1297 1956 explicit NodeMap(const Adaptor& adaptor) 1957 : Parent(*adaptor._digraph) {} 1298 1958 1299 1959 NodeMap(const Adaptor& adaptor, const _Value& value) 1300 1960 : Parent(*adaptor._digraph, value) { } 1301 1961 1302 1962 private: … … 1310 1970 return *this; 1311 1971 } 1312 1972 1313 1973 }; 1314 1974 1315 1975 template <typename _Value> 1316 class ArcMap 1317 : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 1976 class ArcMap 1977 : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 1318 1978 { 1319 1979 public: 1320 1980 typedef _Value Value; 1321 1981 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; 1322 1323 ArcMap(const Adaptor& adaptor) 1324 1325 1326 ArcMap(const Adaptor& adaptor, const Value& value) 1327 1328 1982 1983 ArcMap(const Adaptor& adaptor) 1984 : Parent(adaptor) {} 1985 1986 ArcMap(const Adaptor& adaptor, const Value& value) 1987 : Parent(adaptor, value) {} 1988 1329 1989 private: 1330 1990 ArcMap& operator=(const ArcMap& cmap) { 1331 1332 } 1333 1991 return operator=<ArcMap>(cmap); 1992 } 1993 1334 1994 template <typename CMap> 1335 1995 ArcMap& operator=(const CMap& cmap) { 1336 1996 Parent::operator=(cmap); 1337 1997 return *this; 1338 1998 } 1339 1999 }; 1340 2000 1341 2001 template <typename _Value> 1342 2002 class EdgeMap : public Digraph::template ArcMap<_Value> { 1343 2003 public: 1344 2004 1345 2005 typedef _Value Value; 1346 2006 typedef typename Digraph::template ArcMap<Value> Parent; 1347 1348 explicit EdgeMap(const Adaptor& adaptor) 1349 2007 2008 explicit EdgeMap(const Adaptor& adaptor) 2009 : Parent(*adaptor._digraph) {} 1350 2010 1351 2011 EdgeMap(const Adaptor& adaptor, const Value& value) 1352 2012 : Parent(*adaptor._digraph, value) {} 1353 2013 1354 2014 private: … … 1366 2026 1367 2027 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier; 1368 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 2028 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 1369 2029 1370 2030 protected: 1371 2031 1372 Undir DigraphAdaptorBase() : _digraph(0) {}2032 UndirectorBase() : _digraph(0) {} 1373 2033 1374 2034 Digraph* _digraph; … … 1377 2037 _digraph = &digraph; 1378 2038 } 1379 2039 1380 2040 }; 1381 2041 1382 /// \ingroup graph_adaptors1383 /// 1384 /// \brief A graph is made from a directed digraph by an adaptor2042 /// \ingroup graph_adaptors 2043 /// 2044 /// \brief Undirect the graph 1385 2045 /// 1386 2046 /// This adaptor makes an undirected graph from a directed 1387 /// graph. All arc of the underlying digraph will be showed in the 1388 /// adaptor as an edge. Let's see an informal example about using 1389 /// this adaptor. 1390 /// 1391 /// There is a network of the streets of a town. Of course there are 1392 /// some one-way street in the town hence the network is a directed 1393 /// one. There is a crazy driver who go oppositely in the one-way 1394 /// street without moral sense. Of course he can pass this streets 1395 /// slower than the regular way, in fact his speed is half of the 1396 /// normal speed. How long should he drive to get from a source 1397 /// point to the target? Let see the example code which calculate it: 1398 /// 1399 /// \todo BadCode, SimpleMap does no exists 1400 ///\code 1401 /// typedef UndirDigraphAdaptor<Digraph> Graph; 1402 /// Graph graph(digraph); 1403 /// 1404 /// typedef SimpleMap<LengthMap> FLengthMap; 1405 /// FLengthMap flength(length); 1406 /// 1407 /// typedef ScaleMap<LengthMap> RLengthMap; 1408 /// RLengthMap rlength(length, 2.0); 1409 /// 1410 /// typedef Graph::CombinedArcMap<FLengthMap, RLengthMap > ULengthMap; 1411 /// ULengthMap ulength(flength, rlength); 1412 /// 1413 /// Dijkstra<Graph, ULengthMap> dijkstra(graph, ulength); 1414 /// std::cout << "Driving time : " << dijkstra.run(src, trg) << std::endl; 1415 ///\endcode 1416 /// 1417 /// The combined arc map makes the length map for the undirected 1418 /// graph. It is created from a forward and reverse map. The forward 1419 /// map is created from the original length map with a SimpleMap 1420 /// adaptor which just makes a read-write map from the reference map 1421 /// i.e. it forgets that it can be return reference to values. The 1422 /// reverse map is just the scaled original map with the ScaleMap 1423 /// adaptor. The combination solves that passing the reverse way 1424 /// takes double time than the original. To get the driving time we 1425 /// run the dijkstra algorithm on the graph. 2047 /// graph. All arcs of the underlying digraph will be showed in the 2048 /// adaptor as an edge. The Orienter adaptor is conform to the \ref 2049 /// concepts::Graph "Graph concept". 2050 /// 2051 /// \tparam _Digraph It must be conform to the \ref 2052 /// concepts::Digraph "Digraph concept". The type can be specified 2053 /// to const. 1426 2054 template<typename _Digraph> 1427 class Undir DigraphAdaptor1428 : public GraphAdaptorExtender<Undir DigraphAdaptorBase<_Digraph> > {2055 class Undirector 2056 : public GraphAdaptorExtender<UndirectorBase<_Digraph> > { 1429 2057 public: 1430 2058 typedef _Digraph Digraph; 1431 typedef GraphAdaptorExtender<Undir DigraphAdaptorBase<Digraph> > Parent;2059 typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent; 1432 2060 protected: 1433 Undir DigraphAdaptor() { }2061 Undirector() { } 1434 2062 public: 1435 2063 1436 2064 /// \brief Constructor 1437 2065 /// 1438 /// C onstructor1439 Undir DigraphAdaptor(_Digraph& _digraph) {1440 setDigraph( _digraph);2066 /// Creates a undirected graph from the given digraph 2067 Undirector(_Digraph& digraph) { 2068 setDigraph(digraph); 1441 2069 } 1442 2070 … … 1444 2072 /// 1445 2073 /// This class adapts two original digraph ArcMap to 1446 /// get an arc map on the adaptor.2074 /// get an arc map on the undirected graph. 1447 2075 template <typename _ForwardMap, typename _BackwardMap> 1448 2076 class CombinedArcMap { 1449 2077 public: 1450 2078 1451 2079 typedef _ForwardMap ForwardMap; 1452 2080 typedef _BackwardMap BackwardMap; … … 1457 2085 typedef typename Parent::Arc Key; 1458 2086 1459 /// \brief Constructor 2087 /// \brief Constructor 1460 2088 /// 1461 /// Constructor 1462 CombinedArcMap() : _forward(0), _backward(0) {} 1463 1464 /// \brief Constructor 1465 /// 1466 /// Constructor 1467 CombinedArcMap(ForwardMap& forward, BackwardMap& backward) 2089 /// Constructor 2090 CombinedArcMap(ForwardMap& forward, BackwardMap& backward) 1468 2091 : _forward(&forward), _backward(&backward) {} 1469 2092 1470 2093 1471 2094 /// \brief Sets the value associated with a key. 1472 2095 /// 1473 2096 /// Sets the value associated with a key. 1474 void set(const Key& e, const Value& a) { 1475 1476 _forward->set(e, a); 1477 } else { 1478 1479 } 2097 void set(const Key& e, const Value& a) { 2098 if (Parent::direction(e)) { 2099 _forward->set(e, a); 2100 } else { 2101 _backward->set(e, a); 2102 } 1480 2103 } 1481 2104 … … 1483 2106 /// 1484 2107 /// Returns the value associated with a key. 1485 typename MapTraits<ForwardMap>::ConstReturnValue 1486 operator[](const Key& e) const { 1487 1488 return (*_forward)[e]; 1489 } else { 1490 return (*_backward)[e]; 2108 typename MapTraits<ForwardMap>::ConstReturnValue 2109 operator[](const Key& e) const { 2110 if (Parent::direction(e)) { 2111 return (*_forward)[e]; 2112 } else { 2113 return (*_backward)[e]; 1491 2114 } 1492 2115 } … … 1495 2118 /// 1496 2119 /// Returns the value associated with a key. 1497 typename MapTraits<ForwardMap>::ReturnValue 1498 operator[](const Key& e) { 1499 1500 return (*_forward)[e]; 1501 } else { 1502 return (*_backward)[e]; 2120 typename MapTraits<ForwardMap>::ReturnValue 2121 operator[](const Key& e) { 2122 if (Parent::direction(e)) { 2123 return (*_forward)[e]; 2124 } else { 2125 return (*_backward)[e]; 1503 2126 } 1504 2127 } 1505 2128 1506 /// \brief Sets the forward map1507 ///1508 /// Sets the forward map1509 void setForwardMap(ForwardMap& forward) {1510 _forward = &forward;1511 }1512 1513 /// \brief Sets the backward map1514 ///1515 /// Sets the backward map1516 void setBackwardMap(BackwardMap& backward) {1517 _backward = &backward;1518 }1519 1520 2129 protected: 1521 2130 1522 2131 ForwardMap* _forward; 1523 BackwardMap* _backward; 2132 BackwardMap* _backward; 1524 2133 1525 2134 }; 1526 2135 2136 /// \brief Just gives back a combined arc map 2137 /// 2138 /// Just gives back a combined arc map 2139 template <typename ForwardMap, typename BackwardMap> 2140 static CombinedArcMap<ForwardMap, BackwardMap> 2141 combinedArcMap(ForwardMap& forward, BackwardMap& backward) { 2142 return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward); 2143 } 2144 2145 template <typename ForwardMap, typename BackwardMap> 2146 static CombinedArcMap<const ForwardMap, BackwardMap> 2147 combinedArcMap(const ForwardMap& forward, BackwardMap& backward) { 2148 return CombinedArcMap<const ForwardMap, 2149 BackwardMap>(forward, backward); 2150 } 2151 2152 template <typename ForwardMap, typename BackwardMap> 2153 static CombinedArcMap<ForwardMap, const BackwardMap> 2154 combinedArcMap(ForwardMap& forward, const BackwardMap& backward) { 2155 return CombinedArcMap<ForwardMap, 2156 const BackwardMap>(forward, backward); 2157 } 2158 2159 template <typename ForwardMap, typename BackwardMap> 2160 static CombinedArcMap<const ForwardMap, const BackwardMap> 2161 combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) { 2162 return CombinedArcMap<const ForwardMap, 2163 const BackwardMap>(forward, backward); 2164 } 2165 1527 2166 }; 1528 2167 1529 /// \brief Just gives back an undir digraph adaptor1530 /// 1531 /// Just gives back an undir digraph adaptor2168 /// \brief Just gives back an undirected view of the given digraph 2169 /// 2170 /// Just gives back an undirected view of the given digraph 1532 2171 template<typename Digraph> 1533 Undir DigraphAdaptor<const Digraph>1534 undir DigraphAdaptor(const Digraph& digraph) {1535 return Undir DigraphAdaptor<const Digraph>(digraph);2172 Undirector<const Digraph> 2173 undirector(const Digraph& digraph) { 2174 return Undirector<const Digraph>(digraph); 1536 2175 } 1537 2176 1538 template<typename _Digraph, 1539 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 1540 typename _FlowMap = _CapacityMap, 2177 template <typename _Graph, typename _DirectionMap> 2178 class OrienterBase { 2179 public: 2180 2181 typedef _Graph Graph; 2182 typedef _DirectionMap DirectionMap; 2183 2184 typedef typename Graph::Node Node; 2185 typedef typename Graph::Edge Arc; 2186 2187 void reverseArc(const Arc& arc) { 2188 _direction->set(arc, !(*_direction)[arc]); 2189 } 2190 2191 void first(Node& i) const { _graph->first(i); } 2192 void first(Arc& i) const { _graph->first(i); } 2193 void firstIn(Arc& i, const Node& n) const { 2194 bool d; 2195 _graph->firstInc(i, d, n); 2196 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); 2197 } 2198 void firstOut(Arc& i, const Node& n ) const { 2199 bool d; 2200 _graph->firstInc(i, d, n); 2201 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); 2202 } 2203 2204 void next(Node& i) const { _graph->next(i); } 2205 void next(Arc& i) const { _graph->next(i); } 2206 void nextIn(Arc& i) const { 2207 bool d = !(*_direction)[i]; 2208 _graph->nextInc(i, d); 2209 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); 2210 } 2211 void nextOut(Arc& i) const { 2212 bool d = (*_direction)[i]; 2213 _graph->nextInc(i, d); 2214 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); 2215 } 2216 2217 Node source(const Arc& e) const { 2218 return (*_direction)[e] ? _graph->u(e) : _graph->v(e); 2219 } 2220 Node target(const Arc& e) const { 2221 return (*_direction)[e] ? _graph->v(e) : _graph->u(e); 2222 } 2223 2224 typedef NodeNumTagIndicator<Graph> NodeNumTag; 2225 int nodeNum() const { return _graph->nodeNum(); } 2226 2227 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; 2228 int arcNum() const { return _graph->edgeNum(); } 2229 2230 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 2231 Arc findArc(const Node& u, const Node& v, 2232 const Arc& prev = INVALID) { 2233 Arc arc = prev; 2234 bool d = arc == INVALID ? true : (*_direction)[arc]; 2235 if (d) { 2236 arc = _graph->findEdge(u, v, arc); 2237 while (arc != INVALID && !(*_direction)[arc]) { 2238 _graph->findEdge(u, v, arc); 2239 } 2240 if (arc != INVALID) return arc; 2241 } 2242 _graph->findEdge(v, u, arc); 2243 while (arc != INVALID && (*_direction)[arc]) { 2244 _graph->findEdge(u, v, arc); 2245 } 2246 return arc; 2247 } 2248 2249 Node addNode() { 2250 return Node(_graph->addNode()); 2251 } 2252 2253 Arc addArc(const Node& u, const Node& v) { 2254 Arc arc = _graph->addArc(u, v); 2255 _direction->set(arc, _graph->source(arc) == u); 2256 return arc; 2257 } 2258 2259 void erase(const Node& i) { _graph->erase(i); } 2260 void erase(const Arc& i) { _graph->erase(i); } 2261 2262 void clear() { _graph->clear(); } 2263 2264 int id(const Node& v) const { return _graph->id(v); } 2265 int id(const Arc& e) const { return _graph->id(e); } 2266 2267 Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); } 2268 Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); } 2269 2270 int maxNodeId() const { return _graph->maxNodeId(); } 2271 int maxArcId() const { return _graph->maxEdgeId(); } 2272 2273 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; 2274 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 2275 2276 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier; 2277 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 2278 2279 template <typename _Value> 2280 class NodeMap : public _Graph::template NodeMap<_Value> { 2281 public: 2282 2283 typedef typename _Graph::template NodeMap<_Value> Parent; 2284 2285 explicit NodeMap(const OrienterBase& adapter) 2286 : Parent(*adapter._graph) {} 2287 2288 NodeMap(const OrienterBase& adapter, const _Value& value) 2289 : Parent(*adapter._graph, value) {} 2290 2291 private: 2292 NodeMap& operator=(const NodeMap& cmap) { 2293 return operator=<NodeMap>(cmap); 2294 } 2295 2296 template <typename CMap> 2297 NodeMap& operator=(const CMap& cmap) { 2298 Parent::operator=(cmap); 2299 return *this; 2300 } 2301 2302 }; 2303 2304 template <typename _Value> 2305 class ArcMap : public _Graph::template EdgeMap<_Value> { 2306 public: 2307 2308 typedef typename Graph::template EdgeMap<_Value> Parent; 2309 2310 explicit ArcMap(const OrienterBase& adapter) 2311 : Parent(*adapter._graph) { } 2312 2313 ArcMap(const OrienterBase& adapter, const _Value& value) 2314 : Parent(*adapter._graph, value) { } 2315 2316 private: 2317 ArcMap& operator=(const ArcMap& cmap) { 2318 return operator=<ArcMap>(cmap); 2319 } 2320 2321 template <typename CMap> 2322 ArcMap& operator=(const CMap& cmap) { 2323 Parent::operator=(cmap); 2324 return *this; 2325 } 2326 }; 2327 2328 2329 2330 protected: 2331 Graph* _graph; 2332 DirectionMap* _direction; 2333 2334 void setDirectionMap(DirectionMap& direction) { 2335 _direction = &direction; 2336 } 2337 2338 void setGraph(Graph& graph) { 2339 _graph = &graph; 2340 } 2341 2342 }; 2343 2344 /// \ingroup graph_adaptors 2345 /// 2346 /// \brief Orients the edges of the graph to get a digraph 2347 /// 2348 /// This adaptor orients each edge in the undirected graph. The 2349 /// direction of the arcs stored in an edge node map. The arcs can 2350 /// be easily reverted by the \c reverseArc() member function in the 2351 /// adaptor. The Orienter adaptor is conform to the \ref 2352 /// concepts::Digraph "Digraph concept". 2353 /// 2354 /// \tparam _Graph It must be conform to the \ref concepts::Graph 2355 /// "Graph concept". The type can be specified to be const. 2356 /// \tparam _DirectionMap A bool valued edge map of the the adapted 2357 /// graph. 2358 /// 2359 /// \sa orienter 2360 template<typename _Graph, 2361 typename DirectionMap = typename _Graph::template EdgeMap<bool> > 2362 class Orienter : 2363 public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > { 2364 public: 2365 typedef _Graph Graph; 2366 typedef DigraphAdaptorExtender< 2367 OrienterBase<_Graph, DirectionMap> > Parent; 2368 typedef typename Parent::Arc Arc; 2369 protected: 2370 Orienter() { } 2371 public: 2372 2373 /// \brief Constructor of the adaptor 2374 /// 2375 /// Constructor of the adaptor 2376 Orienter(Graph& graph, DirectionMap& direction) { 2377 setGraph(graph); 2378 setDirectionMap(direction); 2379 } 2380 2381 /// \brief Reverse arc 2382 /// 2383 /// It reverse the given arc. It simply negate the direction in the map. 2384 void reverseArc(const Arc& a) { 2385 Parent::reverseArc(a); 2386 } 2387 }; 2388 2389 /// \brief Just gives back a Orienter 2390 /// 2391 /// Just gives back a Orienter 2392 template<typename Graph, typename DirectionMap> 2393 Orienter<const Graph, DirectionMap> 2394 orienter(const Graph& graph, DirectionMap& dm) { 2395 return Orienter<const Graph, DirectionMap>(graph, dm); 2396 } 2397 2398 template<typename Graph, typename DirectionMap> 2399 Orienter<const Graph, const DirectionMap> 2400 orienter(const Graph& graph, const DirectionMap& dm) { 2401 return Orienter<const Graph, const DirectionMap>(graph, dm); 2402 } 2403 2404 namespace _adaptor_bits { 2405 2406 template<typename _Digraph, 2407 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 2408 typename _FlowMap = _CapacityMap, 2409 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 2410 class ResForwardFilter { 2411 public: 2412 2413 typedef _Digraph Digraph; 2414 typedef _CapacityMap CapacityMap; 2415 typedef _FlowMap FlowMap; 2416 typedef _Tolerance Tolerance; 2417 2418 typedef typename Digraph::Arc Key; 2419 typedef bool Value; 2420 2421 private: 2422 2423 const CapacityMap* _capacity; 2424 const FlowMap* _flow; 2425 Tolerance _tolerance; 2426 public: 2427 2428 ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow, 2429 const Tolerance& tolerance = Tolerance()) 2430 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2431 2432 bool operator[](const typename Digraph::Arc& a) const { 2433 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]); 2434 } 2435 }; 2436 2437 template<typename _Digraph, 2438 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 2439 typename _FlowMap = _CapacityMap, 2440 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 2441 class ResBackwardFilter { 2442 public: 2443 2444 typedef _Digraph Digraph; 2445 typedef _CapacityMap CapacityMap; 2446 typedef _FlowMap FlowMap; 2447 typedef _Tolerance Tolerance; 2448 2449 typedef typename Digraph::Arc Key; 2450 typedef bool Value; 2451 2452 private: 2453 2454 const CapacityMap* _capacity; 2455 const FlowMap* _flow; 2456 Tolerance _tolerance; 2457 2458 public: 2459 2460 ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow, 2461 const Tolerance& tolerance = Tolerance()) 2462 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2463 2464 bool operator[](const typename Digraph::Arc& a) const { 2465 return _tolerance.positive((*_flow)[a]); 2466 } 2467 }; 2468 2469 } 2470 2471 /// \ingroup graph_adaptors 2472 /// 2473 /// \brief An adaptor for composing the residual graph for directed 2474 /// flow and circulation problems. 2475 /// 2476 /// An adaptor for composing the residual graph for directed flow and 2477 /// circulation problems. Let \f$ G=(V, A) \f$ be a directed graph 2478 /// and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$, 2479 /// be functions on the arc-set. 2480 /// 2481 /// Then Residual implements the digraph structure with 2482 /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward} \f$, 2483 /// where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and 2484 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so 2485 /// called residual graph. When we take the union 2486 /// \f$ A_{forward}\cup A_{backward} \f$, multiplicities are counted, 2487 /// i.e. if an arc is in both \f$ A_{forward} \f$ and 2488 /// \f$ A_{backward} \f$, then in the adaptor it appears in both 2489 /// orientation. 2490 /// 2491 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 2492 /// "Digraph concept". The type is implicitly const. 2493 /// \tparam _CapacityMap An arc map of some numeric type, it defines 2494 /// the capacities in the flow problem. The map is implicitly const. 2495 /// \tparam _FlowMap An arc map of some numeric type, it defines 2496 /// the capacities in the flow problem. 2497 /// \tparam _Tolerance Handler for inexact computation. 2498 template<typename _Digraph, 2499 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 2500 typename _FlowMap = _CapacityMap, 1541 2501 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 1542 class ResForwardFilter { 2502 class Residual : 2503 public FilterArcs< 2504 Undirector<const _Digraph>, 2505 typename Undirector<const _Digraph>::template CombinedArcMap< 2506 _adaptor_bits::ResForwardFilter<const _Digraph, _CapacityMap, 2507 _FlowMap, _Tolerance>, 2508 _adaptor_bits::ResBackwardFilter<const _Digraph, _CapacityMap, 2509 _FlowMap, _Tolerance> > > 2510 { 1543 2511 public: 1544 2512 … … 1548 2516 typedef _Tolerance Tolerance; 1549 2517 1550 typedef typename Digraph::Arc Key;1551 typedef bool Value;1552 1553 private:1554 1555 const CapacityMap* _capacity;1556 const FlowMap* _flow;1557 Tolerance _tolerance;1558 public:1559 1560 ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow,1561 const Tolerance& tolerance = Tolerance())1562 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }1563 1564 ResForwardFilter(const Tolerance& tolerance = Tolerance())1565 : _capacity(0), _flow(0), _tolerance(tolerance) { }1566 1567 void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }1568 void setFlow(const FlowMap& flow) { _flow = &flow; }1569 1570 bool operator[](const typename Digraph::Arc& a) const {1571 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]);1572 }1573 };1574 1575 template<typename _Digraph,1576 typename _CapacityMap = typename _Digraph::template ArcMap<int>,1577 typename _FlowMap = _CapacityMap,1578 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >1579 class ResBackwardFilter {1580 public:1581 1582 typedef _Digraph Digraph;1583 typedef _CapacityMap CapacityMap;1584 typedef _FlowMap FlowMap;1585 typedef _Tolerance Tolerance;1586 1587 typedef typename Digraph::Arc Key;1588 typedef bool Value;1589 1590 private:1591 1592 const CapacityMap* _capacity;1593 const FlowMap* _flow;1594 Tolerance _tolerance;1595 1596 public:1597 1598 ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow,1599 const Tolerance& tolerance = Tolerance())1600 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { }1601 ResBackwardFilter(const Tolerance& tolerance = Tolerance())1602 : _capacity(0), _flow(0), _tolerance(tolerance) { }1603 1604 void setCapacity(const CapacityMap& capacity) { _capacity = &capacity; }1605 void setFlow(const FlowMap& flow) { _flow = &flow; }1606 1607 bool operator[](const typename Digraph::Arc& a) const {1608 return _tolerance.positive((*_flow)[a]);1609 }1610 };1611 1612 1613 ///\ingroup graph_adaptors1614 ///1615 ///\brief An adaptor for composing the residual graph for directed1616 ///flow and circulation problems.1617 ///1618 ///An adaptor for composing the residual graph for directed flow and1619 ///circulation problems. Let \f$ G=(V, A) \f$ be a directed digraph1620 ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F1621 ///\f$, be functions on the arc-set.1622 ///1623 ///In the appications of ResDigraphAdaptor, \f$ f \f$ usually stands1624 ///for a flow and \f$ c \f$ for a capacity function. Suppose that a1625 ///graph instance \c g of type \c ListDigraph implements \f$ G \f$.1626 ///1627 ///\code1628 /// ListDigraph g;1629 ///\endcode1630 ///1631 ///Then ResDigraphAdaptor implements the digraph structure with1632 /// node-set \f$ V \f$ and arc-set \f$ A_{forward}\cup A_{backward}1633 /// \f$, where \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and1634 /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, i.e. the so1635 /// called residual graph. When we take the union \f$1636 /// A_{forward}\cup A_{backward} \f$, multilicities are counted,1637 /// i.e. if an arc is in both \f$ A_{forward} \f$ and \f$1638 /// A_{backward} \f$, then in the adaptor it appears twice. The1639 /// following code shows how such an instance can be constructed.1640 ///1641 ///\code1642 /// typedef ListDigraph Digraph;1643 /// IntArcMap f(g), c(g);1644 /// ResDigraphAdaptor<Digraph, int, IntArcMap, IntArcMap> ga(g);1645 ///\endcode1646 template<typename _Digraph,1647 typename _CapacityMap = typename _Digraph::template ArcMap<int>,1648 typename _FlowMap = _CapacityMap,1649 typename _Tolerance = Tolerance<typename _CapacityMap::Value> >1650 class ResDigraphAdaptor :1651 public ArcSubDigraphAdaptor<1652 UndirDigraphAdaptor<const _Digraph>,1653 typename UndirDigraphAdaptor<const _Digraph>::template CombinedArcMap<1654 ResForwardFilter<const _Digraph, _CapacityMap, _FlowMap>,1655 ResBackwardFilter<const _Digraph, _CapacityMap, _FlowMap> > > {1656 public:1657 1658 typedef _Digraph Digraph;1659 typedef _CapacityMap CapacityMap;1660 typedef _FlowMap FlowMap;1661 typedef _Tolerance Tolerance;1662 1663 2518 typedef typename CapacityMap::Value Value; 1664 typedef Res DigraphAdaptorAdaptor;2519 typedef Residual Adaptor; 1665 2520 1666 2521 protected: 1667 2522 1668 typedef Undir DigraphAdaptor<const Digraph> UndirDigraph;1669 1670 typedef ResForwardFilter<const Digraph, CapacityMap, FlowMap>1671 ForwardFilter;1672 1673 typedef ResBackwardFilter<const Digraph, CapacityMap, FlowMap>1674 BackwardFilter;1675 1676 typedef typename Undir Digraph::2523 typedef Undirector<const Digraph> Undirected; 2524 2525 typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap, 2526 FlowMap, Tolerance> ForwardFilter; 2527 2528 typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap, 2529 FlowMap, Tolerance> BackwardFilter; 2530 2531 typedef typename Undirected:: 1677 2532 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter; 1678 2533 1679 typedef ArcSubDigraphAdaptor<UndirDigraph, ArcFilter> Parent;2534 typedef FilterArcs<Undirected, ArcFilter> Parent; 1680 2535 1681 2536 const CapacityMap* _capacity; 1682 2537 FlowMap* _flow; 1683 2538 1684 Undir Digraph_graph;2539 Undirected _graph; 1685 2540 ForwardFilter _forward_filter; 1686 2541 BackwardFilter _backward_filter; 1687 2542 ArcFilter _arc_filter; 1688 2543 1689 void setCapacityMap(const CapacityMap& capacity) {1690 _capacity = &capacity;1691 _forward_filter.setCapacity(capacity);1692 _backward_filter.setCapacity(capacity);1693 }1694 1695 void setFlowMap(FlowMap& flow) {1696 _flow = &flow;1697 _forward_filter.setFlow(flow);1698 _backward_filter.setFlow(flow);1699 }1700 1701 2544 public: 1702 2545 1703 2546 /// \brief Constructor of the residual digraph. 1704 2547 /// 1705 /// Constructor of the residual graph. The parameters are the digraph type,2548 /// Constructor of the residual graph. The parameters are the digraph, 1706 2549 /// the flow map, the capacity map and a tolerance object. 1707 Res DigraphAdaptor(const Digraph& digraph, const CapacityMap& capacity,1708 FlowMap& flow, const Tolerance& tolerance = Tolerance())2550 Residual(const Digraph& digraph, const CapacityMap& capacity, 2551 FlowMap& flow, const Tolerance& tolerance = Tolerance()) 1709 2552 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph), 1710 _forward_filter(capacity, flow, tolerance), 2553 _forward_filter(capacity, flow, tolerance), 1711 2554 _backward_filter(capacity, flow, tolerance), 1712 2555 _arc_filter(_forward_filter, _backward_filter) … … 1721 2564 /// 1722 2565 /// Gives back the residual capacity of the arc. 1723 Value res cap(const Arc& arc) const {1724 if (Undir Digraph::direction(arc)) {1725 return (*_capacity)[a rc] - (*_flow)[arc];2566 Value residualCapacity(const Arc& a) const { 2567 if (Undirected::direction(a)) { 2568 return (*_capacity)[a] - (*_flow)[a]; 1726 2569 } else { 1727 return (*_flow)[a rc];1728 } 1729 } 1730 1731 /// \brief Augment on the given arc in the residual digraph.1732 /// 1733 /// Augment on the given arc in the residual digraph. It increase2570 return (*_flow)[a]; 2571 } 2572 } 2573 2574 /// \brief Augment on the given arc in the residual graph. 2575 /// 2576 /// Augment on the given arc in the residual graph. It increase 1734 2577 /// or decrease the flow on the original arc depend on the direction 1735 2578 /// of the residual arc. 1736 void augment(const Arc& e, const Value& a) const {1737 if (Undir Digraph::direction(e)) {1738 _flow->set( e, (*_flow)[e] + a);1739 } else { 1740 _flow->set( e, (*_flow)[e] - a);2579 void augment(const Arc& a, const Value& v) const { 2580 if (Undirected::direction(a)) { 2581 _flow->set(a, (*_flow)[a] + v); 2582 } else { 2583 _flow->set(a, (*_flow)[a] - v); 1741 2584 } 1742 2585 } … … 1745 2588 /// 1746 2589 /// Returns true when the arc is same oriented as the original arc. 1747 static bool forward(const Arc& e) {1748 return Undir Digraph::direction(e);2590 static bool forward(const Arc& a) { 2591 return Undirected::direction(a); 1749 2592 } 1750 2593 … … 1752 2595 /// 1753 2596 /// Returns true when the arc is opposite oriented as the original arc. 1754 static bool backward(const Arc& e) {1755 return !Undir Digraph::direction(e);2597 static bool backward(const Arc& a) { 2598 return !Undirected::direction(a); 1756 2599 } 1757 2600 … … 1759 2602 /// 1760 2603 /// Gives back the forward oriented residual arc. 1761 static Arc forward(const typename Digraph::Arc& e) {1762 return Undir Digraph::direct(e, true);2604 static Arc forward(const typename Digraph::Arc& a) { 2605 return Undirected::direct(a, true); 1763 2606 } 1764 2607 … … 1766 2609 /// 1767 2610 /// Gives back the backward oriented residual arc. 1768 static Arc backward(const typename Digraph::Arc& e) {1769 return Undir Digraph::direct(e, false);2611 static Arc backward(const typename Digraph::Arc& a) { 2612 return Undirected::direct(a, false); 1770 2613 } 1771 2614 1772 2615 /// \brief Residual capacity map. 1773 2616 /// 1774 /// In generic residual digraphs the residual capacity can be obtained1775 /// as a map. 1776 class Res Cap{2617 /// In generic residual graph the residual capacity can be obtained 2618 /// as a map. 2619 class ResidualCapacity { 1777 2620 protected: 1778 2621 const Adaptor* _adaptor; 1779 2622 public: 2623 /// The Key type 1780 2624 typedef Arc Key; 2625 /// The Value type 1781 2626 typedef typename _CapacityMap::Value Value; 1782 2627 1783 ResCap(const Adaptor& adaptor) : _adaptor(&adaptor) {} 1784 1785 Value operator[](const Arc& e) const { 1786 return _adaptor->rescap(e); 1787 } 1788 2628 /// Constructor 2629 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {} 2630 2631 /// \e 2632 Value operator[](const Arc& a) const { 2633 return _adaptor->residualCapacity(a); 2634 } 2635 1789 2636 }; 1790 2637 … … 1792 2639 1793 2640 template <typename _Digraph> 1794 class Split DigraphAdaptorBase {2641 class SplitNodesBase { 1795 2642 public: 1796 2643 1797 2644 typedef _Digraph Digraph; 1798 2645 typedef DigraphAdaptorBase<const _Digraph> Parent; 1799 typedef Split DigraphAdaptorBase Adaptor;2646 typedef SplitNodesBase Adaptor; 1800 2647 1801 2648 typedef typename Digraph::Node DigraphNode; … … 1811 2658 1812 2659 public: 1813 2660 1814 2661 class Node : public DigraphNode { 1815 friend class Split DigraphAdaptorBase;2662 friend class SplitNodesBase; 1816 2663 template <typename T> friend class NodeMapBase; 1817 2664 private: … … 1819 2666 bool _in; 1820 2667 Node(DigraphNode node, bool in) 1821 1822 2668 : DigraphNode(node), _in(in) {} 2669 1823 2670 public: 1824 2671 … … 1827 2674 1828 2675 bool operator==(const Node& node) const { 1829 1830 } 1831 2676 return DigraphNode::operator==(node) && _in == node._in; 2677 } 2678 1832 2679 bool operator!=(const Node& node) const { 1833 1834 } 1835 2680 return !(*this == node); 2681 } 2682 1836 2683 bool operator<(const Node& node) const { 1837 return DigraphNode::operator<(node) || 1838 2684 return DigraphNode::operator<(node) || 2685 (DigraphNode::operator==(node) && _in < node._in); 1839 2686 } 1840 2687 }; 1841 2688 1842 2689 class Arc { 1843 friend class Split DigraphAdaptorBase;2690 friend class SplitNodesBase; 1844 2691 template <typename T> friend class ArcMapBase; 1845 2692 private: … … 1848 2695 explicit Arc(const DigraphArc& arc) : _item(arc) {} 1849 2696 explicit Arc(const DigraphNode& node) : _item(node) {} 1850 2697 1851 2698 ArcImpl _item; 1852 2699 … … 1867 2714 return false; 1868 2715 } 1869 2716 1870 2717 bool operator!=(const Arc& arc) const { 1871 1872 } 1873 2718 return !(*this == arc); 2719 } 2720 1874 2721 bool operator<(const Arc& arc) const { 1875 2722 if (_item.firstState()) { … … 1898 2745 void next(Node& n) const { 1899 2746 if (n._in) { 1900 2747 n._in = false; 1901 2748 } else { 1902 1903 2749 n._in = true; 2750 _digraph->next(n); 1904 2751 } 1905 2752 } … … 1910 2757 if (e._item.second() == INVALID) { 1911 2758 e._item.setFirst(); 1912 2759 _digraph->first(e._item.first()); 1913 2760 } 1914 2761 } … … 1916 2763 void next(Arc& e) const { 1917 2764 if (e._item.secondState()) { 1918 2765 _digraph->next(e._item.second()); 1919 2766 if (e._item.second() == INVALID) { 1920 2767 e._item.setFirst(); … … 1922 2769 } 1923 2770 } else { 1924 1925 } 2771 _digraph->next(e._item.first()); 2772 } 1926 2773 } 1927 2774 … … 1931 2778 } else { 1932 2779 e._item.setFirst(); 1933 2780 _digraph->firstOut(e._item.first(), n); 1934 2781 } 1935 2782 } … … 1937 2784 void nextOut(Arc& e) const { 1938 2785 if (!e._item.firstState()) { 1939 2786 e._item.setFirst(INVALID); 1940 2787 } else { 1941 1942 } 2788 _digraph->nextOut(e._item.first()); 2789 } 1943 2790 } 1944 2791 1945 2792 void firstIn(Arc& e, const Node& n) const { 1946 2793 if (!n._in) { 1947 e._item.setSecond(n); 2794 e._item.setSecond(n); 1948 2795 } else { 1949 2796 e._item.setFirst(); 1950 2797 _digraph->firstIn(e._item.first(), n); 1951 2798 } 1952 2799 } … … 1954 2801 void nextIn(Arc& e) const { 1955 2802 if (!e._item.firstState()) { 1956 2803 e._item.setFirst(INVALID); 1957 2804 } else { 1958 2805 _digraph->nextIn(e._item.first()); 1959 2806 } 1960 2807 } … … 1962 2809 Node source(const Arc& e) const { 1963 2810 if (e._item.firstState()) { 1964 2811 return Node(_digraph->source(e._item.first()), false); 1965 2812 } else { 1966 2813 return Node(e._item.second(), true); 1967 2814 } 1968 2815 } … … 1970 2817 Node target(const Arc& e) const { 1971 2818 if (e._item.firstState()) { 1972 2819 return Node(_digraph->target(e._item.first()), true); 1973 2820 } else { 1974 2821 return Node(e._item.second(), false); 1975 2822 } 1976 2823 } … … 2001 2848 } 2002 2849 int maxArcId() const { 2003 return std::max(_digraph->maxNodeId() << 1, 2850 return std::max(_digraph->maxNodeId() << 1, 2004 2851 (_digraph->maxArcId() << 1) | 1); 2005 2852 } … … 2049 2896 2050 2897 typedef True FindEdgeTag; 2051 Arc findArc(const Node& u, const Node& v, 2052 2898 Arc findArc(const Node& u, const Node& v, 2899 const Arc& prev = INVALID) const { 2053 2900 if (inNode(u)) { 2054 2901 if (outNode(v)) { 2055 if (static_cast<const DigraphNode&>(u) == 2902 if (static_cast<const DigraphNode&>(u) == 2056 2903 static_cast<const DigraphNode&>(v) && prev == INVALID) { 2057 2904 return Arc(u); … … 2067 2914 2068 2915 private: 2069 2916 2070 2917 template <typename _Value> 2071 class NodeMapBase 2918 class NodeMapBase 2072 2919 : public MapTraits<typename Parent::template NodeMap<_Value> > { 2073 2920 typedef typename Parent::template NodeMap<_Value> NodeImpl; … … 2075 2922 typedef Node Key; 2076 2923 typedef _Value Value; 2077 2078 NodeMapBase(const Adaptor& adaptor) 2079 2080 NodeMapBase(const Adaptor& adaptor, const Value& value) 2081 : _in_map(*adaptor._digraph, value), 2082 2924 2925 NodeMapBase(const Adaptor& adaptor) 2926 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {} 2927 NodeMapBase(const Adaptor& adaptor, const Value& value) 2928 : _in_map(*adaptor._digraph, value), 2929 _out_map(*adaptor._digraph, value) {} 2083 2930 2084 2931 void set(const Node& key, const Value& val) { 2085 2086 2087 } 2088 2089 typename MapTraits<NodeImpl>::ReturnValue 2932 if (Adaptor::inNode(key)) { _in_map.set(key, val); } 2933 else {_out_map.set(key, val); } 2934 } 2935 2936 typename MapTraits<NodeImpl>::ReturnValue 2090 2937 operator[](const Node& key) { 2091 2092 2938 if (Adaptor::inNode(key)) { return _in_map[key]; } 2939 else { return _out_map[key]; } 2093 2940 } 2094 2941 2095 2942 typename MapTraits<NodeImpl>::ConstReturnValue 2096 2943 operator[](const Node& key) const { 2097 2098 2944 if (Adaptor::inNode(key)) { return _in_map[key]; } 2945 else { return _out_map[key]; } 2099 2946 } 2100 2947 … … 2104 2951 2105 2952 template <typename _Value> 2106 class ArcMapBase 2953 class ArcMapBase 2107 2954 : public MapTraits<typename Parent::template ArcMap<_Value> > { 2108 2955 typedef typename Parent::template ArcMap<_Value> ArcImpl; … … 2112 2959 typedef _Value Value; 2113 2960 2114 ArcMapBase(const Adaptor& adaptor) 2115 2116 ArcMapBase(const Adaptor& adaptor, const Value& value) 2117 : _arc_map(*adaptor._digraph, value), 2118 2961 ArcMapBase(const Adaptor& adaptor) 2962 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {} 2963 ArcMapBase(const Adaptor& adaptor, const Value& value) 2964 : _arc_map(*adaptor._digraph, value), 2965 _node_map(*adaptor._digraph, value) {} 2119 2966 2120 2967 void set(const Arc& key, const Value& val) { 2121 if (Adaptor::origArc(key)) { 2122 _arc_map.set(key._item.first(), val); 2968 if (Adaptor::origArc(key)) { 2969 _arc_map.set(key._item.first(), val); 2123 2970 } else { 2124 _node_map.set(key._item.second(), val); 2971 _node_map.set(key._item.second(), val); 2125 2972 } 2126 2973 } 2127 2974 2128 2975 typename MapTraits<ArcImpl>::ReturnValue 2129 2976 operator[](const Arc& key) { 2130 if (Adaptor::origArc(key)) { 2977 if (Adaptor::origArc(key)) { 2131 2978 return _arc_map[key._item.first()]; 2132 2979 } else { … … 2137 2984 typename MapTraits<ArcImpl>::ConstReturnValue 2138 2985 operator[](const Arc& key) const { 2139 if (Adaptor::origArc(key)) { 2986 if (Adaptor::origArc(key)) { 2140 2987 return _arc_map[key._item.first()]; 2141 2988 } else { … … 2152 2999 2153 3000 template <typename _Value> 2154 class NodeMap 2155 : public SubMapExtender<Adaptor, NodeMapBase<_Value> > 3001 class NodeMap 3002 : public SubMapExtender<Adaptor, NodeMapBase<_Value> > 2156 3003 { 2157 3004 public: 2158 3005 typedef _Value Value; 2159 3006 typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent; 2160 2161 NodeMap(const Adaptor& adaptor) 2162 2163 2164 NodeMap(const Adaptor& adaptor, const Value& value) 2165 2166 3007 3008 NodeMap(const Adaptor& adaptor) 3009 : Parent(adaptor) {} 3010 3011 NodeMap(const Adaptor& adaptor, const Value& value) 3012 : Parent(adaptor, value) {} 3013 2167 3014 private: 2168 3015 NodeMap& operator=(const NodeMap& cmap) { 2169 2170 } 2171 3016 return operator=<NodeMap>(cmap); 3017 } 3018 2172 3019 template <typename CMap> 2173 3020 NodeMap& operator=(const CMap& cmap) { 2174 3021 Parent::operator=(cmap); 2175 3022 return *this; 2176 3023 } 2177 3024 }; 2178 3025 2179 3026 template <typename _Value> 2180 class ArcMap 2181 : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 3027 class ArcMap 3028 : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 2182 3029 { 2183 3030 public: 2184 3031 typedef _Value Value; 2185 3032 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; 2186 2187 ArcMap(const Adaptor& adaptor) 2188 2189 2190 ArcMap(const Adaptor& adaptor, const Value& value) 2191 2192 3033 3034 ArcMap(const Adaptor& adaptor) 3035 : Parent(adaptor) {} 3036 3037 ArcMap(const Adaptor& adaptor, const Value& value) 3038 : Parent(adaptor, value) {} 3039 2193 3040 private: 2194 3041 ArcMap& operator=(const ArcMap& cmap) { 2195 2196 } 2197 3042 return operator=<ArcMap>(cmap); 3043 } 3044 2198 3045 template <typename CMap> 2199 3046 ArcMap& operator=(const CMap& cmap) { 2200 3047 Parent::operator=(cmap); 2201 3048 return *this; 2202 3049 } 2203 3050 }; … … 2205 3052 protected: 2206 3053 2207 Split DigraphAdaptorBase() : _digraph(0) {}3054 SplitNodesBase() : _digraph(0) {} 2208 3055 2209 3056 Digraph* _digraph; … … 2212 3059 _digraph = &digraph; 2213 3060 } 2214 3061 2215 3062 }; 2216 3063 2217 3064 /// \ingroup graph_adaptors 2218 3065 /// 2219 /// \brief Split digraph adaptor class2220 /// 2221 /// Th is is an digraph adaptor which splits all node into an in-node2222 /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$2223 /// node in the digraph with two node, \f$ u_{in} \f$ node and2224 /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ arc in the2225 /// original digraph the new target of the arc will be \f$ u_{in} \f$ and2226 /// similarly the source of the original \f$ (u, v) \f$ arc will be2227 /// \f$ u_{out} \f$. The adaptor will add for each node in the2228 /// original digraph an additional arc which will connect3066 /// \brief Split the nodes of a directed graph 3067 /// 3068 /// The SplitNodes adaptor splits each node into an in-node and an 3069 /// out-node. Formaly, the adaptor replaces each \f$ u \f$ node in 3070 /// the digraph with two nodes(namely node \f$ u_{in} \f$ and node 3071 /// \f$ u_{out} \f$). If there is a \f$ (v, u) \f$ arc in the 3072 /// original digraph the new target of the arc will be \f$ u_{in} \f$ 3073 /// and similarly the source of the original \f$ (u, v) \f$ arc 3074 /// will be \f$ u_{out} \f$. The adaptor will add for each node in 3075 /// the original digraph an additional arc which connects 2229 3076 /// \f$ (u_{in}, u_{out}) \f$. 2230 3077 /// 2231 /// The aim of this class is to run algorithm with node costs if the 3078 /// The aim of this class is to run algorithm with node costs if the 2232 3079 /// algorithm can use directly just arc costs. In this case we should use 2233 /// a \c SplitDigraphAdaptor and set the node cost of the digraph to the 2234 /// bind arc in the adapted digraph. 2235 /// 2236 /// For example a maximum flow algorithm can compute how many arc 2237 /// disjoint paths are in the digraph. But we would like to know how 2238 /// many node disjoint paths are in the digraph. First we have to 2239 /// adapt the digraph with the \c SplitDigraphAdaptor. Then run the flow 2240 /// algorithm on the adapted digraph. The bottleneck of the flow will 2241 /// be the bind arcs which bounds the flow with the count of the 2242 /// node disjoint paths. 2243 /// 2244 ///\code 2245 /// 2246 /// typedef SplitDigraphAdaptor<SmartDigraph> SDigraph; 2247 /// 2248 /// SDigraph sdigraph(digraph); 2249 /// 2250 /// typedef ConstMap<SDigraph::Arc, int> SCapacity; 2251 /// SCapacity scapacity(1); 2252 /// 2253 /// SDigraph::ArcMap<int> sflow(sdigraph); 2254 /// 2255 /// Preflow<SDigraph, SCapacity> 2256 /// spreflow(sdigraph, scapacity, 2257 /// SDigraph::outNode(source), SDigraph::inNode(target)); 2258 /// 2259 /// spreflow.run(); 2260 /// 2261 ///\endcode 2262 /// 2263 /// The result of the mamixum flow on the original digraph 2264 /// shows the next figure: 2265 /// 2266 /// \image html arc_disjoint.png 2267 /// \image latex arc_disjoint.eps "Arc disjoint paths" width=\textwidth 2268 /// 2269 /// And the maximum flow on the adapted digraph: 2270 /// 2271 /// \image html node_disjoint.png 2272 /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth 2273 /// 2274 /// The second solution contains just 3 disjoint paths while the first 4. 2275 /// The full code can be found in the \ref disjoint_paths_demo.cc demo file. 2276 /// 2277 /// This digraph adaptor is fully conform to the 2278 /// \ref concepts::Digraph "Digraph" concept and 2279 /// contains some additional member functions and types. The 2280 /// documentation of some member functions may be found just in the 2281 /// SplitDigraphAdaptorBase class. 2282 /// 2283 /// \sa SplitDigraphAdaptorBase 3080 /// a \c SplitNodes and set the node cost of the graph to the 3081 /// bind arc in the adapted graph. 3082 /// 3083 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 3084 /// "Digraph concept". The type can be specified to be const. 2284 3085 template <typename _Digraph> 2285 class Split DigraphAdaptor2286 : public DigraphAdaptorExtender<Split DigraphAdaptorBase<_Digraph> > {3086 class SplitNodes 3087 : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > { 2287 3088 public: 2288 3089 typedef _Digraph Digraph; 2289 typedef DigraphAdaptorExtender<Split DigraphAdaptorBase<Digraph> > Parent;3090 typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent; 2290 3091 2291 3092 typedef typename Digraph::Node DigraphNode; … … 2298 3099 /// 2299 3100 /// Constructor of the adaptor. 2300 Split DigraphAdaptor(Digraph& g) {3101 SplitNodes(Digraph& g) { 2301 3102 Parent::setDigraph(g); 2302 3103 } … … 2345 3146 2346 3147 /// \brief Gives back the arc binds the two part of the node. 2347 /// 3148 /// 2348 3149 /// Gives back the arc binds the two part of the node. 2349 3150 static Arc arc(const DigraphNode& n) { … … 2352 3153 2353 3154 /// \brief Gives back the arc of the original arc. 2354 /// 3155 /// 2355 3156 /// Gives back the arc of the original arc. 2356 3157 static Arc arc(const DigraphArc& a) { … … 2372 3173 /// 2373 3174 /// Constructor. 2374 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) 2375 3175 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) 3176 : _in_map(in_map), _out_map(out_map) {} 2376 3177 2377 3178 /// \brief The subscript operator. … … 2379 3180 /// The subscript operator. 2380 3181 Value& operator[](const Key& key) { 2381 2382 2383 2384 2385 3182 if (Parent::inNode(key)) { 3183 return _in_map[key]; 3184 } else { 3185 return _out_map[key]; 3186 } 2386 3187 } 2387 3188 … … 2390 3191 /// The const subscript operator. 2391 3192 Value operator[](const Key& key) const { 2392 2393 2394 2395 2396 3193 if (Parent::inNode(key)) { 3194 return _in_map[key]; 3195 } else { 3196 return _out_map[key]; 3197 } 2397 3198 } 2398 3199 2399 3200 /// \brief The setter function of the map. 2400 /// 3201 /// 2401 3202 /// The setter function of the map. 2402 3203 void set(const Key& key, const Value& value) { 2403 2404 2405 2406 2407 2408 } 2409 3204 if (Parent::inNode(key)) { 3205 _in_map.set(key, value); 3206 } else { 3207 _out_map.set(key, value); 3208 } 3209 } 3210 2410 3211 private: 2411 3212 2412 3213 InNodeMap& _in_map; 2413 3214 OutNodeMap& _out_map; 2414 3215 2415 3216 }; 2416 3217 2417 3218 2418 /// \brief Just gives back a combined node map .2419 /// 2420 /// Just gives back a combined node map .3219 /// \brief Just gives back a combined node map 3220 /// 3221 /// Just gives back a combined node map 2421 3222 template <typename InNodeMap, typename OutNodeMap> 2422 static CombinedNodeMap<InNodeMap, OutNodeMap> 3223 static CombinedNodeMap<InNodeMap, OutNodeMap> 2423 3224 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) { 2424 3225 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map); … … 2426 3227 2427 3228 template <typename InNodeMap, typename OutNodeMap> 2428 static CombinedNodeMap<const InNodeMap, OutNodeMap> 3229 static CombinedNodeMap<const InNodeMap, OutNodeMap> 2429 3230 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) { 2430 3231 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map); … … 2432 3233 2433 3234 template <typename InNodeMap, typename OutNodeMap> 2434 static CombinedNodeMap<InNodeMap, const OutNodeMap> 3235 static CombinedNodeMap<InNodeMap, const OutNodeMap> 2435 3236 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) { 2436 3237 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map); … … 2438 3239 2439 3240 template <typename InNodeMap, typename OutNodeMap> 2440 static CombinedNodeMap<const InNodeMap, const OutNodeMap> 3241 static CombinedNodeMap<const InNodeMap, const OutNodeMap> 2441 3242 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) { 2442 return CombinedNodeMap<const InNodeMap, 3243 return CombinedNodeMap<const InNodeMap, 2443 3244 const OutNodeMap>(in_map, out_map); 2444 3245 } 2445 3246 2446 /// \brief ArcMap combined from an original ArcMap and NodeMap2447 /// 2448 /// This class adapt an original digraph ArcMap and NodeMap to2449 /// get an arc map on the adapted digraph.3247 /// \brief ArcMap combined from an original ArcMap and a NodeMap 3248 /// 3249 /// This class adapt an original ArcMap and a NodeMap to get an 3250 /// arc map on the adapted digraph 2450 3251 template <typename DigraphArcMap, typename DigraphNodeMap> 2451 3252 class CombinedArcMap { 2452 3253 public: 2453 3254 2454 3255 typedef Arc Key; 2455 3256 typedef typename DigraphArcMap::Value Value; 2456 3257 2457 3258 /// \brief Constructor 2458 3259 /// 2459 3260 /// Constructor. 2460 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) 2461 3261 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) 3262 : _arc_map(arc_map), _node_map(node_map) {} 2462 3263 2463 3264 /// \brief The subscript operator. … … 2465 3266 /// The subscript operator. 2466 3267 void set(const Arc& arc, const Value& val) { 2467 2468 2469 2470 2471 3268 if (Parent::origArc(arc)) { 3269 _arc_map.set(arc, val); 3270 } else { 3271 _node_map.set(arc, val); 3272 } 2472 3273 } 2473 3274 … … 2476 3277 /// The const subscript operator. 2477 3278 Value operator[](const Key& arc) const { 2478 2479 2480 2481 2482 2483 } 3279 if (Parent::origArc(arc)) { 3280 return _arc_map[arc]; 3281 } else { 3282 return _node_map[arc]; 3283 } 3284 } 2484 3285 2485 3286 /// \brief The const subscript operator. … … 2487 3288 /// The const subscript operator. 2488 3289 Value& operator[](const Key& arc) { 2489 2490 2491 2492 2493 2494 } 2495 3290 if (Parent::origArc(arc)) { 3291 return _arc_map[arc]; 3292 } else { 3293 return _node_map[arc]; 3294 } 3295 } 3296 2496 3297 private: 2497 3298 DigraphArcMap& _arc_map; 2498 3299 DigraphNodeMap& _node_map; 2499 3300 }; 2500 2501 /// \brief Just gives back a combined arc map .2502 /// 2503 /// Just gives back a combined arc map .3301 3302 /// \brief Just gives back a combined arc map 3303 /// 3304 /// Just gives back a combined arc map 2504 3305 template <typename DigraphArcMap, typename DigraphNodeMap> 2505 static CombinedArcMap<DigraphArcMap, DigraphNodeMap> 3306 static CombinedArcMap<DigraphArcMap, DigraphNodeMap> 2506 3307 combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) { 2507 3308 return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map); … … 2509 3310 2510 3311 template <typename DigraphArcMap, typename DigraphNodeMap> 2511 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap> 3312 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap> 2512 3313 combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) { 2513 return CombinedArcMap<const DigraphArcMap, 3314 return CombinedArcMap<const DigraphArcMap, 2514 3315 DigraphNodeMap>(arc_map, node_map); 2515 3316 } 2516 3317 2517 3318 template <typename DigraphArcMap, typename DigraphNodeMap> 2518 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap> 3319 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap> 2519 3320 combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) { 2520 return CombinedArcMap<DigraphArcMap, 3321 return CombinedArcMap<DigraphArcMap, 2521 3322 const DigraphNodeMap>(arc_map, node_map); 2522 3323 } 2523 3324 2524 3325 template <typename DigraphArcMap, typename DigraphNodeMap> 2525 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap> 2526 combinedArcMap(const DigraphArcMap& arc_map, 2527 2528 return CombinedArcMap<const DigraphArcMap, 3326 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap> 3327 combinedArcMap(const DigraphArcMap& arc_map, 3328 const DigraphNodeMap& node_map) { 3329 return CombinedArcMap<const DigraphArcMap, 2529 3330 const DigraphNodeMap>(arc_map, node_map); 2530 3331 } … … 2532 3333 }; 2533 3334 2534 /// \brief Just gives back a split digraph adaptor2535 /// 2536 /// Just gives back a split digraph adaptor3335 /// \brief Just gives back a node splitter 3336 /// 3337 /// Just gives back a node splitter 2537 3338 template<typename Digraph> 2538 Split DigraphAdaptor<Digraph>2539 split DigraphAdaptor(const Digraph& digraph) {2540 return Split DigraphAdaptor<Digraph>(digraph);3339 SplitNodes<Digraph> 3340 splitNodes(const Digraph& digraph) { 3341 return SplitNodes<Digraph>(digraph); 2541 3342 } 2542 3343 … … 2544 3345 } //namespace lemon 2545 3346 2546 #endif //LEMON_DIGRAPH_ADAPTOR_H 2547 3347 #endif //LEMON_ADAPTORS_H -
lemon/bits/graph_adaptor_extender.h
r414 r416 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 25 25 #include <lemon/bits/default_map.h> 26 26 27 28 ///\ingroup digraphbits29 ///\file30 ///\brief Extenders for the digraph adaptor types31 27 namespace lemon { 32 28 33 /// \ingroup digraphbits34 ///35 /// \brief Extender for the DigraphAdaptors36 29 template <typename _Digraph> 37 30 class DigraphAdaptorExtender : public _Digraph { … … 65 58 Node oppositeNode(const Node &n, const Arc &e) const { 66 59 if (n == Parent::source(e)) 67 60 return Parent::target(e); 68 61 else if(n==Parent::target(e)) 69 62 return Parent::source(e); 70 63 else 71 72 } 73 74 class NodeIt : public Node { 64 return INVALID; 65 } 66 67 class NodeIt : public Node { 75 68 const Adaptor* _adaptor; 76 69 public: … … 81 74 82 75 explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { 83 84 } 85 86 NodeIt(const Adaptor& adaptor, const Node& node) 87 88 89 NodeIt& operator++() { 90 91 return *this; 92 } 93 94 }; 95 96 97 class ArcIt : public Arc { 76 _adaptor->first(static_cast<Node&>(*this)); 77 } 78 79 NodeIt(const Adaptor& adaptor, const Node& node) 80 : Node(node), _adaptor(&adaptor) {} 81 82 NodeIt& operator++() { 83 _adaptor->next(*this); 84 return *this; 85 } 86 87 }; 88 89 90 class ArcIt : public Arc { 98 91 const Adaptor* _adaptor; 99 92 public: … … 104 97 105 98 explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) { 106 107 } 108 109 ArcIt(const Adaptor& adaptor, const Arc& e) : 110 111 112 ArcIt& operator++() { 113 114 return *this; 115 } 116 117 }; 118 119 120 class OutArcIt : public Arc { 99 _adaptor->first(static_cast<Arc&>(*this)); 100 } 101 102 ArcIt(const Adaptor& adaptor, const Arc& e) : 103 Arc(e), _adaptor(&adaptor) { } 104 105 ArcIt& operator++() { 106 _adaptor->next(*this); 107 return *this; 108 } 109 110 }; 111 112 113 class OutArcIt : public Arc { 121 114 const Adaptor* _adaptor; 122 115 public: … … 126 119 OutArcIt(Invalid i) : Arc(i) { } 127 120 128 OutArcIt(const Adaptor& adaptor, const Node& node) 129 130 131 } 132 133 OutArcIt(const Adaptor& adaptor, const Arc& arc) 134 135 136 OutArcIt& operator++() { 137 138 return *this; 139 } 140 141 }; 142 143 144 class InArcIt : public Arc { 121 OutArcIt(const Adaptor& adaptor, const Node& node) 122 : _adaptor(&adaptor) { 123 _adaptor->firstOut(*this, node); 124 } 125 126 OutArcIt(const Adaptor& adaptor, const Arc& arc) 127 : Arc(arc), _adaptor(&adaptor) {} 128 129 OutArcIt& operator++() { 130 _adaptor->nextOut(*this); 131 return *this; 132 } 133 134 }; 135 136 137 class InArcIt : public Arc { 145 138 const Adaptor* _adaptor; 146 139 public: … … 150 143 InArcIt(Invalid i) : Arc(i) { } 151 144 152 InArcIt(const Adaptor& adaptor, const Node& node) 153 : _adaptor(&adaptor) { 154 _adaptor->firstIn(*this, node); 155 } 156 157 InArcIt(const Adaptor& adaptor, const Arc& arc) : 158 Arc(arc), _adaptor(&adaptor) {} 159 160 InArcIt& operator++() { 161 _adaptor->nextIn(*this); 162 return *this; 163 } 164 165 }; 166 167 /// \brief Base node of the iterator 168 /// 169 /// Returns the base node (ie. the source in this case) of the iterator 145 InArcIt(const Adaptor& adaptor, const Node& node) 146 : _adaptor(&adaptor) { 147 _adaptor->firstIn(*this, node); 148 } 149 150 InArcIt(const Adaptor& adaptor, const Arc& arc) : 151 Arc(arc), _adaptor(&adaptor) {} 152 153 InArcIt& operator++() { 154 _adaptor->nextIn(*this); 155 return *this; 156 } 157 158 }; 159 170 160 Node baseNode(const OutArcIt &e) const { 171 161 return Parent::source(e); 172 162 } 173 /// \brief Running node of the iterator174 ///175 /// Returns the running node (ie. the target in this case) of the176 /// iterator177 163 Node runningNode(const OutArcIt &e) const { 178 164 return Parent::target(e); 179 165 } 180 166 181 /// \brief Base node of the iterator182 ///183 /// Returns the base node (ie. the target in this case) of the iterator184 167 Node baseNode(const InArcIt &e) const { 185 168 return Parent::target(e); 186 169 } 187 /// \brief Running node of the iterator188 ///189 /// Returns the running node (ie. the source in this case) of the190 /// iterator191 170 Node runningNode(const InArcIt &e) const { 192 171 return Parent::source(e); … … 199 178 /// 200 179 /// \brief Extender for the GraphAdaptors 201 template <typename _Graph> 180 template <typename _Graph> 202 181 class GraphAdaptorExtender : public _Graph { 203 182 public: 204 183 205 184 typedef _Graph Parent; 206 185 typedef _Graph Graph; … … 211 190 typedef typename Parent::Edge Edge; 212 191 213 // Graph extension 192 // Graph extension 214 193 215 194 int maxId(Node) const { … … 239 218 Node oppositeNode(const Node &n, const Edge &e) const { 240 219 if( n == Parent::u(e)) 241 220 return Parent::v(e); 242 221 else if( n == Parent::v(e)) 243 222 return Parent::u(e); 244 223 else 245 224 return INVALID; 246 225 } 247 226 … … 256 235 257 236 258 class NodeIt : public Node { 237 class NodeIt : public Node { 259 238 const Adaptor* _adaptor; 260 239 public: … … 265 244 266 245 explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { 267 268 } 269 270 NodeIt(const Adaptor& adaptor, const Node& node) 271 272 273 NodeIt& operator++() { 274 275 return *this; 276 } 277 278 }; 279 280 281 class ArcIt : public Arc { 246 _adaptor->first(static_cast<Node&>(*this)); 247 } 248 249 NodeIt(const Adaptor& adaptor, const Node& node) 250 : Node(node), _adaptor(&adaptor) {} 251 252 NodeIt& operator++() { 253 _adaptor->next(*this); 254 return *this; 255 } 256 257 }; 258 259 260 class ArcIt : public Arc { 282 261 const Adaptor* _adaptor; 283 262 public: … … 288 267 289 268 explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) { 290 291 } 292 293 ArcIt(const Adaptor& adaptor, const Arc& e) : 294 295 296 ArcIt& operator++() { 297 298 return *this; 299 } 300 301 }; 302 303 304 class OutArcIt : public Arc { 269 _adaptor->first(static_cast<Arc&>(*this)); 270 } 271 272 ArcIt(const Adaptor& adaptor, const Arc& e) : 273 Arc(e), _adaptor(&adaptor) { } 274 275 ArcIt& operator++() { 276 _adaptor->next(*this); 277 return *this; 278 } 279 280 }; 281 282 283 class OutArcIt : public Arc { 305 284 const Adaptor* _adaptor; 306 285 public: … … 310 289 OutArcIt(Invalid i) : Arc(i) { } 311 290 312 OutArcIt(const Adaptor& adaptor, const Node& node) 313 314 315 } 316 317 OutArcIt(const Adaptor& adaptor, const Arc& arc) 318 319 320 OutArcIt& operator++() { 321 322 return *this; 323 } 324 325 }; 326 327 328 class InArcIt : public Arc { 291 OutArcIt(const Adaptor& adaptor, const Node& node) 292 : _adaptor(&adaptor) { 293 _adaptor->firstOut(*this, node); 294 } 295 296 OutArcIt(const Adaptor& adaptor, const Arc& arc) 297 : Arc(arc), _adaptor(&adaptor) {} 298 299 OutArcIt& operator++() { 300 _adaptor->nextOut(*this); 301 return *this; 302 } 303 304 }; 305 306 307 class InArcIt : public Arc { 329 308 const Adaptor* _adaptor; 330 309 public: … … 334 313 InArcIt(Invalid i) : Arc(i) { } 335 314 336 InArcIt(const Adaptor& adaptor, const Node& node) 337 338 339 } 340 341 InArcIt(const Adaptor& adaptor, const Arc& arc) : 342 343 344 InArcIt& operator++() { 345 346 return *this; 347 } 348 349 }; 350 351 class EdgeIt : public Parent::Edge { 315 InArcIt(const Adaptor& adaptor, const Node& node) 316 : _adaptor(&adaptor) { 317 _adaptor->firstIn(*this, node); 318 } 319 320 InArcIt(const Adaptor& adaptor, const Arc& arc) : 321 Arc(arc), _adaptor(&adaptor) {} 322 323 InArcIt& operator++() { 324 _adaptor->nextIn(*this); 325 return *this; 326 } 327 328 }; 329 330 class EdgeIt : public Parent::Edge { 352 331 const Adaptor* _adaptor; 353 332 public: … … 358 337 359 338 explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) { 360 361 } 362 363 EdgeIt(const Adaptor& adaptor, const Edge& e) : 364 365 366 EdgeIt& operator++() { 367 368 return *this; 369 } 370 371 }; 372 373 class IncEdgeIt : public Edge { 339 _adaptor->first(static_cast<Edge&>(*this)); 340 } 341 342 EdgeIt(const Adaptor& adaptor, const Edge& e) : 343 Edge(e), _adaptor(&adaptor) { } 344 345 EdgeIt& operator++() { 346 _adaptor->next(*this); 347 return *this; 348 } 349 350 }; 351 352 class IncEdgeIt : public Edge { 374 353 friend class GraphAdaptorExtender; 375 354 const Adaptor* _adaptor; … … 382 361 383 362 IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) { 384 363 _adaptor->firstInc(static_cast<Edge&>(*this), direction, n); 385 364 } 386 365 387 366 IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n) 388 389 367 : _adaptor(&adaptor), Edge(e) { 368 direction = (_adaptor->u(e) == n); 390 369 } 391 370 392 371 IncEdgeIt& operator++() { 393 _adaptor->nextInc(*this, direction); 394 return *this; 395 } 396 }; 397 398 /// \brief Base node of the iterator 399 /// 400 /// Returns the base node (ie. the source in this case) of the iterator 372 _adaptor->nextInc(*this, direction); 373 return *this; 374 } 375 }; 376 401 377 Node baseNode(const OutArcIt &a) const { 402 378 return Parent::source(a); 403 379 } 404 /// \brief Running node of the iterator405 ///406 /// Returns the running node (ie. the target in this case) of the407 /// iterator408 380 Node runningNode(const OutArcIt &a) const { 409 381 return Parent::target(a); 410 382 } 411 383 412 /// \brief Base node of the iterator413 ///414 /// Returns the base node (ie. the target in this case) of the iterator415 384 Node baseNode(const InArcIt &a) const { 416 385 return Parent::target(a); 417 386 } 418 /// \brief Running node of the iterator419 ///420 /// Returns the running node (ie. the source in this case) of the421 /// iterator422 387 Node runningNode(const InArcIt &a) const { 423 388 return Parent::source(a); 424 389 } 425 390 426 /// Base node of the iterator427 ///428 /// Returns the base node of the iterator429 391 Node baseNode(const IncEdgeIt &e) const { 430 392 return e.direction ? Parent::u(e) : Parent::v(e); 431 393 } 432 /// Running node of the iterator433 ///434 /// Returns the running node of the iterator435 394 Node runningNode(const IncEdgeIt &e) const { 436 395 return e.direction ? Parent::v(e) : Parent::u(e); -
lemon/bits/variant.h
r414 r416 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 28 28 29 29 namespace _variant_bits { 30 30 31 31 template <int left, int right> 32 32 struct CTMax { … … 87 87 flag = bivariant.flag; 88 88 if (flag) { 89 new(reinterpret_cast<First*>(data)) First(bivariant.first()); 89 new(reinterpret_cast<First*>(data)) First(bivariant.first()); 90 90 } else { 91 new(reinterpret_cast<Second*>(data)) Second(bivariant.second()); 91 new(reinterpret_cast<Second*>(data)) Second(bivariant.second()); 92 92 } 93 93 } … … 107 107 destroy(); 108 108 flag = true; 109 new(reinterpret_cast<First*>(data)) First(); 109 new(reinterpret_cast<First*>(data)) First(); 110 110 return *this; 111 111 } … … 118 118 destroy(); 119 119 flag = true; 120 new(reinterpret_cast<First*>(data)) First(f); 120 new(reinterpret_cast<First*>(data)) First(f); 121 121 return *this; 122 122 } … … 129 129 destroy(); 130 130 flag = false; 131 new(reinterpret_cast<Second*>(data)) Second(); 131 new(reinterpret_cast<Second*>(data)) Second(); 132 132 return *this; 133 133 } … … 140 140 destroy(); 141 141 flag = false; 142 new(reinterpret_cast<Second*>(data)) Second(s); 142 new(reinterpret_cast<Second*>(data)) Second(s); 143 143 return *this; 144 144 } … … 160 160 flag = bivariant.flag; 161 161 if (flag) { 162 new(reinterpret_cast<First*>(data)) First(bivariant.first()); 162 new(reinterpret_cast<First*>(data)) First(bivariant.first()); 163 163 } else { 164 new(reinterpret_cast<Second*>(data)) Second(bivariant.second()); 164 new(reinterpret_cast<Second*>(data)) Second(bivariant.second()); 165 165 } 166 166 return *this; … … 232 232 } 233 233 } 234 234 235 235 char data[_variant_bits::CTMax<sizeof(First), sizeof(Second)>::value]; 236 236 bool flag; … … 238 238 239 239 namespace _variant_bits { 240 240 241 241 template <int _idx, typename _TypeMap> 242 242 struct Memory { … … 277 277 template <int _idx, typename _TypeMap> 278 278 struct Size { 279 static const int value = 280 CTMax<sizeof(typename _TypeMap::template Map<_idx>::Type), 279 static const int value = 280 CTMax<sizeof(typename _TypeMap::template Map<_idx>::Type), 281 281 Size<_idx - 1, _TypeMap>::value>::value; 282 282 }; … … 284 284 template <typename _TypeMap> 285 285 struct Size<0, _TypeMap> { 286 static const int value = 286 static const int value = 287 287 sizeof(typename _TypeMap::template Map<0>::Type); 288 288 }; … … 302 302 /// variant type. 303 303 /// \param _TypeMap This class describes the types of the Variant. The 304 /// _TypeMap::Map<index>::Type should be a valid type for each index 304 /// _TypeMap::Map<index>::Type should be a valid type for each index 305 305 /// in the range {0, 1, ..., _num - 1}. The \c VariantTypeMap is helper 306 306 /// class to define such type mappings up to 10 types. … … 338 338 Variant() { 339 339 flag = 0; 340 new(reinterpret_cast<typename TypeMap::template Map<0>::Type*>(data)) 340 new(reinterpret_cast<typename TypeMap::template Map<0>::Type*>(data)) 341 341 typename TypeMap::template Map<0>::Type(); 342 342 } … … 379 379 _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data); 380 380 flag = _idx; 381 new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data)) 381 new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data)) 382 382 typename TypeMap::template Map<_idx>::Type(); 383 383 return *this; … … 392 392 _variant_bits::Memory<num - 1, TypeMap>::destroy(flag, data); 393 393 flag = _idx; 394 new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data)) 394 new(reinterpret_cast<typename TypeMap::template Map<_idx>::Type*>(data)) 395 395 typename TypeMap::template Map<_idx>::Type(init); 396 396 return *this; … … 404 404 LEMON_DEBUG(_idx == flag, "Variant wrong index"); 405 405 return *reinterpret_cast<const typename TypeMap:: 406 template Map<_idx>::Type*>(data); 406 template Map<_idx>::Type*>(data); 407 407 } 408 408 … … 414 414 LEMON_DEBUG(_idx == flag, "Variant wrong index"); 415 415 return *reinterpret_cast<typename TypeMap::template Map<_idx>::Type*> 416 (data); 416 (data); 417 417 } 418 418 … … 425 425 426 426 private: 427 427 428 428 char data[_variant_bits::Size<num - 1, TypeMap>::value]; 429 429 int flag; … … 443 443 444 444 struct List {}; 445 445 446 446 template <typename _Type, typename _List> 447 447 struct Insert { … … 450 450 }; 451 451 452 template <int _idx, typename _T0, typename _T1, typename _T2, 452 template <int _idx, typename _T0, typename _T1, typename _T2, 453 453 typename _T3, typename _T5, typename _T4, typename _T6, 454 454 typename _T7, typename _T8, typename _T9> … … 467 467 typedef typename Get<_idx, L0>::Type Type; 468 468 }; 469 469 470 470 } 471 471 … … 476 476 /// \see Variant 477 477 template < 478 typename _T0, 478 typename _T0, 479 479 typename _T1 = void, typename _T2 = void, typename _T3 = void, 480 480 typename _T5 = void, typename _T4 = void, typename _T6 = void, … … 488 488 }; 489 489 }; 490 490 491 491 } 492 492
Note: See TracChangeset
for help on using the changeset viewer.