Changeset 512:9b9ffe7d9b75 in lemon1.2 for lemon/adaptors.h
 Timestamp:
 02/13/09 13:29:28 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/adaptors.h
r464 r512 37 37 namespace lemon { 38 38 39 template<typename _Digraph> 39 #ifdef _MSC_VER 40 #define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED 41 #else 42 #define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED 43 #endif 44 45 template<typename DGR> 40 46 class DigraphAdaptorBase { 41 47 public: 42 typedef _DigraphDigraph;48 typedef DGR Digraph; 43 49 typedef DigraphAdaptorBase Adaptor; 44 typedef Digraph ParentDigraph;45 50 46 51 protected: 47 D igraph* _digraph;52 DGR* _digraph; 48 53 DigraphAdaptorBase() : _digraph(0) { } 49 void setDigraph(Digraph& digraph) { _digraph = &digraph; }50 51 public: 52 DigraphAdaptorBase(D igraph& digraph) : _digraph(&digraph) { }53 54 typedef typename D igraph::Node Node;55 typedef typename D igraph::Arc Arc;54 void initialize(DGR& digraph) { _digraph = &digraph; } 55 56 public: 57 DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { } 58 59 typedef typename DGR::Node Node; 60 typedef typename DGR::Arc Arc; 56 61 57 62 void first(Node& i) const { _digraph>first(i); } … … 68 73 Node target(const Arc& a) const { return _digraph>target(a); } 69 74 70 typedef NodeNumTagIndicator<D igraph> NodeNumTag;75 typedef NodeNumTagIndicator<DGR> NodeNumTag; 71 76 int nodeNum() const { return _digraph>nodeNum(); } 72 77 73 typedef ArcNumTagIndicator<D igraph> ArcNumTag;78 typedef ArcNumTagIndicator<DGR> ArcNumTag; 74 79 int arcNum() const { return _digraph>arcNum(); } 75 80 76 typedef FindArcTagIndicator<D igraph> FindArcTag;81 typedef FindArcTagIndicator<DGR> FindArcTag; 77 82 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const { 78 83 return _digraph>findArc(u, v, prev); … … 96 101 int maxArcId() const { return _digraph>maxArcId(); } 97 102 98 typedef typename ItemSetTraits<D igraph, Node>::ItemNotifier NodeNotifier;103 typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier; 99 104 NodeNotifier& notifier(Node) const { return _digraph>notifier(Node()); } 100 105 101 typedef typename ItemSetTraits<D igraph, Arc>::ItemNotifier ArcNotifier;106 typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier; 102 107 ArcNotifier& notifier(Arc) const { return _digraph>notifier(Arc()); } 103 108 104 template <typename _Value>105 class NodeMap : public D igraph::template NodeMap<_Value> {109 template <typename V> 110 class NodeMap : public DGR::template NodeMap<V> { 106 111 public: 107 112 108 typedef typename D igraph::template NodeMap<_Value> Parent;113 typedef typename DGR::template NodeMap<V> Parent; 109 114 110 115 explicit NodeMap(const Adaptor& adaptor) 111 116 : Parent(*adaptor._digraph) {} 112 117 113 NodeMap(const Adaptor& adaptor, const _Value& value)118 NodeMap(const Adaptor& adaptor, const V& value) 114 119 : Parent(*adaptor._digraph, value) { } 115 120 … … 127 132 }; 128 133 129 template <typename _Value>130 class ArcMap : public D igraph::template ArcMap<_Value> {134 template <typename V> 135 class ArcMap : public DGR::template ArcMap<V> { 131 136 public: 132 137 133 typedef typename D igraph::template ArcMap<_Value> Parent;134 135 explicit ArcMap(const Adaptor& adaptor)138 typedef typename DGR::template ArcMap<V> Parent; 139 140 explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor) 136 141 : Parent(*adaptor._digraph) {} 137 142 138 ArcMap(const Adaptor& adaptor, const _Value& value)143 ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value) 139 144 : Parent(*adaptor._digraph, value) {} 140 145 … … 154 159 }; 155 160 156 template<typename _Graph>161 template<typename GR> 157 162 class GraphAdaptorBase { 158 163 public: 159 typedef _Graph Graph; 160 typedef Graph ParentGraph; 164 typedef GR Graph; 161 165 162 166 protected: 163 G raph* _graph;167 GR* _graph; 164 168 165 169 GraphAdaptorBase() : _graph(0) {} 166 170 167 void setGraph(Graph& graph) { _graph = &graph; }168 169 public: 170 GraphAdaptorBase(G raph& graph) : _graph(&graph) {}171 172 typedef typename G raph::Node Node;173 typedef typename G raph::Arc Arc;174 typedef typename G raph::Edge Edge;171 void initialize(GR& graph) { _graph = &graph; } 172 173 public: 174 GraphAdaptorBase(GR& graph) : _graph(&graph) {} 175 176 typedef typename GR::Node Node; 177 typedef typename GR::Arc Arc; 178 typedef typename GR::Edge Edge; 175 179 176 180 void first(Node& i) const { _graph>first(i); } … … 240 244 int maxEdgeId() const { return _graph>maxEdgeId(); } 241 245 242 typedef typename ItemSetTraits<G raph, Node>::ItemNotifier NodeNotifier;246 typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier; 243 247 NodeNotifier& notifier(Node) const { return _graph>notifier(Node()); } 244 248 245 typedef typename ItemSetTraits<G raph, Arc>::ItemNotifier ArcNotifier;249 typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier; 246 250 ArcNotifier& notifier(Arc) const { return _graph>notifier(Arc()); } 247 251 248 typedef typename ItemSetTraits<G raph, Edge>::ItemNotifier EdgeNotifier;252 typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier; 249 253 EdgeNotifier& notifier(Edge) const { return _graph>notifier(Edge()); } 250 254 251 template <typename _Value>252 class NodeMap : public G raph::template NodeMap<_Value> {255 template <typename V> 256 class NodeMap : public GR::template NodeMap<V> { 253 257 public: 254 typedef typename G raph::template NodeMap<_Value> Parent;255 explicit NodeMap(const GraphAdaptorBase<G raph>& adapter)258 typedef typename GR::template NodeMap<V> Parent; 259 explicit NodeMap(const GraphAdaptorBase<GR>& adapter) 256 260 : Parent(*adapter._graph) {} 257 NodeMap(const GraphAdaptorBase<G raph>& adapter, const _Value& value)261 NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value) 258 262 : Parent(*adapter._graph, value) {} 259 263 … … 271 275 }; 272 276 273 template <typename _Value>274 class ArcMap : public G raph::template ArcMap<_Value> {277 template <typename V> 278 class ArcMap : public GR::template ArcMap<V> { 275 279 public: 276 typedef typename G raph::template ArcMap<_Value> Parent;277 explicit ArcMap(const GraphAdaptorBase<G raph>& adapter)280 typedef typename GR::template ArcMap<V> Parent; 281 explicit ArcMap(const GraphAdaptorBase<GR>& adapter) 278 282 : Parent(*adapter._graph) {} 279 ArcMap(const GraphAdaptorBase<G raph>& adapter, const _Value& value)283 ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value) 280 284 : Parent(*adapter._graph, value) {} 281 285 … … 292 296 }; 293 297 294 template <typename _Value>295 class EdgeMap : public G raph::template EdgeMap<_Value> {298 template <typename V> 299 class EdgeMap : public GR::template EdgeMap<V> { 296 300 public: 297 typedef typename G raph::template EdgeMap<_Value> Parent;298 explicit EdgeMap(const GraphAdaptorBase<G raph>& adapter)301 typedef typename GR::template EdgeMap<V> Parent; 302 explicit EdgeMap(const GraphAdaptorBase<GR>& adapter) 299 303 : Parent(*adapter._graph) {} 300 EdgeMap(const GraphAdaptorBase<G raph>& adapter, const _Value& value)304 EdgeMap(const GraphAdaptorBase<GR>& adapter, const V& value) 301 305 : Parent(*adapter._graph, value) {} 302 306 … … 315 319 }; 316 320 317 template <typename _Digraph>318 class ReverseDigraphBase : public DigraphAdaptorBase< _Digraph> {319 public: 320 typedef _DigraphDigraph;321 typedef DigraphAdaptorBase< _Digraph> Parent;321 template <typename DGR> 322 class ReverseDigraphBase : public DigraphAdaptorBase<DGR> { 323 public: 324 typedef DGR Digraph; 325 typedef DigraphAdaptorBase<DGR> Parent; 322 326 protected: 323 327 ReverseDigraphBase() : Parent() { } … … 337 341 Arc addArc(const Node& u, const Node& v) { return Parent::addArc(v, u); } 338 342 339 typedef FindArcTagIndicator<D igraph> FindArcTag;343 typedef FindArcTagIndicator<DGR> FindArcTag; 340 344 Arc findArc(const Node& u, const Node& v, 341 345 const Arc& prev = INVALID) const { … … 357 361 /// parameter is set to be \c const. 358 362 /// 359 /// \tparam GR The type of the adapted digraph.363 /// \tparam DGR The type of the adapted digraph. 360 364 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 361 365 /// It can also be specified to be \c const. … … 363 367 /// \note The \c Node and \c Arc types of this adaptor and the adapted 364 368 /// digraph are convertible to each other. 365 template<typename GR>369 template<typename DGR> 366 370 #ifdef DOXYGEN 367 371 class ReverseDigraph { 368 372 #else 369 373 class ReverseDigraph : 370 public DigraphAdaptorExtender<ReverseDigraphBase< GR> > {374 public DigraphAdaptorExtender<ReverseDigraphBase<DGR> > { 371 375 #endif 372 376 public: 373 377 /// The type of the adapted digraph. 374 typedef GR Digraph;375 typedef DigraphAdaptorExtender<ReverseDigraphBase< GR> > Parent;378 typedef DGR Digraph; 379 typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent; 376 380 protected: 377 381 ReverseDigraph() { } … … 381 385 /// 382 386 /// Creates a reverse digraph adaptor for the given digraph. 383 explicit ReverseDigraph(D igraph& digraph) {384 Parent:: setDigraph(digraph);387 explicit ReverseDigraph(DGR& digraph) { 388 Parent::initialize(digraph); 385 389 } 386 390 }; … … 391 395 /// \ingroup graph_adaptors 392 396 /// \relates ReverseDigraph 393 template<typename GR>394 ReverseDigraph<const GR> reverseDigraph(constGR& digraph) {395 return ReverseDigraph<const GR>(digraph);397 template<typename DGR> 398 ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) { 399 return ReverseDigraph<const DGR>(digraph); 396 400 } 397 401 398 402 399 template <typename _Digraph, typename _NodeFilterMap, 400 typename _ArcFilterMap, bool _checked = true> 401 class SubDigraphBase : public DigraphAdaptorBase<_Digraph> { 402 public: 403 typedef _Digraph Digraph; 404 typedef _NodeFilterMap NodeFilterMap; 405 typedef _ArcFilterMap ArcFilterMap; 403 template <typename DGR, typename NF, typename AF, bool ch = true> 404 class SubDigraphBase : public DigraphAdaptorBase<DGR> { 405 public: 406 typedef DGR Digraph; 407 typedef NF NodeFilterMap; 408 typedef AF ArcFilterMap; 406 409 407 410 typedef SubDigraphBase Adaptor; 408 typedef DigraphAdaptorBase< _Digraph> Parent;411 typedef DigraphAdaptorBase<DGR> Parent; 409 412 protected: 410 N odeFilterMap* _node_filter;411 A rcFilterMap* _arc_filter;413 NF* _node_filter; 414 AF* _arc_filter; 412 415 SubDigraphBase() 413 416 : Parent(), _node_filter(0), _arc_filter(0) { } 414 417 415 void setNodeFilterMap(NodeFilterMap& node_filter) { 418 void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { 419 Parent::initialize(digraph); 416 420 _node_filter = &node_filter; 417 } 418 void setArcFilterMap(ArcFilterMap& arc_filter) { 419 _arc_filter = &arc_filter; 421 _arc_filter = &arc_filter; 420 422 } 421 423 … … 488 490 typedef False ArcNumTag; 489 491 490 typedef FindArcTagIndicator<D igraph> FindArcTag;492 typedef FindArcTagIndicator<DGR> FindArcTag; 491 493 Arc findArc(const Node& source, const Node& target, 492 494 const Arc& prev = INVALID) const { … … 501 503 } 502 504 503 template <typename _Value> 504 class NodeMap : public SubMapExtender<Adaptor, 505 typename Parent::template NodeMap<_Value> > { 505 public: 506 507 template <typename V> 508 class NodeMap 509 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 510 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> { 506 511 public: 507 typedef _ValueValue;508 typedef SubMapExtender< Adaptor, typename Parent::509 template NodeMap<Value> > MapParent;510 511 NodeMap(const Adaptor& adaptor)512 : MapParent(adaptor) {}513 NodeMap(const Adaptor& adaptor, const Value& value)514 : MapParent(adaptor, value) {}512 typedef V Value; 513 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 514 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent; 515 516 NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor) 517 : Parent(adaptor) {} 518 NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value) 519 : Parent(adaptor, value) {} 515 520 516 521 private: … … 521 526 template <typename CMap> 522 527 NodeMap& operator=(const CMap& cmap) { 523 MapParent::operator=(cmap);528 Parent::operator=(cmap); 524 529 return *this; 525 530 } 526 531 }; 527 532 528 template <typename _Value> 529 class ArcMap : public SubMapExtender<Adaptor, 530 typename Parent::template ArcMap<_Value> > { 533 template <typename V> 534 class ArcMap 535 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 536 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> { 531 537 public: 532 typedef _ValueValue;533 typedef SubMapExtender< Adaptor, typename Parent::534 template ArcMap<Value> > MapParent;535 536 ArcMap(const Adaptor& adaptor)537 : MapParent(adaptor) {}538 ArcMap(const Adaptor& adaptor, const Value& value)539 : MapParent(adaptor, value) {}538 typedef V Value; 539 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 540 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent; 541 542 ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor) 543 : Parent(adaptor) {} 544 ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value) 545 : Parent(adaptor, value) {} 540 546 541 547 private: … … 546 552 template <typename CMap> 547 553 ArcMap& operator=(const CMap& cmap) { 548 MapParent::operator=(cmap);554 Parent::operator=(cmap); 549 555 return *this; 550 556 } … … 553 559 }; 554 560 555 template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap>556 class SubDigraphBase< _Digraph, _NodeFilterMap, _ArcFilterMap, false>557 : public DigraphAdaptorBase< _Digraph> {558 public: 559 typedef _DigraphDigraph;560 typedef _NodeFilterMapNodeFilterMap;561 typedef _ArcFilterMapArcFilterMap;561 template <typename DGR, typename NF, typename AF> 562 class SubDigraphBase<DGR, NF, AF, false> 563 : public DigraphAdaptorBase<DGR> { 564 public: 565 typedef DGR Digraph; 566 typedef NF NodeFilterMap; 567 typedef AF ArcFilterMap; 562 568 563 569 typedef SubDigraphBase Adaptor; 564 570 typedef DigraphAdaptorBase<Digraph> Parent; 565 571 protected: 566 N odeFilterMap* _node_filter;567 A rcFilterMap* _arc_filter;572 NF* _node_filter; 573 AF* _arc_filter; 568 574 SubDigraphBase() 569 575 : Parent(), _node_filter(0), _arc_filter(0) { } 570 576 571 void setNodeFilterMap(NodeFilterMap& node_filter) { 577 void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { 578 Parent::initialize(digraph); 572 579 _node_filter = &node_filter; 573 } 574 void setArcFilterMap(ArcFilterMap& arc_filter) { 575 _arc_filter = &arc_filter; 580 _arc_filter = &arc_filter; 576 581 } 577 582 … … 628 633 typedef False ArcNumTag; 629 634 630 typedef FindArcTagIndicator<D igraph> FindArcTag;635 typedef FindArcTagIndicator<DGR> FindArcTag; 631 636 Arc findArc(const Node& source, const Node& target, 632 637 const Arc& prev = INVALID) const { … … 641 646 } 642 647 643 template <typename _Value> 644 class NodeMap : public SubMapExtender<Adaptor, 645 typename Parent::template NodeMap<_Value> > { 648 template <typename V> 649 class NodeMap 650 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 651 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> { 646 652 public: 647 typedef _ValueValue;648 typedef SubMapExtender< Adaptor, typename Parent::649 template NodeMap<Value> > MapParent;650 651 NodeMap(const Adaptor& adaptor)652 : MapParent(adaptor) {}653 NodeMap(const Adaptor& adaptor, const Value& value)654 : MapParent(adaptor, value) {}653 typedef V Value; 654 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 655 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent; 656 657 NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor) 658 : Parent(adaptor) {} 659 NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value) 660 : Parent(adaptor, value) {} 655 661 656 662 private: … … 661 667 template <typename CMap> 662 668 NodeMap& operator=(const CMap& cmap) { 663 MapParent::operator=(cmap);669 Parent::operator=(cmap); 664 670 return *this; 665 671 } 666 672 }; 667 673 668 template <typename _Value> 669 class ArcMap : public SubMapExtender<Adaptor, 670 typename Parent::template ArcMap<_Value> > { 674 template <typename V> 675 class ArcMap 676 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 677 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> { 671 678 public: 672 typedef _ValueValue;673 typedef SubMapExtender< Adaptor, typename Parent::674 template ArcMap<Value> > MapParent;675 676 ArcMap(const Adaptor& adaptor)677 : MapParent(adaptor) {}678 ArcMap(const Adaptor& adaptor, const Value& value)679 : MapParent(adaptor, value) {}679 typedef V Value; 680 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 681 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent; 682 683 ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor) 684 : Parent(adaptor) {} 685 ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value) 686 : Parent(adaptor, value) {} 680 687 681 688 private: … … 686 693 template <typename CMap> 687 694 ArcMap& operator=(const CMap& cmap) { 688 MapParent::operator=(cmap);695 Parent::operator=(cmap); 689 696 return *this; 690 697 } … … 709 716 /// parameter is set to be \c const. 710 717 /// 711 /// \tparam GR The type of the adapted digraph.718 /// \tparam DGR The type of the adapted digraph. 712 719 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 713 720 /// It can also be specified to be \c const. … … 715 722 /// It must be a \c bool (or convertible) node map of the 716 723 /// adapted digraph. The default type is 717 /// \ref concepts::Digraph::NodeMap " GR::NodeMap<bool>".724 /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>". 718 725 /// \tparam AF The type of the arc filter map. 719 726 /// It must be \c bool (or convertible) arc map of the 720 727 /// adapted digraph. The default type is 721 /// \ref concepts::Digraph::ArcMap " GR::ArcMap<bool>".728 /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>". 722 729 /// 723 730 /// \note The \c Node and \c Arc types of this adaptor and the adapted … … 727 734 /// \see FilterArcs 728 735 #ifdef DOXYGEN 729 template<typename GR, typename NF, typename AF>736 template<typename DGR, typename NF, typename AF> 730 737 class SubDigraph { 731 738 #else 732 template<typename GR,733 typename NF = typename GR::template NodeMap<bool>,734 typename AF = typename GR::template ArcMap<bool> >739 template<typename DGR, 740 typename NF = typename DGR::template NodeMap<bool>, 741 typename AF = typename DGR::template ArcMap<bool> > 735 742 class SubDigraph : 736 public DigraphAdaptorExtender<SubDigraphBase< GR, NF, AF, true> > {743 public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > { 737 744 #endif 738 745 public: 739 746 /// The type of the adapted digraph. 740 typedef GR Digraph;747 typedef DGR Digraph; 741 748 /// The type of the node filter map. 742 749 typedef NF NodeFilterMap; … … 744 751 typedef AF ArcFilterMap; 745 752 746 typedef DigraphAdaptorExtender<SubDigraphBase< GR, NF, AF, true> >753 typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > 747 754 Parent; 748 755 … … 758 765 /// Creates a subdigraph for the given digraph with the 759 766 /// given node and arc filter maps. 760 SubDigraph(Digraph& digraph, NodeFilterMap& node_filter, 761 ArcFilterMap& arc_filter) { 762 setDigraph(digraph); 763 setNodeFilterMap(node_filter); 764 setArcFilterMap(arc_filter); 767 SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) { 768 Parent::initialize(digraph, node_filter, arc_filter); 765 769 } 766 770 … … 824 828 /// \ingroup graph_adaptors 825 829 /// \relates SubDigraph 826 template<typename GR, typename NF, typename AF>827 SubDigraph<const GR, NF, AF>828 subDigraph(const GR& digraph,829 NF& node_filter _map, AF& arc_filter_map) {830 return SubDigraph<const GR, NF, AF>831 (digraph, node_filter _map, arc_filter_map);830 template<typename DGR, typename NF, typename AF> 831 SubDigraph<const DGR, NF, AF> 832 subDigraph(const DGR& digraph, 833 NF& node_filter, AF& arc_filter) { 834 return SubDigraph<const DGR, NF, AF> 835 (digraph, node_filter, arc_filter); 832 836 } 833 837 834 template<typename GR, typename NF, typename AF>835 SubDigraph<const GR, const NF, AF>836 subDigraph(const GR& digraph,837 const NF& node_filter _map, AF& arc_filter_map) {838 return SubDigraph<const GR, const NF, AF>839 (digraph, node_filter _map, arc_filter_map);838 template<typename DGR, typename NF, typename AF> 839 SubDigraph<const DGR, const NF, AF> 840 subDigraph(const DGR& digraph, 841 const NF& node_filter, AF& arc_filter) { 842 return SubDigraph<const DGR, const NF, AF> 843 (digraph, node_filter, arc_filter); 840 844 } 841 845 842 template<typename GR, typename NF, typename AF>843 SubDigraph<const GR, NF, const AF>844 subDigraph(const GR& digraph,845 NF& node_filter _map, const AF& arc_filter_map) {846 return SubDigraph<const GR, NF, const AF>847 (digraph, node_filter _map, arc_filter_map);846 template<typename DGR, typename NF, typename AF> 847 SubDigraph<const DGR, NF, const AF> 848 subDigraph(const DGR& digraph, 849 NF& node_filter, const AF& arc_filter) { 850 return SubDigraph<const DGR, NF, const AF> 851 (digraph, node_filter, arc_filter); 848 852 } 849 853 850 template<typename GR, typename NF, typename AF>851 SubDigraph<const GR, const NF, const AF>852 subDigraph(const GR& digraph,853 const NF& node_filter _map, const AF& arc_filter_map) {854 return SubDigraph<const GR, const NF, const AF>855 (digraph, node_filter _map, arc_filter_map);854 template<typename DGR, typename NF, typename AF> 855 SubDigraph<const DGR, const NF, const AF> 856 subDigraph(const DGR& digraph, 857 const NF& node_filter, const AF& arc_filter) { 858 return SubDigraph<const DGR, const NF, const AF> 859 (digraph, node_filter, arc_filter); 856 860 } 857 861 858 862 859 template <typename _Graph, typename _NodeFilterMap, 860 typename _EdgeFilterMap, bool _checked = true> 861 class SubGraphBase : public GraphAdaptorBase<_Graph> { 862 public: 863 typedef _Graph Graph; 864 typedef _NodeFilterMap NodeFilterMap; 865 typedef _EdgeFilterMap EdgeFilterMap; 863 template <typename GR, typename NF, typename EF, bool ch = true> 864 class SubGraphBase : public GraphAdaptorBase<GR> { 865 public: 866 typedef GR Graph; 867 typedef NF NodeFilterMap; 868 typedef EF EdgeFilterMap; 866 869 867 870 typedef SubGraphBase Adaptor; 868 typedef GraphAdaptorBase< _Graph> Parent;871 typedef GraphAdaptorBase<GR> Parent; 869 872 protected: 870 873 871 N odeFilterMap* _node_filter_map;872 E dgeFilterMap* _edge_filter_map;874 NF* _node_filter; 875 EF* _edge_filter; 873 876 874 877 SubGraphBase() 875 : Parent(), _node_filter_map(0), _edge_filter_map(0) { } 876 877 void setNodeFilterMap(NodeFilterMap& node_filter_map) { 878 _node_filter_map=&node_filter_map; 879 } 880 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) { 881 _edge_filter_map=&edge_filter_map; 878 : Parent(), _node_filter(0), _edge_filter(0) { } 879 880 void initialize(GR& graph, NF& node_filter, EF& edge_filter) { 881 Parent::initialize(graph); 882 _node_filter = &node_filter; 883 _edge_filter = &edge_filter; 882 884 } 883 885 … … 890 892 void first(Node& i) const { 891 893 Parent::first(i); 892 while (i!=INVALID && !(*_node_filter _map)[i]) Parent::next(i);894 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 893 895 } 894 896 895 897 void first(Arc& i) const { 896 898 Parent::first(i); 897 while (i!=INVALID && (!(*_edge_filter _map)[i]898  !(*_node_filter _map)[Parent::source(i)]899  !(*_node_filter _map)[Parent::target(i)]))899 while (i!=INVALID && (!(*_edge_filter)[i] 900  !(*_node_filter)[Parent::source(i)] 901  !(*_node_filter)[Parent::target(i)])) 900 902 Parent::next(i); 901 903 } … … 903 905 void first(Edge& i) const { 904 906 Parent::first(i); 905 while (i!=INVALID && (!(*_edge_filter _map)[i]906  !(*_node_filter _map)[Parent::u(i)]907  !(*_node_filter _map)[Parent::v(i)]))907 while (i!=INVALID && (!(*_edge_filter)[i] 908  !(*_node_filter)[Parent::u(i)] 909  !(*_node_filter)[Parent::v(i)])) 908 910 Parent::next(i); 909 911 } … … 911 913 void firstIn(Arc& i, const Node& n) const { 912 914 Parent::firstIn(i, n); 913 while (i!=INVALID && (!(*_edge_filter _map)[i]914  !(*_node_filter _map)[Parent::source(i)]))915 while (i!=INVALID && (!(*_edge_filter)[i] 916  !(*_node_filter)[Parent::source(i)])) 915 917 Parent::nextIn(i); 916 918 } … … 918 920 void firstOut(Arc& i, const Node& n) const { 919 921 Parent::firstOut(i, n); 920 while (i!=INVALID && (!(*_edge_filter _map)[i]921  !(*_node_filter _map)[Parent::target(i)]))922 while (i!=INVALID && (!(*_edge_filter)[i] 923  !(*_node_filter)[Parent::target(i)])) 922 924 Parent::nextOut(i); 923 925 } … … 925 927 void firstInc(Edge& i, bool& d, const Node& n) const { 926 928 Parent::firstInc(i, d, n); 927 while (i!=INVALID && (!(*_edge_filter _map)[i]928  !(*_node_filter _map)[Parent::u(i)]929  !(*_node_filter _map)[Parent::v(i)]))929 while (i!=INVALID && (!(*_edge_filter)[i] 930  !(*_node_filter)[Parent::u(i)] 931  !(*_node_filter)[Parent::v(i)])) 930 932 Parent::nextInc(i, d); 931 933 } … … 933 935 void next(Node& i) const { 934 936 Parent::next(i); 935 while (i!=INVALID && !(*_node_filter _map)[i]) Parent::next(i);937 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 936 938 } 937 939 938 940 void next(Arc& i) const { 939 941 Parent::next(i); 940 while (i!=INVALID && (!(*_edge_filter _map)[i]941  !(*_node_filter _map)[Parent::source(i)]942  !(*_node_filter _map)[Parent::target(i)]))942 while (i!=INVALID && (!(*_edge_filter)[i] 943  !(*_node_filter)[Parent::source(i)] 944  !(*_node_filter)[Parent::target(i)])) 943 945 Parent::next(i); 944 946 } … … 946 948 void next(Edge& i) const { 947 949 Parent::next(i); 948 while (i!=INVALID && (!(*_edge_filter _map)[i]949  !(*_node_filter _map)[Parent::u(i)]950  !(*_node_filter _map)[Parent::v(i)]))950 while (i!=INVALID && (!(*_edge_filter)[i] 951  !(*_node_filter)[Parent::u(i)] 952  !(*_node_filter)[Parent::v(i)])) 951 953 Parent::next(i); 952 954 } … … 954 956 void nextIn(Arc& i) const { 955 957 Parent::nextIn(i); 956 while (i!=INVALID && (!(*_edge_filter _map)[i]957  !(*_node_filter _map)[Parent::source(i)]))958 while (i!=INVALID && (!(*_edge_filter)[i] 959  !(*_node_filter)[Parent::source(i)])) 958 960 Parent::nextIn(i); 959 961 } … … 961 963 void nextOut(Arc& i) const { 962 964 Parent::nextOut(i); 963 while (i!=INVALID && (!(*_edge_filter _map)[i]964  !(*_node_filter _map)[Parent::target(i)]))965 while (i!=INVALID && (!(*_edge_filter)[i] 966  !(*_node_filter)[Parent::target(i)])) 965 967 Parent::nextOut(i); 966 968 } … … 968 970 void nextInc(Edge& i, bool& d) const { 969 971 Parent::nextInc(i, d); 970 while (i!=INVALID && (!(*_edge_filter _map)[i]971  !(*_node_filter _map)[Parent::u(i)]972  !(*_node_filter _map)[Parent::v(i)]))972 while (i!=INVALID && (!(*_edge_filter)[i] 973  !(*_node_filter)[Parent::u(i)] 974  !(*_node_filter)[Parent::v(i)])) 973 975 Parent::nextInc(i, d); 974 976 } 975 977 976 void status(const Node& n, bool v) const { _node_filter _map>set(n, v); }977 void status(const Edge& e, bool v) const { _edge_filter _map>set(e, v); }978 979 bool status(const Node& n) const { return (*_node_filter _map)[n]; }980 bool status(const Edge& e) const { return (*_edge_filter _map)[e]; }978 void status(const Node& n, bool v) const { _node_filter>set(n, v); } 979 void status(const Edge& e, bool v) const { _edge_filter>set(e, v); } 980 981 bool status(const Node& n) const { return (*_node_filter)[n]; } 982 bool status(const Edge& e) const { return (*_edge_filter)[e]; } 981 983 982 984 typedef False NodeNumTag; … … 987 989 Arc findArc(const Node& u, const Node& v, 988 990 const Arc& prev = INVALID) const { 989 if (!(*_node_filter _map)[u]  !(*_node_filter_map)[v]) {991 if (!(*_node_filter)[u]  !(*_node_filter)[v]) { 990 992 return INVALID; 991 993 } 992 994 Arc arc = Parent::findArc(u, v, prev); 993 while (arc != INVALID && !(*_edge_filter _map)[arc]) {995 while (arc != INVALID && !(*_edge_filter)[arc]) { 994 996 arc = Parent::findArc(u, v, arc); 995 997 } … … 1000 1002 Edge findEdge(const Node& u, const Node& v, 1001 1003 const Edge& prev = INVALID) const { 1002 if (!(*_node_filter _map)[u]  !(*_node_filter_map)[v]) {1004 if (!(*_node_filter)[u]  !(*_node_filter)[v]) { 1003 1005 return INVALID; 1004 1006 } 1005 1007 Edge edge = Parent::findEdge(u, v, prev); 1006 while (edge != INVALID && !(*_edge_filter _map)[edge]) {1008 while (edge != INVALID && !(*_edge_filter)[edge]) { 1007 1009 edge = Parent::findEdge(u, v, edge); 1008 1010 } … … 1010 1012 } 1011 1013 1012 template <typename _Value> 1013 class NodeMap : public SubMapExtender<Adaptor, 1014 typename Parent::template NodeMap<_Value> > { 1014 template <typename V> 1015 class NodeMap 1016 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1017 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> { 1015 1018 public: 1016 typedef _ValueValue;1017 typedef SubMapExtender< Adaptor, typename Parent::1018 template NodeMap<Value> > MapParent;1019 1020 NodeMap(const Adaptor& adaptor)1021 : MapParent(adaptor) {}1022 NodeMap(const Adaptor& adaptor, const Value& value)1023 : MapParent(adaptor, value) {}1019 typedef V Value; 1020 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1021 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent; 1022 1023 NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor) 1024 : Parent(adaptor) {} 1025 NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value) 1026 : Parent(adaptor, value) {} 1024 1027 1025 1028 private: … … 1030 1033 template <typename CMap> 1031 1034 NodeMap& operator=(const CMap& cmap) { 1032 MapParent::operator=(cmap);1035 Parent::operator=(cmap); 1033 1036 return *this; 1034 1037 } 1035 1038 }; 1036 1039 1037 template <typename _Value> 1038 class ArcMap : public SubMapExtender<Adaptor, 1039 typename Parent::template ArcMap<_Value> > { 1040 template <typename V> 1041 class ArcMap 1042 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1043 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> { 1040 1044 public: 1041 typedef _ValueValue;1042 typedef SubMapExtender< Adaptor, typename Parent::1043 template ArcMap<Value> > MapParent;1044 1045 ArcMap(const Adaptor& adaptor)1046 : MapParent(adaptor) {}1047 ArcMap(const Adaptor& adaptor, const Value& value)1048 : MapParent(adaptor, value) {}1045 typedef V Value; 1046 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1047 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent; 1048 1049 ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor) 1050 : Parent(adaptor) {} 1051 ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value) 1052 : Parent(adaptor, value) {} 1049 1053 1050 1054 private: … … 1055 1059 template <typename CMap> 1056 1060 ArcMap& operator=(const CMap& cmap) { 1057 MapParent::operator=(cmap);1061 Parent::operator=(cmap); 1058 1062 return *this; 1059 1063 } 1060 1064 }; 1061 1065 1062 template <typename _Value> 1063 class EdgeMap : public SubMapExtender<Adaptor, 1064 typename Parent::template EdgeMap<_Value> > { 1066 template <typename V> 1067 class EdgeMap 1068 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1069 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> { 1065 1070 public: 1066 typedef _ValueValue;1067 typedef SubMapExtender< Adaptor, typename Parent::1068 template EdgeMap<Value> > MapParent;1069 1070 EdgeMap(const Adaptor& adaptor)1071 : MapParent(adaptor) {}1072 1073 EdgeMap(const Adaptor& adaptor, const Value& value)1074 : MapParent(adaptor, value) {}1071 typedef V Value; 1072 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1073 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent; 1074 1075 EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor) 1076 : Parent(adaptor) {} 1077 1078 EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value) 1079 : Parent(adaptor, value) {} 1075 1080 1076 1081 private: … … 1081 1086 template <typename CMap> 1082 1087 EdgeMap& operator=(const CMap& cmap) { 1083 MapParent::operator=(cmap);1088 Parent::operator=(cmap); 1084 1089 return *this; 1085 1090 } … … 1088 1093 }; 1089 1094 1090 template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>1091 class SubGraphBase< _Graph, _NodeFilterMap, _EdgeFilterMap, false>1092 : public GraphAdaptorBase< _Graph> {1093 public: 1094 typedef _GraphGraph;1095 typedef _NodeFilterMapNodeFilterMap;1096 typedef _EdgeFilterMapEdgeFilterMap;1095 template <typename GR, typename NF, typename EF> 1096 class SubGraphBase<GR, NF, EF, false> 1097 : public GraphAdaptorBase<GR> { 1098 public: 1099 typedef GR Graph; 1100 typedef NF NodeFilterMap; 1101 typedef EF EdgeFilterMap; 1097 1102 1098 1103 typedef SubGraphBase Adaptor; 1099 typedef GraphAdaptorBase< _Graph> Parent;1104 typedef GraphAdaptorBase<GR> Parent; 1100 1105 protected: 1101 NodeFilterMap* _node_filter_map; 1102 EdgeFilterMap* _edge_filter_map; 1103 SubGraphBase() : Parent(), 1104 _node_filter_map(0), _edge_filter_map(0) { } 1105 1106 void setNodeFilterMap(NodeFilterMap& node_filter_map) { 1107 _node_filter_map=&node_filter_map; 1108 } 1109 void setEdgeFilterMap(EdgeFilterMap& edge_filter_map) { 1110 _edge_filter_map=&edge_filter_map; 1106 NF* _node_filter; 1107 EF* _edge_filter; 1108 SubGraphBase() 1109 : Parent(), _node_filter(0), _edge_filter(0) { } 1110 1111 void initialize(GR& graph, NF& node_filter, EF& edge_filter) { 1112 Parent::initialize(graph); 1113 _node_filter = &node_filter; 1114 _edge_filter = &edge_filter; 1111 1115 } 1112 1116 … … 1119 1123 void first(Node& i) const { 1120 1124 Parent::first(i); 1121 while (i!=INVALID && !(*_node_filter _map)[i]) Parent::next(i);1125 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 1122 1126 } 1123 1127 1124 1128 void first(Arc& i) const { 1125 1129 Parent::first(i); 1126 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::next(i);1130 while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); 1127 1131 } 1128 1132 1129 1133 void first(Edge& i) const { 1130 1134 Parent::first(i); 1131 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::next(i);1135 while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); 1132 1136 } 1133 1137 1134 1138 void firstIn(Arc& i, const Node& n) const { 1135 1139 Parent::firstIn(i, n); 1136 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextIn(i);1140 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i); 1137 1141 } 1138 1142 1139 1143 void firstOut(Arc& i, const Node& n) const { 1140 1144 Parent::firstOut(i, n); 1141 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextOut(i);1145 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i); 1142 1146 } 1143 1147 1144 1148 void firstInc(Edge& i, bool& d, const Node& n) const { 1145 1149 Parent::firstInc(i, d, n); 1146 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextInc(i, d);1150 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d); 1147 1151 } 1148 1152 1149 1153 void next(Node& i) const { 1150 1154 Parent::next(i); 1151 while (i!=INVALID && !(*_node_filter _map)[i]) Parent::next(i);1155 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 1152 1156 } 1153 1157 void next(Arc& i) const { 1154 1158 Parent::next(i); 1155 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::next(i);1159 while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); 1156 1160 } 1157 1161 void next(Edge& i) const { 1158 1162 Parent::next(i); 1159 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::next(i);1163 while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); 1160 1164 } 1161 1165 void nextIn(Arc& i) const { 1162 1166 Parent::nextIn(i); 1163 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextIn(i);1167 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i); 1164 1168 } 1165 1169 1166 1170 void nextOut(Arc& i) const { 1167 1171 Parent::nextOut(i); 1168 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextOut(i);1172 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i); 1169 1173 } 1170 1174 void nextInc(Edge& i, bool& d) const { 1171 1175 Parent::nextInc(i, d); 1172 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextInc(i, d);1173 } 1174 1175 void status(const Node& n, bool v) const { _node_filter _map>set(n, v); }1176 void status(const Edge& e, bool v) const { _edge_filter _map>set(e, v); }1177 1178 bool status(const Node& n) const { return (*_node_filter _map)[n]; }1179 bool status(const Edge& e) const { return (*_edge_filter _map)[e]; }1176 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d); 1177 } 1178 1179 void status(const Node& n, bool v) const { _node_filter>set(n, v); } 1180 void status(const Edge& e, bool v) const { _edge_filter>set(e, v); } 1181 1182 bool status(const Node& n) const { return (*_node_filter)[n]; } 1183 bool status(const Edge& e) const { return (*_edge_filter)[e]; } 1180 1184 1181 1185 typedef False NodeNumTag; … … 1187 1191 const Arc& prev = INVALID) const { 1188 1192 Arc arc = Parent::findArc(u, v, prev); 1189 while (arc != INVALID && !(*_edge_filter _map)[arc]) {1193 while (arc != INVALID && !(*_edge_filter)[arc]) { 1190 1194 arc = Parent::findArc(u, v, arc); 1191 1195 } … … 1197 1201 const Edge& prev = INVALID) const { 1198 1202 Edge edge = Parent::findEdge(u, v, prev); 1199 while (edge != INVALID && !(*_edge_filter _map)[edge]) {1203 while (edge != INVALID && !(*_edge_filter)[edge]) { 1200 1204 edge = Parent::findEdge(u, v, edge); 1201 1205 } … … 1203 1207 } 1204 1208 1205 template <typename _Value> 1206 class NodeMap : public SubMapExtender<Adaptor, 1207 typename Parent::template NodeMap<_Value> > { 1209 template <typename V> 1210 class NodeMap 1211 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1212 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> { 1208 1213 public: 1209 typedef _ValueValue;1210 typedef SubMapExtender< Adaptor, typename Parent::1211 template NodeMap<Value> > MapParent;1212 1213 NodeMap(const Adaptor& adaptor)1214 : MapParent(adaptor) {}1215 NodeMap(const Adaptor& adaptor, const Value& value)1216 : MapParent(adaptor, value) {}1214 typedef V Value; 1215 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1216 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent; 1217 1218 NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor) 1219 : Parent(adaptor) {} 1220 NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value) 1221 : Parent(adaptor, value) {} 1217 1222 1218 1223 private: … … 1223 1228 template <typename CMap> 1224 1229 NodeMap& operator=(const CMap& cmap) { 1225 MapParent::operator=(cmap);1230 Parent::operator=(cmap); 1226 1231 return *this; 1227 1232 } 1228 1233 }; 1229 1234 1230 template <typename _Value> 1231 class ArcMap : public SubMapExtender<Adaptor, 1232 typename Parent::template ArcMap<_Value> > { 1235 template <typename V> 1236 class ArcMap 1237 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1238 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> { 1233 1239 public: 1234 typedef _ValueValue;1235 typedef SubMapExtender< Adaptor, typename Parent::1236 template ArcMap<Value> > MapParent;1237 1238 ArcMap(const Adaptor& adaptor)1239 : MapParent(adaptor) {}1240 ArcMap(const Adaptor& adaptor, const Value& value)1241 : MapParent(adaptor, value) {}1240 typedef V Value; 1241 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1242 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent; 1243 1244 ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor) 1245 : Parent(adaptor) {} 1246 ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value) 1247 : Parent(adaptor, value) {} 1242 1248 1243 1249 private: … … 1248 1254 template <typename CMap> 1249 1255 ArcMap& operator=(const CMap& cmap) { 1250 MapParent::operator=(cmap);1256 Parent::operator=(cmap); 1251 1257 return *this; 1252 1258 } 1253 1259 }; 1254 1260 1255 template <typename _Value> 1256 class EdgeMap : public SubMapExtender<Adaptor, 1257 typename Parent::template EdgeMap<_Value> > { 1261 template <typename V> 1262 class EdgeMap 1263 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1264 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> { 1258 1265 public: 1259 typedef _ValueValue;1260 typedef SubMapExtender< Adaptor, typename Parent::1261 template EdgeMap<Value> > MapParent;1262 1263 EdgeMap(const Adaptor& adaptor)1264 : MapParent(adaptor) {}1265 1266 EdgeMap(const Adaptor& adaptor, const _Value& value)1267 : MapParent(adaptor, value) {}1266 typedef V Value; 1267 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1268 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent; 1269 1270 EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor) 1271 : Parent(adaptor) {} 1272 1273 EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value) 1274 : Parent(adaptor, value) {} 1268 1275 1269 1276 private: … … 1274 1281 template <typename CMap> 1275 1282 EdgeMap& operator=(const CMap& cmap) { 1276 MapParent::operator=(cmap);1283 Parent::operator=(cmap); 1277 1284 return *this; 1278 1285 } … … 1333 1340 typedef EF EdgeFilterMap; 1334 1341 1335 typedef GraphAdaptorExtender< 1342 typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > 1336 1343 Parent; 1337 1344 … … 1347 1354 /// Creates a subgraph for the given graph with the given node 1348 1355 /// and edge filter maps. 1349 SubGraph(Graph& graph, NodeFilterMap& node_filter_map, 1350 EdgeFilterMap& edge_filter_map) { 1351 setGraph(graph); 1352 setNodeFilterMap(node_filter_map); 1353 setEdgeFilterMap(edge_filter_map); 1356 SubGraph(GR& graph, NF& node_filter, EF& edge_filter) { 1357 initialize(graph, node_filter, edge_filter); 1354 1358 } 1355 1359 … … 1415 1419 template<typename GR, typename NF, typename EF> 1416 1420 SubGraph<const GR, NF, EF> 1417 subGraph(const GR& graph, 1418 NF& node_filter_map, EF& edge_filter_map) { 1421 subGraph(const GR& graph, NF& node_filter, EF& edge_filter) { 1419 1422 return SubGraph<const GR, NF, EF> 1420 (graph, node_filter _map, edge_filter_map);1423 (graph, node_filter, edge_filter); 1421 1424 } 1422 1425 1423 1426 template<typename GR, typename NF, typename EF> 1424 1427 SubGraph<const GR, const NF, EF> 1425 subGraph(const GR& graph, 1426 const NF& node_filter_map, EF& edge_filter_map) { 1428 subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) { 1427 1429 return SubGraph<const GR, const NF, EF> 1428 (graph, node_filter _map, edge_filter_map);1430 (graph, node_filter, edge_filter); 1429 1431 } 1430 1432 1431 1433 template<typename GR, typename NF, typename EF> 1432 1434 SubGraph<const GR, NF, const EF> 1433 subGraph(const GR& graph, 1434 NF& node_filter_map, const EF& edge_filter_map) { 1435 subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) { 1435 1436 return SubGraph<const GR, NF, const EF> 1436 (graph, node_filter _map, edge_filter_map);1437 (graph, node_filter, edge_filter); 1437 1438 } 1438 1439 1439 1440 template<typename GR, typename NF, typename EF> 1440 1441 SubGraph<const GR, const NF, const EF> 1441 subGraph(const GR& graph, 1442 const NF& node_filter_map, const EF& edge_filter_map) { 1442 subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) { 1443 1443 return SubGraph<const GR, const NF, const EF> 1444 (graph, node_filter _map, edge_filter_map);1444 (graph, node_filter, edge_filter); 1445 1445 } 1446 1446 … … 1482 1482 class FilterNodes : 1483 1483 public DigraphAdaptorExtender< 1484 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > { 1484 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 1485 true> > { 1485 1486 #endif 1486 1487 public: … … 1490 1491 1491 1492 typedef DigraphAdaptorExtender< 1492 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >1493 Parent;1493 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 1494 true> > Parent; 1494 1495 1495 1496 typedef typename Parent::Node Node; 1496 1497 1497 1498 protected: 1498 ConstMap<typename Digraph::Arc, bool> const_true_map; 1499 1500 FilterNodes() : const_true_map(true) { 1501 Parent::setArcFilterMap(const_true_map); 1502 } 1499 ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map; 1500 1501 FilterNodes() : const_true_map() {} 1503 1502 1504 1503 public: … … 1508 1507 /// Creates a subgraph for the given digraph or graph with the 1509 1508 /// given node filter map. 1510 FilterNodes(GR& graph, N odeFilterMap& node_filter) :1511 Parent(), const_true_map(true)1509 FilterNodes(GR& graph, NF& node_filter) 1510 : Parent(), const_true_map() 1512 1511 { 1513 Parent::setDigraph(graph); 1514 Parent::setNodeFilterMap(node_filter); 1515 Parent::setArcFilterMap(const_true_map); 1512 Parent::initialize(graph, node_filter, const_true_map); 1516 1513 } 1517 1514 … … 1548 1545 typename enable_if<UndirectedTagIndicator<GR> >::type> : 1549 1546 public GraphAdaptorExtender< 1550 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > { 1547 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 1548 true> > { 1551 1549 1552 1550 public: … … 1554 1552 typedef NF NodeFilterMap; 1555 1553 typedef GraphAdaptorExtender< 1556 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >1557 Parent;1554 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 1555 true> > Parent; 1558 1556 1559 1557 typedef typename Parent::Node Node; 1560 1558 protected: 1561 ConstMap<typename Graph::Edge, bool> const_true_map; 1562 1563 FilterNodes() : const_true_map(true) { 1564 Parent::setEdgeFilterMap(const_true_map); 1565 } 1566 1567 public: 1568 1569 FilterNodes(Graph& _graph, NodeFilterMap& node_filter_map) : 1570 Parent(), const_true_map(true) { 1571 Parent::setGraph(_graph); 1572 Parent::setNodeFilterMap(node_filter_map); 1573 Parent::setEdgeFilterMap(const_true_map); 1559 ConstMap<typename GR::Edge, Const<bool, true> > const_true_map; 1560 1561 FilterNodes() : const_true_map() {} 1562 1563 public: 1564 1565 FilterNodes(GR& graph, NodeFilterMap& node_filter) : 1566 Parent(), const_true_map() { 1567 Parent::initialize(graph, node_filter, const_true_map); 1574 1568 } 1575 1569 … … 1589 1583 template<typename GR, typename NF> 1590 1584 FilterNodes<const GR, NF> 1591 filterNodes(const GR& graph, NF& node_filter _map) {1592 return FilterNodes<const GR, NF>(graph, node_filter _map);1585 filterNodes(const GR& graph, NF& node_filter) { 1586 return FilterNodes<const GR, NF>(graph, node_filter); 1593 1587 } 1594 1588 1595 1589 template<typename GR, typename NF> 1596 1590 FilterNodes<const GR, const NF> 1597 filterNodes(const GR& graph, const NF& node_filter _map) {1598 return FilterNodes<const GR, const NF>(graph, node_filter _map);1591 filterNodes(const GR& graph, const NF& node_filter) { 1592 return FilterNodes<const GR, const NF>(graph, node_filter); 1599 1593 } 1600 1594 … … 1613 1607 /// parameter is set to be \c const. 1614 1608 /// 1615 /// \tparam GR The type of the adapted digraph.1609 /// \tparam DGR The type of the adapted digraph. 1616 1610 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 1617 1611 /// It can also be specified to be \c const. … … 1619 1613 /// It must be a \c bool (or convertible) arc map of the 1620 1614 /// adapted digraph. The default type is 1621 /// \ref concepts::Digraph::ArcMap " GR::ArcMap<bool>".1615 /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>". 1622 1616 /// 1623 1617 /// \note The \c Node and \c Arc types of this adaptor and the adapted 1624 1618 /// digraph are convertible to each other. 1625 1619 #ifdef DOXYGEN 1626 template<typename GR,1620 template<typename DGR, 1627 1621 typename AF> 1628 1622 class FilterArcs { 1629 1623 #else 1630 template<typename GR,1631 typename AF = typename GR::template ArcMap<bool> >1624 template<typename DGR, 1625 typename AF = typename DGR::template ArcMap<bool> > 1632 1626 class FilterArcs : 1633 1627 public DigraphAdaptorExtender< 1634 SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > { 1628 SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 1629 AF, false> > { 1635 1630 #endif 1636 1631 public: 1637 1632 /// The type of the adapted digraph. 1638 typedef GR Digraph;1633 typedef DGR Digraph; 1639 1634 /// The type of the arc filter map. 1640 1635 typedef AF ArcFilterMap; 1641 1636 1642 1637 typedef DigraphAdaptorExtender< 1643 SubDigraphBase< GR, ConstMap<typename GR::Node, bool>, AF, false> >1644 Parent;1638 SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 1639 AF, false> > Parent; 1645 1640 1646 1641 typedef typename Parent::Arc Arc; 1647 1642 1648 1643 protected: 1649 ConstMap<typename Digraph::Node, bool> const_true_map; 1650 1651 FilterArcs() : const_true_map(true) { 1652 Parent::setNodeFilterMap(const_true_map); 1653 } 1644 ConstMap<typename DGR::Node, Const<bool, true> > const_true_map; 1645 1646 FilterArcs() : const_true_map() {} 1654 1647 1655 1648 public: … … 1659 1652 /// Creates a subdigraph for the given digraph with the given arc 1660 1653 /// filter map. 1661 FilterArcs(Digraph& digraph, ArcFilterMap& arc_filter) 1662 : Parent(), const_true_map(true) { 1663 Parent::setDigraph(digraph); 1664 Parent::setNodeFilterMap(const_true_map); 1665 Parent::setArcFilterMap(arc_filter); 1654 FilterArcs(DGR& digraph, ArcFilterMap& arc_filter) 1655 : Parent(), const_true_map() { 1656 Parent::initialize(digraph, const_true_map, arc_filter); 1666 1657 } 1667 1658 … … 1699 1690 /// \ingroup graph_adaptors 1700 1691 /// \relates FilterArcs 1701 template<typename GR, typename AF>1702 FilterArcs<const GR, AF>1703 filterArcs(const GR& digraph, AF& arc_filter_map) {1704 return FilterArcs<const GR, AF>(digraph, arc_filter_map);1692 template<typename DGR, typename AF> 1693 FilterArcs<const DGR, AF> 1694 filterArcs(const DGR& digraph, AF& arc_filter) { 1695 return FilterArcs<const DGR, AF>(digraph, arc_filter); 1705 1696 } 1706 1697 1707 template<typename GR, typename AF>1708 FilterArcs<const GR, const AF>1709 filterArcs(const GR& digraph, const AF& arc_filter_map) {1710 return FilterArcs<const GR, const AF>(digraph, arc_filter_map);1698 template<typename DGR, typename AF> 1699 FilterArcs<const DGR, const AF> 1700 filterArcs(const DGR& digraph, const AF& arc_filter) { 1701 return FilterArcs<const DGR, const AF>(digraph, arc_filter); 1711 1702 } 1712 1703 … … 1744 1735 class FilterEdges : 1745 1736 public GraphAdaptorExtender< 1746 SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > { 1737 SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 1738 EF, false> > { 1747 1739 #endif 1748 1740 public: … … 1753 1745 1754 1746 typedef GraphAdaptorExtender< 1755 SubGraphBase<GR, ConstMap<typename GR::Node, bool>, EF, false> >1756 Parent;1747 SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 1748 EF, false> > Parent; 1757 1749 1758 1750 typedef typename Parent::Edge Edge; 1759 1751 1760 1752 protected: 1761 ConstMap<typename G raph::Node, bool> const_true_map;1753 ConstMap<typename GR::Node, Const<bool, true> > const_true_map; 1762 1754 1763 1755 FilterEdges() : const_true_map(true) { … … 1771 1763 /// Creates a subgraph for the given graph with the given edge 1772 1764 /// filter map. 1773 FilterEdges(Graph& graph, EdgeFilterMap& edge_filter_map) : 1774 Parent(), const_true_map(true) { 1775 Parent::setGraph(graph); 1776 Parent::setNodeFilterMap(const_true_map); 1777 Parent::setEdgeFilterMap(edge_filter_map); 1765 FilterEdges(GR& graph, EF& edge_filter) 1766 : Parent(), const_true_map() { 1767 Parent::initialize(graph, const_true_map, edge_filter); 1778 1768 } 1779 1769 … … 1813 1803 template<typename GR, typename EF> 1814 1804 FilterEdges<const GR, EF> 1815 filterEdges(const GR& graph, EF& edge_filter _map) {1816 return FilterEdges<const GR, EF>(graph, edge_filter _map);1805 filterEdges(const GR& graph, EF& edge_filter) { 1806 return FilterEdges<const GR, EF>(graph, edge_filter); 1817 1807 } 1818 1808 1819 1809 template<typename GR, typename EF> 1820 1810 FilterEdges<const GR, const EF> 1821 filterEdges(const GR& graph, const EF& edge_filter _map) {1822 return FilterEdges<const GR, const EF>(graph, edge_filter _map);1811 filterEdges(const GR& graph, const EF& edge_filter) { 1812 return FilterEdges<const GR, const EF>(graph, edge_filter); 1823 1813 } 1824 1814 1825 1815 1826 template <typename _Digraph>1816 template <typename DGR> 1827 1817 class UndirectorBase { 1828 1818 public: 1829 typedef _DigraphDigraph;1819 typedef DGR Digraph; 1830 1820 typedef UndirectorBase Adaptor; 1831 1821 … … 2063 2053 private: 2064 2054 2065 template <typename _Value>2055 template <typename V> 2066 2056 class ArcMapBase { 2067 2057 private: 2068 2058 2069 typedef typename D igraph::template ArcMap<_Value> MapImpl;2059 typedef typename DGR::template ArcMap<V> MapImpl; 2070 2060 2071 2061 public: … … 2073 2063 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag; 2074 2064 2075 typedef _ValueValue;2065 typedef V Value; 2076 2066 typedef Arc Key; 2077 2067 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue; … … 2080 2070 typedef typename MapTraits<MapImpl>::ReturnValue Reference; 2081 2071 2082 ArcMapBase(const Adaptor& adaptor) :2072 ArcMapBase(const UndirectorBase<DGR>& adaptor) : 2083 2073 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} 2084 2074 2085 ArcMapBase(const Adaptor& adaptor, const Value& v) 2086 : _forward(*adaptor._digraph, v), _backward(*adaptor._digraph, v) {} 2087 2088 void set(const Arc& a, const Value& v) { 2075 ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value) 2076 : _forward(*adaptor._digraph, value), 2077 _backward(*adaptor._digraph, value) {} 2078 2079 void set(const Arc& a, const V& value) { 2089 2080 if (direction(a)) { 2090 _forward.set(a, v );2081 _forward.set(a, value); 2091 2082 } else { 2092 _backward.set(a, v );2083 _backward.set(a, value); 2093 2084 } 2094 2085 } … … 2118 2109 public: 2119 2110 2120 template <typename _Value>2121 class NodeMap : public D igraph::template NodeMap<_Value> {2111 template <typename V> 2112 class NodeMap : public DGR::template NodeMap<V> { 2122 2113 public: 2123 2114 2124 typedef _ValueValue;2125 typedef typename D igraph::template NodeMap<Value> Parent;2126 2127 explicit NodeMap(const Adaptor& adaptor)2115 typedef V Value; 2116 typedef typename DGR::template NodeMap<Value> Parent; 2117 2118 explicit NodeMap(const UndirectorBase<DGR>& adaptor) 2128 2119 : Parent(*adaptor._digraph) {} 2129 2120 2130 NodeMap(const Adaptor& adaptor, const _Value& value)2121 NodeMap(const UndirectorBase<DGR>& adaptor, const V& value) 2131 2122 : Parent(*adaptor._digraph, value) { } 2132 2123 … … 2144 2135 }; 2145 2136 2146 template <typename _Value>2137 template <typename V> 2147 2138 class ArcMap 2148 : public SubMapExtender< Adaptor, ArcMapBase<_Value> >2139 : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > 2149 2140 { 2150 2141 public: 2151 typedef _ValueValue;2152 typedef SubMapExtender<Adaptor, ArcMapBase<V alue> > Parent;2153 2154 explicit ArcMap(const Adaptor& adaptor)2142 typedef V Value; 2143 typedef SubMapExtender<Adaptor, ArcMapBase<V> > Parent; 2144 2145 explicit ArcMap(const UndirectorBase<DGR>& adaptor) 2155 2146 : Parent(adaptor) {} 2156 2147 2157 ArcMap(const Adaptor& adaptor, const Value& value)2148 ArcMap(const UndirectorBase<DGR>& adaptor, const V& value) 2158 2149 : Parent(adaptor, value) {} 2159 2150 … … 2170 2161 }; 2171 2162 2172 template <typename _Value>2173 class EdgeMap : public Digraph::template ArcMap< _Value> {2163 template <typename V> 2164 class EdgeMap : public Digraph::template ArcMap<V> { 2174 2165 public: 2175 2166 2176 typedef _ValueValue;2177 typedef typename Digraph::template ArcMap<V alue> Parent;2178 2179 explicit EdgeMap(const Adaptor& adaptor)2167 typedef V Value; 2168 typedef typename Digraph::template ArcMap<V> Parent; 2169 2170 explicit EdgeMap(const UndirectorBase<DGR>& adaptor) 2180 2171 : Parent(*adaptor._digraph) {} 2181 2172 2182 EdgeMap(const Adaptor& adaptor, const Value& value)2173 EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value) 2183 2174 : Parent(*adaptor._digraph, value) {} 2184 2175 … … 2196 2187 }; 2197 2188 2198 typedef typename ItemSetTraits<D igraph, Node>::ItemNotifier NodeNotifier;2189 typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier; 2199 2190 NodeNotifier& notifier(Node) const { return _digraph>notifier(Node()); } 2200 2191 2201 typedef typename ItemSetTraits<D igraph, Edge>::ItemNotifier EdgeNotifier;2192 typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier; 2202 2193 EdgeNotifier& notifier(Edge) const { return _digraph>notifier(Edge()); } 2203 2194 … … 2206 2197 UndirectorBase() : _digraph(0) {} 2207 2198 2208 D igraph* _digraph;2209 2210 void setDigraph(Digraph& digraph) {2199 DGR* _digraph; 2200 2201 void initialize(DGR& digraph) { 2211 2202 _digraph = &digraph; 2212 2203 } … … 2227 2218 /// parameter is set to be \c const. 2228 2219 /// 2229 /// \tparam GR The type of the adapted digraph.2220 /// \tparam DGR The type of the adapted digraph. 2230 2221 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 2231 2222 /// It can also be specified to be \c const. … … 2237 2228 /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type 2238 2229 /// of the adapted digraph.) 2239 template<typename GR>2230 template<typename DGR> 2240 2231 #ifdef DOXYGEN 2241 2232 class Undirector { 2242 2233 #else 2243 2234 class Undirector : 2244 public GraphAdaptorExtender<UndirectorBase< GR> > {2235 public GraphAdaptorExtender<UndirectorBase<DGR> > { 2245 2236 #endif 2246 2237 public: 2247 2238 /// The type of the adapted digraph. 2248 typedef GR Digraph;2249 typedef GraphAdaptorExtender<UndirectorBase< GR> > Parent;2239 typedef DGR Digraph; 2240 typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent; 2250 2241 protected: 2251 2242 Undirector() { } … … 2255 2246 /// 2256 2247 /// Creates an undirected graph from the given digraph. 2257 Undirector(D igraph& digraph) {2258 setDigraph(digraph);2248 Undirector(DGR& digraph) { 2249 initialize(digraph); 2259 2250 } 2260 2251 … … 2356 2347 /// \ingroup graph_adaptors 2357 2348 /// \relates Undirector 2358 template<typename GR>2359 Undirector<const GR> undirector(constGR& digraph) {2360 return Undirector<const GR>(digraph);2349 template<typename DGR> 2350 Undirector<const DGR> undirector(const DGR& digraph) { 2351 return Undirector<const DGR>(digraph); 2361 2352 } 2362 2353 2363 2354 2364 template <typename _Graph, typename _DirectionMap>2355 template <typename GR, typename DM> 2365 2356 class OrienterBase { 2366 2357 public: 2367 2358 2368 typedef _GraphGraph;2369 typedef _DirectionMapDirectionMap;2370 2371 typedef typename G raph::Node Node;2372 typedef typename G raph::Edge Arc;2359 typedef GR Graph; 2360 typedef DM DirectionMap; 2361 2362 typedef typename GR::Node Node; 2363 typedef typename GR::Edge Arc; 2373 2364 2374 2365 void reverseArc(const Arc& arc) { … … 2449 2440 int maxArcId() const { return _graph>maxEdgeId(); } 2450 2441 2451 typedef typename ItemSetTraits<G raph, Node>::ItemNotifier NodeNotifier;2442 typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier; 2452 2443 NodeNotifier& notifier(Node) const { return _graph>notifier(Node()); } 2453 2444 2454 typedef typename ItemSetTraits<G raph, Arc>::ItemNotifier ArcNotifier;2445 typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier; 2455 2446 ArcNotifier& notifier(Arc) const { return _graph>notifier(Arc()); } 2456 2447 2457 template <typename _Value>2458 class NodeMap : public _Graph::template NodeMap<_Value> {2448 template <typename V> 2449 class NodeMap : public GR::template NodeMap<V> { 2459 2450 public: 2460 2451 2461 typedef typename _Graph::template NodeMap<_Value> Parent;2462 2463 explicit NodeMap(const OrienterBase & adapter)2452 typedef typename GR::template NodeMap<V> Parent; 2453 2454 explicit NodeMap(const OrienterBase<GR, DM>& adapter) 2464 2455 : Parent(*adapter._graph) {} 2465 2456 2466 NodeMap(const OrienterBase & adapter, const _Value& value)2457 NodeMap(const OrienterBase<GR, DM>& adapter, const V& value) 2467 2458 : Parent(*adapter._graph, value) {} 2468 2459 … … 2480 2471 }; 2481 2472 2482 template <typename _Value>2483 class ArcMap : public _Graph::template EdgeMap<_Value> {2473 template <typename V> 2474 class ArcMap : public GR::template EdgeMap<V> { 2484 2475 public: 2485 2476 2486 typedef typename Graph::template EdgeMap< _Value> Parent;2487 2488 explicit ArcMap(const OrienterBase & adapter)2477 typedef typename Graph::template EdgeMap<V> Parent; 2478 2479 explicit ArcMap(const OrienterBase<GR, DM>& adapter) 2489 2480 : Parent(*adapter._graph) { } 2490 2481 2491 ArcMap(const OrienterBase & adapter, const _Value& value)2482 ArcMap(const OrienterBase<GR, DM>& adapter, const V& value) 2492 2483 : Parent(*adapter._graph, value) { } 2493 2484 … … 2508 2499 protected: 2509 2500 Graph* _graph; 2510 DirectionMap* _direction; 2511 2512 void setDirectionMap(DirectionMap& direction) { 2501 DM* _direction; 2502 2503 void initialize(GR& graph, DM& direction) { 2504 _graph = &graph; 2513 2505 _direction = &direction; 2514 }2515 2516 void setGraph(Graph& graph) {2517 _graph = &graph;2518 2506 } 2519 2507 … … 2573 2561 /// 2574 2562 /// Constructor of the adaptor. 2575 Orienter(Graph& graph, DirectionMap& direction) { 2576 setGraph(graph); 2577 setDirectionMap(direction); 2563 Orienter(GR& graph, DM& direction) { 2564 Parent::initialize(graph, direction); 2578 2565 } 2579 2566 … … 2595 2582 template<typename GR, typename DM> 2596 2583 Orienter<const GR, DM> 2597 orienter(const GR& graph, DM& direction _map) {2598 return Orienter<const GR, DM>(graph, direction _map);2584 orienter(const GR& graph, DM& direction) { 2585 return Orienter<const GR, DM>(graph, direction); 2599 2586 } 2600 2587 2601 2588 template<typename GR, typename DM> 2602 2589 Orienter<const GR, const DM> 2603 orienter(const GR& graph, const DM& direction _map) {2604 return Orienter<const GR, const DM>(graph, direction _map);2590 orienter(const GR& graph, const DM& direction) { 2591 return Orienter<const GR, const DM>(graph, direction); 2605 2592 } 2606 2593 2607 2594 namespace _adaptor_bits { 2608 2595 2609 template<typename Digraph, 2610 typename CapacityMap, 2611 typename FlowMap, 2612 typename Tolerance> 2596 template <typename DGR, typename CM, typename FM, typename TL> 2613 2597 class ResForwardFilter { 2614 2598 public: 2615 2599 2616 typedef typename D igraph::Arc Key;2600 typedef typename DGR::Arc Key; 2617 2601 typedef bool Value; 2618 2602 2619 2603 private: 2620 2604 2621 const CapacityMap* _capacity; 2622 const FlowMap* _flow; 2623 Tolerance _tolerance; 2605 const CM* _capacity; 2606 const FM* _flow; 2607 TL _tolerance; 2608 2624 2609 public: 2625 2610 2626 ResForwardFilter(const C apacityMap& capacity, const FlowMap& flow,2627 const T olerance& tolerance = Tolerance())2611 ResForwardFilter(const CM& capacity, const FM& flow, 2612 const TL& tolerance = TL()) 2628 2613 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2629 2614 2630 bool operator[](const typename D igraph::Arc& a) const {2615 bool operator[](const typename DGR::Arc& a) const { 2631 2616 return _tolerance.positive((*_capacity)[a]  (*_flow)[a]); 2632 2617 } 2633 2618 }; 2634 2619 2635 template<typename Digraph, 2636 typename CapacityMap, 2637 typename FlowMap, 2638 typename Tolerance> 2620 template<typename DGR,typename CM, typename FM, typename TL> 2639 2621 class ResBackwardFilter { 2640 2622 public: 2641 2623 2642 typedef typename D igraph::Arc Key;2624 typedef typename DGR::Arc Key; 2643 2625 typedef bool Value; 2644 2626 2645 2627 private: 2646 2628 2647 const C apacityMap* _capacity;2648 const F lowMap* _flow;2649 T olerance_tolerance;2629 const CM* _capacity; 2630 const FM* _flow; 2631 TL _tolerance; 2650 2632 2651 2633 public: 2652 2634 2653 ResBackwardFilter(const C apacityMap& capacity, const FlowMap& flow,2654 const T olerance& tolerance = Tolerance())2635 ResBackwardFilter(const CM& capacity, const FM& flow, 2636 const TL& tolerance = TL()) 2655 2637 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2656 2638 2657 bool operator[](const typename D igraph::Arc& a) const {2639 bool operator[](const typename DGR::Arc& a) const { 2658 2640 return _tolerance.positive((*_flow)[a]); 2659 2641 } … … 2682 2664 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. 2683 2665 /// 2684 /// \tparam GR The type of the adapted digraph.2666 /// \tparam DGR The type of the adapted digraph. 2685 2667 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 2686 2668 /// It is implicitly \c const. … … 2704 2686 /// is convertible to the \c Arc type of the adapted digraph. 2705 2687 #ifdef DOXYGEN 2706 template<typename GR, typename CM, typename FM, typename TL>2688 template<typename DGR, typename CM, typename FM, typename TL> 2707 2689 class ResidualDigraph 2708 2690 #else 2709 template<typename GR,2710 typename CM = typename GR::template ArcMap<int>,2691 template<typename DGR, 2692 typename CM = typename DGR::template ArcMap<int>, 2711 2693 typename FM = CM, 2712 2694 typename TL = Tolerance<typename CM::Value> > 2713 class ResidualDigraph : 2714 public FilterArcs< 2715 Undirector<const GR>, 2716 typename Undirector<const GR>::template CombinedArcMap< 2717 _adaptor_bits::ResForwardFilter<const GR, CM, FM, TL>, 2718 _adaptor_bits::ResBackwardFilter<const GR, CM, FM, TL> > > 2695 class ResidualDigraph 2696 : public SubDigraph< 2697 Undirector<const DGR>, 2698 ConstMap<typename DGR::Node, Const<bool, true> >, 2699 typename Undirector<const DGR>::template CombinedArcMap< 2700 _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>, 2701 _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > > 2719 2702 #endif 2720 2703 { … … 2722 2705 2723 2706 /// The type of the underlying digraph. 2724 typedef GR Digraph;2707 typedef DGR Digraph; 2725 2708 /// The type of the capacity map. 2726 2709 typedef CM CapacityMap; … … 2737 2720 typedef Undirector<const Digraph> Undirected; 2738 2721 2739 typedef _adaptor_bits::ResForwardFilter<const Digraph, CapacityMap, 2740 FlowMap, Tolerance> ForwardFilter; 2741 2742 typedef _adaptor_bits::ResBackwardFilter<const Digraph, CapacityMap, 2743 FlowMap, Tolerance> BackwardFilter; 2722 typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter; 2723 2724 typedef _adaptor_bits::ResForwardFilter<const DGR, CM, 2725 FM, TL> ForwardFilter; 2726 2727 typedef _adaptor_bits::ResBackwardFilter<const DGR, CM, 2728 FM, TL> BackwardFilter; 2744 2729 2745 2730 typedef typename Undirected:: 2746 2731 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter; 2747 2732 2748 typedef FilterArcs<Undirected, ArcFilter> Parent;2733 typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent; 2749 2734 2750 2735 const CapacityMap* _capacity; … … 2752 2737 2753 2738 Undirected _graph; 2739 NodeFilter _node_filter; 2754 2740 ForwardFilter _forward_filter; 2755 2741 BackwardFilter _backward_filter; … … 2762 2748 /// Constructor of the residual digraph adaptor. The parameters are the 2763 2749 /// digraph, the capacity map, the flow map, and a tolerance object. 2764 ResidualDigraph(const Digraph& digraph, const CapacityMap& capacity, 2765 FlowMap& flow, const Tolerance& tolerance = Tolerance()) 2766 : Parent(), _capacity(&capacity), _flow(&flow), _graph(digraph), 2750 ResidualDigraph(const DGR& digraph, const CM& capacity, 2751 FM& flow, const TL& tolerance = Tolerance()) 2752 : Parent(), _capacity(&capacity), _flow(&flow), 2753 _graph(digraph), _node_filter(), 2767 2754 _forward_filter(capacity, flow, tolerance), 2768 2755 _backward_filter(capacity, flow, tolerance), 2769 2756 _arc_filter(_forward_filter, _backward_filter) 2770 2757 { 2771 Parent::setDigraph(_graph); 2772 Parent::setArcFilterMap(_arc_filter); 2758 Parent::initialize(_graph, _node_filter, _arc_filter); 2773 2759 } 2774 2760 … … 2846 2832 2847 2833 /// Constructor 2848 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {} 2834 ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 2835 : _adaptor(&adaptor) {} 2849 2836 2850 2837 /// Returns the value associated with the given residual arc … … 2866 2853 /// \brief Returns a (readonly) Residual adaptor 2867 2854 /// 2868 /// This function just returns a (readonly) \ref Residual adaptor.2855 /// This function just returns a (readonly) \ref ResidualDigraph adaptor. 2869 2856 /// \ingroup graph_adaptors 2870 /// \relates Residual 2871 template<typenameGR, typename CM, typename FM>2872 ResidualDigraph< GR, CM, FM>2873 residualDigraph(const GR& digraph, const CM& capacity_map, FM& flow_map) {2874 return ResidualDigraph< GR, CM, FM> (digraph, capacity_map, flow_map);2857 /// \relates ResidualDigraph 2858 template<typename DGR, typename CM, typename FM> 2859 ResidualDigraph<DGR, CM, FM> 2860 residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) { 2861 return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map); 2875 2862 } 2876 2863 2877 2864 2878 template <typename _Digraph>2865 template <typename DGR> 2879 2866 class SplitNodesBase { 2880 2867 public: 2881 2868 2882 typedef _DigraphDigraph;2883 typedef DigraphAdaptorBase<const _Digraph> Parent;2869 typedef DGR Digraph; 2870 typedef DigraphAdaptorBase<const DGR> Parent; 2884 2871 typedef SplitNodesBase Adaptor; 2885 2872 2886 typedef typename D igraph::Node DigraphNode;2887 typedef typename D igraph::Arc DigraphArc;2873 typedef typename DGR::Node DigraphNode; 2874 typedef typename DGR::Arc DigraphArc; 2888 2875 2889 2876 class Node; … … 3149 3136 private: 3150 3137 3151 template <typename _Value>3138 template <typename V> 3152 3139 class NodeMapBase 3153 : public MapTraits<typename Parent::template NodeMap< _Value> > {3154 typedef typename Parent::template NodeMap< _Value> NodeImpl;3140 : public MapTraits<typename Parent::template NodeMap<V> > { 3141 typedef typename Parent::template NodeMap<V> NodeImpl; 3155 3142 public: 3156 3143 typedef Node Key; 3157 typedef _ValueValue;3144 typedef V Value; 3158 3145 typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag; 3159 3146 typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue; … … 3162 3149 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference; 3163 3150 3164 NodeMapBase(const Adaptor& adaptor)3151 NodeMapBase(const SplitNodesBase<DGR>& adaptor) 3165 3152 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {} 3166 NodeMapBase(const Adaptor& adaptor, const Value& value)3153 NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value) 3167 3154 : _in_map(*adaptor._digraph, value), 3168 3155 _out_map(*adaptor._digraph, value) {} 3169 3156 3170 void set(const Node& key, const V alue& val) {3171 if ( Adaptor::inNode(key)) { _in_map.set(key, val); }3157 void set(const Node& key, const V& val) { 3158 if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); } 3172 3159 else {_out_map.set(key, val); } 3173 3160 } 3174 3161 3175 3162 ReturnValue operator[](const Node& key) { 3176 if ( Adaptor::inNode(key)) { return _in_map[key]; }3163 if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; } 3177 3164 else { return _out_map[key]; } 3178 3165 } … … 3187 3174 }; 3188 3175 3189 template <typename _Value>3176 template <typename V> 3190 3177 class ArcMapBase 3191 : public MapTraits<typename Parent::template ArcMap< _Value> > {3192 typedef typename Parent::template ArcMap< _Value> ArcImpl;3193 typedef typename Parent::template NodeMap< _Value> NodeImpl;3178 : public MapTraits<typename Parent::template ArcMap<V> > { 3179 typedef typename Parent::template ArcMap<V> ArcImpl; 3180 typedef typename Parent::template NodeMap<V> NodeImpl; 3194 3181 public: 3195 3182 typedef Arc Key; 3196 typedef _ValueValue;3183 typedef V Value; 3197 3184 typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag; 3198 3185 typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue; … … 3201 3188 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference; 3202 3189 3203 ArcMapBase(const Adaptor& adaptor)3190 ArcMapBase(const SplitNodesBase<DGR>& adaptor) 3204 3191 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {} 3205 ArcMapBase(const Adaptor& adaptor, const Value& value)3192 ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value) 3206 3193 : _arc_map(*adaptor._digraph, value), 3207 3194 _node_map(*adaptor._digraph, value) {} 3208 3195 3209 void set(const Arc& key, const V alue& val) {3210 if ( Adaptor::origArc(key)) {3196 void set(const Arc& key, const V& val) { 3197 if (SplitNodesBase<DGR>::origArc(key)) { 3211 3198 _arc_map.set(key._item.first(), val); 3212 3199 } else { … … 3216 3203 3217 3204 ReturnValue operator[](const Arc& key) { 3218 if ( Adaptor::origArc(key)) {3205 if (SplitNodesBase<DGR>::origArc(key)) { 3219 3206 return _arc_map[key._item.first()]; 3220 3207 } else { … … 3224 3211 3225 3212 ConstReturnValue operator[](const Arc& key) const { 3226 if ( Adaptor::origArc(key)) {3213 if (SplitNodesBase<DGR>::origArc(key)) { 3227 3214 return _arc_map[key._item.first()]; 3228 3215 } else { … … 3238 3225 public: 3239 3226 3240 template <typename _Value>3227 template <typename V> 3241 3228 class NodeMap 3242 : public SubMapExtender< Adaptor, NodeMapBase<_Value> >3229 : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > 3243 3230 { 3244 3231 public: 3245 typedef _ValueValue;3246 typedef SubMapExtender< Adaptor, NodeMapBase<Value> > Parent;3247 3248 NodeMap(const Adaptor& adaptor)3232 typedef V Value; 3233 typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<Value> > Parent; 3234 3235 NodeMap(const SplitNodesBase<DGR>& adaptor) 3249 3236 : Parent(adaptor) {} 3250 3237 3251 NodeMap(const Adaptor& adaptor, const Value& value)3238 NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value) 3252 3239 : Parent(adaptor, value) {} 3253 3240 … … 3264 3251 }; 3265 3252 3266 template <typename _Value>3253 template <typename V> 3267 3254 class ArcMap 3268 : public SubMapExtender< Adaptor, ArcMapBase<_Value> >3255 : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > 3269 3256 { 3270 3257 public: 3271 typedef _ValueValue;3272 typedef SubMapExtender< Adaptor, ArcMapBase<Value> > Parent;3273 3274 ArcMap(const Adaptor& adaptor)3258 typedef V Value; 3259 typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<Value> > Parent; 3260 3261 ArcMap(const SplitNodesBase<DGR>& adaptor) 3275 3262 : Parent(adaptor) {} 3276 3263 3277 ArcMap(const Adaptor& adaptor, const Value& value)3264 ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value) 3278 3265 : Parent(adaptor, value) {} 3279 3266 … … 3294 3281 SplitNodesBase() : _digraph(0) {} 3295 3282 3296 D igraph* _digraph;3297 3298 void setDigraph(Digraph& digraph) {3283 DGR* _digraph; 3284 3285 void initialize(Digraph& digraph) { 3299 3286 _digraph = &digraph; 3300 3287 } … … 3323 3310 /// in the adaptor. 3324 3311 /// 3325 /// \tparam GR The type of the adapted digraph.3312 /// \tparam DGR The type of the adapted digraph. 3326 3313 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 3327 3314 /// It is implicitly \c const. … … 3329 3316 /// \note The \c Node type of this adaptor is converible to the \c Node 3330 3317 /// type of the adapted digraph. 3331 template <typename GR>3318 template <typename DGR> 3332 3319 #ifdef DOXYGEN 3333 3320 class SplitNodes { 3334 3321 #else 3335 3322 class SplitNodes 3336 : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {3323 : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > { 3337 3324 #endif 3338 3325 public: 3339 typedef GR Digraph;3340 typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent;3341 3342 typedef typename D igraph::Node DigraphNode;3343 typedef typename D igraph::Arc DigraphArc;3326 typedef DGR Digraph; 3327 typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent; 3328 3329 typedef typename DGR::Node DigraphNode; 3330 typedef typename DGR::Arc DigraphArc; 3344 3331 3345 3332 typedef typename Parent::Node Node; … … 3349 3336 /// 3350 3337 /// Constructor of the adaptor. 3351 SplitNodes(const D igraph& g) {3352 Parent:: setDigraph(g);3338 SplitNodes(const DGR& g) { 3339 Parent::initialize(g); 3353 3340 } 3354 3341 … … 3442 3429 /// Returns the value associated with the given key. 3443 3430 Value operator[](const Key& key) const { 3444 if ( Parent::inNode(key)) {3431 if (SplitNodesBase<const DGR>::inNode(key)) { 3445 3432 return _in_map[key]; 3446 3433 } else { … … 3451 3438 /// Returns a reference to the value associated with the given key. 3452 3439 Value& operator[](const Key& key) { 3453 if ( Parent::inNode(key)) {3440 if (SplitNodesBase<const DGR>::inNode(key)) { 3454 3441 return _in_map[key]; 3455 3442 } else { … … 3460 3447 /// Sets the value associated with the given key. 3461 3448 void set(const Key& key, const Value& value) { 3462 if ( Parent::inNode(key)) {3449 if (SplitNodesBase<const DGR>::inNode(key)) { 3463 3450 _in_map.set(key, value); 3464 3451 } else { … … 3531 3518 /// Returns the value associated with the given key. 3532 3519 Value operator[](const Key& arc) const { 3533 if ( Parent::origArc(arc)) {3520 if (SplitNodesBase<const DGR>::origArc(arc)) { 3534 3521 return _arc_map[arc]; 3535 3522 } else { … … 3540 3527 /// Returns a reference to the value associated with the given key. 3541 3528 Value& operator[](const Key& arc) { 3542 if ( Parent::origArc(arc)) {3529 if (SplitNodesBase<const DGR>::origArc(arc)) { 3543 3530 return _arc_map[arc]; 3544 3531 } else { … … 3549 3536 /// Sets the value associated with the given key. 3550 3537 void set(const Arc& arc, const Value& val) { 3551 if ( Parent::origArc(arc)) {3538 if (SplitNodesBase<const DGR>::origArc(arc)) { 3552 3539 _arc_map.set(arc, val); 3553 3540 } else { … … 3595 3582 /// \ingroup graph_adaptors 3596 3583 /// \relates SplitNodes 3597 template<typename GR>3598 SplitNodes< GR>3599 splitNodes(const GR& digraph) {3600 return SplitNodes< GR>(digraph);3584 template<typename DGR> 3585 SplitNodes<DGR> 3586 splitNodes(const DGR& digraph) { 3587 return SplitNodes<DGR>(digraph); 3601 3588 } 3602 3589 3590 #undef LEMON_SCOPE_FIX 3591 3603 3592 } //namespace lemon 3604 3593
Note: See TracChangeset
for help on using the changeset viewer.