376 } |
376 } |
377 /// Changes the source of \c e to \c n |
377 /// Changes the source of \c e to \c n |
378 |
378 |
379 /// Changes the source of \c e to \c n |
379 /// Changes the source of \c e to \c n |
380 /// |
380 /// |
381 ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing |
381 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing |
382 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are |
382 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are |
383 ///invalidated. |
383 ///invalidated. |
384 ///\warning This functionality cannot be used together with the Snapshot |
384 ///\warning This functionality cannot be used together with the Snapshot |
385 ///feature. |
385 ///feature. |
386 void changeSource(Edge e, Node n) { |
386 void changeSource(Edge e, Node n) { |
387 Parent::changeSource(e,n); |
387 Parent::changeSource(e,n); |
388 } |
388 } |
389 |
389 |
390 /// Invert the direction of an edge. |
390 /// Invert the direction of an edge. |
391 |
391 |
392 ///\note The <tt>Edge</tt>s referencing the changed edge remain |
392 ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain |
393 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are |
393 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are |
394 ///invalidated. |
394 ///invalidated. |
395 ///\warning This functionality cannot be used together with the Snapshot |
395 ///\warning This functionality cannot be used together with the Snapshot |
396 ///feature. |
396 ///feature. |
397 void reverseEdge(Edge e) { |
397 void reverseEdge(Edge e) { |
424 ///Node \p b will be removed but instead of deleting |
424 ///Node \p b will be removed but instead of deleting |
425 ///incident edges, they will be joined to \p a. |
425 ///incident edges, they will be joined to \p a. |
426 ///The last parameter \p r controls whether to remove loops. \c true |
426 ///The last parameter \p r controls whether to remove loops. \c true |
427 ///means that loops will be removed. |
427 ///means that loops will be removed. |
428 /// |
428 /// |
429 ///\note The <tt>Edge</tt>s |
429 ///\note The <tt>EdgeIt</tt>s |
430 ///referencing a moved edge remain |
430 ///referencing a moved edge remain |
431 ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s |
431 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s |
432 ///may be invalidated. |
432 ///may be invalidated. |
433 ///\warning This functionality cannot be used together with the Snapshot |
433 ///\warning This functionality cannot be used together with the Snapshot |
434 ///feature. |
434 ///feature. |
435 void contract(Node a, Node b, bool r = true) |
435 void contract(Node a, Node b, bool r = true) |
436 { |
436 { |
457 ///then the source of each outgoing edge of \c n is moved to this new node. |
457 ///then the source of each outgoing edge of \c n is moved to this new node. |
458 ///If \c connect is \c true (this is the default value), then a new edge |
458 ///If \c connect is \c true (this is the default value), then a new edge |
459 ///from \c n to the newly created node is also added. |
459 ///from \c n to the newly created node is also added. |
460 ///\return The newly created node. |
460 ///\return The newly created node. |
461 /// |
461 /// |
462 ///\note The <tt>Edge</tt>s |
462 ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain |
463 ///referencing a moved edge remain |
463 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may |
464 ///valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s |
464 ///be invalidated. |
465 ///may be invalidated. |
465 /// |
466 ///\warning This functionality cannot be used together with the Snapshot |
466 ///\warning This functionality cannot be used together with the |
467 ///feature. |
467 ///Snapshot feature. \todo It could be implemented in a bit |
468 ///\todo It could be implemented in a bit faster way. |
468 ///faster way. |
469 Node split(Node n, bool connect = true) { |
469 Node split(Node n, bool connect = true) { |
470 Node b = addNode(); |
470 Node b = addNode(); |
471 for(OutEdgeIt e(*this,n);e!=INVALID;) { |
471 for(OutEdgeIt e(*this,n);e!=INVALID;) { |
472 OutEdgeIt f=e; |
472 OutEdgeIt f=e; |
473 ++f; |
473 ++f; |
786 /// and target node \c t. |
783 /// and target node \c t. |
787 /// \return the new undirected edge. |
784 /// \return the new undirected edge. |
788 UEdge addEdge(const Node& s, const Node& t) { |
785 UEdge addEdge(const Node& s, const Node& t) { |
789 return Parent::addEdge(s, t); |
786 return Parent::addEdge(s, t); |
790 } |
787 } |
|
788 /// \brief Changes the source of \c e to \c n |
|
789 /// |
|
790 /// Changes the source of \c e to \c n |
|
791 /// |
|
792 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s |
|
793 ///referencing the changed edge remain |
|
794 ///valid. However <tt>OutEdgeIt</tt>s are invalidated. |
|
795 void changeSource(UEdge e, Node n) { |
|
796 Parent::changeSource(e,n); |
|
797 } |
791 /// \brief Changes the target of \c e to \c n |
798 /// \brief Changes the target of \c e to \c n |
792 /// |
799 /// |
793 /// Changes the target of \c e to \c n |
800 /// Changes the target of \c e to \c n |
794 /// |
801 /// |
795 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s |
802 /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain |
796 /// referencing the changed edge remain |
803 /// valid. However the other iterators may be invalidated. |
797 /// valid. However <tt>InEdge</tt>'s are invalidated. |
|
798 void changeTarget(UEdge e, Node n) { |
804 void changeTarget(UEdge e, Node n) { |
799 Parent::changeTarget(e,n); |
805 Parent::changeTarget(e,n); |
800 } |
806 } |
801 /// Changes the source of \c e to \c n |
807 /// \brief Changes the source of \c e to \c n |
802 /// |
808 /// |
803 /// Changes the source of \c e to \c n |
809 /// Changes the source of \c e to \c n. It changes the proper |
804 /// |
810 /// node of the represented undirected edge. |
805 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s |
811 /// |
|
812 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s |
806 ///referencing the changed edge remain |
813 ///referencing the changed edge remain |
807 ///valid. However <tt>OutEdge</tt>'s are invalidated. |
814 ///valid. However <tt>OutEdgeIt</tt>s are invalidated. |
808 void changeSource(UEdge e, Node n) { |
815 void changeSource(Edge e, Node n) { |
809 Parent::changeSource(e,n); |
816 if (Parent::direction(e)) { |
|
817 Parent::changeSource(e,n); |
|
818 } else { |
|
819 Parent::changeTarget(e,n); |
|
820 } |
|
821 } |
|
822 /// \brief Changes the target of \c e to \c n |
|
823 /// |
|
824 /// Changes the target of \c e to \c n. It changes the proper |
|
825 /// node of the represented undirected edge. |
|
826 /// |
|
827 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s |
|
828 ///referencing the changed edge remain |
|
829 ///valid. However <tt>InEdgeIt</tt>s are invalidated. |
|
830 void changeTarget(Edge e, Node n) { |
|
831 if (Parent::direction(e)) { |
|
832 Parent::changeTarget(e,n); |
|
833 } else { |
|
834 Parent::changeSource(e,n); |
|
835 } |
810 } |
836 } |
811 /// \brief Contract two nodes. |
837 /// \brief Contract two nodes. |
812 /// |
838 /// |
813 /// This function contracts two nodes. |
839 /// This function contracts two nodes. |
814 /// |
840 /// |
815 /// Node \p b will be removed but instead of deleting |
841 /// Node \p b will be removed but instead of deleting |
816 /// its neighboring edges, they will be joined to \p a. |
842 /// its neighboring edges, they will be joined to \p a. |
817 /// The last parameter \p r controls whether to remove loops. \c true |
843 /// The last parameter \p r controls whether to remove loops. \c true |
818 /// means that loops will be removed. |
844 /// means that loops will be removed. |
819 /// |
845 /// |
820 /// \note The <tt>Edge</tt>s |
846 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain |
821 /// referencing a moved edge remain |
|
822 /// valid. |
847 /// valid. |
823 void contract(Node a, Node b, bool r = true) { |
848 void contract(Node a, Node b, bool r = true) { |
824 for(IncEdgeIt e(*this, b); e!=INVALID;) { |
849 for(IncEdgeIt e(*this, b); e!=INVALID;) { |
825 IncEdgeIt f = e; ++f; |
850 IncEdgeIt f = e; ++f; |
826 if (r && runningNode(e) == a) { |
851 if (r && runningNode(e) == a) { |
1181 first_bnode = -1; |
1203 first_bnode = -1; |
1182 first_free_bnode = -1; |
1204 first_free_bnode = -1; |
1183 first_free_edge = -1; |
1205 first_free_edge = -1; |
1184 } |
1206 } |
1185 |
1207 |
|
1208 void changeANode(const UEdge& edge, const Node& node) { |
|
1209 LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); |
|
1210 if (edges[edge.id].prev_out != -1) { |
|
1211 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; |
|
1212 } else { |
|
1213 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out; |
|
1214 } |
|
1215 if (edges[edge.id].next_out != -1) { |
|
1216 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; |
|
1217 } |
|
1218 if (aNodes[node.id >> 1].first_edge != -1) { |
|
1219 edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id; |
|
1220 } |
|
1221 edges[edge.id].prev_out = -1; |
|
1222 edges[edge.id].next_out = aNodes[node.id >> 1].first_edge; |
|
1223 aNodes[node.id >> 1].first_edge = edge.id; |
|
1224 edges[edge.id].aNode = node.id; |
|
1225 } |
|
1226 |
|
1227 void changeBNode(const UEdge& edge, const Node& node) { |
|
1228 LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); |
|
1229 if (edges[edge.id].prev_in != -1) { |
|
1230 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in; |
|
1231 } else { |
|
1232 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in; |
|
1233 } |
|
1234 if (edges[edge.id].next_in != -1) { |
|
1235 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; |
|
1236 } |
|
1237 if (bNodes[node.id >> 1].first_edge != -1) { |
|
1238 edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id; |
|
1239 } |
|
1240 edges[edge.id].prev_in = -1; |
|
1241 edges[edge.id].next_in = bNodes[node.id >> 1].first_edge; |
|
1242 bNodes[node.id >> 1].first_edge = edge.id; |
|
1243 edges[edge.id].bNode = node.id; |
|
1244 } |
|
1245 |
1186 }; |
1246 }; |
1187 |
1247 |
1188 |
1248 |
1189 typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase; |
1249 typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase; |
1190 |
1250 |
1194 /// |
1254 /// |
1195 /// This is a bipartite undirected graph implementation. |
1255 /// This is a bipartite undirected graph implementation. |
1196 /// It is conforms to the \ref concept::BpUGraph "BpUGraph concept". |
1256 /// It is conforms to the \ref concept::BpUGraph "BpUGraph concept". |
1197 /// \sa concept::BpUGraph. |
1257 /// \sa concept::BpUGraph. |
1198 /// |
1258 /// |
1199 class ListBpUGraph : public ExtendedListBpUGraphBase {}; |
1259 class ListBpUGraph : public ExtendedListBpUGraphBase { |
|
1260 /// \brief ListBpUGraph is \e not copy constructible. |
|
1261 /// |
|
1262 ///ListBpUGraph is \e not copy constructible. |
|
1263 ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase() {}; |
|
1264 /// \brief Assignment of ListBpUGraph to another one is \e not |
|
1265 /// allowed. |
|
1266 /// |
|
1267 /// Assignment of ListBpUGraph to another one is \e not allowed. |
|
1268 void operator=(const ListBpUGraph &) {} |
|
1269 public: |
|
1270 /// \brief Constructor |
|
1271 /// |
|
1272 /// Constructor. |
|
1273 /// |
|
1274 ListBpUGraph() {} |
|
1275 |
|
1276 typedef ExtendedListBpUGraphBase Parent; |
|
1277 /// \brief Add a new ANode to the graph. |
|
1278 /// |
|
1279 /// \return the new node. |
|
1280 /// |
|
1281 Node addANode() { return Parent::addANode(); } |
|
1282 |
|
1283 /// \brief Add a new BNode to the graph. |
|
1284 /// |
|
1285 /// \return the new node. |
|
1286 /// |
|
1287 Node addBNode() { return Parent::addBNode(); } |
|
1288 |
|
1289 /// \brief Add a new edge to the graph. |
|
1290 /// |
|
1291 /// Add a new edge to the graph with an ANode and a BNode. |
|
1292 /// \return the new undirected edge. |
|
1293 UEdge addEdge(const Node& s, const Node& t) { |
|
1294 return Parent::addEdge(s, t); |
|
1295 } |
|
1296 |
|
1297 /// \brief Changes the ANode of \c e to \c n |
|
1298 /// |
|
1299 /// Changes the ANode of \c e to \c n |
|
1300 /// |
|
1301 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing |
|
1302 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are |
|
1303 ///invalidated. |
|
1304 void changeANode(UEdge e, Node n) { |
|
1305 Parent::changeANode(e,n); |
|
1306 } |
|
1307 |
|
1308 /// \brief Changes the BNode of \c e to \c n |
|
1309 /// |
|
1310 /// Changes the BNode of \c e to \c n |
|
1311 /// |
|
1312 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s |
|
1313 /// referencing the changed edge remain |
|
1314 /// valid. However <tt>InEdgeIt</tt>s are invalidated. |
|
1315 void changeBNode(UEdge e, Node n) { |
|
1316 Parent::changeBNode(e,n); |
|
1317 } |
|
1318 |
|
1319 /// \brief Changes the source(ANode) of \c e to \c n |
|
1320 /// |
|
1321 /// Changes the source(ANode) of \c e to \c n |
|
1322 /// |
|
1323 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing |
|
1324 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are |
|
1325 ///invalidated. |
|
1326 void changeSource(UEdge e, Node n) { |
|
1327 Parent::changeANode(e,n); |
|
1328 } |
|
1329 |
|
1330 /// \brief Changes the target(BNode) of \c e to \c n |
|
1331 /// |
|
1332 /// Changes the target(BNode) of \c e to \c n |
|
1333 /// |
|
1334 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s |
|
1335 /// referencing the changed edge remain |
|
1336 /// valid. However <tt>InEdgeIt</tt>s are invalidated. |
|
1337 void changeTarget(UEdge e, Node n) { |
|
1338 Parent::changeBNode(e,n); |
|
1339 } |
|
1340 |
|
1341 /// \brief Changes the source of \c e to \c n |
|
1342 /// |
|
1343 /// Changes the source of \c e to \c n. It changes the proper |
|
1344 /// node of the represented undirected edge. |
|
1345 /// |
|
1346 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s |
|
1347 ///referencing the changed edge remain |
|
1348 ///valid. However <tt>OutEdgeIt</tt>s are invalidated. |
|
1349 void changeSource(Edge e, Node n) { |
|
1350 if (Parent::direction(e)) { |
|
1351 Parent::changeANode(e,n); |
|
1352 } else { |
|
1353 Parent::changeBNode(e,n); |
|
1354 } |
|
1355 } |
|
1356 /// \brief Changes the target of \c e to \c n |
|
1357 /// |
|
1358 /// Changes the target of \c e to \c n. It changes the proper |
|
1359 /// node of the represented undirected edge. |
|
1360 /// |
|
1361 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s |
|
1362 ///referencing the changed edge remain |
|
1363 ///valid. However <tt>InEdgeIt</tt>s are invalidated. |
|
1364 void changeTarget(Edge e, Node n) { |
|
1365 if (Parent::direction(e)) { |
|
1366 Parent::changeBNode(e,n); |
|
1367 } else { |
|
1368 Parent::changeANode(e,n); |
|
1369 } |
|
1370 } |
|
1371 /// \brief Contract two nodes. |
|
1372 /// |
|
1373 /// This function contracts two nodes. |
|
1374 /// |
|
1375 /// Node \p b will be removed but instead of deleting its |
|
1376 /// neighboring edges, they will be joined to \p a. The two nodes |
|
1377 /// should be from the same nodeset, of course. |
|
1378 /// |
|
1379 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain |
|
1380 /// valid. |
|
1381 void contract(const Node& a, const Node& b) { |
|
1382 LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError()); |
|
1383 if (Parent::aNode(a)) { |
|
1384 for (IncEdgeIt e(*this, b); e!=INVALID;) { |
|
1385 IncEdgeIt f = e; ++f; |
|
1386 changeSource(e, a); |
|
1387 e = f; |
|
1388 } |
|
1389 } else { |
|
1390 for (IncEdgeIt e(*this, b); e!=INVALID;) { |
|
1391 IncEdgeIt f = e; ++f; |
|
1392 changeTarget(e, a); |
|
1393 e = f; |
|
1394 } |
|
1395 } |
|
1396 erase(b); |
|
1397 } |
|
1398 |
|
1399 }; |
1200 |
1400 |
1201 |
1401 |
1202 /// @} |
1402 /// @} |
1203 } //namespace lemon |
1403 } //namespace lemon |
1204 |
1404 |