291 |
291 |
292 }; |
292 }; |
293 |
293 |
294 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase; |
294 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase; |
295 |
295 |
296 /// \addtogroup digraphs |
296 /// \addtogroup graphs |
297 /// @{ |
297 /// @{ |
298 |
298 |
299 ///A list digraph class. |
299 ///A general directed graph structure. |
300 |
300 |
301 ///This is a simple and fast digraph implementation. |
301 ///\ref ListDigraph is a simple and fast <em>directed graph</em> |
|
302 ///implementation based on static linked lists that are stored in |
|
303 ///\c std::vector structures. |
302 /// |
304 /// |
303 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it |
305 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it |
304 ///also provides several additional useful extra functionalities. |
306 ///also provides several useful additional functionalities. |
305 ///The most of the member functions and nested classes are |
307 ///Most of the member functions and nested classes are documented |
306 ///documented only in the concept class. |
308 ///only in the concept class. |
307 /// |
309 /// |
308 ///An important extra feature of this digraph implementation is that |
310 ///An important extra feature of this digraph implementation is that |
309 ///its maps are real \ref concepts::ReferenceMap "reference map"s. |
311 ///its maps are real \ref concepts::ReferenceMap "reference map"s. |
310 /// |
312 /// |
311 ///\sa concepts::Digraph. |
313 ///\sa concepts::Digraph |
312 |
314 |
313 class ListDigraph : public ExtendedListDigraphBase { |
315 class ListDigraph : public ExtendedListDigraphBase { |
314 private: |
316 private: |
315 ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead. |
317 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. |
316 |
318 |
317 ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead. |
319 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. |
318 /// |
320 /// |
319 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {}; |
321 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {}; |
320 ///\brief Assignment of ListDigraph to another one is \e not allowed. |
322 ///\brief Assignment of ListDigraph to another one is \e not allowed. |
321 ///Use DigraphCopy() instead. |
323 ///Use copyDigraph() instead. |
322 |
324 |
323 ///Assignment of ListDigraph to another one is \e not allowed. |
325 ///Assignment of ListDigraph to another one is \e not allowed. |
324 ///Use DigraphCopy() instead. |
326 ///Use copyDigraph() instead. |
325 void operator=(const ListDigraph &) {} |
327 void operator=(const ListDigraph &) {} |
326 public: |
328 public: |
327 |
329 |
328 typedef ExtendedListDigraphBase Parent; |
330 typedef ExtendedListDigraphBase Parent; |
329 |
331 |
346 ///\return the new arc. |
348 ///\return the new arc. |
347 Arc addArc(const Node& s, const Node& t) { |
349 Arc addArc(const Node& s, const Node& t) { |
348 return Parent::addArc(s, t); |
350 return Parent::addArc(s, t); |
349 } |
351 } |
350 |
352 |
351 /// Changes the target of \c e to \c n |
353 /// Change the target of \c e to \c n |
352 |
354 |
353 /// Changes the target of \c e to \c n |
355 /// Change the target of \c e to \c n |
354 /// |
356 /// |
355 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing |
357 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing |
356 ///the changed arc remain valid. However <tt>InArcIt</tt>s are |
358 ///the changed arc remain valid. However <tt>InArcIt</tt>s are |
357 ///invalidated. |
359 ///invalidated. |
|
360 /// |
358 ///\warning This functionality cannot be used together with the Snapshot |
361 ///\warning This functionality cannot be used together with the Snapshot |
359 ///feature. |
362 ///feature. |
360 void changeTarget(Arc e, Node n) { |
363 void changeTarget(Arc e, Node n) { |
361 Parent::changeTarget(e,n); |
364 Parent::changeTarget(e,n); |
362 } |
365 } |
363 /// Changes the source of \c e to \c n |
366 /// Change the source of \c e to \c n |
364 |
367 |
365 /// Changes the source of \c e to \c n |
368 /// Change the source of \c e to \c n |
366 /// |
369 /// |
367 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing |
370 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing |
368 ///the changed arc remain valid. However <tt>OutArcIt</tt>s are |
371 ///the changed arc remain valid. However <tt>OutArcIt</tt>s are |
369 ///invalidated. |
372 ///invalidated. |
|
373 /// |
370 ///\warning This functionality cannot be used together with the Snapshot |
374 ///\warning This functionality cannot be used together with the Snapshot |
371 ///feature. |
375 ///feature. |
372 void changeSource(Arc e, Node n) { |
376 void changeSource(Arc e, Node n) { |
373 Parent::changeSource(e,n); |
377 Parent::changeSource(e,n); |
374 } |
378 } |
376 /// Invert the direction of an arc. |
380 /// Invert the direction of an arc. |
377 |
381 |
378 ///\note The <tt>ArcIt</tt>s referencing the changed arc remain |
382 ///\note The <tt>ArcIt</tt>s referencing the changed arc remain |
379 ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are |
383 ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are |
380 ///invalidated. |
384 ///invalidated. |
|
385 /// |
381 ///\warning This functionality cannot be used together with the Snapshot |
386 ///\warning This functionality cannot be used together with the Snapshot |
382 ///feature. |
387 ///feature. |
383 void reverseArc(Arc e) { |
388 void reverseArc(Arc e) { |
384 Node t=target(e); |
389 Node t=target(e); |
385 changeTarget(e,source(e)); |
390 changeTarget(e,source(e)); |
386 changeSource(e,t); |
391 changeSource(e,t); |
387 } |
392 } |
388 |
393 |
389 /// Using this it is possible to avoid the superfluous memory |
394 /// Reserve memory for nodes. |
|
395 |
|
396 /// Using this function it is possible to avoid the superfluous memory |
390 /// allocation: if you know that the digraph you want to build will |
397 /// allocation: if you know that the digraph you want to build will |
391 /// be very large (e.g. it will contain millions of nodes and/or arcs) |
398 /// be very large (e.g. it will contain millions of nodes and/or arcs) |
392 /// then it is worth reserving space for this amount before starting |
399 /// then it is worth reserving space for this amount before starting |
393 /// to build the digraph. |
400 /// to build the digraph. |
394 /// \sa reserveArc |
401 /// \sa reserveArc |
395 void reserveNode(int n) { nodes.reserve(n); }; |
402 void reserveNode(int n) { nodes.reserve(n); }; |
396 |
403 |
397 /// \brief Using this it is possible to avoid the superfluous memory |
404 /// Reserve memory for arcs. |
398 /// allocation. |
405 |
399 |
406 /// Using this function it is possible to avoid the superfluous memory |
400 /// Using this it is possible to avoid the superfluous memory |
|
401 /// allocation: if you know that the digraph you want to build will |
407 /// allocation: if you know that the digraph you want to build will |
402 /// be very large (e.g. it will contain millions of nodes and/or arcs) |
408 /// be very large (e.g. it will contain millions of nodes and/or arcs) |
403 /// then it is worth reserving space for this amount before starting |
409 /// then it is worth reserving space for this amount before starting |
404 /// to build the digraph. |
410 /// to build the digraph. |
405 /// \sa reserveNode |
411 /// \sa reserveNode |
406 void reserveArc(int m) { arcs.reserve(m); }; |
412 void reserveArc(int m) { arcs.reserve(m); }; |
407 |
413 |
408 ///Contract two nodes. |
414 ///Contract two nodes. |
409 |
415 |
410 ///This function contracts two nodes. |
416 ///This function contracts two nodes. |
411 /// |
|
412 ///Node \p b will be removed but instead of deleting |
417 ///Node \p b will be removed but instead of deleting |
413 ///incident arcs, they will be joined to \p a. |
418 ///incident arcs, they will be joined to \p a. |
414 ///The last parameter \p r controls whether to remove loops. \c true |
419 ///The last parameter \p r controls whether to remove loops. \c true |
415 ///means that loops will be removed. |
420 ///means that loops will be removed. |
416 /// |
421 /// |
417 ///\note The <tt>ArcIt</tt>s |
422 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain |
418 ///referencing a moved arc remain |
|
419 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s |
423 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s |
420 ///may be invalidated. |
424 ///may be invalidated. |
|
425 /// |
421 ///\warning This functionality cannot be used together with the Snapshot |
426 ///\warning This functionality cannot be used together with the Snapshot |
422 ///feature. |
427 ///feature. |
423 void contract(Node a, Node b, bool r = true) |
428 void contract(Node a, Node b, bool r = true) |
424 { |
429 { |
425 for(OutArcIt e(*this,b);e!=INVALID;) { |
430 for(OutArcIt e(*this,b);e!=INVALID;) { |
1087 nodes[n.id].first_out = ((2 * e.id) | 1); |
1095 nodes[n.id].first_out = ((2 * e.id) | 1); |
1088 } |
1096 } |
1089 |
1097 |
1090 }; |
1098 }; |
1091 |
1099 |
1092 // typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> > |
|
1093 // ExtendedListGraphBase; |
|
1094 |
|
1095 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase; |
1100 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase; |
1096 |
1101 |
1097 |
1102 |
1098 |
1103 /// \addtogroup graphs |
1099 /// \addtogroup digraphs |
|
1100 /// @{ |
1104 /// @{ |
1101 |
1105 |
1102 ///An undirected list digraph class. |
1106 ///A general undirected graph structure. |
1103 |
1107 |
1104 ///This is a simple and fast undirected digraph implementation. |
1108 ///\ref ListGraph is a simple and fast <em>undirected graph</em> |
|
1109 ///implementation based on static linked lists that are stored in |
|
1110 ///\c std::vector structures. |
1105 /// |
1111 /// |
1106 ///An important extra feature of this digraph implementation is that |
1112 ///It conforms to the \ref concepts::Graph "Graph concept" and it |
|
1113 ///also provides several useful additional functionalities. |
|
1114 ///Most of the member functions and nested classes are documented |
|
1115 ///only in the concept class. |
|
1116 /// |
|
1117 ///An important extra feature of this graph implementation is that |
1107 ///its maps are real \ref concepts::ReferenceMap "reference map"s. |
1118 ///its maps are real \ref concepts::ReferenceMap "reference map"s. |
1108 /// |
1119 /// |
1109 ///It conforms to the |
1120 ///\sa concepts::Graph |
1110 ///\ref concepts::Graph "Graph concept". |
1121 |
1111 /// |
|
1112 ///\sa concepts::Graph. |
|
1113 /// |
|
1114 class ListGraph : public ExtendedListGraphBase { |
1122 class ListGraph : public ExtendedListGraphBase { |
1115 private: |
1123 private: |
1116 ///ListGraph is \e not copy constructible. Use GraphCopy() instead. |
1124 ///ListGraph is \e not copy constructible. Use copyGraph() instead. |
1117 |
1125 |
1118 ///ListGraph is \e not copy constructible. Use GraphCopy() instead. |
1126 ///ListGraph is \e not copy constructible. Use copyGraph() instead. |
1119 /// |
1127 /// |
1120 ListGraph(const ListGraph &) :ExtendedListGraphBase() {}; |
1128 ListGraph(const ListGraph &) :ExtendedListGraphBase() {}; |
1121 ///\brief Assignment of ListGraph to another one is \e not allowed. |
1129 ///\brief Assignment of ListGraph to another one is \e not allowed. |
1122 ///Use GraphCopy() instead. |
1130 ///Use copyGraph() instead. |
1123 |
1131 |
1124 ///Assignment of ListGraph to another one is \e not allowed. |
1132 ///Assignment of ListGraph to another one is \e not allowed. |
1125 ///Use GraphCopy() instead. |
1133 ///Use copyGraph() instead. |
1126 void operator=(const ListGraph &) {} |
1134 void operator=(const ListGraph &) {} |
1127 public: |
1135 public: |
1128 /// Constructor |
1136 /// Constructor |
1129 |
1137 |
1130 /// Constructor. |
1138 /// Constructor. |
1131 /// |
1139 /// |
1132 ListGraph() {} |
1140 ListGraph() {} |
1133 |
1141 |
1134 typedef ExtendedListGraphBase Parent; |
1142 typedef ExtendedListGraphBase Parent; |
1135 |
1143 |
1136 typedef Parent::OutArcIt IncArcIt; |
1144 typedef Parent::OutArcIt IncEdgeIt; |
1137 |
1145 |
1138 /// \brief Add a new node to the digraph. |
1146 /// \brief Add a new node to the graph. |
1139 /// |
1147 /// |
|
1148 /// Add a new node to the graph. |
1140 /// \return the new node. |
1149 /// \return the new node. |
1141 /// |
|
1142 Node addNode() { return Parent::addNode(); } |
1150 Node addNode() { return Parent::addNode(); } |
1143 |
1151 |
1144 /// \brief Add a new edge to the digraph. |
1152 /// \brief Add a new edge to the graph. |
1145 /// |
1153 /// |
1146 /// Add a new arc to the digraph with source node \c s |
1154 /// Add a new edge to the graph with source node \c s |
1147 /// and target node \c t. |
1155 /// and target node \c t. |
1148 /// \return the new edge. |
1156 /// \return the new edge. |
1149 Edge addEdge(const Node& s, const Node& t) { |
1157 Edge addEdge(const Node& s, const Node& t) { |
1150 return Parent::addEdge(s, t); |
1158 return Parent::addEdge(s, t); |
1151 } |
1159 } |
1152 /// \brief Changes the source of \c e to \c n |
1160 /// \brief Change the source of \c e to \c n |
1153 /// |
1161 /// |
1154 /// Changes the source of \c e to \c n |
1162 /// This function changes the source of \c e to \c n. |
1155 /// |
1163 /// |
1156 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s |
1164 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s |
1157 ///referencing the changed arc remain |
1165 ///referencing the changed arc remain |
1158 ///valid. However <tt>OutArcIt</tt>s are invalidated. |
1166 ///valid. However <tt>OutArcIt</tt>s are invalidated. |
|
1167 /// |
|
1168 ///\warning This functionality cannot be used together with the |
|
1169 ///Snapshot feature. |
1159 void changeSource(Edge e, Node n) { |
1170 void changeSource(Edge e, Node n) { |
1160 Parent::changeSource(e,n); |
1171 Parent::changeSource(e,n); |
1161 } |
1172 } |
1162 /// \brief Changes the target of \c e to \c n |
1173 /// \brief Change the target of \c e to \c n |
1163 /// |
1174 /// |
1164 /// Changes the target of \c e to \c n |
1175 /// This function changes the target of \c e to \c n. |
1165 /// |
1176 /// |
1166 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain |
1177 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain |
1167 /// valid. However the other iterators may be invalidated. |
1178 /// valid. However the other iterators may be invalidated. |
|
1179 /// |
|
1180 ///\warning This functionality cannot be used together with the |
|
1181 ///Snapshot feature. |
1168 void changeTarget(Edge e, Node n) { |
1182 void changeTarget(Edge e, Node n) { |
1169 Parent::changeTarget(e,n); |
1183 Parent::changeTarget(e,n); |
1170 } |
1184 } |
1171 /// \brief Changes the source of \c e to \c n |
1185 /// \brief Change the source of \c e to \c n |
1172 /// |
1186 /// |
1173 /// Changes the source of \c e to \c n. It changes the proper |
1187 /// This function changes the source of \c e to \c n. |
1174 /// node of the represented edge. |
1188 /// It also changes the proper node of the represented edge. |
1175 /// |
1189 /// |
1176 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s |
1190 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s |
1177 ///referencing the changed arc remain |
1191 ///referencing the changed arc remain |
1178 ///valid. However <tt>OutArcIt</tt>s are invalidated. |
1192 ///valid. However <tt>OutArcIt</tt>s are invalidated. |
|
1193 /// |
|
1194 ///\warning This functionality cannot be used together with the |
|
1195 ///Snapshot feature. |
1179 void changeSource(Arc e, Node n) { |
1196 void changeSource(Arc e, Node n) { |
1180 if (Parent::direction(e)) { |
1197 if (Parent::direction(e)) { |
1181 Parent::changeSource(e,n); |
1198 Parent::changeSource(e,n); |
1182 } else { |
1199 } else { |
1183 Parent::changeTarget(e,n); |
1200 Parent::changeTarget(e,n); |
1184 } |
1201 } |
1185 } |
1202 } |
1186 /// \brief Changes the target of \c e to \c n |
1203 /// \brief Change the target of \c e to \c n |
1187 /// |
1204 /// |
1188 /// Changes the target of \c e to \c n. It changes the proper |
1205 /// This function changes the target of \c e to \c n. |
1189 /// node of the represented edge. |
1206 /// It also changes the proper node of the represented edge. |
1190 /// |
1207 /// |
1191 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s |
1208 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s |
1192 ///referencing the changed arc remain |
1209 ///referencing the changed arc remain |
1193 ///valid. However <tt>InArcIt</tt>s are invalidated. |
1210 ///valid. However <tt>InArcIt</tt>s are invalidated. |
|
1211 /// |
|
1212 ///\warning This functionality cannot be used together with the |
|
1213 ///Snapshot feature. |
1194 void changeTarget(Arc e, Node n) { |
1214 void changeTarget(Arc e, Node n) { |
1195 if (Parent::direction(e)) { |
1215 if (Parent::direction(e)) { |
1196 Parent::changeTarget(e,n); |
1216 Parent::changeTarget(e,n); |
1197 } else { |
1217 } else { |
1198 Parent::changeSource(e,n); |
1218 Parent::changeSource(e,n); |
1199 } |
1219 } |
1200 } |
1220 } |
1201 /// \brief Contract two nodes. |
1221 /// \brief Contract two nodes. |
1202 /// |
1222 /// |
1203 /// This function contracts two nodes. |
1223 /// This function contracts two nodes. |
1204 /// |
|
1205 /// Node \p b will be removed but instead of deleting |
1224 /// Node \p b will be removed but instead of deleting |
1206 /// its neighboring arcs, they will be joined to \p a. |
1225 /// its neighboring arcs, they will be joined to \p a. |
1207 /// The last parameter \p r controls whether to remove loops. \c true |
1226 /// The last parameter \p r controls whether to remove loops. \c true |
1208 /// means that loops will be removed. |
1227 /// means that loops will be removed. |
1209 /// |
1228 /// |
1210 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain |
1229 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain |
1211 /// valid. |
1230 /// valid. |
|
1231 /// |
|
1232 ///\warning This functionality cannot be used together with the |
|
1233 ///Snapshot feature. |
1212 void contract(Node a, Node b, bool r = true) { |
1234 void contract(Node a, Node b, bool r = true) { |
1213 for(IncArcIt e(*this, b); e!=INVALID;) { |
1235 for(IncEdgeIt e(*this, b); e!=INVALID;) { |
1214 IncArcIt f = e; ++f; |
1236 IncEdgeIt f = e; ++f; |
1215 if (r && runningNode(e) == a) { |
1237 if (r && runningNode(e) == a) { |
1216 erase(e); |
1238 erase(e); |
1217 } else if (source(e) == b) { |
1239 } else if (source(e) == b) { |
1218 changeSource(e, a); |
1240 changeSource(e, a); |
1219 } else { |
1241 } else { |
1301 using EdgeNotifier::ObserverBase::detach; |
1323 using EdgeNotifier::ObserverBase::detach; |
1302 using EdgeNotifier::ObserverBase::attached; |
1324 using EdgeNotifier::ObserverBase::attached; |
1303 |
1325 |
1304 protected: |
1326 protected: |
1305 |
1327 |
1306 virtual void add(const Edge& arc) { |
1328 virtual void add(const Edge& edge) { |
1307 snapshot.addEdge(arc); |
1329 snapshot.addEdge(edge); |
1308 } |
1330 } |
1309 virtual void add(const std::vector<Edge>& arcs) { |
1331 virtual void add(const std::vector<Edge>& edges) { |
1310 for (int i = arcs.size() - 1; i >= 0; ++i) { |
1332 for (int i = edges.size() - 1; i >= 0; ++i) { |
1311 snapshot.addEdge(arcs[i]); |
1333 snapshot.addEdge(edges[i]); |
1312 } |
1334 } |
1313 } |
1335 } |
1314 virtual void erase(const Edge& arc) { |
1336 virtual void erase(const Edge& edge) { |
1315 snapshot.eraseEdge(arc); |
1337 snapshot.eraseEdge(edge); |
1316 } |
1338 } |
1317 virtual void erase(const std::vector<Edge>& arcs) { |
1339 virtual void erase(const std::vector<Edge>& edges) { |
1318 for (int i = 0; i < int(arcs.size()); ++i) { |
1340 for (int i = 0; i < int(edges.size()); ++i) { |
1319 snapshot.eraseEdge(arcs[i]); |
1341 snapshot.eraseEdge(edges[i]); |
1320 } |
1342 } |
1321 } |
1343 } |
1322 virtual void build() { |
1344 virtual void build() { |
1323 Edge arc; |
1345 Edge edge; |
1324 std::vector<Edge> arcs; |
1346 std::vector<Edge> edges; |
1325 for (notifier()->first(arc); arc != INVALID; |
1347 for (notifier()->first(edge); edge != INVALID; |
1326 notifier()->next(arc)) { |
1348 notifier()->next(edge)) { |
1327 arcs.push_back(arc); |
1349 edges.push_back(edge); |
1328 } |
1350 } |
1329 for (int i = arcs.size() - 1; i >= 0; --i) { |
1351 for (int i = edges.size() - 1; i >= 0; --i) { |
1330 snapshot.addEdge(arcs[i]); |
1352 snapshot.addEdge(edges[i]); |
1331 } |
1353 } |
1332 } |
1354 } |
1333 virtual void clear() { |
1355 virtual void clear() { |
1334 Edge arc; |
1356 Edge edge; |
1335 for (notifier()->first(arc); arc != INVALID; |
1357 for (notifier()->first(edge); edge != INVALID; |
1336 notifier()->next(arc)) { |
1358 notifier()->next(edge)) { |
1337 snapshot.eraseEdge(arc); |
1359 snapshot.eraseEdge(edge); |
1338 } |
1360 } |
1339 } |
1361 } |
1340 |
1362 |
1341 Snapshot& snapshot; |
1363 Snapshot& snapshot; |
1342 }; |
1364 }; |
1343 |
1365 |
1344 ListGraph *digraph; |
1366 ListGraph *graph; |
1345 |
1367 |
1346 NodeObserverProxy node_observer_proxy; |
1368 NodeObserverProxy node_observer_proxy; |
1347 EdgeObserverProxy arc_observer_proxy; |
1369 EdgeObserverProxy edge_observer_proxy; |
1348 |
1370 |
1349 std::list<Node> added_nodes; |
1371 std::list<Node> added_nodes; |
1350 std::list<Edge> added_arcs; |
1372 std::list<Edge> added_edges; |
1351 |
1373 |
1352 |
1374 |
1353 void addNode(const Node& node) { |
1375 void addNode(const Node& node) { |
1354 added_nodes.push_front(node); |
1376 added_nodes.push_front(node); |
1355 } |
1377 } |
1356 void eraseNode(const Node& node) { |
1378 void eraseNode(const Node& node) { |
1357 std::list<Node>::iterator it = |
1379 std::list<Node>::iterator it = |
1358 std::find(added_nodes.begin(), added_nodes.end(), node); |
1380 std::find(added_nodes.begin(), added_nodes.end(), node); |
1359 if (it == added_nodes.end()) { |
1381 if (it == added_nodes.end()) { |
1360 clear(); |
1382 clear(); |
1361 arc_observer_proxy.detach(); |
1383 edge_observer_proxy.detach(); |
1362 throw NodeNotifier::ImmediateDetach(); |
1384 throw NodeNotifier::ImmediateDetach(); |
1363 } else { |
1385 } else { |
1364 added_nodes.erase(it); |
1386 added_nodes.erase(it); |
1365 } |
1387 } |
1366 } |
1388 } |
1367 |
1389 |
1368 void addEdge(const Edge& arc) { |
1390 void addEdge(const Edge& edge) { |
1369 added_arcs.push_front(arc); |
1391 added_edges.push_front(edge); |
1370 } |
1392 } |
1371 void eraseEdge(const Edge& arc) { |
1393 void eraseEdge(const Edge& edge) { |
1372 std::list<Edge>::iterator it = |
1394 std::list<Edge>::iterator it = |
1373 std::find(added_arcs.begin(), added_arcs.end(), arc); |
1395 std::find(added_edges.begin(), added_edges.end(), edge); |
1374 if (it == added_arcs.end()) { |
1396 if (it == added_edges.end()) { |
1375 clear(); |
1397 clear(); |
1376 node_observer_proxy.detach(); |
1398 node_observer_proxy.detach(); |
1377 throw EdgeNotifier::ImmediateDetach(); |
1399 throw EdgeNotifier::ImmediateDetach(); |
1378 } else { |
1400 } else { |
1379 added_arcs.erase(it); |
1401 added_edges.erase(it); |
1380 } |
1402 } |
1381 } |
1403 } |
1382 |
1404 |
1383 void attach(ListGraph &_digraph) { |
1405 void attach(ListGraph &_graph) { |
1384 digraph = &_digraph; |
1406 graph = &_graph; |
1385 node_observer_proxy.attach(digraph->notifier(Node())); |
1407 node_observer_proxy.attach(graph->notifier(Node())); |
1386 arc_observer_proxy.attach(digraph->notifier(Edge())); |
1408 edge_observer_proxy.attach(graph->notifier(Edge())); |
1387 } |
1409 } |
1388 |
1410 |
1389 void detach() { |
1411 void detach() { |
1390 node_observer_proxy.detach(); |
1412 node_observer_proxy.detach(); |
1391 arc_observer_proxy.detach(); |
1413 edge_observer_proxy.detach(); |
1392 } |
1414 } |
1393 |
1415 |
1394 bool attached() const { |
1416 bool attached() const { |
1395 return node_observer_proxy.attached(); |
1417 return node_observer_proxy.attached(); |
1396 } |
1418 } |
1397 |
1419 |
1398 void clear() { |
1420 void clear() { |
1399 added_nodes.clear(); |
1421 added_nodes.clear(); |
1400 added_arcs.clear(); |
1422 added_edges.clear(); |
1401 } |
1423 } |
1402 |
1424 |
1403 public: |
1425 public: |
1404 |
1426 |
1405 /// \brief Default constructor. |
1427 /// \brief Default constructor. |
1406 /// |
1428 /// |
1407 /// Default constructor. |
1429 /// Default constructor. |
1408 /// To actually make a snapshot you must call save(). |
1430 /// To actually make a snapshot you must call save(). |
1409 Snapshot() |
1431 Snapshot() |
1410 : digraph(0), node_observer_proxy(*this), |
1432 : graph(0), node_observer_proxy(*this), |
1411 arc_observer_proxy(*this) {} |
1433 edge_observer_proxy(*this) {} |
1412 |
1434 |
1413 /// \brief Constructor that immediately makes a snapshot. |
1435 /// \brief Constructor that immediately makes a snapshot. |
1414 /// |
1436 /// |
1415 /// This constructor immediately makes a snapshot of the digraph. |
1437 /// This constructor immediately makes a snapshot of the graph. |
1416 /// \param _digraph The digraph we make a snapshot of. |
1438 /// \param _graph The graph we make a snapshot of. |
1417 Snapshot(ListGraph &_digraph) |
1439 Snapshot(ListGraph &_graph) |
1418 : node_observer_proxy(*this), |
1440 : node_observer_proxy(*this), |
1419 arc_observer_proxy(*this) { |
1441 edge_observer_proxy(*this) { |
1420 attach(_digraph); |
1442 attach(_graph); |
1421 } |
1443 } |
1422 |
1444 |
1423 /// \brief Make a snapshot. |
1445 /// \brief Make a snapshot. |
1424 /// |
1446 /// |
1425 /// Make a snapshot of the digraph. |
1447 /// Make a snapshot of the graph. |
1426 /// |
1448 /// |
1427 /// This function can be called more than once. In case of a repeated |
1449 /// This function can be called more than once. In case of a repeated |
1428 /// call, the previous snapshot gets lost. |
1450 /// call, the previous snapshot gets lost. |
1429 /// \param _digraph The digraph we make the snapshot of. |
1451 /// \param _graph The graph we make the snapshot of. |
1430 void save(ListGraph &_digraph) { |
1452 void save(ListGraph &_graph) { |
1431 if (attached()) { |
1453 if (attached()) { |
1432 detach(); |
1454 detach(); |
1433 clear(); |
1455 clear(); |
1434 } |
1456 } |
1435 attach(_digraph); |
1457 attach(_graph); |
1436 } |
1458 } |
1437 |
1459 |
1438 /// \brief Undo the changes until the last snapshot. |
1460 /// \brief Undo the changes until the last snapshot. |
1439 // |
1461 // |
1440 /// Undo the changes until the last snapshot created by save(). |
1462 /// Undo the changes until the last snapshot created by save(). |
1441 void restore() { |
1463 void restore() { |
1442 detach(); |
1464 detach(); |
1443 for(std::list<Edge>::iterator it = added_arcs.begin(); |
1465 for(std::list<Edge>::iterator it = added_edges.begin(); |
1444 it != added_arcs.end(); ++it) { |
1466 it != added_edges.end(); ++it) { |
1445 digraph->erase(*it); |
1467 graph->erase(*it); |
1446 } |
1468 } |
1447 for(std::list<Node>::iterator it = added_nodes.begin(); |
1469 for(std::list<Node>::iterator it = added_nodes.begin(); |
1448 it != added_nodes.end(); ++it) { |
1470 it != added_nodes.end(); ++it) { |
1449 digraph->erase(*it); |
1471 graph->erase(*it); |
1450 } |
1472 } |
1451 clear(); |
1473 clear(); |
1452 } |
1474 } |
1453 |
1475 |
1454 /// \brief Gives back true when the snapshot is valid. |
1476 /// \brief Gives back true when the snapshot is valid. |