Changeset 559:9b9ffe7d9b75 in lemon for lemon/edge_set.h
 Timestamp:
 02/13/09 13:29:28 (14 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/edge_set.h
r491 r559 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
Note: See TracChangeset
for help on using the changeset viewer.