Changes in lemon/adaptors.h [566:c786cd201266:432:76287c8caa26] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/adaptors.h
r566 r432 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 95 * Copyright (C) 2003-2008 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 Adaptor classes for digraphs and graphs24 /// \brief Several graph adaptors 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>34 33 #include <lemon/tolerance.h> 35 34 … … 38 37 namespace lemon { 39 38 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> 39 template<typename _Digraph> 47 40 class DigraphAdaptorBase { 48 41 public: 49 typedef DGRDigraph;42 typedef _Digraph Digraph; 50 43 typedef DigraphAdaptorBase Adaptor; 44 typedef Digraph ParentDigraph; 51 45 52 46 protected: 53 D GR* _digraph;47 Digraph* _digraph; 54 48 DigraphAdaptorBase() : _digraph(0) { } 55 void initialize(DGR& digraph) { _digraph = &digraph; }56 57 public: 58 DigraphAdaptorBase(D GR& digraph) : _digraph(&digraph) { }59 60 typedef typename D GR::Node Node;61 typedef typename D GR::Arc Arc;49 void setDigraph(Digraph& digraph) { _digraph = &digraph; } 50 51 public: 52 DigraphAdaptorBase(Digraph& digraph) : _digraph(&digraph) { } 53 54 typedef typename Digraph::Node Node; 55 typedef typename Digraph::Arc Arc; 62 56 63 57 void first(Node& i) const { _digraph->first(i); } … … 74 68 Node target(const Arc& a) const { return _digraph->target(a); } 75 69 76 typedef NodeNumTagIndicator<D GR> NodeNumTag;70 typedef NodeNumTagIndicator<Digraph> NodeNumTag; 77 71 int nodeNum() const { return _digraph->nodeNum(); } 78 72 79 typedef ArcNumTagIndicator<DGR> ArcNumTag;73 typedef EdgeNumTagIndicator<Digraph> EdgeNumTag; 80 74 int arcNum() const { return _digraph->arcNum(); } 81 75 82 typedef Find ArcTagIndicator<DGR> FindArcTag;83 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const{76 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 77 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) { 84 78 return _digraph->findArc(u, v, prev); 85 79 } … … 88 82 Arc addArc(const Node& u, const Node& v) { return _digraph->addArc(u, v); } 89 83 90 void erase(const Node& n) { _digraph->erase(n); }91 void erase(const Arc& a) { _digraph->erase(a); }92 93 void clear() { _digraph->clear(); }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(); } 94 88 95 89 int id(const Node& n) const { return _digraph->id(n); } … … 102 96 int maxArcId() const { return _digraph->maxArcId(); } 103 97 104 typedef typename ItemSetTraits<D GR, Node>::ItemNotifier NodeNotifier;98 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier; 105 99 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 106 100 107 typedef typename ItemSetTraits<D GR, Arc>::ItemNotifier ArcNotifier;101 typedef typename ItemSetTraits<Digraph, Arc>::ItemNotifier ArcNotifier; 108 102 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); } 109 103 110 template <typename V>111 class NodeMap : public D GR::template NodeMap<V> {112 public: 113 114 typedef typename D GR::template NodeMap<V> Parent;104 template <typename _Value> 105 class NodeMap : public Digraph::template NodeMap<_Value> { 106 public: 107 108 typedef typename Digraph::template NodeMap<_Value> Parent; 115 109 116 110 explicit NodeMap(const Adaptor& adaptor) 117 111 : Parent(*adaptor._digraph) {} 118 112 119 NodeMap(const Adaptor& adaptor, const V& value)113 NodeMap(const Adaptor& adaptor, const _Value& value) 120 114 : Parent(*adaptor._digraph, value) { } 121 115 … … 133 127 }; 134 128 135 template <typename V>136 class ArcMap : public D GR::template ArcMap<V> {137 public: 138 139 typedef typename D GR::template ArcMap<V> Parent;140 141 explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor)129 template <typename _Value> 130 class ArcMap : public Digraph::template ArcMap<_Value> { 131 public: 132 133 typedef typename Digraph::template ArcMap<_Value> Parent; 134 135 explicit ArcMap(const Adaptor& adaptor) 142 136 : Parent(*adaptor._digraph) {} 143 137 144 ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value)138 ArcMap(const Adaptor& adaptor, const _Value& value) 145 139 : Parent(*adaptor._digraph, value) {} 146 140 … … 160 154 }; 161 155 162 template<typename GR>156 template<typename _Graph> 163 157 class GraphAdaptorBase { 164 158 public: 165 typedef GR Graph; 159 typedef _Graph Graph; 160 typedef Graph ParentGraph; 166 161 167 162 protected: 168 G R* _graph;163 Graph* _graph; 169 164 170 165 GraphAdaptorBase() : _graph(0) {} 171 166 172 void initialize(GR& graph) { _graph = &graph; }173 174 public: 175 GraphAdaptorBase(G R& graph) : _graph(&graph) {}176 177 typedef typename G R::Node Node;178 typedef typename G R::Arc Arc;179 typedef typename G R::Edge Edge;167 void setGraph(Graph& graph) { _graph = &graph; } 168 169 public: 170 GraphAdaptorBase(Graph& graph) : _graph(&graph) {} 171 172 typedef typename Graph::Node Node; 173 typedef typename Graph::Arc Arc; 174 typedef typename Graph::Edge Edge; 180 175 181 176 void first(Node& i) const { _graph->first(i); } … … 204 199 int nodeNum() const { return _graph->nodeNum(); } 205 200 206 typedef ArcNumTagIndicator<Graph> ArcNumTag;201 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; 207 202 int arcNum() const { return _graph->arcNum(); } 208 209 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;210 203 int edgeNum() const { return _graph->edgeNum(); } 211 204 212 typedef FindArcTagIndicator<Graph> FindArcTag; 213 Arc findArc(const Node& u, const Node& v, 214 const Arc& prev = INVALID) const { 205 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 206 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) { 215 207 return _graph->findArc(u, v, prev); 216 208 } 217 218 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 219 Edge findEdge(const Node& u, const Node& v, 220 const Edge& prev = INVALID) const { 209 Edge findEdge(const Node& u, const Node& v, const Edge& prev = INVALID) { 221 210 return _graph->findEdge(u, v, prev); 222 211 } … … 245 234 int maxEdgeId() const { return _graph->maxEdgeId(); } 246 235 247 typedef typename ItemSetTraits<G R, Node>::ItemNotifier NodeNotifier;236 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; 248 237 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 249 238 250 typedef typename ItemSetTraits<G R, Arc>::ItemNotifier ArcNotifier;239 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier; 251 240 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 252 241 253 typedef typename ItemSetTraits<G R, Edge>::ItemNotifier EdgeNotifier;242 typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier; 254 243 EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); } 255 244 256 template <typename V>257 class NodeMap : public G R::template NodeMap<V> {258 public: 259 typedef typename G R::template NodeMap<V> Parent;260 explicit NodeMap(const GraphAdaptorBase<G R>& adapter)245 template <typename _Value> 246 class NodeMap : public Graph::template NodeMap<_Value> { 247 public: 248 typedef typename Graph::template NodeMap<_Value> Parent; 249 explicit NodeMap(const GraphAdaptorBase<Graph>& adapter) 261 250 : Parent(*adapter._graph) {} 262 NodeMap(const GraphAdaptorBase<G R>& adapter, const V& value)251 NodeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) 263 252 : Parent(*adapter._graph, value) {} 264 253 … … 276 265 }; 277 266 278 template <typename V>279 class ArcMap : public G R::template ArcMap<V> {280 public: 281 typedef typename G R::template ArcMap<V> Parent;282 explicit ArcMap(const GraphAdaptorBase<G R>& adapter)267 template <typename _Value> 268 class ArcMap : public Graph::template ArcMap<_Value> { 269 public: 270 typedef typename Graph::template ArcMap<_Value> Parent; 271 explicit ArcMap(const GraphAdaptorBase<Graph>& adapter) 283 272 : Parent(*adapter._graph) {} 284 ArcMap(const GraphAdaptorBase<G R>& adapter, const V& value)273 ArcMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) 285 274 : Parent(*adapter._graph, value) {} 286 275 … … 297 286 }; 298 287 299 template <typename V>300 class EdgeMap : public G R::template EdgeMap<V> {301 public: 302 typedef typename G R::template EdgeMap<V> Parent;303 explicit EdgeMap(const GraphAdaptorBase<G R>& adapter)288 template <typename _Value> 289 class EdgeMap : public Graph::template EdgeMap<_Value> { 290 public: 291 typedef typename Graph::template EdgeMap<_Value> Parent; 292 explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter) 304 293 : Parent(*adapter._graph) {} 305 EdgeMap(const GraphAdaptorBase<G R>& adapter, const V& value)294 EdgeMap(const GraphAdaptorBase<Graph>& adapter, const _Value& value) 306 295 : Parent(*adapter._graph, value) {} 307 296 … … 320 309 }; 321 310 322 template <typename DGR>323 class ReverseDigraphBase : public DigraphAdaptorBase< DGR> {324 public: 325 typedef DGRDigraph;326 typedef DigraphAdaptorBase< DGR> Parent;311 template <typename _Digraph> 312 class ReverseDigraphBase : public DigraphAdaptorBase<_Digraph> { 313 public: 314 typedef _Digraph Digraph; 315 typedef DigraphAdaptorBase<_Digraph> Parent; 327 316 protected: 328 317 ReverseDigraphBase() : Parent() { } … … 342 331 Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); } 343 332 344 typedef Find ArcTagIndicator<DGR> FindArcTag;333 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 345 334 Arc findArc(const Node& u, const Node& v, 346 const Arc& prev = INVALID) const{335 const Arc& prev = INVALID) { 347 336 return Parent::findArc(v, u, prev); 348 337 } … … 352 341 /// \ingroup graph_adaptors 353 342 /// 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 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> 374 352 class ReverseDigraph : 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; 353 public DigraphAdaptorExtender<ReverseDigraphBase<_Digraph> > { 354 public: 355 typedef _Digraph Digraph; 356 typedef DigraphAdaptorExtender< 357 ReverseDigraphBase<_Digraph> > Parent; 381 358 protected: 382 359 ReverseDigraph() { } … … 385 362 /// \brief Constructor 386 363 /// 387 /// Creates a reverse digraph adaptor for the given digraph .388 explicit ReverseDigraph(D GR& digraph) {389 Parent:: initialize(digraph);364 /// Creates a reverse digraph adaptor for the given digraph 365 explicit ReverseDigraph(Digraph& digraph) { 366 Parent::setDigraph(digraph); 390 367 } 391 368 }; 392 369 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); 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); 401 376 } 402 377 403 404 template <typename DGR, typename NF, typename AF, bool ch= true>405 class SubDigraphBase : public DigraphAdaptorBase< DGR> {406 public: 407 typedef DGRDigraph;408 typedef NFNodeFilterMap;409 typedef AFArcFilterMap;378 template <typename _Digraph, typename _NodeFilterMap, 379 typename _ArcFilterMap, bool _checked = true> 380 class SubDigraphBase : public DigraphAdaptorBase<_Digraph> { 381 public: 382 typedef _Digraph Digraph; 383 typedef _NodeFilterMap NodeFilterMap; 384 typedef _ArcFilterMap ArcFilterMap; 410 385 411 386 typedef SubDigraphBase Adaptor; 412 typedef DigraphAdaptorBase< DGR> Parent;387 typedef DigraphAdaptorBase<_Digraph> Parent; 413 388 protected: 414 N F* _node_filter;415 A F* _arc_filter;389 NodeFilterMap* _node_filter; 390 ArcFilterMap* _arc_filter; 416 391 SubDigraphBase() 417 392 : Parent(), _node_filter(0), _arc_filter(0) { } 418 393 419 void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { 420 Parent::initialize(digraph); 394 void setNodeFilterMap(NodeFilterMap& node_filter) { 421 395 _node_filter = &node_filter; 422 _arc_filter = &arc_filter; 396 } 397 void setArcFilterMap(ArcFilterMap& arc_filter) { 398 _arc_filter = &arc_filter; 423 399 } 424 400 … … 482 458 } 483 459 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]; } 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]; } 489 468 490 469 typedef False NodeNumTag; 491 typedef False ArcNumTag;492 493 typedef Find ArcTagIndicator<DGR> FindArcTag;470 typedef False EdgeNumTag; 471 472 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 494 473 Arc findArc(const Node& source, const Node& target, 495 const Arc& prev = INVALID) const{474 const Arc& prev = INVALID) { 496 475 if (!(*_node_filter)[source] || !(*_node_filter)[target]) { 497 476 return INVALID; … … 504 483 } 505 484 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>)> { 512 public: 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) {} 485 template <typename _Value> 486 class NodeMap : public SubMapExtender<Adaptor, 487 typename Parent::template NodeMap<_Value> > { 488 public: 489 typedef _Value Value; 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) {} 521 497 522 498 private: … … 527 503 template <typename CMap> 528 504 NodeMap& operator=(const CMap& cmap) { 529 Parent::operator=(cmap);505 MapParent::operator=(cmap); 530 506 return *this; 531 507 } 532 508 }; 533 509 534 template <typename V> 535 class ArcMap 536 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 537 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> { 538 public: 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) {} 510 template <typename _Value> 511 class ArcMap : public SubMapExtender<Adaptor, 512 typename Parent::template ArcMap<_Value> > { 513 public: 514 typedef _Value Value; 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) {} 547 522 548 523 private: … … 553 528 template <typename CMap> 554 529 ArcMap& operator=(const CMap& cmap) { 555 Parent::operator=(cmap);530 MapParent::operator=(cmap); 556 531 return *this; 557 532 } … … 560 535 }; 561 536 562 template <typename DGR, typename NF, typename AF>563 class SubDigraphBase< DGR, NF, AF, false>564 : public DigraphAdaptorBase< DGR> {565 public: 566 typedef DGRDigraph;567 typedef NFNodeFilterMap;568 typedef AFArcFilterMap;537 template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap> 538 class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false> 539 : public DigraphAdaptorBase<_Digraph> { 540 public: 541 typedef _Digraph Digraph; 542 typedef _NodeFilterMap NodeFilterMap; 543 typedef _ArcFilterMap ArcFilterMap; 569 544 570 545 typedef SubDigraphBase Adaptor; 571 546 typedef DigraphAdaptorBase<Digraph> Parent; 572 547 protected: 573 N F* _node_filter;574 A F* _arc_filter;548 NodeFilterMap* _node_filter; 549 ArcFilterMap* _arc_filter; 575 550 SubDigraphBase() 576 551 : Parent(), _node_filter(0), _arc_filter(0) { } 577 552 578 void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { 579 Parent::initialize(digraph); 553 void setNodeFilterMap(NodeFilterMap& node_filter) { 580 554 _node_filter = &node_filter; 581 _arc_filter = &arc_filter; 555 } 556 void setArcFilterMap(ArcFilterMap& arc_filter) { 557 _arc_filter = &arc_filter; 582 558 } 583 559 … … 625 601 } 626 602 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]; } 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]; } 632 611 633 612 typedef False NodeNumTag; 634 typedef False ArcNumTag;635 636 typedef Find ArcTagIndicator<DGR> FindArcTag;613 typedef False EdgeNumTag; 614 615 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 637 616 Arc findArc(const Node& source, const Node& target, 638 const Arc& prev = INVALID) const{617 const Arc& prev = INVALID) { 639 618 if (!(*_node_filter)[source] || !(*_node_filter)[target]) { 640 619 return INVALID; … … 647 626 } 648 627 649 template <typename V> 650 class NodeMap 651 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 652 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> { 653 public: 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) {} 628 template <typename _Value> 629 class NodeMap : public SubMapExtender<Adaptor, 630 typename Parent::template NodeMap<_Value> > { 631 public: 632 typedef _Value Value; 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) {} 662 640 663 641 private: … … 668 646 template <typename CMap> 669 647 NodeMap& operator=(const CMap& cmap) { 670 Parent::operator=(cmap);648 MapParent::operator=(cmap); 671 649 return *this; 672 650 } 673 651 }; 674 652 675 template <typename V> 676 class ArcMap 677 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 678 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> { 679 public: 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) {} 653 template <typename _Value> 654 class ArcMap : public SubMapExtender<Adaptor, 655 typename Parent::template ArcMap<_Value> > { 656 public: 657 typedef _Value Value; 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) {} 688 665 689 666 private: … … 694 671 template <typename CMap> 695 672 ArcMap& operator=(const CMap& cmap) { 696 Parent::operator=(cmap);673 MapParent::operator=(cmap); 697 674 return *this; 698 675 } … … 703 680 /// \ingroup graph_adaptors 704 681 /// 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. 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. 733 700 /// 734 701 /// \see FilterNodes 735 702 /// \see FilterArcs 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; 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; 756 718 757 719 typedef typename Parent::Node Node; … … 764 726 /// \brief Constructor 765 727 /// 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); } 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); } 823 776 824 777 }; 825 778 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); 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); 837 787 } 838 788 839 template<typename D GR, typename NF, typename AF>840 SubDigraph<const D GR, const NF, AF>841 subDigraph(const D GR& digraph,842 const N F& node_filter, AF& arc_filter) {843 return SubDigraph<const D GR, const NF, AF>844 (digraph, n ode_filter, arc_filter);789 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 790 SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap> 791 subDigraph(const Digraph& digraph, 792 const NodeFilterMap& nfm, ArcFilterMap& afm) { 793 return SubDigraph<const Digraph, const NodeFilterMap, ArcFilterMap> 794 (digraph, nfm, afm); 845 795 } 846 796 847 template<typename D GR, typename NF, typename AF>848 SubDigraph<const D GR, NF, const AF>849 subDigraph(const D GR& digraph,850 N F& node_filter, const AF& arc_filter) {851 return SubDigraph<const D GR, NF, const AF>852 (digraph, n ode_filter, arc_filter);797 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 798 SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap> 799 subDigraph(const Digraph& digraph, 800 NodeFilterMap& nfm, const ArcFilterMap& afm) { 801 return SubDigraph<const Digraph, NodeFilterMap, const ArcFilterMap> 802 (digraph, nfm, afm); 853 803 } 854 804 855 template<typename D GR, typename NF, typename AF>856 SubDigraph<const D GR, const NF, const AF>857 subDigraph(const D GR& digraph,858 const N F& node_filter, const AF& arc_filter) {859 return SubDigraph<const D GR, const NF, const AF>860 (digraph, node_filter, arc_filter);805 template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap> 806 SubDigraph<const Digraph, const NodeFilterMap, const ArcFilterMap> 807 subDigraph(const Digraph& digraph, 808 const NodeFilterMap& nfm, const ArcFilterMap& afm) { 809 return SubDigraph<const Digraph, const NodeFilterMap, 810 const ArcFilterMap>(digraph, nfm, afm); 861 811 } 862 812 863 813 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 814 template <typename _Graph, typename NodeFilterMap, 815 typename EdgeFilterMap, bool _checked = true> 816 class SubGraphBase : public GraphAdaptorBase<_Graph> { 817 public: 818 typedef _Graph Graph; 871 819 typedef SubGraphBase Adaptor; 872 typedef GraphAdaptorBase< GR> Parent;820 typedef GraphAdaptorBase<_Graph> Parent; 873 821 protected: 874 822 875 N F* _node_filter;876 E F* _edge_filter;823 NodeFilterMap* _node_filter_map; 824 EdgeFilterMap* _edge_filter_map; 877 825 878 826 SubGraphBase() 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; 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; 885 834 } 886 835 … … 893 842 void first(Node& i) const { 894 843 Parent::first(i); 895 while (i!=INVALID && !(*_node_filter )[i]) Parent::next(i);844 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 896 845 } 897 846 898 847 void first(Arc& i) const { 899 848 Parent::first(i); 900 while (i!=INVALID && (!(*_edge_filter )[i]901 || !(*_node_filter )[Parent::source(i)]902 || !(*_node_filter )[Parent::target(i)]))849 while (i!=INVALID && (!(*_edge_filter_map)[i] 850 || !(*_node_filter_map)[Parent::source(i)] 851 || !(*_node_filter_map)[Parent::target(i)])) 903 852 Parent::next(i); 904 853 } … … 906 855 void first(Edge& i) const { 907 856 Parent::first(i); 908 while (i!=INVALID && (!(*_edge_filter )[i]909 || !(*_node_filter )[Parent::u(i)]910 || !(*_node_filter )[Parent::v(i)]))857 while (i!=INVALID && (!(*_edge_filter_map)[i] 858 || !(*_node_filter_map)[Parent::u(i)] 859 || !(*_node_filter_map)[Parent::v(i)])) 911 860 Parent::next(i); 912 861 } … … 914 863 void firstIn(Arc& i, const Node& n) const { 915 864 Parent::firstIn(i, n); 916 while (i!=INVALID && (!(*_edge_filter )[i]917 || !(*_node_filter )[Parent::source(i)]))865 while (i!=INVALID && (!(*_edge_filter_map)[i] 866 || !(*_node_filter_map)[Parent::source(i)])) 918 867 Parent::nextIn(i); 919 868 } … … 921 870 void firstOut(Arc& i, const Node& n) const { 922 871 Parent::firstOut(i, n); 923 while (i!=INVALID && (!(*_edge_filter )[i]924 || !(*_node_filter )[Parent::target(i)]))872 while (i!=INVALID && (!(*_edge_filter_map)[i] 873 || !(*_node_filter_map)[Parent::target(i)])) 925 874 Parent::nextOut(i); 926 875 } … … 928 877 void firstInc(Edge& i, bool& d, const Node& n) const { 929 878 Parent::firstInc(i, d, n); 930 while (i!=INVALID && (!(*_edge_filter )[i]931 || !(*_node_filter )[Parent::u(i)]932 || !(*_node_filter )[Parent::v(i)]))879 while (i!=INVALID && (!(*_edge_filter_map)[i] 880 || !(*_node_filter_map)[Parent::u(i)] 881 || !(*_node_filter_map)[Parent::v(i)])) 933 882 Parent::nextInc(i, d); 934 883 } … … 936 885 void next(Node& i) const { 937 886 Parent::next(i); 938 while (i!=INVALID && !(*_node_filter )[i]) Parent::next(i);887 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 939 888 } 940 889 941 890 void next(Arc& i) const { 942 891 Parent::next(i); 943 while (i!=INVALID && (!(*_edge_filter )[i]944 || !(*_node_filter )[Parent::source(i)]945 || !(*_node_filter )[Parent::target(i)]))892 while (i!=INVALID && (!(*_edge_filter_map)[i] 893 || !(*_node_filter_map)[Parent::source(i)] 894 || !(*_node_filter_map)[Parent::target(i)])) 946 895 Parent::next(i); 947 896 } … … 949 898 void next(Edge& i) const { 950 899 Parent::next(i); 951 while (i!=INVALID && (!(*_edge_filter )[i]952 || !(*_node_filter )[Parent::u(i)]953 || !(*_node_filter )[Parent::v(i)]))900 while (i!=INVALID && (!(*_edge_filter_map)[i] 901 || !(*_node_filter_map)[Parent::u(i)] 902 || !(*_node_filter_map)[Parent::v(i)])) 954 903 Parent::next(i); 955 904 } … … 957 906 void nextIn(Arc& i) const { 958 907 Parent::nextIn(i); 959 while (i!=INVALID && (!(*_edge_filter )[i]960 || !(*_node_filter )[Parent::source(i)]))908 while (i!=INVALID && (!(*_edge_filter_map)[i] 909 || !(*_node_filter_map)[Parent::source(i)])) 961 910 Parent::nextIn(i); 962 911 } … … 964 913 void nextOut(Arc& i) const { 965 914 Parent::nextOut(i); 966 while (i!=INVALID && (!(*_edge_filter )[i]967 || !(*_node_filter )[Parent::target(i)]))915 while (i!=INVALID && (!(*_edge_filter_map)[i] 916 || !(*_node_filter_map)[Parent::target(i)])) 968 917 Parent::nextOut(i); 969 918 } … … 971 920 void nextInc(Edge& i, bool& d) const { 972 921 Parent::nextInc(i, d); 973 while (i!=INVALID && (!(*_edge_filter )[i]974 || !(*_node_filter )[Parent::u(i)]975 || !(*_node_filter )[Parent::v(i)]))922 while (i!=INVALID && (!(*_edge_filter_map)[i] 923 || !(*_node_filter_map)[Parent::u(i)] 924 || !(*_node_filter_map)[Parent::v(i)])) 976 925 Parent::nextInc(i, d); 977 926 } 978 927 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]; } 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]; } 984 936 985 937 typedef False NodeNumTag; 986 typedef False ArcNumTag;987 938 typedef False EdgeNumTag; 988 939 989 typedef Find ArcTagIndicator<Graph> FindArcTag;940 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 990 941 Arc findArc(const Node& u, const Node& v, 991 const Arc& prev = INVALID) const{992 if (!(*_node_filter )[u] || !(*_node_filter)[v]) {942 const Arc& prev = INVALID) { 943 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { 993 944 return INVALID; 994 945 } 995 946 Arc arc = Parent::findArc(u, v, prev); 996 while (arc != INVALID && !(*_edge_filter )[arc]) {947 while (arc != INVALID && !(*_edge_filter_map)[arc]) { 997 948 arc = Parent::findArc(u, v, arc); 998 949 } 999 950 return arc; 1000 951 } 1001 1002 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;1003 952 Edge findEdge(const Node& u, const Node& v, 1004 const Edge& prev = INVALID) const{1005 if (!(*_node_filter )[u] || !(*_node_filter)[v]) {953 const Edge& prev = INVALID) { 954 if (!(*_node_filter_map)[u] || !(*_node_filter_map)[v]) { 1006 955 return INVALID; 1007 956 } 1008 957 Edge edge = Parent::findEdge(u, v, prev); 1009 while (edge != INVALID && !(*_edge_filter )[edge]) {958 while (edge != INVALID && !(*_edge_filter_map)[edge]) { 1010 959 edge = Parent::findEdge(u, v, edge); 1011 960 } … … 1013 962 } 1014 963 1015 template <typename V> 1016 class NodeMap 1017 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1018 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> { 1019 public: 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) {} 964 template <typename _Value> 965 class NodeMap : public SubMapExtender<Adaptor, 966 typename Parent::template NodeMap<_Value> > { 967 public: 968 typedef _Value Value; 969 typedef SubMapExtender<Adaptor, typename Parent:: 970 template NodeMap<Value> > MapParent; 971 972 NodeMap(const Adaptor& adaptor) 973 : MapParent(adaptor) {} 974 NodeMap(const Adaptor& adaptor, const Value& value) 975 : MapParent(adaptor, value) {} 1028 976 1029 977 private: … … 1034 982 template <typename CMap> 1035 983 NodeMap& operator=(const CMap& cmap) { 1036 Parent::operator=(cmap);984 MapParent::operator=(cmap); 1037 985 return *this; 1038 986 } 1039 987 }; 1040 988 1041 template <typename V> 1042 class ArcMap 1043 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1044 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> { 1045 public: 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) {} 989 template <typename _Value> 990 class ArcMap : public SubMapExtender<Adaptor, 991 typename Parent::template ArcMap<_Value> > { 992 public: 993 typedef _Value Value; 994 typedef SubMapExtender<Adaptor, typename Parent:: 995 template ArcMap<Value> > MapParent; 996 997 ArcMap(const Adaptor& adaptor) 998 : MapParent(adaptor) {} 999 ArcMap(const Adaptor& adaptor, const Value& value) 1000 : MapParent(adaptor, value) {} 1054 1001 1055 1002 private: … … 1060 1007 template <typename CMap> 1061 1008 ArcMap& operator=(const CMap& cmap) { 1062 Parent::operator=(cmap);1009 MapParent::operator=(cmap); 1063 1010 return *this; 1064 1011 } 1065 1012 }; 1066 1013 1067 template <typename V> 1068 class EdgeMap 1069 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1070 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> { 1071 public: 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) {} 1014 template <typename _Value> 1015 class EdgeMap : public SubMapExtender<Adaptor, 1016 typename Parent::template EdgeMap<_Value> > { 1017 public: 1018 typedef _Value Value; 1019 typedef SubMapExtender<Adaptor, typename Parent:: 1020 template EdgeMap<Value> > MapParent; 1021 1022 EdgeMap(const Adaptor& adaptor) 1023 : MapParent(adaptor) {} 1024 1025 EdgeMap(const Adaptor& adaptor, const Value& value) 1026 : MapParent(adaptor, value) {} 1081 1027 1082 1028 private: … … 1087 1033 template <typename CMap> 1088 1034 EdgeMap& operator=(const CMap& cmap) { 1089 Parent::operator=(cmap);1035 MapParent::operator=(cmap); 1090 1036 return *this; 1091 1037 } … … 1094 1040 }; 1095 1041 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 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; 1104 1047 typedef SubGraphBase Adaptor; 1105 typedef GraphAdaptorBase< GR> Parent;1048 typedef GraphAdaptorBase<_Graph> Parent; 1106 1049 protected: 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; 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; 1116 1060 } 1117 1061 … … 1124 1068 void first(Node& i) const { 1125 1069 Parent::first(i); 1126 while (i!=INVALID && !(*_node_filter )[i]) Parent::next(i);1070 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 1127 1071 } 1128 1072 1129 1073 void first(Arc& i) const { 1130 1074 Parent::first(i); 1131 while (i!=INVALID && !(*_edge_filter )[i]) Parent::next(i);1075 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 1132 1076 } 1133 1077 1134 1078 void first(Edge& i) const { 1135 1079 Parent::first(i); 1136 while (i!=INVALID && !(*_edge_filter )[i]) Parent::next(i);1080 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 1137 1081 } 1138 1082 1139 1083 void firstIn(Arc& i, const Node& n) const { 1140 1084 Parent::firstIn(i, n); 1141 while (i!=INVALID && !(*_edge_filter )[i]) Parent::nextIn(i);1085 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); 1142 1086 } 1143 1087 1144 1088 void firstOut(Arc& i, const Node& n) const { 1145 1089 Parent::firstOut(i, n); 1146 while (i!=INVALID && !(*_edge_filter )[i]) Parent::nextOut(i);1090 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); 1147 1091 } 1148 1092 1149 1093 void firstInc(Edge& i, bool& d, const Node& n) const { 1150 1094 Parent::firstInc(i, d, n); 1151 while (i!=INVALID && !(*_edge_filter )[i]) Parent::nextInc(i, d);1095 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextInc(i, d); 1152 1096 } 1153 1097 1154 1098 void next(Node& i) const { 1155 1099 Parent::next(i); 1156 while (i!=INVALID && !(*_node_filter )[i]) Parent::next(i);1100 while (i!=INVALID && !(*_node_filter_map)[i]) Parent::next(i); 1157 1101 } 1158 1102 void next(Arc& i) const { 1159 1103 Parent::next(i); 1160 while (i!=INVALID && !(*_edge_filter )[i]) Parent::next(i);1104 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 1161 1105 } 1162 1106 void next(Edge& i) const { 1163 1107 Parent::next(i); 1164 while (i!=INVALID && !(*_edge_filter )[i]) Parent::next(i);1108 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::next(i); 1165 1109 } 1166 1110 void nextIn(Arc& i) const { 1167 1111 Parent::nextIn(i); 1168 while (i!=INVALID && !(*_edge_filter )[i]) Parent::nextIn(i);1112 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextIn(i); 1169 1113 } 1170 1114 1171 1115 void nextOut(Arc& i) const { 1172 1116 Parent::nextOut(i); 1173 while (i!=INVALID && !(*_edge_filter )[i]) Parent::nextOut(i);1117 while (i!=INVALID && !(*_edge_filter_map)[i]) Parent::nextOut(i); 1174 1118 } 1175 1119 void nextInc(Edge& i, bool& d) const { 1176 1120 Parent::nextInc(i, d); 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]; } 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]; } 1185 1132 1186 1133 typedef False NodeNumTag; 1187 typedef False ArcNumTag;1188 1134 typedef False EdgeNumTag; 1189 1135 1190 typedef Find ArcTagIndicator<Graph> FindArcTag;1136 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 1191 1137 Arc findArc(const Node& u, const Node& v, 1192 const Arc& prev = INVALID) const{1138 const Arc& prev = INVALID) { 1193 1139 Arc arc = Parent::findArc(u, v, prev); 1194 while (arc != INVALID && !(*_edge_filter )[arc]) {1140 while (arc != INVALID && !(*_edge_filter_map)[arc]) { 1195 1141 arc = Parent::findArc(u, v, arc); 1196 1142 } 1197 1143 return arc; 1198 1144 } 1199 1200 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;1201 1145 Edge findEdge(const Node& u, const Node& v, 1202 const Edge& prev = INVALID) const{1146 const Edge& prev = INVALID) { 1203 1147 Edge edge = Parent::findEdge(u, v, prev); 1204 while (edge != INVALID && !(*_edge_filter )[edge]) {1148 while (edge != INVALID && !(*_edge_filter_map)[edge]) { 1205 1149 edge = Parent::findEdge(u, v, edge); 1206 1150 } … … 1208 1152 } 1209 1153 1210 template <typename V> 1211 class NodeMap 1212 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1213 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> { 1214 public: 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) {} 1154 template <typename _Value> 1155 class NodeMap : public SubMapExtender<Adaptor, 1156 typename Parent::template NodeMap<_Value> > { 1157 public: 1158 typedef _Value Value; 1159 typedef SubMapExtender<Adaptor, typename Parent:: 1160 template NodeMap<Value> > MapParent; 1161 1162 NodeMap(const Adaptor& adaptor) 1163 : MapParent(adaptor) {} 1164 NodeMap(const Adaptor& adaptor, const Value& value) 1165 : MapParent(adaptor, value) {} 1223 1166 1224 1167 private: … … 1229 1172 template <typename CMap> 1230 1173 NodeMap& operator=(const CMap& cmap) { 1231 Parent::operator=(cmap);1174 MapParent::operator=(cmap); 1232 1175 return *this; 1233 1176 } 1234 1177 }; 1235 1178 1236 template <typename V> 1237 class ArcMap 1238 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1239 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> { 1240 public: 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) {} 1179 template <typename _Value> 1180 class ArcMap : public SubMapExtender<Adaptor, 1181 typename Parent::template ArcMap<_Value> > { 1182 public: 1183 typedef _Value Value; 1184 typedef SubMapExtender<Adaptor, typename Parent:: 1185 template ArcMap<Value> > MapParent; 1186 1187 ArcMap(const Adaptor& adaptor) 1188 : MapParent(adaptor) {} 1189 ArcMap(const Adaptor& adaptor, const Value& value) 1190 : MapParent(adaptor, value) {} 1249 1191 1250 1192 private: … … 1255 1197 template <typename CMap> 1256 1198 ArcMap& operator=(const CMap& cmap) { 1257 Parent::operator=(cmap);1199 MapParent::operator=(cmap); 1258 1200 return *this; 1259 1201 } 1260 1202 }; 1261 1203 1262 template <typename V> 1263 class EdgeMap 1264 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1265 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> { 1266 public: 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) {} 1204 template <typename _Value> 1205 class EdgeMap : public SubMapExtender<Adaptor, 1206 typename Parent::template EdgeMap<_Value> > { 1207 public: 1208 typedef _Value Value; 1209 typedef SubMapExtender<Adaptor, typename Parent:: 1210 template EdgeMap<Value> > MapParent; 1211 1212 EdgeMap(const Adaptor& adaptor) 1213 : MapParent(adaptor) {} 1214 1215 EdgeMap(const Adaptor& adaptor, const _Value& value) 1216 : MapParent(adaptor, value) {} 1276 1217 1277 1218 private: … … 1282 1223 template <typename CMap> 1283 1224 EdgeMap& operator=(const CMap& cmap) { 1284 Parent::operator=(cmap);1225 MapParent::operator=(cmap); 1285 1226 return *this; 1286 1227 } … … 1291 1232 /// \ingroup graph_adaptors 1292 1233 /// 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. 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. 1322 1253 /// 1323 1254 /// \see FilterNodes 1324 1255 /// \see FilterEdges 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; 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; 1345 1265 1346 1266 typedef typename Parent::Node Node; … … 1353 1273 /// \brief Constructor 1354 1274 /// 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 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); } 1413 1323 }; 1414 1324 1415 /// \brief Returns a read-only SubGraph adaptor 1416 /// 1417 /// This function just returns a read-only \ref SubGraph adaptor. 1325 /// \brief Just gives back a subgraph 1326 /// 1327 /// Just gives back a subgraph 1328 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1329 SubGraph<const Graph, NodeFilterMap, ArcFilterMap> 1330 subGraph(const Graph& graph, NodeFilterMap& nfm, ArcFilterMap& efm) { 1331 return SubGraph<const Graph, NodeFilterMap, ArcFilterMap>(graph, nfm, efm); 1332 } 1333 1334 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1335 SubGraph<const Graph, const NodeFilterMap, ArcFilterMap> 1336 subGraph(const Graph& graph, 1337 const NodeFilterMap& nfm, ArcFilterMap& efm) { 1338 return SubGraph<const Graph, const NodeFilterMap, ArcFilterMap> 1339 (graph, nfm, efm); 1340 } 1341 1342 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1343 SubGraph<const Graph, NodeFilterMap, const ArcFilterMap> 1344 subGraph(const Graph& graph, 1345 NodeFilterMap& nfm, const ArcFilterMap& efm) { 1346 return SubGraph<const Graph, NodeFilterMap, const ArcFilterMap> 1347 (graph, nfm, efm); 1348 } 1349 1350 template<typename Graph, typename NodeFilterMap, typename ArcFilterMap> 1351 SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap> 1352 subGraph(const Graph& graph, 1353 const NodeFilterMap& nfm, const ArcFilterMap& efm) { 1354 return SubGraph<const Graph, const NodeFilterMap, const ArcFilterMap> 1355 (graph, nfm, efm); 1356 } 1357 1418 1358 /// \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); 1425 } 1426 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); 1432 } 1433 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); 1439 } 1440 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); 1446 } 1447 1448 1449 /// \ingroup graph_adaptors 1450 /// 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. 1359 /// 1360 /// \brief An adaptor for hiding nodes from a digraph or a graph. 1361 /// 1362 /// FilterNodes adaptor hides nodes in a graph or a digraph. A bool 1363 /// node map must be specified, which defines the filters for 1364 /// nodes. Just the unfiltered nodes and the arcs or edges incident 1365 /// to unfiltered nodes are shown in the subdigraph or subgraph. The 1366 /// FilterNodes is conform to the \ref concepts::Digraph 1367 /// "Digraph concept" or \ref concepts::Graph "Graph concept" depending 1368 /// on the \c _Digraph template parameter. If the \c _checked 1369 /// parameter is true, then the arc or edges incident to filtered nodes 1370 /// are also filtered out. 1371 /// 1372 /// \tparam _Digraph It must be conform to the \ref 1373 /// concepts::Digraph "Digraph concept" or \ref concepts::Graph 1374 /// "Graph concept". The type can be specified to be const. 1375 /// \tparam _NodeFilterMap A bool valued node map of the the adapted graph. 1376 /// \tparam _checked If the parameter is false then the arc or edge 1377 /// filtering is not checked with respect to node filter. In this 1378 /// case just isolated nodes can be filtered out from the 1379 /// graph. 1476 1380 #ifdef DOXYGEN 1477 template<typename GR, typename NF> 1478 class FilterNodes { 1381 template<typename _Digraph, 1382 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 1383 bool _checked = true> 1479 1384 #else 1480 template<typename GR, 1481 typename NF = typename GR::template NodeMap<bool>, 1385 template<typename _Digraph, 1386 typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 1387 bool _checked = true, 1482 1388 typename Enable = void> 1483 class FilterNodes :1484 public DigraphAdaptorExtender<1485 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,1486 true> > {1487 1389 #endif 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; 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; 1496 1401 1497 1402 typedef typename Parent::Node Node; 1498 1403 1499 1404 protected: 1500 ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map; 1501 1502 FilterNodes() : const_true_map() {} 1405 ConstMap<typename Digraph::Arc, bool> const_true_map; 1406 1407 FilterNodes() : const_true_map(true) { 1408 Parent::setArcFilterMap(const_true_map); 1409 } 1503 1410 1504 1411 public: … … 1506 1413 /// \brief Constructor 1507 1414 /// 1508 /// Creates a subgraph for the given digraph or graph with the1415 /// Creates an adaptor for the given digraph or graph with 1509 1416 /// given node filter map. 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); } 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); } 1541 1443 1542 1444 }; 1543 1445 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; 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; 1557 1456 1558 1457 typedef typename Parent::Node Node; 1559 1458 protected: 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); } 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); } 1575 1477 1576 1478 }; 1577 1479 1578 1480 1579 /// \brief Returns a read-only FilterNodes adaptor 1580 /// 1581 /// This function just returns a read-only \ref FilterNodes adaptor. 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); 1488 } 1489 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); 1494 } 1495 1582 1496 /// \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); 1497 /// 1498 /// \brief An adaptor for hiding arcs from a digraph. 1499 /// 1500 /// FilterArcs adaptor hides arcs in a digraph. A bool arc map must 1501 /// be specified, which defines the filters for arcs. Just the 1502 /// unfiltered arcs are shown in the subdigraph. The FilterArcs is 1503 /// conform to the \ref concepts::Digraph "Digraph concept". 1504 /// 1505 /// \tparam _Digraph It must be conform to the \ref concepts::Digraph 1506 /// "Digraph concept". The type can be specified to be const. 1507 /// \tparam _ArcFilterMap A bool valued arc map of the the adapted 1508 /// graph. 1509 template<typename _Digraph, typename _ArcFilterMap> 1510 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; 1519 1520 typedef typename Parent::Arc Arc; 1521 1522 protected: 1523 ConstMap<typename Digraph::Node, bool> const_true_map; 1524 1525 FilterArcs() : const_true_map(true) { 1526 Parent::setNodeFilterMap(const_true_map); 1527 } 1528 1529 public: 1530 1531 /// \brief Constructor 1532 /// 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); } 1561 1562 }; 1563 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); 1588 1571 } 1589 1572 1590 template<typename GR, typename NF>1591 Filter Nodes<const GR, const NF>1592 filter Nodes(const GR& graph, const NF& node_filter) {1593 return Filter Nodes<const GR, const NF>(graph, node_filter);1573 template<typename Digraph, typename ArcFilterMap> 1574 FilterArcs<const Digraph, const ArcFilterMap> 1575 filterArcs(const Digraph& digraph, const ArcFilterMap& afm) { 1576 return FilterArcs<const Digraph, const ArcFilterMap>(digraph, afm); 1594 1577 } 1595 1578 1596 1579 /// \ingroup graph_adaptors 1597 1580 /// 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> > 1627 class FilterArcs : 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; 1641 1642 typedef typename Parent::Arc Arc; 1643 1581 /// \brief An adaptor for hiding edges from a graph. 1582 /// 1583 /// FilterEdges adaptor hides edges in a digraph. A bool edge map must 1584 /// be specified, which defines the filters for edges. Just the 1585 /// unfiltered edges are shown in the subdigraph. The FilterEdges is 1586 /// conform to the \ref concepts::Graph "Graph concept". 1587 /// 1588 /// \tparam _Graph It must be conform to the \ref concepts::Graph 1589 /// "Graph concept". The type can be specified to be const. 1590 /// \tparam _EdgeFilterMap A bool valued edge map of the the adapted 1591 /// graph. 1592 template<typename _Graph, typename _EdgeFilterMap> 1593 class FilterEdges : 1594 public SubGraph<_Graph, ConstMap<typename _Graph::Node,bool>, 1595 _EdgeFilterMap, false> { 1596 public: 1597 typedef _Graph Graph; 1598 typedef _EdgeFilterMap EdgeFilterMap; 1599 typedef SubGraph<Graph, ConstMap<typename Graph::Node,bool>, 1600 EdgeFilterMap, false> Parent; 1601 typedef typename Parent::Edge Edge; 1644 1602 protected: 1645 ConstMap<typename DGR::Node, Const<bool, true> > const_true_map; 1646 1647 FilterArcs() : const_true_map() {} 1648 1649 public: 1650 1651 /// \brief Constructor 1652 /// 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); } 1685 1686 }; 1687 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); 1697 } 1698 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); 1703 } 1704 1705 /// \ingroup graph_adaptors 1706 /// 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> > 1736 class FilterEdges : 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 1751 typedef typename Parent::Edge Edge; 1752 1753 protected: 1754 ConstMap<typename GR::Node, Const<bool, true> > const_true_map; 1603 ConstMap<typename Graph::Node, bool> const_true_map; 1755 1604 1756 1605 FilterEdges() : const_true_map(true) { … … 1762 1611 /// \brief Constructor 1763 1612 /// 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); } 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); } 1796 1641 1797 1642 }; 1798 1643 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); 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); 1808 1651 } 1809 1652 1810 template<typename G R, typename EF>1811 FilterEdges<const G R, const EF>1812 filterEdges(const G R& graph, const EF& edge_filter) {1813 return FilterEdges<const G R, const EF>(graph, edge_filter);1653 template<typename Graph, typename EdgeFilterMap> 1654 FilterEdges<const Graph, const EdgeFilterMap> 1655 filterEdges(const Graph& graph, const EdgeFilterMap& efm) { 1656 return FilterEdges<const Graph, const EdgeFilterMap>(graph, efm); 1814 1657 } 1815 1658 1816 1817 template <typename DGR> 1659 template <typename _Digraph> 1818 1660 class UndirectorBase { 1819 1661 public: 1820 typedef DGRDigraph;1662 typedef _Digraph Digraph; 1821 1663 typedef UndirectorBase Adaptor; 1822 1664 … … 1853 1695 } 1854 1696 }; 1697 1698 1855 1699 1856 1700 void first(Node& n) const { … … 2002 1846 2003 1847 typedef NodeNumTagIndicator<Digraph> NodeNumTag; 2004 int nodeNum() const { return _digraph->nodeNum(); } 2005 2006 typedef ArcNumTagIndicator<Digraph> ArcNumTag; 1848 int nodeNum() const { return 2 * _digraph->arcNum(); } 1849 typedef EdgeNumTagIndicator<Digraph> EdgeNumTag; 2007 1850 int arcNum() const { return 2 * _digraph->arcNum(); } 2008 2009 typedef ArcNumTag EdgeNumTag;2010 1851 int edgeNum() const { return _digraph->arcNum(); } 2011 1852 2012 typedef Find ArcTagIndicator<Digraph> FindArcTag;1853 typedef FindEdgeTagIndicator<Digraph> FindEdgeTag; 2013 1854 Arc findArc(Node s, Node t, Arc p = INVALID) const { 2014 1855 if (p == INVALID) { … … 2029 1870 } 2030 1871 2031 typedef FindArcTag FindEdgeTag;2032 1872 Edge findEdge(Node s, Node t, Edge p = INVALID) const { 2033 1873 if (s != t) { … … 2037 1877 arc = _digraph->findArc(t, s); 2038 1878 if (arc != INVALID) return arc; 2039 } else if (_digraph->s ource(p) == s) {1879 } else if (_digraph->s(p) == s) { 2040 1880 Edge arc = _digraph->findArc(s, t, p); 2041 1881 if (arc != INVALID) return arc; … … 2054 1894 private: 2055 1895 2056 template <typename V>1896 template <typename _Value> 2057 1897 class ArcMapBase { 2058 1898 private: 2059 1899 2060 typedef typename D GR::template ArcMap<V> MapImpl;1900 typedef typename Digraph::template ArcMap<_Value> MapImpl; 2061 1901 2062 1902 public: … … 2064 1904 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag; 2065 1905 2066 typedef VValue;1906 typedef _Value Value; 2067 1907 typedef Arc Key; 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) : 1908 1909 ArcMapBase(const Adaptor& adaptor) : 2074 1910 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} 2075 1911 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) { 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) { 2081 1916 if (direction(a)) { 2082 _forward.set(a, v alue);1917 _forward.set(a, v); 2083 1918 } else { 2084 _backward.set(a, v alue);1919 _backward.set(a, v); 2085 1920 } 2086 1921 } 2087 1922 2088 ConstReturnValue operator[](const Arc& a) const { 1923 typename MapTraits<MapImpl>::ConstReturnValue 1924 operator[](const Arc& a) const { 2089 1925 if (direction(a)) { 2090 1926 return _forward[a]; … … 2094 1930 } 2095 1931 2096 ReturnValue operator[](const Arc& a) { 1932 typename MapTraits<MapImpl>::ReturnValue 1933 operator[](const Arc& a) { 2097 1934 if (direction(a)) { 2098 1935 return _forward[a]; … … 2110 1947 public: 2111 1948 2112 template <typename V>2113 class NodeMap : public D GR::template NodeMap<V> {2114 public: 2115 2116 typedef VValue;2117 typedef typename D GR::template NodeMap<Value> Parent;2118 2119 explicit NodeMap(const UndirectorBase<DGR>& adaptor)1949 template <typename _Value> 1950 class NodeMap : public Digraph::template NodeMap<_Value> { 1951 public: 1952 1953 typedef _Value Value; 1954 typedef typename Digraph::template NodeMap<Value> Parent; 1955 1956 explicit NodeMap(const Adaptor& adaptor) 2120 1957 : Parent(*adaptor._digraph) {} 2121 1958 2122 NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)1959 NodeMap(const Adaptor& adaptor, const _Value& value) 2123 1960 : Parent(*adaptor._digraph, value) { } 2124 1961 … … 2136 1973 }; 2137 1974 2138 template <typename V>1975 template <typename _Value> 2139 1976 class ArcMap 2140 : public SubMapExtender< UndirectorBase<DGR>, ArcMapBase<V> >1977 : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 2141 1978 { 2142 1979 public: 2143 typedef VValue;2144 typedef SubMapExtender<Adaptor, ArcMapBase<V > > Parent;2145 2146 explicit ArcMap(const UndirectorBase<DGR>& adaptor)1980 typedef _Value Value; 1981 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; 1982 1983 ArcMap(const Adaptor& adaptor) 2147 1984 : Parent(adaptor) {} 2148 1985 2149 ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)1986 ArcMap(const Adaptor& adaptor, const Value& value) 2150 1987 : Parent(adaptor, value) {} 2151 1988 … … 2162 1999 }; 2163 2000 2164 template <typename V>2165 class EdgeMap : public Digraph::template ArcMap< V> {2166 public: 2167 2168 typedef VValue;2169 typedef typename Digraph::template ArcMap<V > Parent;2170 2171 explicit EdgeMap(const UndirectorBase<DGR>& adaptor)2001 template <typename _Value> 2002 class EdgeMap : public Digraph::template ArcMap<_Value> { 2003 public: 2004 2005 typedef _Value Value; 2006 typedef typename Digraph::template ArcMap<Value> Parent; 2007 2008 explicit EdgeMap(const Adaptor& adaptor) 2172 2009 : Parent(*adaptor._digraph) {} 2173 2010 2174 EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)2011 EdgeMap(const Adaptor& adaptor, const Value& value) 2175 2012 : Parent(*adaptor._digraph, value) {} 2176 2013 … … 2188 2025 }; 2189 2026 2190 typedef typename ItemSetTraits<D GR, Node>::ItemNotifier NodeNotifier;2027 typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier; 2191 2028 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 2192 2029 2193 typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;2194 EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }2195 2196 2030 protected: 2197 2031 2198 2032 UndirectorBase() : _digraph(0) {} 2199 2033 2200 D GR* _digraph;2201 2202 void initialize(DGR& digraph) {2034 Digraph* _digraph; 2035 2036 void setDigraph(Digraph& digraph) { 2203 2037 _digraph = &digraph; 2204 2038 } … … 2208 2042 /// \ingroup graph_adaptors 2209 2043 /// 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; 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; 2242 2060 protected: 2243 2061 Undirector() { } … … 2246 2064 /// \brief Constructor 2247 2065 /// 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> 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> 2260 2076 class CombinedArcMap { 2261 2077 public: 2262 2078 2263 /// The key type of the map 2079 typedef _ForwardMap ForwardMap; 2080 typedef _BackwardMap BackwardMap; 2081 2082 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag; 2083 2084 typedef typename ForwardMap::Value Value; 2264 2085 typedef typename Parent::Arc Key; 2265 /// The value type of the map 2266 typedef typename ForwardMap::Value Value; 2267 2268 typedef typename MapTraits<ForwardMap>::ReferenceMapTag ReferenceMapTag; 2269 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 2086 2087 /// \brief Constructor 2088 /// 2275 2089 /// Constructor 2276 2090 CombinedArcMap(ForwardMap& forward, BackwardMap& backward) 2277 2091 : _forward(&forward), _backward(&backward) {} 2278 2092 2279 /// Sets the value associated with the given key. 2093 2094 /// \brief Sets the value associated with a key. 2095 /// 2096 /// Sets the value associated with a key. 2280 2097 void set(const Key& e, const Value& a) { 2281 2098 if (Parent::direction(e)) { … … 2286 2103 } 2287 2104 2288 /// Returns the value associated with the given key. 2289 ConstReturnValue operator[](const Key& e) const { 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 { 2290 2110 if (Parent::direction(e)) { 2291 2111 return (*_forward)[e]; … … 2295 2115 } 2296 2116 2297 /// Returns a reference to the value associated with the given key. 2298 ReturnValue operator[](const Key& e) { 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) { 2299 2122 if (Parent::direction(e)) { 2300 2123 return (*_forward)[e]; … … 2311 2134 }; 2312 2135 2313 /// \brief Returnsa combined arc map2314 /// 2315 /// This function just returns a combined arc map.2136 /// \brief Just gives back a combined arc map 2137 /// 2138 /// Just gives back a combined arc map 2316 2139 template <typename ForwardMap, typename BackwardMap> 2317 2140 static CombinedArcMap<ForwardMap, BackwardMap> … … 2343 2166 }; 2344 2167 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); 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); 2353 2175 } 2354 2176 2355 2356 template <typename GR, typename DM> 2177 template <typename _Graph, typename _DirectionMap> 2357 2178 class OrienterBase { 2358 2179 public: 2359 2180 2360 typedef GRGraph;2361 typedef DMDirectionMap;2362 2363 typedef typename G R::Node Node;2364 typedef typename G R::Edge Arc;2181 typedef _Graph Graph; 2182 typedef _DirectionMap DirectionMap; 2183 2184 typedef typename Graph::Node Node; 2185 typedef typename Graph::Edge Arc; 2365 2186 2366 2187 void reverseArc(const Arc& arc) { … … 2371 2192 void first(Arc& i) const { _graph->first(i); } 2372 2193 void firstIn(Arc& i, const Node& n) const { 2373 bool d = true;2194 bool d; 2374 2195 _graph->firstInc(i, d, n); 2375 2196 while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d); 2376 2197 } 2377 2198 void firstOut(Arc& i, const Node& n ) const { 2378 bool d = true;2199 bool d; 2379 2200 _graph->firstInc(i, d, n); 2380 2201 while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d); … … 2404 2225 int nodeNum() const { return _graph->nodeNum(); } 2405 2226 2406 typedef EdgeNumTagIndicator<Graph> ArcNumTag;2227 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; 2407 2228 int arcNum() const { return _graph->edgeNum(); } 2408 2229 2409 typedef FindEdgeTagIndicator<Graph> Find ArcTag;2230 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; 2410 2231 Arc findArc(const Node& u, const Node& v, 2411 const Arc& prev = INVALID) const { 2412 Arc arc = _graph->findEdge(u, v, prev); 2413 while (arc != INVALID && source(arc) != u) { 2232 const Arc& prev = INVALID) { 2233 Arc arc = prev; 2234 bool d = arc == INVALID ? true : (*_direction)[arc]; 2235 if (d) { 2414 2236 arc = _graph->findEdge(u, v, arc); 2237 while (arc != INVALID && !(*_direction)[arc]) { 2238 _graph->findEdge(u, v, arc); 2239 } 2240 if (arc != INVALID) return arc; 2241 } 2242 _graph->findEdge(v, u, arc); 2243 while (arc != INVALID && (*_direction)[arc]) { 2244 _graph->findEdge(u, v, arc); 2415 2245 } 2416 2246 return arc; … … 2422 2252 2423 2253 Arc addArc(const Node& u, const Node& v) { 2424 Arc arc = _graph->add Edge(u, v);2425 _direction->set(arc, _graph-> u(arc) == u);2254 Arc arc = _graph->addArc(u, v); 2255 _direction->set(arc, _graph->source(arc) == u); 2426 2256 return arc; 2427 2257 } … … 2441 2271 int maxArcId() const { return _graph->maxEdgeId(); } 2442 2272 2443 typedef typename ItemSetTraits<G R, Node>::ItemNotifier NodeNotifier;2273 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier; 2444 2274 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 2445 2275 2446 typedef typename ItemSetTraits<G R, Arc>::ItemNotifier ArcNotifier;2276 typedef typename ItemSetTraits<Graph, Arc>::ItemNotifier ArcNotifier; 2447 2277 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 2448 2278 2449 template <typename V>2450 class NodeMap : public GR::template NodeMap<V> {2451 public: 2452 2453 typedef typename GR::template NodeMap<V> Parent;2454 2455 explicit NodeMap(const OrienterBase <GR, DM>& adapter)2279 template <typename _Value> 2280 class NodeMap : public _Graph::template NodeMap<_Value> { 2281 public: 2282 2283 typedef typename _Graph::template NodeMap<_Value> Parent; 2284 2285 explicit NodeMap(const OrienterBase& adapter) 2456 2286 : Parent(*adapter._graph) {} 2457 2287 2458 NodeMap(const OrienterBase <GR, DM>& adapter, const V& value)2288 NodeMap(const OrienterBase& adapter, const _Value& value) 2459 2289 : Parent(*adapter._graph, value) {} 2460 2290 … … 2472 2302 }; 2473 2303 2474 template <typename V>2475 class ArcMap : public GR::template EdgeMap<V> {2476 public: 2477 2478 typedef typename Graph::template EdgeMap< V> Parent;2479 2480 explicit ArcMap(const OrienterBase <GR, DM>& adapter)2304 template <typename _Value> 2305 class ArcMap : public _Graph::template EdgeMap<_Value> { 2306 public: 2307 2308 typedef typename Graph::template EdgeMap<_Value> Parent; 2309 2310 explicit ArcMap(const OrienterBase& adapter) 2481 2311 : Parent(*adapter._graph) { } 2482 2312 2483 ArcMap(const OrienterBase <GR, DM>& adapter, const V& value)2313 ArcMap(const OrienterBase& adapter, const _Value& value) 2484 2314 : Parent(*adapter._graph, value) { } 2485 2315 … … 2500 2330 protected: 2501 2331 Graph* _graph; 2502 DM* _direction; 2503 2504 void initialize(GR& graph, DM& direction) { 2332 DirectionMap* _direction; 2333 2334 void setDirectionMap(DirectionMap& direction) { 2335 _direction = &direction; 2336 } 2337 2338 void setGraph(Graph& graph) { 2505 2339 _graph = &graph; 2506 _direction = &direction;2507 2340 } 2508 2341 … … 2511 2344 /// \ingroup graph_adaptors 2512 2345 /// 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> > 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> > 2545 2362 class Orienter : 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; 2363 public DigraphAdaptorExtender<OrienterBase<_Graph, DirectionMap> > { 2364 public: 2365 typedef _Graph Graph; 2366 typedef DigraphAdaptorExtender< 2367 OrienterBase<_Graph, DirectionMap> > Parent; 2556 2368 typedef typename Parent::Arc Arc; 2557 2369 protected: … … 2559 2371 public: 2560 2372 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. 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. 2573 2384 void reverseArc(const Arc& a) { 2574 2385 Parent::reverseArc(a); … … 2576 2387 }; 2577 2388 2578 /// \brief Returns a read-only Orienter adaptor 2579 /// 2580 /// This function just returns a read-only \ref Orienter adaptor. 2389 /// \brief Just gives back a Orienter 2390 /// 2391 /// Just gives back a Orienter 2392 template<typename Graph, typename DirectionMap> 2393 Orienter<const Graph, DirectionMap> 2394 orienter(const Graph& graph, DirectionMap& dm) { 2395 return Orienter<const Graph, DirectionMap>(graph, dm); 2396 } 2397 2398 template<typename Graph, typename DirectionMap> 2399 Orienter<const Graph, const DirectionMap> 2400 orienter(const Graph& graph, const DirectionMap& dm) { 2401 return Orienter<const Graph, const DirectionMap>(graph, dm); 2402 } 2403 2404 namespace _adaptor_bits { 2405 2406 template<typename _Digraph, 2407 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 2408 typename _FlowMap = _CapacityMap, 2409 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 2410 class ResForwardFilter { 2411 public: 2412 2413 typedef _Digraph Digraph; 2414 typedef _CapacityMap CapacityMap; 2415 typedef _FlowMap FlowMap; 2416 typedef _Tolerance Tolerance; 2417 2418 typedef typename Digraph::Arc Key; 2419 typedef bool Value; 2420 2421 private: 2422 2423 const CapacityMap* _capacity; 2424 const FlowMap* _flow; 2425 Tolerance _tolerance; 2426 public: 2427 2428 ResForwardFilter(const CapacityMap& capacity, const FlowMap& flow, 2429 const Tolerance& tolerance = Tolerance()) 2430 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2431 2432 bool operator[](const typename Digraph::Arc& a) const { 2433 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]); 2434 } 2435 }; 2436 2437 template<typename _Digraph, 2438 typename _CapacityMap = typename _Digraph::template ArcMap<int>, 2439 typename _FlowMap = _CapacityMap, 2440 typename _Tolerance = Tolerance<typename _CapacityMap::Value> > 2441 class ResBackwardFilter { 2442 public: 2443 2444 typedef _Digraph Digraph; 2445 typedef _CapacityMap CapacityMap; 2446 typedef _FlowMap FlowMap; 2447 typedef _Tolerance Tolerance; 2448 2449 typedef typename Digraph::Arc Key; 2450 typedef bool Value; 2451 2452 private: 2453 2454 const CapacityMap* _capacity; 2455 const FlowMap* _flow; 2456 Tolerance _tolerance; 2457 2458 public: 2459 2460 ResBackwardFilter(const CapacityMap& capacity, const FlowMap& flow, 2461 const Tolerance& tolerance = Tolerance()) 2462 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2463 2464 bool operator[](const typename Digraph::Arc& a) const { 2465 return _tolerance.positive((*_flow)[a]); 2466 } 2467 }; 2468 2469 } 2470 2581 2471 /// \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); 2587 } 2588 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); 2593 } 2594 2595 namespace _adaptor_bits { 2596 2597 template <typename DGR, typename CM, typename FM, typename TL> 2598 class ResForwardFilter { 2599 public: 2600 2601 typedef typename DGR::Arc Key; 2602 typedef bool Value; 2603 2604 private: 2605 2606 const CM* _capacity; 2607 const FM* _flow; 2608 TL _tolerance; 2609 2610 public: 2611 2612 ResForwardFilter(const CM& capacity, const FM& flow, 2613 const TL& tolerance = TL()) 2614 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2615 2616 bool operator[](const typename DGR::Arc& a) const { 2617 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]); 2618 } 2619 }; 2620 2621 template<typename DGR,typename CM, typename FM, typename TL> 2622 class ResBackwardFilter { 2623 public: 2624 2625 typedef typename DGR::Arc Key; 2626 typedef bool Value; 2627 2628 private: 2629 2630 const CM* _capacity; 2631 const FM* _flow; 2632 TL _tolerance; 2633 2634 public: 2635 2636 ResBackwardFilter(const CM& capacity, const FM& flow, 2637 const TL& tolerance = TL()) 2638 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2639 2640 bool operator[](const typename DGR::Arc& a) const { 2641 return _tolerance.positive((*_flow)[a]); 2642 } 2643 }; 2644 2645 } 2646 2647 /// \ingroup graph_adaptors 2648 /// 2649 /// \brief Adaptor class for composing the residual digraph for directed 2472 /// 2473 /// \brief An adaptor for composing the residual graph for directed 2650 2474 /// flow and circulation problems. 2651 2475 /// 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 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> > > 2704 2510 { 2705 2511 public: 2706 2512 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; 2513 typedef _Digraph Digraph; 2514 typedef _CapacityMap CapacityMap; 2515 typedef _FlowMap FlowMap; 2516 typedef _Tolerance Tolerance; 2715 2517 2716 2518 typedef typename CapacityMap::Value Value; 2717 typedef Residual DigraphAdaptor;2519 typedef Residual Adaptor; 2718 2520 2719 2521 protected: … … 2721 2523 typedef Undirector<const Digraph> Undirected; 2722 2524 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; 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; 2730 2530 2731 2531 typedef typename Undirected:: 2732 2733 2734 typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;2532 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter; 2533 2534 typedef FilterArcs<Undirected, ArcFilter> Parent; 2735 2535 2736 2536 const CapacityMap* _capacity; … … 2738 2538 2739 2539 Undirected _graph; 2740 NodeFilter _node_filter;2741 2540 ForwardFilter _forward_filter; 2742 2541 BackwardFilter _backward_filter; … … 2745 2544 public: 2746 2545 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(), 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), 2755 2553 _forward_filter(capacity, flow, tolerance), 2756 2554 _backward_filter(capacity, flow, tolerance), 2757 2555 _arc_filter(_forward_filter, _backward_filter) 2758 2556 { 2759 Parent::initialize(_graph, _node_filter, _arc_filter); 2557 Parent::setDigraph(_graph); 2558 Parent::setArcFilterMap(_arc_filter); 2760 2559 } 2761 2560 2762 2561 typedef typename Parent::Arc Arc; 2763 2562 2764 /// \brief Returns the residual capacity of the givenarc.2765 /// 2766 /// Returns the residual capacity of the givenarc.2563 /// \brief Gives back the residual capacity of the arc. 2564 /// 2565 /// Gives back the residual capacity of the arc. 2767 2566 Value residualCapacity(const Arc& a) const { 2768 2567 if (Undirected::direction(a)) { … … 2773 2572 } 2774 2573 2775 /// \brief Augment s on the given arc in the residual digraph.2776 /// 2777 /// Augment s on the given arc in the residual digraph. It increases2778 /// or decrease s the flow value on the original arc according to the2779 /// directionof the residual arc.2574 /// \brief Augment on the given arc in the residual graph. 2575 /// 2576 /// Augment on the given arc in the residual graph. It increase 2577 /// or decrease the flow on the original arc depend on the direction 2578 /// of the residual arc. 2780 2579 void augment(const Arc& a, const Value& v) const { 2781 2580 if (Undirected::direction(a)) { … … 2786 2585 } 2787 2586 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. 2587 /// \brief Returns the direction of the arc. 2588 /// 2589 /// Returns true when the arc is same oriented as the original arc. 2792 2590 static bool forward(const Arc& a) { 2793 2591 return Undirected::direction(a); 2794 2592 } 2795 2593 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. 2594 /// \brief Returns the direction of the arc. 2595 /// 2596 /// Returns true when the arc is opposite oriented as the original arc. 2800 2597 static bool backward(const Arc& a) { 2801 2598 return !Undirected::direction(a); 2802 2599 } 2803 2600 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. 2601 /// \brief Gives back the forward oriented residual arc. 2602 /// 2603 /// Gives back the forward oriented residual arc. 2808 2604 static Arc forward(const typename Digraph::Arc& a) { 2809 2605 return Undirected::direct(a, true); 2810 2606 } 2811 2607 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. 2608 /// \brief Gives back the backward oriented residual arc. 2609 /// 2610 /// Gives back the backward oriented residual arc. 2816 2611 static Arc backward(const typename Digraph::Arc& a) { 2817 2612 return Undirected::direct(a, false); … … 2820 2615 /// \brief Residual capacity map. 2821 2616 /// 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. 2617 /// In generic residual graph the residual capacity can be obtained 2618 /// as a map. 2825 2619 class ResidualCapacity { 2826 2620 protected: 2827 2621 const Adaptor* _adaptor; 2828 2622 public: 2829 /// The key type of the map2623 /// The Key type 2830 2624 typedef Arc Key; 2831 /// The value type of the map2832 typedef typename CapacityMap::Value Value;2625 /// The Value type 2626 typedef typename _CapacityMap::Value Value; 2833 2627 2834 2628 /// Constructor 2835 ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 2836 : _adaptor(&adaptor) {} 2837 2838 /// Returns the value associated with the given residual arc 2629 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {} 2630 2631 /// \e 2839 2632 Value operator[](const Arc& a) const { 2840 2633 return _adaptor->residualCapacity(a); … … 2843 2636 }; 2844 2637 2845 /// \brief Returns a residual capacity map2846 ///2847 /// This function just returns a residual capacity map.2848 ResidualCapacity residualCapacity() const {2849 return ResidualCapacity(*this);2850 }2851 2852 2638 }; 2853 2639 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> 2640 template <typename _Digraph> 2867 2641 class SplitNodesBase { 2868 2642 public: 2869 2643 2870 typedef DGRDigraph;2871 typedef DigraphAdaptorBase<const DGR> Parent;2644 typedef _Digraph Digraph; 2645 typedef DigraphAdaptorBase<const _Digraph> Parent; 2872 2646 typedef SplitNodesBase Adaptor; 2873 2647 2874 typedef typename D GR::Node DigraphNode;2875 typedef typename D GR::Arc DigraphArc;2648 typedef typename Digraph::Node DigraphNode; 2649 typedef typename Digraph::Arc DigraphArc; 2876 2650 2877 2651 class Node; … … 3111 2885 3112 2886 typedef True NodeNumTag; 2887 3113 2888 int nodeNum() const { 3114 2889 return 2 * countNodes(*_digraph); 3115 2890 } 3116 2891 3117 typedef True ArcNumTag;2892 typedef True EdgeNumTag; 3118 2893 int arcNum() const { 3119 2894 return countArcs(*_digraph) + countNodes(*_digraph); 3120 2895 } 3121 2896 3122 typedef True Find ArcTag;2897 typedef True FindEdgeTag; 3123 2898 Arc findArc(const Node& u, const Node& v, 3124 2899 const Arc& prev = INVALID) const { 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); 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 } 3129 2906 } 3130 } 3131 else if (outNode(u) && inNode(v)) { 3132 return Arc(::lemon::findArc(*_digraph, u, v, prev)); 2907 } else { 2908 if (inNode(v)) { 2909 return Arc(::lemon::findArc(*_digraph, u, v, prev)); 2910 } 3133 2911 } 3134 2912 return INVALID; … … 3137 2915 private: 3138 2916 3139 template <typename V>2917 template <typename _Value> 3140 2918 class NodeMapBase 3141 : public MapTraits<typename Parent::template NodeMap< V> > {3142 typedef typename Parent::template NodeMap< V> NodeImpl;2919 : public MapTraits<typename Parent::template NodeMap<_Value> > { 2920 typedef typename Parent::template NodeMap<_Value> NodeImpl; 3143 2921 public: 3144 2922 typedef Node Key; 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) 2923 typedef _Value Value; 2924 2925 NodeMapBase(const Adaptor& adaptor) 3153 2926 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {} 3154 NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)2927 NodeMapBase(const Adaptor& adaptor, const Value& value) 3155 2928 : _in_map(*adaptor._digraph, value), 3156 2929 _out_map(*adaptor._digraph, value) {} 3157 2930 3158 void set(const Node& key, const V & val) {3159 if ( SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); }2931 void set(const Node& key, const Value& val) { 2932 if (Adaptor::inNode(key)) { _in_map.set(key, val); } 3160 2933 else {_out_map.set(key, val); } 3161 2934 } 3162 2935 3163 ReturnValue operator[](const Node& key) { 3164 if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; } 2936 typename MapTraits<NodeImpl>::ReturnValue 2937 operator[](const Node& key) { 2938 if (Adaptor::inNode(key)) { return _in_map[key]; } 3165 2939 else { return _out_map[key]; } 3166 2940 } 3167 2941 3168 ConstReturnValue operator[](const Node& key) const { 2942 typename MapTraits<NodeImpl>::ConstReturnValue 2943 operator[](const Node& key) const { 3169 2944 if (Adaptor::inNode(key)) { return _in_map[key]; } 3170 2945 else { return _out_map[key]; } … … 3175 2950 }; 3176 2951 3177 template <typename V>2952 template <typename _Value> 3178 2953 class ArcMapBase 3179 : public MapTraits<typename Parent::template ArcMap< V> > {3180 typedef typename Parent::template ArcMap< V> ArcImpl;3181 typedef typename Parent::template NodeMap< V> NodeImpl;2954 : public MapTraits<typename Parent::template ArcMap<_Value> > { 2955 typedef typename Parent::template ArcMap<_Value> ArcImpl; 2956 typedef typename Parent::template NodeMap<_Value> NodeImpl; 3182 2957 public: 3183 2958 typedef Arc Key; 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) 2959 typedef _Value Value; 2960 2961 ArcMapBase(const Adaptor& adaptor) 3192 2962 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {} 3193 ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value)2963 ArcMapBase(const Adaptor& adaptor, const Value& value) 3194 2964 : _arc_map(*adaptor._digraph, value), 3195 2965 _node_map(*adaptor._digraph, value) {} 3196 2966 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);2967 void set(const Arc& key, const Value& val) { 2968 if (Adaptor::origArc(key)) { 2969 _arc_map.set(key._item.first(), val); 3200 2970 } else { 3201 _node_map.set( static_cast<const DigraphNode&>(key), val);2971 _node_map.set(key._item.second(), val); 3202 2972 } 3203 2973 } 3204 2974 3205 ReturnValue operator[](const Arc& key) { 3206 if (SplitNodesBase<DGR>::origArc(key)) { 3207 return _arc_map[static_cast<const DigraphArc&>(key)]; 2975 typename MapTraits<ArcImpl>::ReturnValue 2976 operator[](const Arc& key) { 2977 if (Adaptor::origArc(key)) { 2978 return _arc_map[key._item.first()]; 3208 2979 } else { 3209 return _node_map[ static_cast<const DigraphNode&>(key)];2980 return _node_map[key._item.second()]; 3210 2981 } 3211 2982 } 3212 2983 3213 ConstReturnValue operator[](const Arc& key) const { 3214 if (SplitNodesBase<DGR>::origArc(key)) { 3215 return _arc_map[static_cast<const DigraphArc&>(key)]; 2984 typename MapTraits<ArcImpl>::ConstReturnValue 2985 operator[](const Arc& key) const { 2986 if (Adaptor::origArc(key)) { 2987 return _arc_map[key._item.first()]; 3216 2988 } else { 3217 return _node_map[ static_cast<const DigraphNode&>(key)];2989 return _node_map[key._item.second()]; 3218 2990 } 3219 2991 } … … 3226 2998 public: 3227 2999 3228 template <typename V>3000 template <typename _Value> 3229 3001 class NodeMap 3230 : public SubMapExtender< SplitNodesBase<DGR>, NodeMapBase<V> >3002 : public SubMapExtender<Adaptor, NodeMapBase<_Value> > 3231 3003 { 3232 3004 public: 3233 typedef VValue;3234 typedef SubMapExtender< SplitNodesBase<DGR>, NodeMapBase<Value> > Parent;3235 3236 NodeMap(const SplitNodesBase<DGR>& adaptor)3005 typedef _Value Value; 3006 typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent; 3007 3008 NodeMap(const Adaptor& adaptor) 3237 3009 : Parent(adaptor) {} 3238 3010 3239 NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value)3011 NodeMap(const Adaptor& adaptor, const Value& value) 3240 3012 : Parent(adaptor, value) {} 3241 3013 … … 3252 3024 }; 3253 3025 3254 template <typename V>3026 template <typename _Value> 3255 3027 class ArcMap 3256 : public SubMapExtender< SplitNodesBase<DGR>, ArcMapBase<V> >3028 : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 3257 3029 { 3258 3030 public: 3259 typedef VValue;3260 typedef SubMapExtender< SplitNodesBase<DGR>, ArcMapBase<Value> > Parent;3261 3262 ArcMap(const SplitNodesBase<DGR>& adaptor)3031 typedef _Value Value; 3032 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; 3033 3034 ArcMap(const Adaptor& adaptor) 3263 3035 : Parent(adaptor) {} 3264 3036 3265 ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value)3037 ArcMap(const Adaptor& adaptor, const Value& value) 3266 3038 : Parent(adaptor, value) {} 3267 3039 … … 3282 3054 SplitNodesBase() : _digraph(0) {} 3283 3055 3284 D GR* _digraph;3285 3286 void initialize(Digraph& digraph) {3056 Digraph* _digraph; 3057 3058 void setDigraph(Digraph& digraph) { 3287 3059 _digraph = &digraph; 3288 3060 } … … 3292 3064 /// \ingroup graph_adaptors 3293 3065 /// 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 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> 3323 3086 class SplitNodes 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; 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; 3332 3094 3333 3095 typedef typename Parent::Node Node; 3334 3096 typedef typename Parent::Arc Arc; 3335 3097 3336 /// \brief Constructor 3098 /// \brief Constructor of the adaptor. 3337 3099 /// 3338 3100 /// Constructor of the adaptor. 3339 SplitNodes( const DGR& g) {3340 Parent:: initialize(g);3341 } 3342 3343 /// \brief Returns \c true if the given node is anin-node.3344 /// 3345 /// Returns \c true if the given node is anin-node.3101 SplitNodes(Digraph& g) { 3102 Parent::setDigraph(g); 3103 } 3104 3105 /// \brief Returns true when the node is in-node. 3106 /// 3107 /// Returns true when the node is in-node. 3346 3108 static bool inNode(const Node& n) { 3347 3109 return Parent::inNode(n); 3348 3110 } 3349 3111 3350 /// \brief Returns \c true if the given node is anout-node.3351 /// 3352 /// Returns \c true if the given node is anout-node.3112 /// \brief Returns true when the node is out-node. 3113 /// 3114 /// Returns true when the node is out-node. 3353 3115 static bool outNode(const Node& n) { 3354 3116 return Parent::outNode(n); 3355 3117 } 3356 3118 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. 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. 3361 3122 static bool origArc(const Arc& a) { 3362 3123 return Parent::origArc(a); 3363 3124 } 3364 3125 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. 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. 3369 3129 static bool bindArc(const Arc& a) { 3370 3130 return Parent::bindArc(a); 3371 3131 } 3372 3132 3373 /// \brief Returns the in-node created from the given originalnode.3374 /// 3375 /// Returns the in-node created from the given originalnode.3133 /// \brief Gives back the in-node created from the \c node. 3134 /// 3135 /// Gives back the in-node created from the \c node. 3376 3136 static Node inNode(const DigraphNode& n) { 3377 3137 return Parent::inNode(n); 3378 3138 } 3379 3139 3380 /// \brief Returns the out-node created from the given originalnode.3381 /// 3382 /// Returns the out-node created from the given originalnode.3140 /// \brief Gives back the out-node created from the \c node. 3141 /// 3142 /// Gives back the out-node created from the \c node. 3383 3143 static Node outNode(const DigraphNode& n) { 3384 3144 return Parent::outNode(n); 3385 3145 } 3386 3146 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. 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. 3393 3150 static Arc arc(const DigraphNode& n) { 3394 3151 return Parent::arc(n); 3395 3152 } 3396 3153 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. 3154 /// \brief Gives back the arc of the original arc. 3155 /// 3156 /// Gives back the arc of the original arc. 3401 3157 static Arc arc(const DigraphArc& a) { 3402 3158 return Parent::arc(a); 3403 3159 } 3404 3160 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). 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. 3411 3165 template <typename InNodeMap, typename OutNodeMap> 3412 3166 class CombinedNodeMap { 3413 3167 public: 3414 3168 3415 /// The key type of the map3416 3169 typedef Node Key; 3417 /// The value type of the map3418 3170 typedef typename InNodeMap::Value Value; 3419 3171 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 3172 /// \brief Constructor 3173 /// 3174 /// Constructor. 3427 3175 CombinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) 3428 3176 : _in_map(in_map), _out_map(out_map) {} 3429 3177 3430 /// Returns the value associated with the given key. 3431 Value operator[](const Key& key) const { 3432 if (SplitNodesBase<const DGR>::inNode(key)) { 3178 /// \brief The subscript operator. 3179 /// 3180 /// The subscript operator. 3181 Value& operator[](const Key& key) { 3182 if (Parent::inNode(key)) { 3433 3183 return _in_map[key]; 3434 3184 } else { … … 3437 3187 } 3438 3188 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)) { 3189 /// \brief The const subscript operator. 3190 /// 3191 /// The const subscript operator. 3192 Value operator[](const Key& key) const { 3193 if (Parent::inNode(key)) { 3442 3194 return _in_map[key]; 3443 3195 } else { … … 3446 3198 } 3447 3199 3448 /// Sets the value associated with the given key. 3200 /// \brief The setter function of the map. 3201 /// 3202 /// The setter function of the map. 3449 3203 void set(const Key& key, const Value& value) { 3450 if ( SplitNodesBase<const DGR>::inNode(key)) {3204 if (Parent::inNode(key)) { 3451 3205 _in_map.set(key, value); 3452 3206 } else { … … 3463 3217 3464 3218 3465 /// \brief Returnsa combined node map3466 /// 3467 /// This function just returns a combined node map.3219 /// \brief Just gives back a combined node map 3220 /// 3221 /// Just gives back a combined node map 3468 3222 template <typename InNodeMap, typename OutNodeMap> 3469 3223 static CombinedNodeMap<InNodeMap, OutNodeMap> … … 3491 3245 } 3492 3246 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> 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> 3501 3252 class CombinedArcMap { 3502 3253 public: 3503 3254 3504 /// The key type of the map3505 3255 typedef Arc Key; 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) 3256 typedef typename DigraphArcMap::Value Value; 3257 3258 /// \brief Constructor 3259 /// 3260 /// Constructor. 3261 CombinedArcMap(DigraphArcMap& arc_map, DigraphNodeMap& node_map) 3517 3262 : _arc_map(arc_map), _node_map(node_map) {} 3518 3263 3519 /// Returns the value associated with the given key. 3264 /// \brief The subscript operator. 3265 /// 3266 /// The subscript operator. 3267 void set(const Arc& arc, const Value& val) { 3268 if (Parent::origArc(arc)) { 3269 _arc_map.set(arc, val); 3270 } else { 3271 _node_map.set(arc, val); 3272 } 3273 } 3274 3275 /// \brief The const subscript operator. 3276 /// 3277 /// The const subscript operator. 3520 3278 Value operator[](const Key& arc) const { 3521 if ( SplitNodesBase<const DGR>::origArc(arc)) {3279 if (Parent::origArc(arc)) { 3522 3280 return _arc_map[arc]; 3523 3281 } else { … … 3526 3284 } 3527 3285 3528 /// Returns a reference to the value associated with the given key. 3286 /// \brief The const subscript operator. 3287 /// 3288 /// The const subscript operator. 3529 3289 Value& operator[](const Key& arc) { 3530 if ( SplitNodesBase<const DGR>::origArc(arc)) {3290 if (Parent::origArc(arc)) { 3531 3291 return _arc_map[arc]; 3532 3292 } else { … … 3535 3295 } 3536 3296 3537 /// Sets the value associated with the given key.3538 void set(const Arc& arc, const Value& val) {3539 if (SplitNodesBase<const DGR>::origArc(arc)) {3540 _arc_map.set(arc, val);3541 } else {3542 _node_map.set(arc, val);3543 }3544 }3545 3546 3297 private: 3547 ArcMap& _arc_map;3548 NodeMap& _node_map;3298 DigraphArcMap& _arc_map; 3299 DigraphNodeMap& _node_map; 3549 3300 }; 3550 3301 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); 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); 3576 3331 } 3577 3332 3578 3333 }; 3579 3334 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); 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); 3589 3342 } 3590 3343 3591 #undef LEMON_SCOPE_FIX3592 3344 3593 3345 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.