Changeset 736:2e20aad15754 in lemon-main

Timestamp:

08/23/09 11:10:40 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Add reserve functions to ListGraph? and SmartGraph? (#311)
ListDigraph? and SmartDigraph? already have such functions.

Files:

• lemon/list_graph.h (modified) (1 diff)
• lemon/smart_graph.h (modified) (1 diff)
• test/digraph_test.cc (modified) (1 diff)
• test/graph_test.cc (modified) (1 diff)

lemon/list_graph.h

@@ -1312 +1312 @@
     }
 
+    /// Reserve memory for nodes.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveEdge()
+    void reserveNode(int n) { nodes.reserve(n); };
+
+    /// Reserve memory for edges.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveNode()
+    void reserveEdge(int m) { arcs.reserve(2 * m); };
+
     /// \brief Class to make a snapshot of the graph and restore
     /// it later.

lemon/smart_graph.h

@@ -692 +692 @@
     }
 
+    /// Reserve memory for nodes.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveEdge()
+    void reserveNode(int n) { nodes.reserve(n); };
+
+    /// Reserve memory for edges.
+
+    /// Using this function, it is possible to avoid superfluous memory
+    /// allocation: if you know that the graph you want to build will
+    /// be large (e.g. it will contain millions of nodes and/or edges),
+    /// then it is worth reserving space for this amount before starting
+    /// to build the graph.
+    /// \sa reserveNode()
+    void reserveEdge(int m) { arcs.reserve(2 * m); };
+
   public:
 

test/digraph_test.cc

@@ -36 +36 @@
   checkGraphArcList(G, 0);
 
+  G.reserveNode(3);
+  G.reserveArc(4);
+
   Node
     n1 = G.addNode(),

test/graph_test.cc

@@ -39 +39 @@
   checkGraphArcList(G, 0);
 
+  G.reserveNode(3);
+  G.reserveEdge(3);
+
   Node
     n1 = G.addNode(),