Changes in lemon/adaptors.h [432:76287c8caa26:566:c786cd201266] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/adaptors.h
r432 r566 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 22 22 /// \ingroup graph_adaptors 23 23 /// \file 24 /// \brief Several graph adaptors24 /// \brief Adaptor classes for digraphs and graphs 25 25 /// 26 26 /// This file contains several useful adaptors for digraphs and graphs. … … 31 31 32 32 #include <lemon/bits/graph_adaptor_extender.h> 33 #include <lemon/bits/map_extender.h> 33 34 #include <lemon/tolerance.h> 34 35 … … 37 38 namespace lemon { 38 39 39 template<typename _Digraph> 40 #ifdef _MSC_VER 41 #define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED 42 #else 43 #define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED 44 #endif 45 46 template<typename DGR> 40 47 class DigraphAdaptorBase { 41 48 public: 42 typedef _DigraphDigraph;49 typedef DGR Digraph; 43 50 typedef DigraphAdaptorBase Adaptor; 44 typedef Digraph ParentDigraph;45 51 46 52 protected: 47 D igraph* _digraph;53 DGR* _digraph; 48 54 DigraphAdaptorBase() : _digraph(0) { } 49 void setDigraph(Digraph& digraph) { _digraph = &digraph; }50 51 public: 52 DigraphAdaptorBase(D igraph& digraph) : _digraph(&digraph) { }53 54 typedef typename D igraph::Node Node;55 typedef typename D igraph::Arc Arc;55 void initialize(DGR& digraph) { _digraph = &digraph; } 56 57 public: 58 DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { } 59 60 typedef typename DGR::Node Node; 61 typedef typename DGR::Arc Arc; 56 62 57 63 void first(Node& i) const { _digraph->first(i); } … … 68 74 Node target(const Arc& a) const { return _digraph->target(a); } 69 75 70 typedef NodeNumTagIndicator<D igraph> NodeNumTag;76 typedef NodeNumTagIndicator<DGR> NodeNumTag; 71 77 int nodeNum() const { return _digraph->nodeNum(); } 72 78 73 typedef EdgeNumTagIndicator<Digraph> EdgeNumTag;79 typedef ArcNumTagIndicator<DGR> ArcNumTag; 74 80 int arcNum() const { return _digraph->arcNum(); } 75 81 76 typedef Find EdgeTagIndicator<Digraph> FindEdgeTag;77 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) {82 typedef FindArcTagIndicator<DGR> FindArcTag; 83 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const { 78 84 return _digraph->findArc(u, v, prev); 79 85 } … … 82 88 Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); } 83 89 84 void erase(const Node& n) const{ _digraph->erase(n); }85 void erase(const Arc& a) const{ _digraph->erase(a); }86 87 void clear() const{ _digraph->clear(); }90 void erase(const Node& n) { _digraph->erase(n); } 91 void erase(const Arc& a) { _digraph->erase(a); } 92 93 void clear() { _digraph->clear(); } 88 94 89 95 int id(const Node& n) const { return _digraph->id(n); } … … 96 102 int maxArcId() const { return _digraph->maxArcId(); } 97 103 98 typedef typename ItemSetTraits<D igraph, Node>::ItemNotifier NodeNotifier;104 typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier; 99 105 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 100 106 101 typedef typename ItemSetTraits<D igraph, Arc>::ItemNotifier ArcNotifier;107 typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier; 102 108 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); } 103 109 104 template <typename _Value>105 class NodeMap : public D igraph::template NodeMap<_Value> {110 template <typename V> 111 class NodeMap : public DGR::template NodeMap<V> { 106 112 public: 107 113 108 typedef typename D igraph::template NodeMap<_Value> Parent;114 typedef typename DGR::template NodeMap<V> Parent; 109 115 110 116 explicit NodeMap(const Adaptor& adaptor) 111 117 : Parent(*adaptor._digraph) {} 112 118 113 NodeMap(const Adaptor& adaptor, const _Value& value)119 NodeMap(const Adaptor& adaptor, const V& value) 114 120 : Parent(*adaptor._digraph, value) { } 115 121 … … 127 133 }; 128 134 129 template <typename _Value>130 class ArcMap : public D igraph::template ArcMap<_Value> {135 template <typename V> 136 class ArcMap : public DGR::template ArcMap<V> { 131 137 public: 132 138 133 typedef typename D igraph::template ArcMap<_Value> Parent;134 135 explicit ArcMap(const Adaptor& adaptor)139 typedef typename DGR::template ArcMap<V> Parent; 140 141 explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor) 136 142 : Parent(*adaptor._digraph) {} 137 143 138 ArcMap(const Adaptor& adaptor, const _Value& value)144 ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value) 139 145 : Parent(*adaptor._digraph, value) {} 140 146 … … 154 160 }; 155 161 156 template<typename _Graph>162 template<typename GR> 157 163 class GraphAdaptorBase { 158 164 public: 159 typedef _Graph Graph; 160 typedef Graph ParentGraph; 165 typedef GR Graph; 161 166 162 167 protected: 163 G raph* _graph;168 GR* _graph; 164 169 165 170 GraphAdaptorBase() : _graph(0) {} 166 171 167 void setGraph(Graph& graph) { _graph = &graph; }168 169 public: 170 GraphAdaptorBase(G raph& graph) : _graph(&graph) {}171 172 typedef typename G raph::Node Node;173 typedef typename G raph::Arc Arc;174 typedef typename G raph::Edge Edge;172 void initialize(GR& graph) { _graph = &graph; } 173 174 public: 175 GraphAdaptorBase(GR& graph) : _graph(&graph) {} 176 177 typedef typename GR::Node Node; 178 typedef typename GR::Arc Arc; 179 typedef typename GR::Edge Edge; 175 180 176 181 void first(Node& i) const { _graph->first(i); } … … 199 204 int nodeNum() const { return _graph->nodeNum(); } 200 205 206 typedef ArcNumTagIndicator<Graph> ArcNumTag; 207 int arcNum() const { return _graph->arcNum(); } 208 201 209 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; 202 int arcNum() const { return _graph->arcNum(); }203 210 int edgeNum() const { return _graph->edgeNum(); } 204 211 212 typedef FindArcTagIndicator<Graph> FindArcTag; 213 Arc findArc(const Node& u, const Node& v, 214 const Arc& prev = INVALID) const { 215 return _graph->findArc(u, v, prev); 216 } 217 205 218 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) { 219 Edge findEdge(const Node& u, const Node& v, 220 const Edge& prev = INVALID) const { 210 221 return _graph->findEdge(u, v, prev); 211 222 } … … 234 245 int maxEdgeId() const { return _graph->maxEdgeId(); } 235 246 236 typedef typename ItemSetTraits<G raph, Node>::ItemNotifier NodeNotifier;247 typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier; 237 248 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 238 249 239 typedef typename ItemSetTraits<G raph, Arc>::ItemNotifier ArcNotifier;250 typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier; 240 251 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 241 252 242 typedef typename ItemSetTraits<G raph, Edge>::ItemNotifier EdgeNotifier;253 typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier; 243 254 EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); } 244 255 245 template <typename _Value>246 class NodeMap : public G raph::template NodeMap<_Value> {256 template <typename V> 257 class NodeMap : public GR::template NodeMap<V> { 247 258 public: 248 typedef typename G raph::template NodeMap<_Value> Parent;249 explicit NodeMap(const GraphAdaptorBase<G raph>& adapter)259 typedef typename GR::template NodeMap<V> Parent; 260 explicit NodeMap(const GraphAdaptorBase<GR>& adapter) 250 261 : Parent(*adapter._graph) {} 251 NodeMap(const GraphAdaptorBase<G raph>& adapter, const _Value& value)262 NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value) 252 263 : Parent(*adapter._graph, value) {} 253 264 … … 265 276 }; 266 277 267 template <typename _Value>268 class ArcMap : public G raph::template ArcMap<_Value> {278 template <typename V> 279 class ArcMap : public GR::template ArcMap<V> { 269 280 public: 270 typedef typename G raph::template ArcMap<_Value> Parent;271 explicit ArcMap(const GraphAdaptorBase<G raph>& adapter)281 typedef typename GR::template ArcMap<V> Parent; 282 explicit ArcMap(const GraphAdaptorBase<GR>& adapter) 272 283 : Parent(*adapter._graph) {} 273 ArcMap(const GraphAdaptorBase<G raph>& adapter, const _Value& value)284 ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value) 274 285 : Parent(*adapter._graph, value) {} 275 286 … … 286 297 }; 287 298 288 template <typename _Value>289 class EdgeMap : public G raph::template EdgeMap<_Value> {299 template <typename V> 300 class EdgeMap : public GR::template EdgeMap<V> { 290 301 public: 291 typedef typename G raph::template EdgeMap<_Value> Parent;292 explicit EdgeMap(const GraphAdaptorBase<G raph>& adapter)302 typedef typename GR::template EdgeMap<V> Parent; 303 explicit EdgeMap(const GraphAdaptorBase<GR>& adapter) 293 304 : Parent(*adapter._graph) {} 294 EdgeMap(const GraphAdaptorBase<G raph>& adapter, const _Value& value)305 EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value) 295 306 : Parent(*adapter._graph, value) {} 296 307 … … 309 320 }; 310 321 311 template <typename _Digraph>312 class ReverseDigraphBase : public DigraphAdaptorBase< _Digraph> {313 public: 314 typedef _DigraphDigraph;315 typedef DigraphAdaptorBase< _Digraph> Parent;322 template <typename DGR> 323 class ReverseDigraphBase : public DigraphAdaptorBase<DGR> { 324 public: 325 typedef DGR Digraph; 326 typedef DigraphAdaptorBase<DGR> Parent; 316 327 protected: 317 328 ReverseDigraphBase() : Parent() { } … … 331 342 Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); } 332 343 333 typedef Find EdgeTagIndicator<Digraph> FindEdgeTag;344 typedef FindArcTagIndicator<DGR> FindArcTag; 334 345 Arc findArc(const Node& u, const Node& v, 335 const Arc& prev = INVALID) {346 const Arc& prev = INVALID) const { 336 347 return Parent::findArc(v, u, prev); 337 348 } … … 341 352 /// \ingroup graph_adaptors 342 353 /// 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. 351 template<typename _Digraph> 354 /// \brief Adaptor class for reversing the orientation of the arcs in 355 /// a digraph. 356 /// 357 /// ReverseDigraph can be used for reversing the arcs in a digraph. 358 /// It conforms to the \ref concepts::Digraph "Digraph" concept. 359 /// 360 /// The adapted digraph can also be modified through this adaptor 361 /// by adding or removing nodes or arcs, unless the \c GR template 362 /// parameter is set to be \c const. 363 /// 364 /// \tparam DGR The type of the adapted digraph. 365 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 366 /// It can also be specified to be \c const. 367 /// 368 /// \note The \c Node and \c Arc types of this adaptor and the adapted 369 /// digraph are convertible to each other. 370 template<typename DGR> 371 #ifdef DOXYGEN 372 class ReverseDigraph { 373 #else 352 374 class ReverseDigraph : 353 public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > { 354 public: 355 typedef _Digraph Digraph; 356 typedef DigraphAdaptorExtender< 357 ReverseDigraphBase<_Digraph> > Parent; 375 public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > { 376 #endif 377 public: 378 /// The type of the adapted digraph. 379 typedef DGR Digraph; 380 typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent; 358 381 protected: 359 382 ReverseDigraph() { } … … 362 385 /// \brief Constructor 363 386 /// 364 /// Creates a reverse digraph adaptor for the given digraph 365 explicit ReverseDigraph(D igraph& digraph) {366 Parent:: setDigraph(digraph);387 /// Creates a reverse digraph adaptor for the given digraph. 388 explicit ReverseDigraph(DGR& digraph) { 389 Parent::initialize(digraph); 367 390 } 368 391 }; 369 392 370 /// \brief Just gives back a reverse digraph adaptor 371 /// 372 /// Just gives back a reverse digraph adaptor 373 template<typename Digraph> 374 ReverseDigraph<const Digraph> reverseDigraph(const Digraph& digraph) { 375 return ReverseDigraph<const Digraph>(digraph); 393 /// \brief Returns a read-only ReverseDigraph adaptor 394 /// 395 /// This function just returns a read-only \ref ReverseDigraph adaptor. 396 /// \ingroup graph_adaptors 397 /// \relates ReverseDigraph 398 template<typename DGR> 399 ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) { 400 return ReverseDigraph<const DGR>(digraph); 376 401 } 377 402 378 template <typename _Digraph, typename _NodeFilterMap, 379 typename _ArcFilterMap, bool _checked= true>380 class SubDigraphBase : public DigraphAdaptorBase< _Digraph> {381 public: 382 typedef _DigraphDigraph;383 typedef _NodeFilterMapNodeFilterMap;384 typedef _ArcFilterMapArcFilterMap;403 404 template <typename DGR, typename NF, typename AF, bool ch = true> 405 class SubDigraphBase : public DigraphAdaptorBase<DGR> { 406 public: 407 typedef DGR Digraph; 408 typedef NF NodeFilterMap; 409 typedef AF ArcFilterMap; 385 410 386 411 typedef SubDigraphBase Adaptor; 387 typedef DigraphAdaptorBase< _Digraph> Parent;412 typedef DigraphAdaptorBase<DGR> Parent; 388 413 protected: 389 N odeFilterMap* _node_filter;390 A rcFilterMap* _arc_filter;414 NF* _node_filter; 415 AF* _arc_filter; 391 416 SubDigraphBase() 392 417 : Parent(), _node_filter(0), _arc_filter(0) { } 393 418 394 void setNodeFilterMap(NodeFilterMap& node_filter) { 419 void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { 420 Parent::initialize(digraph); 395 421 _node_filter = &node_filter; 396 } 397 void setArcFilterMap(ArcFilterMap& arc_filter) { 398 _arc_filter = &arc_filter; 422 _arc_filter = &arc_filter; 399 423 } 400 424 … … 458 482 } 459 483 460 void hide(const Node& n) const { _node_filter->set(n, false); } 461 void hide(const Arc& a) const { _arc_filter->set(a, false); } 462 463 void unHide(const Node& n) const { _node_filter->set(n, true); } 464 void unHide(const Arc& a) const { _arc_filter->set(a, true); } 465 466 bool hidden(const Node& n) const { return !(*_node_filter)[n]; } 467 bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; } 484 void status(const Node& n, bool v) const { _node_filter->set(n, v); } 485 void status(const Arc& a, bool v) const { _arc_filter->set(a, v); } 486 487 bool status(const Node& n) const { return (*_node_filter)[n]; } 488 bool status(const Arc& a) const { return (*_arc_filter)[a]; } 468 489 469 490 typedef False NodeNumTag; 470 typedef False EdgeNumTag;471 472 typedef Find EdgeTagIndicator<Digraph> FindEdgeTag;491 typedef False ArcNumTag; 492 493 typedef FindArcTagIndicator<DGR> FindArcTag; 473 494 Arc findArc(const Node& source, const Node& target, 474 const Arc& prev = INVALID) {495 const Arc& prev = INVALID) const { 475 496 if (!(*_node_filter)[source] || !(*_node_filter)[target]) { 476 497 return INVALID; … … 483 504 } 484 505 485 template <typename _Value> 486 class NodeMap : public SubMapExtender<Adaptor, 487 typename Parent::template NodeMap<_Value> > { 506 public: 507 508 template <typename V> 509 class NodeMap 510 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 511 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> { 488 512 public: 489 typedef _ValueValue;490 typedef SubMapExtender< Adaptor, typename Parent::491 template NodeMap<Value> > MapParent;492 493 NodeMap(const Adaptor& adaptor)494 : MapParent(adaptor) {}495 NodeMap(const Adaptor& adaptor, const Value& value)496 : MapParent(adaptor, value) {}513 typedef V Value; 514 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 515 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent; 516 517 NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor) 518 : Parent(adaptor) {} 519 NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value) 520 : Parent(adaptor, value) {} 497 521 498 522 private: … … 503 527 template <typename CMap> 504 528 NodeMap& operator=(const CMap& cmap) { 505 MapParent::operator=(cmap);529 Parent::operator=(cmap); 506 530 return *this; 507 531 } 508 532 }; 509 533 510 template <typename _Value> 511 class ArcMap : public SubMapExtender<Adaptor, 512 typename Parent::template ArcMap<_Value> > { 534 template <typename V> 535 class ArcMap 536 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 537 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> { 513 538 public: 514 typedef _ValueValue;515 typedef SubMapExtender< Adaptor, typename Parent::516 template ArcMap<Value> > MapParent;517 518 ArcMap(const Adaptor& adaptor)519 : MapParent(adaptor) {}520 ArcMap(const Adaptor& adaptor, const Value& value)521 : MapParent(adaptor, value) {}539 typedef V Value; 540 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 541 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent; 542 543 ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor) 544 : Parent(adaptor) {} 545 ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value) 546 : Parent(adaptor, value) {} 522 547 523 548 private: … … 528 553 template <typename CMap> 529 554 ArcMap& operator=(const CMap& cmap) { 530 MapParent::operator=(cmap);555 Parent::operator=(cmap); 531 556 return *this; 532 557 } … … 535 560 }; 536 561 537 template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>538 class SubDigraphBase< _Digraph, _NodeFilterMap, _ArcFilterMap, false>539 : public DigraphAdaptorBase< _Digraph> {540 public: 541 typedef _DigraphDigraph;542 typedef _NodeFilterMapNodeFilterMap;543 typedef _ArcFilterMapArcFilterMap;562 template <typename DGR, typename NF, typename AF> 563 class SubDigraphBase<DGR, NF, AF, false> 564 : public DigraphAdaptorBase<DGR> { 565 public: 566 typedef DGR Digraph; 567 typedef NF NodeFilterMap; 568 typedef AF ArcFilterMap; 544 569 545 570 typedef SubDigraphBase Adaptor; 546 571 typedef DigraphAdaptorBase<Digraph> Parent; 547 572 protected: 548 N odeFilterMap* _node_filter;549 A rcFilterMap* _arc_filter;573 NF* _node_filter; 574 AF* _arc_filter; 550 575 SubDigraphBase() 551 576 : Parent(), _node_filter(0), _arc_filter(0) { } 552 577 553 void setNodeFilterMap(NodeFilterMap& node_filter) { 578 void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { 579 Parent::initialize(digraph); 554 580 _node_filter = &node_filter; 555 } 556 void setArcFilterMap(ArcFilterMap& arc_filter) { 557 _arc_filter = &arc_filter; 581 _arc_filter = &arc_filter; 558 582 } 559 583 … … 601 625 } 602 626 603 void hide(const Node& n) const { _node_filter->set(n, false); } 604 void hide(const Arc& e) const { _arc_filter->set(e, false); } 605 606 void unHide(const Node& n) const { _node_filter->set(n, true); } 607 void unHide(const Arc& e) const { _arc_filter->set(e, true); } 608 609 bool hidden(const Node& n) const { return !(*_node_filter)[n]; } 610 bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; } 627 void status(const Node& n, bool v) const { _node_filter->set(n, v); } 628 void status(const Arc& a, bool v) const { _arc_filter->set(a, v); } 629 630 bool status(const Node& n) const { return (*_node_filter)[n]; } 631 bool status(const Arc& a) const { return (*_arc_filter)[a]; } 611 632 612 633 typedef False NodeNumTag; 613 typedef False EdgeNumTag;614 615 typedef Find EdgeTagIndicator<Digraph> FindEdgeTag;634 typedef False ArcNumTag; 635 636 typedef FindArcTagIndicator<DGR> FindArcTag; 616 637 Arc findArc(const Node& source, const Node& target, 617 const Arc& prev = INVALID) {638 const Arc& prev = INVALID) const { 618 639 if (!(*_node_filter)[source] || !(*_node_filter)[target]) { 619 640 return INVALID; … … 626 647 } 627 648 628 template <typename _Value> 629 class NodeMap : public SubMapExtender<Adaptor, 630 typename Parent::template NodeMap<_Value> > { 649 template <typename V> 650 class NodeMap 651 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 652 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> { 631 653 public: 632 typedef _ValueValue;633 typedef SubMapExtender< Adaptor, typename Parent::634 template NodeMap<Value> > MapParent;635 636 NodeMap(const Adaptor& adaptor)637 : MapParent(adaptor) {}638 NodeMap(const Adaptor& adaptor, const Value& value)639 : MapParent(adaptor, value) {}654 typedef V Value; 655 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 656 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent; 657 658 NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor) 659 : Parent(adaptor) {} 660 NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value) 661 : Parent(adaptor, value) {} 640 662 641 663 private: … … 646 668 template <typename CMap> 647 669 NodeMap& operator=(const CMap& cmap) { 648 MapParent::operator=(cmap);670 Parent::operator=(cmap); 649 671 return *this; 650 672 } 651 673 }; 652 674 653 template <typename _Value> 654 class ArcMap : public SubMapExtender<Adaptor, 655 typename Parent::template ArcMap<_Value> > { 675 template <typename V> 676 class ArcMap 677 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 678 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> { 656 679 public: 657 typedef _ValueValue;658 typedef SubMapExtender< Adaptor, typename Parent::659 template ArcMap<Value> > MapParent;660 661 ArcMap(const Adaptor& adaptor)662 : MapParent(adaptor) {}663 ArcMap(const Adaptor& adaptor, const Value& value)664 : MapParent(adaptor, value) {}680 typedef V Value; 681 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 682 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent; 683 684 ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor) 685 : Parent(adaptor) {} 686 ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value) 687 : Parent(adaptor, value) {} 665 688 666 689 private: … … 671 694 template <typename CMap> 672 695 ArcMap& operator=(const CMap& cmap) { 673 MapParent::operator=(cmap);696 Parent::operator=(cmap); 674 697 return *this; 675 698 } … … 680 703 /// \ingroup graph_adaptors 681 704 /// 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. 705 /// \brief Adaptor class for hiding nodes and arcs in a digraph 706 /// 707 /// SubDigraph can be used for hiding nodes and arcs in a digraph. 708 /// A \c bool node map and a \c bool arc map must be specified, which 709 /// define the filters for nodes and arcs. 710 /// Only the nodes and arcs with \c true filter value are 711 /// shown in the subdigraph. The arcs that are incident to hidden 712 /// nodes are also filtered out. 713 /// This adaptor conforms to the \ref concepts::Digraph "Digraph" concept. 714 /// 715 /// The adapted digraph can also be modified through this adaptor 716 /// by adding or removing nodes or arcs, unless the \c GR template 717 /// parameter is set to be \c const. 718 /// 719 /// \tparam DGR The type of the adapted digraph. 720 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 721 /// It can also be specified to be \c const. 722 /// \tparam NF The type of the node filter map. 723 /// It must be a \c bool (or convertible) node map of the 724 /// adapted digraph. The default type is 725 /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>". 726 /// \tparam AF The type of the arc filter map. 727 /// It must be \c bool (or convertible) arc map of the 728 /// adapted digraph. The default type is 729 /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>". 730 /// 731 /// \note The \c Node and \c Arc types of this adaptor and the adapted 732 /// digraph are convertible to each other. 700 733 /// 701 734 /// \see FilterNodes 702 735 /// \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> > { 710 public: 711 typedef _Digraph Digraph; 712 typedef _NodeFilterMap NodeFilterMap; 713 typedef _ArcFilterMap ArcFilterMap; 714 715 typedef DigraphAdaptorExtender< 716 SubDigraphBase<Digraph, NodeFilterMap, ArcFilterMap, _checked> > 717 Parent; 736 #ifdef DOXYGEN 737 template<typename DGR, typename NF, typename AF> 738 class SubDigraph { 739 #else 740 template<typename DGR, 741 typename NF = typename DGR::template NodeMap<bool>, 742 typename AF = typename DGR::template ArcMap<bool> > 743 class SubDigraph : 744 public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > { 745 #endif 746 public: 747 /// The type of the adapted digraph. 748 typedef DGR Digraph; 749 /// The type of the node filter map. 750 typedef NF NodeFilterMap; 751 /// The type of the arc filter map. 752 typedef AF ArcFilterMap; 753 754 typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > 755 Parent; 718 756 719 757 typedef typename Parent::Node Node; … … 726 764 /// \brief Constructor 727 765 /// 728 /// Creates a subdigraph for the given digraph with 729 /// given node and arc map filters. 730 SubDigraph(Digraph& digraph, NodeFilterMap& node_filter, 731 ArcFilterMap& arc_filter) { 732 setDigraph(digraph); 733 setNodeFilterMap(node_filter); 734 setArcFilterMap(arc_filter); 735 } 736 737 /// \brief Hides the node of the graph 738 /// 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 741 /// to be false in the corresponding node-map. 742 void hide(const Node& n) const { Parent::hide(n); } 743 744 /// \brief Hides the arc of the graph 745 /// 746 /// This function hides \c a in the digraph, i.e. the iteration 747 /// jumps over it. This is done by simply setting the value of \c a 748 /// to be false in the corresponding arc-map. 749 void hide(const Arc& a) const { Parent::hide(a); } 750 751 /// \brief Unhides the node of the graph 752 /// 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 755 /// again 756 void unHide(const Node& n) const { Parent::unHide(n); } 757 758 /// \brief Unhides the arc of the graph 759 /// 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 762 /// again 763 void unHide(const Arc& a) const { Parent::unHide(a); } 764 765 /// \brief Returns true if \c n is hidden. 766 /// 767 /// Returns true if \c n is hidden. 768 /// 769 bool hidden(const Node& n) const { return Parent::hidden(n); } 770 771 /// \brief Returns true if \c a is hidden. 772 /// 773 /// Returns true if \c a is hidden. 774 /// 775 bool hidden(const Arc& a) const { return Parent::hidden(a); } 766 /// Creates a subdigraph for the given digraph with the 767 /// given node and arc filter maps. 768 SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) { 769 Parent::initialize(digraph, node_filter, arc_filter); 770 } 771 772 /// \brief Sets the status of the given node 773 /// 774 /// This function sets the status of the given node. 775 /// It is done by simply setting the assigned value of \c n 776 /// to \c v in the node filter map. 777 void status(const Node& n, bool v) const { Parent::status(n, v); } 778 779 /// \brief Sets the status of the given arc 780 /// 781 /// This function sets the status of the given arc. 782 /// It is done by simply setting the assigned value of \c a 783 /// to \c v in the arc filter map. 784 void status(const Arc& a, bool v) const { Parent::status(a, v); } 785 786 /// \brief Returns the status of the given node 787 /// 788 /// This function returns the status of the given node. 789 /// It is \c true if the given node is enabled (i.e. not hidden). 790 bool status(const Node& n) const { return Parent::status(n); } 791 792 /// \brief Returns the status of the given arc 793 /// 794 /// This function returns the status of the given arc. 795 /// It is \c true if the given arc is enabled (i.e. not hidden). 796 bool status(const Arc& a) const { return Parent::status(a); } 797 798 /// \brief Disables the given node 799 /// 800 /// This function disables the given node in the subdigraph, 801 /// so the iteration jumps over it. 802 /// It is the same as \ref status() "status(n, false)". 803 void disable(const Node& n) const { Parent::status(n, false); } 804 805 /// \brief Disables the given arc 806 /// 807 /// This function disables the given arc in the subdigraph, 808 /// so the iteration jumps over it. 809 /// It is the same as \ref status() "status(a, false)". 810 void disable(const Arc& a) const { Parent::status(a, false); } 811 812 /// \brief Enables the given node 813 /// 814 /// This function enables the given node in the subdigraph. 815 /// It is the same as \ref status() "status(n, true)". 816 void enable(const Node& n) const { Parent::status(n, true); } 817 818 /// \brief Enables the given arc 819 /// 820 /// This function enables the given arc in the subdigraph. 821 /// It is the same as \ref status() "status(a, true)". 822 void enable(const Arc& a) const { Parent::status(a, true); } 776 823 777 824 }; 778 825 779 /// \brief Just gives back a subdigraph 780 /// 781 /// Just gives back a subdigraph 782 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 783 SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> 784 subDigraph(const Digraph& digraph, NodeFilterMap& nfm, ArcFilterMap& afm) { 785 return SubDigraph<const Digraph, NodeFilterMap, ArcFilterMap> 786 (digraph, nfm, afm); 826 /// \brief Returns a read-only SubDigraph adaptor 827 /// 828 /// This function just returns a read-only \ref SubDigraph adaptor. 829 /// \ingroup graph_adaptors 830 /// \relates SubDigraph 831 template<typename DGR, typename NF, typename AF> 832 SubDigraph<const DGR, NF, AF> 833 subDigraph(const DGR& digraph, 834 NF& node_filter, AF& arc_filter) { 835 return SubDigraph<const DGR, NF, AF> 836 (digraph, node_filter, arc_filter); 787 837 } 788 838 789 template<typename D igraph, typename NodeFilterMap, typename ArcFilterMap>790 SubDigraph<const D igraph, const NodeFilterMap, ArcFilterMap>791 subDigraph(const D igraph& digraph,792 const N odeFilterMap& nfm, ArcFilterMap& afm) {793 return SubDigraph<const D igraph, const NodeFilterMap, ArcFilterMap>794 (digraph, n fm, afm);839 template<typename DGR, typename NF, typename AF> 840 SubDigraph<const DGR, const NF, AF> 841 subDigraph(const DGR& digraph, 842 const NF& node_filter, AF& arc_filter) { 843 return SubDigraph<const DGR, const NF, AF> 844 (digraph, node_filter, arc_filter); 795 845 } 796 846 797 template<typename D igraph, typename NodeFilterMap, typename ArcFilterMap>798 SubDigraph<const D igraph, NodeFilterMap, const ArcFilterMap>799 subDigraph(const D igraph& digraph,800 N odeFilterMap& nfm, const ArcFilterMap& afm) {801 return SubDigraph<const D igraph, NodeFilterMap, const ArcFilterMap>802 (digraph, n fm, afm);847 template<typename DGR, typename NF, typename AF> 848 SubDigraph<const DGR, NF, const AF> 849 subDigraph(const DGR& digraph, 850 NF& node_filter, const AF& arc_filter) { 851 return SubDigraph<const DGR, NF, const AF> 852 (digraph, node_filter, arc_filter); 803 853 } 804 854 805 template<typename D igraph, typename NodeFilterMap, typename ArcFilterMap>806 SubDigraph<const D igraph, const NodeFilterMap, const ArcFilterMap>807 subDigraph(const D igraph& digraph,808 const N odeFilterMap& nfm, const ArcFilterMap& afm) {809 return SubDigraph<const D igraph, const NodeFilterMap,810 const ArcFilterMap>(digraph, nfm, afm);855 template<typename DGR, typename NF, typename AF> 856 SubDigraph<const DGR, const NF, const AF> 857 subDigraph(const DGR& digraph, 858 const NF& node_filter, const AF& arc_filter) { 859 return SubDigraph<const DGR, const NF, const AF> 860 (digraph, node_filter, arc_filter); 811 861 } 812 862 813 863 814 template <typename _Graph, typename NodeFilterMap, 815 typename EdgeFilterMap, bool _checked = true> 816 class SubGraphBase : public GraphAdaptorBase<_Graph> { 817 public: 818 typedef _Graph Graph; 864 template <typename GR, typename NF, typename EF, bool ch = true> 865 class SubGraphBase : public GraphAdaptorBase<GR> { 866 public: 867 typedef GR Graph; 868 typedef NF NodeFilterMap; 869 typedef EF EdgeFilterMap; 870 819 871 typedef SubGraphBase Adaptor; 820 typedef GraphAdaptorBase< _Graph> Parent;872 typedef GraphAdaptorBase<GR> Parent; 821 873 protected: 822 874 823 N odeFilterMap* _node_filter_map;824 E dgeFilterMap* _edge_filter_map;875 NF* _node_filter; 876 EF* _edge_filter; 825 877 826 878 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; 879 : Parent(), _node_filter(0), _edge_filter(0) { } 880 881 void initialize(GR& graph, NF& node_filter, EF& edge_filter) { 882 Parent::initialize(graph); 883 _node_filter = &node_filter; 884 _edge_filter = &edge_filter; 834 885 } 835 886 … … 842 893 void first(Node& i) const { 843 894 Parent::first(i); 844 while (i!=INVALID && !(*_node_filter _map)[i]) Parent::next(i);895 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 845 896 } 846 897 847 898 void first(Arc& i) const { 848 899 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)]))900 while (i!=INVALID && (!(*_edge_filter)[i] 901 || !(*_node_filter)[Parent::source(i)] 902 || !(*_node_filter)[Parent::target(i)])) 852 903 Parent::next(i); 853 904 } … … 855 906 void first(Edge& i) const { 856 907 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)]))908 while (i!=INVALID && (!(*_edge_filter)[i] 909 || !(*_node_filter)[Parent::u(i)] 910 || !(*_node_filter)[Parent::v(i)])) 860 911 Parent::next(i); 861 912 } … … 863 914 void firstIn(Arc& i, const Node& n) const { 864 915 Parent::firstIn(i, n); 865 while (i!=INVALID && (!(*_edge_filter _map)[i]866 || !(*_node_filter _map)[Parent::source(i)]))916 while (i!=INVALID && (!(*_edge_filter)[i] 917 || !(*_node_filter)[Parent::source(i)])) 867 918 Parent::nextIn(i); 868 919 } … … 870 921 void firstOut(Arc& i, const Node& n) const { 871 922 Parent::firstOut(i, n); 872 while (i!=INVALID && (!(*_edge_filter _map)[i]873 || !(*_node_filter _map)[Parent::target(i)]))923 while (i!=INVALID && (!(*_edge_filter)[i] 924 || !(*_node_filter)[Parent::target(i)])) 874 925 Parent::nextOut(i); 875 926 } … … 877 928 void firstInc(Edge& i, bool& d, const Node& n) const { 878 929 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)]))930 while (i!=INVALID && (!(*_edge_filter)[i] 931 || !(*_node_filter)[Parent::u(i)] 932 || !(*_node_filter)[Parent::v(i)])) 882 933 Parent::nextInc(i, d); 883 934 } … … 885 936 void next(Node& i) const { 886 937 Parent::next(i); 887 while (i!=INVALID && !(*_node_filter _map)[i]) Parent::next(i);938 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 888 939 } 889 940 890 941 void next(Arc& i) const { 891 942 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)]))943 while (i!=INVALID && (!(*_edge_filter)[i] 944 || !(*_node_filter)[Parent::source(i)] 945 || !(*_node_filter)[Parent::target(i)])) 895 946 Parent::next(i); 896 947 } … … 898 949 void next(Edge& i) const { 899 950 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)]))951 while (i!=INVALID && (!(*_edge_filter)[i] 952 || !(*_node_filter)[Parent::u(i)] 953 || !(*_node_filter)[Parent::v(i)])) 903 954 Parent::next(i); 904 955 } … … 906 957 void nextIn(Arc& i) const { 907 958 Parent::nextIn(i); 908 while (i!=INVALID && (!(*_edge_filter _map)[i]909 || !(*_node_filter _map)[Parent::source(i)]))959 while (i!=INVALID && (!(*_edge_filter)[i] 960 || !(*_node_filter)[Parent::source(i)])) 910 961 Parent::nextIn(i); 911 962 } … … 913 964 void nextOut(Arc& i) const { 914 965 Parent::nextOut(i); 915 while (i!=INVALID && (!(*_edge_filter _map)[i]916 || !(*_node_filter _map)[Parent::target(i)]))966 while (i!=INVALID && (!(*_edge_filter)[i] 967 || !(*_node_filter)[Parent::target(i)])) 917 968 Parent::nextOut(i); 918 969 } … … 920 971 void nextInc(Edge& i, bool& d) const { 921 972 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)]))973 while (i!=INVALID && (!(*_edge_filter)[i] 974 || !(*_node_filter)[Parent::u(i)] 975 || !(*_node_filter)[Parent::v(i)])) 925 976 Parent::nextInc(i, d); 926 977 } 927 978 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]; } 979 void status(const Node& n, bool v) const { _node_filter->set(n, v); } 980 void status(const Edge& e, bool v) const { _edge_filter->set(e, v); } 981 982 bool status(const Node& n) const { return (*_node_filter)[n]; } 983 bool status(const Edge& e) const { return (*_edge_filter)[e]; } 936 984 937 985 typedef False NodeNumTag; 986 typedef False ArcNumTag; 938 987 typedef False EdgeNumTag; 939 988 989 typedef FindArcTagIndicator<Graph> FindArcTag; 990 Arc findArc(const Node& u, const Node& v, 991 const Arc& prev = INVALID) const { 992 if (!(*_node_filter)[u] || !(*_node_filter)[v]) { 993 return INVALID; 994 } 995 Arc arc = Parent::findArc(u, v, prev); 996 while (arc != INVALID && !(*_edge_filter)[arc]) { 997 arc = Parent::findArc(u, v, arc); 998 } 999 return arc; 1000 } 1001 940 1002 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]) {1003 Edge findEdge(const Node& u, const Node& v, 1004 const Edge& prev = INVALID) const { 1005 if (!(*_node_filter)[u] || !(*_node_filter)[v]) { 944 1006 return INVALID; 945 1007 } 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 1008 Edge edge = Parent::findEdge(u, v, prev); 958 while (edge != INVALID && !(*_edge_filter _map)[edge]) {1009 while (edge != INVALID && !(*_edge_filter)[edge]) { 959 1010 edge = Parent::findEdge(u, v, edge); 960 1011 } … … 962 1013 } 963 1014 964 template <typename _Value> 965 class NodeMap : public SubMapExtender<Adaptor, 966 typename Parent::template NodeMap<_Value> > { 1015 template <typename V> 1016 class NodeMap 1017 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1018 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> { 967 1019 public: 968 typedef _ValueValue;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) {}1020 typedef V Value; 1021 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1022 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent; 1023 1024 NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor) 1025 : Parent(adaptor) {} 1026 NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value) 1027 : Parent(adaptor, value) {} 976 1028 977 1029 private: … … 982 1034 template <typename CMap> 983 1035 NodeMap& operator=(const CMap& cmap) { 984 MapParent::operator=(cmap);1036 Parent::operator=(cmap); 985 1037 return *this; 986 1038 } 987 1039 }; 988 1040 989 template <typename _Value> 990 class ArcMap : public SubMapExtender<Adaptor, 991 typename Parent::template ArcMap<_Value> > { 1041 template <typename V> 1042 class ArcMap 1043 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1044 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> { 992 1045 public: 993 typedef _ValueValue;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) {}1046 typedef V Value; 1047 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1048 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent; 1049 1050 ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor) 1051 : Parent(adaptor) {} 1052 ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value) 1053 : Parent(adaptor, value) {} 1001 1054 1002 1055 private: … … 1007 1060 template <typename CMap> 1008 1061 ArcMap& operator=(const CMap& cmap) { 1009 MapParent::operator=(cmap);1062 Parent::operator=(cmap); 1010 1063 return *this; 1011 1064 } 1012 1065 }; 1013 1066 1014 template <typename _Value> 1015 class EdgeMap : public SubMapExtender<Adaptor, 1016 typename Parent::template EdgeMap<_Value> > { 1067 template <typename V> 1068 class EdgeMap 1069 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1070 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> { 1017 1071 public: 1018 typedef _ValueValue;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) {}1072 typedef V Value; 1073 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1074 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent; 1075 1076 EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor) 1077 : Parent(adaptor) {} 1078 1079 EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value) 1080 : Parent(adaptor, value) {} 1027 1081 1028 1082 private: … … 1033 1087 template <typename CMap> 1034 1088 EdgeMap& operator=(const CMap& cmap) { 1035 MapParent::operator=(cmap);1089 Parent::operator=(cmap); 1036 1090 return *this; 1037 1091 } … … 1040 1094 }; 1041 1095 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; 1096 template <typename GR, typename NF, typename EF> 1097 class SubGraphBase<GR, NF, EF, false> 1098 : public GraphAdaptorBase<GR> { 1099 public: 1100 typedef GR Graph; 1101 typedef NF NodeFilterMap; 1102 typedef EF EdgeFilterMap; 1103 1047 1104 typedef SubGraphBase Adaptor; 1048 typedef GraphAdaptorBase< _Graph> Parent;1105 typedef GraphAdaptorBase<GR> Parent; 1049 1106 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; 1107 NF* _node_filter; 1108 EF* _edge_filter; 1109 SubGraphBase() 1110 : Parent(), _node_filter(0), _edge_filter(0) { } 1111 1112 void initialize(GR& graph, NF& node_filter, EF& edge_filter) { 1113 Parent::initialize(graph); 1114 _node_filter = &node_filter; 1115 _edge_filter = &edge_filter; 1060 1116 } 1061 1117 … … 1068 1124 void first(Node& i) const { 1069 1125 Parent::first(i); 1070 while (i!=INVALID && !(*_node_filter _map)[i]) Parent::next(i);1126 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 1071 1127 } 1072 1128 1073 1129 void first(Arc& i) const { 1074 1130 Parent::first(i); 1075 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::next(i);1131 while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); 1076 1132 } 1077 1133 1078 1134 void first(Edge& i) const { 1079 1135 Parent::first(i); 1080 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::next(i);1136 while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); 1081 1137 } 1082 1138 1083 1139 void firstIn(Arc& i, const Node& n) const { 1084 1140 Parent::firstIn(i, n); 1085 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextIn(i);1141 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i); 1086 1142 } 1087 1143 1088 1144 void firstOut(Arc& i, const Node& n) const { 1089 1145 Parent::firstOut(i, n); 1090 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextOut(i);1146 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i); 1091 1147 } 1092 1148 1093 1149 void firstInc(Edge& i, bool& d, const Node& n) const { 1094 1150 Parent::firstInc(i, d, n); 1095 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextInc(i, d);1151 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d); 1096 1152 } 1097 1153 1098 1154 void next(Node& i) const { 1099 1155 Parent::next(i); 1100 while (i!=INVALID && !(*_node_filter _map)[i]) Parent::next(i);1156 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 1101 1157 } 1102 1158 void next(Arc& i) const { 1103 1159 Parent::next(i); 1104 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::next(i);1160 while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); 1105 1161 } 1106 1162 void next(Edge& i) const { 1107 1163 Parent::next(i); 1108 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::next(i);1164 while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); 1109 1165 } 1110 1166 void nextIn(Arc& i) const { 1111 1167 Parent::nextIn(i); 1112 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextIn(i);1168 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i); 1113 1169 } 1114 1170 1115 1171 void nextOut(Arc& i) const { 1116 1172 Parent::nextOut(i); 1117 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextOut(i);1173 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i); 1118 1174 } 1119 1175 void nextInc(Edge& i, bool& d) const { 1120 1176 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]; } 1177 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d); 1178 } 1179 1180 void status(const Node& n, bool v) const { _node_filter->set(n, v); } 1181 void status(const Edge& e, bool v) const { _edge_filter->set(e, v); } 1182 1183 bool status(const Node& n) const { return (*_node_filter)[n]; } 1184 bool status(const Edge& e) const { return (*_edge_filter)[e]; } 1132 1185 1133 1186 typedef False NodeNumTag; 1187 typedef False ArcNumTag; 1134 1188 typedef False EdgeNumTag; 1135 1189 1190 typedef FindArcTagIndicator<Graph> FindArcTag; 1191 Arc findArc(const Node& u, const Node& v, 1192 const Arc& prev = INVALID) const { 1193 Arc arc = Parent::findArc(u, v, prev); 1194 while (arc != INVALID && !(*_edge_filter)[arc]) { 1195 arc = Parent::findArc(u, v, arc); 1196 } 1197 return arc; 1198 } 1199 1136 1200 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 1201 Edge findEdge(const Node& u, const Node& v, 1146 const Edge& prev = INVALID) {1202 const Edge& prev = INVALID) const { 1147 1203 Edge edge = Parent::findEdge(u, v, prev); 1148 while (edge != INVALID && !(*_edge_filter _map)[edge]) {1204 while (edge != INVALID && !(*_edge_filter)[edge]) { 1149 1205 edge = Parent::findEdge(u, v, edge); 1150 1206 } … … 1152 1208 } 1153 1209 1154 template <typename _Value> 1155 class NodeMap : public SubMapExtender<Adaptor, 1156 typename Parent::template NodeMap<_Value> > { 1210 template <typename V> 1211 class NodeMap 1212 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1213 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> { 1157 1214 public: 1158 typedef _ValueValue;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) {}1215 typedef V Value; 1216 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1217 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent; 1218 1219 NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor) 1220 : Parent(adaptor) {} 1221 NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value) 1222 : Parent(adaptor, value) {} 1166 1223 1167 1224 private: … … 1172 1229 template <typename CMap> 1173 1230 NodeMap& operator=(const CMap& cmap) { 1174 MapParent::operator=(cmap);1231 Parent::operator=(cmap); 1175 1232 return *this; 1176 1233 } 1177 1234 }; 1178 1235 1179 template <typename _Value> 1180 class ArcMap : public SubMapExtender<Adaptor, 1181 typename Parent::template ArcMap<_Value> > { 1236 template <typename V> 1237 class ArcMap 1238 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1239 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> { 1182 1240 public: 1183 typedef _ValueValue;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) {}1241 typedef V Value; 1242 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1243 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent; 1244 1245 ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor) 1246 : Parent(adaptor) {} 1247 ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value) 1248 : Parent(adaptor, value) {} 1191 1249 1192 1250 private: … … 1197 1255 template <typename CMap> 1198 1256 ArcMap& operator=(const CMap& cmap) { 1199 MapParent::operator=(cmap);1257 Parent::operator=(cmap); 1200 1258 return *this; 1201 1259 } 1202 1260 }; 1203 1261 1204 template <typename _Value> 1205 class EdgeMap : public SubMapExtender<Adaptor, 1206 typename Parent::template EdgeMap<_Value> > { 1262 template <typename V> 1263 class EdgeMap 1264 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1265 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> { 1207 1266 public: 1208 typedef _ValueValue;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) {}1267 typedef V Value; 1268 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1269 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent; 1270 1271 EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor) 1272 : Parent(adaptor) {} 1273 1274 EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value) 1275 : Parent(adaptor, value) {} 1217 1276 1218 1277 private: … … 1223 1282 template <typename CMap> 1224 1283 EdgeMap& operator=(const CMap& cmap) { 1225 MapParent::operator=(cmap);1284 Parent::operator=(cmap); 1226 1285 return *this; 1227 1286 } … … 1232 1291 /// \ingroup graph_adaptors 1233 1292 /// 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. 1293 /// \brief Adaptor class for hiding nodes and edges in an undirected 1294 /// graph. 1295 /// 1296 /// SubGraph can be used for hiding nodes and edges in a graph. 1297 /// A \c bool node map and a \c bool edge map must be specified, which 1298 /// define the filters for nodes and edges. 1299 /// Only the nodes and edges with \c true filter value are 1300 /// shown in the subgraph. The edges that are incident to hidden 1301 /// nodes are also filtered out. 1302 /// This adaptor conforms to the \ref concepts::Graph "Graph" concept. 1303 /// 1304 /// The adapted graph can also be modified through this adaptor 1305 /// by adding or removing nodes or edges, unless the \c GR template 1306 /// parameter is set to be \c const. 1307 /// 1308 /// \tparam GR The type of the adapted graph. 1309 /// It must conform to the \ref concepts::Graph "Graph" concept. 1310 /// It can also be specified to be \c const. 1311 /// \tparam NF The type of the node filter map. 1312 /// It must be a \c bool (or convertible) node map of the 1313 /// adapted graph. The default type is 1314 /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>". 1315 /// \tparam EF The type of the edge filter map. 1316 /// It must be a \c bool (or convertible) edge map of the 1317 /// adapted graph. The default type is 1318 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>". 1319 /// 1320 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the 1321 /// adapted graph are convertible to each other. 1253 1322 /// 1254 1323 /// \see FilterNodes 1255 1324 /// \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; 1325 #ifdef DOXYGEN 1326 template<typename GR, typename NF, typename EF> 1327 class SubGraph { 1328 #else 1329 template<typename GR, 1330 typename NF = typename GR::template NodeMap<bool>, 1331 typename EF = typename GR::template EdgeMap<bool> > 1332 class SubGraph : 1333 public GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > { 1334 #endif 1335 public: 1336 /// The type of the adapted graph. 1337 typedef GR Graph; 1338 /// The type of the node filter map. 1339 typedef NF NodeFilterMap; 1340 /// The type of the edge filter map. 1341 typedef EF EdgeFilterMap; 1342 1343 typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > 1344 Parent; 1265 1345 1266 1346 typedef typename Parent::Node Node; … … 1273 1353 /// \brief Constructor 1274 1354 /// 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); } 1355 /// Creates a subgraph for the given graph with the given node 1356 /// and edge filter maps. 1357 SubGraph(GR& graph, NF& node_filter, EF& edge_filter) { 1358 initialize(graph, node_filter, edge_filter); 1359 } 1360 1361 /// \brief Sets the status of the given node 1362 /// 1363 /// This function sets the status of the given node. 1364 /// It is done by simply setting the assigned value of \c n 1365 /// to \c v in the node filter map. 1366 void status(const Node& n, bool v) const { Parent::status(n, v); } 1367 1368 /// \brief Sets the status of the given edge 1369 /// 1370 /// This function sets the status of the given edge. 1371 /// It is done by simply setting the assigned value of \c e 1372 /// to \c v in the edge filter map. 1373 void status(const Edge& e, bool v) const { Parent::status(e, v); } 1374 1375 /// \brief Returns the status of the given node 1376 /// 1377 /// This function returns the status of the given node. 1378 /// It is \c true if the given node is enabled (i.e. not hidden). 1379 bool status(const Node& n) const { return Parent::status(n); } 1380 1381 /// \brief Returns the status of the given edge 1382 /// 1383 /// This function returns the status of the given edge. 1384 /// It is \c true if the given edge is enabled (i.e. not hidden). 1385 bool status(const Edge& e) const { return Parent::status(e); } 1386 1387 /// \brief Disables the given node 1388 /// 1389 /// This function disables the given node in the subdigraph, 1390 /// so the iteration jumps over it. 1391 /// It is the same as \ref status() "status(n, false)". 1392 void disable(const Node& n) const { Parent::status(n, false); } 1393 1394 /// \brief Disables the given edge 1395 /// 1396 /// This function disables the given edge in the subgraph, 1397 /// so the iteration jumps over it. 1398 /// It is the same as \ref status() "status(e, false)". 1399 void disable(const Edge& e) const { Parent::status(e, false); } 1400 1401 /// \brief Enables the given node 1402 /// 1403 /// This function enables the given node in the subdigraph. 1404 /// It is the same as \ref status() "status(n, true)". 1405 void enable(const Node& n) const { Parent::status(n, true); } 1406 1407 /// \brief Enables the given edge 1408 /// 1409 /// This function enables the given edge in the subgraph. 1410 /// It is the same as \ref status() "status(e, true)". 1411 void enable(const Edge& e) const { Parent::status(e, true); } 1412 1323 1413 }; 1324 1414 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); 1415 /// \brief Returns a read-only SubGraph adaptor 1416 /// 1417 /// This function just returns a read-only \ref SubGraph adaptor. 1418 /// \ingroup graph_adaptors 1419 /// \relates SubGraph 1420 template<typename GR, typename NF, typename EF> 1421 SubGraph<const GR, NF, EF> 1422 subGraph(const GR& graph, NF& node_filter, EF& edge_filter) { 1423 return SubGraph<const GR, NF, EF> 1424 (graph, node_filter, edge_filter); 1332 1425 } 1333 1426 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); 1427 template<typename GR, typename NF, typename EF> 1428 SubGraph<const GR, const NF, EF> 1429 subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) { 1430 return SubGraph<const GR, const NF, EF> 1431 (graph, node_filter, edge_filter); 1340 1432 } 1341 1433 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); 1434 template<typename GR, typename NF, typename EF> 1435 SubGraph<const GR, NF, const EF> 1436 subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) { 1437 return SubGraph<const GR, NF, const EF> 1438 (graph, node_filter, edge_filter); 1348 1439 } 1349 1440 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); 1441 template<typename GR, typename NF, typename EF> 1442 SubGraph<const GR, const NF, const EF> 1443 subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) { 1444 return SubGraph<const GR, const NF, const EF> 1445 (graph, node_filter, edge_filter); 1356 1446 } 1357 1447 1448 1358 1449 /// \ingroup graph_adaptors 1359 1450 /// 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. 1451 /// \brief Adaptor class for hiding nodes in a digraph or a graph. 1452 /// 1453 /// FilterNodes adaptor can be used for hiding nodes in a digraph or a 1454 /// graph. A \c bool node map must be specified, which defines the filter 1455 /// for the nodes. Only the nodes with \c true filter value and the 1456 /// arcs/edges incident to nodes both with \c true filter value are shown 1457 /// in the subgraph. This adaptor conforms to the \ref concepts::Digraph 1458 /// "Digraph" concept or the \ref concepts::Graph "Graph" concept 1459 /// depending on the \c GR template parameter. 1460 /// 1461 /// The adapted (di)graph can also be modified through this adaptor 1462 /// by adding or removing nodes or arcs/edges, unless the \c GR template 1463 /// parameter is set to be \c const. 1464 /// 1465 /// \tparam GR The type of the adapted digraph or graph. 1466 /// It must conform to the \ref concepts::Digraph "Digraph" concept 1467 /// or the \ref concepts::Graph "Graph" concept. 1468 /// It can also be specified to be \c const. 1469 /// \tparam NF The type of the node filter map. 1470 /// It must be a \c bool (or convertible) node map of the 1471 /// adapted (di)graph. The default type is 1472 /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>". 1473 /// 1474 /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the 1475 /// adapted (di)graph are convertible to each other. 1380 1476 #ifdef DOXYGEN 1381 template<typename _Digraph, 1382 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 1383 bool _checked = true> 1477 template<typename GR, typename NF> 1478 class FilterNodes { 1384 1479 #else 1385 template<typename _Digraph, 1386 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 1387 bool _checked = true, 1480 template<typename GR, 1481 typename NF = typename GR::template NodeMap<bool>, 1388 1482 typename Enable = void> 1483 class FilterNodes : 1484 public DigraphAdaptorExtender< 1485 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 1486 true> > { 1389 1487 #endif 1390 class FilterNodes 1391 : public SubDigraph<_Digraph, _NodeFilterMap, 1392 ConstMap<typename _Digraph::Arc, bool>, _checked> { 1393 public: 1394 1395 typedef _Digraph Digraph; 1396 typedef _NodeFilterMap NodeFilterMap; 1397 1398 typedef SubDigraph<Digraph, NodeFilterMap, 1399 ConstMap<typename Digraph::Arc, bool>, _checked> 1400 Parent; 1488 public: 1489 1490 typedef GR Digraph; 1491 typedef NF NodeFilterMap; 1492 1493 typedef DigraphAdaptorExtender< 1494 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 1495 true> > Parent; 1401 1496 1402 1497 typedef typename Parent::Node Node; 1403 1498 1404 1499 protected: 1405 ConstMap<typename Digraph::Arc, bool> const_true_map; 1406 1407 FilterNodes() : const_true_map(true) { 1408 Parent::setArcFilterMap(const_true_map); 1409 } 1500 ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map; 1501 1502 FilterNodes() : const_true_map() {} 1410 1503 1411 1504 public: … … 1413 1506 /// \brief Constructor 1414 1507 /// 1415 /// Creates a n adaptor for the given digraph or graph with1508 /// Creates a subgraph for the given digraph or graph with the 1416 1509 /// given node filter map. 1417 FilterNodes(Digraph& _digraph, NodeFilterMap& node_filter) : 1418 Parent(), const_true_map(true) { 1419 Parent::setDigraph(_digraph); 1420 Parent::setNodeFilterMap(node_filter); 1421 Parent::setArcFilterMap(const_true_map); 1422 } 1423 1424 /// \brief Hides the node of the graph 1425 /// 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. 1429 void hide(const Node& n) const { Parent::hide(n); } 1430 1431 /// \brief Unhides the node of the graph 1432 /// 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 1435 /// again 1436 void unHide(const Node& n) const { Parent::unHide(n); } 1437 1438 /// \brief Returns true if \c n is hidden. 1439 /// 1440 /// Returns true if \c n is hidden. 1441 /// 1442 bool hidden(const Node& n) const { return Parent::hidden(n); } 1510 FilterNodes(GR& graph, NF& node_filter) 1511 : Parent(), const_true_map() 1512 { 1513 Parent::initialize(graph, node_filter, const_true_map); 1514 } 1515 1516 /// \brief Sets the status of the given node 1517 /// 1518 /// This function sets the status of the given node. 1519 /// It is done by simply setting the assigned value of \c n 1520 /// to \c v in the node filter map. 1521 void status(const Node& n, bool v) const { Parent::status(n, v); } 1522 1523 /// \brief Returns the status of the given node 1524 /// 1525 /// This function returns the status of the given node. 1526 /// It is \c true if the given node is enabled (i.e. not hidden). 1527 bool status(const Node& n) const { return Parent::status(n); } 1528 1529 /// \brief Disables the given node 1530 /// 1531 /// This function disables the given node, so the iteration 1532 /// jumps over it. 1533 /// It is the same as \ref status() "status(n, false)". 1534 void disable(const Node& n) const { Parent::status(n, false); } 1535 1536 /// \brief Enables the given node 1537 /// 1538 /// This function enables the given node. 1539 /// It is the same as \ref status() "status(n, true)". 1540 void enable(const Node& n) const { Parent::status(n, true); } 1443 1541 1444 1542 }; 1445 1543 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; 1544 template<typename GR, typename NF> 1545 class FilterNodes<GR, NF, 1546 typename enable_if<UndirectedTagIndicator<GR> >::type> : 1547 public GraphAdaptorExtender< 1548 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 1549 true> > { 1550 1551 public: 1552 typedef GR Graph; 1553 typedef NF NodeFilterMap; 1554 typedef GraphAdaptorExtender< 1555 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 1556 true> > Parent; 1456 1557 1457 1558 typedef typename Parent::Node Node; 1458 1559 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); } 1560 ConstMap<typename GR::Edge, Const<bool, true> > const_true_map; 1561 1562 FilterNodes() : const_true_map() {} 1563 1564 public: 1565 1566 FilterNodes(GR& graph, NodeFilterMap& node_filter) : 1567 Parent(), const_true_map() { 1568 Parent::initialize(graph, node_filter, const_true_map); 1569 } 1570 1571 void status(const Node& n, bool v) const { Parent::status(n, v); } 1572 bool status(const Node& n) const { return Parent::status(n); } 1573 void disable(const Node& n) const { Parent::status(n, false); } 1574 void enable(const Node& n) const { Parent::status(n, true); } 1477 1575 1478 1576 }; 1479 1577 1480 1578 1481 /// \brief Just gives back a FilterNodes adaptor 1482 /// 1483 /// Just gives back a FilterNodes adaptor 1484 template<typename Digraph, typename NodeFilterMap> 1485 FilterNodes<const Digraph, NodeFilterMap> 1486 filterNodes(const Digraph& digraph, NodeFilterMap& nfm) { 1487 return FilterNodes<const Digraph, NodeFilterMap>(digraph, nfm); 1579 /// \brief Returns a read-only FilterNodes adaptor 1580 /// 1581 /// This function just returns a read-only \ref FilterNodes adaptor. 1582 /// \ingroup graph_adaptors 1583 /// \relates FilterNodes 1584 template<typename GR, typename NF> 1585 FilterNodes<const GR, NF> 1586 filterNodes(const GR& graph, NF& node_filter) { 1587 return FilterNodes<const GR, NF>(graph, node_filter); 1488 1588 } 1489 1589 1490 template<typename Digraph, typename NodeFilterMap>1491 FilterNodes<const Digraph, const NodeFilterMap>1492 filterNodes(const Digraph& digraph, const NodeFilterMap& nfm) {1493 return FilterNodes<const Digraph, const NodeFilterMap>(digraph, nfm);1590 template<typename GR, typename NF> 1591 FilterNodes<const GR, const NF> 1592 filterNodes(const GR& graph, const NF& node_filter) { 1593 return FilterNodes<const GR, const NF>(graph, node_filter); 1494 1594 } 1495 1595 1496 1596 /// \ingroup graph_adaptors 1497 1597 /// 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. 1509 template<typename _Digraph, typename _ArcFilterMap> 1598 /// \brief Adaptor class for hiding arcs in a digraph. 1599 /// 1600 /// FilterArcs adaptor can be used for hiding arcs in a digraph. 1601 /// A \c bool arc map must be specified, which defines the filter for 1602 /// the arcs. Only the arcs with \c true filter value are shown in the 1603 /// subdigraph. This adaptor conforms to the \ref concepts::Digraph 1604 /// "Digraph" concept. 1605 /// 1606 /// The adapted digraph can also be modified through this adaptor 1607 /// by adding or removing nodes or arcs, unless the \c GR template 1608 /// parameter is set to be \c const. 1609 /// 1610 /// \tparam DGR The type of the adapted digraph. 1611 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 1612 /// It can also be specified to be \c const. 1613 /// \tparam AF The type of the arc filter map. 1614 /// It must be a \c bool (or convertible) arc map of the 1615 /// adapted digraph. The default type is 1616 /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>". 1617 /// 1618 /// \note The \c Node and \c Arc types of this adaptor and the adapted 1619 /// digraph are convertible to each other. 1620 #ifdef DOXYGEN 1621 template<typename DGR, 1622 typename AF> 1623 class FilterArcs { 1624 #else 1625 template<typename DGR, 1626 typename AF = typename DGR::template ArcMap<bool> > 1510 1627 class FilterArcs : 1511 public SubDigraph<_Digraph, ConstMap<typename _Digraph::Node, bool>, 1512 _ArcFilterMap, false> { 1513 public: 1514 typedef _Digraph Digraph; 1515 typedef _ArcFilterMap ArcFilterMap; 1516 1517 typedef SubDigraph<Digraph, ConstMap<typename Digraph::Node, bool>, 1518 ArcFilterMap, false> Parent; 1628 public DigraphAdaptorExtender< 1629 SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 1630 AF, false> > { 1631 #endif 1632 public: 1633 /// The type of the adapted digraph. 1634 typedef DGR Digraph; 1635 /// The type of the arc filter map. 1636 typedef AF ArcFilterMap; 1637 1638 typedef DigraphAdaptorExtender< 1639 SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 1640 AF, false> > Parent; 1519 1641 1520 1642 typedef typename Parent::Arc Arc; 1521 1643 1522 1644 protected: 1523 ConstMap<typename Digraph::Node, bool> const_true_map; 1524 1525 FilterArcs() : const_true_map(true) { 1526 Parent::setNodeFilterMap(const_true_map); 1527 } 1645 ConstMap<typename DGR::Node, Const<bool, true> > const_true_map; 1646 1647 FilterArcs() : const_true_map() {} 1528 1648 1529 1649 public: … … 1531 1651 /// \brief Constructor 1532 1652 /// 1533 /// Creates a FilterArcs adaptor for the given graph with 1534 /// given arc map filter. 1535 FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter) 1536 : Parent(), const_true_map(true) { 1537 Parent::setDigraph(digraph); 1538 Parent::setNodeFilterMap(const_true_map); 1539 Parent::setArcFilterMap(arc_filter); 1540 } 1541 1542 /// \brief Hides the arc of the graph 1543 /// 1544 /// This function hides \c a in the graph, i.e. the iteration 1545 /// jumps over it. This is done by simply setting the value of \c a 1546 /// to be false in the corresponding arc map. 1547 void hide(const Arc& a) const { Parent::hide(a); } 1548 1549 /// \brief Unhides the arc of the graph 1550 /// 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 1553 /// again 1554 void unHide(const Arc& a) const { Parent::unHide(a); } 1555 1556 /// \brief Returns true if \c a is hidden. 1557 /// 1558 /// Returns true if \c a is hidden. 1559 /// 1560 bool hidden(const Arc& a) const { return Parent::hidden(a); } 1653 /// Creates a subdigraph for the given digraph with the given arc 1654 /// filter map. 1655 FilterArcs(DGR& digraph, ArcFilterMap& arc_filter) 1656 : Parent(), const_true_map() { 1657 Parent::initialize(digraph, const_true_map, arc_filter); 1658 } 1659 1660 /// \brief Sets the status of the given arc 1661 /// 1662 /// This function sets the status of the given arc. 1663 /// It is done by simply setting the assigned value of \c a 1664 /// to \c v in the arc filter map. 1665 void status(const Arc& a, bool v) const { Parent::status(a, v); } 1666 1667 /// \brief Returns the status of the given arc 1668 /// 1669 /// This function returns the status of the given arc. 1670 /// It is \c true if the given arc is enabled (i.e. not hidden). 1671 bool status(const Arc& a) const { return Parent::status(a); } 1672 1673 /// \brief Disables the given arc 1674 /// 1675 /// This function disables the given arc in the subdigraph, 1676 /// so the iteration jumps over it. 1677 /// It is the same as \ref status() "status(a, false)". 1678 void disable(const Arc& a) const { Parent::status(a, false); } 1679 1680 /// \brief Enables the given arc 1681 /// 1682 /// This function enables the given arc in the subdigraph. 1683 /// It is the same as \ref status() "status(a, true)". 1684 void enable(const Arc& a) const { Parent::status(a, true); } 1561 1685 1562 1686 }; 1563 1687 1564 /// \brief Just gives back an FilterArcs adaptor 1565 /// 1566 /// Just gives back an FilterArcs adaptor 1567 template<typename Digraph, typename ArcFilterMap> 1568 FilterArcs<const Digraph, ArcFilterMap> 1569 filterArcs(const Digraph& digraph, ArcFilterMap& afm) { 1570 return FilterArcs<const Digraph, ArcFilterMap>(digraph, afm); 1688 /// \brief Returns a read-only FilterArcs adaptor 1689 /// 1690 /// This function just returns a read-only \ref FilterArcs adaptor. 1691 /// \ingroup graph_adaptors 1692 /// \relates FilterArcs 1693 template<typename DGR, typename AF> 1694 FilterArcs<const DGR, AF> 1695 filterArcs(const DGR& digraph, AF& arc_filter) { 1696 return FilterArcs<const DGR, AF>(digraph, arc_filter); 1571 1697 } 1572 1698 1573 template<typename D igraph, typename ArcFilterMap>1574 FilterArcs<const D igraph, const ArcFilterMap>1575 filterArcs(const D igraph& digraph, const ArcFilterMap& afm) {1576 return FilterArcs<const D igraph, const ArcFilterMap>(digraph, afm);1699 template<typename DGR, typename AF> 1700 FilterArcs<const DGR, const AF> 1701 filterArcs(const DGR& digraph, const AF& arc_filter) { 1702 return FilterArcs<const DGR, const AF>(digraph, arc_filter); 1577 1703 } 1578 1704 1579 1705 /// \ingroup graph_adaptors 1580 1706 /// 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> 1707 /// \brief Adaptor class for hiding edges in a graph. 1708 /// 1709 /// FilterEdges adaptor can be used for hiding edges in a graph. 1710 /// A \c bool edge map must be specified, which defines the filter for 1711 /// the edges. Only the edges with \c true filter value are shown in the 1712 /// subgraph. This adaptor conforms to the \ref concepts::Graph 1713 /// "Graph" concept. 1714 /// 1715 /// The adapted graph can also be modified through this adaptor 1716 /// by adding or removing nodes or edges, unless the \c GR template 1717 /// parameter is set to be \c const. 1718 /// 1719 /// \tparam GR The type of the adapted graph. 1720 /// It must conform to the \ref concepts::Graph "Graph" concept. 1721 /// It can also be specified to be \c const. 1722 /// \tparam EF The type of the edge filter map. 1723 /// It must be a \c bool (or convertible) edge map of the 1724 /// adapted graph. The default type is 1725 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>". 1726 /// 1727 /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the 1728 /// adapted graph are convertible to each other. 1729 #ifdef DOXYGEN 1730 template<typename GR, 1731 typename EF> 1732 class FilterEdges { 1733 #else 1734 template<typename GR, 1735 typename EF = typename GR::template EdgeMap<bool> > 1593 1736 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; 1737 public GraphAdaptorExtender< 1738 SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 1739 EF, false> > { 1740 #endif 1741 public: 1742 /// The type of the adapted graph. 1743 typedef GR Graph; 1744 /// The type of the edge filter map. 1745 typedef EF EdgeFilterMap; 1746 1747 typedef GraphAdaptorExtender< 1748 SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 1749 EF, false> > Parent; 1750 1601 1751 typedef typename Parent::Edge Edge; 1752 1602 1753 protected: 1603 ConstMap<typename G raph::Node, bool> const_true_map;1754 ConstMap<typename GR::Node, Const<bool, true> > const_true_map; 1604 1755 1605 1756 FilterEdges() : const_true_map(true) { … … 1611 1762 /// \brief Constructor 1612 1763 /// 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); } 1764 /// Creates a subgraph for the given graph with the given edge 1765 /// filter map. 1766 FilterEdges(GR& graph, EF& edge_filter) 1767 : Parent(), const_true_map() { 1768 Parent::initialize(graph, const_true_map, edge_filter); 1769 } 1770 1771 /// \brief Sets the status of the given edge 1772 /// 1773 /// This function sets the status of the given edge. 1774 /// It is done by simply setting the assigned value of \c e 1775 /// to \c v in the edge filter map. 1776 void status(const Edge& e, bool v) const { Parent::status(e, v); } 1777 1778 /// \brief Returns the status of the given edge 1779 /// 1780 /// This function returns the status of the given edge. 1781 /// It is \c true if the given edge is enabled (i.e. not hidden). 1782 bool status(const Edge& e) const { return Parent::status(e); } 1783 1784 /// \brief Disables the given edge 1785 /// 1786 /// This function disables the given edge in the subgraph, 1787 /// so the iteration jumps over it. 1788 /// It is the same as \ref status() "status(e, false)". 1789 void disable(const Edge& e) const { Parent::status(e, false); } 1790 1791 /// \brief Enables the given edge 1792 /// 1793 /// This function enables the given edge in the subgraph. 1794 /// It is the same as \ref status() "status(e, true)". 1795 void enable(const Edge& e) const { Parent::status(e, true); } 1641 1796 1642 1797 }; 1643 1798 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); 1799 /// \brief Returns a read-only FilterEdges adaptor 1800 /// 1801 /// This function just returns a read-only \ref FilterEdges adaptor. 1802 /// \ingroup graph_adaptors 1803 /// \relates FilterEdges 1804 template<typename GR, typename EF> 1805 FilterEdges<const GR, EF> 1806 filterEdges(const GR& graph, EF& edge_filter) { 1807 return FilterEdges<const GR, EF>(graph, edge_filter); 1651 1808 } 1652 1809 1653 template<typename G raph, typename EdgeFilterMap>1654 FilterEdges<const G raph, const EdgeFilterMap>1655 filterEdges(const G raph& graph, const EdgeFilterMap& efm) {1656 return FilterEdges<const G raph, const EdgeFilterMap>(graph, efm);1810 template<typename GR, typename EF> 1811 FilterEdges<const GR, const EF> 1812 filterEdges(const GR& graph, const EF& edge_filter) { 1813 return FilterEdges<const GR, const EF>(graph, edge_filter); 1657 1814 } 1658 1815 1659 template <typename _Digraph> 1816 1817 template <typename DGR> 1660 1818 class UndirectorBase { 1661 1819 public: 1662 typedef _DigraphDigraph;1820 typedef DGR Digraph; 1663 1821 typedef UndirectorBase Adaptor; 1664 1822 … … 1695 1853 } 1696 1854 }; 1697 1698 1699 1855 1700 1856 void first(Node& n) const { … … 1846 2002 1847 2003 typedef NodeNumTagIndicator<Digraph> NodeNumTag; 1848 int nodeNum() const { return 2 * _digraph->arcNum(); } 1849 typedef EdgeNumTagIndicator<Digraph> EdgeNumTag; 2004 int nodeNum() const { return _digraph->nodeNum(); } 2005 2006 typedef ArcNumTagIndicator<Digraph> ArcNumTag; 1850 2007 int arcNum() const { return 2 * _digraph->arcNum(); } 2008 2009 typedef ArcNumTag EdgeNumTag; 1851 2010 int edgeNum() const { return _digraph->arcNum(); } 1852 2011 1853 typedef Find EdgeTagIndicator<Digraph> FindEdgeTag;2012 typedef FindArcTagIndicator<Digraph> FindArcTag; 1854 2013 Arc findArc(Node s, Node t, Arc p = INVALID) const { 1855 2014 if (p == INVALID) { … … 1870 2029 } 1871 2030 2031 typedef FindArcTag FindEdgeTag; 1872 2032 Edge findEdge(Node s, Node t, Edge p = INVALID) const { 1873 2033 if (s != t) { … … 1877 2037 arc = _digraph->findArc(t, s); 1878 2038 if (arc != INVALID) return arc; 1879 } else if (_digraph->s (p) == s) {2039 } else if (_digraph->source(p) == s) { 1880 2040 Edge arc = _digraph->findArc(s, t, p); 1881 2041 if (arc != INVALID) return arc; … … 1894 2054 private: 1895 2055 1896 template <typename _Value>2056 template <typename V> 1897 2057 class ArcMapBase { 1898 2058 private: 1899 2059 1900 typedef typename D igraph::template ArcMap<_Value> MapImpl;2060 typedef typename DGR::template ArcMap<V> MapImpl; 1901 2061 1902 2062 public: … … 1904 2064 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag; 1905 2065 1906 typedef _ValueValue;2066 typedef V Value; 1907 2067 typedef Arc Key; 1908 1909 ArcMapBase(const Adaptor& adaptor) : 2068 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue; 2069 typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue; 2070 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference; 2071 typedef typename MapTraits<MapImpl>::ReturnValue Reference; 2072 2073 ArcMapBase(const UndirectorBase<DGR>& adaptor) : 1910 2074 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} 1911 2075 1912 ArcMapBase(const Adaptor& adaptor, const Value& v) 1913 : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {} 1914 1915 void set(const Arc& a, const Value& v) { 2076 ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value) 2077 : _forward(*adaptor._digraph, value), 2078 _backward(*adaptor._digraph, value) {} 2079 2080 void set(const Arc& a, const V& value) { 1916 2081 if (direction(a)) { 1917 _forward.set(a, v );2082 _forward.set(a, value); 1918 2083 } else { 1919 _backward.set(a, v );2084 _backward.set(a, value); 1920 2085 } 1921 2086 } 1922 2087 1923 typename MapTraits<MapImpl>::ConstReturnValue 1924 operator[](const Arc& a) const { 2088 ConstReturnValue operator[](const Arc& a) const { 1925 2089 if (direction(a)) { 1926 2090 return _forward[a]; … … 1930 2094 } 1931 2095 1932 typename MapTraits<MapImpl>::ReturnValue 1933 operator[](const Arc& a) { 2096 ReturnValue operator[](const Arc& a) { 1934 2097 if (direction(a)) { 1935 2098 return _forward[a]; … … 1947 2110 public: 1948 2111 1949 template <typename _Value>1950 class NodeMap : public D igraph::template NodeMap<_Value> {2112 template <typename V> 2113 class NodeMap : public DGR::template NodeMap<V> { 1951 2114 public: 1952 2115 1953 typedef _ValueValue;1954 typedef typename D igraph::template NodeMap<Value> Parent;1955 1956 explicit NodeMap(const Adaptor& adaptor)2116 typedef V Value; 2117 typedef typename DGR::template NodeMap<Value> Parent; 2118 2119 explicit NodeMap(const UndirectorBase<DGR>& adaptor) 1957 2120 : Parent(*adaptor._digraph) {} 1958 2121 1959 NodeMap(const Adaptor& adaptor, const _Value& value)2122 NodeMap(const UndirectorBase<DGR>& adaptor, const V& value) 1960 2123 : Parent(*adaptor._digraph, value) { } 1961 2124 … … 1973 2136 }; 1974 2137 1975 template <typename _Value>2138 template <typename V> 1976 2139 class ArcMap 1977 : public SubMapExtender< Adaptor, ArcMapBase<_Value> >2140 : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > 1978 2141 { 1979 2142 public: 1980 typedef _ValueValue;1981 typedef SubMapExtender<Adaptor, ArcMapBase<V alue> > Parent;1982 1983 ArcMap(const Adaptor& adaptor)2143 typedef V Value; 2144 typedef SubMapExtender<Adaptor, ArcMapBase<V> > Parent; 2145 2146 explicit ArcMap(const UndirectorBase<DGR>& adaptor) 1984 2147 : Parent(adaptor) {} 1985 2148 1986 ArcMap(const Adaptor& adaptor, const Value& value)2149 ArcMap(const UndirectorBase<DGR>& adaptor, const V& value) 1987 2150 : Parent(adaptor, value) {} 1988 2151 … … 1999 2162 }; 2000 2163 2001 template <typename _Value>2002 class EdgeMap : public Digraph::template ArcMap< _Value> {2164 template <typename V> 2165 class EdgeMap : public Digraph::template ArcMap<V> { 2003 2166 public: 2004 2167 2005 typedef _ValueValue;2006 typedef typename Digraph::template ArcMap<V alue> Parent;2007 2008 explicit EdgeMap(const Adaptor& adaptor)2168 typedef V Value; 2169 typedef typename Digraph::template ArcMap<V> Parent; 2170 2171 explicit EdgeMap(const UndirectorBase<DGR>& adaptor) 2009 2172 : Parent(*adaptor._digraph) {} 2010 2173 2011 EdgeMap(const Adaptor& adaptor, const Value& value)2174 EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value) 2012 2175 : Parent(*adaptor._digraph, value) {} 2013 2176 … … 2025 2188 }; 2026 2189 2027 typedef typename ItemSetTraits<D igraph, Node>::ItemNotifier NodeNotifier;2190 typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier; 2028 2191 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 2029 2192 2193 typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier; 2194 EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); } 2195 2030 2196 protected: 2031 2197 2032 2198 UndirectorBase() : _digraph(0) {} 2033 2199 2034 D igraph* _digraph;2035 2036 void setDigraph(Digraph& digraph) {2200 DGR* _digraph; 2201 2202 void initialize(DGR& digraph) { 2037 2203 _digraph = &digraph; 2038 2204 } … … 2042 2208 /// \ingroup graph_adaptors 2043 2209 /// 2044 /// \brief Undirect the graph 2045 /// 2046 /// This adaptor makes an undirected graph from a directed 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. 2054 template<typename _Digraph> 2055 class Undirector 2056 : public GraphAdaptorExtender<UndirectorBase<_Digraph> > { 2057 public: 2058 typedef _Digraph Digraph; 2059 typedef GraphAdaptorExtender<UndirectorBase<Digraph> > Parent; 2210 /// \brief Adaptor class for viewing a digraph as an undirected graph. 2211 /// 2212 /// Undirector adaptor can be used for viewing a digraph as an undirected 2213 /// graph. All arcs of the underlying digraph are showed in the 2214 /// adaptor as an edge (and also as a pair of arcs, of course). 2215 /// This adaptor conforms to the \ref concepts::Graph "Graph" concept. 2216 /// 2217 /// The adapted digraph can also be modified through this adaptor 2218 /// by adding or removing nodes or edges, unless the \c GR template 2219 /// parameter is set to be \c const. 2220 /// 2221 /// \tparam DGR The type of the adapted digraph. 2222 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 2223 /// It can also be specified to be \c const. 2224 /// 2225 /// \note The \c Node type of this adaptor and the adapted digraph are 2226 /// convertible to each other, moreover the \c Edge type of the adaptor 2227 /// and the \c Arc type of the adapted digraph are also convertible to 2228 /// each other. 2229 /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type 2230 /// of the adapted digraph.) 2231 template<typename DGR> 2232 #ifdef DOXYGEN 2233 class Undirector { 2234 #else 2235 class Undirector : 2236 public GraphAdaptorExtender<UndirectorBase<DGR> > { 2237 #endif 2238 public: 2239 /// The type of the adapted digraph. 2240 typedef DGR Digraph; 2241 typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent; 2060 2242 protected: 2061 2243 Undirector() { } … … 2064 2246 /// \brief Constructor 2065 2247 /// 2066 /// Creates a undirected graph from the given digraph 2067 Undirector(_Digraph& digraph) { 2068 setDigraph(digraph); 2069 } 2070 2071 /// \brief ArcMap combined from two original ArcMap 2072 /// 2073 /// This class adapts two original digraph ArcMap to 2074 /// get an arc map on the undirected graph. 2075 template <typename _ForwardMap, typename _BackwardMap> 2248 /// Creates an undirected graph from the given digraph. 2249 Undirector(DGR& digraph) { 2250 initialize(digraph); 2251 } 2252 2253 /// \brief Arc map combined from two original arc maps 2254 /// 2255 /// This map adaptor class adapts two arc maps of the underlying 2256 /// digraph to get an arc map of the undirected graph. 2257 /// Its value type is inherited from the first arc map type 2258 /// (\c %ForwardMap). 2259 template <typename ForwardMap, typename BackwardMap> 2076 2260 class CombinedArcMap { 2077 2261 public: 2078 2262 2079 typedef _ForwardMap ForwardMap; 2080 typedef _BackwardMap BackwardMap; 2263 /// The key type of the map 2264 typedef typename Parent::Arc Key; 2265 /// The value type of the map 2266 typedef typename ForwardMap::Value Value; 2081 2267 2082 2268 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag; 2083 2269 2084 typedef typename ForwardMap::ValueValue;2085 typedef typename Parent::Arc Key;2086 2087 /// \brief Constructor2088 /// 2270 typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue; 2271 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue; 2272 typedef typename MapTraits<ForwardMap>::ReturnValue Reference; 2273 typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference; 2274 2089 2275 /// Constructor 2090 2276 CombinedArcMap(ForwardMap& forward, BackwardMap& backward) 2091 2277 : _forward(&forward), _backward(&backward) {} 2092 2278 2093 2094 /// \brief Sets the value associated with a key. 2095 /// 2096 /// Sets the value associated with a key. 2279 /// Sets the value associated with the given key. 2097 2280 void set(const Key& e, const Value& a) { 2098 2281 if (Parent::direction(e)) { … … 2103 2286 } 2104 2287 2105 /// \brief Returns the value associated with a key. 2106 /// 2107 /// Returns the value associated with a key. 2108 typename MapTraits<ForwardMap>::ConstReturnValue 2109 operator[](const Key& e) const { 2288 /// Returns the value associated with the given key. 2289 ConstReturnValue operator[](const Key& e) const { 2110 2290 if (Parent::direction(e)) { 2111 2291 return (*_forward)[e]; … … 2115 2295 } 2116 2296 2117 /// \brief Returns the value associated with a key. 2118 /// 2119 /// Returns the value associated with a key. 2120 typename MapTraits<ForwardMap>::ReturnValue 2121 operator[](const Key& e) { 2297 /// Returns a reference to the value associated with the given key. 2298 ReturnValue operator[](const Key& e) { 2122 2299 if (Parent::direction(e)) { 2123 2300 return (*_forward)[e]; … … 2134 2311 }; 2135 2312 2136 /// \brief Just gives backa combined arc map2137 /// 2138 /// Just gives back a combined arc map2313 /// \brief Returns a combined arc map 2314 /// 2315 /// This function just returns a combined arc map. 2139 2316 template <typename ForwardMap, typename BackwardMap> 2140 2317 static CombinedArcMap<ForwardMap, BackwardMap> … … 2166 2343 }; 2167 2344 2168 /// \brief Just gives back an undirected view of the given digraph 2169 /// 2170 /// Just gives back an undirected view of the given digraph 2171 template<typename Digraph> 2172 Undirector<const Digraph> 2173 undirector(const Digraph& digraph) { 2174 return Undirector<const Digraph>(digraph); 2345 /// \brief Returns a read-only Undirector adaptor 2346 /// 2347 /// This function just returns a read-only \ref Undirector adaptor. 2348 /// \ingroup graph_adaptors 2349 /// \relates Undirector 2350 template<typename DGR> 2351 Undirector<const DGR> undirector(const DGR& digraph) { 2352 return Undirector<const DGR>(digraph); 2175 2353 } 2176 2354 2177 template <typename _Graph, typename _DirectionMap> 2355 2356 template <typename GR, typename DM> 2178 2357 class OrienterBase { 2179 2358 public: 2180 2359 2181 typedef _GraphGraph;2182 typedef _DirectionMapDirectionMap;2183 2184 typedef typename G raph::Node Node;2185 typedef typename G raph::Edge Arc;2360 typedef GR Graph; 2361 typedef DM DirectionMap; 2362 2363 typedef typename GR::Node Node; 2364 typedef typename GR::Edge Arc; 2186 2365 2187 2366 void reverseArc(const Arc& arc) { … … 2192 2371 void first(Arc& i) const { _graph->first(i); } 2193 2372 void firstIn(Arc& i, const Node& n) const { 2194 bool d ;2373 bool d = true; 2195 2374 _graph->firstInc(i, d, n); 2196 2375 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); 2197 2376 } 2198 2377 void firstOut(Arc& i, const Node& n ) const { 2199 bool d ;2378 bool d = true; 2200 2379 _graph->firstInc(i, d, n); 2201 2380 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); … … 2225 2404 int nodeNum() const { return _graph->nodeNum(); } 2226 2405 2227 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;2406 typedef EdgeNumTagIndicator<Graph> ArcNumTag; 2228 2407 int arcNum() const { return _graph->edgeNum(); } 2229 2408 2230 typedef FindEdgeTagIndicator<Graph> Find EdgeTag;2409 typedef FindEdgeTagIndicator<Graph> FindArcTag; 2231 2410 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) { 2411 const Arc& prev = INVALID) const { 2412 Arc arc = _graph->findEdge(u, v, prev); 2413 while (arc != INVALID && source(arc) != u) { 2236 2414 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 2415 } 2246 2416 return arc; … … 2252 2422 2253 2423 Arc addArc(const Node& u, const Node& v) { 2254 Arc arc = _graph->add Arc(u, v);2255 _direction->set(arc, _graph-> source(arc) == u);2424 Arc arc = _graph->addEdge(u, v); 2425 _direction->set(arc, _graph->u(arc) == u); 2256 2426 return arc; 2257 2427 } … … 2271 2441 int maxArcId() const { return _graph->maxEdgeId(); } 2272 2442 2273 typedef typename ItemSetTraits<G raph, Node>::ItemNotifier NodeNotifier;2443 typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier; 2274 2444 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 2275 2445 2276 typedef typename ItemSetTraits<G raph, Arc>::ItemNotifier ArcNotifier;2446 typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier; 2277 2447 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 2278 2448 2279 template <typename _Value>2280 class NodeMap : public _Graph::template NodeMap<_Value> {2449 template <typename V> 2450 class NodeMap : public GR::template NodeMap<V> { 2281 2451 public: 2282 2452 2283 typedef typename _Graph::template NodeMap<_Value> Parent;2284 2285 explicit NodeMap(const OrienterBase & adapter)2453 typedef typename GR::template NodeMap<V> Parent; 2454 2455 explicit NodeMap(const OrienterBase<GR, DM>& adapter) 2286 2456 : Parent(*adapter._graph) {} 2287 2457 2288 NodeMap(const OrienterBase & adapter, const _Value& value)2458 NodeMap(const OrienterBase<GR, DM>& adapter, const V& value) 2289 2459 : Parent(*adapter._graph, value) {} 2290 2460 … … 2302 2472 }; 2303 2473 2304 template <typename _Value>2305 class ArcMap : public _Graph::template EdgeMap<_Value> {2474 template <typename V> 2475 class ArcMap : public GR::template EdgeMap<V> { 2306 2476 public: 2307 2477 2308 typedef typename Graph::template EdgeMap< _Value> Parent;2309 2310 explicit ArcMap(const OrienterBase & adapter)2478 typedef typename Graph::template EdgeMap<V> Parent; 2479 2480 explicit ArcMap(const OrienterBase<GR, DM>& adapter) 2311 2481 : Parent(*adapter._graph) { } 2312 2482 2313 ArcMap(const OrienterBase & adapter, const _Value& value)2483 ArcMap(const OrienterBase<GR, DM>& adapter, const V& value) 2314 2484 : Parent(*adapter._graph, value) { } 2315 2485 … … 2330 2500 protected: 2331 2501 Graph* _graph; 2332 DirectionMap* _direction; 2333 2334 void setDirectionMap(DirectionMap& direction) { 2502 DM* _direction; 2503 2504 void initialize(GR& graph, DM& direction) { 2505 _graph = &graph; 2335 2506 _direction = &direction; 2336 2507 } 2337 2508 2338 void setGraph(Graph& graph) {2339 _graph = &graph;2340 }2341 2342 2509 }; 2343 2510 2344 2511 /// \ingroup graph_adaptors 2345 2512 /// 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> > 2513 /// \brief Adaptor class for orienting the edges of a graph to get a digraph 2514 /// 2515 /// Orienter adaptor can be used for orienting the edges of a graph to 2516 /// get a digraph. A \c bool edge map of the underlying graph must be 2517 /// specified, which define the direction of the arcs in the adaptor. 2518 /// The arcs can be easily reversed by the \c reverseArc() member function 2519 /// of the adaptor. 2520 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. 2521 /// 2522 /// The adapted graph can also be modified through this adaptor 2523 /// by adding or removing nodes or arcs, unless the \c GR template 2524 /// parameter is set to be \c const. 2525 /// 2526 /// \tparam GR The type of the adapted graph. 2527 /// It must conform to the \ref concepts::Graph "Graph" concept. 2528 /// It can also be specified to be \c const. 2529 /// \tparam DM The type of the direction map. 2530 /// It must be a \c bool (or convertible) edge map of the 2531 /// adapted graph. The default type is 2532 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>". 2533 /// 2534 /// \note The \c Node type of this adaptor and the adapted graph are 2535 /// convertible to each other, moreover the \c Arc type of the adaptor 2536 /// and the \c Edge type of the adapted graph are also convertible to 2537 /// each other. 2538 #ifdef DOXYGEN 2539 template<typename GR, 2540 typename DM> 2541 class Orienter { 2542 #else 2543 template<typename GR, 2544 typename DM = typename GR::template EdgeMap<bool> > 2362 2545 class Orienter : 2363 public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > { 2364 public: 2365 typedef _Graph Graph; 2366 typedef DigraphAdaptorExtender< 2367 OrienterBase<_Graph, DirectionMap> > Parent; 2546 public DigraphAdaptorExtender<OrienterBase<GR, DM> > { 2547 #endif 2548 public: 2549 2550 /// The type of the adapted graph. 2551 typedef GR Graph; 2552 /// The type of the direction edge map. 2553 typedef DM DirectionMap; 2554 2555 typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent; 2368 2556 typedef typename Parent::Arc Arc; 2369 2557 protected: … … 2371 2559 public: 2372 2560 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. 2561 /// \brief Constructor 2562 /// 2563 /// Constructor of the adaptor. 2564 Orienter(GR& graph, DM& direction) { 2565 Parent::initialize(graph, direction); 2566 } 2567 2568 /// \brief Reverses the given arc 2569 /// 2570 /// This function reverses the given arc. 2571 /// It is done by simply negate the assigned value of \c a 2572 /// in the direction map. 2384 2573 void reverseArc(const Arc& a) { 2385 2574 Parent::reverseArc(a); … … 2387 2576 }; 2388 2577 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); 2578 /// \brief Returns a read-only Orienter adaptor 2579 /// 2580 /// This function just returns a read-only \ref Orienter adaptor. 2581 /// \ingroup graph_adaptors 2582 /// \relates Orienter 2583 template<typename GR, typename DM> 2584 Orienter<const GR, DM> 2585 orienter(const GR& graph, DM& direction) { 2586 return Orienter<const GR, DM>(graph, direction); 2396 2587 } 2397 2588 2398 template<typename G raph, typename DirectionMap>2399 Orienter<const G raph, const DirectionMap>2400 orienter(const G raph& graph, const DirectionMap& dm) {2401 return Orienter<const G raph, const DirectionMap>(graph, dm);2589 template<typename GR, typename DM> 2590 Orienter<const GR, const DM> 2591 orienter(const GR& graph, const DM& direction) { 2592 return Orienter<const GR, const DM>(graph, direction); 2402 2593 } 2403 2594 2404 2595 namespace _adaptor_bits { 2405 2596 2406 template<typename _Digraph, 2407 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 2408 typename _FlowMap = _CapacityMap, 2409 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 2597 template <typename DGR, typename CM, typename FM, typename TL> 2410 2598 class ResForwardFilter { 2411 2599 public: 2412 2600 2413 typedef _Digraph Digraph; 2414 typedef _CapacityMap CapacityMap; 2415 typedef _FlowMap FlowMap; 2416 typedef _Tolerance Tolerance; 2417 2418 typedef typename Digraph::Arc Key; 2601 typedef typename DGR::Arc Key; 2419 2602 typedef bool Value; 2420 2603 2421 2604 private: 2422 2605 2423 const CapacityMap* _capacity; 2424 const FlowMap* _flow; 2425 Tolerance _tolerance; 2606 const CM* _capacity; 2607 const FM* _flow; 2608 TL _tolerance; 2609 2426 2610 public: 2427 2611 2428 ResForwardFilter(const C apacityMap& capacity, const FlowMap& flow,2429 const T olerance& tolerance = Tolerance())2612 ResForwardFilter(const CM& capacity, const FM& flow, 2613 const TL& tolerance = TL()) 2430 2614 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2431 2615 2432 bool operator[](const typename D igraph::Arc& a) const {2616 bool operator[](const typename DGR::Arc& a) const { 2433 2617 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]); 2434 2618 } 2435 2619 }; 2436 2620 2437 template<typename _Digraph, 2438 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 2439 typename _FlowMap = _CapacityMap, 2440 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 2621 template<typename DGR,typename CM, typename FM, typename TL> 2441 2622 class ResBackwardFilter { 2442 2623 public: 2443 2624 2444 typedef _Digraph Digraph; 2445 typedef _CapacityMap CapacityMap; 2446 typedef _FlowMap FlowMap; 2447 typedef _Tolerance Tolerance; 2448 2449 typedef typename Digraph::Arc Key; 2625 typedef typename DGR::Arc Key; 2450 2626 typedef bool Value; 2451 2627 2452 2628 private: 2453 2629 2454 const C apacityMap* _capacity;2455 const F lowMap* _flow;2456 T olerance_tolerance;2630 const CM* _capacity; 2631 const FM* _flow; 2632 TL _tolerance; 2457 2633 2458 2634 public: 2459 2635 2460 ResBackwardFilter(const C apacityMap& capacity, const FlowMap& flow,2461 const T olerance& tolerance = Tolerance())2636 ResBackwardFilter(const CM& capacity, const FM& flow, 2637 const TL& tolerance = TL()) 2462 2638 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2463 2639 2464 bool operator[](const typename D igraph::Arc& a) const {2640 bool operator[](const typename DGR::Arc& a) const { 2465 2641 return _tolerance.positive((*_flow)[a]); 2466 2642 } … … 2471 2647 /// \ingroup graph_adaptors 2472 2648 /// 2473 /// \brief A n adaptor for composing the residualgraph for directed2649 /// \brief Adaptor class for composing the residual digraph for directed 2474 2650 /// flow and circulation problems. 2475 2651 /// 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, 2501 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 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> > > 2652 /// ResidualDigraph can be used for composing the \e residual digraph 2653 /// for directed flow and circulation problems. Let \f$ G=(V, A) \f$ 2654 /// be a directed graph and let \f$ F \f$ be a number type. 2655 /// Let \f$ flow, cap: A\to F \f$ be functions on the arcs. 2656 /// This adaptor implements a digraph structure with node set \f$ V \f$ 2657 /// and arc set \f$ A_{forward}\cup A_{backward} \f$, 2658 /// where \f$ A_{forward}=\{uv : uv\in A, flow(uv)<cap(uv)\} \f$ and 2659 /// \f$ A_{backward}=\{vu : uv\in A, flow(uv)>0\} \f$, i.e. the so 2660 /// called residual digraph. 2661 /// When the union \f$ A_{forward}\cup A_{backward} \f$ is taken, 2662 /// multiplicities are counted, i.e. the adaptor has exactly 2663 /// \f$ |A_{forward}| + |A_{backward}|\f$ arcs (it may have parallel 2664 /// arcs). 2665 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. 2666 /// 2667 /// \tparam DGR The type of the adapted digraph. 2668 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 2669 /// It is implicitly \c const. 2670 /// \tparam CM The type of the capacity map. 2671 /// It must be an arc map of some numerical type, which defines 2672 /// the capacities in the flow problem. It is implicitly \c const. 2673 /// The default type is 2674 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 2675 /// \tparam FM The type of the flow map. 2676 /// It must be an arc map of some numerical type, which defines 2677 /// the flow values in the flow problem. The default type is \c CM. 2678 /// \tparam TL The tolerance type for handling inexact computation. 2679 /// The default tolerance type depends on the value type of the 2680 /// capacity map. 2681 /// 2682 /// \note This adaptor is implemented using Undirector and FilterArcs 2683 /// adaptors. 2684 /// 2685 /// \note The \c Node type of this adaptor and the adapted digraph are 2686 /// convertible to each other, moreover the \c Arc type of the adaptor 2687 /// is convertible to the \c Arc type of the adapted digraph. 2688 #ifdef DOXYGEN 2689 template<typename DGR, typename CM, typename FM, typename TL> 2690 class ResidualDigraph 2691 #else 2692 template<typename DGR, 2693 typename CM = typename DGR::template ArcMap<int>, 2694 typename FM = CM, 2695 typename TL = Tolerance<typename CM::Value> > 2696 class ResidualDigraph 2697 : public SubDigraph< 2698 Undirector<const DGR>, 2699 ConstMap<typename DGR::Node, Const<bool, true> >, 2700 typename Undirector<const DGR>::template CombinedArcMap< 2701 _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>, 2702 _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > > 2703 #endif 2510 2704 { 2511 2705 public: 2512 2706 2513 typedef _Digraph Digraph; 2514 typedef _CapacityMap CapacityMap; 2515 typedef _FlowMap FlowMap; 2516 typedef _Tolerance Tolerance; 2707 /// The type of the underlying digraph. 2708 typedef DGR Digraph; 2709 /// The type of the capacity map. 2710 typedef CM CapacityMap; 2711 /// The type of the flow map. 2712 typedef FM FlowMap; 2713 /// The tolerance type. 2714 typedef TL Tolerance; 2517 2715 2518 2716 typedef typename CapacityMap::Value Value; 2519 typedef Residual Adaptor;2717 typedef ResidualDigraph Adaptor; 2520 2718 2521 2719 protected: … … 2523 2721 typedef Undirector<const Digraph> Undirected; 2524 2722 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; 2723 typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter; 2724 2725 typedef _adaptor_bits::ResForwardFilter<const DGR, CM, 2726 FM, TL> ForwardFilter; 2727 2728 typedef _adaptor_bits::ResBackwardFilter<const DGR, CM, 2729 FM, TL> BackwardFilter; 2530 2730 2531 2731 typedef typename Undirected:: 2532 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;2533 2534 typedef FilterArcs<Undirected, ArcFilter> Parent;2732 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter; 2733 2734 typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent; 2535 2735 2536 2736 const CapacityMap* _capacity; … … 2538 2738 2539 2739 Undirected _graph; 2740 NodeFilter _node_filter; 2540 2741 ForwardFilter _forward_filter; 2541 2742 BackwardFilter _backward_filter; … … 2544 2745 public: 2545 2746 2546 /// \brief Constructor of the residual digraph. 2547 /// 2548 /// Constructor of the residual graph. The parameters are the digraph, 2549 /// the flow map, the capacity map and a tolerance object. 2550 Residual(const Digraph& digraph, const CapacityMap& capacity, 2551 FlowMap& flow, const Tolerance& tolerance = Tolerance()) 2552 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph), 2747 /// \brief Constructor 2748 /// 2749 /// Constructor of the residual digraph adaptor. The parameters are the 2750 /// digraph, the capacity map, the flow map, and a tolerance object. 2751 ResidualDigraph(const DGR& digraph, const CM& capacity, 2752 FM& flow, const TL& tolerance = Tolerance()) 2753 : Parent(), _capacity(&capacity), _flow(&flow), 2754 _graph(digraph), _node_filter(), 2553 2755 _forward_filter(capacity, flow, tolerance), 2554 2756 _backward_filter(capacity, flow, tolerance), 2555 2757 _arc_filter(_forward_filter, _backward_filter) 2556 2758 { 2557 Parent::setDigraph(_graph); 2558 Parent::setArcFilterMap(_arc_filter); 2759 Parent::initialize(_graph, _node_filter, _arc_filter); 2559 2760 } 2560 2761 2561 2762 typedef typename Parent::Arc Arc; 2562 2763 2563 /// \brief Gives back the residual capacity of thearc.2564 /// 2565 /// Gives back the residual capacity of thearc.2764 /// \brief Returns the residual capacity of the given arc. 2765 /// 2766 /// Returns the residual capacity of the given arc. 2566 2767 Value residualCapacity(const Arc& a) const { 2567 2768 if (Undirected::direction(a)) { … … 2572 2773 } 2573 2774 2574 /// \brief Augment on the given arc in the residualgraph.2575 /// 2576 /// Augment on the given arc in the residual graph. It increase2577 /// or decrease the flow on the original arc depend on the direction2578 /// of the residual arc.2775 /// \brief Augments on the given arc in the residual digraph. 2776 /// 2777 /// Augments on the given arc in the residual digraph. It increases 2778 /// or decreases the flow value on the original arc according to the 2779 /// direction of the residual arc. 2579 2780 void augment(const Arc& a, const Value& v) const { 2580 2781 if (Undirected::direction(a)) { … … 2585 2786 } 2586 2787 2587 /// \brief Returns the direction of the arc. 2588 /// 2589 /// Returns true when the arc is same oriented as the original arc. 2788 /// \brief Returns \c true if the given residual arc is a forward arc. 2789 /// 2790 /// Returns \c true if the given residual arc has the same orientation 2791 /// as the original arc, i.e. it is a so called forward arc. 2590 2792 static bool forward(const Arc& a) { 2591 2793 return Undirected::direction(a); 2592 2794 } 2593 2795 2594 /// \brief Returns the direction of the arc. 2595 /// 2596 /// Returns true when the arc is opposite oriented as the original arc. 2796 /// \brief Returns \c true if the given residual arc is a backward arc. 2797 /// 2798 /// Returns \c true if the given residual arc has the opposite orientation 2799 /// than the original arc, i.e. it is a so called backward arc. 2597 2800 static bool backward(const Arc& a) { 2598 2801 return !Undirected::direction(a); 2599 2802 } 2600 2803 2601 /// \brief Gives back the forward oriented residual arc. 2602 /// 2603 /// Gives back the forward oriented residual arc. 2804 /// \brief Returns the forward oriented residual arc. 2805 /// 2806 /// Returns the forward oriented residual arc related to the given 2807 /// arc of the underlying digraph. 2604 2808 static Arc forward(const typename Digraph::Arc& a) { 2605 2809 return Undirected::direct(a, true); 2606 2810 } 2607 2811 2608 /// \brief Gives back the backward oriented residual arc. 2609 /// 2610 /// Gives back the backward oriented residual arc. 2812 /// \brief Returns the backward oriented residual arc. 2813 /// 2814 /// Returns the backward oriented residual arc related to the given 2815 /// arc of the underlying digraph. 2611 2816 static Arc backward(const typename Digraph::Arc& a) { 2612 2817 return Undirected::direct(a, false); … … 2615 2820 /// \brief Residual capacity map. 2616 2821 /// 2617 /// In generic residual graph the residual capacity can be obtained 2618 /// as a map. 2822 /// This map adaptor class can be used for obtaining the residual 2823 /// capacities as an arc map of the residual digraph. 2824 /// Its value type is inherited from the capacity map. 2619 2825 class ResidualCapacity { 2620 2826 protected: 2621 2827 const Adaptor* _adaptor; 2622 2828 public: 2623 /// The Key type2829 /// The key type of the map 2624 2830 typedef Arc Key; 2625 /// The Value type2626 typedef typename _CapacityMap::Value Value;2831 /// The value type of the map 2832 typedef typename CapacityMap::Value Value; 2627 2833 2628 2834 /// Constructor 2629 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {} 2630 2631 /// \e 2835 ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 2836 : _adaptor(&adaptor) {} 2837 2838 /// Returns the value associated with the given residual arc 2632 2839 Value operator[](const Arc& a) const { 2633 2840 return _adaptor->residualCapacity(a); … … 2636 2843 }; 2637 2844 2845 /// \brief Returns a residual capacity map 2846 /// 2847 /// This function just returns a residual capacity map. 2848 ResidualCapacity residualCapacity() const { 2849 return ResidualCapacity(*this); 2850 } 2851 2638 2852 }; 2639 2853 2640 template <typename _Digraph> 2854 /// \brief Returns a (read-only) Residual adaptor 2855 /// 2856 /// This function just returns a (read-only) \ref ResidualDigraph adaptor. 2857 /// \ingroup graph_adaptors 2858 /// \relates ResidualDigraph 2859 template<typename DGR, typename CM, typename FM> 2860 ResidualDigraph<DGR, CM, FM> 2861 residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) { 2862 return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map); 2863 } 2864 2865 2866 template <typename DGR> 2641 2867 class SplitNodesBase { 2642 2868 public: 2643 2869 2644 typedef _DigraphDigraph;2645 typedef DigraphAdaptorBase<const _Digraph> Parent;2870 typedef DGR Digraph; 2871 typedef DigraphAdaptorBase<const DGR> Parent; 2646 2872 typedef SplitNodesBase Adaptor; 2647 2873 2648 typedef typename D igraph::Node DigraphNode;2649 typedef typename D igraph::Arc DigraphArc;2874 typedef typename DGR::Node DigraphNode; 2875 typedef typename DGR::Arc DigraphArc; 2650 2876 2651 2877 class Node; … … 2885 3111 2886 3112 typedef True NodeNumTag; 2887 2888 3113 int nodeNum() const { 2889 3114 return 2 * countNodes(*_digraph); 2890 3115 } 2891 3116 2892 typedef True EdgeNumTag;3117 typedef True ArcNumTag; 2893 3118 int arcNum() const { 2894 3119 return countArcs(*_digraph) + countNodes(*_digraph); 2895 3120 } 2896 3121 2897 typedef True Find EdgeTag;3122 typedef True FindArcTag; 2898 3123 Arc findArc(const Node& u, const Node& v, 2899 3124 const Arc& prev = INVALID) const { 2900 if (inNode(u)) { 2901 if (outNode(v)) { 2902 if (static_cast<const DigraphNode&>(u) == 2903 static_cast<const DigraphNode&>(v) && prev == INVALID) { 2904 return Arc(u); 2905 } 3125 if (inNode(u) && outNode(v)) { 3126 if (static_cast<const DigraphNode&>(u) == 3127 static_cast<const DigraphNode&>(v) && prev == INVALID) { 3128 return Arc(u); 2906 3129 } 2907 } else { 2908 if (inNode(v)) { 2909 return Arc(::lemon::findArc(*_digraph, u, v, prev)); 2910 } 3130 } 3131 else if (outNode(u) && inNode(v)) { 3132 return Arc(::lemon::findArc(*_digraph, u, v, prev)); 2911 3133 } 2912 3134 return INVALID; … … 2915 3137 private: 2916 3138 2917 template <typename _Value>3139 template <typename V> 2918 3140 class NodeMapBase 2919 : public MapTraits<typename Parent::template NodeMap< _Value> > {2920 typedef typename Parent::template NodeMap< _Value> NodeImpl;3141 : public MapTraits<typename Parent::template NodeMap<V> > { 3142 typedef typename Parent::template NodeMap<V> NodeImpl; 2921 3143 public: 2922 3144 typedef Node Key; 2923 typedef _Value Value; 2924 2925 NodeMapBase(const Adaptor& adaptor) 3145 typedef V Value; 3146 typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag; 3147 typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue; 3148 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue; 3149 typedef typename MapTraits<NodeImpl>::ReturnValue Reference; 3150 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference; 3151 3152 NodeMapBase(const SplitNodesBase<DGR>& adaptor) 2926 3153 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {} 2927 NodeMapBase(const Adaptor& adaptor, const Value& value)3154 NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value) 2928 3155 : _in_map(*adaptor._digraph, value), 2929 3156 _out_map(*adaptor._digraph, value) {} 2930 3157 2931 void set(const Node& key, const V alue& val) {2932 if ( Adaptor::inNode(key)) { _in_map.set(key, val); }3158 void set(const Node& key, const V& val) { 3159 if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); } 2933 3160 else {_out_map.set(key, val); } 2934 3161 } 2935 3162 2936 typename MapTraits<NodeImpl>::ReturnValue 2937 operator[](const Node& key) { 2938 if (Adaptor::inNode(key)) { return _in_map[key]; } 3163 ReturnValue operator[](const Node& key) { 3164 if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; } 2939 3165 else { return _out_map[key]; } 2940 3166 } 2941 3167 2942 typename MapTraits<NodeImpl>::ConstReturnValue 2943 operator[](const Node& key) const { 3168 ConstReturnValue operator[](const Node& key) const { 2944 3169 if (Adaptor::inNode(key)) { return _in_map[key]; } 2945 3170 else { return _out_map[key]; } … … 2950 3175 }; 2951 3176 2952 template <typename _Value>3177 template <typename V> 2953 3178 class ArcMapBase 2954 : public MapTraits<typename Parent::template ArcMap< _Value> > {2955 typedef typename Parent::template ArcMap< _Value> ArcImpl;2956 typedef typename Parent::template NodeMap< _Value> NodeImpl;3179 : public MapTraits<typename Parent::template ArcMap<V> > { 3180 typedef typename Parent::template ArcMap<V> ArcImpl; 3181 typedef typename Parent::template NodeMap<V> NodeImpl; 2957 3182 public: 2958 3183 typedef Arc Key; 2959 typedef _Value Value; 2960 2961 ArcMapBase(const Adaptor& adaptor) 3184 typedef V Value; 3185 typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag; 3186 typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue; 3187 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue; 3188 typedef typename MapTraits<ArcImpl>::ReturnValue Reference; 3189 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference; 3190 3191 ArcMapBase(const SplitNodesBase<DGR>& adaptor) 2962 3192 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {} 2963 ArcMapBase(const Adaptor& adaptor, const Value& value)3193 ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value) 2964 3194 : _arc_map(*adaptor._digraph, value), 2965 3195 _node_map(*adaptor._digraph, value) {} 2966 3196 2967 void set(const Arc& key, const V alue& val) {2968 if ( Adaptor::origArc(key)) {2969 _arc_map.set( key._item.first(), val);3197 void set(const Arc& key, const V& val) { 3198 if (SplitNodesBase<DGR>::origArc(key)) { 3199 _arc_map.set(static_cast<const DigraphArc&>(key), val); 2970 3200 } else { 2971 _node_map.set( key._item.second(), val);3201 _node_map.set(static_cast<const DigraphNode&>(key), val); 2972 3202 } 2973 3203 } 2974 3204 2975 typename MapTraits<ArcImpl>::ReturnValue 2976 operator[](const Arc& key) { 2977 if (Adaptor::origArc(key)) { 2978 return _arc_map[key._item.first()]; 3205 ReturnValue operator[](const Arc& key) { 3206 if (SplitNodesBase<DGR>::origArc(key)) { 3207 return _arc_map[static_cast<const DigraphArc&>(key)]; 2979 3208 } else { 2980 return _node_map[ key._item.second()];3209 return _node_map[static_cast<const DigraphNode&>(key)]; 2981 3210 } 2982 3211 } 2983 3212 2984 typename MapTraits<ArcImpl>::ConstReturnValue 2985 operator[](const Arc& key) const { 2986 if (Adaptor::origArc(key)) { 2987 return _arc_map[key._item.first()]; 3213 ConstReturnValue operator[](const Arc& key) const { 3214 if (SplitNodesBase<DGR>::origArc(key)) { 3215 return _arc_map[static_cast<const DigraphArc&>(key)]; 2988 3216 } else { 2989 return _node_map[ key._item.second()];3217 return _node_map[static_cast<const DigraphNode&>(key)]; 2990 3218 } 2991 3219 } … … 2998 3226 public: 2999 3227 3000 template <typename _Value>3228 template <typename V> 3001 3229 class NodeMap 3002 : public SubMapExtender< Adaptor, NodeMapBase<_Value> >3230 : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > 3003 3231 { 3004 3232 public: 3005 typedef _ValueValue;3006 typedef SubMapExtender< Adaptor, NodeMapBase<Value> > Parent;3007 3008 NodeMap(const Adaptor& adaptor)3233 typedef V Value; 3234 typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent; 3235 3236 NodeMap(const SplitNodesBase<DGR>& adaptor) 3009 3237 : Parent(adaptor) {} 3010 3238 3011 NodeMap(const Adaptor& adaptor, const Value& value)3239 NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value) 3012 3240 : Parent(adaptor, value) {} 3013 3241 … … 3024 3252 }; 3025 3253 3026 template <typename _Value>3254 template <typename V> 3027 3255 class ArcMap 3028 : public SubMapExtender< Adaptor, ArcMapBase<_Value> >3256 : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > 3029 3257 { 3030 3258 public: 3031 typedef _ValueValue;3032 typedef SubMapExtender< Adaptor, ArcMapBase<Value> > Parent;3033 3034 ArcMap(const Adaptor& adaptor)3259 typedef V Value; 3260 typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent; 3261 3262 ArcMap(const SplitNodesBase<DGR>& adaptor) 3035 3263 : Parent(adaptor) {} 3036 3264 3037 ArcMap(const Adaptor& adaptor, const Value& value)3265 ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value) 3038 3266 : Parent(adaptor, value) {} 3039 3267 … … 3054 3282 SplitNodesBase() : _digraph(0) {} 3055 3283 3056 D igraph* _digraph;3057 3058 void setDigraph(Digraph& digraph) {3284 DGR* _digraph; 3285 3286 void initialize(Digraph& digraph) { 3059 3287 _digraph = &digraph; 3060 3288 } … … 3064 3292 /// \ingroup graph_adaptors 3065 3293 /// 3066 /// \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 3076 /// \f$ (u_{in}, u_{out}) \f$. 3077 /// 3078 /// The aim of this class is to run algorithm with node costs if the 3079 /// algorithm can use directly just arc costs. In this case we should use 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. 3085 template <typename _Digraph> 3294 /// \brief Adaptor class for splitting the nodes of a digraph. 3295 /// 3296 /// SplitNodes adaptor can be used for splitting each node into an 3297 /// \e in-node and an \e out-node in a digraph. Formaly, the adaptor 3298 /// replaces each node \f$ u \f$ in the digraph with two nodes, 3299 /// namely node \f$ u_{in} \f$ and node \f$ u_{out} \f$. 3300 /// If there is a \f$ (v, u) \f$ arc in the original digraph, then the 3301 /// new target of the arc will be \f$ u_{in} \f$ and similarly the 3302 /// source of each original \f$ (u, v) \f$ arc will be \f$ u_{out} \f$. 3303 /// The adaptor adds an additional \e bind \e arc from \f$ u_{in} \f$ 3304 /// to \f$ u_{out} \f$ for each node \f$ u \f$ of the original digraph. 3305 /// 3306 /// The aim of this class is running an algorithm with respect to node 3307 /// costs or capacities if the algorithm considers only arc costs or 3308 /// capacities directly. 3309 /// In this case you can use \c SplitNodes adaptor, and set the node 3310 /// costs/capacities of the original digraph to the \e bind \e arcs 3311 /// in the adaptor. 3312 /// 3313 /// \tparam DGR The type of the adapted digraph. 3314 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 3315 /// It is implicitly \c const. 3316 /// 3317 /// \note The \c Node type of this adaptor is converible to the \c Node 3318 /// type of the adapted digraph. 3319 template <typename DGR> 3320 #ifdef DOXYGEN 3321 class SplitNodes { 3322 #else 3086 3323 class SplitNodes 3087 : public DigraphAdaptorExtender<SplitNodesBase<_Digraph> > { 3088 public: 3089 typedef _Digraph Digraph; 3090 typedef DigraphAdaptorExtender<SplitNodesBase<Digraph> > Parent; 3091 3092 typedef typename Digraph::Node DigraphNode; 3093 typedef typename Digraph::Arc DigraphArc; 3324 : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > { 3325 #endif 3326 public: 3327 typedef DGR Digraph; 3328 typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent; 3329 3330 typedef typename DGR::Node DigraphNode; 3331 typedef typename DGR::Arc DigraphArc; 3094 3332 3095 3333 typedef typename Parent::Node Node; 3096 3334 typedef typename Parent::Arc Arc; 3097 3335 3098 /// \brief Constructor of the adaptor.3336 /// \brief Constructor 3099 3337 /// 3100 3338 /// Constructor of the adaptor. 3101 SplitNodes( Digraph& g) {3102 Parent:: setDigraph(g);3103 } 3104 3105 /// \brief Returns true when the node isin-node.3106 /// 3107 /// Returns true when the node isin-node.3339 SplitNodes(const DGR& g) { 3340 Parent::initialize(g); 3341 } 3342 3343 /// \brief Returns \c true if the given node is an in-node. 3344 /// 3345 /// Returns \c true if the given node is an in-node. 3108 3346 static bool inNode(const Node& n) { 3109 3347 return Parent::inNode(n); 3110 3348 } 3111 3349 3112 /// \brief Returns true when the node isout-node.3113 /// 3114 /// Returns true when the node isout-node.3350 /// \brief Returns \c true if the given node is an out-node. 3351 /// 3352 /// Returns \c true if the given node is an out-node. 3115 3353 static bool outNode(const Node& n) { 3116 3354 return Parent::outNode(n); 3117 3355 } 3118 3356 3119 /// \brief Returns true when the arc is arc in the original digraph. 3120 /// 3121 /// Returns true when the arc is arc in the original digraph. 3357 /// \brief Returns \c true if the given arc is an original arc. 3358 /// 3359 /// Returns \c true if the given arc is one of the arcs in the 3360 /// original digraph. 3122 3361 static bool origArc(const Arc& a) { 3123 3362 return Parent::origArc(a); 3124 3363 } 3125 3364 3126 /// \brief Returns true when the arc binds an in-node and an out-node. 3127 /// 3128 /// Returns true when the arc binds an in-node and an out-node. 3365 /// \brief Returns \c true if the given arc is a bind arc. 3366 /// 3367 /// Returns \c true if the given arc is a bind arc, i.e. it connects 3368 /// an in-node and an out-node. 3129 3369 static bool bindArc(const Arc& a) { 3130 3370 return Parent::bindArc(a); 3131 3371 } 3132 3372 3133 /// \brief Gives back the in-node created from the \cnode.3134 /// 3135 /// Gives back the in-node created from the \cnode.3373 /// \brief Returns the in-node created from the given original node. 3374 /// 3375 /// Returns the in-node created from the given original node. 3136 3376 static Node inNode(const DigraphNode& n) { 3137 3377 return Parent::inNode(n); 3138 3378 } 3139 3379 3140 /// \brief Gives back the out-node created from the \cnode.3141 /// 3142 /// Gives back the out-node created from the \cnode.3380 /// \brief Returns the out-node created from the given original node. 3381 /// 3382 /// Returns the out-node created from the given original node. 3143 3383 static Node outNode(const DigraphNode& n) { 3144 3384 return Parent::outNode(n); 3145 3385 } 3146 3386 3147 /// \brief Gives back the arc binds the two part of the node. 3148 /// 3149 /// Gives back the arc binds the two part of the node. 3387 /// \brief Returns the bind arc that corresponds to the given 3388 /// original node. 3389 /// 3390 /// Returns the bind arc in the adaptor that corresponds to the given 3391 /// original node, i.e. the arc connecting the in-node and out-node 3392 /// of \c n. 3150 3393 static Arc arc(const DigraphNode& n) { 3151 3394 return Parent::arc(n); 3152 3395 } 3153 3396 3154 /// \brief Gives back the arc of the original arc. 3155 /// 3156 /// Gives back the arc of the original arc. 3397 /// \brief Returns the arc that corresponds to the given original arc. 3398 /// 3399 /// Returns the arc in the adaptor that corresponds to the given 3400 /// original arc. 3157 3401 static Arc arc(const DigraphArc& a) { 3158 3402 return Parent::arc(a); 3159 3403 } 3160 3404 3161 /// \brief NodeMap combined from two original NodeMap 3162 /// 3163 /// This class adapt two of the original digraph NodeMap to 3164 /// get a node map on the adapted digraph. 3405 /// \brief Node map combined from two original node maps 3406 /// 3407 /// This map adaptor class adapts two node maps of the original digraph 3408 /// to get a node map of the split digraph. 3409 /// Its value type is inherited from the first node map type 3410 /// (\c InNodeMap). 3165 3411 template <typename InNodeMap, typename OutNodeMap> 3166 3412 class CombinedNodeMap { 3167 3413 public: 3168 3414 3415 /// The key type of the map 3169 3416 typedef Node Key; 3417 /// The value type of the map 3170 3418 typedef typename InNodeMap::Value Value; 3171 3419 3172 /// \brief Constructor 3173 /// 3174 /// Constructor. 3420 typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag; 3421 typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue; 3422 typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue; 3423 typedef typename MapTraits<InNodeMap>::ReturnValue Reference; 3424 typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference; 3425 3426 /// Constructor 3175 3427 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) 3176 3428 : _in_map(in_map), _out_map(out_map) {} 3177 3429 3178 /// \brief The subscript operator. 3179 /// 3180 /// The subscript operator. 3181 Value& operator[](const Key& key) { 3182 if (Parent::inNode(key)) { 3430 /// Returns the value associated with the given key. 3431 Value operator[](const Key& key) const { 3432 if (SplitNodesBase<const DGR>::inNode(key)) { 3183 3433 return _in_map[key]; 3184 3434 } else { … … 3187 3437 } 3188 3438 3189 /// \brief The const subscript operator. 3190 /// 3191 /// The const subscript operator. 3192 Value operator[](const Key& key) const { 3193 if (Parent::inNode(key)) { 3439 /// Returns a reference to the value associated with the given key. 3440 Value& operator[](const Key& key) { 3441 if (SplitNodesBase<const DGR>::inNode(key)) { 3194 3442 return _in_map[key]; 3195 3443 } else { … … 3198 3446 } 3199 3447 3200 /// \brief The setter function of the map. 3201 /// 3202 /// The setter function of the map. 3448 /// Sets the value associated with the given key. 3203 3449 void set(const Key& key, const Value& value) { 3204 if ( Parent::inNode(key)) {3450 if (SplitNodesBase<const DGR>::inNode(key)) { 3205 3451 _in_map.set(key, value); 3206 3452 } else { … … 3217 3463 3218 3464 3219 /// \brief Just gives backa combined node map3220 /// 3221 /// Just gives back a combined node map3465 /// \brief Returns a combined node map 3466 /// 3467 /// This function just returns a combined node map. 3222 3468 template <typename InNodeMap, typename OutNodeMap> 3223 3469 static CombinedNodeMap<InNodeMap, OutNodeMap> … … 3245 3491 } 3246 3492 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 3251 template <typename DigraphArcMap, typename DigraphNodeMap> 3493 /// \brief Arc map combined from an arc map and a node map of the 3494 /// original digraph. 3495 /// 3496 /// This map adaptor class adapts an arc map and a node map of the 3497 /// original digraph to get an arc map of the split digraph. 3498 /// Its value type is inherited from the original arc map type 3499 /// (\c ArcMap). 3500 template <typename ArcMap, typename NodeMap> 3252 3501 class CombinedArcMap { 3253 3502 public: 3254 3503 3504 /// The key type of the map 3255 3505 typedef Arc Key; 3256 typedef typename DigraphArcMap::Value Value; 3257 3258 /// \brief Constructor 3259 /// 3260 /// Constructor. 3261 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) 3506 /// The value type of the map 3507 typedef typename ArcMap::Value Value; 3508 3509 typedef typename MapTraits<ArcMap>::ReferenceMapTag ReferenceMapTag; 3510 typedef typename MapTraits<ArcMap>::ReturnValue ReturnValue; 3511 typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReturnValue; 3512 typedef typename MapTraits<ArcMap>::ReturnValue Reference; 3513 typedef typename MapTraits<ArcMap>::ConstReturnValue ConstReference; 3514 3515 /// Constructor 3516 CombinedArcMap(ArcMap& arc_map, NodeMap& node_map) 3262 3517 : _arc_map(arc_map), _node_map(node_map) {} 3263 3518 3264 /// \brief The subscript operator. 3265 /// 3266 /// The subscript operator. 3519 /// Returns the value associated with the given key. 3520 Value operator[](const Key& arc) const { 3521 if (SplitNodesBase<const DGR>::origArc(arc)) { 3522 return _arc_map[arc]; 3523 } else { 3524 return _node_map[arc]; 3525 } 3526 } 3527 3528 /// Returns a reference to the value associated with the given key. 3529 Value& operator[](const Key& arc) { 3530 if (SplitNodesBase<const DGR>::origArc(arc)) { 3531 return _arc_map[arc]; 3532 } else { 3533 return _node_map[arc]; 3534 } 3535 } 3536 3537 /// Sets the value associated with the given key. 3267 3538 void set(const Arc& arc, const Value& val) { 3268 if ( Parent::origArc(arc)) {3539 if (SplitNodesBase<const DGR>::origArc(arc)) { 3269 3540 _arc_map.set(arc, val); 3270 3541 } else { … … 3273 3544 } 3274 3545 3275 /// \brief The const subscript operator.3276 ///3277 /// The const subscript operator.3278 Value operator[](const Key& arc) const {3279 if (Parent::origArc(arc)) {3280 return _arc_map[arc];3281 } else {3282 return _node_map[arc];3283 }3284 }3285 3286 /// \brief The const subscript operator.3287 ///3288 /// The const subscript operator.3289 Value& operator[](const Key& arc) {3290 if (Parent::origArc(arc)) {3291 return _arc_map[arc];3292 } else {3293 return _node_map[arc];3294 }3295 }3296 3297 3546 private: 3298 DigraphArcMap& _arc_map;3299 DigraphNodeMap& _node_map;3547 ArcMap& _arc_map; 3548 NodeMap& _node_map; 3300 3549 }; 3301 3550 3302 /// \brief Just gives back a combined arc map 3303 /// 3304 /// Just gives back a combined arc map 3305 template <typename DigraphArcMap, typename DigraphNodeMap> 3306 static CombinedArcMap<DigraphArcMap, DigraphNodeMap> 3307 combinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) { 3308 return CombinedArcMap<DigraphArcMap, DigraphNodeMap>(arc_map, node_map); 3309 } 3310 3311 template <typename DigraphArcMap, typename DigraphNodeMap> 3312 static CombinedArcMap<const DigraphArcMap, DigraphNodeMap> 3313 combinedArcMap(const DigraphArcMap& arc_map, DigraphNodeMap& node_map) { 3314 return CombinedArcMap<const DigraphArcMap, 3315 DigraphNodeMap>(arc_map, node_map); 3316 } 3317 3318 template <typename DigraphArcMap, typename DigraphNodeMap> 3319 static CombinedArcMap<DigraphArcMap, const DigraphNodeMap> 3320 combinedArcMap(DigraphArcMap& arc_map, const DigraphNodeMap& node_map) { 3321 return CombinedArcMap<DigraphArcMap, 3322 const DigraphNodeMap>(arc_map, node_map); 3323 } 3324 3325 template <typename DigraphArcMap, typename DigraphNodeMap> 3326 static CombinedArcMap<const DigraphArcMap, const DigraphNodeMap> 3327 combinedArcMap(const DigraphArcMap& arc_map, 3328 const DigraphNodeMap& node_map) { 3329 return CombinedArcMap<const DigraphArcMap, 3330 const DigraphNodeMap>(arc_map, node_map); 3551 /// \brief Returns a combined arc map 3552 /// 3553 /// This function just returns a combined arc map. 3554 template <typename ArcMap, typename NodeMap> 3555 static CombinedArcMap<ArcMap, NodeMap> 3556 combinedArcMap(ArcMap& arc_map, NodeMap& node_map) { 3557 return CombinedArcMap<ArcMap, NodeMap>(arc_map, node_map); 3558 } 3559 3560 template <typename ArcMap, typename NodeMap> 3561 static CombinedArcMap<const ArcMap, NodeMap> 3562 combinedArcMap(const ArcMap& arc_map, NodeMap& node_map) { 3563 return CombinedArcMap<const ArcMap, NodeMap>(arc_map, node_map); 3564 } 3565 3566 template <typename ArcMap, typename NodeMap> 3567 static CombinedArcMap<ArcMap, const NodeMap> 3568 combinedArcMap(ArcMap& arc_map, const NodeMap& node_map) { 3569 return CombinedArcMap<ArcMap, const NodeMap>(arc_map, node_map); 3570 } 3571 3572 template <typename ArcMap, typename NodeMap> 3573 static CombinedArcMap<const ArcMap, const NodeMap> 3574 combinedArcMap(const ArcMap& arc_map, const NodeMap& node_map) { 3575 return CombinedArcMap<const ArcMap, const NodeMap>(arc_map, node_map); 3331 3576 } 3332 3577 3333 3578 }; 3334 3579 3335 /// \brief Just gives back a node splitter 3336 /// 3337 /// Just gives back a node splitter 3338 template<typename Digraph> 3339 SplitNodes<Digraph> 3340 splitNodes(const Digraph& digraph) { 3341 return SplitNodes<Digraph>(digraph); 3580 /// \brief Returns a (read-only) SplitNodes adaptor 3581 /// 3582 /// This function just returns a (read-only) \ref SplitNodes adaptor. 3583 /// \ingroup graph_adaptors 3584 /// \relates SplitNodes 3585 template<typename DGR> 3586 SplitNodes<DGR> 3587 splitNodes(const DGR& digraph) { 3588 return SplitNodes<DGR>(digraph); 3342 3589 } 3343 3590 3591 #undef LEMON_SCOPE_FIX 3344 3592 3345 3593 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.