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

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/smart_graph.h
r157 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 … … 46 46 protected: 47 47 48 struct NodeT 48 struct NodeT 49 49 { 50 int first_in, first_out; 50 int first_in, first_out; 51 51 NodeT() {} 52 52 }; 53 struct ArcT 53 struct ArcT 54 54 { 55 int target, source, next_in, next_out; 56 ArcT() {} 55 int target, source, next_in, next_out; 56 ArcT() {} 57 57 }; 58 58 59 59 std::vector<NodeT> nodes; 60 60 std::vector<ArcT> arcs; 61 61 62 62 public: 63 63 … … 70 70 71 71 SmartDigraphBase() : nodes(), arcs() { } 72 SmartDigraphBase(const SmartDigraphBase &_g) 72 SmartDigraphBase(const SmartDigraphBase &_g) 73 73 : nodes(_g.nodes), arcs(_g.arcs) { } 74 74 75 75 typedef True NodeNumTag; 76 76 typedef True EdgeNumTag; … … 83 83 84 84 Node addNode() { 85 int n = nodes.size(); 85 int n = nodes.size(); 86 86 nodes.push_back(NodeT()); 87 87 nodes[n].first_in = 1; … … 89 89 return Node(n); 90 90 } 91 91 92 92 Arc addArc(Node u, Node v) { 93 int n = arcs.size(); 93 int n = arcs.size(); 94 94 arcs.push_back(ArcT()); 95 arcs[n].source = u._id; 95 arcs[n].source = u._id; 96 96 arcs[n].target = v._id; 97 97 arcs[n].next_out = nodes[u._id].first_out; … … 116 116 static Arc arcFromId(int id) { return Arc(id);} 117 117 118 bool valid(Node n) const { 119 return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 120 } 121 bool valid(Arc a) const { 122 return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 118 bool valid(Node n) const { 119 return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 120 } 121 bool valid(Arc a) const { 122 return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 123 123 } 124 124 … … 137 137 bool operator<(const Node i) const {return _id < i._id;} 138 138 }; 139 139 140 140 141 141 class Arc { … … 181 181 arc._id = nodes[node._id].first_in; 182 182 } 183 183 184 184 void nextIn(Arc& arc) const { 185 185 arc._id = arcs[arc._id].next_in; … … 223 223 224 224 public: 225 225 226 226 /// Constructor 227 227 228 228 /// Constructor. 229 229 /// 230 230 SmartDigraph() {}; 231 231 232 232 ///Add a new node to the digraph. 233 233 234 234 /// \return the new node. 235 235 /// 236 236 Node addNode() { return Parent::addNode(); } 237 237 238 238 ///Add a new arc to the digraph. 239 239 240 240 ///Add a new arc to the digraph with source node \c s 241 241 ///and target node \c t. 242 242 ///\return the new arc. 243 Arc addArc(const Node& s, const Node& t) { 244 return Parent::addArc(s, t); 243 Arc addArc(const Node& s, const Node& t) { 244 return Parent::addArc(s, t); 245 245 } 246 246 … … 270 270 /// 271 271 /// This function gives back true if the given node is valid, 272 /// ie. it is a real node of the graph. 272 /// ie. it is a real node of the graph. 273 273 /// 274 274 /// \warning A removed node (using Snapshot) could become valid again … … 279 279 /// 280 280 /// This function gives back true if the given arc is valid, 281 /// ie. it is a real arc of the graph. 281 /// ie. it is a real arc of the graph. 282 282 /// 283 283 /// \warning A removed arc (using Snapshot) could become valid again … … 286 286 287 287 ///Clear the digraph. 288 288 289 289 ///Erase all the nodes and arcs from the digraph. 290 290 /// … … 294 294 295 295 ///Split a node. 296 296 297 297 ///This function splits a node. First a new node is added to the digraph, 298 298 ///then the source of each outgoing arc of \c n is moved to this new node. … … 319 319 320 320 public: 321 321 322 322 class Snapshot; 323 323 … … 328 328 while(s.arc_num<arcs.size()) { 329 329 Arc arc = arcFromId(arcs.size()1); 330 331 332 333 330 Parent::notifier(Arc()).erase(arc); 331 nodes[arcs.back().source].first_out=arcs.back().next_out; 332 nodes[arcs.back().target].first_in=arcs.back().next_in; 333 arcs.pop_back(); 334 334 } 335 335 while(s.node_num<nodes.size()) { 336 336 Node node = nodeFromId(nodes.size()1); 337 338 339 } 340 } 337 Parent::notifier(Node()).erase(node); 338 nodes.pop_back(); 339 } 340 } 341 341 342 342 public: … … 356 356 ///not the restored digraph or no change. Because the runtime performance 357 357 ///the validity of the snapshot is not stored. 358 class Snapshot 358 class Snapshot 359 359 { 360 360 SmartDigraph *_graph; … … 365 365 public: 366 366 ///Default constructor. 367 367 368 368 ///Default constructor. 369 369 ///To actually make a snapshot you must call save(). … … 371 371 Snapshot() : _graph(0) {} 372 372 ///Constructor that immediately makes a snapshot 373 373 374 374 ///This constructor immediately makes a snapshot of the digraph. 375 375 ///\param _g The digraph we make a snapshot of. 376 376 Snapshot(SmartDigraph &graph) : _graph(&graph) { 377 378 377 node_num=_graph>nodes.size(); 378 arc_num=_graph>arcs.size(); 379 379 } 380 380 … … 386 386 ///call, the previous snapshot gets lost. 387 387 ///\param _g The digraph we make the snapshot of. 388 void save(SmartDigraph &graph) 388 void save(SmartDigraph &graph) 389 389 { 390 391 392 390 _graph=&graph; 391 node_num=_graph>nodes.size(); 392 arc_num=_graph>arcs.size(); 393 393 } 394 394 395 395 ///Undo the changes until a snapshot. 396 396 397 397 ///Undo the changes until a snapshot created by save(). 398 398 /// … … 402 402 void restore() 403 403 { 404 404 _graph>restoreSnapshot(*this); 405 405 } 406 406 }; … … 415 415 int first_out; 416 416 }; 417 417 418 418 struct ArcT { 419 419 int target; … … 425 425 426 426 int first_free_arc; 427 428 public: 429 427 428 public: 429 430 430 typedef SmartGraphBase Digraph; 431 431 … … 433 433 class Arc; 434 434 class Edge; 435 435 436 436 class Node { 437 437 friend class SmartGraphBase; … … 486 486 : nodes(), arcs() {} 487 487 488 489 int maxNodeId() const { return nodes.size()1; } 488 489 int maxNodeId() const { return nodes.size()1; } 490 490 int maxEdgeId() const { return arcs.size() / 2  1; } 491 491 int maxArcId() const { return arcs.size()1; } … … 505 505 } 506 506 507 void first(Node& node) const { 507 void first(Node& node) const { 508 508 node._id = nodes.size()  1; 509 509 } … … 513 513 } 514 514 515 void first(Arc& arc) const { 515 void first(Arc& arc) const { 516 516 arc._id = arcs.size()  1; 517 517 } … … 521 521 } 522 522 523 void first(Edge& arc) const { 523 void first(Edge& arc) const { 524 524 arc._id = arcs.size() / 2  1; 525 525 } … … 562 562 } else { 563 563 arc._id = 1; 564 d = true; 565 } 566 } 567 564 d = true; 565 } 566 } 567 568 568 static int id(Node v) { return v._id; } 569 569 static int id(Arc e) { return e._id; } … … 574 574 static Edge edgeFromId(int id) { return Edge(id);} 575 575 576 bool valid(Node n) const { 577 return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 578 } 579 bool valid(Arc a) const { 576 bool valid(Node n) const { 577 return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 578 } 579 bool valid(Arc a) const { 580 580 return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 581 581 } 582 bool valid(Edge e) const { 583 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); 584 } 585 586 Node addNode() { 582 bool valid(Edge e) const { 583 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); 584 } 585 586 Node addNode() { 587 587 int n = nodes.size(); 588 588 nodes.push_back(NodeT()); 589 589 nodes[n].first_out = 1; 590 590 591 591 return Node(n); 592 592 } 593 593 594 594 Edge addEdge(Node u, Node v) { 595 595 int n = arcs.size(); 596 596 arcs.push_back(ArcT()); 597 597 arcs.push_back(ArcT()); 598 598 599 599 arcs[n].target = u._id; 600 600 arcs[n  1].target = v._id; … … 603 603 nodes[v._id].first_out = n; 604 604 605 arcs[n  1].next_out = nodes[u._id].first_out; 605 arcs[n  1].next_out = nodes[u._id].first_out; 606 606 nodes[u._id].first_out = (n  1); 607 607 608 608 return Edge(n / 2); 609 609 } 610 610 611 611 void clear() { 612 612 arcs.clear(); … … 626 626 /// that <b> it does support only limited (only stacklike) 627 627 /// node and arc deletions</b>. 628 /// Except from this it conforms to 628 /// Except from this it conforms to 629 629 /// the \ref concepts::Graph "Graph concept". 630 630 /// … … 656 656 657 657 /// Constructor 658 658 659 659 /// Constructor. 660 660 /// … … 662 662 663 663 ///Add a new node to the graph. 664 664 665 665 /// \return the new node. 666 666 /// 667 667 Node addNode() { return Parent::addNode(); } 668 668 669 669 ///Add a new edge to the graph. 670 670 671 671 ///Add a new edge to the graph with node \c s 672 672 ///and \c t. 673 673 ///\return the new edge. 674 Edge addEdge(const Node& s, const Node& t) { 675 return Parent::addEdge(s, t); 674 Edge addEdge(const Node& s, const Node& t) { 675 return Parent::addEdge(s, t); 676 676 } 677 677 … … 679 679 /// 680 680 /// This function gives back true if the given node is valid, 681 /// ie. it is a real node of the graph. 681 /// ie. it is a real node of the graph. 682 682 /// 683 683 /// \warning A removed node (using Snapshot) could become valid again … … 688 688 /// 689 689 /// This function gives back true if the given arc is valid, 690 /// ie. it is a real arc of the graph. 690 /// ie. it is a real arc of the graph. 691 691 /// 692 692 /// \warning A removed arc (using Snapshot) could become valid again … … 697 697 /// 698 698 /// This function gives back true if the given edge is valid, 699 /// ie. it is a real edge of the graph. 699 /// ie. it is a real edge of the graph. 700 700 /// 701 701 /// \warning A removed edge (using Snapshot) could become valid again … … 704 704 705 705 ///Clear the graph. 706 706 707 707 ///Erase all the nodes and edges from the graph. 708 708 /// … … 712 712 713 713 public: 714 714 715 715 class Snapshot; 716 716 … … 729 729 int n=arcs.size()1; 730 730 Edge arc=edgeFromId(n/2); 731 731 Parent::notifier(Edge()).erase(arc); 732 732 std::vector<Arc> dir; 733 733 dir.push_back(arcFromId(n)); 734 734 dir.push_back(arcFromId(n1)); 735 736 737 738 739 735 Parent::notifier(Arc()).erase(dir); 736 nodes[arcs[n].target].first_out=arcs[n].next_out; 737 nodes[arcs[n1].target].first_out=arcs[n1].next_out; 738 arcs.pop_back(); 739 arcs.pop_back(); 740 740 } 741 741 while(s.node_num<nodes.size()) { 742 742 int n=nodes.size()1; 743 743 Node node = nodeFromId(n); 744 745 746 } 747 } 744 Parent::notifier(Node()).erase(node); 745 nodes.pop_back(); 746 } 747 } 748 748 749 749 public: … … 764 764 ///not the restored digraph or no change. Because the runtime performance 765 765 ///the validity of the snapshot is not stored. 766 class Snapshot 766 class Snapshot 767 767 { 768 768 SmartGraph *_graph; … … 773 773 public: 774 774 ///Default constructor. 775 775 776 776 ///Default constructor. 777 777 ///To actually make a snapshot you must call save(). … … 779 779 Snapshot() : _graph(0) {} 780 780 ///Constructor that immediately makes a snapshot 781 781 782 782 ///This constructor immediately makes a snapshot of the digraph. 783 783 ///\param g The digraph we make a snapshot of. … … 793 793 ///call, the previous snapshot gets lost. 794 794 ///\param g The digraph we make the snapshot of. 795 void save(SmartGraph &graph) 795 void save(SmartGraph &graph) 796 796 { 797 797 graph.saveSnapshot(*this); … … 799 799 800 800 ///Undo the changes until a snapshot. 801 801 802 802 ///Undo the changes until a snapshot created by save(). 803 803 /// … … 811 811 }; 812 812 }; 813 813 814 814 } //namespace lemon 815 815
Note: See TracChangeset
for help on using the changeset viewer.