Changeset 78:c46b3453455f in lemon-1.0 for lemon
- Timestamp:
- 02/28/08 17:06:02 (17 years ago)
- Branch:
- default
- Children:
- 84:8161012eaa61, 92:5d4decd1b870
- Phase:
- public
- Location:
- lemon
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/graph_extender.h
r77 r78 65 65 } 66 66 67 Node oppositeNode(const Node &n , const Arc &e) const {68 if (n == Parent::source(e))69 return Parent::target( e);70 else if(n ==Parent::target(e))71 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); 72 72 else 73 73 return INVALID; … … 96 96 97 97 class NodeIt : public Node { 98 const Digraph* digraph;98 const Digraph* _digraph; 99 99 public: 100 100 … … 103 103 NodeIt(Invalid i) : Node(i) { } 104 104 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) {}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) {} 111 111 112 112 NodeIt& operator++() { 113 digraph->next(*this);113 _digraph->next(*this); 114 114 return *this; 115 115 } … … 119 119 120 120 class ArcIt : public Arc { 121 const Digraph* digraph;121 const Digraph* _digraph; 122 122 public: 123 123 … … 126 126 ArcIt(Invalid i) : Arc(i) { } 127 127 128 explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {129 _digraph .first(static_cast<Arc&>(*this));130 } 131 132 ArcIt(const Digraph& _digraph, const Arc& e) :133 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) { } 134 134 135 135 ArcIt& operator++() { 136 digraph->next(*this);136 _digraph->next(*this); 137 137 return *this; 138 138 } … … 142 142 143 143 class OutArcIt : public Arc { 144 const Digraph* digraph;144 const Digraph* _digraph; 145 145 public: 146 146 … … 149 149 OutArcIt(Invalid i) : Arc(i) { } 150 150 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) {}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) {} 158 158 159 159 OutArcIt& operator++() { 160 digraph->nextOut(*this);160 _digraph->nextOut(*this); 161 161 return *this; 162 162 } … … 166 166 167 167 class InArcIt : public Arc { 168 const Digraph* digraph;168 const Digraph* _digraph; 169 169 public: 170 170 … … 173 173 InArcIt(Invalid i) : Arc(i) { } 174 174 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) {}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) {} 182 182 183 183 InArcIt& operator++() { 184 digraph->nextIn(*this);184 _digraph->nextIn(*this); 185 185 return *this; 186 186 } … … 191 191 /// 192 192 /// Returns the base node (i.e. the source in this case) of the iterator 193 Node baseNode(const OutArcIt & e) const {194 return Parent::source( e);193 Node baseNode(const OutArcIt &arc) const { 194 return Parent::source(arc); 195 195 } 196 196 /// \brief Running node of the iterator … … 198 198 /// Returns the running node (i.e. the target in this case) of the 199 199 /// iterator 200 Node runningNode(const OutArcIt & e) const {201 return Parent::target( e);200 Node runningNode(const OutArcIt &arc) const { 201 return Parent::target(arc); 202 202 } 203 203 … … 205 205 /// 206 206 /// Returns the base node (i.e. the target in this case) of the iterator 207 Node baseNode(const InArcIt & e) const {208 return Parent::target( e);207 Node baseNode(const InArcIt &arc) const { 208 return Parent::target(arc); 209 209 } 210 210 /// \brief Running node of the iterator … … 212 212 /// Returns the running node (i.e. the source in this case) of the 213 213 /// iterator 214 Node runningNode(const InArcIt & e) const {215 return Parent::source( e);214 Node runningNode(const InArcIt &arc) const { 215 return Parent::source(arc); 216 216 } 217 217 … … 325 325 }; 326 326 327 /// \ingroup graphbits327 /// \ingroup _graphbits 328 328 /// 329 329 /// \brief Extender for the Graphs … … 333 333 334 334 typedef Base Parent; 335 typedef GraphExtender Digraph;335 typedef GraphExtender Graph; 336 336 337 337 typedef True UndirectedTag; … … 376 376 } 377 377 378 Arc oppositeArc(const Arc & e) const {379 return Parent::direct( e, !Parent::direction(e));378 Arc oppositeArc(const Arc &arc) const { 379 return Parent::direct(arc, !Parent::direction(arc)); 380 380 } 381 381 382 382 using Parent::direct; 383 Arc direct(const Edge & ue, const Node &s) const {384 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); 385 385 } 386 386 … … 415 415 416 416 class NodeIt : public Node { 417 const Digraph* digraph;417 const Graph* _graph; 418 418 public: 419 419 … … 422 422 NodeIt(Invalid i) : Node(i) { } 423 423 424 explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {425 _ digraph.first(static_cast<Node&>(*this));426 } 427 428 NodeIt(const Digraph& _digraph, const Node& node)429 : 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) {} 430 430 431 431 NodeIt& operator++() { 432 digraph->next(*this);432 _graph->next(*this); 433 433 return *this; 434 434 } … … 438 438 439 439 class ArcIt : public Arc { 440 const Digraph* digraph;440 const Graph* _graph; 441 441 public: 442 442 … … 445 445 ArcIt(Invalid i) : Arc(i) { } 446 446 447 explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {448 _ digraph.first(static_cast<Arc&>(*this));449 } 450 451 ArcIt(const Digraph& _digraph, const Arc& e) :452 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) { } 453 453 454 454 ArcIt& operator++() { 455 digraph->next(*this);455 _graph->next(*this); 456 456 return *this; 457 457 } … … 461 461 462 462 class OutArcIt : public Arc { 463 const Digraph* digraph;463 const Graph* _graph; 464 464 public: 465 465 … … 468 468 OutArcIt(Invalid i) : Arc(i) { } 469 469 470 OutArcIt(const Digraph& _digraph, const Node& node)471 : digraph(&_digraph) {472 _ digraph.firstOut(*this, node);473 } 474 475 OutArcIt(const Digraph& _digraph, const Arc& arc)476 : 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) {} 477 477 478 478 OutArcIt& operator++() { 479 digraph->nextOut(*this);479 _graph->nextOut(*this); 480 480 return *this; 481 481 } … … 485 485 486 486 class InArcIt : public Arc { 487 const Digraph* digraph;487 const Graph* _graph; 488 488 public: 489 489 … … 492 492 InArcIt(Invalid i) : Arc(i) { } 493 493 494 InArcIt(const Digraph& _digraph, const Node& node)495 : digraph(&_digraph) {496 _ digraph.firstIn(*this, node);497 } 498 499 InArcIt(const Digraph& _digraph, const Arc& arc) :500 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) {} 501 501 502 502 InArcIt& operator++() { 503 digraph->nextIn(*this);503 _graph->nextIn(*this); 504 504 return *this; 505 505 } … … 509 509 510 510 class EdgeIt : public Parent::Edge { 511 const Digraph* digraph;511 const Graph* _graph; 512 512 public: 513 513 … … 516 516 EdgeIt(Invalid i) : Edge(i) { } 517 517 518 explicit EdgeIt(const Digraph& _digraph) : digraph(&_digraph) {519 _ digraph.first(static_cast<Edge&>(*this));520 } 521 522 EdgeIt(const Digraph& _digraph, const Edge&e) :523 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) { } 524 524 525 525 EdgeIt& operator++() { 526 digraph->next(*this);527 return *this; 528 } 529 530 }; 531 532 class Inc ArcIt : public Parent::Edge {526 _graph->next(*this); 527 return *this; 528 } 529 530 }; 531 532 class IncEdgeIt : public Parent::Edge { 533 533 friend class GraphExtender; 534 const Digraph* digraph;535 bool direction;536 public: 537 538 Inc ArcIt() { }539 540 Inc ArcIt(Invalid i) : Edge(i),direction(false) { }541 542 Inc ArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {543 _ digraph.firstInc(*this, direction, n);544 } 545 546 Inc ArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)547 : digraph(&_digraph), Edge(ue) {548 direction = (_digraph.source(ue) == n);549 } 550 551 Inc ArcIt& operator++() {552 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); 553 553 return *this; 554 554 } … … 558 558 /// 559 559 /// Returns the base node (ie. the source in this case) of the iterator 560 Node baseNode(const OutArcIt & e) const {561 return Parent::source(static_cast<const Arc&>( e));560 Node baseNode(const OutArcIt &arc) const { 561 return Parent::source(static_cast<const Arc&>(arc)); 562 562 } 563 563 /// \brief Running node of the iterator … … 565 565 /// Returns the running node (ie. the target in this case) of the 566 566 /// iterator 567 Node runningNode(const OutArcIt & e) const {568 return Parent::target(static_cast<const Arc&>( e));567 Node runningNode(const OutArcIt &arc) const { 568 return Parent::target(static_cast<const Arc&>(arc)); 569 569 } 570 570 … … 572 572 /// 573 573 /// Returns the base node (ie. the target in this case) of the iterator 574 Node baseNode(const InArcIt & e) const {575 return Parent::target(static_cast<const Arc&>( e));574 Node baseNode(const InArcIt &arc) const { 575 return Parent::target(static_cast<const Arc&>(arc)); 576 576 } 577 577 /// \brief Running node of the iterator … … 579 579 /// Returns the running node (ie. the source in this case) of the 580 580 /// iterator 581 Node runningNode(const InArcIt & e) const {582 return Parent::source(static_cast<const Arc&>( e));581 Node runningNode(const InArcIt &arc) const { 582 return Parent::source(static_cast<const Arc&>(arc)); 583 583 } 584 584 … … 586 586 /// 587 587 /// Returns the base node of the iterator 588 Node baseNode(const Inc ArcIt &e) const {589 return e .direction ? source(e) : target(e);588 Node baseNode(const IncEdgeIt &edge) const { 589 return edge._direction ? source(edge) : target(edge); 590 590 } 591 591 /// Running node of the iterator 592 592 /// 593 593 /// Returns the running node of the iterator 594 Node runningNode(const Inc ArcIt &e) const {595 return e .direction ? target(e) : source(e);594 Node runningNode(const IncEdgeIt &edge) const { 595 return edge._direction ? target(edge) : source(edge); 596 596 } 597 597 … … 600 600 template <typename _Value> 601 601 class NodeMap 602 : public MapExtender<DefaultMap< Digraph, Node, _Value> > {603 public: 604 typedef GraphExtender Digraph;605 typedef MapExtender<DefaultMap< Digraph, Node, _Value> > Parent;606 607 NodeMap(const Digraph& digraph)608 : Parent( digraph) {}609 NodeMap(const Digraph& digraph, const _Value& value)610 : 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) {} 611 611 612 612 NodeMap& operator=(const NodeMap& cmap) { … … 624 624 template <typename _Value> 625 625 class ArcMap 626 : public MapExtender<DefaultMap< Digraph, Arc, _Value> > {627 public: 628 typedef GraphExtender Digraph;629 typedef MapExtender<DefaultMap< Digraph, Arc, _Value> > Parent;630 631 ArcMap(const Digraph& digraph)632 : Parent( digraph) {}633 ArcMap(const Digraph& digraph, const _Value& value)634 : 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) {} 635 635 636 636 ArcMap& operator=(const ArcMap& cmap) { … … 648 648 template <typename _Value> 649 649 class EdgeMap 650 : public MapExtender<DefaultMap< Digraph, Edge, _Value> > {651 public: 652 typedef GraphExtender Digraph;653 typedef MapExtender<DefaultMap< Digraph, Edge, _Value> > Parent;654 655 EdgeMap(const Digraph& digraph)656 : Parent( digraph) {}657 658 EdgeMap(const Digraph& digraph, const _Value& value)659 : 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) {} 660 660 661 661 EdgeMap& operator=(const EdgeMap& cmap) { … … 696 696 } 697 697 698 template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>699 void build(const Digraph& digraph, NodeRefMap& nodeRef,698 template <typename Graph, typename NodeRefMap, typename EdgeRefMap> 699 void build(const Graph& graph, NodeRefMap& nodeRef, 700 700 EdgeRefMap& edgeRef) { 701 Parent::build( digraph, nodeRef, edgeRef);701 Parent::build(graph, nodeRef, edgeRef); 702 702 notifier(Node()).build(); 703 703 notifier(Edge()).build(); … … 724 724 725 725 void erase(const Edge& edge) { 726 std::vector<Arc> ev;727 ev.push_back(Parent::direct(edge, true));728 ev.push_back(Parent::direct(edge, false));729 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); 730 730 notifier(Edge()).erase(edge); 731 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 arc-set, 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.