Changeset 2190:dd887831e9c1 in lemon0.x for lemon/smart_graph.h
 Timestamp:
 09/04/06 13:09:13 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2915
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/smart_graph.h
r2162 r2190 44 44 /// 45 45 class SmartGraphBase { 46 47 friend class SmatGraph;48 49 46 protected: 47 50 48 struct NodeT 51 49 { 52 int first_in, first_out;53 NodeT() : first_in(1), first_out(1){}50 int first_in, first_out; 51 NodeT() {} 54 52 }; 55 53 struct EdgeT 56 54 { 57 55 int target, source, next_in, next_out; 58 //FIXME: is this necessary? 59 EdgeT() : next_in(1), next_out(1) {} 56 EdgeT() {} 60 57 }; 61 58 … … 82 79 typedef True EdgeNumTag; 83 80 84 ///Number of nodes.85 81 int nodeNum() const { return nodes.size(); } 86 ///Number of edges.87 82 int edgeNum() const { return edges.size(); } 88 83 89 /// Maximum node ID.90 91 /// Maximum node ID.92 ///\sa id(Node)93 84 int maxNodeId() const { return nodes.size()1; } 94 /// Maximum edge ID.95 96 /// Maximum edge ID.97 ///\sa id(Edge)98 85 int maxEdgeId() const { return edges.size()1; } 99 86 100 87 Node addNode() { 101 Node n; n.n=nodes.size(); 102 nodes.push_back(NodeT()); //FIXME: Hmmm... 103 return n; 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); 104 93 } 105 94 106 95 Edge addEdge(Node u, Node v) { 107 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... 108 edges[e.n].source=u.n; edges[e.n].target=v.n; 109 edges[e.n].next_out=nodes[u.n].first_out; 110 edges[e.n].next_in=nodes[v.n].first_in; 111 nodes[u.n].first_out=nodes[v.n].first_in=e.n; 112 113 return e; 114 } 115 116 117 Node source(Edge e) const { return edges[e.n].source; } 118 Node target(Edge e) const { return edges[e.n].target; } 119 120 /// Node ID. 121 122 /// The ID of a valid Node is a nonnegative integer not greater than 123 /// \ref maxNodeId(). The range of the ID's is not surely continuous 124 /// and the greatest node ID can be actually less then \ref maxNodeId(). 125 /// 126 /// The ID of the \ref INVALID node is 1. 127 ///\return The ID of the node \c v. 128 static int id(Node v) { return v.n; } 129 /// Edge ID. 130 131 /// The ID of a valid Edge is a nonnegative integer not greater than 132 /// \ref maxEdgeId(). The range of the ID's is not surely continuous 133 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). 134 /// 135 /// The ID of the \ref INVALID edge is 1. 136 ///\return The ID of the edge \c e. 137 static int id(Edge e) { return e.n; } 138 139 /// \brief Returns the node from its \c id. 140 /// 141 /// Returns the node from its \c id. If there is not node 142 /// with the given id the effect of the function is undefinied. 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 107 void clear() { 108 edges.clear(); 109 nodes.clear(); 110 } 111 112 Node source(Edge e) const { return Node(edges[e.id].source); } 113 Node target(Edge e) const { return Node(edges[e.id].target); } 114 115 static int id(Node v) { return v.id; } 116 static int id(Edge e) { return e.id; } 117 143 118 static Node nodeFromId(int id) { return Node(id);} 144 145 /// \brief Returns the edge from its \c id.146 ///147 /// Returns the edge from its \c id. If there is not edge148 /// with the given id the effect of the function is undefinied.149 119 static Edge edgeFromId(int id) { return Edge(id);} 150 120 … … 154 124 155 125 protected: 156 int n;157 Node(int nn) {n=nn;}126 int id; 127 explicit Node(int _id) : id(_id) {} 158 128 public: 159 129 Node() {} 160 Node (Invalid) { n=1;}161 bool operator==(const Node i) const {return n==i.n;}162 bool operator!=(const Node i) const {return n!=i.n;}163 bool operator<(const Node i) const {return n<i.n;}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;} 164 134 }; 165 135 … … 170 140 171 141 protected: 172 int n;173 Edge(int nn) {n=nn;}142 int id; 143 explicit Edge(int _id) : id(_id) {} 174 144 public: 175 145 Edge() { } 176 Edge (Invalid) { n=1;}177 bool operator==(const Edge i) const {return n==i.n;}178 bool operator!=(const Edge i) const {return n!=i.n;}179 bool operator<(const Edge i) const {return n<i.n;}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;} 180 150 }; 181 151 182 152 void first(Node& node) const { 183 node. n= nodes.size()  1;153 node.id = nodes.size()  1; 184 154 } 185 155 186 156 static void next(Node& node) { 187 node. n;157 node.id; 188 158 } 189 159 190 160 void first(Edge& edge) const { 191 edge. n= edges.size()  1;161 edge.id = edges.size()  1; 192 162 } 193 163 194 164 static void next(Edge& edge) { 195 edge. n;165 edge.id; 196 166 } 197 167 198 168 void firstOut(Edge& edge, const Node& node) const { 199 edge. n = nodes[node.n].first_out;169 edge.id = nodes[node.id].first_out; 200 170 } 201 171 202 172 void nextOut(Edge& edge) const { 203 edge. n = edges[edge.n].next_out;173 edge.id = edges[edge.id].next_out; 204 174 } 205 175 206 176 void firstIn(Edge& edge, const Node& node) const { 207 edge. n = nodes[node.n].first_in;177 edge.id = nodes[node.id].first_in; 208 178 } 209 179 210 180 void nextIn(Edge& edge) const { 211 edge. n = edges[edge.n].next_in;181 edge.id = edges[edge.id].next_in; 212 182 } 213 183 … … 234 204 typedef ExtendedSmartGraphBase Parent; 235 205 236 class Snapshot;237 friend class Snapshot;238 239 206 private: 207 240 208 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 241 209 242 210 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 243 211 /// 244 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};212 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; 245 213 ///\brief Assignment of SmartGraph to another one is \e not allowed. 246 214 ///Use GraphCopy() instead. … … 249 217 ///Use GraphCopy() instead. 250 218 void operator=(const SmartGraph &) {} 251 protected:252 void restoreSnapshot(const Snapshot &s)253 {254 while(s.edge_num<edges.size()) {255 Parent::getNotifier(Edge()).erase(Edge(edges.size()1));256 nodes[edges.back().target].first_in=edges.back().next_in;257 nodes[edges.back().source].first_out=edges.back().next_out;258 edges.pop_back();259 }260 //nodes.resize(s.nodes_num);261 while(s.node_num<nodes.size()) {262 Parent::getNotifier(Node()).erase(Node(nodes.size()1));263 nodes.pop_back();264 }265 }266 219 267 220 public: … … 288 241 } 289 242 290 /// \e291 292 /// \bug Undocumented293 /// \bug Doesn't destruct the maps.243 ///Clear the graph. 244 245 ///Erase all the nodes and edges from the graph. 246 /// 294 247 void clear() { 295 edges.clear(); 296 nodes.clear(); 248 Parent::clear(); 297 249 } 298 250 … … 315 267 { 316 268 Node b = addNode(); 317 nodes[b. n].first_out=nodes[n.n].first_out;318 nodes[n. n].first_out=1;319 for(int i=nodes[b. n].first_out;i!=1;i++) edges[i].source=b.n;269 nodes[b.id].first_out=nodes[n.id].first_out; 270 nodes[n.id].first_out=1; 271 for(int i=nodes[b.id].first_out;i!=1;i++) edges[i].source=b.id; 320 272 if(connect) addEdge(n,b); 321 273 return b; 322 274 } 275 276 public: 277 278 class Snapshot; 279 280 protected: 281 282 void restoreSnapshot(const Snapshot &s) 283 { 284 while(s.edge_num<edges.size()) { 285 Edge edge = edgeFromId(edges.size()1); 286 Parent::getNotifier(Edge()).erase(edge); 287 nodes[edges.back().source].first_out=edges.back().next_out; 288 nodes[edges.back().target].first_in=edges.back().next_in; 289 edges.pop_back(); 290 } 291 while(s.node_num<nodes.size()) { 292 Node node = nodeFromId(nodes.size()1); 293 Parent::getNotifier(Node()).erase(node); 294 nodes.pop_back(); 295 } 296 } 297 298 public: 323 299 324 300 ///Class to make a snapshot of the graph and to restrore to it later. … … 332 308 ///by restore() using another one Snapshot instance. 333 309 /// 310 ///\warning If you do not use correctly the snapshot that can cause 311 ///either broken program, invalid state of the graph, valid but 312 ///not the restored graph or no change. Because the runtime performance 313 ///the validity of the snapshot is not stored. 334 314 class Snapshot 335 315 { … … 376 356 ///a later state, in other word you cannot add again the edges deleted 377 357 ///by restore(). 378 ///379 ///\todo This function might be called undo().380 381 358 void restore() 382 359 { … … 408 385 class SmartUGraph : public ExtendedSmartUGraphBase { 409 386 private: 387 410 388 ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead. 411 389 … … 413 391 /// 414 392 SmartUGraph(const SmartUGraph &) : ExtendedSmartUGraphBase() {}; 393 415 394 ///\brief Assignment of SmartUGraph to another one is \e not allowed. 416 395 ///Use UGraphCopy() instead. … … 419 398 ///Use UGraphCopy() instead. 420 399 void operator=(const SmartUGraph &) {} 421 public: 400 401 public: 402 403 typedef ExtendedSmartUGraphBase Parent; 404 422 405 /// Constructor 423 406 … … 425 408 /// 426 409 SmartUGraph() {} 410 411 ///Add a new node to the graph. 412 413 /// \return the new node. 414 /// 415 Node addNode() { return Parent::addNode(); } 416 417 ///Add a new undirected edge to the graph. 418 419 ///Add a new undirected edge to the graph with node \c s 420 ///and \c t. 421 ///\return the new undirected edge. 422 UEdge addEdge(const Node& s, const Node& t) { 423 return Parent::addEdge(s, t); 424 } 425 426 ///Clear the graph. 427 428 ///Erase all the nodes and edges from the graph. 429 /// 430 void clear() { 431 Parent::clear(); 432 } 433 434 public: 435 436 class Snapshot; 437 438 protected: 439 440 441 void restoreSnapshot(const Snapshot &s) 442 { 443 while(s.edge_num<edges.size()) { 444 UEdge edge = uEdgeFromId(edges.size()1); 445 Parent::getNotifier(UEdge()).erase(edge); 446 std::vector<Edge> dir; 447 dir.push_back(Parent::direct(edge, true)); 448 dir.push_back(Parent::direct(edge, false)); 449 Parent::getNotifier(Edge()).erase(dir); 450 nodes[edges.back().source].first_out=edges.back().next_out; 451 nodes[edges.back().target].first_in=edges.back().next_in; 452 edges.pop_back(); 453 } 454 while(s.node_num<nodes.size()) { 455 Node node = nodeFromId(nodes.size()1); 456 Parent::getNotifier(Node()).erase(node); 457 nodes.pop_back(); 458 } 459 } 460 461 public: 462 463 ///Class to make a snapshot of the graph and to restrore to it later. 464 465 ///Class to make a snapshot of the graph and to restrore to it later. 466 /// 467 ///The newly added nodes and edges can be removed using the 468 ///restore() function. 469 /// 470 ///\note After you restore a state, you cannot restore 471 ///a later state, in other word you cannot add again the edges deleted 472 ///by restore() using another one Snapshot instance. 473 /// 474 ///\warning If you do not use correctly the snapshot that can cause 475 ///either broken program, invalid state of the graph, valid but 476 ///not the restored graph or no change. Because the runtime performance 477 ///the validity of the snapshot is not stored. 478 class Snapshot 479 { 480 SmartUGraph *g; 481 protected: 482 friend class SmartUGraph; 483 unsigned int node_num; 484 unsigned int edge_num; 485 public: 486 ///Default constructor. 487 488 ///Default constructor. 489 ///To actually make a snapshot you must call save(). 490 /// 491 Snapshot() : g(0) {} 492 ///Constructor that immediately makes a snapshot 493 494 ///This constructor immediately makes a snapshot of the graph. 495 ///\param _g The graph we make a snapshot of. 496 Snapshot(SmartUGraph &_g) :g(&_g) { 497 node_num=g>nodes.size(); 498 edge_num=g>edges.size(); 499 } 500 501 ///Make a snapshot. 502 503 ///Make a snapshot of the graph. 504 /// 505 ///This function can be called more than once. In case of a repeated 506 ///call, the previous snapshot gets lost. 507 ///\param _g The graph we make the snapshot of. 508 void save(SmartUGraph &_g) 509 { 510 g=&_g; 511 node_num=g>nodes.size(); 512 edge_num=g>edges.size(); 513 } 514 515 ///Undo the changes until a snapshot. 516 517 ///Undo the changes until a snapshot created by save(). 518 /// 519 ///\note After you restored a state, you cannot restore 520 ///a later state, in other word you cannot add again the edges deleted 521 ///by restore(). 522 void restore() 523 { 524 g>restoreSnapshot(*this); 525 } 526 }; 427 527 }; 428 528 … … 463 563 int id; 464 564 465 Node(int _id) : id(_id) {}565 explicit Node(int _id) : id(_id) {} 466 566 public: 467 567 Node() {} 468 Node(Invalid) { id = 1;}568 Node(Invalid) : id(1) {} 469 569 bool operator==(const Node i) const {return id==i.id;} 470 570 bool operator!=(const Node i) const {return id!=i.id;} … … 477 577 int id; 478 578 479 UEdge(int _id) { id = _id;}579 UEdge(int _id) : id(_id) {} 480 580 public: 481 581 UEdge() {} 482 UEdge (Invalid) { id = 1;}582 UEdge(Invalid) : id(1) {} 483 583 bool operator==(const UEdge i) const {return id==i.id;} 484 584 bool operator!=(const UEdge i) const {return id!=i.id;} … … 657 757 /// \sa concept::BpUGraph. 658 758 /// 659 class SmartBpUGraph : public ExtendedSmartBpUGraphBase {}; 759 class SmartBpUGraph : public ExtendedSmartBpUGraphBase { 760 private: 761 762 /// \brief SmartBpUGraph is \e not copy constructible. 763 /// 764 ///SmartBpUGraph is \e not copy constructible. 765 SmartBpUGraph(const SmartBpUGraph &) : ExtendedSmartBpUGraphBase() {}; 766 767 /// \brief Assignment of SmartBpUGraph to another one is \e not 768 /// allowed. 769 /// 770 /// Assignment of SmartBpUGraph to another one is \e not allowed. 771 void operator=(const SmartBpUGraph &) {} 772 773 public: 774 775 typedef ExtendedSmartBpUGraphBase Parent; 776 777 ///Constructor 778 779 ///Constructor. 780 /// 781 SmartBpUGraph() : ExtendedSmartBpUGraphBase() {} 782 783 ///Add a new ANode to the graph. 784 785 /// \return the new node. 786 /// 787 Node addANode() { return Parent::addANode(); } 788 789 ///Add a new BNode to the graph. 790 791 /// \return the new node. 792 /// 793 Node addBNode() { return Parent::addBNode(); } 794 795 ///Add a new undirected edge to the graph. 796 797 ///Add a new undirected edge to the graph with node \c s 798 ///and \c t. 799 ///\return the new undirected edge. 800 UEdge addEdge(const Node& s, const Node& t) { 801 return Parent::addEdge(s, t); 802 } 803 804 ///Clear the graph. 805 806 ///Erase all the nodes and edges from the graph. 807 /// 808 void clear() { 809 Parent::clear(); 810 } 811 812 public: 813 814 class Snapshot; 815 816 protected: 817 818 void restoreSnapshot(const Snapshot &s) 819 { 820 while(s.edge_num<edges.size()) { 821 UEdge edge = uEdgeFromId(edges.size()1); 822 Parent::getNotifier(UEdge()).erase(edge); 823 std::vector<Edge> dir; 824 dir.push_back(Parent::direct(edge, true)); 825 dir.push_back(Parent::direct(edge, false)); 826 Parent::getNotifier(Edge()).erase(dir); 827 aNodes[edges.back().aNode >> 1].first=edges.back().next_out; 828 bNodes[edges.back().bNode >> 1].first=edges.back().next_in; 829 edges.pop_back(); 830 } 831 while(s.anode_num<aNodes.size()) { 832 Node node = fromANodeId(aNodes.size()  1); 833 Parent::getNotifier(ANode()).erase(node); 834 Parent::getNotifier(Node()).erase(node); 835 aNodes.pop_back(); 836 } 837 while(s.bnode_num<bNodes.size()) { 838 Node node = fromBNodeId(bNodes.size()  1); 839 Parent::getNotifier(BNode()).erase(node); 840 Parent::getNotifier(Node()).erase(node); 841 bNodes.pop_back(); 842 } 843 } 844 845 public: 846 847 ///Class to make a snapshot of the graph and to restrore to it later. 848 849 ///Class to make a snapshot of the graph and to restrore to it later. 850 /// 851 ///The newly added nodes and edges can be removed using the 852 ///restore() function. 853 /// 854 ///\note After you restore a state, you cannot restore 855 ///a later state, in other word you cannot add again the edges deleted 856 ///by restore() using another one Snapshot instance. 857 /// 858 ///\warning If you do not use correctly the snapshot that can cause 859 ///either broken program, invalid state of the graph, valid but 860 ///not the restored graph or no change. Because the runtime performance 861 ///the validity of the snapshot is not stored. 862 class Snapshot 863 { 864 SmartBpUGraph *g; 865 protected: 866 friend class SmartBpUGraph; 867 unsigned int anode_num; 868 unsigned int bnode_num; 869 unsigned int edge_num; 870 public: 871 ///Default constructor. 872 873 ///Default constructor. 874 ///To actually make a snapshot you must call save(). 875 /// 876 Snapshot() : g(0) {} 877 878 ///Constructor that immediately makes a snapshot 879 880 ///This constructor immediately makes a snapshot of the graph. 881 ///\param _g The graph we make a snapshot of. 882 Snapshot(SmartBpUGraph &_g) : g(&_g) { 883 anode_num=g>aNodes.size(); 884 bnode_num=g>bNodes.size(); 885 edge_num=g>edges.size(); 886 } 887 888 ///Make a snapshot. 889 890 ///Make a snapshot of the graph. 891 /// 892 ///This function can be called more than once. In case of a repeated 893 ///call, the previous snapshot gets lost. 894 ///\param _g The graph we make the snapshot of. 895 void save(SmartBpUGraph &_g) 896 { 897 g=&_g; 898 anode_num=g>aNodes.size(); 899 bnode_num=g>bNodes.size(); 900 edge_num=g>edges.size(); 901 } 902 903 ///Undo the changes until a snapshot. 904 905 ///Undo the changes until a snapshot created by save(). 906 /// 907 ///\note After you restored a state, you cannot restore 908 ///a later state, in other word you cannot add again the edges deleted 909 ///by restore(). 910 void restore() 911 { 912 g>restoreSnapshot(*this); 913 } 914 }; 915 }; 660 916 661 917
Note: See TracChangeset
for help on using the changeset viewer.