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 }