1 /* -*- C++ -*- 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 4 * 5 * Copyright (C) 2003-2008 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). 8 * 9 * Permission to use, modify and distribute this software is granted 10 * provided that this copyright notice appears in all copies. For 11 * precise terms see the accompanying LICENSE file. 12 * 13 * This software is provided "AS IS" with no warranty of any kind, 14 * express or implied, and with no claim as to its suitability for any 15 * purpose. 16 * 17 */ 18 19 #ifndef LEMON_BITS_GRAPH_EXTENDER_H 20 #define LEMON_BITS_GRAPH_EXTENDER_H 21 22 #include <lemon/bits/invalid.h> 23 #include <lemon/bits/utility.h> 24 #include <lemon/error.h> 25 26 #include <lemon/bits/map_extender.h> 27 #include <lemon/bits/default_map.h> 28 29 #include <lemon/concept_check.h> 30 #include <lemon/concepts/maps.h> 31 32 ///\ingroup graphbits 33 ///\file 34 ///\brief Extenders for the graph types 35 namespace lemon { 36 37 /// \ingroup graphbits 38 /// 39 /// \brief Extender for the Graphs 40 template <typename Base> 41 class GraphExtender : public Base { 42 public: 43 44 typedef Base Parent; 45 typedef GraphExtender Graph; 46 47 // Base extensions 48 49 typedef typename Parent::Node Node; 50 typedef typename Parent::Edge Edge; 51 maxId(Node)52 int maxId(Node) const { 53 return Parent::maxNodeId(); 54 } 55 maxId(Edge)56 int maxId(Edge) const { 57 return Parent::maxEdgeId(); 58 } 59 fromId(int id,Node)60 Node fromId(int id, Node) const { 61 return Parent::nodeFromId(id); 62 } 63 fromId(int id,Edge)64 Edge fromId(int id, Edge) const { 65 return Parent::edgeFromId(id); 66 } 67 oppositeNode(const Node & n,const Edge & e)68 Node oppositeNode(const Node &n, const Edge &e) const { 69 if (n == Parent::source(e)) 70 return Parent::target(e); 71 else if(n==Parent::target(e)) 72 return Parent::source(e); 73 else 74 return INVALID; 75 } 76 77 // Alterable extension 78 79 typedef AlterationNotifier<GraphExtender, Node> NodeNotifier; 80 typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier; 81 82 83 protected: 84 85 mutable NodeNotifier node_notifier; 86 mutable EdgeNotifier edge_notifier; 87 88 public: 89 notifier(Node)90 NodeNotifier& notifier(Node) const { 91 return node_notifier; 92 } 93 notifier(Edge)94 EdgeNotifier& notifier(Edge) const { 95 return edge_notifier; 96 } 97 98 class NodeIt : public Node { 99 const Graph* graph; 100 public: 101 NodeIt()102 NodeIt() {} 103 NodeIt(Invalid i)104 NodeIt(Invalid i) : Node(i) { } 105 NodeIt(const Graph & _graph)106 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 107 _graph.first(static_cast<Node&>(*this)); 108 } 109 NodeIt(const Graph & _graph,const Node & node)110 NodeIt(const Graph& _graph, const Node& node) 111 : Node(node), graph(&_graph) {} 112 113 NodeIt& operator++() { 114 graph->next(*this); 115 return *this; 116 } 117 118 }; 119 120 121 class EdgeIt : public Edge { 122 const Graph* graph; 123 public: 124 EdgeIt()125 EdgeIt() { } 126 EdgeIt(Invalid i)127 EdgeIt(Invalid i) : Edge(i) { } 128 EdgeIt(const Graph & _graph)129 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 130 _graph.first(static_cast<Edge&>(*this)); 131 } 132 EdgeIt(const Graph & _graph,const Edge & e)133 EdgeIt(const Graph& _graph, const Edge& e) : 134 Edge(e), graph(&_graph) { } 135 136 EdgeIt& operator++() { 137 graph->next(*this); 138 return *this; 139 } 140 141 }; 142 143 144 class OutEdgeIt : public Edge { 145 const Graph* graph; 146 public: 147 OutEdgeIt()148 OutEdgeIt() { } 149 OutEdgeIt(Invalid i)150 OutEdgeIt(Invalid i) : Edge(i) { } 151 OutEdgeIt(const Graph & _graph,const Node & node)152 OutEdgeIt(const Graph& _graph, const Node& node) 153 : graph(&_graph) { 154 _graph.firstOut(*this, node); 155 } 156 OutEdgeIt(const Graph & _graph,const Edge & edge)157 OutEdgeIt(const Graph& _graph, const Edge& edge) 158 : Edge(edge), graph(&_graph) {} 159 160 OutEdgeIt& operator++() { 161 graph->nextOut(*this); 162 return *this; 163 } 164 165 }; 166 167 168 class InEdgeIt : public Edge { 169 const Graph* graph; 170 public: 171 InEdgeIt()172 InEdgeIt() { } 173 InEdgeIt(Invalid i)174 InEdgeIt(Invalid i) : Edge(i) { } 175 InEdgeIt(const Graph & _graph,const Node & node)176 InEdgeIt(const Graph& _graph, const Node& node) 177 : graph(&_graph) { 178 _graph.firstIn(*this, node); 179 } 180 InEdgeIt(const Graph & _graph,const Edge & edge)181 InEdgeIt(const Graph& _graph, const Edge& edge) : 182 Edge(edge), graph(&_graph) {} 183 184 InEdgeIt& operator++() { 185 graph->nextIn(*this); 186 return *this; 187 } 188 189 }; 190 191 /// \brief Base node of the iterator 192 /// 193 /// Returns the base node (i.e. the source in this case) of the iterator baseNode(const OutEdgeIt & e)194 Node baseNode(const OutEdgeIt &e) const { 195 return Parent::source(e); 196 } 197 /// \brief Running node of the iterator 198 /// 199 /// Returns the running node (i.e. the target in this case) of the 200 /// iterator runningNode(const OutEdgeIt & e)201 Node runningNode(const OutEdgeIt &e) const { 202 return Parent::target(e); 203 } 204 205 /// \brief Base node of the iterator 206 /// 207 /// Returns the base node (i.e. the target in this case) of the iterator baseNode(const InEdgeIt & e)208 Node baseNode(const InEdgeIt &e) const { 209 return Parent::target(e); 210 } 211 /// \brief Running node of the iterator 212 /// 213 /// Returns the running node (i.e. the source in this case) of the 214 /// iterator runningNode(const InEdgeIt & e)215 Node runningNode(const InEdgeIt &e) const { 216 return Parent::source(e); 217 } 218 219 220 template <typename _Value> 221 class NodeMap 222 : public MapExtender<DefaultMap<Graph, Node, _Value> > { 223 public: 224 typedef GraphExtender Graph; 225 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; 226 NodeMap(const Graph & graph)227 explicit NodeMap(const Graph& graph) 228 : Parent(graph) {} NodeMap(const Graph & graph,const _Value & value)229 NodeMap(const Graph& graph, const _Value& value) 230 : Parent(graph, value) {} 231 232 NodeMap& operator=(const NodeMap& cmap) { 233 return operator=<NodeMap>(cmap); 234 } 235 236 template <typename CMap> 237 NodeMap& operator=(const CMap& cmap) { 238 Parent::operator=(cmap); 239 return *this; 240 } 241 242 }; 243 244 template <typename _Value> 245 class EdgeMap 246 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 247 public: 248 typedef GraphExtender Graph; 249 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 250 EdgeMap(const Graph & graph)251 explicit EdgeMap(const Graph& graph) 252 : Parent(graph) {} EdgeMap(const Graph & graph,const _Value & value)253 EdgeMap(const Graph& graph, const _Value& value) 254 : Parent(graph, value) {} 255 256 EdgeMap& operator=(const EdgeMap& cmap) { 257 return operator=<EdgeMap>(cmap); 258 } 259 260 template <typename CMap> 261 EdgeMap& operator=(const CMap& cmap) { 262 Parent::operator=(cmap); 263 return *this; 264 } 265 }; 266 267 addNode()268 Node addNode() { 269 Node node = Parent::addNode(); 270 notifier(Node()).add(node); 271 return node; 272 } 273 addEdge(const Node & from,const Node & to)274 Edge addEdge(const Node& from, const Node& to) { 275 Edge edge = Parent::addEdge(from, to); 276 notifier(Edge()).add(edge); 277 return edge; 278 } 279 clear()280 void clear() { 281 notifier(Edge()).clear(); 282 notifier(Node()).clear(); 283 Parent::clear(); 284 } 285 286 template <typename Graph, typename NodeRefMap, typename EdgeRefMap> build(const Graph & graph,NodeRefMap & nodeRef,EdgeRefMap & edgeRef)287 void build(const Graph& graph, NodeRefMap& nodeRef, EdgeRefMap& edgeRef) { 288 Parent::build(graph, nodeRef, edgeRef); 289 notifier(Node()).build(); 290 notifier(Edge()).build(); 291 } 292 erase(const Node & node)293 void erase(const Node& node) { 294 Edge edge; 295 Parent::firstOut(edge, node); 296 while (edge != INVALID ) { 297 erase(edge); 298 Parent::firstOut(edge, node); 299 } 300 301 Parent::firstIn(edge, node); 302 while (edge != INVALID ) { 303 erase(edge); 304 Parent::firstIn(edge, node); 305 } 306 307 notifier(Node()).erase(node); 308 Parent::erase(node); 309 } 310 erase(const Edge & edge)311 void erase(const Edge& edge) { 312 notifier(Edge()).erase(edge); 313 Parent::erase(edge); 314 } 315 GraphExtender()316 GraphExtender() { 317 node_notifier.setContainer(*this); 318 edge_notifier.setContainer(*this); 319 } 320 321 ~GraphExtender()322 ~GraphExtender() { 323 edge_notifier.clear(); 324 node_notifier.clear(); 325 } 326 }; 327 328 /// \ingroup graphbits 329 /// 330 /// \brief Extender for the UGraphs 331 template <typename Base> 332 class UGraphExtender : public Base { 333 public: 334 335 typedef Base Parent; 336 typedef UGraphExtender Graph; 337 338 typedef True UndirectedTag; 339 340 typedef typename Parent::Node Node; 341 typedef typename Parent::Edge Edge; 342 typedef typename Parent::UEdge UEdge; 343 344 // UGraph extension 345 maxId(Node)346 int maxId(Node) const { 347 return Parent::maxNodeId(); 348 } 349 maxId(Edge)350 int maxId(Edge) const { 351 return Parent::maxEdgeId(); 352 } 353 maxId(UEdge)354 int maxId(UEdge) const { 355 return Parent::maxUEdgeId(); 356 } 357 fromId(int id,Node)358 Node fromId(int id, Node) const { 359 return Parent::nodeFromId(id); 360 } 361 fromId(int id,Edge)362 Edge fromId(int id, Edge) const { 363 return Parent::edgeFromId(id); 364 } 365 fromId(int id,UEdge)366 UEdge fromId(int id, UEdge) const { 367 return Parent::uEdgeFromId(id); 368 } 369 oppositeNode(const Node & n,const UEdge & e)370 Node oppositeNode(const Node &n, const UEdge &e) const { 371 if( n == Parent::source(e)) 372 return Parent::target(e); 373 else if( n == Parent::target(e)) 374 return Parent::source(e); 375 else 376 return INVALID; 377 } 378 oppositeEdge(const Edge & e)379 Edge oppositeEdge(const Edge &e) const { 380 return Parent::direct(e, !Parent::direction(e)); 381 } 382 383 using Parent::direct; direct(const UEdge & ue,const Node & s)384 Edge direct(const UEdge &ue, const Node &s) const { 385 return Parent::direct(ue, Parent::source(ue) == s); 386 } 387 388 // Alterable extension 389 390 typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier; 391 typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier; 392 typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier; 393 394 395 protected: 396 397 mutable NodeNotifier node_notifier; 398 mutable EdgeNotifier edge_notifier; 399 mutable UEdgeNotifier uedge_notifier; 400 401 public: 402 notifier(Node)403 NodeNotifier& notifier(Node) const { 404 return node_notifier; 405 } 406 notifier(Edge)407 EdgeNotifier& notifier(Edge) const { 408 return edge_notifier; 409 } 410 notifier(UEdge)411 UEdgeNotifier& notifier(UEdge) const { 412 return uedge_notifier; 413 } 414 415 416 417 class NodeIt : public Node { 418 const Graph* graph; 419 public: 420 NodeIt()421 NodeIt() {} 422 NodeIt(Invalid i)423 NodeIt(Invalid i) : Node(i) { } 424 NodeIt(const Graph & _graph)425 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 426 _graph.first(static_cast<Node&>(*this)); 427 } 428 NodeIt(const Graph & _graph,const Node & node)429 NodeIt(const Graph& _graph, const Node& node) 430 : Node(node), graph(&_graph) {} 431 432 NodeIt& operator++() { 433 graph->next(*this); 434 return *this; 435 } 436 437 }; 438 439 440 class EdgeIt : public Edge { 441 const Graph* graph; 442 public: 443 EdgeIt()444 EdgeIt() { } 445 EdgeIt(Invalid i)446 EdgeIt(Invalid i) : Edge(i) { } 447 EdgeIt(const Graph & _graph)448 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 449 _graph.first(static_cast<Edge&>(*this)); 450 } 451 EdgeIt(const Graph & _graph,const Edge & e)452 EdgeIt(const Graph& _graph, const Edge& e) : 453 Edge(e), graph(&_graph) { } 454 455 EdgeIt& operator++() { 456 graph->next(*this); 457 return *this; 458 } 459 460 }; 461 462 463 class OutEdgeIt : public Edge { 464 const Graph* graph; 465 public: 466 OutEdgeIt()467 OutEdgeIt() { } 468 OutEdgeIt(Invalid i)469 OutEdgeIt(Invalid i) : Edge(i) { } 470 OutEdgeIt(const Graph & _graph,const Node & node)471 OutEdgeIt(const Graph& _graph, const Node& node) 472 : graph(&_graph) { 473 _graph.firstOut(*this, node); 474 } 475 OutEdgeIt(const Graph & _graph,const Edge & edge)476 OutEdgeIt(const Graph& _graph, const Edge& edge) 477 : Edge(edge), graph(&_graph) {} 478 479 OutEdgeIt& operator++() { 480 graph->nextOut(*this); 481 return *this; 482 } 483 484 }; 485 486 487 class InEdgeIt : public Edge { 488 const Graph* graph; 489 public: 490 InEdgeIt()491 InEdgeIt() { } 492 InEdgeIt(Invalid i)493 InEdgeIt(Invalid i) : Edge(i) { } 494 InEdgeIt(const Graph & _graph,const Node & node)495 InEdgeIt(const Graph& _graph, const Node& node) 496 : graph(&_graph) { 497 _graph.firstIn(*this, node); 498 } 499 InEdgeIt(const Graph & _graph,const Edge & edge)500 InEdgeIt(const Graph& _graph, const Edge& edge) : 501 Edge(edge), graph(&_graph) {} 502 503 InEdgeIt& operator++() { 504 graph->nextIn(*this); 505 return *this; 506 } 507 508 }; 509 510 511 class UEdgeIt : public Parent::UEdge { 512 const Graph* graph; 513 public: 514 UEdgeIt()515 UEdgeIt() { } 516 UEdgeIt(Invalid i)517 UEdgeIt(Invalid i) : UEdge(i) { } 518 UEdgeIt(const Graph & _graph)519 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { 520 _graph.first(static_cast<UEdge&>(*this)); 521 } 522 UEdgeIt(const Graph & _graph,const UEdge & e)523 UEdgeIt(const Graph& _graph, const UEdge& e) : 524 UEdge(e), graph(&_graph) { } 525 526 UEdgeIt& operator++() { 527 graph->next(*this); 528 return *this; 529 } 530 531 }; 532 533 class IncEdgeIt : public Parent::UEdge { 534 friend class UGraphExtender; 535 const Graph* graph; 536 bool direction; 537 public: 538 IncEdgeIt()539 IncEdgeIt() { } 540 IncEdgeIt(Invalid i)541 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { } 542 IncEdgeIt(const Graph & _graph,const Node & n)543 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 544 _graph.firstInc(*this, direction, n); 545 } 546 IncEdgeIt(const Graph & _graph,const UEdge & ue,const Node & n)547 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) 548 : graph(&_graph), UEdge(ue) { 549 direction = (_graph.source(ue) == n); 550 } 551 552 IncEdgeIt& operator++() { 553 graph->nextInc(*this, direction); 554 return *this; 555 } 556 }; 557 558 /// \brief Base node of the iterator 559 /// 560 /// Returns the base node (ie. the source in this case) of the iterator baseNode(const OutEdgeIt & e)561 Node baseNode(const OutEdgeIt &e) const { 562 return Parent::source(static_cast<const Edge&>(e)); 563 } 564 /// \brief Running node of the iterator 565 /// 566 /// Returns the running node (ie. the target in this case) of the 567 /// iterator runningNode(const OutEdgeIt & e)568 Node runningNode(const OutEdgeIt &e) const { 569 return Parent::target(static_cast<const Edge&>(e)); 570 } 571 572 /// \brief Base node of the iterator 573 /// 574 /// Returns the base node (ie. the target in this case) of the iterator baseNode(const InEdgeIt & e)575 Node baseNode(const InEdgeIt &e) const { 576 return Parent::target(static_cast<const Edge&>(e)); 577 } 578 /// \brief Running node of the iterator 579 /// 580 /// Returns the running node (ie. the source in this case) of the 581 /// iterator runningNode(const InEdgeIt & e)582 Node runningNode(const InEdgeIt &e) const { 583 return Parent::source(static_cast<const Edge&>(e)); 584 } 585 586 /// Base node of the iterator 587 /// 588 /// Returns the base node of the iterator baseNode(const IncEdgeIt & e)589 Node baseNode(const IncEdgeIt &e) const { 590 return e.direction ? source(e) : target(e); 591 } 592 /// Running node of the iterator 593 /// 594 /// Returns the running node of the iterator runningNode(const IncEdgeIt & e)595 Node runningNode(const IncEdgeIt &e) const { 596 return e.direction ? target(e) : source(e); 597 } 598 599 // Mappable extension 600 601 template <typename _Value> 602 class NodeMap 603 : public MapExtender<DefaultMap<Graph, Node, _Value> > { 604 public: 605 typedef UGraphExtender Graph; 606 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; 607 NodeMap(const Graph & graph)608 NodeMap(const Graph& graph) 609 : Parent(graph) {} NodeMap(const Graph & graph,const _Value & value)610 NodeMap(const Graph& graph, const _Value& value) 611 : Parent(graph, value) {} 612 613 NodeMap& operator=(const NodeMap& cmap) { 614 return operator=<NodeMap>(cmap); 615 } 616 617 template <typename CMap> 618 NodeMap& operator=(const CMap& cmap) { 619 Parent::operator=(cmap); 620 return *this; 621 } 622 623 }; 624 625 template <typename _Value> 626 class EdgeMap 627 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 628 public: 629 typedef UGraphExtender Graph; 630 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 631 EdgeMap(const Graph & graph)632 EdgeMap(const Graph& graph) 633 : Parent(graph) {} EdgeMap(const Graph & graph,const _Value & value)634 EdgeMap(const Graph& graph, const _Value& value) 635 : Parent(graph, value) {} 636 637 EdgeMap& operator=(const EdgeMap& cmap) { 638 return operator=<EdgeMap>(cmap); 639 } 640 641 template <typename CMap> 642 EdgeMap& operator=(const CMap& cmap) { 643 Parent::operator=(cmap); 644 return *this; 645 } 646 }; 647 648 649 template <typename _Value> 650 class UEdgeMap 651 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > { 652 public: 653 typedef UGraphExtender Graph; 654 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; 655 UEdgeMap(const Graph & graph)656 UEdgeMap(const Graph& graph) 657 : Parent(graph) {} 658 UEdgeMap(const Graph & graph,const _Value & value)659 UEdgeMap(const Graph& graph, const _Value& value) 660 : Parent(graph, value) {} 661 662 UEdgeMap& operator=(const UEdgeMap& cmap) { 663 return operator=<UEdgeMap>(cmap); 664 } 665 666 template <typename CMap> 667 UEdgeMap& operator=(const CMap& cmap) { 668 Parent::operator=(cmap); 669 return *this; 670 } 671 672 }; 673 674 // Alteration extension 675 addNode()676 Node addNode() { 677 Node node = Parent::addNode(); 678 notifier(Node()).add(node); 679 return node; 680 } 681 addEdge(const Node & from,const Node & to)682 UEdge addEdge(const Node& from, const Node& to) { 683 UEdge uedge = Parent::addEdge(from, to); 684 notifier(UEdge()).add(uedge); 685 std::vector<Edge> ev; 686 ev.push_back(Parent::direct(uedge, true)); 687 ev.push_back(Parent::direct(uedge, false)); 688 notifier(Edge()).add(ev); 689 return uedge; 690 } 691 clear()692 void clear() { 693 notifier(Edge()).clear(); 694 notifier(UEdge()).clear(); 695 notifier(Node()).clear(); 696 Parent::clear(); 697 } 698 699 template <typename Graph, typename NodeRefMap, typename UEdgeRefMap> build(const Graph & graph,NodeRefMap & nodeRef,UEdgeRefMap & uEdgeRef)700 void build(const Graph& graph, NodeRefMap& nodeRef, 701 UEdgeRefMap& uEdgeRef) { 702 Parent::build(graph, nodeRef, uEdgeRef); 703 notifier(Node()).build(); 704 notifier(UEdge()).build(); 705 notifier(Edge()).build(); 706 } 707 erase(const Node & node)708 void erase(const Node& node) { 709 Edge edge; 710 Parent::firstOut(edge, node); 711 while (edge != INVALID ) { 712 erase(edge); 713 Parent::firstOut(edge, node); 714 } 715 716 Parent::firstIn(edge, node); 717 while (edge != INVALID ) { 718 erase(edge); 719 Parent::firstIn(edge, node); 720 } 721 722 notifier(Node()).erase(node); 723 Parent::erase(node); 724 } 725 erase(const UEdge & uedge)726 void erase(const UEdge& uedge) { 727 std::vector<Edge> ev; 728 ev.push_back(Parent::direct(uedge, true)); 729 ev.push_back(Parent::direct(uedge, false)); 730 notifier(Edge()).erase(ev); 731 notifier(UEdge()).erase(uedge); 732 Parent::erase(uedge); 733 } 734 UGraphExtender()735 UGraphExtender() { 736 node_notifier.setContainer(*this); 737 edge_notifier.setContainer(*this); 738 uedge_notifier.setContainer(*this); 739 } 740 ~UGraphExtender()741 ~UGraphExtender() { 742 uedge_notifier.clear(); 743 edge_notifier.clear(); 744 node_notifier.clear(); 745 } 746 747 }; 748 749 /// \ingroup graphbits 750 /// 751 /// \brief Extender for the BpUGraphs 752 template <typename Base> 753 class BpUGraphExtender : public Base { 754 public: 755 756 typedef Base Parent; 757 typedef BpUGraphExtender Graph; 758 759 typedef True UndirectedTag; 760 761 typedef typename Parent::Node Node; 762 typedef typename Parent::ANode ANode; 763 typedef typename Parent::BNode BNode; 764 typedef typename Parent::Edge Edge; 765 typedef typename Parent::UEdge UEdge; 766 767 oppositeNode(const Node & node,const UEdge & edge)768 Node oppositeNode(const Node& node, const UEdge& edge) const { 769 return Parent::aNode(edge) == node ? 770 Parent::bNode(edge) : Parent::aNode(edge); 771 } 772 773 using Parent::direct; direct(const UEdge & edge,const Node & node)774 Edge direct(const UEdge& edge, const Node& node) const { 775 return Parent::direct(edge, node == Parent::source(edge)); 776 } 777 oppositeEdge(const Edge & edge)778 Edge oppositeEdge(const Edge& edge) const { 779 return direct(edge, !Parent::direction(edge)); 780 } 781 maxId(Node)782 int maxId(Node) const { 783 return Parent::maxNodeId(); 784 } maxId(BNode)785 int maxId(BNode) const { 786 return Parent::maxBNodeId(); 787 } maxId(ANode)788 int maxId(ANode) const { 789 return Parent::maxANodeId(); 790 } maxId(Edge)791 int maxId(Edge) const { 792 return Parent::maxEdgeId(); 793 } maxId(UEdge)794 int maxId(UEdge) const { 795 return Parent::maxUEdgeId(); 796 } 797 798 fromId(int id,Node)799 Node fromId(int id, Node) const { 800 return Parent::nodeFromId(id); 801 } fromId(int id,ANode)802 ANode fromId(int id, ANode) const { 803 return Parent::nodeFromANodeId(id); 804 } fromId(int id,BNode)805 BNode fromId(int id, BNode) const { 806 return Parent::nodeFromBNodeId(id); 807 } fromId(int id,Edge)808 Edge fromId(int id, Edge) const { 809 return Parent::edgeFromId(id); 810 } fromId(int id,UEdge)811 UEdge fromId(int id, UEdge) const { 812 return Parent::uEdgeFromId(id); 813 } 814 815 typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier; 816 typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier; 817 typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier; 818 typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier; 819 typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier; 820 821 protected: 822 823 mutable ANodeNotifier anode_notifier; 824 mutable BNodeNotifier bnode_notifier; 825 mutable NodeNotifier node_notifier; 826 mutable EdgeNotifier edge_notifier; 827 mutable UEdgeNotifier uedge_notifier; 828 829 public: 830 notifier(Node)831 NodeNotifier& notifier(Node) const { 832 return node_notifier; 833 } 834 notifier(ANode)835 ANodeNotifier& notifier(ANode) const { 836 return anode_notifier; 837 } 838 notifier(BNode)839 BNodeNotifier& notifier(BNode) const { 840 return bnode_notifier; 841 } 842 notifier(Edge)843 EdgeNotifier& notifier(Edge) const { 844 return edge_notifier; 845 } 846 notifier(UEdge)847 UEdgeNotifier& notifier(UEdge) const { 848 return uedge_notifier; 849 } 850 851 class NodeIt : public Node { 852 const Graph* graph; 853 public: 854 NodeIt()855 NodeIt() { } 856 NodeIt(Invalid i)857 NodeIt(Invalid i) : Node(INVALID) { } 858 NodeIt(const Graph & _graph)859 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 860 graph->first(static_cast<Node&>(*this)); 861 } 862 NodeIt(const Graph & _graph,const Node & node)863 NodeIt(const Graph& _graph, const Node& node) 864 : Node(node), graph(&_graph) { } 865 866 NodeIt& operator++() { 867 graph->next(*this); 868 return *this; 869 } 870 871 }; 872 873 class ANodeIt : public Node { 874 friend class BpUGraphExtender; 875 const Graph* graph; 876 public: 877 ANodeIt()878 ANodeIt() { } 879 ANodeIt(Invalid i)880 ANodeIt(Invalid i) : Node(INVALID) { } 881 ANodeIt(const Graph & _graph)882 explicit ANodeIt(const Graph& _graph) : graph(&_graph) { 883 graph->firstANode(static_cast<Node&>(*this)); 884 } 885 ANodeIt(const Graph & _graph,const Node & node)886 ANodeIt(const Graph& _graph, const Node& node) 887 : Node(node), graph(&_graph) {} 888 889 ANodeIt& operator++() { 890 graph->nextANode(*this); 891 return *this; 892 } 893 }; 894 895 class BNodeIt : public Node { 896 friend class BpUGraphExtender; 897 const Graph* graph; 898 public: 899 BNodeIt()900 BNodeIt() { } 901 BNodeIt(Invalid i)902 BNodeIt(Invalid i) : Node(INVALID) { } 903 BNodeIt(const Graph & _graph)904 explicit BNodeIt(const Graph& _graph) : graph(&_graph) { 905 graph->firstBNode(static_cast<Node&>(*this)); 906 } 907 BNodeIt(const Graph & _graph,const Node & node)908 BNodeIt(const Graph& _graph, const Node& node) 909 : Node(node), graph(&_graph) {} 910 911 BNodeIt& operator++() { 912 graph->nextBNode(*this); 913 return *this; 914 } 915 }; 916 917 class EdgeIt : public Edge { 918 friend class BpUGraphExtender; 919 const Graph* graph; 920 public: 921 EdgeIt()922 EdgeIt() { } 923 EdgeIt(Invalid i)924 EdgeIt(Invalid i) : Edge(INVALID) { } 925 EdgeIt(const Graph & _graph)926 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 927 graph->first(static_cast<Edge&>(*this)); 928 } 929 EdgeIt(const Graph & _graph,const Edge & edge)930 EdgeIt(const Graph& _graph, const Edge& edge) 931 : Edge(edge), graph(&_graph) { } 932 933 EdgeIt& operator++() { 934 graph->next(*this); 935 return *this; 936 } 937 938 }; 939 940 class UEdgeIt : public UEdge { 941 friend class BpUGraphExtender; 942 const Graph* graph; 943 public: 944 UEdgeIt()945 UEdgeIt() { } 946 UEdgeIt(Invalid i)947 UEdgeIt(Invalid i) : UEdge(INVALID) { } 948 UEdgeIt(const Graph & _graph)949 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { 950 graph->first(static_cast<UEdge&>(*this)); 951 } 952 UEdgeIt(const Graph & _graph,const UEdge & edge)953 UEdgeIt(const Graph& _graph, const UEdge& edge) 954 : UEdge(edge), graph(&_graph) { } 955 956 UEdgeIt& operator++() { 957 graph->next(*this); 958 return *this; 959 } 960 }; 961 962 class OutEdgeIt : public Edge { 963 friend class BpUGraphExtender; 964 const Graph* graph; 965 public: 966 OutEdgeIt()967 OutEdgeIt() { } 968 OutEdgeIt(Invalid i)969 OutEdgeIt(Invalid i) : Edge(i) { } 970 OutEdgeIt(const Graph & _graph,const Node & node)971 OutEdgeIt(const Graph& _graph, const Node& node) 972 : graph(&_graph) { 973 graph->firstOut(*this, node); 974 } 975 OutEdgeIt(const Graph & _graph,const Edge & edge)976 OutEdgeIt(const Graph& _graph, const Edge& edge) 977 : Edge(edge), graph(&_graph) {} 978 979 OutEdgeIt& operator++() { 980 graph->nextOut(*this); 981 return *this; 982 } 983 984 }; 985 986 987 class InEdgeIt : public Edge { 988 friend class BpUGraphExtender; 989 const Graph* graph; 990 public: 991 InEdgeIt()992 InEdgeIt() { } 993 InEdgeIt(Invalid i)994 InEdgeIt(Invalid i) : Edge(i) { } 995 InEdgeIt(const Graph & _graph,const Node & node)996 InEdgeIt(const Graph& _graph, const Node& node) 997 : graph(&_graph) { 998 graph->firstIn(*this, node); 999 } 1000 InEdgeIt(const Graph & _graph,const Edge & edge)1001 InEdgeIt(const Graph& _graph, const Edge& edge) : 1002 Edge(edge), graph(&_graph) {} 1003 1004 InEdgeIt& operator++() { 1005 graph->nextIn(*this); 1006 return *this; 1007 } 1008 1009 }; 1010 1011 /// \brief Base node of the iterator 1012 /// 1013 /// Returns the base node (ie. the source in this case) of the iterator baseNode(const OutEdgeIt & e)1014 Node baseNode(const OutEdgeIt &e) const { 1015 return Parent::source(static_cast<const Edge&>(e)); 1016 } 1017 /// \brief Running node of the iterator 1018 /// 1019 /// Returns the running node (ie. the target in this case) of the 1020 /// iterator runningNode(const OutEdgeIt & e)1021 Node runningNode(const OutEdgeIt &e) const { 1022 return Parent::target(static_cast<const Edge&>(e)); 1023 } 1024 1025 /// \brief Base node of the iterator 1026 /// 1027 /// Returns the base node (ie. the target in this case) of the iterator baseNode(const InEdgeIt & e)1028 Node baseNode(const InEdgeIt &e) const { 1029 return Parent::target(static_cast<const Edge&>(e)); 1030 } 1031 /// \brief Running node of the iterator 1032 /// 1033 /// Returns the running node (ie. the source in this case) of the 1034 /// iterator runningNode(const InEdgeIt & e)1035 Node runningNode(const InEdgeIt &e) const { 1036 return Parent::source(static_cast<const Edge&>(e)); 1037 } 1038 1039 class IncEdgeIt : public Parent::UEdge { 1040 friend class BpUGraphExtender; 1041 const Graph* graph; 1042 bool direction; 1043 public: 1044 IncEdgeIt()1045 IncEdgeIt() { } 1046 IncEdgeIt(Invalid i)1047 IncEdgeIt(Invalid i) : UEdge(i), direction(true) { } 1048 IncEdgeIt(const Graph & _graph,const Node & n)1049 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 1050 graph->firstInc(*this, direction, n); 1051 } 1052 IncEdgeIt(const Graph & _graph,const UEdge & ue,const Node & n)1053 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) 1054 : graph(&_graph), UEdge(ue) { 1055 direction = (graph->source(ue) == n); 1056 } 1057 1058 IncEdgeIt& operator++() { 1059 graph->nextInc(*this, direction); 1060 return *this; 1061 } 1062 }; 1063 1064 1065 /// Base node of the iterator 1066 /// 1067 /// Returns the base node of the iterator baseNode(const IncEdgeIt & e)1068 Node baseNode(const IncEdgeIt &e) const { 1069 return e.direction ? source(e) : target(e); 1070 } 1071 1072 /// Running node of the iterator 1073 /// 1074 /// Returns the running node of the iterator runningNode(const IncEdgeIt & e)1075 Node runningNode(const IncEdgeIt &e) const { 1076 return e.direction ? target(e) : source(e); 1077 } 1078 1079 template <typename _Value> 1080 class ANodeMap 1081 : public MapExtender<DefaultMap<Graph, ANode, _Value> > { 1082 public: 1083 typedef BpUGraphExtender Graph; 1084 typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent; 1085 ANodeMap(const Graph & graph)1086 ANodeMap(const Graph& graph) 1087 : Parent(graph) {} ANodeMap(const Graph & graph,const _Value & value)1088 ANodeMap(const Graph& graph, const _Value& value) 1089 : Parent(graph, value) {} 1090 1091 ANodeMap& operator=(const ANodeMap& cmap) { 1092 return operator=<ANodeMap>(cmap); 1093 } 1094 1095 template <typename CMap> 1096 ANodeMap& operator=(const CMap& cmap) { 1097 Parent::operator=(cmap); 1098 return *this; 1099 } 1100 1101 }; 1102 1103 template <typename _Value> 1104 class BNodeMap 1105 : public MapExtender<DefaultMap<Graph, BNode, _Value> > { 1106 public: 1107 typedef BpUGraphExtender Graph; 1108 typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent; 1109 BNodeMap(const Graph & graph)1110 BNodeMap(const Graph& graph) 1111 : Parent(graph) {} BNodeMap(const Graph & graph,const _Value & value)1112 BNodeMap(const Graph& graph, const _Value& value) 1113 : Parent(graph, value) {} 1114 1115 BNodeMap& operator=(const BNodeMap& cmap) { 1116 return operator=<BNodeMap>(cmap); 1117 } 1118 1119 template <typename CMap> 1120 BNodeMap& operator=(const CMap& cmap) { 1121 Parent::operator=(cmap); 1122 return *this; 1123 } 1124 1125 }; 1126 1127 public: 1128 1129 template <typename _Value> 1130 class NodeMap { 1131 public: 1132 typedef BpUGraphExtender Graph; 1133 1134 typedef Node Key; 1135 typedef _Value Value; 1136 1137 /// The reference type of the map; 1138 typedef typename ANodeMap<_Value>::Reference Reference; 1139 /// The const reference type of the map; 1140 typedef typename ANodeMap<_Value>::ConstReference ConstReference; 1141 1142 typedef True ReferenceMapTag; 1143 NodeMap(const Graph & _graph)1144 NodeMap(const Graph& _graph) 1145 : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {} NodeMap(const Graph & _graph,const _Value & _value)1146 NodeMap(const Graph& _graph, const _Value& _value) 1147 : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {} 1148 1149 NodeMap& operator=(const NodeMap& cmap) { 1150 return operator=<NodeMap>(cmap); 1151 } 1152 1153 template <typename CMap> 1154 NodeMap& operator=(const CMap& cmap) { 1155 checkConcept<concepts::ReadMap<Node, _Value>, CMap>(); 1156 aNodeMap = cmap; 1157 bNodeMap = cmap; 1158 return *this; 1159 } 1160 1161 ConstReference operator[](const Key& node) const { 1162 if (Parent::aNode(node)) { 1163 return aNodeMap[node]; 1164 } else { 1165 return bNodeMap[node]; 1166 } 1167 } 1168 1169 Reference operator[](const Key& node) { 1170 if (Parent::aNode(node)) { 1171 return aNodeMap[node]; 1172 } else { 1173 return bNodeMap[node]; 1174 } 1175 } 1176 set(const Key & node,const Value & value)1177 void set(const Key& node, const Value& value) { 1178 if (Parent::aNode(node)) { 1179 aNodeMap.set(node, value); 1180 } else { 1181 bNodeMap.set(node, value); 1182 } 1183 } 1184 1185 class MapIt : public NodeIt { 1186 public: 1187 1188 typedef NodeIt Parent; 1189 MapIt(NodeMap & _map)1190 explicit MapIt(NodeMap& _map) 1191 : Parent(_map.graph), map(_map) {} 1192 1193 typename MapTraits<NodeMap>::ConstReturnValue operator*() const { 1194 return map[*this]; 1195 } 1196 1197 typename MapTraits<NodeMap>::ReturnValue operator*() { 1198 return map[*this]; 1199 } 1200 set(const Value & value)1201 void set(const Value& value) { 1202 map.set(*this, value); 1203 } 1204 1205 private: 1206 NodeMap& map; 1207 }; 1208 1209 class ConstMapIt : public NodeIt { 1210 public: 1211 1212 typedef NodeIt Parent; 1213 ConstMapIt(const NodeMap & _map)1214 explicit ConstMapIt(const NodeMap& _map) 1215 : Parent(_map.graph), map(_map) {} 1216 1217 typename MapTraits<NodeMap>::ConstReturnValue operator*() const { 1218 return map[*this]; 1219 } 1220 1221 private: 1222 const NodeMap& map; 1223 }; 1224 1225 class ItemIt : public NodeIt { 1226 public: 1227 1228 typedef NodeIt Parent; 1229 ItemIt(const NodeMap & _map)1230 explicit ItemIt(const NodeMap& _map) 1231 : Parent(_map.graph) {} 1232 1233 }; 1234 1235 private: 1236 const Graph& graph; 1237 ANodeMap<_Value> aNodeMap; 1238 BNodeMap<_Value> bNodeMap; 1239 }; 1240 1241 1242 template <typename _Value> 1243 class EdgeMap 1244 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 1245 public: 1246 typedef BpUGraphExtender Graph; 1247 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 1248 EdgeMap(const Graph & graph)1249 EdgeMap(const Graph& graph) 1250 : Parent(graph) {} EdgeMap(const Graph & graph,const _Value & value)1251 EdgeMap(const Graph& graph, const _Value& value) 1252 : Parent(graph, value) {} 1253 1254 EdgeMap& operator=(const EdgeMap& cmap) { 1255 return operator=<EdgeMap>(cmap); 1256 } 1257 1258 template <typename CMap> 1259 EdgeMap& operator=(const CMap& cmap) { 1260 Parent::operator=(cmap); 1261 return *this; 1262 } 1263 }; 1264 1265 template <typename _Value> 1266 class UEdgeMap 1267 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > { 1268 public: 1269 typedef BpUGraphExtender Graph; 1270 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; 1271 UEdgeMap(const Graph & graph)1272 UEdgeMap(const Graph& graph) 1273 : Parent(graph) {} UEdgeMap(const Graph & graph,const _Value & value)1274 UEdgeMap(const Graph& graph, const _Value& value) 1275 : Parent(graph, value) {} 1276 1277 UEdgeMap& operator=(const UEdgeMap& cmap) { 1278 return operator=<UEdgeMap>(cmap); 1279 } 1280 1281 template <typename CMap> 1282 UEdgeMap& operator=(const CMap& cmap) { 1283 Parent::operator=(cmap); 1284 return *this; 1285 } 1286 }; 1287 1288 addANode()1289 Node addANode() { 1290 Node node = Parent::addANode(); 1291 notifier(ANode()).add(node); 1292 notifier(Node()).add(node); 1293 return node; 1294 } 1295 addBNode()1296 Node addBNode() { 1297 Node node = Parent::addBNode(); 1298 notifier(BNode()).add(node); 1299 notifier(Node()).add(node); 1300 return node; 1301 } 1302 addEdge(const Node & s,const Node & t)1303 UEdge addEdge(const Node& s, const Node& t) { 1304 UEdge uedge = Parent::addEdge(s, t); 1305 notifier(UEdge()).add(uedge); 1306 1307 std::vector<Edge> ev; 1308 ev.push_back(Parent::direct(uedge, true)); 1309 ev.push_back(Parent::direct(uedge, false)); 1310 notifier(Edge()).add(ev); 1311 1312 return uedge; 1313 } 1314 clear()1315 void clear() { 1316 notifier(Edge()).clear(); 1317 notifier(UEdge()).clear(); 1318 notifier(Node()).clear(); 1319 notifier(BNode()).clear(); 1320 notifier(ANode()).clear(); 1321 Parent::clear(); 1322 } 1323 1324 template <typename Graph, typename ANodeRefMap, 1325 typename BNodeRefMap, typename UEdgeRefMap> build(const Graph & graph,ANodeRefMap & aNodeRef,BNodeRefMap & bNodeRef,UEdgeRefMap & uEdgeRef)1326 void build(const Graph& graph, ANodeRefMap& aNodeRef, 1327 BNodeRefMap& bNodeRef, UEdgeRefMap& uEdgeRef) { 1328 Parent::build(graph, aNodeRef, bNodeRef, uEdgeRef); 1329 notifier(ANode()).build(); 1330 notifier(BNode()).build(); 1331 notifier(Node()).build(); 1332 notifier(UEdge()).build(); 1333 notifier(Edge()).build(); 1334 } 1335 erase(const Node & node)1336 void erase(const Node& node) { 1337 UEdge uedge; 1338 if (Parent::aNode(node)) { 1339 Parent::firstFromANode(uedge, node); 1340 while (uedge != INVALID) { 1341 erase(uedge); 1342 Parent::firstFromANode(uedge, node); 1343 } 1344 notifier(ANode()).erase(node); 1345 } else { 1346 Parent::firstFromBNode(uedge, node); 1347 while (uedge != INVALID) { 1348 erase(uedge); 1349 Parent::firstFromBNode(uedge, node); 1350 } 1351 notifier(BNode()).erase(node); 1352 } 1353 1354 notifier(Node()).erase(node); 1355 Parent::erase(node); 1356 } 1357 erase(const UEdge & uedge)1358 void erase(const UEdge& uedge) { 1359 std::vector<Edge> ev; 1360 ev.push_back(Parent::direct(uedge, true)); 1361 ev.push_back(Parent::direct(uedge, false)); 1362 notifier(Edge()).erase(ev); 1363 notifier(UEdge()).erase(uedge); 1364 Parent::erase(uedge); 1365 } 1366 1367 BpUGraphExtender()1368 BpUGraphExtender() { 1369 anode_notifier.setContainer(*this); 1370 bnode_notifier.setContainer(*this); 1371 node_notifier.setContainer(*this); 1372 edge_notifier.setContainer(*this); 1373 uedge_notifier.setContainer(*this); 1374 } 1375 ~BpUGraphExtender()1376 ~BpUGraphExtender() { 1377 uedge_notifier.clear(); 1378 edge_notifier.clear(); 1379 node_notifier.clear(); 1380 anode_notifier.clear(); 1381 bnode_notifier.clear(); 1382 } 1383 1384 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { 1385 UEdge uedge = Parent::findUEdge(u, v, prev); 1386 if (uedge != INVALID) { 1387 return Parent::direct(uedge, Parent::aNode(u)); 1388 } else { 1389 return INVALID; 1390 } 1391 } 1392 1393 }; 1394 1395 } 1396 1397 #endif 1398