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