Changeset 73:c56b7389dc78 in lemon-1.2
- Timestamp:
- 02/05/08 11:24:57 (17 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/list_graph.h
r57 r73 112 112 113 113 114 void first(Arc& e) const {114 void first(Arc& arc) const { 115 115 int n; 116 116 for(n = first_node; 117 117 n!=-1 && nodes[n].first_in == -1; 118 118 n = nodes[n].next); 119 e.id = (n == -1) ? -1 : nodes[n].first_in;119 arc.id = (n == -1) ? -1 : nodes[n].first_in; 120 120 } 121 121 … … 294 294 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase; 295 295 296 /// \addtogroup digraphs296 /// \addtogroup graphs 297 297 /// @{ 298 298 299 ///A list digraph class. 300 301 ///This is a simple and fast digraph implementation. 299 ///A general directed graph structure. 300 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 305 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it 304 ///also provides several additional useful extrafunctionalities.305 /// The most of the member functions and nested classes are306 /// documentedonly in the concept class.306 ///also provides several useful additional functionalities. 307 ///Most of the member functions and nested classes are documented 308 ///only in the concept class. 307 309 /// 308 310 ///An important extra feature of this digraph implementation is that 309 311 ///its maps are real \ref concepts::ReferenceMap "reference map"s. 310 312 /// 311 ///\sa concepts::Digraph .313 ///\sa concepts::Digraph 312 314 313 315 class ListDigraph : public ExtendedListDigraphBase { 314 316 private: 315 ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.316 317 ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.317 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 318 319 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead. 318 320 /// 319 321 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {}; 320 322 ///\brief Assignment of ListDigraph to another one is \e not allowed. 321 ///Use DigraphCopy() instead.323 ///Use copyDigraph() instead. 322 324 323 325 ///Assignment of ListDigraph to another one is \e not allowed. 324 ///Use DigraphCopy() instead.326 ///Use copyDigraph() instead. 325 327 void operator=(const ListDigraph &) {} 326 328 public: … … 336 338 ///Add a new node to the digraph. 337 339 338 /// \return the new node.339 /// 340 ///Add a new node to the digraph. 341 ///\return the new node. 340 342 Node addNode() { return Parent::addNode(); } 341 343 … … 349 351 } 350 352 351 /// Change sthe target of \c e to \c n352 353 /// Change sthe target of \c e to \c n353 /// Change the target of \c e to \c n 354 355 /// Change the target of \c e to \c n 354 356 /// 355 357 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing 356 358 ///the changed arc remain valid. However <tt>InArcIt</tt>s are 357 359 ///invalidated. 360 /// 358 361 ///\warning This functionality cannot be used together with the Snapshot 359 362 ///feature. … … 361 364 Parent::changeTarget(e,n); 362 365 } 363 /// Change sthe source of \c e to \c n364 365 /// Change sthe source of \c e to \c n366 /// Change the source of \c e to \c n 367 368 /// Change the source of \c e to \c n 366 369 /// 367 370 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing 368 371 ///the changed arc remain valid. However <tt>OutArcIt</tt>s are 369 372 ///invalidated. 373 /// 370 374 ///\warning This functionality cannot be used together with the Snapshot 371 375 ///feature. … … 379 383 ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are 380 384 ///invalidated. 385 /// 381 386 ///\warning This functionality cannot be used together with the Snapshot 382 387 ///feature. … … 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 397 /// allocation: if you know that the digraph you want to build will 391 398 /// be very large (e.g. it will contain millions of nodes and/or arcs) … … 395 402 void reserveNode(int n) { nodes.reserve(n); }; 396 403 397 /// \brief Using this it is possible to avoid the superfluous memory 398 /// allocation. 399 400 /// Using this it is possible to avoid the superfluous memory 404 /// Reserve memory for arcs. 405 406 /// Using this function it is possible to avoid the superfluous memory 401 407 /// allocation: if you know that the digraph you want to build will 402 408 /// be very large (e.g. it will contain millions of nodes and/or arcs) … … 409 415 410 416 ///This function contracts two nodes. 411 ///412 417 ///Node \p b will be removed but instead of deleting 413 418 ///incident arcs, they will be joined to \p a. … … 415 420 ///means that loops will be removed. 416 421 /// 417 ///\note The <tt>ArcIt</tt>s 418 ///referencing a moved arc remain 422 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain 419 423 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s 420 424 ///may be invalidated. 425 /// 421 426 ///\warning This functionality cannot be used together with the Snapshot 422 427 ///feature. … … 453 458 /// 454 459 ///\warning This functionality cannot be used together with the 455 ///Snapshot feature. \todo It could be implemented in a bit 456 ///faster way. 460 ///Snapshot feature. 461 /// 462 ///\todo It could be implemented in a bit faster way. 457 463 Node split(Node n, bool connect = true) { 458 464 Node b = addNode(); … … 472 478 ///the digraph, then the original arc is re-targeted to \c 473 479 ///b. Finally an arc from \c b to the original target is added. 474 ///\return The newly created node. 475 ///\warning This functionality 476 ///cannot be used together with the Snapshot feature. 480 /// 481 ///\return The newly created node. 482 /// 483 ///\warning This functionality cannot be used together with the 484 ///Snapshot feature. 477 485 Node split(Arc e) { 478 486 Node b = addNode(); … … 483 491 484 492 /// \brief Class to make a snapshot of the digraph and restore 485 /// to it later. 486 /// 487 /// Class to make a snapshot of the digraph and to restore it 488 /// later. 493 /// it later. 494 /// 495 /// Class to make a snapshot of the digraph and restore it later. 489 496 /// 490 497 /// The newly added nodes and arcs can be removed using the 491 498 /// restore() function. 492 499 /// 493 /// \warning Arc and node deletions cannot be restored. This 494 /// events invalidate the snapshot. 500 /// \warning Arc and node deletions and other modifications (e.g. 501 /// contracting, splitting, reversing arcs or nodes) cannot be 502 /// restored. These events invalidate the snapshot. 495 503 class Snapshot { 496 504 protected: … … 777 785 Edge() {} 778 786 Edge (Invalid) { id = -1; } 779 bool operator==(const Edge& arc) const {return id == arc.id;}780 bool operator!=(const Edge& arc) const {return id != arc.id;}781 bool operator<(const Edge& arc) const {return id < arc.id;}787 bool operator==(const Edge& edge) const {return id == edge.id;} 788 bool operator!=(const Edge& edge) const {return id != edge.id;} 789 bool operator<(const Edge& edge) const {return id < edge.id;} 782 790 }; 783 791 … … 910 918 911 919 void firstInc(Edge &e, bool& d, const Node& v) const { 912 int de= nodes[v.id].first_out;913 if ( de!= -1 ) {914 e.id = de/ 2;915 d = (( de& 1) == 1);920 int a = nodes[v.id].first_out; 921 if (a != -1 ) { 922 e.id = a / 2; 923 d = ((a & 1) == 1); 916 924 } else { 917 925 e.id = -1; … … 920 928 } 921 929 void nextInc(Edge &e, bool& d) const { 922 int de= (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);923 if ( de!= -1 ) {924 e.id = de/ 2;925 d = (( de& 1) == 1);930 int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out); 931 if (a != -1 ) { 932 e.id = a / 2; 933 d = ((a & 1) == 1); 926 934 } else { 927 935 e.id = -1; … … 1009 1017 } 1010 1018 1011 void erase(const Edge& arc) {1012 int n = arc.id * 2;1019 void erase(const Edge& edge) { 1020 int n = edge.id * 2; 1013 1021 1014 1022 if (arcs[n].next_out != -1) { … … 1090 1098 }; 1091 1099 1092 // typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> >1093 // ExtendedListGraphBase;1094 1095 1100 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase; 1096 1101 1097 1102 1098 1099 /// \addtogroup digraphs 1103 /// \addtogroup graphs 1100 1104 /// @{ 1101 1105 1102 ///An undirected list digraph class. 1103 1104 ///This is a simple and fast undirected digraph implementation. 1106 ///A general undirected graph structure. 1107 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 1118 ///its maps are real \ref concepts::ReferenceMap "reference map"s. 1108 1119 /// 1109 ///It conforms to the 1110 ///\ref concepts::Graph "Graph concept". 1111 /// 1112 ///\sa concepts::Graph. 1113 /// 1120 ///\sa concepts::Graph 1121 1114 1122 class ListGraph : public ExtendedListGraphBase { 1115 1123 private: 1116 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.1117 1118 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.1124 ///ListGraph is \e not copy constructible. Use copyGraph() instead. 1125 1126 ///ListGraph is \e not copy constructible. Use copyGraph() instead. 1119 1127 /// 1120 1128 ListGraph(const ListGraph &) :ExtendedListGraphBase() {}; 1121 1129 ///\brief Assignment of ListGraph to another one is \e not allowed. 1122 ///Use GraphCopy() instead.1130 ///Use copyGraph() instead. 1123 1131 1124 1132 ///Assignment of ListGraph to another one is \e not allowed. 1125 ///Use GraphCopy() instead.1133 ///Use copyGraph() instead. 1126 1134 void operator=(const ListGraph &) {} 1127 1135 public: … … 1134 1142 typedef ExtendedListGraphBase Parent; 1135 1143 1136 typedef Parent::OutArcIt IncArcIt; 1137 1138 /// \brief Add a new node to the digraph. 1139 /// 1144 typedef Parent::OutArcIt IncEdgeIt; 1145 1146 /// \brief Add a new node to the graph. 1147 /// 1148 /// Add a new node to the graph. 1140 1149 /// \return the new node. 1141 ///1142 1150 Node addNode() { return Parent::addNode(); } 1143 1151 1144 /// \brief Add a new edge to the digraph.1145 /// 1146 /// Add a new arc to the digraph with source node \c s1152 /// \brief Add a new edge to the graph. 1153 /// 1154 /// Add a new edge to the graph with source node \c s 1147 1155 /// and target node \c t. 1148 1156 /// \return the new edge. … … 1150 1158 return Parent::addEdge(s, t); 1151 1159 } 1152 /// \brief Change sthe source of \c e to \c n1153 /// 1154 /// Changes the source of \c e to \c n1160 /// \brief Change the source of \c e to \c n 1161 /// 1162 /// This function changes the source of \c e to \c n. 1155 1163 /// 1156 1164 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s 1157 1165 ///referencing the changed arc remain 1158 1166 ///valid. However <tt>OutArcIt</tt>s are invalidated. 1167 /// 1168 ///\warning This functionality cannot be used together with the 1169 ///Snapshot feature. 1159 1170 void changeSource(Edge e, Node n) { 1160 1171 Parent::changeSource(e,n); 1161 1172 } 1162 /// \brief Change sthe target of \c e to \c n1163 /// 1164 /// Changes the target of \c e to \c n1173 /// \brief Change the target of \c e to \c n 1174 /// 1175 /// This function changes the target of \c e to \c n. 1165 1176 /// 1166 1177 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain 1167 1178 /// valid. However the other iterators may be invalidated. 1179 /// 1180 ///\warning This functionality cannot be used together with the 1181 ///Snapshot feature. 1168 1182 void changeTarget(Edge e, Node n) { 1169 1183 Parent::changeTarget(e,n); 1170 1184 } 1171 /// \brief Change sthe source of \c e to \c n1172 /// 1173 /// Changes the source of \c e to \c n. It changes the proper1174 /// node of the represented edge.1185 /// \brief Change the source of \c e to \c n 1186 /// 1187 /// This function changes the source of \c e to \c n. 1188 /// It also changes the proper node of the represented edge. 1175 1189 /// 1176 1190 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s 1177 1191 ///referencing the changed arc remain 1178 1192 ///valid. However <tt>OutArcIt</tt>s are invalidated. 1193 /// 1194 ///\warning This functionality cannot be used together with the 1195 ///Snapshot feature. 1179 1196 void changeSource(Arc e, Node n) { 1180 1197 if (Parent::direction(e)) { … … 1184 1201 } 1185 1202 } 1186 /// \brief Change sthe target of \c e to \c n1187 /// 1188 /// Changes the target of \c e to \c n. It changes the proper1189 /// node of the represented edge.1203 /// \brief Change the target of \c e to \c n 1204 /// 1205 /// This function changes the target of \c e to \c n. 1206 /// It also changes the proper node of the represented edge. 1190 1207 /// 1191 1208 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s 1192 1209 ///referencing the changed arc remain 1193 1210 ///valid. However <tt>InArcIt</tt>s are invalidated. 1211 /// 1212 ///\warning This functionality cannot be used together with the 1213 ///Snapshot feature. 1194 1214 void changeTarget(Arc e, Node n) { 1195 1215 if (Parent::direction(e)) { … … 1202 1222 /// 1203 1223 /// This function contracts two nodes. 1204 ///1205 1224 /// Node \p b will be removed but instead of deleting 1206 1225 /// its neighboring arcs, they will be joined to \p a. … … 1210 1229 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain 1211 1230 /// valid. 1231 /// 1232 ///\warning This functionality cannot be used together with the 1233 ///Snapshot feature. 1212 1234 void contract(Node a, Node b, bool r = true) { 1213 for(Inc ArcIt e(*this, b); e!=INVALID;) {1214 Inc ArcIt f = e; ++f;1235 for(IncEdgeIt e(*this, b); e!=INVALID;) { 1236 IncEdgeIt f = e; ++f; 1215 1237 if (r && runningNode(e) == a) { 1216 1238 erase(e); … … 1226 1248 1227 1249 1228 /// \brief Class to make a snapshot of the digraph and restore 1229 /// to it later. 1230 /// 1231 /// Class to make a snapshot of the digraph and to restore it 1232 /// later. 1250 /// \brief Class to make a snapshot of the graph and restore 1251 /// it later. 1252 /// 1253 /// Class to make a snapshot of the graph and restore it later. 1233 1254 /// 1234 1255 /// The newly added nodes and edges can be removed 1235 1256 /// using the restore() function. 1236 1257 /// 1237 /// \warning Arc and node deletions cannot be restored. This 1238 /// events invalidate the snapshot. 1258 /// \warning Edge and node deletions and other modifications 1259 /// (e.g. changing nodes of edges, contracting nodes) cannot be 1260 /// restored. These events invalidate the snapshot. 1239 1261 class Snapshot { 1240 1262 protected: … … 1304 1326 protected: 1305 1327 1306 virtual void add(const Edge& arc) {1307 snapshot.addEdge( arc);1308 } 1309 virtual void add(const std::vector<Edge>& arcs) {1310 for (int i = arcs.size() - 1; i >= 0; ++i) {1311 snapshot.addEdge( arcs[i]);1312 } 1313 } 1314 virtual void erase(const Edge& arc) {1315 snapshot.eraseEdge( arc);1316 } 1317 virtual void erase(const std::vector<Edge>& arcs) {1318 for (int i = 0; i < int( arcs.size()); ++i) {1319 snapshot.eraseEdge( arcs[i]);1328 virtual void add(const Edge& edge) { 1329 snapshot.addEdge(edge); 1330 } 1331 virtual void add(const std::vector<Edge>& edges) { 1332 for (int i = edges.size() - 1; i >= 0; ++i) { 1333 snapshot.addEdge(edges[i]); 1334 } 1335 } 1336 virtual void erase(const Edge& edge) { 1337 snapshot.eraseEdge(edge); 1338 } 1339 virtual void erase(const std::vector<Edge>& edges) { 1340 for (int i = 0; i < int(edges.size()); ++i) { 1341 snapshot.eraseEdge(edges[i]); 1320 1342 } 1321 1343 } 1322 1344 virtual void build() { 1323 Edge arc;1324 std::vector<Edge> arcs;1325 for (notifier()->first( arc); arc!= INVALID;1326 notifier()->next( arc)) {1327 arcs.push_back(arc);1328 } 1329 for (int i = arcs.size() - 1; i >= 0; --i) {1330 snapshot.addEdge( arcs[i]);1345 Edge edge; 1346 std::vector<Edge> edges; 1347 for (notifier()->first(edge); edge != INVALID; 1348 notifier()->next(edge)) { 1349 edges.push_back(edge); 1350 } 1351 for (int i = edges.size() - 1; i >= 0; --i) { 1352 snapshot.addEdge(edges[i]); 1331 1353 } 1332 1354 } 1333 1355 virtual void clear() { 1334 Edge arc;1335 for (notifier()->first( arc); arc!= INVALID;1336 notifier()->next( arc)) {1337 snapshot.eraseEdge( arc);1356 Edge edge; 1357 for (notifier()->first(edge); edge != INVALID; 1358 notifier()->next(edge)) { 1359 snapshot.eraseEdge(edge); 1338 1360 } 1339 1361 } … … 1341 1363 Snapshot& snapshot; 1342 1364 }; 1343 1344 ListGraph * digraph;1365 1366 ListGraph *graph; 1345 1367 1346 1368 NodeObserverProxy node_observer_proxy; 1347 EdgeObserverProxy arc_observer_proxy;1369 EdgeObserverProxy edge_observer_proxy; 1348 1370 1349 1371 std::list<Node> added_nodes; 1350 std::list<Edge> added_ arcs;1372 std::list<Edge> added_edges; 1351 1373 1352 1374 … … 1359 1381 if (it == added_nodes.end()) { 1360 1382 clear(); 1361 arc_observer_proxy.detach();1383 edge_observer_proxy.detach(); 1362 1384 throw NodeNotifier::ImmediateDetach(); 1363 1385 } else { … … 1366 1388 } 1367 1389 1368 void addEdge(const Edge& arc) {1369 added_ arcs.push_front(arc);1370 } 1371 void eraseEdge(const Edge& arc) {1390 void addEdge(const Edge& edge) { 1391 added_edges.push_front(edge); 1392 } 1393 void eraseEdge(const Edge& edge) { 1372 1394 std::list<Edge>::iterator it = 1373 std::find(added_ arcs.begin(), added_arcs.end(), arc);1374 if (it == added_ arcs.end()) {1395 std::find(added_edges.begin(), added_edges.end(), edge); 1396 if (it == added_edges.end()) { 1375 1397 clear(); 1376 1398 node_observer_proxy.detach(); 1377 1399 throw EdgeNotifier::ImmediateDetach(); 1378 1400 } else { 1379 added_ arcs.erase(it);1380 } 1381 } 1382 1383 void attach(ListGraph &_ digraph) {1384 digraph = &_digraph;1385 node_observer_proxy.attach( digraph->notifier(Node()));1386 arc_observer_proxy.attach(digraph->notifier(Edge()));1401 added_edges.erase(it); 1402 } 1403 } 1404 1405 void attach(ListGraph &_graph) { 1406 graph = &_graph; 1407 node_observer_proxy.attach(graph->notifier(Node())); 1408 edge_observer_proxy.attach(graph->notifier(Edge())); 1387 1409 } 1388 1410 1389 1411 void detach() { 1390 1412 node_observer_proxy.detach(); 1391 arc_observer_proxy.detach();1413 edge_observer_proxy.detach(); 1392 1414 } 1393 1415 … … 1398 1420 void clear() { 1399 1421 added_nodes.clear(); 1400 added_ arcs.clear();1422 added_edges.clear(); 1401 1423 } 1402 1424 … … 1408 1430 /// To actually make a snapshot you must call save(). 1409 1431 Snapshot() 1410 : digraph(0), node_observer_proxy(*this),1411 arc_observer_proxy(*this) {}1432 : graph(0), node_observer_proxy(*this), 1433 edge_observer_proxy(*this) {} 1412 1434 1413 1435 /// \brief Constructor that immediately makes a snapshot. 1414 1436 /// 1415 /// This constructor immediately makes a snapshot of the digraph.1416 /// \param _ digraph The digraph we make a snapshot of.1417 Snapshot(ListGraph &_ digraph)1437 /// This constructor immediately makes a snapshot of the graph. 1438 /// \param _graph The graph we make a snapshot of. 1439 Snapshot(ListGraph &_graph) 1418 1440 : node_observer_proxy(*this), 1419 arc_observer_proxy(*this) {1420 attach(_ digraph);1441 edge_observer_proxy(*this) { 1442 attach(_graph); 1421 1443 } 1422 1444 1423 1445 /// \brief Make a snapshot. 1424 1446 /// 1425 /// Make a snapshot of the digraph.1447 /// Make a snapshot of the graph. 1426 1448 /// 1427 1449 /// This function can be called more than once. In case of a repeated 1428 1450 /// call, the previous snapshot gets lost. 1429 /// \param _ digraph The digraph we make the snapshot of.1430 void save(ListGraph &_ digraph) {1451 /// \param _graph The graph we make the snapshot of. 1452 void save(ListGraph &_graph) { 1431 1453 if (attached()) { 1432 1454 detach(); 1433 1455 clear(); 1434 1456 } 1435 attach(_ digraph);1457 attach(_graph); 1436 1458 } 1437 1459 … … 1441 1463 void restore() { 1442 1464 detach(); 1443 for(std::list<Edge>::iterator it = added_ arcs.begin();1444 it != added_ arcs.end(); ++it) {1445 digraph->erase(*it);1465 for(std::list<Edge>::iterator it = added_edges.begin(); 1466 it != added_edges.end(); ++it) { 1467 graph->erase(*it); 1446 1468 } 1447 1469 for(std::list<Node>::iterator it = added_nodes.begin(); 1448 1470 it != added_nodes.end(); ++it) { 1449 digraph->erase(*it);1471 graph->erase(*it); 1450 1472 } 1451 1473 clear();
Note: See TracChangeset
for help on using the changeset viewer.