Changeset 2160:abd867cf8a9c in lemon0.x for lemon/list_graph.h
 Timestamp:
 07/24/06 11:49:50 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2875
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/list_graph.h
r2151 r2160 367 367 /// Changes the target of \c e to \c n 368 368 /// 369 ///\note The <tt>Edge </tt>s and <tt>OutEdgeIt</tt>s referencing369 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing 370 370 ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are 371 371 ///invalidated. … … 379 379 /// Changes the source of \c e to \c n 380 380 /// 381 ///\note The <tt>Edge </tt>s and <tt>InEdgeIt</tt>s referencing381 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing 382 382 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are 383 383 ///invalidated. … … 390 390 /// Invert the direction of an edge. 391 391 392 ///\note The <tt>Edge </tt>s referencing the changed edge remain392 ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain 393 393 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are 394 394 ///invalidated. … … 427 427 ///means that loops will be removed. 428 428 /// 429 ///\note The <tt>Edge </tt>s429 ///\note The <tt>EdgeIt</tt>s 430 430 ///referencing a moved edge remain 431 ///valid. However <tt>InEdge </tt>s and <tt>OutEdge</tt>s431 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s 432 432 ///may be invalidated. 433 433 ///\warning This functionality cannot be used together with the Snapshot … … 460 460 ///\return The newly created node. 461 461 /// 462 ///\note The <tt>Edge </tt>s463 /// referencing a moved edge remain464 /// valid. However <tt>InEdge</tt>s and <tt>OutEdge</tt>s465 /// may be invalidated.466 ///\warning This functionality cannot be used together with the Snapshot467 /// feature.468 /// \todo It could be implemented in a bitfaster way.462 ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain 463 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may 464 ///be invalidated. 465 /// 466 ///\warning This functionality cannot be used together with the 467 ///Snapshot feature. \todo It could be implemented in a bit 468 ///faster way. 469 469 Node split(Node n, bool connect = true) { 470 470 Node b = addNode(); … … 677 677 public: 678 678 679 /// \brief Default construct ur.679 /// \brief Default constructor. 680 680 /// 681 681 /// Default constructor. … … 751 751 ///\sa concept::UGraph. 752 752 /// 753 ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()754 ///haven't been implemented yet.755 ///756 753 class ListUGraph : public ExtendedListUGraphBase { 757 754 private: … … 789 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 798 /// \brief Changes the target of \c e to \c n 792 799 /// 793 800 /// Changes the target of \c e to \c n 794 801 /// 795 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s 796 /// referencing the changed edge remain 797 /// valid. However <tt>InEdge</tt>'s are invalidated. 802 /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain 803 /// valid. However the other iterators may be invalidated. 798 804 void changeTarget(UEdge e, Node n) { 799 805 Parent::changeTarget(e,n); 800 806 } 801 /// Changes the source of \c e to \c n 802 /// 803 /// Changes the source of \c e to \c n 804 /// 805 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s 807 /// \brief Changes the source of \c e to \c n 808 /// 809 /// Changes the source of \c e to \c n. It changes the proper 810 /// node of the represented undirected edge. 811 /// 812 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s 806 813 ///referencing the changed edge remain 807 ///valid. However <tt>OutEdge</tt>'s are invalidated. 808 void changeSource(UEdge e, Node n) { 809 Parent::changeSource(e,n); 814 ///valid. However <tt>OutEdgeIt</tt>s are invalidated. 815 void changeSource(Edge e, Node 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 837 /// \brief Contract two nodes. … … 818 844 /// means that loops will be removed. 819 845 /// 820 /// \note The <tt>Edge</tt>s 821 /// referencing a moved edge remain 846 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain 822 847 /// valid. 823 848 void contract(Node a, Node b, bool r = true) { … … 842 867 843 868 class NodeSetError : public LogicError { 869 public: 844 870 virtual const char* what() const throw() { 845 871 return "lemon::ListBpUGraph::NodeSetError"; … … 1169 1195 } 1170 1196 1171 ///\e1172 1173 ///\bug Undocumented1174 ///\bug Doesn't destruct the maps.1175 1197 void clear() { 1176 1198 aNodes.clear(); … … 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 … … 1197 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
Note: See TracChangeset
for help on using the changeset viewer.