gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Add reserve functions to ListGraph and SmartGraph (#311) ListDigraph and SmartDigraph already have such functions.
0 4 0
default
4 files changed with 46 insertions and 0 deletions:
↑ Collapse diff ↑
Ignore white space 6 line context
... ...
@@ -1290,48 +1290,68 @@
1290 1290
    ///Snapshot feature.
1291 1291
    void contract(Node a, Node b, bool r = true) {
1292 1292
      for(IncEdgeIt e(*this, b); e!=INVALID;) {
1293 1293
        IncEdgeIt f = e; ++f;
1294 1294
        if (r && runningNode(e) == a) {
1295 1295
          erase(e);
1296 1296
        } else if (u(e) == b) {
1297 1297
          changeU(e, a);
1298 1298
        } else {
1299 1299
          changeV(e, a);
1300 1300
        }
1301 1301
        e = f;
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
    ///
1326 1346
    /// \warning Node and edge deletions and other modifications
1327 1347
    /// (e.g. changing the end-nodes of edges or contracting nodes)
1328 1348
    /// cannot be restored. These events invalidate the snapshot.
1329 1349
    /// However the edges and nodes that were added to the graph after
1330 1350
    /// making the current snapshot can be removed without invalidating it.
1331 1351
    class Snapshot {
1332 1352
    protected:
1333 1353

	
1334 1354
      typedef Parent::NodeNotifier NodeNotifier;
1335 1355

	
1336 1356
      class NodeObserverProxy : public NodeNotifier::ObserverBase {
1337 1357
      public:
Ignore white space 48 line context
... ...
@@ -670,48 +670,68 @@
670 670
    /// This function gives back \c true if the given edge is valid,
671 671
    /// i.e. it is a real edge of the graph.
672 672
    ///
673 673
    /// \warning A removed edge (using Snapshot) could become valid again
674 674
    /// if new edges are added to the graph.
675 675
    bool valid(Edge e) const { return Parent::valid(e); }
676 676

	
677 677
    /// \brief Arc validity check
678 678
    ///
679 679
    /// This function gives back \c true if the given arc is valid,
680 680
    /// i.e. it is a real arc of the graph.
681 681
    ///
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
    }
706 726

	
707 727
    void restoreSnapshot(const Snapshot &s)
708 728
    {
709 729
      while(s.arc_num<arcs.size()) {
710 730
        int n=arcs.size()-1;
711 731
        Edge arc=edgeFromId(n/2);
712 732
        Parent::notifier(Edge()).erase(arc);
713 733
        std::vector<Arc> dir;
714 734
        dir.push_back(arcFromId(n));
715 735
        dir.push_back(arcFromId(n-1));
716 736
        Parent::notifier(Arc()).erase(dir);
717 737
        nodes[arcs[n-1].target].first_out=arcs[n].next_out;
Ignore white space 6 line context
... ...
@@ -14,48 +14,51 @@
14 14
 * express or implied, and with no claim as to its suitability for any
15 15
 * purpose.
16 16
 *
17 17
 */
18 18

	
19 19
#include <lemon/concepts/digraph.h>
20 20
#include <lemon/list_graph.h>
21 21
#include <lemon/smart_graph.h>
22 22
#include <lemon/full_graph.h>
23 23

	
24 24
#include "test_tools.h"
25 25
#include "graph_test.h"
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

	
50 53
  checkGraphOutArcList(G, n1, 1);
51 54
  checkGraphOutArcList(G, n2, 0);
52 55
  checkGraphOutArcList(G, n3, 0);
53 56

	
54 57
  checkGraphInArcList(G, n1, 0);
55 58
  checkGraphInArcList(G, n2, 1);
56 59
  checkGraphInArcList(G, n3, 0);
57 60

	
58 61
  checkGraphConArcList(G, 1);
59 62

	
60 63
  Arc a2 = G.addArc(n2, n1),
61 64
      a3 = G.addArc(n2, n3),
Ignore white space 6 line context
... ...
@@ -17,48 +17,51 @@
17 17
 */
18 18

	
19 19
#include <lemon/concepts/graph.h>
20 20
#include <lemon/list_graph.h>
21 21
#include <lemon/smart_graph.h>
22 22
#include <lemon/full_graph.h>
23 23
#include <lemon/grid_graph.h>
24 24
#include <lemon/hypercube_graph.h>
25 25

	
26 26
#include "test_tools.h"
27 27
#include "graph_test.h"
28 28

	
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

	
53 56
  checkGraphNodeList(G, 3);
54 57
  checkGraphEdgeList(G, 1);
55 58
  checkGraphArcList(G, 2);
56 59

	
57 60
  checkGraphIncEdgeArcLists(G, n1, 1);
58 61
  checkGraphIncEdgeArcLists(G, n2, 1);
59 62
  checkGraphIncEdgeArcLists(G, n3, 0);
60 63

	
61 64
  checkGraphConEdgeList(G, 1);
62 65
  checkGraphConArcList(G, 2);
63 66

	
64 67
  Edge e2 = G.addEdge(n2, n1),
0 comments (0 inline)