Changes in lemon/adaptors.h [487:acfb0f24d178:703:cb38ccedd2c1] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/adaptors.h
r487 r703 31 31 32 32 #include <lemon/bits/graph_adaptor_extender.h> 33 #include <lemon/bits/map_extender.h> 33 34 #include <lemon/tolerance.h> 34 35 … … 37 38 namespace lemon { 38 39 39 template<typename _Digraph> 40 #ifdef _MSC_VER 41 #define LEMON_SCOPE_FIX(OUTER, NESTED) OUTER::NESTED 42 #else 43 #define LEMON_SCOPE_FIX(OUTER, NESTED) typename OUTER::template NESTED 44 #endif 45 46 template<typename DGR> 40 47 class DigraphAdaptorBase { 41 48 public: 42 typedef _DigraphDigraph;49 typedef DGR Digraph; 43 50 typedef DigraphAdaptorBase Adaptor; 44 typedef Digraph ParentDigraph;45 51 46 52 protected: 47 D igraph* _digraph;53 DGR* _digraph; 48 54 DigraphAdaptorBase() : _digraph(0) { } 49 void setDigraph(Digraph& digraph) { _digraph = &digraph; }50 51 public: 52 DigraphAdaptorBase(D igraph& digraph) : _digraph(&digraph) { }53 54 typedef typename D igraph::Node Node;55 typedef typename D igraph::Arc Arc;55 void initialize(DGR& digraph) { _digraph = &digraph; } 56 57 public: 58 DigraphAdaptorBase(DGR& digraph) : _digraph(&digraph) { } 59 60 typedef typename DGR::Node Node; 61 typedef typename DGR::Arc Arc; 56 62 57 63 void first(Node& i) const { _digraph->first(i); } … … 68 74 Node target(const Arc& a) const { return _digraph->target(a); } 69 75 70 typedef NodeNumTagIndicator<D igraph> NodeNumTag;76 typedef NodeNumTagIndicator<DGR> NodeNumTag; 71 77 int nodeNum() const { return _digraph->nodeNum(); } 72 78 73 typedef ArcNumTagIndicator<D igraph> ArcNumTag;79 typedef ArcNumTagIndicator<DGR> ArcNumTag; 74 80 int arcNum() const { return _digraph->arcNum(); } 75 81 76 typedef FindArcTagIndicator<D igraph> FindArcTag;82 typedef FindArcTagIndicator<DGR> FindArcTag; 77 83 Arc findArc(const Node& u, const Node& v, const Arc& prev = INVALID) const { 78 84 return _digraph->findArc(u, v, prev); … … 96 102 int maxArcId() const { return _digraph->maxArcId(); } 97 103 98 typedef typename ItemSetTraits<D igraph, Node>::ItemNotifier NodeNotifier;104 typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier; 99 105 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 100 106 101 typedef typename ItemSetTraits<D igraph, Arc>::ItemNotifier ArcNotifier;107 typedef typename ItemSetTraits<DGR, Arc>::ItemNotifier ArcNotifier; 102 108 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Arc()); } 103 109 104 template <typename _Value> 105 class NodeMap : public Digraph::template NodeMap<_Value> { 110 template <typename V> 111 class NodeMap : public DGR::template NodeMap<V> { 112 typedef typename DGR::template NodeMap<V> Parent; 113 106 114 public: 107 108 typedef typename Digraph::template NodeMap<_Value> Parent;109 110 115 explicit NodeMap(const Adaptor& adaptor) 111 116 : Parent(*adaptor._digraph) {} 112 113 NodeMap(const Adaptor& adaptor, const _Value& value) 117 NodeMap(const Adaptor& adaptor, const V& value) 114 118 : Parent(*adaptor._digraph, value) { } 115 119 … … 127 131 }; 128 132 129 template <typename _Value> 130 class ArcMap : public Digraph::template ArcMap<_Value> { 133 template <typename V> 134 class ArcMap : public DGR::template ArcMap<V> { 135 typedef typename DGR::template ArcMap<V> Parent; 136 131 137 public: 132 133 typedef typename Digraph::template ArcMap<_Value> Parent; 134 135 explicit ArcMap(const Adaptor& adaptor) 138 explicit ArcMap(const DigraphAdaptorBase<DGR>& adaptor) 136 139 : Parent(*adaptor._digraph) {} 137 138 ArcMap(const Adaptor& adaptor, const _Value& value) 140 ArcMap(const DigraphAdaptorBase<DGR>& adaptor, const V& value) 139 141 : Parent(*adaptor._digraph, value) {} 140 142 … … 154 156 }; 155 157 156 template<typename _Graph>158 template<typename GR> 157 159 class GraphAdaptorBase { 158 160 public: 159 typedef _Graph Graph; 160 typedef Graph ParentGraph; 161 typedef GR Graph; 161 162 162 163 protected: 163 G raph* _graph;164 GR* _graph; 164 165 165 166 GraphAdaptorBase() : _graph(0) {} 166 167 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;168 void initialize(GR& graph) { _graph = &graph; } 169 170 public: 171 GraphAdaptorBase(GR& graph) : _graph(&graph) {} 172 173 typedef typename GR::Node Node; 174 typedef typename GR::Arc Arc; 175 typedef typename GR::Edge Edge; 175 176 176 177 void first(Node& i) const { _graph->first(i); } … … 240 241 int maxEdgeId() const { return _graph->maxEdgeId(); } 241 242 242 typedef typename ItemSetTraits<G raph, Node>::ItemNotifier NodeNotifier;243 typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier; 243 244 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 244 245 245 typedef typename ItemSetTraits<G raph, Arc>::ItemNotifier ArcNotifier;246 typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier; 246 247 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 247 248 248 typedef typename ItemSetTraits<G raph, Edge>::ItemNotifier EdgeNotifier;249 typedef typename ItemSetTraits<GR, Edge>::ItemNotifier EdgeNotifier; 249 250 EdgeNotifier& notifier(Edge) const { return _graph->notifier(Edge()); } 250 251 251 template <typename _Value> 252 class NodeMap : public Graph::template NodeMap<_Value> { 252 template <typename V> 253 class NodeMap : public GR::template NodeMap<V> { 254 typedef typename GR::template NodeMap<V> Parent; 255 253 256 public: 254 typedef typename Graph::template NodeMap<_Value> Parent; 255 explicit NodeMap(const GraphAdaptorBase<Graph>& adapter) 257 explicit NodeMap(const GraphAdaptorBase<GR>& adapter) 256 258 : Parent(*adapter._graph) {} 257 NodeMap(const GraphAdaptorBase<G raph>& adapter, const _Value& value)259 NodeMap(const GraphAdaptorBase<GR>& adapter, const V& value) 258 260 : Parent(*adapter._graph, value) {} 259 261 … … 271 273 }; 272 274 273 template <typename _Value> 274 class ArcMap : public Graph::template ArcMap<_Value> { 275 template <typename V> 276 class ArcMap : public GR::template ArcMap<V> { 277 typedef typename GR::template ArcMap<V> Parent; 278 275 279 public: 276 typedef typename Graph::template ArcMap<_Value> Parent; 277 explicit ArcMap(const GraphAdaptorBase<Graph>& adapter) 280 explicit ArcMap(const GraphAdaptorBase<GR>& adapter) 278 281 : Parent(*adapter._graph) {} 279 ArcMap(const GraphAdaptorBase<G raph>& adapter, const _Value& value)282 ArcMap(const GraphAdaptorBase<GR>& adapter, const V& value) 280 283 : Parent(*adapter._graph, value) {} 281 284 … … 292 295 }; 293 296 294 template <typename _Value> 295 class EdgeMap : public Graph::template EdgeMap<_Value> { 297 template <typename V> 298 class EdgeMap : public GR::template EdgeMap<V> { 299 typedef typename GR::template EdgeMap<V> Parent; 300 296 301 public: 297 typedef typename Graph::template EdgeMap<_Value> Parent; 298 explicit EdgeMap(const GraphAdaptorBase<Graph>& adapter) 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 _Digraph Digraph;321 typedef D igraphAdaptorBase<_Digraph> Parent;321 template <typename DGR> 322 class ReverseDigraphBase : public DigraphAdaptorBase<DGR> { 323 typedef DigraphAdaptorBase<DGR> Parent; 324 public: 325 typedef DGR Digraph; 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 376 typedef DigraphAdaptorExtender<ReverseDigraphBase<DGR> > Parent; 372 377 public: 373 378 /// The type of the adapted digraph. 374 typedef GR Digraph; 375 typedef DigraphAdaptorExtender<ReverseDigraphBase<GR> > Parent; 379 typedef DGR Digraph; 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 _DigraphDigraph;404 typedef _NodeFilterMapNodeFilterMap;405 typedef _ArcFilterMapArcFilterMap;403 template <typename DGR, typename NF, typename AF, bool ch = true> 404 class SubDigraphBase : public DigraphAdaptorBase<DGR> { 405 typedef DigraphAdaptorBase<DGR> Parent; 406 public: 407 typedef DGR Digraph; 408 typedef NF NodeFilterMap; 409 typedef AF ArcFilterMap; 406 410 407 411 typedef SubDigraphBase Adaptor; 408 typedef DigraphAdaptorBase<_Digraph> 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>)> { 511 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 512 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent; 513 506 514 public: 507 typedef _Value Value; 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) {} 515 typedef V Value; 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) {} 515 521 516 522 private: … … 521 527 template <typename CMap> 522 528 NodeMap& operator=(const CMap& cmap) { 523 MapParent::operator=(cmap);529 Parent::operator=(cmap); 524 530 return *this; 525 531 } 526 532 }; 527 533 528 template <typename _Value> 529 class ArcMap : public SubMapExtender<Adaptor, 530 typename Parent::template ArcMap<_Value> > { 534 template <typename V> 535 class ArcMap 536 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 537 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> { 538 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 539 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent; 540 531 541 public: 532 typedef _Value Value; 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) {} 542 typedef V Value; 543 544 ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor) 545 : Parent(adaptor) {} 546 ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value) 547 : Parent(adaptor, value) {} 540 548 541 549 private: … … 546 554 template <typename CMap> 547 555 ArcMap& operator=(const CMap& cmap) { 548 MapParent::operator=(cmap);556 Parent::operator=(cmap); 549 557 return *this; 550 558 } … … 553 561 }; 554 562 555 template <typename _Digraph, typename _NodeFilterMap, typename _ArcFilterMap> 556 class SubDigraphBase<_Digraph, _NodeFilterMap, _ArcFilterMap, false> 557 : public DigraphAdaptorBase<_Digraph> { 558 public: 559 typedef _Digraph Digraph; 560 typedef _NodeFilterMap NodeFilterMap; 561 typedef _ArcFilterMap ArcFilterMap; 563 template <typename DGR, typename NF, typename AF> 564 class SubDigraphBase<DGR, NF, AF, false> 565 : public DigraphAdaptorBase<DGR> { 566 typedef DigraphAdaptorBase<DGR> Parent; 567 public: 568 typedef DGR Digraph; 569 typedef NF NodeFilterMap; 570 typedef AF ArcFilterMap; 562 571 563 572 typedef SubDigraphBase Adaptor; 564 typedef DigraphAdaptorBase<Digraph> Parent;565 573 protected: 566 N odeFilterMap* _node_filter;567 A rcFilterMap* _arc_filter;574 NF* _node_filter; 575 AF* _arc_filter; 568 576 SubDigraphBase() 569 577 : Parent(), _node_filter(0), _arc_filter(0) { } 570 578 571 void setNodeFilterMap(NodeFilterMap& node_filter) { 579 void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) { 580 Parent::initialize(digraph); 572 581 _node_filter = &node_filter; 573 } 574 void setArcFilterMap(ArcFilterMap& arc_filter) { 575 _arc_filter = &arc_filter; 582 _arc_filter = &arc_filter; 576 583 } 577 584 … … 628 635 typedef False ArcNumTag; 629 636 630 typedef FindArcTagIndicator<D igraph> FindArcTag;637 typedef FindArcTagIndicator<DGR> FindArcTag; 631 638 Arc findArc(const Node& source, const Node& target, 632 639 const Arc& prev = INVALID) const { … … 641 648 } 642 649 643 template <typename _Value> 644 class NodeMap : public SubMapExtender<Adaptor, 645 typename Parent::template NodeMap<_Value> > { 650 template <typename V> 651 class NodeMap 652 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 653 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> { 654 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 655 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent; 656 646 657 public: 647 typedef _Value Value; 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) {} 658 typedef V Value; 659 660 NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor) 661 : Parent(adaptor) {} 662 NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value) 663 : Parent(adaptor, value) {} 655 664 656 665 private: … … 661 670 template <typename CMap> 662 671 NodeMap& operator=(const CMap& cmap) { 663 MapParent::operator=(cmap);672 Parent::operator=(cmap); 664 673 return *this; 665 674 } 666 675 }; 667 676 668 template <typename _Value> 669 class ArcMap : public SubMapExtender<Adaptor, 670 typename Parent::template ArcMap<_Value> > { 677 template <typename V> 678 class ArcMap 679 : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 680 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> { 681 typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 682 LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent; 683 671 684 public: 672 typedef _Value Value; 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) {} 685 typedef V Value; 686 687 ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor) 688 : Parent(adaptor) {} 689 ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value) 690 : Parent(adaptor, value) {} 680 691 681 692 private: … … 686 697 template <typename CMap> 687 698 ArcMap& operator=(const CMap& cmap) { 688 MapParent::operator=(cmap);699 Parent::operator=(cmap); 689 700 return *this; 690 701 } … … 709 720 /// parameter is set to be \c const. 710 721 /// 711 /// \tparam GR The type of the adapted digraph.722 /// \tparam DGR The type of the adapted digraph. 712 723 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 713 724 /// It can also be specified to be \c const. … … 715 726 /// It must be a \c bool (or convertible) node map of the 716 727 /// adapted digraph. The default type is 717 /// \ref concepts::Digraph::NodeMap " GR::NodeMap<bool>".728 /// \ref concepts::Digraph::NodeMap "DGR::NodeMap<bool>". 718 729 /// \tparam AF The type of the arc filter map. 719 730 /// It must be \c bool (or convertible) arc map of the 720 731 /// adapted digraph. The default type is 721 /// \ref concepts::Digraph::ArcMap " GR::ArcMap<bool>".732 /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>". 722 733 /// 723 734 /// \note The \c Node and \c Arc types of this adaptor and the adapted … … 727 738 /// \see FilterArcs 728 739 #ifdef DOXYGEN 729 template<typename GR, typename NF, typename AF>740 template<typename DGR, typename NF, typename AF> 730 741 class SubDigraph { 731 742 #else 732 template<typename GR,733 typename NF = typename GR::template NodeMap<bool>,734 typename AF = typename GR::template ArcMap<bool> >743 template<typename DGR, 744 typename NF = typename DGR::template NodeMap<bool>, 745 typename AF = typename DGR::template ArcMap<bool> > 735 746 class SubDigraph : 736 public DigraphAdaptorExtender<SubDigraphBase< GR, NF, AF, true> > {747 public DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > { 737 748 #endif 738 749 public: 739 750 /// The type of the adapted digraph. 740 typedef GR Digraph;751 typedef DGR Digraph; 741 752 /// The type of the node filter map. 742 753 typedef NF NodeFilterMap; … … 744 755 typedef AF ArcFilterMap; 745 756 746 typedef DigraphAdaptorExtender<SubDigraphBase< GR, NF, AF, true> >757 typedef DigraphAdaptorExtender<SubDigraphBase<DGR, NF, AF, true> > 747 758 Parent; 748 759 … … 758 769 /// Creates a subdigraph for the given digraph with the 759 770 /// 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); 771 SubDigraph(DGR& digraph, NF& node_filter, AF& arc_filter) { 772 Parent::initialize(digraph, node_filter, arc_filter); 765 773 } 766 774 … … 824 832 /// \ingroup graph_adaptors 825 833 /// \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);834 template<typename DGR, typename NF, typename AF> 835 SubDigraph<const DGR, NF, AF> 836 subDigraph(const DGR& digraph, 837 NF& node_filter, AF& arc_filter) { 838 return SubDigraph<const DGR, NF, AF> 839 (digraph, node_filter, arc_filter); 832 840 } 833 841 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);842 template<typename DGR, typename NF, typename AF> 843 SubDigraph<const DGR, const NF, AF> 844 subDigraph(const DGR& digraph, 845 const NF& node_filter, AF& arc_filter) { 846 return SubDigraph<const DGR, const NF, AF> 847 (digraph, node_filter, arc_filter); 840 848 } 841 849 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);850 template<typename DGR, typename NF, typename AF> 851 SubDigraph<const DGR, NF, const AF> 852 subDigraph(const DGR& digraph, 853 NF& node_filter, const AF& arc_filter) { 854 return SubDigraph<const DGR, NF, const AF> 855 (digraph, node_filter, arc_filter); 848 856 } 849 857 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);858 template<typename DGR, typename NF, typename AF> 859 SubDigraph<const DGR, const NF, const AF> 860 subDigraph(const DGR& digraph, 861 const NF& node_filter, const AF& arc_filter) { 862 return SubDigraph<const DGR, const NF, const AF> 863 (digraph, node_filter, arc_filter); 856 864 } 857 865 858 866 859 template <typename _Graph, typename _NodeFilterMap,860 typename _EdgeFilterMap, bool _checked = true>861 class SubGraphBase : public GraphAdaptorBase<_Graph> {862 public: 863 typedef _GraphGraph;864 typedef _NodeFilterMapNodeFilterMap;865 typedef _EdgeFilterMapEdgeFilterMap;867 template <typename GR, typename NF, typename EF, bool ch = true> 868 class SubGraphBase : public GraphAdaptorBase<GR> { 869 typedef GraphAdaptorBase<GR> Parent; 870 public: 871 typedef GR Graph; 872 typedef NF NodeFilterMap; 873 typedef EF EdgeFilterMap; 866 874 867 875 typedef SubGraphBase Adaptor; 868 typedef GraphAdaptorBase<_Graph> Parent;869 876 protected: 870 877 871 N odeFilterMap* _node_filter_map;872 E dgeFilterMap* _edge_filter_map;878 NF* _node_filter; 879 EF* _edge_filter; 873 880 874 881 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; 882 : Parent(), _node_filter(0), _edge_filter(0) { } 883 884 void initialize(GR& graph, NF& node_filter, EF& edge_filter) { 885 Parent::initialize(graph); 886 _node_filter = &node_filter; 887 _edge_filter = &edge_filter; 882 888 } 883 889 … … 890 896 void first(Node& i) const { 891 897 Parent::first(i); 892 while (i!=INVALID && !(*_node_filter _map)[i]) Parent::next(i);898 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 893 899 } 894 900 895 901 void first(Arc& i) const { 896 902 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)]))903 while (i!=INVALID && (!(*_edge_filter)[i] 904 || !(*_node_filter)[Parent::source(i)] 905 || !(*_node_filter)[Parent::target(i)])) 900 906 Parent::next(i); 901 907 } … … 903 909 void first(Edge& i) const { 904 910 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)]))911 while (i!=INVALID && (!(*_edge_filter)[i] 912 || !(*_node_filter)[Parent::u(i)] 913 || !(*_node_filter)[Parent::v(i)])) 908 914 Parent::next(i); 909 915 } … … 911 917 void firstIn(Arc& i, const Node& n) const { 912 918 Parent::firstIn(i, n); 913 while (i!=INVALID && (!(*_edge_filter _map)[i]914 || !(*_node_filter _map)[Parent::source(i)]))919 while (i!=INVALID && (!(*_edge_filter)[i] 920 || !(*_node_filter)[Parent::source(i)])) 915 921 Parent::nextIn(i); 916 922 } … … 918 924 void firstOut(Arc& i, const Node& n) const { 919 925 Parent::firstOut(i, n); 920 while (i!=INVALID && (!(*_edge_filter _map)[i]921 || !(*_node_filter _map)[Parent::target(i)]))926 while (i!=INVALID && (!(*_edge_filter)[i] 927 || !(*_node_filter)[Parent::target(i)])) 922 928 Parent::nextOut(i); 923 929 } … … 925 931 void firstInc(Edge& i, bool& d, const Node& n) const { 926 932 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)]))933 while (i!=INVALID && (!(*_edge_filter)[i] 934 || !(*_node_filter)[Parent::u(i)] 935 || !(*_node_filter)[Parent::v(i)])) 930 936 Parent::nextInc(i, d); 931 937 } … … 933 939 void next(Node& i) const { 934 940 Parent::next(i); 935 while (i!=INVALID && !(*_node_filter _map)[i]) Parent::next(i);941 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 936 942 } 937 943 938 944 void next(Arc& i) const { 939 945 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)]))946 while (i!=INVALID && (!(*_edge_filter)[i] 947 || !(*_node_filter)[Parent::source(i)] 948 || !(*_node_filter)[Parent::target(i)])) 943 949 Parent::next(i); 944 950 } … … 946 952 void next(Edge& i) const { 947 953 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)]))954 while (i!=INVALID && (!(*_edge_filter)[i] 955 || !(*_node_filter)[Parent::u(i)] 956 || !(*_node_filter)[Parent::v(i)])) 951 957 Parent::next(i); 952 958 } … … 954 960 void nextIn(Arc& i) const { 955 961 Parent::nextIn(i); 956 while (i!=INVALID && (!(*_edge_filter _map)[i]957 || !(*_node_filter _map)[Parent::source(i)]))962 while (i!=INVALID && (!(*_edge_filter)[i] 963 || !(*_node_filter)[Parent::source(i)])) 958 964 Parent::nextIn(i); 959 965 } … … 961 967 void nextOut(Arc& i) const { 962 968 Parent::nextOut(i); 963 while (i!=INVALID && (!(*_edge_filter _map)[i]964 || !(*_node_filter _map)[Parent::target(i)]))969 while (i!=INVALID && (!(*_edge_filter)[i] 970 || !(*_node_filter)[Parent::target(i)])) 965 971 Parent::nextOut(i); 966 972 } … … 968 974 void nextInc(Edge& i, bool& d) const { 969 975 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)]))976 while (i!=INVALID && (!(*_edge_filter)[i] 977 || !(*_node_filter)[Parent::u(i)] 978 || !(*_node_filter)[Parent::v(i)])) 973 979 Parent::nextInc(i, d); 974 980 } 975 981 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]; }982 void status(const Node& n, bool v) const { _node_filter->set(n, v); } 983 void status(const Edge& e, bool v) const { _edge_filter->set(e, v); } 984 985 bool status(const Node& n) const { return (*_node_filter)[n]; } 986 bool status(const Edge& e) const { return (*_edge_filter)[e]; } 981 987 982 988 typedef False NodeNumTag; … … 987 993 Arc findArc(const Node& u, const Node& v, 988 994 const Arc& prev = INVALID) const { 989 if (!(*_node_filter _map)[u] || !(*_node_filter_map)[v]) {995 if (!(*_node_filter)[u] || !(*_node_filter)[v]) { 990 996 return INVALID; 991 997 } 992 998 Arc arc = Parent::findArc(u, v, prev); 993 while (arc != INVALID && !(*_edge_filter _map)[arc]) {999 while (arc != INVALID && !(*_edge_filter)[arc]) { 994 1000 arc = Parent::findArc(u, v, arc); 995 1001 } … … 1000 1006 Edge findEdge(const Node& u, const Node& v, 1001 1007 const Edge& prev = INVALID) const { 1002 if (!(*_node_filter _map)[u] || !(*_node_filter_map)[v]) {1008 if (!(*_node_filter)[u] || !(*_node_filter)[v]) { 1003 1009 return INVALID; 1004 1010 } 1005 1011 Edge edge = Parent::findEdge(u, v, prev); 1006 while (edge != INVALID && !(*_edge_filter _map)[edge]) {1012 while (edge != INVALID && !(*_edge_filter)[edge]) { 1007 1013 edge = Parent::findEdge(u, v, edge); 1008 1014 } … … 1010 1016 } 1011 1017 1012 template <typename _Value> 1013 class NodeMap : public SubMapExtender<Adaptor, 1014 typename Parent::template NodeMap<_Value> > { 1018 template <typename V> 1019 class NodeMap 1020 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1021 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> { 1022 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1023 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent; 1024 1015 1025 public: 1016 typedef _Value Value; 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) {} 1026 typedef V Value; 1027 1028 NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor) 1029 : Parent(adaptor) {} 1030 NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value) 1031 : Parent(adaptor, value) {} 1024 1032 1025 1033 private: … … 1030 1038 template <typename CMap> 1031 1039 NodeMap& operator=(const CMap& cmap) { 1032 MapParent::operator=(cmap);1040 Parent::operator=(cmap); 1033 1041 return *this; 1034 1042 } 1035 1043 }; 1036 1044 1037 template <typename _Value> 1038 class ArcMap : public SubMapExtender<Adaptor, 1039 typename Parent::template ArcMap<_Value> > { 1045 template <typename V> 1046 class ArcMap 1047 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1048 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> { 1049 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1050 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent; 1051 1040 1052 public: 1041 typedef _Value Value; 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) {} 1053 typedef V Value; 1054 1055 ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor) 1056 : Parent(adaptor) {} 1057 ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value) 1058 : Parent(adaptor, value) {} 1049 1059 1050 1060 private: … … 1055 1065 template <typename CMap> 1056 1066 ArcMap& operator=(const CMap& cmap) { 1057 MapParent::operator=(cmap);1067 Parent::operator=(cmap); 1058 1068 return *this; 1059 1069 } 1060 1070 }; 1061 1071 1062 template <typename _Value> 1063 class EdgeMap : public SubMapExtender<Adaptor, 1064 typename Parent::template EdgeMap<_Value> > { 1072 template <typename V> 1073 class EdgeMap 1074 : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1075 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> { 1076 typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 1077 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent; 1078 1065 1079 public: 1066 typedef _Value Value; 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) {} 1080 typedef V Value; 1081 1082 EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor) 1083 : Parent(adaptor) {} 1084 1085 EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value) 1086 : Parent(adaptor, value) {} 1075 1087 1076 1088 private: … … 1081 1093 template <typename CMap> 1082 1094 EdgeMap& operator=(const CMap& cmap) { 1083 MapParent::operator=(cmap);1095 Parent::operator=(cmap); 1084 1096 return *this; 1085 1097 } … … 1088 1100 }; 1089 1101 1090 template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap> 1091 class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false> 1092 : public GraphAdaptorBase<_Graph> { 1093 public: 1094 typedef _Graph Graph; 1095 typedef _NodeFilterMap NodeFilterMap; 1096 typedef _EdgeFilterMap EdgeFilterMap; 1102 template <typename GR, typename NF, typename EF> 1103 class SubGraphBase<GR, NF, EF, false> 1104 : public GraphAdaptorBase<GR> { 1105 typedef GraphAdaptorBase<GR> Parent; 1106 public: 1107 typedef GR Graph; 1108 typedef NF NodeFilterMap; 1109 typedef EF EdgeFilterMap; 1097 1110 1098 1111 typedef SubGraphBase Adaptor; 1099 typedef GraphAdaptorBase<_Graph> Parent;1100 1112 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; 1113 NF* _node_filter; 1114 EF* _edge_filter; 1115 SubGraphBase() 1116 : Parent(), _node_filter(0), _edge_filter(0) { } 1117 1118 void initialize(GR& graph, NF& node_filter, EF& edge_filter) { 1119 Parent::initialize(graph); 1120 _node_filter = &node_filter; 1121 _edge_filter = &edge_filter; 1111 1122 } 1112 1123 … … 1119 1130 void first(Node& i) const { 1120 1131 Parent::first(i); 1121 while (i!=INVALID && !(*_node_filter _map)[i]) Parent::next(i);1132 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 1122 1133 } 1123 1134 1124 1135 void first(Arc& i) const { 1125 1136 Parent::first(i); 1126 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::next(i);1137 while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); 1127 1138 } 1128 1139 1129 1140 void first(Edge& i) const { 1130 1141 Parent::first(i); 1131 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::next(i);1142 while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); 1132 1143 } 1133 1144 1134 1145 void firstIn(Arc& i, const Node& n) const { 1135 1146 Parent::firstIn(i, n); 1136 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextIn(i);1147 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i); 1137 1148 } 1138 1149 1139 1150 void firstOut(Arc& i, const Node& n) const { 1140 1151 Parent::firstOut(i, n); 1141 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextOut(i);1152 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i); 1142 1153 } 1143 1154 1144 1155 void firstInc(Edge& i, bool& d, const Node& n) const { 1145 1156 Parent::firstInc(i, d, n); 1146 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextInc(i, d);1157 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d); 1147 1158 } 1148 1159 1149 1160 void next(Node& i) const { 1150 1161 Parent::next(i); 1151 while (i!=INVALID && !(*_node_filter _map)[i]) Parent::next(i);1162 while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i); 1152 1163 } 1153 1164 void next(Arc& i) const { 1154 1165 Parent::next(i); 1155 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::next(i);1166 while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); 1156 1167 } 1157 1168 void next(Edge& i) const { 1158 1169 Parent::next(i); 1159 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::next(i);1170 while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i); 1160 1171 } 1161 1172 void nextIn(Arc& i) const { 1162 1173 Parent::nextIn(i); 1163 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextIn(i);1174 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextIn(i); 1164 1175 } 1165 1176 1166 1177 void nextOut(Arc& i) const { 1167 1178 Parent::nextOut(i); 1168 while (i!=INVALID && !(*_edge_filter _map)[i]) Parent::nextOut(i);1179 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextOut(i); 1169 1180 } 1170 1181 void nextInc(Edge& i, bool& d) const { 1171 1182 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]; }1183 while (i!=INVALID && !(*_edge_filter)[i]) Parent::nextInc(i, d); 1184 } 1185 1186 void status(const Node& n, bool v) const { _node_filter->set(n, v); } 1187 void status(const Edge& e, bool v) const { _edge_filter->set(e, v); } 1188 1189 bool status(const Node& n) const { return (*_node_filter)[n]; } 1190 bool status(const Edge& e) const { return (*_edge_filter)[e]; } 1180 1191 1181 1192 typedef False NodeNumTag; … … 1187 1198 const Arc& prev = INVALID) const { 1188 1199 Arc arc = Parent::findArc(u, v, prev); 1189 while (arc != INVALID && !(*_edge_filter _map)[arc]) {1200 while (arc != INVALID && !(*_edge_filter)[arc]) { 1190 1201 arc = Parent::findArc(u, v, arc); 1191 1202 } … … 1197 1208 const Edge& prev = INVALID) const { 1198 1209 Edge edge = Parent::findEdge(u, v, prev); 1199 while (edge != INVALID && !(*_edge_filter _map)[edge]) {1210 while (edge != INVALID && !(*_edge_filter)[edge]) { 1200 1211 edge = Parent::findEdge(u, v, edge); 1201 1212 } … … 1203 1214 } 1204 1215 1205 template <typename _Value> 1206 class NodeMap : public SubMapExtender<Adaptor, 1207 typename Parent::template NodeMap<_Value> > { 1216 template <typename V> 1217 class NodeMap 1218 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1219 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> { 1220 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1221 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent; 1222 1208 1223 public: 1209 typedef _Value Value; 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) {} 1224 typedef V Value; 1225 1226 NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor) 1227 : Parent(adaptor) {} 1228 NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value) 1229 : Parent(adaptor, value) {} 1217 1230 1218 1231 private: … … 1223 1236 template <typename CMap> 1224 1237 NodeMap& operator=(const CMap& cmap) { 1225 MapParent::operator=(cmap);1238 Parent::operator=(cmap); 1226 1239 return *this; 1227 1240 } 1228 1241 }; 1229 1242 1230 template <typename _Value> 1231 class ArcMap : public SubMapExtender<Adaptor, 1232 typename Parent::template ArcMap<_Value> > { 1243 template <typename V> 1244 class ArcMap 1245 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1246 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> { 1247 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1248 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent; 1249 1233 1250 public: 1234 typedef _Value Value; 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) {} 1251 typedef V Value; 1252 1253 ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor) 1254 : Parent(adaptor) {} 1255 ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value) 1256 : Parent(adaptor, value) {} 1242 1257 1243 1258 private: … … 1248 1263 template <typename CMap> 1249 1264 ArcMap& operator=(const CMap& cmap) { 1250 MapParent::operator=(cmap);1265 Parent::operator=(cmap); 1251 1266 return *this; 1252 1267 } 1253 1268 }; 1254 1269 1255 template <typename _Value> 1256 class EdgeMap : public SubMapExtender<Adaptor, 1257 typename Parent::template EdgeMap<_Value> > { 1270 template <typename V> 1271 class EdgeMap 1272 : public SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1273 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> { 1274 typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 1275 LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent; 1276 1258 1277 public: 1259 typedef _Value Value; 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) {} 1278 typedef V Value; 1279 1280 EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor) 1281 : Parent(adaptor) {} 1282 1283 EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value) 1284 : Parent(adaptor, value) {} 1268 1285 1269 1286 private: … … 1274 1291 template <typename CMap> 1275 1292 EdgeMap& operator=(const CMap& cmap) { 1276 MapParent::operator=(cmap);1293 Parent::operator=(cmap); 1277 1294 return *this; 1278 1295 } … … 1333 1350 typedef EF EdgeFilterMap; 1334 1351 1335 typedef GraphAdaptorExtender< 1352 typedef GraphAdaptorExtender<SubGraphBase<GR, NF, EF, true> > 1336 1353 Parent; 1337 1354 … … 1347 1364 /// Creates a subgraph for the given graph with the given node 1348 1365 /// 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); 1366 SubGraph(GR& graph, NF& node_filter, EF& edge_filter) { 1367 initialize(graph, node_filter, edge_filter); 1354 1368 } 1355 1369 … … 1415 1429 template<typename GR, typename NF, typename EF> 1416 1430 SubGraph<const GR, NF, EF> 1417 subGraph(const GR& graph, 1418 NF& node_filter_map, EF& edge_filter_map) { 1431 subGraph(const GR& graph, NF& node_filter, EF& edge_filter) { 1419 1432 return SubGraph<const GR, NF, EF> 1420 (graph, node_filter _map, edge_filter_map);1433 (graph, node_filter, edge_filter); 1421 1434 } 1422 1435 1423 1436 template<typename GR, typename NF, typename EF> 1424 1437 SubGraph<const GR, const NF, EF> 1425 subGraph(const GR& graph, 1426 const NF& node_filter_map, EF& edge_filter_map) { 1438 subGraph(const GR& graph, const NF& node_filter, EF& edge_filter) { 1427 1439 return SubGraph<const GR, const NF, EF> 1428 (graph, node_filter _map, edge_filter_map);1440 (graph, node_filter, edge_filter); 1429 1441 } 1430 1442 1431 1443 template<typename GR, typename NF, typename EF> 1432 1444 SubGraph<const GR, NF, const EF> 1433 subGraph(const GR& graph, 1434 NF& node_filter_map, const EF& edge_filter_map) { 1445 subGraph(const GR& graph, NF& node_filter, const EF& edge_filter) { 1435 1446 return SubGraph<const GR, NF, const EF> 1436 (graph, node_filter _map, edge_filter_map);1447 (graph, node_filter, edge_filter); 1437 1448 } 1438 1449 1439 1450 template<typename GR, typename NF, typename EF> 1440 1451 SubGraph<const GR, const NF, const EF> 1441 subGraph(const GR& graph, 1442 const NF& node_filter_map, const EF& edge_filter_map) { 1452 subGraph(const GR& graph, const NF& node_filter, const EF& edge_filter) { 1443 1453 return SubGraph<const GR, const NF, const EF> 1444 (graph, node_filter _map, edge_filter_map);1454 (graph, node_filter, edge_filter); 1445 1455 } 1446 1456 … … 1482 1492 class FilterNodes : 1483 1493 public DigraphAdaptorExtender< 1484 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> > { 1494 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 1495 true> > { 1485 1496 #endif 1497 typedef DigraphAdaptorExtender< 1498 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 1499 true> > Parent; 1500 1486 1501 public: 1487 1502 … … 1489 1504 typedef NF NodeFilterMap; 1490 1505 1491 typedef DigraphAdaptorExtender<1492 SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, bool>, true> >1493 Parent;1494 1495 1506 typedef typename Parent::Node Node; 1496 1507 1497 1508 protected: 1498 ConstMap<typename Digraph::Arc, bool> const_true_map; 1499 1500 FilterNodes() : const_true_map(true) { 1501 Parent::setArcFilterMap(const_true_map); 1502 } 1509 ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map; 1510 1511 FilterNodes() : const_true_map() {} 1503 1512 1504 1513 public: … … 1508 1517 /// Creates a subgraph for the given digraph or graph with the 1509 1518 /// given node filter map. 1510 FilterNodes(GR& graph, N odeFilterMap& node_filter) :1511 Parent(), const_true_map(true)1519 FilterNodes(GR& graph, NF& node_filter) 1520 : Parent(), const_true_map() 1512 1521 { 1513 Parent::setDigraph(graph); 1514 Parent::setNodeFilterMap(node_filter); 1515 Parent::setArcFilterMap(const_true_map); 1522 Parent::initialize(graph, node_filter, const_true_map); 1516 1523 } 1517 1524 … … 1548 1555 typename enable_if<UndirectedTagIndicator<GR> >::type> : 1549 1556 public GraphAdaptorExtender< 1550 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> > { 1551 1552 public: 1557 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 1558 true> > { 1559 1560 typedef GraphAdaptorExtender< 1561 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 1562 true> > Parent; 1563 1564 public: 1565 1553 1566 typedef GR Graph; 1554 1567 typedef NF NodeFilterMap; 1555 typedef GraphAdaptorExtender<1556 SubGraphBase<GR, NF, ConstMap<typename GR::Edge, bool>, true> >1557 Parent;1558 1568 1559 1569 typedef typename Parent::Node Node; 1570 1560 1571 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); 1572 ConstMap<typename GR::Edge, Const<bool, true> > const_true_map; 1573 1574 FilterNodes() : const_true_map() {} 1575 1576 public: 1577 1578 FilterNodes(GR& graph, NodeFilterMap& node_filter) : 1579 Parent(), const_true_map() { 1580 Parent::initialize(graph, node_filter, const_true_map); 1574 1581 } 1575 1582 … … 1589 1596 template<typename GR, typename NF> 1590 1597 FilterNodes<const GR, NF> 1591 filterNodes(const GR& graph, NF& node_filter _map) {1592 return FilterNodes<const GR, NF>(graph, node_filter _map);1598 filterNodes(const GR& graph, NF& node_filter) { 1599 return FilterNodes<const GR, NF>(graph, node_filter); 1593 1600 } 1594 1601 1595 1602 template<typename GR, typename NF> 1596 1603 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);1604 filterNodes(const GR& graph, const NF& node_filter) { 1605 return FilterNodes<const GR, const NF>(graph, node_filter); 1599 1606 } 1600 1607 … … 1613 1620 /// parameter is set to be \c const. 1614 1621 /// 1615 /// \tparam GR The type of the adapted digraph.1622 /// \tparam DGR The type of the adapted digraph. 1616 1623 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 1617 1624 /// It can also be specified to be \c const. … … 1619 1626 /// It must be a \c bool (or convertible) arc map of the 1620 1627 /// adapted digraph. The default type is 1621 /// \ref concepts::Digraph::ArcMap " GR::ArcMap<bool>".1628 /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>". 1622 1629 /// 1623 1630 /// \note The \c Node and \c Arc types of this adaptor and the adapted 1624 1631 /// digraph are convertible to each other. 1625 1632 #ifdef DOXYGEN 1626 template<typename GR,1633 template<typename DGR, 1627 1634 typename AF> 1628 1635 class FilterArcs { 1629 1636 #else 1630 template<typename GR,1631 typename AF = typename GR::template ArcMap<bool> >1637 template<typename DGR, 1638 typename AF = typename DGR::template ArcMap<bool> > 1632 1639 class FilterArcs : 1633 1640 public DigraphAdaptorExtender< 1634 SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> > { 1641 SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 1642 AF, false> > { 1635 1643 #endif 1636 public: 1644 typedef DigraphAdaptorExtender< 1645 SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 1646 AF, false> > Parent; 1647 1648 public: 1649 1637 1650 /// The type of the adapted digraph. 1638 typedef GR Digraph;1651 typedef DGR Digraph; 1639 1652 /// The type of the arc filter map. 1640 1653 typedef AF ArcFilterMap; 1641 1654 1642 typedef DigraphAdaptorExtender<1643 SubDigraphBase<GR, ConstMap<typename GR::Node, bool>, AF, false> >1644 Parent;1645 1646 1655 typedef typename Parent::Arc Arc; 1647 1656 1648 1657 protected: 1649 ConstMap<typename Digraph::Node, bool> const_true_map; 1650 1651 FilterArcs() : const_true_map(true) { 1652 Parent::setNodeFilterMap(const_true_map); 1653 } 1658 ConstMap<typename DGR::Node, Const<bool, true> > const_true_map; 1659 1660 FilterArcs() : const_true_map() {} 1654 1661 1655 1662 public: … … 1659 1666 /// Creates a subdigraph for the given digraph with the given arc 1660 1667 /// 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); 1668 FilterArcs(DGR& digraph, ArcFilterMap& arc_filter) 1669 : Parent(), const_true_map() { 1670 Parent::initialize(digraph, const_true_map, arc_filter); 1666 1671 } 1667 1672 … … 1699 1704 /// \ingroup graph_adaptors 1700 1705 /// \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);1706 template<typename DGR, typename AF> 1707 FilterArcs<const DGR, AF> 1708 filterArcs(const DGR& digraph, AF& arc_filter) { 1709 return FilterArcs<const DGR, AF>(digraph, arc_filter); 1705 1710 } 1706 1711 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);1712 template<typename DGR, typename AF> 1713 FilterArcs<const DGR, const AF> 1714 filterArcs(const DGR& digraph, const AF& arc_filter) { 1715 return FilterArcs<const DGR, const AF>(digraph, arc_filter); 1711 1716 } 1712 1717 … … 1744 1749 class FilterEdges : 1745 1750 public GraphAdaptorExtender< 1746 SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> > { 1751 SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 1752 EF, false> > { 1747 1753 #endif 1748 public: 1754 typedef GraphAdaptorExtender< 1755 SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 1756 EF, false> > Parent; 1757 1758 public: 1759 1749 1760 /// The type of the adapted graph. 1750 1761 typedef GR Graph; … … 1752 1763 typedef EF EdgeFilterMap; 1753 1764 1754 typedef GraphAdaptorExtender<1755 SubGraphBase<GR, ConstMap<typename GR::Node,bool>, EF, false> >1756 Parent;1757 1758 1765 typedef typename Parent::Edge Edge; 1759 1766 1760 1767 protected: 1761 ConstMap<typename G raph::Node, bool> const_true_map;1768 ConstMap<typename GR::Node, Const<bool, true> > const_true_map; 1762 1769 1763 1770 FilterEdges() : const_true_map(true) { … … 1771 1778 /// Creates a subgraph for the given graph with the given edge 1772 1779 /// 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); 1780 FilterEdges(GR& graph, EF& edge_filter) 1781 : Parent(), const_true_map() { 1782 Parent::initialize(graph, const_true_map, edge_filter); 1778 1783 } 1779 1784 … … 1813 1818 template<typename GR, typename EF> 1814 1819 FilterEdges<const GR, EF> 1815 filterEdges(const GR& graph, EF& edge_filter _map) {1816 return FilterEdges<const GR, EF>(graph, edge_filter _map);1820 filterEdges(const GR& graph, EF& edge_filter) { 1821 return FilterEdges<const GR, EF>(graph, edge_filter); 1817 1822 } 1818 1823 1819 1824 template<typename GR, typename EF> 1820 1825 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);1826 filterEdges(const GR& graph, const EF& edge_filter) { 1827 return FilterEdges<const GR, const EF>(graph, edge_filter); 1823 1828 } 1824 1829 1825 1830 1826 template <typename _Digraph>1831 template <typename DGR> 1827 1832 class UndirectorBase { 1828 1833 public: 1829 typedef _DigraphDigraph;1834 typedef DGR Digraph; 1830 1835 typedef UndirectorBase Adaptor; 1831 1836 … … 1835 1840 typedef typename Digraph::Node Node; 1836 1841 1837 class Arc : public Edge{1842 class Arc { 1838 1843 friend class UndirectorBase; 1839 1844 protected: 1845 Edge _edge; 1840 1846 bool _forward; 1841 1847 1842 Arc(const Edge& edge, bool forward) :1843 Edge(edge), _forward(forward) {}1848 Arc(const Edge& edge, bool forward) 1849 : _edge(edge), _forward(forward) {} 1844 1850 1845 1851 public: 1846 1852 Arc() {} 1847 1853 1848 Arc(Invalid) : Edge(INVALID), _forward(true) {} 1854 Arc(Invalid) : _edge(INVALID), _forward(true) {} 1855 1856 operator const Edge&() const { return _edge; } 1849 1857 1850 1858 bool operator==(const Arc &other) const { 1851 return _forward == other._forward && 1852 static_cast<const Edge&>(*this) == static_cast<const Edge&>(other); 1859 return _forward == other._forward && _edge == other._edge; 1853 1860 } 1854 1861 bool operator!=(const Arc &other) const { 1855 return _forward != other._forward || 1856 static_cast<const Edge&>(*this) != static_cast<const Edge&>(other); 1862 return _forward != other._forward || _edge != other._edge; 1857 1863 } 1858 1864 bool operator<(const Arc &other) const { 1859 1865 return _forward < other._forward || 1860 (_forward == other._forward && 1861 static_cast<const Edge&>(*this) < static_cast<const Edge&>(other)); 1866 (_forward == other._forward && _edge < other._edge); 1862 1867 } 1863 1868 }; … … 1872 1877 1873 1878 void first(Arc& a) const { 1874 _digraph->first(a );1879 _digraph->first(a._edge); 1875 1880 a._forward = true; 1876 1881 } … … 1880 1885 a._forward = false; 1881 1886 } else { 1882 _digraph->next(a );1887 _digraph->next(a._edge); 1883 1888 a._forward = true; 1884 1889 } … … 1894 1899 1895 1900 void firstOut(Arc& a, const Node& n) const { 1896 _digraph->firstIn(a , n);1897 if ( static_cast<const Edge&>(a)!= INVALID ) {1901 _digraph->firstIn(a._edge, n); 1902 if (a._edge != INVALID ) { 1898 1903 a._forward = false; 1899 1904 } else { 1900 _digraph->firstOut(a , n);1905 _digraph->firstOut(a._edge, n); 1901 1906 a._forward = true; 1902 1907 } … … 1904 1909 void nextOut(Arc &a) const { 1905 1910 if (!a._forward) { 1906 Node n = _digraph->target(a );1907 _digraph->nextIn(a );1908 if ( static_cast<const Edge&>(a) == INVALID) {1909 _digraph->firstOut(a , n);1911 Node n = _digraph->target(a._edge); 1912 _digraph->nextIn(a._edge); 1913 if (a._edge == INVALID) { 1914 _digraph->firstOut(a._edge, n); 1910 1915 a._forward = true; 1911 1916 } 1912 1917 } 1913 1918 else { 1914 _digraph->nextOut(a );1919 _digraph->nextOut(a._edge); 1915 1920 } 1916 1921 } 1917 1922 1918 1923 void firstIn(Arc &a, const Node &n) const { 1919 _digraph->firstOut(a , n);1920 if ( static_cast<const Edge&>(a)!= INVALID ) {1924 _digraph->firstOut(a._edge, n); 1925 if (a._edge != INVALID ) { 1921 1926 a._forward = false; 1922 1927 } else { 1923 _digraph->firstIn(a , n);1928 _digraph->firstIn(a._edge, n); 1924 1929 a._forward = true; 1925 1930 } … … 1927 1932 void nextIn(Arc &a) const { 1928 1933 if (!a._forward) { 1929 Node n = _digraph->source(a );1930 _digraph->nextOut(a );1931 if ( static_cast<const Edge&>(a)== INVALID ) {1932 _digraph->firstIn(a , n);1934 Node n = _digraph->source(a._edge); 1935 _digraph->nextOut(a._edge); 1936 if (a._edge == INVALID ) { 1937 _digraph->firstIn(a._edge, n); 1933 1938 a._forward = true; 1934 1939 } 1935 1940 } 1936 1941 else { 1937 _digraph->nextIn(a );1942 _digraph->nextIn(a._edge); 1938 1943 } 1939 1944 } … … 1968 1973 1969 1974 Node source(const Arc &a) const { 1970 return a._forward ? _digraph->source(a ) : _digraph->target(a);1975 return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge); 1971 1976 } 1972 1977 1973 1978 Node target(const Arc &a) const { 1974 return a._forward ? _digraph->target(a ) : _digraph->source(a);1979 return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge); 1975 1980 } 1976 1981 1977 1982 static Arc direct(const Edge &e, bool d) { 1978 1983 return Arc(e, d); 1979 }1980 Arc direct(const Edge &e, const Node& n) const {1981 return Arc(e, _digraph->source(e) == n);1982 1984 } 1983 1985 … … 2063 2065 private: 2064 2066 2065 template <typename _Value>2067 template <typename V> 2066 2068 class ArcMapBase { 2067 2069 private: 2068 2070 2069 typedef typename D igraph::template ArcMap<_Value> MapImpl;2071 typedef typename DGR::template ArcMap<V> MapImpl; 2070 2072 2071 2073 public: … … 2073 2075 typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag; 2074 2076 2075 typedef _ValueValue;2077 typedef V Value; 2076 2078 typedef Arc Key; 2077 2079 typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue; … … 2080 2082 typedef typename MapTraits<MapImpl>::ReturnValue Reference; 2081 2083 2082 ArcMapBase(const Adaptor& adaptor) :2084 ArcMapBase(const UndirectorBase<DGR>& adaptor) : 2083 2085 _forward(*adaptor._digraph), _backward(*adaptor._digraph) {} 2084 2086 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) { 2087 ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value) 2088 : _forward(*adaptor._digraph, value), 2089 _backward(*adaptor._digraph, value) {} 2090 2091 void set(const Arc& a, const V& value) { 2089 2092 if (direction(a)) { 2090 _forward.set(a, v );2093 _forward.set(a, value); 2091 2094 } else { 2092 _backward.set(a, v );2095 _backward.set(a, value); 2093 2096 } 2094 2097 } … … 2118 2121 public: 2119 2122 2120 template <typename _Value> 2121 class NodeMap : public Digraph::template NodeMap<_Value> { 2123 template <typename V> 2124 class NodeMap : public DGR::template NodeMap<V> { 2125 typedef typename DGR::template NodeMap<V> Parent; 2126 2122 2127 public: 2123 2124 typedef _Value Value; 2125 typedef typename Digraph::template NodeMap<Value> Parent; 2126 2127 explicit NodeMap(const Adaptor& adaptor) 2128 typedef V Value; 2129 2130 explicit NodeMap(const UndirectorBase<DGR>& adaptor) 2128 2131 : Parent(*adaptor._digraph) {} 2129 2132 2130 NodeMap(const Adaptor& adaptor, const _Value& value)2133 NodeMap(const UndirectorBase<DGR>& adaptor, const V& value) 2131 2134 : Parent(*adaptor._digraph, value) { } 2132 2135 … … 2144 2147 }; 2145 2148 2146 template <typename _Value>2149 template <typename V> 2147 2150 class ArcMap 2148 : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 2149 { 2151 : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > { 2152 typedef SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> > Parent; 2153 2150 2154 public: 2151 typedef _Value Value; 2152 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; 2153 2154 explicit ArcMap(const Adaptor& adaptor) 2155 typedef V Value; 2156 2157 explicit ArcMap(const UndirectorBase<DGR>& adaptor) 2155 2158 : Parent(adaptor) {} 2156 2159 2157 ArcMap(const Adaptor& adaptor, const Value& value)2160 ArcMap(const UndirectorBase<DGR>& adaptor, const V& value) 2158 2161 : Parent(adaptor, value) {} 2159 2162 … … 2170 2173 }; 2171 2174 2172 template <typename _Value> 2173 class EdgeMap : public Digraph::template ArcMap<_Value> { 2175 template <typename V> 2176 class EdgeMap : public Digraph::template ArcMap<V> { 2177 typedef typename Digraph::template ArcMap<V> Parent; 2178 2174 2179 public: 2175 2176 typedef _Value Value; 2177 typedef typename Digraph::template ArcMap<Value> Parent; 2178 2179 explicit EdgeMap(const Adaptor& adaptor) 2180 typedef V Value; 2181 2182 explicit EdgeMap(const UndirectorBase<DGR>& adaptor) 2180 2183 : Parent(*adaptor._digraph) {} 2181 2184 2182 EdgeMap(const Adaptor& adaptor, const Value& value)2185 EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value) 2183 2186 : Parent(*adaptor._digraph, value) {} 2184 2187 … … 2196 2199 }; 2197 2200 2198 typedef typename ItemSetTraits<D igraph, Node>::ItemNotifier NodeNotifier;2201 typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier; 2199 2202 NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); } 2200 2203 2201 typedef typename ItemSetTraits<D igraph, Edge>::ItemNotifier EdgeNotifier;2204 typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier; 2202 2205 EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); } 2206 2207 typedef EdgeNotifier ArcNotifier; 2208 ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); } 2203 2209 2204 2210 protected: … … 2206 2212 UndirectorBase() : _digraph(0) {} 2207 2213 2208 D igraph* _digraph;2209 2210 void setDigraph(Digraph& digraph) {2214 DGR* _digraph; 2215 2216 void initialize(DGR& digraph) { 2211 2217 _digraph = &digraph; 2212 2218 } … … 2227 2233 /// parameter is set to be \c const. 2228 2234 /// 2229 /// \tparam GR The type of the adapted digraph.2235 /// \tparam DGR The type of the adapted digraph. 2230 2236 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 2231 2237 /// It can also be specified to be \c const. … … 2237 2243 /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type 2238 2244 /// of the adapted digraph.) 2239 template<typename GR>2245 template<typename DGR> 2240 2246 #ifdef DOXYGEN 2241 2247 class Undirector { 2242 2248 #else 2243 2249 class Undirector : 2244 public GraphAdaptorExtender<UndirectorBase< GR> > {2250 public GraphAdaptorExtender<UndirectorBase<DGR> > { 2245 2251 #endif 2252 typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent; 2246 2253 public: 2247 2254 /// The type of the adapted digraph. 2248 typedef GR Digraph; 2249 typedef GraphAdaptorExtender<UndirectorBase<GR> > Parent; 2255 typedef DGR Digraph; 2250 2256 protected: 2251 2257 Undirector() { } … … 2255 2261 /// 2256 2262 /// Creates an undirected graph from the given digraph. 2257 Undirector(D igraph& digraph) {2258 setDigraph(digraph);2263 Undirector(DGR& digraph) { 2264 initialize(digraph); 2259 2265 } 2260 2266 … … 2263 2269 /// This map adaptor class adapts two arc maps of the underlying 2264 2270 /// digraph to get an arc map of the undirected graph. 2265 /// Its value type is inherited from the first arc map type 2266 /// (\c %ForwardMap). 2267 template <typename ForwardMap, typename BackwardMap> 2271 /// Its value type is inherited from the first arc map type (\c FW). 2272 /// \tparam FW The type of the "foward" arc map. 2273 /// \tparam BK The type of the "backward" arc map. 2274 template <typename FW, typename BK> 2268 2275 class CombinedArcMap { 2269 2276 public: … … 2272 2279 typedef typename Parent::Arc Key; 2273 2280 /// The value type of the map 2274 typedef typename F orwardMap::Value Value;2275 2276 typedef typename MapTraits<F orwardMap>::ReferenceMapTag ReferenceMapTag;2277 2278 typedef typename MapTraits<F orwardMap>::ReturnValue ReturnValue;2279 typedef typename MapTraits<F orwardMap>::ConstReturnValue ConstReturnValue;2280 typedef typename MapTraits<F orwardMap>::ReturnValue Reference;2281 typedef typename MapTraits<F orwardMap>::ConstReturnValue ConstReference;2281 typedef typename FW::Value Value; 2282 2283 typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag; 2284 2285 typedef typename MapTraits<FW>::ReturnValue ReturnValue; 2286 typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue; 2287 typedef typename MapTraits<FW>::ReturnValue Reference; 2288 typedef typename MapTraits<FW>::ConstReturnValue ConstReference; 2282 2289 2283 2290 /// Constructor 2284 CombinedArcMap(F orwardMap& forward, BackwardMap& backward)2291 CombinedArcMap(FW& forward, BK& backward) 2285 2292 : _forward(&forward), _backward(&backward) {} 2286 2293 … … 2314 2321 protected: 2315 2322 2316 F orwardMap* _forward;2317 B ackwardMap* _backward;2323 FW* _forward; 2324 BK* _backward; 2318 2325 2319 2326 }; … … 2322 2329 /// 2323 2330 /// This function just returns a combined arc map. 2324 template <typename ForwardMap, typename BackwardMap> 2325 static CombinedArcMap<ForwardMap, BackwardMap> 2326 combinedArcMap(ForwardMap& forward, BackwardMap& backward) { 2327 return CombinedArcMap<ForwardMap, BackwardMap>(forward, backward); 2328 } 2329 2330 template <typename ForwardMap, typename BackwardMap> 2331 static CombinedArcMap<const ForwardMap, BackwardMap> 2332 combinedArcMap(const ForwardMap& forward, BackwardMap& backward) { 2333 return CombinedArcMap<const ForwardMap, 2334 BackwardMap>(forward, backward); 2335 } 2336 2337 template <typename ForwardMap, typename BackwardMap> 2338 static CombinedArcMap<ForwardMap, const BackwardMap> 2339 combinedArcMap(ForwardMap& forward, const BackwardMap& backward) { 2340 return CombinedArcMap<ForwardMap, 2341 const BackwardMap>(forward, backward); 2342 } 2343 2344 template <typename ForwardMap, typename BackwardMap> 2345 static CombinedArcMap<const ForwardMap, const BackwardMap> 2346 combinedArcMap(const ForwardMap& forward, const BackwardMap& backward) { 2347 return CombinedArcMap<const ForwardMap, 2348 const BackwardMap>(forward, backward); 2331 template <typename FW, typename BK> 2332 static CombinedArcMap<FW, BK> 2333 combinedArcMap(FW& forward, BK& backward) { 2334 return CombinedArcMap<FW, BK>(forward, backward); 2335 } 2336 2337 template <typename FW, typename BK> 2338 static CombinedArcMap<const FW, BK> 2339 combinedArcMap(const FW& forward, BK& backward) { 2340 return CombinedArcMap<const FW, BK>(forward, backward); 2341 } 2342 2343 template <typename FW, typename BK> 2344 static CombinedArcMap<FW, const BK> 2345 combinedArcMap(FW& forward, const BK& backward) { 2346 return CombinedArcMap<FW, const BK>(forward, backward); 2347 } 2348 2349 template <typename FW, typename BK> 2350 static CombinedArcMap<const FW, const BK> 2351 combinedArcMap(const FW& forward, const BK& backward) { 2352 return CombinedArcMap<const FW, const BK>(forward, backward); 2349 2353 } 2350 2354 … … 2356 2360 /// \ingroup graph_adaptors 2357 2361 /// \relates Undirector 2358 template<typename GR>2359 Undirector<const GR> undirector(constGR& digraph) {2360 return Undirector<const GR>(digraph);2362 template<typename DGR> 2363 Undirector<const DGR> undirector(const DGR& digraph) { 2364 return Undirector<const DGR>(digraph); 2361 2365 } 2362 2366 2363 2367 2364 template <typename _Graph, typename _DirectionMap>2368 template <typename GR, typename DM> 2365 2369 class OrienterBase { 2366 2370 public: 2367 2371 2368 typedef _GraphGraph;2369 typedef _DirectionMapDirectionMap;2370 2371 typedef typename G raph::Node Node;2372 typedef typename G raph::Edge Arc;2372 typedef GR Graph; 2373 typedef DM DirectionMap; 2374 2375 typedef typename GR::Node Node; 2376 typedef typename GR::Edge Arc; 2373 2377 2374 2378 void reverseArc(const Arc& arc) { … … 2449 2453 int maxArcId() const { return _graph->maxEdgeId(); } 2450 2454 2451 typedef typename ItemSetTraits<G raph, Node>::ItemNotifier NodeNotifier;2455 typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier; 2452 2456 NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); } 2453 2457 2454 typedef typename ItemSetTraits<G raph, Arc>::ItemNotifier ArcNotifier;2458 typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier; 2455 2459 ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); } 2456 2460 2457 template <typename _Value> 2458 class NodeMap : public _Graph::template NodeMap<_Value> { 2461 template <typename V> 2462 class NodeMap : public GR::template NodeMap<V> { 2463 typedef typename GR::template NodeMap<V> Parent; 2464 2459 2465 public: 2460 2466 2461 typedef typename _Graph::template NodeMap<_Value> Parent; 2462 2463 explicit NodeMap(const OrienterBase& adapter) 2467 explicit NodeMap(const OrienterBase<GR, DM>& adapter) 2464 2468 : Parent(*adapter._graph) {} 2465 2469 2466 NodeMap(const OrienterBase & adapter, const _Value& value)2470 NodeMap(const OrienterBase<GR, DM>& adapter, const V& value) 2467 2471 : Parent(*adapter._graph, value) {} 2468 2472 … … 2480 2484 }; 2481 2485 2482 template <typename _Value> 2483 class ArcMap : public _Graph::template EdgeMap<_Value> { 2486 template <typename V> 2487 class ArcMap : public GR::template EdgeMap<V> { 2488 typedef typename Graph::template EdgeMap<V> Parent; 2489 2484 2490 public: 2485 2491 2486 typedef typename Graph::template EdgeMap<_Value> Parent; 2487 2488 explicit ArcMap(const OrienterBase& adapter) 2492 explicit ArcMap(const OrienterBase<GR, DM>& adapter) 2489 2493 : Parent(*adapter._graph) { } 2490 2494 2491 ArcMap(const OrienterBase & adapter, const _Value& value)2495 ArcMap(const OrienterBase<GR, DM>& adapter, const V& value) 2492 2496 : Parent(*adapter._graph, value) { } 2493 2497 … … 2508 2512 protected: 2509 2513 Graph* _graph; 2510 DirectionMap* _direction; 2511 2512 void setDirectionMap(DirectionMap& direction) { 2514 DM* _direction; 2515 2516 void initialize(GR& graph, DM& direction) { 2517 _graph = &graph; 2513 2518 _direction = &direction; 2514 }2515 2516 void setGraph(Graph& graph) {2517 _graph = &graph;2518 2519 } 2519 2520 … … 2557 2558 public DigraphAdaptorExtender<OrienterBase<GR, DM> > { 2558 2559 #endif 2560 typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent; 2559 2561 public: 2560 2562 … … 2564 2566 typedef DM DirectionMap; 2565 2567 2566 typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;2567 2568 typedef typename Parent::Arc Arc; 2569 2568 2570 protected: 2569 2571 Orienter() { } 2572 2570 2573 public: 2571 2574 … … 2573 2576 /// 2574 2577 /// Constructor of the adaptor. 2575 Orienter(Graph& graph, DirectionMap& direction) { 2576 setGraph(graph); 2577 setDirectionMap(direction); 2578 Orienter(GR& graph, DM& direction) { 2579 Parent::initialize(graph, direction); 2578 2580 } 2579 2581 … … 2595 2597 template<typename GR, typename DM> 2596 2598 Orienter<const GR, DM> 2597 orienter(const GR& graph, DM& direction _map) {2598 return Orienter<const GR, DM>(graph, direction _map);2599 orienter(const GR& graph, DM& direction) { 2600 return Orienter<const GR, DM>(graph, direction); 2599 2601 } 2600 2602 2601 2603 template<typename GR, typename DM> 2602 2604 Orienter<const GR, const DM> 2603 orienter(const GR& graph, const DM& direction _map) {2604 return Orienter<const GR, const DM>(graph, direction _map);2605 orienter(const GR& graph, const DM& direction) { 2606 return Orienter<const GR, const DM>(graph, direction); 2605 2607 } 2606 2608 2607 2609 namespace _adaptor_bits { 2608 2610 2609 template<typename Digraph, 2610 typename CapacityMap, 2611 typename FlowMap, 2612 typename Tolerance> 2611 template <typename DGR, typename CM, typename FM, typename TL> 2613 2612 class ResForwardFilter { 2614 2613 public: 2615 2614 2616 typedef typename D igraph::Arc Key;2615 typedef typename DGR::Arc Key; 2617 2616 typedef bool Value; 2618 2617 2619 2618 private: 2620 2619 2621 const CapacityMap* _capacity; 2622 const FlowMap* _flow; 2623 Tolerance _tolerance; 2620 const CM* _capacity; 2621 const FM* _flow; 2622 TL _tolerance; 2623 2624 2624 public: 2625 2625 2626 ResForwardFilter(const C apacityMap& capacity, const FlowMap& flow,2627 const T olerance& tolerance = Tolerance())2626 ResForwardFilter(const CM& capacity, const FM& flow, 2627 const TL& tolerance = TL()) 2628 2628 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2629 2629 2630 bool operator[](const typename D igraph::Arc& a) const {2630 bool operator[](const typename DGR::Arc& a) const { 2631 2631 return _tolerance.positive((*_capacity)[a] - (*_flow)[a]); 2632 2632 } 2633 2633 }; 2634 2634 2635 template<typename Digraph, 2636 typename CapacityMap, 2637 typename FlowMap, 2638 typename Tolerance> 2635 template<typename DGR,typename CM, typename FM, typename TL> 2639 2636 class ResBackwardFilter { 2640 2637 public: 2641 2638 2642 typedef typename D igraph::Arc Key;2639 typedef typename DGR::Arc Key; 2643 2640 typedef bool Value; 2644 2641 2645 2642 private: 2646 2643 2647 const C apacityMap* _capacity;2648 const F lowMap* _flow;2649 T olerance_tolerance;2644 const CM* _capacity; 2645 const FM* _flow; 2646 TL _tolerance; 2650 2647 2651 2648 public: 2652 2649 2653 ResBackwardFilter(const C apacityMap& capacity, const FlowMap& flow,2654 const T olerance& tolerance = Tolerance())2650 ResBackwardFilter(const CM& capacity, const FM& flow, 2651 const TL& tolerance = TL()) 2655 2652 : _capacity(&capacity), _flow(&flow), _tolerance(tolerance) { } 2656 2653 2657 bool operator[](const typename D igraph::Arc& a) const {2654 bool operator[](const typename DGR::Arc& a) const { 2658 2655 return _tolerance.positive((*_flow)[a]); 2659 2656 } … … 2682 2679 /// This class conforms to the \ref concepts::Digraph "Digraph" concept. 2683 2680 /// 2684 /// \tparam GR The type of the adapted digraph.2681 /// \tparam DGR The type of the adapted digraph. 2685 2682 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 2686 2683 /// It is implicitly \c const. … … 2704 2701 /// is convertible to the \c Arc type of the adapted digraph. 2705 2702 #ifdef DOXYGEN 2706 template<typename GR, typename CM, typename FM, typename TL>2703 template<typename DGR, typename CM, typename FM, typename TL> 2707 2704 class ResidualDigraph 2708 2705 #else 2709 template<typename GR,2710 typename CM = typename GR::template ArcMap<int>,2706 template<typename DGR, 2707 typename CM = typename DGR::template ArcMap<int>, 2711 2708 typename FM = CM, 2712 2709 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> > > 2710 class ResidualDigraph 2711 : public SubDigraph< 2712 Undirector<const DGR>, 2713 ConstMap<typename DGR::Node, Const<bool, true> >, 2714 typename Undirector<const DGR>::template CombinedArcMap< 2715 _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>, 2716 _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > > 2719 2717 #endif 2720 2718 { … … 2722 2720 2723 2721 /// The type of the underlying digraph. 2724 typedef GR Digraph;2722 typedef DGR Digraph; 2725 2723 /// The type of the capacity map. 2726 2724 typedef CM CapacityMap; … … 2737 2735 typedef Undirector<const Digraph> Undirected; 2738 2736 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; 2737 typedef ConstMap<typename DGR::Node, Const<bool, true> > NodeFilter; 2738 2739 typedef _adaptor_bits::ResForwardFilter<const DGR, CM, 2740 FM, TL> ForwardFilter; 2741 2742 typedef _adaptor_bits::ResBackwardFilter<const DGR, CM, 2743 FM, TL> BackwardFilter; 2744 2744 2745 2745 typedef typename Undirected:: 2746 2746 template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter; 2747 2747 2748 typedef FilterArcs<Undirected, ArcFilter> Parent;2748 typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent; 2749 2749 2750 2750 const CapacityMap* _capacity; … … 2752 2752 2753 2753 Undirected _graph; 2754 NodeFilter _node_filter; 2754 2755 ForwardFilter _forward_filter; 2755 2756 BackwardFilter _backward_filter; … … 2762 2763 /// Constructor of the residual digraph adaptor. The parameters are the 2763 2764 /// 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), 2765 ResidualDigraph(const DGR& digraph, const CM& capacity, 2766 FM& flow, const TL& tolerance = Tolerance()) 2767 : Parent(), _capacity(&capacity), _flow(&flow), 2768 _graph(digraph), _node_filter(), 2767 2769 _forward_filter(capacity, flow, tolerance), 2768 2770 _backward_filter(capacity, flow, tolerance), 2769 2771 _arc_filter(_forward_filter, _backward_filter) 2770 2772 { 2771 Parent::setDigraph(_graph); 2772 Parent::setArcFilterMap(_arc_filter); 2773 Parent::initialize(_graph, _node_filter, _arc_filter); 2773 2774 } 2774 2775 … … 2846 2847 2847 2848 /// Constructor 2848 ResidualCapacity(const Adaptor& adaptor) : _adaptor(&adaptor) {} 2849 ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 2850 : _adaptor(&adaptor) {} 2849 2851 2850 2852 /// Returns the value associated with the given residual arc … … 2866 2868 /// \brief Returns a (read-only) Residual adaptor 2867 2869 /// 2868 /// This function just returns a (read-only) \ref Residual adaptor.2870 /// This function just returns a (read-only) \ref ResidualDigraph adaptor. 2869 2871 /// \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);2872 /// \relates ResidualDigraph 2873 template<typename DGR, typename CM, typename FM> 2874 ResidualDigraph<DGR, CM, FM> 2875 residualDigraph(const DGR& digraph, const CM& capacity_map, FM& flow_map) { 2876 return ResidualDigraph<DGR, CM, FM> (digraph, capacity_map, flow_map); 2875 2877 } 2876 2878 2877 2879 2878 template <typename _Digraph>2880 template <typename DGR> 2879 2881 class SplitNodesBase { 2880 public: 2881 2882 typedef _Digraph Digraph; 2883 typedef DigraphAdaptorBase<const _Digraph> Parent; 2882 typedef DigraphAdaptorBase<const DGR> Parent; 2883 2884 public: 2885 2886 typedef DGR Digraph; 2884 2887 typedef SplitNodesBase Adaptor; 2885 2888 2886 typedef typename D igraph::Node DigraphNode;2887 typedef typename D igraph::Arc DigraphArc;2889 typedef typename DGR::Node DigraphNode; 2890 typedef typename DGR::Arc DigraphArc; 2888 2891 2889 2892 class Node; … … 3149 3152 private: 3150 3153 3151 template <typename _Value>3154 template <typename V> 3152 3155 class NodeMapBase 3153 : public MapTraits<typename Parent::template NodeMap< _Value> > {3154 typedef typename Parent::template NodeMap< _Value> NodeImpl;3156 : public MapTraits<typename Parent::template NodeMap<V> > { 3157 typedef typename Parent::template NodeMap<V> NodeImpl; 3155 3158 public: 3156 3159 typedef Node Key; 3157 typedef _ValueValue;3160 typedef V Value; 3158 3161 typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag; 3159 3162 typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue; … … 3162 3165 typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference; 3163 3166 3164 NodeMapBase(const Adaptor& adaptor)3167 NodeMapBase(const SplitNodesBase<DGR>& adaptor) 3165 3168 : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {} 3166 NodeMapBase(const Adaptor& adaptor, const Value& value)3169 NodeMapBase(const SplitNodesBase<DGR>& adaptor, const V& value) 3167 3170 : _in_map(*adaptor._digraph, value), 3168 3171 _out_map(*adaptor._digraph, value) {} 3169 3172 3170 void set(const Node& key, const V alue& val) {3171 if ( Adaptor::inNode(key)) { _in_map.set(key, val); }3173 void set(const Node& key, const V& val) { 3174 if (SplitNodesBase<DGR>::inNode(key)) { _in_map.set(key, val); } 3172 3175 else {_out_map.set(key, val); } 3173 3176 } 3174 3177 3175 3178 ReturnValue operator[](const Node& key) { 3176 if ( Adaptor::inNode(key)) { return _in_map[key]; }3179 if (SplitNodesBase<DGR>::inNode(key)) { return _in_map[key]; } 3177 3180 else { return _out_map[key]; } 3178 3181 } … … 3187 3190 }; 3188 3191 3189 template <typename _Value>3192 template <typename V> 3190 3193 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;3194 : public MapTraits<typename Parent::template ArcMap<V> > { 3195 typedef typename Parent::template ArcMap<V> ArcImpl; 3196 typedef typename Parent::template NodeMap<V> NodeImpl; 3194 3197 public: 3195 3198 typedef Arc Key; 3196 typedef _ValueValue;3199 typedef V Value; 3197 3200 typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag; 3198 3201 typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue; … … 3201 3204 typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference; 3202 3205 3203 ArcMapBase(const Adaptor& adaptor)3206 ArcMapBase(const SplitNodesBase<DGR>& adaptor) 3204 3207 : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {} 3205 ArcMapBase(const Adaptor& adaptor, const Value& value)3208 ArcMapBase(const SplitNodesBase<DGR>& adaptor, const V& value) 3206 3209 : _arc_map(*adaptor._digraph, value), 3207 3210 _node_map(*adaptor._digraph, value) {} 3208 3211 3209 void set(const Arc& key, const V alue& val) {3210 if ( Adaptor::origArc(key)) {3211 _arc_map.set( key._item.first(), val);3212 void set(const Arc& key, const V& val) { 3213 if (SplitNodesBase<DGR>::origArc(key)) { 3214 _arc_map.set(static_cast<const DigraphArc&>(key), val); 3212 3215 } else { 3213 _node_map.set( key._item.second(), val);3216 _node_map.set(static_cast<const DigraphNode&>(key), val); 3214 3217 } 3215 3218 } 3216 3219 3217 3220 ReturnValue operator[](const Arc& key) { 3218 if ( Adaptor::origArc(key)) {3219 return _arc_map[ key._item.first()];3221 if (SplitNodesBase<DGR>::origArc(key)) { 3222 return _arc_map[static_cast<const DigraphArc&>(key)]; 3220 3223 } else { 3221 return _node_map[ key._item.second()];3224 return _node_map[static_cast<const DigraphNode&>(key)]; 3222 3225 } 3223 3226 } 3224 3227 3225 3228 ConstReturnValue operator[](const Arc& key) const { 3226 if ( Adaptor::origArc(key)) {3227 return _arc_map[ key._item.first()];3229 if (SplitNodesBase<DGR>::origArc(key)) { 3230 return _arc_map[static_cast<const DigraphArc&>(key)]; 3228 3231 } else { 3229 return _node_map[ key._item.second()];3232 return _node_map[static_cast<const DigraphNode&>(key)]; 3230 3233 } 3231 3234 } … … 3238 3241 public: 3239 3242 3240 template <typename _Value>3243 template <typename V> 3241 3244 class NodeMap 3242 : public SubMapExtender<Adaptor, NodeMapBase<_Value> > 3243 { 3245 : public SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > { 3246 typedef SubMapExtender<SplitNodesBase<DGR>, NodeMapBase<V> > Parent; 3247 3244 3248 public: 3245 typedef _Value Value; 3246 typedef SubMapExtender<Adaptor, NodeMapBase<Value> > Parent; 3247 3248 NodeMap(const Adaptor& adaptor) 3249 typedef V Value; 3250 3251 NodeMap(const SplitNodesBase<DGR>& adaptor) 3249 3252 : Parent(adaptor) {} 3250 3253 3251 NodeMap(const Adaptor& adaptor, const Value& value)3254 NodeMap(const SplitNodesBase<DGR>& adaptor, const V& value) 3252 3255 : Parent(adaptor, value) {} 3253 3256 … … 3264 3267 }; 3265 3268 3266 template <typename _Value>3269 template <typename V> 3267 3270 class ArcMap 3268 : public SubMapExtender<Adaptor, ArcMapBase<_Value> > 3269 { 3271 : public SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > { 3272 typedef SubMapExtender<SplitNodesBase<DGR>, ArcMapBase<V> > Parent; 3273 3270 3274 public: 3271 typedef _Value Value; 3272 typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent; 3273 3274 ArcMap(const Adaptor& adaptor) 3275 typedef V Value; 3276 3277 ArcMap(const SplitNodesBase<DGR>& adaptor) 3275 3278 : Parent(adaptor) {} 3276 3279 3277 ArcMap(const Adaptor& adaptor, const Value& value)3280 ArcMap(const SplitNodesBase<DGR>& adaptor, const V& value) 3278 3281 : Parent(adaptor, value) {} 3279 3282 … … 3294 3297 SplitNodesBase() : _digraph(0) {} 3295 3298 3296 D igraph* _digraph;3297 3298 void setDigraph(Digraph& digraph) {3299 DGR* _digraph; 3300 3301 void initialize(Digraph& digraph) { 3299 3302 _digraph = &digraph; 3300 3303 } … … 3323 3326 /// in the adaptor. 3324 3327 /// 3325 /// \tparam GR The type of the adapted digraph.3328 /// \tparam DGR The type of the adapted digraph. 3326 3329 /// It must conform to the \ref concepts::Digraph "Digraph" concept. 3327 3330 /// It is implicitly \c const. … … 3329 3332 /// \note The \c Node type of this adaptor is converible to the \c Node 3330 3333 /// type of the adapted digraph. 3331 template <typename GR>3334 template <typename DGR> 3332 3335 #ifdef DOXYGEN 3333 3336 class SplitNodes { 3334 3337 #else 3335 3338 class SplitNodes 3336 : public DigraphAdaptorExtender<SplitNodesBase<const GR> > {3339 : public DigraphAdaptorExtender<SplitNodesBase<const DGR> > { 3337 3340 #endif 3338 public: 3339 typedef GR Digraph; 3340 typedef DigraphAdaptorExtender<SplitNodesBase<const GR> > Parent; 3341 3342 typedef typename Digraph::Node DigraphNode; 3343 typedef typename Digraph::Arc DigraphArc; 3341 typedef DigraphAdaptorExtender<SplitNodesBase<const DGR> > Parent; 3342 3343 public: 3344 typedef DGR Digraph; 3345 3346 typedef typename DGR::Node DigraphNode; 3347 typedef typename DGR::Arc DigraphArc; 3344 3348 3345 3349 typedef typename Parent::Node Node; … … 3349 3353 /// 3350 3354 /// Constructor of the adaptor. 3351 SplitNodes(const D igraph& g) {3352 Parent:: setDigraph(g);3355 SplitNodes(const DGR& g) { 3356 Parent::initialize(g); 3353 3357 } 3354 3358 … … 3419 3423 /// This map adaptor class adapts two node maps of the original digraph 3420 3424 /// to get a node map of the split digraph. 3421 /// Its value type is inherited from the first node map type 3422 /// (\c InNodeMap). 3423 template <typename InNodeMap, typename OutNodeMap> 3425 /// Its value type is inherited from the first node map type (\c IN). 3426 /// \tparam IN The type of the node map for the in-nodes. 3427 /// \tparam OUT The type of the node map for the out-nodes. 3428 template <typename IN, typename OUT> 3424 3429 class CombinedNodeMap { 3425 3430 public: … … 3428 3433 typedef Node Key; 3429 3434 /// The value type of the map 3430 typedef typename I nNodeMap::Value Value;3431 3432 typedef typename MapTraits<I nNodeMap>::ReferenceMapTag ReferenceMapTag;3433 typedef typename MapTraits<I nNodeMap>::ReturnValue ReturnValue;3434 typedef typename MapTraits<I nNodeMap>::ConstReturnValue ConstReturnValue;3435 typedef typename MapTraits<I nNodeMap>::ReturnValue Reference;3436 typedef typename MapTraits<I nNodeMap>::ConstReturnValue ConstReference;3435 typedef typename IN::Value Value; 3436 3437 typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag; 3438 typedef typename MapTraits<IN>::ReturnValue ReturnValue; 3439 typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue; 3440 typedef typename MapTraits<IN>::ReturnValue Reference; 3441 typedef typename MapTraits<IN>::ConstReturnValue ConstReference; 3437 3442 3438 3443 /// Constructor 3439 CombinedNodeMap(I nNodeMap& in_map, OutNodeMap& out_map)3444 CombinedNodeMap(IN& in_map, OUT& out_map) 3440 3445 : _in_map(in_map), _out_map(out_map) {} 3441 3446 3442 3447 /// Returns the value associated with the given key. 3443 3448 Value operator[](const Key& key) const { 3444 if ( Parent::inNode(key)) {3449 if (SplitNodesBase<const DGR>::inNode(key)) { 3445 3450 return _in_map[key]; 3446 3451 } else { … … 3451 3456 /// Returns a reference to the value associated with the given key. 3452 3457 Value& operator[](const Key& key) { 3453 if ( Parent::inNode(key)) {3458 if (SplitNodesBase<const DGR>::inNode(key)) { 3454 3459 return _in_map[key]; 3455 3460 } else { … … 3460 3465 /// Sets the value associated with the given key. 3461 3466 void set(const Key& key, const Value& value) { 3462 if ( Parent::inNode(key)) {3467 if (SplitNodesBase<const DGR>::inNode(key)) { 3463 3468 _in_map.set(key, value); 3464 3469 } else { … … 3469 3474 private: 3470 3475 3471 I nNodeMap& _in_map;3472 O utNodeMap& _out_map;3476 IN& _in_map; 3477 OUT& _out_map; 3473 3478 3474 3479 }; … … 3478 3483 /// 3479 3484 /// This function just returns a combined node map. 3480 template <typename InNodeMap, typename OutNodeMap> 3481 static CombinedNodeMap<InNodeMap, OutNodeMap> 3482 combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) { 3483 return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map); 3484 } 3485 3486 template <typename InNodeMap, typename OutNodeMap> 3487 static CombinedNodeMap<const InNodeMap, OutNodeMap> 3488 combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) { 3489 return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map); 3490 } 3491 3492 template <typename InNodeMap, typename OutNodeMap> 3493 static CombinedNodeMap<InNodeMap, const OutNodeMap> 3494 combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) { 3495 return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map); 3496 } 3497 3498 template <typename InNodeMap, typename OutNodeMap> 3499 static CombinedNodeMap<const InNodeMap, const OutNodeMap> 3500 combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) { 3501 return CombinedNodeMap<const InNodeMap, 3502 const OutNodeMap>(in_map, out_map); 3485 template <typename IN, typename OUT> 3486 static CombinedNodeMap<IN, OUT> 3487 combinedNodeMap(IN& in_map, OUT& out_map) { 3488 return CombinedNodeMap<IN, OUT>(in_map, out_map); 3489 } 3490 3491 template <typename IN, typename OUT> 3492 static CombinedNodeMap<const IN, OUT> 3493 combinedNodeMap(const IN& in_map, OUT& out_map) { 3494 return CombinedNodeMap<const IN, OUT>(in_map, out_map); 3495 } 3496 3497 template <typename IN, typename OUT> 3498 static CombinedNodeMap<IN, const OUT> 3499 combinedNodeMap(IN& in_map, const OUT& out_map) { 3500 return CombinedNodeMap<IN, const OUT>(in_map, out_map); 3501 } 3502 3503 template <typename IN, typename OUT> 3504 static CombinedNodeMap<const IN, const OUT> 3505 combinedNodeMap(const IN& in_map, const OUT& out_map) { 3506 return CombinedNodeMap<const IN, const OUT>(in_map, out_map); 3503 3507 } 3504 3508 … … 3508 3512 /// This map adaptor class adapts an arc map and a node map of the 3509 3513 /// original digraph to get an arc map of the split digraph. 3510 /// Its value type is inherited from the original arc map type 3511 /// (\c ArcMap). 3512 template <typename ArcMap, typename NodeMap> 3514 /// Its value type is inherited from the original arc map type (\c AM). 3515 /// \tparam AM The type of the arc map. 3516 /// \tparam NM the type of the node map. 3517 template <typename AM, typename NM> 3513 3518 class CombinedArcMap { 3514 3519 public: … … 3517 3522 typedef Arc Key; 3518 3523 /// The value type of the map 3519 typedef typename A rcMap::Value Value;3520 3521 typedef typename MapTraits<A rcMap>::ReferenceMapTag ReferenceMapTag;3522 typedef typename MapTraits<A rcMap>::ReturnValue ReturnValue;3523 typedef typename MapTraits<A rcMap>::ConstReturnValue ConstReturnValue;3524 typedef typename MapTraits<A rcMap>::ReturnValue Reference;3525 typedef typename MapTraits<A rcMap>::ConstReturnValue ConstReference;3524 typedef typename AM::Value Value; 3525 3526 typedef typename MapTraits<AM>::ReferenceMapTag ReferenceMapTag; 3527 typedef typename MapTraits<AM>::ReturnValue ReturnValue; 3528 typedef typename MapTraits<AM>::ConstReturnValue ConstReturnValue; 3529 typedef typename MapTraits<AM>::ReturnValue Reference; 3530 typedef typename MapTraits<AM>::ConstReturnValue ConstReference; 3526 3531 3527 3532 /// Constructor 3528 CombinedArcMap(A rcMap& arc_map, NodeMap& node_map)3533 CombinedArcMap(AM& arc_map, NM& node_map) 3529 3534 : _arc_map(arc_map), _node_map(node_map) {} 3530 3535 3531 3536 /// Returns the value associated with the given key. 3532 3537 Value operator[](const Key& arc) const { 3533 if ( Parent::origArc(arc)) {3538 if (SplitNodesBase<const DGR>::origArc(arc)) { 3534 3539 return _arc_map[arc]; 3535 3540 } else { … … 3540 3545 /// Returns a reference to the value associated with the given key. 3541 3546 Value& operator[](const Key& arc) { 3542 if ( Parent::origArc(arc)) {3547 if (SplitNodesBase<const DGR>::origArc(arc)) { 3543 3548 return _arc_map[arc]; 3544 3549 } else { … … 3549 3554 /// Sets the value associated with the given key. 3550 3555 void set(const Arc& arc, const Value& val) { 3551 if ( Parent::origArc(arc)) {3556 if (SplitNodesBase<const DGR>::origArc(arc)) { 3552 3557 _arc_map.set(arc, val); 3553 3558 } else { … … 3557 3562 3558 3563 private: 3559 ArcMap& _arc_map; 3560 NodeMap& _node_map; 3564 3565 AM& _arc_map; 3566 NM& _node_map; 3567 3561 3568 }; 3562 3569 … … 3595 3602 /// \ingroup graph_adaptors 3596 3603 /// \relates SplitNodes 3597 template<typename GR>3598 SplitNodes< GR>3599 splitNodes(const GR& digraph) {3600 return SplitNodes< GR>(digraph);3604 template<typename DGR> 3605 SplitNodes<DGR> 3606 splitNodes(const DGR& digraph) { 3607 return SplitNodes<DGR>(digraph); 3601 3608 } 3602 3609 3610 #undef LEMON_SCOPE_FIX 3611 3603 3612 } //namespace lemon 3604 3613
Note: See TracChangeset
for help on using the changeset viewer.