Changeset 2128:509846825ddf in lemon-0.x for lemon/smart_graph.h
- Timestamp:
- 07/11/06 18:09:49 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2841
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/smart_graph.h
r2123 r2128 98 98 int maxEdgeId() const { return edges.size()-1; } 99 99 100 Node source(Edge e) const { return edges[e.n].source; }101 Node target(Edge e) const { return edges[e.n].target; }102 103 /// Node ID.104 105 /// The ID of a valid Node is a nonnegative integer not greater than106 /// \ref maxNodeId(). The range of the ID's is not surely continuous107 /// and the greatest node ID can be actually less then \ref maxNodeId().108 ///109 /// The ID of the \ref INVALID node is -1.110 ///\return The ID of the node \c v.111 static int id(Node v) { return v.n; }112 /// Edge ID.113 114 /// The ID of a valid Edge is a nonnegative integer not greater than115 /// \ref maxEdgeId(). The range of the ID's is not surely continuous116 /// and the greatest edge ID can be actually less then \ref maxEdgeId().117 ///118 /// The ID of the \ref INVALID edge is -1.119 ///\return The ID of the edge \c e.120 static int id(Edge e) { return e.n; }121 122 /// \brief Returns the node from its \c id.123 ///124 /// Returns the node from its \c id. If there is not node125 /// with the given id the effect of the function is undefinied.126 static Node nodeFromId(int id) { return Node(id);}127 128 /// \brief Returns the edge from its \c id.129 ///130 /// Returns the edge from its \c id. If there is not edge131 /// with the given id the effect of the function is undefinied.132 static Edge edgeFromId(int id) { return Edge(id);}133 134 100 Node addNode() { 135 101 Node n; n.n=nodes.size(); … … 148 114 } 149 115 150 void clear() { 151 edges.clear(); 152 nodes.clear(); 153 } 154 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. 143 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 edge 148 /// with the given id the effect of the function is undefinied. 149 static Edge edgeFromId(int id) { return Edge(id);} 155 150 156 151 class Node { … … 217 212 } 218 213 219 Node _split(Node n, bool connect = true)220 {221 Node b = addNode();222 nodes[b.n].first_out=nodes[n.n].first_out;223 nodes[n.n].first_out=-1;224 for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;225 if(connect) addEdge(n,b);226 return b;227 }228 229 214 }; 230 215 … … 252 237 friend class Snapshot; 253 238 239 private: 240 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 241 242 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. 243 /// 244 SmartGraph(const SmartGraph &) :ExtendedSmartGraphBase() {}; 245 ///\brief Assignment of SmartGraph to another is \e not allowed. 246 ///Use GraphCopy() instead. 247 248 ///Assignment of SmartGraph to another is \e not allowed. 249 ///Use GraphCopy() instead. 250 void operator=(const SmartGraph &) {} 254 251 protected: 255 252 void restoreSnapshot(const Snapshot &s) … … 269 266 270 267 public: 268 269 /// Constructor 270 271 /// Constructor. 272 /// 273 SmartGraph() {}; 274 275 ///Add a new node to the graph. 276 277 /// \return the new node. 278 /// 279 Node addNode() { return Parent::addNode(); } 280 281 ///Add a new edge to the graph. 282 283 ///Add a new edge to the graph with source node \c s 284 ///and target node \c t. 285 ///\return the new edge. 286 Edge addEdge(const Node& s, const Node& t) { 287 return Parent::addEdge(s, t); 288 } 289 290 ///\e 291 292 ///\bug Undocumented 293 ///\bug Doesn't destruct the maps. 294 void clear() { 295 edges.clear(); 296 nodes.clear(); 297 } 271 298 272 299 ///Split a node. … … 285 312 ///feature. 286 313 ///\todo It could be implemented in a bit faster way. 287 Node split(Node n, bool connect = true) 314 Node split(Node n, bool connect = true) 288 315 { 289 Node b = _split(n,connect); 316 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; 320 if(connect) addEdge(n,b); 290 321 return b; 291 322 } 292 293 323 294 324 ///Class to make a snapshot of the graph and to restrore to it later. … … 377 407 /// 378 408 class SmartUGraph : public ExtendedSmartUGraphBase { 409 private: 410 ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead. 411 412 ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead. 413 /// 414 SmartUGraph(const SmartUGraph &) : ExtendedSmartUGraphBase() {}; 415 ///\brief Assignment of SmartUGraph to another is \e not allowed. 416 ///Use UGraphCopy() instead. 417 418 ///Assignment of SmartUGraph to another is \e not allowed. 419 ///Use UGraphCopy() instead. 420 void operator=(const SmartUGraph &) {} 421 public: 422 /// Constructor 423 424 /// Constructor. 425 /// 426 SmartUGraph() {} 379 427 }; 380 428
Note: See TracChangeset
for help on using the changeset viewer.