r783:2e20aad15754
Sun, 23 Aug 2009 11:10:40
[Not Reviewed]
0 comments (0 inline)
0
4
0
| ... | ... |
@@ -1302,24 +1302,44 @@ |
| 1302 | 1302 |
} |
| 1303 | 1303 |
erase(b); |
| 1304 | 1304 |
} |
| 1305 | 1305 |
|
| 1306 | 1306 |
///Clear the graph. |
| 1307 | 1307 |
|
| 1308 | 1308 |
///This function erases all nodes and arcs from the graph. |
| 1309 | 1309 |
/// |
| 1310 | 1310 |
void clear() {
|
| 1311 | 1311 |
Parent::clear(); |
| 1312 | 1312 |
} |
| 1313 | 1313 |
|
| 1314 |
/// Reserve memory for nodes. |
|
| 1315 |
|
|
| 1316 |
/// Using this function, it is possible to avoid superfluous memory |
|
| 1317 |
/// allocation: if you know that the graph you want to build will |
|
| 1318 |
/// be large (e.g. it will contain millions of nodes and/or edges), |
|
| 1319 |
/// then it is worth reserving space for this amount before starting |
|
| 1320 |
/// to build the graph. |
|
| 1321 |
/// \sa reserveEdge() |
|
| 1322 |
void reserveNode(int n) { nodes.reserve(n); };
|
|
| 1323 |
|
|
| 1324 |
/// Reserve memory for edges. |
|
| 1325 |
|
|
| 1326 |
/// Using this function, it is possible to avoid superfluous memory |
|
| 1327 |
/// allocation: if you know that the graph you want to build will |
|
| 1328 |
/// be large (e.g. it will contain millions of nodes and/or edges), |
|
| 1329 |
/// then it is worth reserving space for this amount before starting |
|
| 1330 |
/// to build the graph. |
|
| 1331 |
/// \sa reserveNode() |
|
| 1332 |
void reserveEdge(int m) { arcs.reserve(2 * m); };
|
|
| 1333 |
|
|
| 1314 | 1334 |
/// \brief Class to make a snapshot of the graph and restore |
| 1315 | 1335 |
/// it later. |
| 1316 | 1336 |
/// |
| 1317 | 1337 |
/// Class to make a snapshot of the graph and restore it later. |
| 1318 | 1338 |
/// |
| 1319 | 1339 |
/// The newly added nodes and edges can be removed |
| 1320 | 1340 |
/// using the restore() function. |
| 1321 | 1341 |
/// |
| 1322 | 1342 |
/// \note After a state is restored, you cannot restore a later state, |
| 1323 | 1343 |
/// i.e. you cannot add the removed nodes and edges again using |
| 1324 | 1344 |
/// another Snapshot instance. |
| 1325 | 1345 |
/// |
| ... | ... |
@@ -682,24 +682,44 @@ |
| 682 | 682 |
/// \warning A removed arc (using Snapshot) could become valid again |
| 683 | 683 |
/// if new edges are added to the graph. |
| 684 | 684 |
bool valid(Arc a) const { return Parent::valid(a); }
|
| 685 | 685 |
|
| 686 | 686 |
///Clear the graph. |
| 687 | 687 |
|
| 688 | 688 |
///This function erases all nodes and arcs from the graph. |
| 689 | 689 |
/// |
| 690 | 690 |
void clear() {
|
| 691 | 691 |
Parent::clear(); |
| 692 | 692 |
} |
| 693 | 693 |
|
| 694 |
/// Reserve memory for nodes. |
|
| 695 |
|
|
| 696 |
/// Using this function, it is possible to avoid superfluous memory |
|
| 697 |
/// allocation: if you know that the graph you want to build will |
|
| 698 |
/// be large (e.g. it will contain millions of nodes and/or edges), |
|
| 699 |
/// then it is worth reserving space for this amount before starting |
|
| 700 |
/// to build the graph. |
|
| 701 |
/// \sa reserveEdge() |
|
| 702 |
void reserveNode(int n) { nodes.reserve(n); };
|
|
| 703 |
|
|
| 704 |
/// Reserve memory for edges. |
|
| 705 |
|
|
| 706 |
/// Using this function, it is possible to avoid superfluous memory |
|
| 707 |
/// allocation: if you know that the graph you want to build will |
|
| 708 |
/// be large (e.g. it will contain millions of nodes and/or edges), |
|
| 709 |
/// then it is worth reserving space for this amount before starting |
|
| 710 |
/// to build the graph. |
|
| 711 |
/// \sa reserveNode() |
|
| 712 |
void reserveEdge(int m) { arcs.reserve(2 * m); };
|
|
| 713 |
|
|
| 694 | 714 |
public: |
| 695 | 715 |
|
| 696 | 716 |
class Snapshot; |
| 697 | 717 |
|
| 698 | 718 |
protected: |
| 699 | 719 |
|
| 700 | 720 |
void saveSnapshot(Snapshot &s) |
| 701 | 721 |
{
|
| 702 | 722 |
s._graph = this; |
| 703 | 723 |
s.node_num = nodes.size(); |
| 704 | 724 |
s.arc_num = arcs.size(); |
| 705 | 725 |
} |
| ... | ... |
@@ -26,24 +26,27 @@ |
| 26 | 26 |
|
| 27 | 27 |
using namespace lemon; |
| 28 | 28 |
using namespace lemon::concepts; |
| 29 | 29 |
|
| 30 | 30 |
template <class Digraph> |
| 31 | 31 |
void checkDigraphBuild() {
|
| 32 | 32 |
TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
| 33 | 33 |
Digraph G; |
| 34 | 34 |
|
| 35 | 35 |
checkGraphNodeList(G, 0); |
| 36 | 36 |
checkGraphArcList(G, 0); |
| 37 | 37 |
|
| 38 |
G.reserveNode(3); |
|
| 39 |
G.reserveArc(4); |
|
| 40 |
|
|
| 38 | 41 |
Node |
| 39 | 42 |
n1 = G.addNode(), |
| 40 | 43 |
n2 = G.addNode(), |
| 41 | 44 |
n3 = G.addNode(); |
| 42 | 45 |
checkGraphNodeList(G, 3); |
| 43 | 46 |
checkGraphArcList(G, 0); |
| 44 | 47 |
|
| 45 | 48 |
Arc a1 = G.addArc(n1, n2); |
| 46 | 49 |
check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc"); |
| 47 | 50 |
checkGraphNodeList(G, 3); |
| 48 | 51 |
checkGraphArcList(G, 1); |
| 49 | 52 |
| ... | ... |
@@ -29,24 +29,27 @@ |
| 29 | 29 |
using namespace lemon; |
| 30 | 30 |
using namespace lemon::concepts; |
| 31 | 31 |
|
| 32 | 32 |
template <class Graph> |
| 33 | 33 |
void checkGraphBuild() {
|
| 34 | 34 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
| 35 | 35 |
|
| 36 | 36 |
Graph G; |
| 37 | 37 |
checkGraphNodeList(G, 0); |
| 38 | 38 |
checkGraphEdgeList(G, 0); |
| 39 | 39 |
checkGraphArcList(G, 0); |
| 40 | 40 |
|
| 41 |
G.reserveNode(3); |
|
| 42 |
G.reserveEdge(3); |
|
| 43 |
|
|
| 41 | 44 |
Node |
| 42 | 45 |
n1 = G.addNode(), |
| 43 | 46 |
n2 = G.addNode(), |
| 44 | 47 |
n3 = G.addNode(); |
| 45 | 48 |
checkGraphNodeList(G, 3); |
| 46 | 49 |
checkGraphEdgeList(G, 0); |
| 47 | 50 |
checkGraphArcList(G, 0); |
| 48 | 51 |
|
| 49 | 52 |
Edge e1 = G.addEdge(n1, n2); |
| 50 | 53 |
check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), |
| 51 | 54 |
"Wrong edge"); |
| 52 | 55 |
|
0 comments (0 inline)