Small improvements + add tests for StaticDigraph (#68)
authorPeter Kovacs <kpeter@inf.elte.hu>
Tue, 25 Aug 2009 13:58:43 +0200
changeset 774f4b5c2d5449d
parent 773 cf360f758f25
child 775 6cab2ab9d8e7
Small improvements + add tests for StaticDigraph (#68)
lemon/static_graph.h
test/digraph_test.cc
     1.1 --- a/lemon/static_graph.h	Tue Aug 25 11:09:02 2009 +0200
     1.2 +++ b/lemon/static_graph.h	Tue Aug 25 13:58:43 2009 +0200
     1.3 @@ -32,13 +32,13 @@
     1.4    public:
     1.5  
     1.6      StaticDigraphBase() 
     1.7 -      : node_num(-1), arc_num(0), 
     1.8 +      : built(false), node_num(0), arc_num(0), 
     1.9          node_first_out(NULL), node_first_in(NULL),
    1.10          arc_source(NULL), arc_target(NULL), 
    1.11          arc_next_in(NULL), arc_next_out(NULL) {}
    1.12      
    1.13      ~StaticDigraphBase() {
    1.14 -      if (node_num != -1) {
    1.15 +      if (built) {
    1.16          delete[] node_first_out;
    1.17          delete[] node_first_in;
    1.18          delete[] arc_source;
    1.19 @@ -128,10 +128,8 @@
    1.20  
    1.21      typedef True BuildTag;
    1.22      
    1.23 -    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
    1.24 -    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
    1.25 -
    1.26 -      if (node_num != -1) {
    1.27 +    void clear() {
    1.28 +      if (built) {
    1.29          delete[] node_first_out;
    1.30          delete[] node_first_in;
    1.31          delete[] arc_source;
    1.32 @@ -139,10 +137,18 @@
    1.33          delete[] arc_next_out;
    1.34          delete[] arc_next_in;
    1.35        }
    1.36 -
    1.37 +      built = false;
    1.38 +      node_num = 0;
    1.39 +      arc_num = 0;
    1.40 +    }
    1.41 +    
    1.42 +    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
    1.43 +    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
    1.44        typedef typename Digraph::Node GNode;
    1.45        typedef typename Digraph::Arc GArc;
    1.46  
    1.47 +      built = true;
    1.48 +
    1.49        node_num = countNodes(digraph);
    1.50        arc_num = countArcs(digraph);
    1.51  
    1.52 @@ -205,7 +211,8 @@
    1.53        e.id = node_first_out[n.id + 1];
    1.54      }
    1.55  
    1.56 -  private:
    1.57 +  protected:
    1.58 +    bool built;
    1.59      int node_num;
    1.60      int arc_num;
    1.61      int *node_first_out;
    1.62 @@ -223,6 +230,15 @@
    1.63    public:
    1.64  
    1.65      typedef ExtendedStaticDigraphBase Parent;
    1.66 +  
    1.67 +  public:
    1.68 +  
    1.69 +    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
    1.70 +    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
    1.71 +      if (built) Parent::clear();
    1.72 +      Parent::build(digraph, nodeRef, arcRef);
    1.73 +    }
    1.74 +  
    1.75  
    1.76    protected:
    1.77  
    1.78 @@ -261,6 +277,22 @@
    1.79        Arc last;
    1.80      };
    1.81  
    1.82 +    Node baseNode(const OutArcIt &arc) const {
    1.83 +      return Parent::source(static_cast<const Arc&>(arc));
    1.84 +    }
    1.85 +
    1.86 +    Node runningNode(const OutArcIt &arc) const {
    1.87 +      return Parent::target(static_cast<const Arc&>(arc));
    1.88 +    }
    1.89 +
    1.90 +    Node baseNode(const InArcIt &arc) const {
    1.91 +      return Parent::target(static_cast<const Arc&>(arc));
    1.92 +    }
    1.93 +
    1.94 +    Node runningNode(const InArcIt &arc) const {
    1.95 +      return Parent::source(static_cast<const Arc&>(arc));
    1.96 +    }
    1.97 +
    1.98    };
    1.99  
   1.100  }
     2.1 --- a/test/digraph_test.cc	Tue Aug 25 11:09:02 2009 +0200
     2.2 +++ b/test/digraph_test.cc	Tue Aug 25 13:58:43 2009 +0200
     2.3 @@ -19,6 +19,7 @@
     2.4  #include <lemon/concepts/digraph.h>
     2.5  #include <lemon/list_graph.h>
     2.6  #include <lemon/smart_graph.h>
     2.7 +#include <lemon/static_graph.h>
     2.8  #include <lemon/full_graph.h>
     2.9  
    2.10  #include "test_tools.h"
    2.11 @@ -317,6 +318,10 @@
    2.12      checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
    2.13      checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    2.14    }
    2.15 +  { // Checking StaticDigraph
    2.16 +    checkConcept<Digraph, StaticDigraph>();
    2.17 +    checkConcept<ClearableDigraphComponent<>, StaticDigraph>();
    2.18 +  }
    2.19    { // Checking FullDigraph
    2.20      checkConcept<Digraph, FullDigraph>();
    2.21    }
    2.22 @@ -372,6 +377,76 @@
    2.23    check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
    2.24  }
    2.25  
    2.26 +void checkStaticDigraph() {
    2.27 +  SmartDigraph g;
    2.28 +  SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
    2.29 +  SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
    2.30 +  
    2.31 +  StaticDigraph G;
    2.32 +  
    2.33 +  checkGraphNodeList(G, 0);
    2.34 +  checkGraphArcList(G, 0);
    2.35 +
    2.36 +  G.build(g, nref, aref);
    2.37 +
    2.38 +  checkGraphNodeList(G, 0);
    2.39 +  checkGraphArcList(G, 0);
    2.40 +
    2.41 +  SmartDigraph::Node
    2.42 +    n1 = g.addNode(),
    2.43 +    n2 = g.addNode(),
    2.44 +    n3 = g.addNode();
    2.45 +
    2.46 +  G.build(g, nref, aref);
    2.47 +
    2.48 +  checkGraphNodeList(G, 3);
    2.49 +  checkGraphArcList(G, 0);
    2.50 +
    2.51 +  SmartDigraph::Arc a1 = g.addArc(n1, n2);
    2.52 +
    2.53 +  G.build(g, nref, aref);
    2.54 +
    2.55 +  check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],
    2.56 +        "Wrong arc or wrong references");
    2.57 +  checkGraphNodeList(G, 3);
    2.58 +  checkGraphArcList(G, 1);
    2.59 +
    2.60 +  checkGraphOutArcList(G, nref[n1], 1);
    2.61 +  checkGraphOutArcList(G, nref[n2], 0);
    2.62 +  checkGraphOutArcList(G, nref[n3], 0);
    2.63 +
    2.64 +  checkGraphInArcList(G, nref[n1], 0);
    2.65 +  checkGraphInArcList(G, nref[n2], 1);
    2.66 +  checkGraphInArcList(G, nref[n3], 0);
    2.67 +
    2.68 +  checkGraphConArcList(G, 1);
    2.69 +
    2.70 +  SmartDigraph::Arc
    2.71 +    a2 = g.addArc(n2, n1),
    2.72 +    a3 = g.addArc(n2, n3),
    2.73 +    a4 = g.addArc(n2, n3);
    2.74 +
    2.75 +  digraphCopy(g, G).nodeRef(nref).run();
    2.76 +
    2.77 +  checkGraphNodeList(G, 3);
    2.78 +  checkGraphArcList(G, 4);
    2.79 +
    2.80 +  checkGraphOutArcList(G, nref[n1], 1);
    2.81 +  checkGraphOutArcList(G, nref[n2], 3);
    2.82 +  checkGraphOutArcList(G, nref[n3], 0);
    2.83 +
    2.84 +  checkGraphInArcList(G, nref[n1], 1);
    2.85 +  checkGraphInArcList(G, nref[n2], 1);
    2.86 +  checkGraphInArcList(G, nref[n3], 2);
    2.87 +
    2.88 +  checkGraphConArcList(G, 4);
    2.89 +
    2.90 +  checkNodeIds(G);
    2.91 +  checkArcIds(G);
    2.92 +  checkGraphNodeMap(G);
    2.93 +  checkGraphArcMap(G);
    2.94 +}
    2.95 +
    2.96  void checkFullDigraph(int num) {
    2.97    typedef FullDigraph Digraph;
    2.98    DIGRAPH_TYPEDEFS(Digraph);
    2.99 @@ -419,6 +494,9 @@
   2.100      checkDigraphSnapshot<SmartDigraph>();
   2.101      checkDigraphValidity<SmartDigraph>();
   2.102    }
   2.103 +  { // Checking StaticDigraph
   2.104 +    checkStaticDigraph();
   2.105 +  }
   2.106    { // Checking FullDigraph
   2.107      checkFullDigraph(8);
   2.108    }