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_SMART_GRAPH_H 20 #define LEMON_SMART_GRAPH_H 21 22 ///\ingroup graphs 23 ///\file 24 ///\brief SmartGraph and SmartUGraph classes. 25 26 #include <vector> 27 28 #include <lemon/bits/invalid.h> 29 30 #include <lemon/bits/base_extender.h> 31 #include <lemon/bits/graph_extender.h> 32 33 #include <lemon/bits/utility.h> 34 #include <lemon/error.h> 35 36 #include <lemon/bits/graph_extender.h> 37 38 namespace lemon { 39 40 class SmartGraph; 41 ///Base of SmartGraph 42 43 ///Base of SmartGraph 44 /// 45 class SmartGraphBase { 46 protected: 47 48 struct NodeT 49 { 50 int first_in, first_out; NodeTNodeT51 NodeT() {} 52 }; 53 struct EdgeT 54 { 55 int target, source, next_in, next_out; EdgeTEdgeT56 EdgeT() {} 57 }; 58 59 std::vector<NodeT> nodes; 60 61 std::vector<EdgeT> edges; 62 63 64 public: 65 66 typedef SmartGraphBase Graph; 67 68 class Node; 69 class Edge; 70 71 72 public: 73 SmartGraphBase()74 SmartGraphBase() : nodes(), edges() { } SmartGraphBase(const SmartGraphBase & _g)75 SmartGraphBase(const SmartGraphBase &_g) 76 : nodes(_g.nodes), edges(_g.edges) { } 77 78 typedef True NodeNumTag; 79 typedef True EdgeNumTag; 80 nodeNum()81 int nodeNum() const { return nodes.size(); } edgeNum()82 int edgeNum() const { return edges.size(); } 83 maxNodeId()84 int maxNodeId() const { return nodes.size()-1; } maxEdgeId()85 int maxEdgeId() const { return edges.size()-1; } 86 addNode()87 Node addNode() { 88 int n = nodes.size(); 89 nodes.push_back(NodeT()); 90 nodes[n].first_in = -1; 91 nodes[n].first_out = -1; 92 return Node(n); 93 } 94 addEdge(Node u,Node v)95 Edge addEdge(Node u, Node v) { 96 int n = edges.size(); 97 edges.push_back(EdgeT()); 98 edges[n].source = u.id; 99 edges[n].target = v.id; 100 edges[n].next_out = nodes[u.id].first_out; 101 edges[n].next_in = nodes[v.id].first_in; 102 nodes[u.id].first_out = nodes[v.id].first_in = n; 103 104 return Edge(n); 105 } 106 clear()107 void clear() { 108 edges.clear(); 109 nodes.clear(); 110 } 111 source(Edge e)112 Node source(Edge e) const { return Node(edges[e.id].source); } target(Edge e)113 Node target(Edge e) const { return Node(edges[e.id].target); } 114 id(Node v)115 static int id(Node v) { return v.id; } id(Edge e)116 static int id(Edge e) { return e.id; } 117 nodeFromId(int id)118 static Node nodeFromId(int id) { return Node(id);} edgeFromId(int id)119 static Edge edgeFromId(int id) { return Edge(id);} 120 121 class Node { 122 friend class SmartGraphBase; 123 friend class SmartGraph; 124 125 protected: 126 int id; Node(int _id)127 explicit Node(int _id) : id(_id) {} 128 public: Node()129 Node() {} Node(Invalid)130 Node (Invalid) : id(-1) {} 131 bool operator==(const Node i) const {return id == i.id;} 132 bool operator!=(const Node i) const {return id != i.id;} 133 bool operator<(const Node i) const {return id < i.id;} 134 }; 135 136 137 class Edge { 138 friend class SmartGraphBase; 139 friend class SmartGraph; 140 141 protected: 142 int id; Edge(int _id)143 explicit Edge(int _id) : id(_id) {} 144 public: Edge()145 Edge() { } Edge(Invalid)146 Edge (Invalid) : id(-1) {} 147 bool operator==(const Edge i) const {return id == i.id;} 148 bool operator!=(const Edge i) const {return id != i.id;} 149 bool operator<(const Edge i) const {return id < i.id;} 150 }; 151 first(Node & node)152 void first(Node& node) const { 153 node.id = nodes.size() - 1; 154 } 155 next(Node & node)156 static void next(Node& node) { 157 --node.id; 158 } 159 first(Edge & edge)160 void first(Edge& edge) const { 161 edge.id = edges.size() - 1; 162 } 163 next(Edge & edge)164 static void next(Edge& edge) { 165 --edge.id; 166 } 167 firstOut(Edge & edge,const Node & node)168 void firstOut(Edge& edge, const Node& node) const { 169 edge.id = nodes[node.id].first_out; 170 } 171 nextOut(Edge & edge)172 void nextOut(Edge& edge) const { 173 edge.id = edges[edge.id].next_out; 174 } 175 firstIn(Edge & edge,const Node & node)176 void firstIn(Edge& edge, const Node& node) const { 177 edge.id = nodes[node.id].first_in; 178 } 179 nextIn(Edge & edge)180 void nextIn(Edge& edge) const { 181 edge.id = edges[edge.id].next_in; 182 } 183 184 }; 185 186 typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase; 187 188 ///\ingroup graphs 189 /// 190 ///\brief A smart graph class. 191 /// 192 ///This is a simple and fast graph implementation. 193 ///It is also quite memory efficient, but at the price 194 ///that <b> it does support only limited (only stack-like) 195 ///node and edge deletions</b>. 196 ///It conforms to 197 ///the \ref concepts::Graph "Graph concept" with an 198 ///important extra feature that 199 ///its maps are real \ref concepts::ReferenceMap "reference map"s. 200 /// 201 ///\sa concepts::Graph. 202 /// 203 ///\author Alpar Juttner 204 class SmartGraph : public ExtendedSmartGraphBase { 205 public: 206 207 typedef ExtendedSmartGraphBase Parent; 208 209 private: 210 211 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 212 213 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 214 /// SmartGraph(const SmartGraph &)215 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; 216 ///\brief Assignment of SmartGraph to another one is \e not allowed. 217 ///Use GraphCopy() instead. 218 219 ///Assignment of SmartGraph to another one is \e not allowed. 220 ///Use GraphCopy() instead. 221 void operator=(const SmartGraph &) {} 222 223 public: 224 225 /// Constructor 226 227 /// Constructor. 228 /// SmartGraph()229 SmartGraph() {}; 230 231 ///Add a new node to the graph. 232 233 /// \return the new node. 234 /// addNode()235 Node addNode() { return Parent::addNode(); } 236 237 ///Add a new edge to the graph. 238 239 ///Add a new edge to the graph with source node \c s 240 ///and target node \c t. 241 ///\return the new edge. addEdge(const Node & s,const Node & t)242 Edge addEdge(const Node& s, const Node& t) { 243 return Parent::addEdge(s, t); 244 } 245 246 /// \brief Using this it is possible to avoid the superfluous memory 247 /// allocation. 248 249 /// Using this it is possible to avoid the superfluous memory 250 /// allocation: if you know that the graph you want to build will 251 /// be very large (e.g. it will contain millions of nodes and/or edges) 252 /// then it is worth reserving space for this amount before starting 253 /// to build the graph. 254 /// \sa reserveEdge reserveNode(int n)255 void reserveNode(int n) { nodes.reserve(n); }; 256 257 /// \brief Using this it is possible to avoid the superfluous memory 258 /// allocation. 259 260 /// Using this it is possible to avoid the superfluous memory 261 /// allocation: if you know that the graph you want to build will 262 /// be very large (e.g. it will contain millions of nodes and/or edges) 263 /// then it is worth reserving space for this amount before starting 264 /// to build the graph. 265 /// \sa reserveNode reserveEdge(int m)266 void reserveEdge(int m) { edges.reserve(m); }; 267 268 ///Clear the graph. 269 270 ///Erase all the nodes and edges from the graph. 271 /// clear()272 void clear() { 273 Parent::clear(); 274 } 275 276 ///Split a node. 277 278 ///This function splits a node. First a new node is added to the graph, 279 ///then the source of each outgoing edge of \c n is moved to this new node. 280 ///If \c connect is \c true (this is the default value), then a new edge 281 ///from \c n to the newly created node is also added. 282 ///\return The newly created node. 283 /// 284 ///\note The <tt>Edge</tt>s 285 ///referencing a moved edge remain 286 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s 287 ///may be invalidated. 288 ///\warning This functionality cannot be used together with the Snapshot 289 ///feature. 290 ///\todo It could be implemented in a bit faster way. 291 Node split(Node n, bool connect = true) 292 { 293 Node b = addNode(); 294 nodes[b.id].first_out=nodes[n.id].first_out; 295 nodes[n.id].first_out=-1; 296 for(int i=nodes[b.id].first_out;i!=-1;i++) edges[i].source=b.id; 297 if(connect) addEdge(n,b); 298 return b; 299 } 300 301 public: 302 303 class Snapshot; 304 305 protected: 306 restoreSnapshot(const Snapshot & s)307 void restoreSnapshot(const Snapshot &s) 308 { 309 while(s.edge_num<edges.size()) { 310 Edge edge = edgeFromId(edges.size()-1); 311 Parent::notifier(Edge()).erase(edge); 312 nodes[edges.back().source].first_out=edges.back().next_out; 313 nodes[edges.back().target].first_in=edges.back().next_in; 314 edges.pop_back(); 315 } 316 while(s.node_num<nodes.size()) { 317 Node node = nodeFromId(nodes.size()-1); 318 Parent::notifier(Node()).erase(node); 319 nodes.pop_back(); 320 } 321 } 322 323 public: 324 325 ///Class to make a snapshot of the graph and to restrore to it later. 326 327 ///Class to make a snapshot of the graph and to restrore to it later. 328 /// 329 ///The newly added nodes and edges can be removed using the 330 ///restore() function. 331 ///\note After you restore a state, you cannot restore 332 ///a later state, in other word you cannot add again the edges deleted 333 ///by restore() using another one Snapshot instance. 334 /// 335 ///\warning If you do not use correctly the snapshot that can cause 336 ///either broken program, invalid state of the graph, valid but 337 ///not the restored graph or no change. Because the runtime performance 338 ///the validity of the snapshot is not stored. 339 class Snapshot 340 { 341 SmartGraph *g; 342 protected: 343 friend class SmartGraph; 344 unsigned int node_num; 345 unsigned int edge_num; 346 public: 347 ///Default constructor. 348 349 ///Default constructor. 350 ///To actually make a snapshot you must call save(). 351 /// Snapshot()352 Snapshot() : g(0) {} 353 ///Constructor that immediately makes a snapshot 354 355 ///This constructor immediately makes a snapshot of the graph. 356 ///\param _g The graph we make a snapshot of. Snapshot(SmartGraph & _g)357 Snapshot(SmartGraph &_g) :g(&_g) { 358 node_num=g->nodes.size(); 359 edge_num=g->edges.size(); 360 } 361 362 ///Make a snapshot. 363 364 ///Make a snapshot of the graph. 365 /// 366 ///This function can be called more than once. In case of a repeated 367 ///call, the previous snapshot gets lost. 368 ///\param _g The graph we make the snapshot of. save(SmartGraph & _g)369 void save(SmartGraph &_g) 370 { 371 g=&_g; 372 node_num=g->nodes.size(); 373 edge_num=g->edges.size(); 374 } 375 376 ///Undo the changes until a snapshot. 377 378 ///Undo the changes until a snapshot created by save(). 379 /// 380 ///\note After you restored a state, you cannot restore 381 ///a later state, in other word you cannot add again the edges deleted 382 ///by restore(). restore()383 void restore() 384 { 385 g->restoreSnapshot(*this); 386 } 387 }; 388 }; 389 390 391 class SmartUGraphBase { 392 393 protected: 394 395 struct NodeT { 396 int first_out; 397 }; 398 399 struct EdgeT { 400 int target; 401 int next_out; 402 }; 403 404 std::vector<NodeT> nodes; 405 std::vector<EdgeT> edges; 406 407 int first_free_edge; 408 409 public: 410 411 typedef SmartUGraphBase Graph; 412 413 class Node; 414 class Edge; 415 class UEdge; 416 417 class Node { 418 friend class SmartUGraphBase; 419 protected: 420 421 int id; Node(int pid)422 explicit Node(int pid) { id = pid;} 423 424 public: Node()425 Node() {} Node(Invalid)426 Node (Invalid) { id = -1; } 427 bool operator==(const Node& node) const {return id == node.id;} 428 bool operator!=(const Node& node) const {return id != node.id;} 429 bool operator<(const Node& node) const {return id < node.id;} 430 }; 431 432 class UEdge { 433 friend class SmartUGraphBase; 434 protected: 435 436 int id; UEdge(int pid)437 explicit UEdge(int pid) { id = pid;} 438 439 public: UEdge()440 UEdge() {} UEdge(Invalid)441 UEdge (Invalid) { id = -1; } 442 bool operator==(const UEdge& edge) const {return id == edge.id;} 443 bool operator!=(const UEdge& edge) const {return id != edge.id;} 444 bool operator<(const UEdge& edge) const {return id < edge.id;} 445 }; 446 447 class Edge { 448 friend class SmartUGraphBase; 449 protected: 450 451 int id; Edge(int pid)452 explicit Edge(int pid) { id = pid;} 453 454 public: UEdge()455 operator UEdge() const { return uEdgeFromId(id / 2); } 456 Edge()457 Edge() {} Edge(Invalid)458 Edge (Invalid) { id = -1; } 459 bool operator==(const Edge& edge) const {return id == edge.id;} 460 bool operator!=(const Edge& edge) const {return id != edge.id;} 461 bool operator<(const Edge& edge) const {return id < edge.id;} 462 }; 463 464 465 SmartUGraphBase()466 SmartUGraphBase() 467 : nodes(), edges() {} 468 469 maxNodeId()470 int maxNodeId() const { return nodes.size()-1; } maxUEdgeId()471 int maxUEdgeId() const { return edges.size() / 2 - 1; } maxEdgeId()472 int maxEdgeId() const { return edges.size()-1; } 473 source(Edge e)474 Node source(Edge e) const { return Node(edges[e.id ^ 1].target); } target(Edge e)475 Node target(Edge e) const { return Node(edges[e.id].target); } 476 source(UEdge e)477 Node source(UEdge e) const { return Node(edges[2 * e.id].target); } target(UEdge e)478 Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); } 479 direction(Edge e)480 static bool direction(Edge e) { 481 return (e.id & 1) == 1; 482 } 483 direct(UEdge e,bool d)484 static Edge direct(UEdge e, bool d) { 485 return Edge(e.id * 2 + (d ? 1 : 0)); 486 } 487 first(Node & node)488 void first(Node& node) const { 489 node.id = nodes.size() - 1; 490 } 491 next(Node & node)492 void next(Node& node) const { 493 --node.id; 494 } 495 first(Edge & edge)496 void first(Edge& edge) const { 497 edge.id = edges.size() - 1; 498 } 499 next(Edge & edge)500 void next(Edge& edge) const { 501 --edge.id; 502 } 503 first(UEdge & edge)504 void first(UEdge& edge) const { 505 edge.id = edges.size() / 2 - 1; 506 } 507 next(UEdge & edge)508 void next(UEdge& edge) const { 509 --edge.id; 510 } 511 firstOut(Edge & edge,const Node & v)512 void firstOut(Edge &edge, const Node& v) const { 513 edge.id = nodes[v.id].first_out; 514 } nextOut(Edge & edge)515 void nextOut(Edge &edge) const { 516 edge.id = edges[edge.id].next_out; 517 } 518 firstIn(Edge & edge,const Node & v)519 void firstIn(Edge &edge, const Node& v) const { 520 edge.id = ((nodes[v.id].first_out) ^ 1); 521 if (edge.id == -2) edge.id = -1; 522 } nextIn(Edge & edge)523 void nextIn(Edge &edge) const { 524 edge.id = ((edges[edge.id ^ 1].next_out) ^ 1); 525 if (edge.id == -2) edge.id = -1; 526 } 527 firstInc(UEdge & edge,bool & d,const Node & v)528 void firstInc(UEdge &edge, bool& d, const Node& v) const { 529 int de = nodes[v.id].first_out; 530 if (de != -1) { 531 edge.id = de / 2; 532 d = ((de & 1) == 1); 533 } else { 534 edge.id = -1; 535 d = true; 536 } 537 } nextInc(UEdge & edge,bool & d)538 void nextInc(UEdge &edge, bool& d) const { 539 int de = (edges[(edge.id * 2) | (d ? 1 : 0)].next_out); 540 if (de != -1) { 541 edge.id = de / 2; 542 d = ((de & 1) == 1); 543 } else { 544 edge.id = -1; 545 d = true; 546 } 547 } 548 id(Node v)549 static int id(Node v) { return v.id; } id(Edge e)550 static int id(Edge e) { return e.id; } id(UEdge e)551 static int id(UEdge e) { return e.id; } 552 nodeFromId(int id)553 static Node nodeFromId(int id) { return Node(id);} edgeFromId(int id)554 static Edge edgeFromId(int id) { return Edge(id);} uEdgeFromId(int id)555 static UEdge uEdgeFromId(int id) { return UEdge(id);} 556 addNode()557 Node addNode() { 558 int n = nodes.size(); 559 nodes.push_back(NodeT()); 560 nodes[n].first_out = -1; 561 562 return Node(n); 563 } 564 addEdge(Node u,Node v)565 UEdge addEdge(Node u, Node v) { 566 int n = edges.size(); 567 edges.push_back(EdgeT()); 568 edges.push_back(EdgeT()); 569 570 edges[n].target = u.id; 571 edges[n | 1].target = v.id; 572 573 edges[n].next_out = nodes[v.id].first_out; 574 nodes[v.id].first_out = n; 575 576 edges[n | 1].next_out = nodes[u.id].first_out; 577 nodes[u.id].first_out = (n | 1); 578 579 return UEdge(n / 2); 580 } 581 clear()582 void clear() { 583 edges.clear(); 584 nodes.clear(); 585 } 586 587 }; 588 589 typedef UGraphExtender<SmartUGraphBase> ExtendedSmartUGraphBase; 590 591 /// \ingroup graphs 592 /// 593 /// \brief A smart undirected graph class. 594 /// 595 /// This is a simple and fast undirected graph implementation. 596 /// It is also quite memory efficient, but at the price 597 /// that <b> it does support only limited (only stack-like) 598 /// node and edge deletions</b>. 599 /// Except from this it conforms to 600 /// the \ref concepts::UGraph "UGraph concept". 601 /// 602 ///It also has an 603 ///important extra feature that 604 ///its maps are real \ref concepts::ReferenceMap "reference map"s. 605 /// 606 /// \sa concepts::UGraph. 607 /// 608 class SmartUGraph : public ExtendedSmartUGraphBase { 609 private: 610 611 ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead. 612 613 ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead. 614 /// SmartUGraph(const SmartUGraph &)615 SmartUGraph(const SmartUGraph &) : ExtendedSmartUGraphBase() {}; 616 617 ///\brief Assignment of SmartUGraph to another one is \e not allowed. 618 ///Use UGraphCopy() instead. 619 620 ///Assignment of SmartUGraph to another one is \e not allowed. 621 ///Use UGraphCopy() instead. 622 void operator=(const SmartUGraph &) {} 623 624 public: 625 626 typedef ExtendedSmartUGraphBase Parent; 627 typedef Parent::OutEdgeIt IncEdgeIt; 628 629 /// Constructor 630 631 /// Constructor. 632 /// SmartUGraph()633 SmartUGraph() {} 634 635 ///Add a new node to the graph. 636 637 /// \return the new node. 638 /// addNode()639 Node addNode() { return Parent::addNode(); } 640 641 ///Add a new undirected edge to the graph. 642 643 ///Add a new undirected edge to the graph with node \c s 644 ///and \c t. 645 ///\return the new undirected edge. addEdge(const Node & s,const Node & t)646 UEdge addEdge(const Node& s, const Node& t) { 647 return Parent::addEdge(s, t); 648 } 649 650 ///Clear the graph. 651 652 ///Erase all the nodes and edges from the graph. 653 /// clear()654 void clear() { 655 Parent::clear(); 656 } 657 658 public: 659 660 class Snapshot; 661 662 protected: 663 saveSnapshot(Snapshot & s)664 void saveSnapshot(Snapshot &s) 665 { 666 s.graph = this; 667 s.node_num = nodes.size(); 668 s.edge_num = edges.size(); 669 } 670 restoreSnapshot(const Snapshot & s)671 void restoreSnapshot(const Snapshot &s) 672 { 673 while(s.edge_num<edges.size()) { 674 int n=edges.size()-1; 675 UEdge edge=uEdgeFromId(n/2); 676 Parent::notifier(UEdge()).erase(edge); 677 std::vector<Edge> dir; 678 dir.push_back(edgeFromId(n)); 679 dir.push_back(edgeFromId(n-1)); 680 Parent::notifier(Edge()).erase(dir); 681 nodes[edges[n].target].first_out=edges[n].next_out; 682 nodes[edges[n-1].target].first_out=edges[n-1].next_out; 683 edges.pop_back(); 684 edges.pop_back(); 685 } 686 while(s.node_num<nodes.size()) { 687 int n=nodes.size()-1; 688 Node node = nodeFromId(n); 689 Parent::notifier(Node()).erase(node); 690 nodes.pop_back(); 691 } 692 } 693 694 public: 695 696 ///Class to make a snapshot of the graph and to restrore to it later. 697 698 ///Class to make a snapshot of the graph and to restrore to it later. 699 /// 700 ///The newly added nodes and edges can be removed using the 701 ///restore() function. 702 /// 703 ///\note After you restore a state, you cannot restore 704 ///a later state, in other word you cannot add again the edges deleted 705 ///by restore() using another one Snapshot instance. 706 /// 707 ///\warning If you do not use correctly the snapshot that can cause 708 ///either broken program, invalid state of the graph, valid but 709 ///not the restored graph or no change. Because the runtime performance 710 ///the validity of the snapshot is not stored. 711 class Snapshot 712 { 713 SmartUGraph *graph; 714 protected: 715 friend class SmartUGraph; 716 unsigned int node_num; 717 unsigned int edge_num; 718 public: 719 ///Default constructor. 720 721 ///Default constructor. 722 ///To actually make a snapshot you must call save(). 723 /// Snapshot()724 Snapshot() : graph(0) {} 725 ///Constructor that immediately makes a snapshot 726 727 ///This constructor immediately makes a snapshot of the graph. 728 ///\param g The graph we make a snapshot of. Snapshot(SmartUGraph & g)729 Snapshot(SmartUGraph &g) { 730 g.saveSnapshot(*this); 731 } 732 733 ///Make a snapshot. 734 735 ///Make a snapshot of the graph. 736 /// 737 ///This function can be called more than once. In case of a repeated 738 ///call, the previous snapshot gets lost. 739 ///\param g The graph we make the snapshot of. save(SmartUGraph & g)740 void save(SmartUGraph &g) 741 { 742 g.saveSnapshot(*this); 743 } 744 745 ///Undo the changes until a snapshot. 746 747 ///Undo the changes until a snapshot created by save(). 748 /// 749 ///\note After you restored a state, you cannot restore 750 ///a later state, in other word you cannot add again the edges deleted 751 ///by restore(). restore()752 void restore() 753 { 754 graph->restoreSnapshot(*this); 755 } 756 }; 757 }; 758 759 760 class SmartBpUGraphBase { 761 public: 762 763 class NodeSetError : public LogicError { 764 public: what()765 virtual const char* what() const throw() { 766 return "lemon::SmartBpUGraph::NodeSetError"; 767 } 768 }; 769 770 protected: 771 772 struct NodeT { 773 int first; NodeTNodeT774 NodeT() {} NodeTNodeT775 NodeT(int _first) : first(_first) {} 776 }; 777 778 struct UEdgeT { 779 int aNode, next_out; 780 int bNode, next_in; 781 }; 782 783 std::vector<NodeT> aNodes; 784 std::vector<NodeT> bNodes; 785 786 std::vector<UEdgeT> edges; 787 788 public: 789 790 class Node { 791 friend class SmartBpUGraphBase; 792 protected: 793 int id; 794 Node(int _id)795 explicit Node(int _id) : id(_id) {} 796 public: Node()797 Node() {} Node(Invalid)798 Node(Invalid) : id(-1) {} 799 bool operator==(const Node i) const {return id==i.id;} 800 bool operator!=(const Node i) const {return id!=i.id;} 801 bool operator<(const Node i) const {return id<i.id;} 802 }; 803 804 class UEdge { 805 friend class SmartBpUGraphBase; 806 protected: 807 int id; 808 UEdge(int _id)809 UEdge(int _id) : id(_id) {} 810 public: UEdge()811 UEdge() {} UEdge(Invalid)812 UEdge(Invalid) : id(-1) {} 813 bool operator==(const UEdge i) const {return id==i.id;} 814 bool operator!=(const UEdge i) const {return id!=i.id;} 815 bool operator<(const UEdge i) const {return id<i.id;} 816 }; 817 firstANode(Node & node)818 void firstANode(Node& node) const { 819 node.id = 2 * aNodes.size() - 2; 820 if (node.id < 0) node.id = -1; 821 } nextANode(Node & node)822 void nextANode(Node& node) const { 823 node.id -= 2; 824 if (node.id < 0) node.id = -1; 825 } 826 firstBNode(Node & node)827 void firstBNode(Node& node) const { 828 node.id = 2 * bNodes.size() - 1; 829 } nextBNode(Node & node)830 void nextBNode(Node& node) const { 831 node.id -= 2; 832 } 833 first(Node & node)834 void first(Node& node) const { 835 if (aNodes.size() > 0) { 836 node.id = 2 * aNodes.size() - 2; 837 } else { 838 node.id = 2 * bNodes.size() - 1; 839 } 840 } next(Node & node)841 void next(Node& node) const { 842 node.id -= 2; 843 if (node.id == -2) { 844 node.id = 2 * bNodes.size() - 1; 845 } 846 } 847 first(UEdge & edge)848 void first(UEdge& edge) const { 849 edge.id = edges.size() - 1; 850 } next(UEdge & edge)851 void next(UEdge& edge) const { 852 --edge.id; 853 } 854 firstFromANode(UEdge & edge,const Node & node)855 void firstFromANode(UEdge& edge, const Node& node) const { 856 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); 857 edge.id = aNodes[node.id >> 1].first; 858 } nextFromANode(UEdge & edge)859 void nextFromANode(UEdge& edge) const { 860 edge.id = edges[edge.id].next_out; 861 } 862 firstFromBNode(UEdge & edge,const Node & node)863 void firstFromBNode(UEdge& edge, const Node& node) const { 864 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); 865 edge.id = bNodes[node.id >> 1].first; 866 } nextFromBNode(UEdge & edge)867 void nextFromBNode(UEdge& edge) const { 868 edge.id = edges[edge.id].next_in; 869 } 870 id(const Node & node)871 static int id(const Node& node) { 872 return node.id; 873 } nodeFromId(int id)874 static Node nodeFromId(int id) { 875 return Node(id); 876 } maxNodeId()877 int maxNodeId() const { 878 return aNodes.size() > bNodes.size() ? 879 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; 880 } 881 id(const UEdge & edge)882 static int id(const UEdge& edge) { 883 return edge.id; 884 } uEdgeFromId(int id)885 static UEdge uEdgeFromId(int id) { 886 return UEdge(id); 887 } maxUEdgeId()888 int maxUEdgeId() const { 889 return edges.size(); 890 } 891 aNodeId(const Node & node)892 static int aNodeId(const Node& node) { 893 return node.id >> 1; 894 } nodeFromANodeId(int id)895 static Node nodeFromANodeId(int id) { 896 return Node(id << 1); 897 } maxANodeId()898 int maxANodeId() const { 899 return aNodes.size(); 900 } 901 bNodeId(const Node & node)902 static int bNodeId(const Node& node) { 903 return node.id >> 1; 904 } nodeFromBNodeId(int id)905 static Node nodeFromBNodeId(int id) { 906 return Node((id << 1) + 1); 907 } maxBNodeId()908 int maxBNodeId() const { 909 return bNodes.size(); 910 } 911 aNode(const UEdge & edge)912 Node aNode(const UEdge& edge) const { 913 return Node(edges[edge.id].aNode); 914 } bNode(const UEdge & edge)915 Node bNode(const UEdge& edge) const { 916 return Node(edges[edge.id].bNode); 917 } 918 aNode(const Node & node)919 static bool aNode(const Node& node) { 920 return (node.id & 1) == 0; 921 } 922 bNode(const Node & node)923 static bool bNode(const Node& node) { 924 return (node.id & 1) == 1; 925 } 926 addANode()927 Node addANode() { 928 NodeT nodeT; 929 nodeT.first = -1; 930 aNodes.push_back(nodeT); 931 return Node(aNodes.size() * 2 - 2); 932 } 933 addBNode()934 Node addBNode() { 935 NodeT nodeT; 936 nodeT.first = -1; 937 bNodes.push_back(nodeT); 938 return Node(bNodes.size() * 2 - 1); 939 } 940 addEdge(const Node & source,const Node & target)941 UEdge addEdge(const Node& source, const Node& target) { 942 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); 943 UEdgeT edgeT; 944 if ((source.id & 1) == 0) { 945 edgeT.aNode = source.id; 946 edgeT.bNode = target.id; 947 } else { 948 edgeT.aNode = target.id; 949 edgeT.bNode = source.id; 950 } 951 edgeT.next_out = aNodes[edgeT.aNode >> 1].first; 952 aNodes[edgeT.aNode >> 1].first = edges.size(); 953 edgeT.next_in = bNodes[edgeT.bNode >> 1].first; 954 bNodes[edgeT.bNode >> 1].first = edges.size(); 955 edges.push_back(edgeT); 956 return UEdge(edges.size() - 1); 957 } 958 reserveANode(int n)959 void reserveANode(int n) { aNodes.reserve(n); }; reserveBNode(int n)960 void reserveBNode(int n) { bNodes.reserve(n); }; 961 reserveEdge(int m)962 void reserveEdge(int m) { edges.reserve(m); }; 963 clear()964 void clear() { 965 aNodes.clear(); 966 bNodes.clear(); 967 edges.clear(); 968 } 969 970 typedef True NodeNumTag; nodeNum()971 int nodeNum() const { return aNodes.size() + bNodes.size(); } aNodeNum()972 int aNodeNum() const { return aNodes.size(); } bNodeNum()973 int bNodeNum() const { return bNodes.size(); } 974 975 typedef True EdgeNumTag; uEdgeNum()976 int uEdgeNum() const { return edges.size(); } 977 978 }; 979 980 981 typedef BpUGraphExtender<BidirBpUGraphExtender<SmartBpUGraphBase> > 982 ExtendedSmartBpUGraphBase; 983 984 /// \ingroup graphs 985 /// 986 /// \brief A smart bipartite undirected graph class. 987 /// 988 /// This is a simple and fast bipartite undirected graph implementation. 989 /// It is also quite memory efficient, but at the price 990 /// that <b> it does not support node and edge deletions</b>. 991 /// Except from this it conforms to 992 /// the \ref concepts::BpUGraph "BpUGraph concept". 993 /// 994 ///It also has an 995 ///important extra feature that 996 ///its maps are real \ref concepts::ReferenceMap "reference map"s. 997 /// 998 /// \sa concepts::BpUGraph. 999 /// 1000 class SmartBpUGraph : public ExtendedSmartBpUGraphBase { 1001 private: 1002 1003 /// \brief SmartBpUGraph is \e not copy constructible. 1004 /// 1005 ///SmartBpUGraph is \e not copy constructible. SmartBpUGraph(const SmartBpUGraph &)1006 SmartBpUGraph(const SmartBpUGraph &) : ExtendedSmartBpUGraphBase() {}; 1007 1008 /// \brief Assignment of SmartBpUGraph to another one is \e not 1009 /// allowed. 1010 /// 1011 /// Assignment of SmartBpUGraph to another one is \e not allowed. 1012 void operator=(const SmartBpUGraph &) {} 1013 1014 public: 1015 1016 typedef ExtendedSmartBpUGraphBase Parent; 1017 1018 ///Constructor 1019 1020 ///Constructor. 1021 /// SmartBpUGraph()1022 SmartBpUGraph() : ExtendedSmartBpUGraphBase() {} 1023 1024 ///Add a new ANode to the graph. 1025 1026 /// \return the new node. 1027 /// addANode()1028 Node addANode() { return Parent::addANode(); } 1029 1030 ///Add a new BNode to the graph. 1031 1032 /// \return the new node. 1033 /// addBNode()1034 Node addBNode() { return Parent::addBNode(); } 1035 1036 ///Add a new undirected edge to the graph. 1037 1038 ///Add a new undirected edge to the graph with node \c s 1039 ///and \c t. 1040 ///\return the new undirected edge. addEdge(const Node & s,const Node & t)1041 UEdge addEdge(const Node& s, const Node& t) { 1042 return Parent::addEdge(s, t); 1043 } 1044 1045 ///Clear the graph. 1046 1047 ///Erase all the nodes and edges from the graph. 1048 /// clear()1049 void clear() { 1050 Parent::clear(); 1051 } 1052 1053 public: 1054 1055 class Snapshot; 1056 1057 protected: 1058 restoreSnapshot(const Snapshot & s)1059 void restoreSnapshot(const Snapshot &s) 1060 { 1061 while(s.edge_num<edges.size()) { 1062 UEdge edge = uEdgeFromId(edges.size()-1); 1063 Parent::notifier(UEdge()).erase(edge); 1064 std::vector<Edge> dir; 1065 dir.push_back(Parent::direct(edge, true)); 1066 dir.push_back(Parent::direct(edge, false)); 1067 Parent::notifier(Edge()).erase(dir); 1068 aNodes[edges.back().aNode >> 1].first=edges.back().next_out; 1069 bNodes[edges.back().bNode >> 1].first=edges.back().next_in; 1070 edges.pop_back(); 1071 } 1072 while(s.anode_num<aNodes.size()) { 1073 Node node = nodeFromANodeId(aNodes.size() - 1); 1074 Parent::notifier(ANode()).erase(node); 1075 Parent::notifier(Node()).erase(node); 1076 aNodes.pop_back(); 1077 } 1078 while(s.bnode_num<bNodes.size()) { 1079 Node node = nodeFromBNodeId(bNodes.size() - 1); 1080 Parent::notifier(BNode()).erase(node); 1081 Parent::notifier(Node()).erase(node); 1082 bNodes.pop_back(); 1083 } 1084 } 1085 1086 public: 1087 1088 ///Class to make a snapshot of the graph and to restrore to it later. 1089 1090 ///Class to make a snapshot of the graph and to restrore to it later. 1091 /// 1092 ///The newly added nodes and edges can be removed using the 1093 ///restore() function. 1094 /// 1095 ///\note After you restore a state, you cannot restore 1096 ///a later state, in other word you cannot add again the edges deleted 1097 ///by restore() using another one Snapshot instance. 1098 /// 1099 ///\warning If you do not use correctly the snapshot that can cause 1100 ///either broken program, invalid state of the graph, valid but 1101 ///not the restored graph or no change. Because the runtime performance 1102 ///the validity of the snapshot is not stored. 1103 class Snapshot 1104 { 1105 SmartBpUGraph *g; 1106 protected: 1107 friend class SmartBpUGraph; 1108 unsigned int anode_num; 1109 unsigned int bnode_num; 1110 unsigned int edge_num; 1111 public: 1112 ///Default constructor. 1113 1114 ///Default constructor. 1115 ///To actually make a snapshot you must call save(). 1116 /// Snapshot()1117 Snapshot() : g(0) {} 1118 1119 ///Constructor that immediately makes a snapshot 1120 1121 ///This constructor immediately makes a snapshot of the graph. 1122 ///\param _g The graph we make a snapshot of. Snapshot(SmartBpUGraph & _g)1123 Snapshot(SmartBpUGraph &_g) : g(&_g) { 1124 anode_num=g->aNodes.size(); 1125 bnode_num=g->bNodes.size(); 1126 edge_num=g->edges.size(); 1127 } 1128 1129 ///Make a snapshot. 1130 1131 ///Make a snapshot of the graph. 1132 /// 1133 ///This function can be called more than once. In case of a repeated 1134 ///call, the previous snapshot gets lost. 1135 ///\param _g The graph we make the snapshot of. save(SmartBpUGraph & _g)1136 void save(SmartBpUGraph &_g) 1137 { 1138 g=&_g; 1139 anode_num=g->aNodes.size(); 1140 bnode_num=g->bNodes.size(); 1141 edge_num=g->edges.size(); 1142 } 1143 1144 ///Undo the changes until a snapshot. 1145 1146 ///Undo the changes until a snapshot created by save(). 1147 /// 1148 ///\note After you restored a state, you cannot restore 1149 ///a later state, in other word you cannot add again the edges deleted 1150 ///by restore(). restore()1151 void restore() 1152 { 1153 g->restoreSnapshot(*this); 1154 } 1155 }; 1156 }; 1157 1158 1159 /// @} 1160 } //namespace lemon 1161 1162 1163 #endif //LEMON_SMART_GRAPH_H 1164