Changeset 209:765619b7cbb2 in lemon1.2 for lemon/bits/graph_extender.h
 Timestamp:
 07/13/08 20:51:02 (16 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bits/graph_extender.h
r125 r209 1 /* * C++*1 /* * mode: C++; indenttabsmode: nil; * 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 20032008 … … 67 67 Node oppositeNode(const Node &node, const Arc &arc) const { 68 68 if (node == Parent::source(arc)) 69 69 return Parent::target(arc); 70 70 else if(node == Parent::target(arc)) 71 71 return Parent::source(arc); 72 72 else 73 73 return INVALID; 74 74 } 75 75 … … 90 90 return node_notifier; 91 91 } 92 92 93 93 ArcNotifier& notifier(Arc) const { 94 94 return arc_notifier; 95 95 } 96 96 97 class NodeIt : public Node { 97 class NodeIt : public Node { 98 98 const Digraph* _digraph; 99 99 public: … … 104 104 105 105 explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) { 106 107 } 108 109 NodeIt(const Digraph& digraph, const Node& node) 110 111 112 NodeIt& operator++() { 113 114 return *this; 115 } 116 117 }; 118 119 120 class ArcIt : public Arc { 106 _digraph>first(static_cast<Node&>(*this)); 107 } 108 109 NodeIt(const Digraph& digraph, const Node& node) 110 : Node(node), _digraph(&digraph) {} 111 112 NodeIt& operator++() { 113 _digraph>next(*this); 114 return *this; 115 } 116 117 }; 118 119 120 class ArcIt : public Arc { 121 121 const Digraph* _digraph; 122 122 public: … … 127 127 128 128 explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) { 129 130 } 131 132 ArcIt(const Digraph& digraph, const Arc& arc) : 133 134 135 ArcIt& operator++() { 136 137 return *this; 138 } 139 140 }; 141 142 143 class OutArcIt : public Arc { 129 _digraph>first(static_cast<Arc&>(*this)); 130 } 131 132 ArcIt(const Digraph& digraph, const Arc& arc) : 133 Arc(arc), _digraph(&digraph) { } 134 135 ArcIt& operator++() { 136 _digraph>next(*this); 137 return *this; 138 } 139 140 }; 141 142 143 class OutArcIt : public Arc { 144 144 const Digraph* _digraph; 145 145 public: … … 149 149 OutArcIt(Invalid i) : Arc(i) { } 150 150 151 OutArcIt(const Digraph& digraph, const Node& node) 152 153 154 } 155 156 OutArcIt(const Digraph& digraph, const Arc& arc) 157 158 159 OutArcIt& operator++() { 160 161 return *this; 162 } 163 164 }; 165 166 167 class InArcIt : public Arc { 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 159 OutArcIt& operator++() { 160 _digraph>nextOut(*this); 161 return *this; 162 } 163 164 }; 165 166 167 class InArcIt : public Arc { 168 168 const Digraph* _digraph; 169 169 public: … … 173 173 InArcIt(Invalid i) : Arc(i) { } 174 174 175 InArcIt(const Digraph& digraph, const Node& node) 176 177 178 } 179 180 InArcIt(const Digraph& digraph, const Arc& arc) : 181 182 183 InArcIt& operator++() { 184 185 return *this; 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 183 InArcIt& operator++() { 184 _digraph>nextIn(*this); 185 return *this; 186 186 } 187 187 … … 216 216 } 217 217 218 218 219 219 template <typename _Value> 220 class NodeMap 220 class NodeMap 221 221 : public MapExtender<DefaultMap<Digraph, Node, _Value> > { 222 222 public: … … 224 224 typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent; 225 225 226 explicit NodeMap(const Digraph& digraph) 227 228 NodeMap(const Digraph& digraph, const _Value& value) 229 226 explicit NodeMap(const Digraph& digraph) 227 : Parent(digraph) {} 228 NodeMap(const Digraph& digraph, const _Value& value) 229 : Parent(digraph, value) {} 230 230 231 231 NodeMap& operator=(const NodeMap& cmap) { 232 232 return operator=<NodeMap>(cmap); 233 233 } 234 234 … … 236 236 NodeMap& operator=(const CMap& cmap) { 237 237 Parent::operator=(cmap); 238 238 return *this; 239 239 } 240 240 … … 242 242 243 243 template <typename _Value> 244 class ArcMap 244 class ArcMap 245 245 : public MapExtender<DefaultMap<Digraph, Arc, _Value> > { 246 246 public: … … 248 248 typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent; 249 249 250 explicit ArcMap(const Digraph& digraph) 251 252 ArcMap(const Digraph& digraph, const _Value& value) 253 250 explicit ArcMap(const Digraph& digraph) 251 : Parent(digraph) {} 252 ArcMap(const Digraph& digraph, const _Value& value) 253 : Parent(digraph, value) {} 254 254 255 255 ArcMap& operator=(const ArcMap& cmap) { 256 256 return operator=<ArcMap>(cmap); 257 257 } 258 258 … … 260 260 ArcMap& operator=(const CMap& cmap) { 261 261 Parent::operator=(cmap); 262 262 return *this; 263 263 } 264 264 }; … … 270 270 return node; 271 271 } 272 272 273 273 Arc addArc(const Node& from, const Node& to) { 274 274 Arc arc = Parent::addArc(from, to); … … 294 294 Parent::firstOut(arc, node); 295 295 while (arc != INVALID ) { 296 297 298 } 296 erase(arc); 297 Parent::firstOut(arc, node); 298 } 299 299 300 300 Parent::firstIn(arc, node); 301 301 while (arc != INVALID ) { 302 303 302 erase(arc); 303 Parent::firstIn(arc, node); 304 304 } 305 305 … … 307 307 Parent::erase(node); 308 308 } 309 309 310 310 void erase(const Arc& arc) { 311 311 notifier(Arc()).erase(arc); … … 316 316 node_notifier.setContainer(*this); 317 317 arc_notifier.setContainer(*this); 318 } 319 318 } 319 320 320 321 321 ~DigraphExtender() { … … 328 328 /// 329 329 /// \brief Extender for the Graphs 330 template <typename Base> 330 template <typename Base> 331 331 class GraphExtender : public Base { 332 332 public: 333 333 334 334 typedef Base Parent; 335 335 typedef GraphExtender Graph; … … 341 341 typedef typename Parent::Edge Edge; 342 342 343 // Graph extension 343 // Graph extension 344 344 345 345 int maxId(Node) const { … … 369 369 Node oppositeNode(const Node &n, const Edge &e) const { 370 370 if( n == Parent::u(e)) 371 371 return Parent::v(e); 372 372 else if( n == Parent::v(e)) 373 373 return Parent::u(e); 374 374 else 375 375 return INVALID; 376 376 } 377 377 … … 403 403 return node_notifier; 404 404 } 405 405 406 406 ArcNotifier& notifier(Arc) const { 407 407 return arc_notifier; … … 414 414 415 415 416 class NodeIt : public Node { 416 class NodeIt : public Node { 417 417 const Graph* _graph; 418 418 public: … … 423 423 424 424 explicit NodeIt(const Graph& graph) : _graph(&graph) { 425 426 } 427 428 NodeIt(const Graph& graph, const Node& node) 429 430 431 NodeIt& operator++() { 432 433 return *this; 434 } 435 436 }; 437 438 439 class ArcIt : public Arc { 425 _graph>first(static_cast<Node&>(*this)); 426 } 427 428 NodeIt(const Graph& graph, const Node& node) 429 : Node(node), _graph(&graph) {} 430 431 NodeIt& operator++() { 432 _graph>next(*this); 433 return *this; 434 } 435 436 }; 437 438 439 class ArcIt : public Arc { 440 440 const Graph* _graph; 441 441 public: … … 446 446 447 447 explicit ArcIt(const Graph& graph) : _graph(&graph) { 448 449 } 450 451 ArcIt(const Graph& graph, const Arc& arc) : 452 453 454 ArcIt& operator++() { 455 456 return *this; 457 } 458 459 }; 460 461 462 class OutArcIt : public Arc { 448 _graph>first(static_cast<Arc&>(*this)); 449 } 450 451 ArcIt(const Graph& graph, const Arc& arc) : 452 Arc(arc), _graph(&graph) { } 453 454 ArcIt& operator++() { 455 _graph>next(*this); 456 return *this; 457 } 458 459 }; 460 461 462 class OutArcIt : public Arc { 463 463 const Graph* _graph; 464 464 public: … … 468 468 OutArcIt(Invalid i) : Arc(i) { } 469 469 470 OutArcIt(const Graph& graph, const Node& node) 471 472 473 } 474 475 OutArcIt(const Graph& graph, const Arc& arc) 476 477 478 OutArcIt& operator++() { 479 480 return *this; 481 } 482 483 }; 484 485 486 class InArcIt : public Arc { 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 478 OutArcIt& operator++() { 479 _graph>nextOut(*this); 480 return *this; 481 } 482 483 }; 484 485 486 class InArcIt : public Arc { 487 487 const Graph* _graph; 488 488 public: … … 492 492 InArcIt(Invalid i) : Arc(i) { } 493 493 494 InArcIt(const Graph& graph, const Node& node) 495 496 497 } 498 499 InArcIt(const Graph& graph, const Arc& arc) : 500 501 502 InArcIt& operator++() { 503 504 return *this; 505 } 506 507 }; 508 509 510 class EdgeIt : public Parent::Edge { 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 502 InArcIt& operator++() { 503 _graph>nextIn(*this); 504 return *this; 505 } 506 507 }; 508 509 510 class EdgeIt : public Parent::Edge { 511 511 const Graph* _graph; 512 512 public: … … 517 517 518 518 explicit EdgeIt(const Graph& graph) : _graph(&graph) { 519 520 } 521 522 EdgeIt(const Graph& graph, const Edge& edge) : 523 524 525 EdgeIt& operator++() { 526 527 return *this; 519 _graph>first(static_cast<Edge&>(*this)); 520 } 521 522 EdgeIt(const Graph& graph, const Edge& edge) : 523 Edge(edge), _graph(&graph) { } 524 525 EdgeIt& operator++() { 526 _graph>next(*this); 527 return *this; 528 528 } 529 529 … … 541 541 542 542 IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) { 543 543 _graph>firstInc(*this, _direction, node); 544 544 } 545 545 546 546 IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node) 547 548 547 : _graph(&graph), Edge(edge) { 548 _direction = (_graph>source(edge) == node); 549 549 } 550 550 551 551 IncEdgeIt& operator++() { 552 553 return *this; 552 _graph>nextInc(*this, _direction); 553 return *this; 554 554 } 555 555 }; … … 599 599 600 600 template <typename _Value> 601 class NodeMap 601 class NodeMap 602 602 : public MapExtender<DefaultMap<Graph, Node, _Value> > { 603 603 public: … … 605 605 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; 606 606 607 NodeMap(const Graph& graph) 608 609 NodeMap(const Graph& graph, const _Value& value) 610 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) { 613 613 return operator=<NodeMap>(cmap); 614 614 } 615 615 … … 617 617 NodeMap& operator=(const CMap& cmap) { 618 618 Parent::operator=(cmap); 619 619 return *this; 620 620 } 621 621 … … 623 623 624 624 template <typename _Value> 625 class ArcMap 625 class ArcMap 626 626 : public MapExtender<DefaultMap<Graph, Arc, _Value> > { 627 627 public: … … 629 629 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent; 630 630 631 ArcMap(const Graph& graph) 632 633 ArcMap(const Graph& graph, const _Value& value) 634 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) { 637 637 return operator=<ArcMap>(cmap); 638 638 } 639 639 … … 641 641 ArcMap& operator=(const CMap& cmap) { 642 642 Parent::operator=(cmap); 643 643 return *this; 644 644 } 645 645 }; … … 647 647 648 648 template <typename _Value> 649 class EdgeMap 649 class EdgeMap 650 650 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 651 651 public: … … 653 653 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 654 654 655 EdgeMap(const Graph& graph) 656 657 658 EdgeMap(const Graph& graph, const _Value& value) 659 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) { 662 662 return operator=<EdgeMap>(cmap); 663 663 } 664 664 … … 666 666 EdgeMap& operator=(const CMap& cmap) { 667 667 Parent::operator=(cmap); 668 668 return *this; 669 669 } 670 670 … … 684 684 std::vector<Arc> ev; 685 685 ev.push_back(Parent::direct(edge, true)); 686 ev.push_back(Parent::direct(edge, false)); 686 ev.push_back(Parent::direct(edge, false)); 687 687 notifier(Arc()).add(ev); 688 688 return edge; 689 689 } 690 690 691 691 void clear() { 692 692 notifier(Arc()).clear(); … … 697 697 698 698 template <typename Graph, typename NodeRefMap, typename EdgeRefMap> 699 void build(const Graph& graph, NodeRefMap& nodeRef, 699 void build(const Graph& graph, NodeRefMap& nodeRef, 700 700 EdgeRefMap& edgeRef) { 701 701 Parent::build(graph, nodeRef, edgeRef); … … 709 709 Parent::firstOut(arc, node); 710 710 while (arc != INVALID ) { 711 712 713 } 711 erase(arc); 712 Parent::firstOut(arc, node); 713 } 714 714 715 715 Parent::firstIn(arc, node); 716 716 while (arc != INVALID ) { 717 718 717 erase(arc); 718 Parent::firstIn(arc, node); 719 719 } 720 720 … … 726 726 std::vector<Arc> av; 727 727 av.push_back(Parent::direct(edge, true)); 728 av.push_back(Parent::direct(edge, false)); 728 av.push_back(Parent::direct(edge, false)); 729 729 notifier(Arc()).erase(av); 730 730 notifier(Edge()).erase(edge); … … 733 733 734 734 GraphExtender() { 735 node_notifier.setContainer(*this); 735 node_notifier.setContainer(*this); 736 736 arc_notifier.setContainer(*this); 737 737 edge_notifier.setContainer(*this); 738 } 738 } 739 739 740 740 ~GraphExtender() { 741 741 edge_notifier.clear(); 742 742 arc_notifier.clear(); 743 node_notifier.clear(); 744 } 743 node_notifier.clear(); 744 } 745 745 746 746 };
Note: See TracChangeset
for help on using the changeset viewer.