95 |
95 |
96 /// Maximum edge ID. |
96 /// Maximum edge ID. |
97 ///\sa id(Edge) |
97 ///\sa id(Edge) |
98 int maxEdgeId() const { return edges.size()-1; } |
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 than |
|
106 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
|
107 /// 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 than |
|
115 /// \ref maxEdgeId(). The range of the ID's is not surely continuous |
|
116 /// 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 node |
|
125 /// 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 edge |
|
131 /// with the given id the effect of the function is undefinied. |
|
132 static Edge edgeFromId(int id) { return Edge(id);} |
|
133 |
|
134 Node addNode() { |
100 Node addNode() { |
135 Node n; n.n=nodes.size(); |
101 Node n; n.n=nodes.size(); |
136 nodes.push_back(NodeT()); //FIXME: Hmmm... |
102 nodes.push_back(NodeT()); //FIXME: Hmmm... |
137 return n; |
103 return n; |
138 } |
104 } |
145 nodes[u.n].first_out=nodes[v.n].first_in=e.n; |
111 nodes[u.n].first_out=nodes[v.n].first_in=e.n; |
146 |
112 |
147 return e; |
113 return e; |
148 } |
114 } |
149 |
115 |
150 void clear() { |
116 |
151 edges.clear(); |
117 Node source(Edge e) const { return edges[e.n].source; } |
152 nodes.clear(); |
118 Node target(Edge e) const { return edges[e.n].target; } |
153 } |
119 |
154 |
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 class Node { |
151 class Node { |
157 friend class SmartGraphBase; |
152 friend class SmartGraphBase; |
158 friend class SmartGraph; |
153 friend class SmartGraph; |
159 |
154 |
214 |
209 |
215 void nextIn(Edge& edge) const { |
210 void nextIn(Edge& edge) const { |
216 edge.n = edges[edge.n].next_in; |
211 edge.n = edges[edge.n].next_in; |
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 |
231 typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase; |
216 typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase; |
232 |
217 |
233 /// \ingroup graphs |
218 /// \ingroup graphs |
249 typedef ExtendedSmartGraphBase Parent; |
234 typedef ExtendedSmartGraphBase Parent; |
250 |
235 |
251 class Snapshot; |
236 class Snapshot; |
252 friend class Snapshot; |
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 protected: |
251 protected: |
255 void restoreSnapshot(const Snapshot &s) |
252 void restoreSnapshot(const Snapshot &s) |
256 { |
253 { |
257 while(s.edge_num<edges.size()) { |
254 while(s.edge_num<edges.size()) { |
258 Parent::getNotifier(Edge()).erase(Edge(edges.size()-1)); |
255 Parent::getNotifier(Edge()).erase(Edge(edges.size()-1)); |
266 nodes.pop_back(); |
263 nodes.pop_back(); |
267 } |
264 } |
268 } |
265 } |
269 |
266 |
270 public: |
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 ///Split a node. |
299 ///Split a node. |
273 |
300 |
274 ///This function splits a node. First a new node is added to the graph, |
301 ///This function splits a node. First a new node is added to the graph, |
275 ///then the source of each outgoing edge of \c n is moved to this new node. |
302 ///then the source of each outgoing edge of \c n is moved to this new node. |
282 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s |
309 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s |
283 ///may be invalidated. |
310 ///may be invalidated. |
284 ///\warning This functionality cannot be used together with the Snapshot |
311 ///\warning This functionality cannot be used together with the Snapshot |
285 ///feature. |
312 ///feature. |
286 ///\todo It could be implemented in a bit faster way. |
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 return b; |
321 return b; |
291 } |
322 } |
292 |
|
293 |
323 |
294 ///Class to make a snapshot of the graph and to restrore to it later. |
324 ///Class to make a snapshot of the graph and to restrore to it later. |
295 |
325 |
296 ///Class to make a snapshot of the graph and to restrore to it later. |
326 ///Class to make a snapshot of the graph and to restrore to it later. |
297 /// |
327 /// |
374 /// \sa concept::UGraph. |
404 /// \sa concept::UGraph. |
375 /// |
405 /// |
376 /// \todo Snapshot hasn't been implemented yet. |
406 /// \todo Snapshot hasn't been implemented yet. |
377 /// |
407 /// |
378 class SmartUGraph : public ExtendedSmartUGraphBase { |
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 |
381 |
429 |
382 class SmartBpUGraphBase { |
430 class SmartBpUGraphBase { |
383 public: |
431 public: |