Changes in / [83:3654324ec035:84:8161012eaa61] in lemon1.2
 Location:
 lemon
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bits/graph_extender.h
r57 r78 21 21 22 22 #include <lemon/bits/invalid.h> 23 #include <lemon/bits/utility.h> 23 24 24 25 #include <lemon/bits/map_extender.h> … … 64 65 } 65 66 66 Node oppositeNode(const Node &n , const Arc &e) const {67 if (n == Parent::source(e))68 return Parent::target( e);69 else if(n ==Parent::target(e))70 return Parent::source( e);67 Node oppositeNode(const Node &node, const Arc &arc) const { 68 if (node == Parent::source(arc)) 69 return Parent::target(arc); 70 else if(node == Parent::target(arc)) 71 return Parent::source(arc); 71 72 else 72 73 return INVALID; … … 95 96 96 97 class NodeIt : public Node { 97 const Digraph* digraph;98 const Digraph* _digraph; 98 99 public: 99 100 … … 102 103 NodeIt(Invalid i) : Node(i) { } 103 104 104 explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {105 _digraph .first(static_cast<Node&>(*this));106 } 107 108 NodeIt(const Digraph& _digraph, const Node& node)109 : Node(node), digraph(&_digraph) {}105 explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) { 106 _digraph>first(static_cast<Node&>(*this)); 107 } 108 109 NodeIt(const Digraph& digraph, const Node& node) 110 : Node(node), _digraph(&digraph) {} 110 111 111 112 NodeIt& operator++() { 112 digraph>next(*this);113 _digraph>next(*this); 113 114 return *this; 114 115 } … … 118 119 119 120 class ArcIt : public Arc { 120 const Digraph* digraph;121 const Digraph* _digraph; 121 122 public: 122 123 … … 125 126 ArcIt(Invalid i) : Arc(i) { } 126 127 127 explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {128 _digraph .first(static_cast<Arc&>(*this));129 } 130 131 ArcIt(const Digraph& _digraph, const Arc& e) :132 Arc( e), digraph(&_digraph) { }128 explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) { 129 _digraph>first(static_cast<Arc&>(*this)); 130 } 131 132 ArcIt(const Digraph& digraph, const Arc& arc) : 133 Arc(arc), _digraph(&digraph) { } 133 134 134 135 ArcIt& operator++() { 135 digraph>next(*this);136 _digraph>next(*this); 136 137 return *this; 137 138 } … … 141 142 142 143 class OutArcIt : public Arc { 143 const Digraph* digraph;144 const Digraph* _digraph; 144 145 public: 145 146 … … 148 149 OutArcIt(Invalid i) : Arc(i) { } 149 150 150 OutArcIt(const Digraph& _digraph, const Node& node)151 : digraph(&_digraph) {152 _digraph .firstOut(*this, node);153 } 154 155 OutArcIt(const Digraph& _digraph, const Arc& arc)156 : Arc(arc), digraph(&_digraph) {}151 OutArcIt(const Digraph& digraph, const Node& node) 152 : _digraph(&digraph) { 153 _digraph>firstOut(*this, node); 154 } 155 156 OutArcIt(const Digraph& digraph, const Arc& arc) 157 : Arc(arc), _digraph(&digraph) {} 157 158 158 159 OutArcIt& operator++() { 159 digraph>nextOut(*this);160 _digraph>nextOut(*this); 160 161 return *this; 161 162 } … … 165 166 166 167 class InArcIt : public Arc { 167 const Digraph* digraph;168 const Digraph* _digraph; 168 169 public: 169 170 … … 172 173 InArcIt(Invalid i) : Arc(i) { } 173 174 174 InArcIt(const Digraph& _digraph, const Node& node)175 : digraph(&_digraph) {176 _digraph .firstIn(*this, node);177 } 178 179 InArcIt(const Digraph& _digraph, const Arc& arc) :180 Arc(arc), digraph(&_digraph) {}175 InArcIt(const Digraph& digraph, const Node& node) 176 : _digraph(&digraph) { 177 _digraph>firstIn(*this, node); 178 } 179 180 InArcIt(const Digraph& digraph, const Arc& arc) : 181 Arc(arc), _digraph(&digraph) {} 181 182 182 183 InArcIt& operator++() { 183 digraph>nextIn(*this);184 _digraph>nextIn(*this); 184 185 return *this; 185 186 } … … 190 191 /// 191 192 /// Returns the base node (i.e. the source in this case) of the iterator 192 Node baseNode(const OutArcIt & e) const {193 return Parent::source( e);193 Node baseNode(const OutArcIt &arc) const { 194 return Parent::source(arc); 194 195 } 195 196 /// \brief Running node of the iterator … … 197 198 /// Returns the running node (i.e. the target in this case) of the 198 199 /// iterator 199 Node runningNode(const OutArcIt & e) const {200 return Parent::target( e);200 Node runningNode(const OutArcIt &arc) const { 201 return Parent::target(arc); 201 202 } 202 203 … … 204 205 /// 205 206 /// Returns the base node (i.e. the target in this case) of the iterator 206 Node baseNode(const InArcIt & e) const {207 return Parent::target( e);207 Node baseNode(const InArcIt &arc) const { 208 return Parent::target(arc); 208 209 } 209 210 /// \brief Running node of the iterator … … 211 212 /// Returns the running node (i.e. the source in this case) of the 212 213 /// iterator 213 Node runningNode(const InArcIt & e) const {214 return Parent::source( e);214 Node runningNode(const InArcIt &arc) const { 215 return Parent::source(arc); 215 216 } 216 217 … … 324 325 }; 325 326 326 /// \ingroup graphbits327 /// \ingroup _graphbits 327 328 /// 328 329 /// \brief Extender for the Graphs … … 332 333 333 334 typedef Base Parent; 334 typedef GraphExtender Digraph; 335 typedef GraphExtender Graph; 336 337 typedef True UndirectedTag; 335 338 336 339 typedef typename Parent::Node Node; … … 373 376 } 374 377 375 Arc oppositeArc(const Arc & e) const {376 return Parent::direct( e, !Parent::direction(e));378 Arc oppositeArc(const Arc &arc) const { 379 return Parent::direct(arc, !Parent::direction(arc)); 377 380 } 378 381 379 382 using Parent::direct; 380 Arc direct(const Edge & ue, const Node &s) const {381 return Parent::direct( ue, Parent::source(ue) == s);383 Arc direct(const Edge &edge, const Node &node) const { 384 return Parent::direct(edge, Parent::source(edge) == node); 382 385 } 383 386 … … 412 415 413 416 class NodeIt : public Node { 414 const Digraph* digraph;417 const Graph* _graph; 415 418 public: 416 419 … … 419 422 NodeIt(Invalid i) : Node(i) { } 420 423 421 explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {422 _ digraph.first(static_cast<Node&>(*this));423 } 424 425 NodeIt(const Digraph& _digraph, const Node& node)426 : Node(node), digraph(&_digraph) {}424 explicit NodeIt(const Graph& graph) : _graph(&graph) { 425 _graph>first(static_cast<Node&>(*this)); 426 } 427 428 NodeIt(const Graph& graph, const Node& node) 429 : Node(node), _graph(&graph) {} 427 430 428 431 NodeIt& operator++() { 429 digraph>next(*this);432 _graph>next(*this); 430 433 return *this; 431 434 } … … 435 438 436 439 class ArcIt : public Arc { 437 const Digraph* digraph;440 const Graph* _graph; 438 441 public: 439 442 … … 442 445 ArcIt(Invalid i) : Arc(i) { } 443 446 444 explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {445 _ digraph.first(static_cast<Arc&>(*this));446 } 447 448 ArcIt(const Digraph& _digraph, const Arc& e) :449 Arc( e), digraph(&_digraph) { }447 explicit ArcIt(const Graph& graph) : _graph(&graph) { 448 _graph>first(static_cast<Arc&>(*this)); 449 } 450 451 ArcIt(const Graph& graph, const Arc& arc) : 452 Arc(arc), _graph(&graph) { } 450 453 451 454 ArcIt& operator++() { 452 digraph>next(*this);455 _graph>next(*this); 453 456 return *this; 454 457 } … … 458 461 459 462 class OutArcIt : public Arc { 460 const Digraph* digraph;463 const Graph* _graph; 461 464 public: 462 465 … … 465 468 OutArcIt(Invalid i) : Arc(i) { } 466 469 467 OutArcIt(const Digraph& _digraph, const Node& node)468 : digraph(&_digraph) {469 _ digraph.firstOut(*this, node);470 } 471 472 OutArcIt(const Digraph& _digraph, const Arc& arc)473 : Arc(arc), digraph(&_digraph) {}470 OutArcIt(const Graph& graph, const Node& node) 471 : _graph(&graph) { 472 _graph>firstOut(*this, node); 473 } 474 475 OutArcIt(const Graph& graph, const Arc& arc) 476 : Arc(arc), _graph(&graph) {} 474 477 475 478 OutArcIt& operator++() { 476 digraph>nextOut(*this);479 _graph>nextOut(*this); 477 480 return *this; 478 481 } … … 482 485 483 486 class InArcIt : public Arc { 484 const Digraph* digraph;487 const Graph* _graph; 485 488 public: 486 489 … … 489 492 InArcIt(Invalid i) : Arc(i) { } 490 493 491 InArcIt(const Digraph& _digraph, const Node& node)492 : digraph(&_digraph) {493 _ digraph.firstIn(*this, node);494 } 495 496 InArcIt(const Digraph& _digraph, const Arc& arc) :497 Arc(arc), digraph(&_digraph) {}494 InArcIt(const Graph& graph, const Node& node) 495 : _graph(&graph) { 496 _graph>firstIn(*this, node); 497 } 498 499 InArcIt(const Graph& graph, const Arc& arc) : 500 Arc(arc), _graph(&graph) {} 498 501 499 502 InArcIt& operator++() { 500 digraph>nextIn(*this);503 _graph>nextIn(*this); 501 504 return *this; 502 505 } … … 506 509 507 510 class EdgeIt : public Parent::Edge { 508 const Digraph* digraph;511 const Graph* _graph; 509 512 public: 510 513 … … 513 516 EdgeIt(Invalid i) : Edge(i) { } 514 517 515 explicit EdgeIt(const Digraph& _digraph) : digraph(&_digraph) {516 _ digraph.first(static_cast<Edge&>(*this));517 } 518 519 EdgeIt(const Digraph& _digraph, const Edge&e) :520 Edge(e ), digraph(&_digraph) { }518 explicit EdgeIt(const Graph& graph) : _graph(&graph) { 519 _graph>first(static_cast<Edge&>(*this)); 520 } 521 522 EdgeIt(const Graph& graph, const Edge& edge) : 523 Edge(edge), _graph(&graph) { } 521 524 522 525 EdgeIt& operator++() { 523 digraph>next(*this);524 return *this; 525 } 526 527 }; 528 529 class Inc ArcIt : public Parent::Edge {526 _graph>next(*this); 527 return *this; 528 } 529 530 }; 531 532 class IncEdgeIt : public Parent::Edge { 530 533 friend class GraphExtender; 531 const Digraph* digraph;532 bool direction;533 public: 534 535 Inc ArcIt() { }536 537 Inc ArcIt(Invalid i) : Edge(i),direction(false) { }538 539 Inc ArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {540 _ digraph.firstInc(*this, direction, n);541 } 542 543 Inc ArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)544 : digraph(&_digraph), Edge(ue) {545 direction = (_digraph.source(ue) == n);546 } 547 548 Inc ArcIt& operator++() {549 digraph>nextInc(*this,direction);534 const Graph* _graph; 535 bool _direction; 536 public: 537 538 IncEdgeIt() { } 539 540 IncEdgeIt(Invalid i) : Edge(i), _direction(false) { } 541 542 IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) { 543 _graph>firstInc(*this, _direction, node); 544 } 545 546 IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node) 547 : _graph(&graph), Edge(edge) { 548 _direction = (_graph>source(edge) == node); 549 } 550 551 IncEdgeIt& operator++() { 552 _graph>nextInc(*this, _direction); 550 553 return *this; 551 554 } … … 555 558 /// 556 559 /// Returns the base node (ie. the source in this case) of the iterator 557 Node baseNode(const OutArcIt & e) const {558 return Parent::source(static_cast<const Arc&>( e));560 Node baseNode(const OutArcIt &arc) const { 561 return Parent::source(static_cast<const Arc&>(arc)); 559 562 } 560 563 /// \brief Running node of the iterator … … 562 565 /// Returns the running node (ie. the target in this case) of the 563 566 /// iterator 564 Node runningNode(const OutArcIt & e) const {565 return Parent::target(static_cast<const Arc&>( e));567 Node runningNode(const OutArcIt &arc) const { 568 return Parent::target(static_cast<const Arc&>(arc)); 566 569 } 567 570 … … 569 572 /// 570 573 /// Returns the base node (ie. the target in this case) of the iterator 571 Node baseNode(const InArcIt & e) const {572 return Parent::target(static_cast<const Arc&>( e));574 Node baseNode(const InArcIt &arc) const { 575 return Parent::target(static_cast<const Arc&>(arc)); 573 576 } 574 577 /// \brief Running node of the iterator … … 576 579 /// Returns the running node (ie. the source in this case) of the 577 580 /// iterator 578 Node runningNode(const InArcIt & e) const {579 return Parent::source(static_cast<const Arc&>( e));581 Node runningNode(const InArcIt &arc) const { 582 return Parent::source(static_cast<const Arc&>(arc)); 580 583 } 581 584 … … 583 586 /// 584 587 /// Returns the base node of the iterator 585 Node baseNode(const Inc ArcIt &e) const {586 return e .direction ? source(e) : target(e);588 Node baseNode(const IncEdgeIt &edge) const { 589 return edge._direction ? source(edge) : target(edge); 587 590 } 588 591 /// Running node of the iterator 589 592 /// 590 593 /// Returns the running node of the iterator 591 Node runningNode(const Inc ArcIt &e) const {592 return e .direction ? target(e) : source(e);594 Node runningNode(const IncEdgeIt &edge) const { 595 return edge._direction ? target(edge) : source(edge); 593 596 } 594 597 … … 597 600 template <typename _Value> 598 601 class NodeMap 599 : public MapExtender<DefaultMap< Digraph, Node, _Value> > {600 public: 601 typedef GraphExtender Digraph;602 typedef MapExtender<DefaultMap< Digraph, Node, _Value> > Parent;603 604 NodeMap(const Digraph& digraph)605 : Parent( digraph) {}606 NodeMap(const Digraph& digraph, const _Value& value)607 : Parent( digraph, value) {}602 : public MapExtender<DefaultMap<Graph, Node, _Value> > { 603 public: 604 typedef GraphExtender Graph; 605 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; 606 607 NodeMap(const Graph& graph) 608 : Parent(graph) {} 609 NodeMap(const Graph& graph, const _Value& value) 610 : Parent(graph, value) {} 608 611 609 612 NodeMap& operator=(const NodeMap& cmap) { … … 621 624 template <typename _Value> 622 625 class ArcMap 623 : public MapExtender<DefaultMap< Digraph, Arc, _Value> > {624 public: 625 typedef GraphExtender Digraph;626 typedef MapExtender<DefaultMap< Digraph, Arc, _Value> > Parent;627 628 ArcMap(const Digraph& digraph)629 : Parent( digraph) {}630 ArcMap(const Digraph& digraph, const _Value& value)631 : Parent( digraph, value) {}626 : public MapExtender<DefaultMap<Graph, Arc, _Value> > { 627 public: 628 typedef GraphExtender Graph; 629 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent; 630 631 ArcMap(const Graph& graph) 632 : Parent(graph) {} 633 ArcMap(const Graph& graph, const _Value& value) 634 : Parent(graph, value) {} 632 635 633 636 ArcMap& operator=(const ArcMap& cmap) { … … 645 648 template <typename _Value> 646 649 class EdgeMap 647 : public MapExtender<DefaultMap< Digraph, Edge, _Value> > {648 public: 649 typedef GraphExtender Digraph;650 typedef MapExtender<DefaultMap< Digraph, Edge, _Value> > Parent;651 652 EdgeMap(const Digraph& digraph)653 : Parent( digraph) {}654 655 EdgeMap(const Digraph& digraph, const _Value& value)656 : Parent( digraph, value) {}650 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 651 public: 652 typedef GraphExtender Graph; 653 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 654 655 EdgeMap(const Graph& graph) 656 : Parent(graph) {} 657 658 EdgeMap(const Graph& graph, const _Value& value) 659 : Parent(graph, value) {} 657 660 658 661 EdgeMap& operator=(const EdgeMap& cmap) { … … 693 696 } 694 697 695 template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>696 void build(const Digraph& digraph, NodeRefMap& nodeRef,698 template <typename Graph, typename NodeRefMap, typename EdgeRefMap> 699 void build(const Graph& graph, NodeRefMap& nodeRef, 697 700 EdgeRefMap& edgeRef) { 698 Parent::build( digraph, nodeRef, edgeRef);701 Parent::build(graph, nodeRef, edgeRef); 699 702 notifier(Node()).build(); 700 703 notifier(Edge()).build(); … … 721 724 722 725 void erase(const Edge& edge) { 723 std::vector<Arc> ev;724 ev.push_back(Parent::direct(edge, true));725 ev.push_back(Parent::direct(edge, false));726 notifier(Arc()).erase( ev);726 std::vector<Arc> av; 727 av.push_back(Parent::direct(edge, true)); 728 av.push_back(Parent::direct(edge, false)); 729 notifier(Arc()).erase(av); 727 730 notifier(Edge()).erase(edge); 728 731 Parent::erase(edge); 
lemon/concepts/graph.h
r61 r78 64 64 /// the EdgeMap to map values for the edges. The InArcIt and 65 65 /// OutArcIt iterates on the same edges but with opposite 66 /// direction. The Inc ArcIt iterates also on the same edges66 /// direction. The IncEdgeIt iterates also on the same edges 67 67 /// as the OutArcIt and InArcIt but it is not convertible to Arc just 68 68 /// to Edge. … … 271 271 ///\code 272 272 /// int count=0; 273 /// for(Graph::Inc ArcIt e(g, n); e!=INVALID; ++e) ++count;273 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; 274 274 ///\endcode 275 class Inc ArcIt : public Edge {276 public: 277 /// Default constructor 278 279 /// @warning The default constructor sets the iterator 280 /// to an undefined value. 281 Inc ArcIt() { }282 /// Copy constructor. 283 284 /// Copy constructor. 285 /// 286 Inc ArcIt(const IncArcIt& e) : Edge(e) { }287 /// Initialize the iterator to be invalid. 288 289 /// Initialize the iterator to be invalid. 290 /// 291 Inc ArcIt(Invalid) { }275 class IncEdgeIt : public Edge { 276 public: 277 /// Default constructor 278 279 /// @warning The default constructor sets the iterator 280 /// to an undefined value. 281 IncEdgeIt() { } 282 /// Copy constructor. 283 284 /// Copy constructor. 285 /// 286 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } 287 /// Initialize the iterator to be invalid. 288 289 /// Initialize the iterator to be invalid. 290 /// 291 IncEdgeIt(Invalid) { } 292 292 /// This constructor sets the iterator to first incident arc. 293 293 294 294 /// This constructor set the iterator to the first incident arc of 295 295 /// the node. 296 Inc ArcIt(const Graph&, const Node&) { }297 /// Edge > Inc ArcIt conversion296 IncEdgeIt(const Graph&, const Node&) { } 297 /// Edge > IncEdgeIt conversion 298 298 299 299 /// Sets the iterator to the value of the trivial iterator \c e. 300 300 /// This feature necessitates that each time we 301 301 /// iterate the arcset, the iteration order is the same. 302 Inc ArcIt(const Graph&, const Edge&) { }302 IncEdgeIt(const Graph&, const Edge&) { } 303 303 /// Next incident arc 304 304 305 305 /// Assign the iterator to the next incident arc 306 306 /// of the corresponding node. 307 Inc ArcIt& operator++() { return *this; }307 IncEdgeIt& operator++() { return *this; } 308 308 }; 309 309 … … 721 721 /// 722 722 /// Returns the base node of the iterator 723 Node baseNode(Inc ArcIt) const {723 Node baseNode(IncEdgeIt) const { 724 724 return INVALID; 725 725 } … … 728 728 /// 729 729 /// Returns the running node of the iterator 730 Node runningNode(Inc ArcIt) const {730 Node runningNode(IncEdgeIt) const { 731 731 return INVALID; 732 732 } 
lemon/concepts/graph_components.h
r57 r78 829 829 /// This iterator goes trough the incident arcs of a certain 830 830 /// node of a graph. 831 typedef GraphIncIt<Graph, Edge, Node, 'u'> Inc ArcIt;831 typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt; 832 832 /// \brief The base node of the iterator. 833 833 /// 834 834 /// Gives back the base node of the iterator. 835 Node baseNode(const Inc ArcIt&) const { return INVALID; }835 Node baseNode(const IncEdgeIt&) const { return INVALID; } 836 836 837 837 /// \brief The running node of the iterator. 838 838 /// 839 839 /// Gives back the running node of the iterator. 840 Node runningNode(const Inc ArcIt&) const { return INVALID; }840 Node runningNode(const IncEdgeIt&) const { return INVALID; } 841 841 842 842 /// @} … … 866 866 typename _Graph::EdgeIt >(); 867 867 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 868 typename _Graph::Node, 'u'>, typename _Graph::Inc ArcIt>();868 typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>(); 869 869 870 870 typename _Graph::Node n; 871 typename _Graph::Inc ArcIt ueit(INVALID);871 typename _Graph::IncEdgeIt ueit(INVALID); 872 872 n = graph.baseNode(ueit); 873 873 n = graph.runningNode(ueit);
Note: See TracChangeset
for help on using the changeset viewer.