r821:f4b5c2d5449d
Tue, 25 Aug 2009 13:58:43
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -32,13 +32,13 @@ |
| 32 | 32 |
public: |
| 33 | 33 |
|
| 34 | 34 |
StaticDigraphBase() |
| 35 |
: node_num( |
|
| 35 |
: built(false), node_num(0), arc_num(0), |
|
| 36 | 36 |
node_first_out(NULL), node_first_in(NULL), |
| 37 | 37 |
arc_source(NULL), arc_target(NULL), |
| 38 | 38 |
arc_next_in(NULL), arc_next_out(NULL) {}
|
| 39 | 39 |
|
| 40 | 40 |
~StaticDigraphBase() {
|
| 41 |
if ( |
|
| 41 |
if (built) {
|
|
| 42 | 42 |
delete[] node_first_out; |
| 43 | 43 |
delete[] node_first_in; |
| 44 | 44 |
delete[] arc_source; |
| ... | ... |
@@ -128,10 +128,8 @@ |
| 128 | 128 |
|
| 129 | 129 |
typedef True BuildTag; |
| 130 | 130 |
|
| 131 |
template <typename Digraph, typename NodeRefMap, typename ArcRefMap> |
|
| 132 |
void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
|
|
| 133 |
|
|
| 134 |
if (node_num != -1) {
|
|
| 131 |
void clear() {
|
|
| 132 |
if (built) {
|
|
| 135 | 133 |
delete[] node_first_out; |
| 136 | 134 |
delete[] node_first_in; |
| 137 | 135 |
delete[] arc_source; |
| ... | ... |
@@ -139,10 +137,18 @@ |
| 139 | 137 |
delete[] arc_next_out; |
| 140 | 138 |
delete[] arc_next_in; |
| 141 | 139 |
} |
| 142 |
|
|
| 140 |
built = false; |
|
| 141 |
node_num = 0; |
|
| 142 |
arc_num = 0; |
|
| 143 |
} |
|
| 144 |
|
|
| 145 |
template <typename Digraph, typename NodeRefMap, typename ArcRefMap> |
|
| 146 |
void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
|
|
| 143 | 147 |
typedef typename Digraph::Node GNode; |
| 144 | 148 |
typedef typename Digraph::Arc GArc; |
| 145 | 149 |
|
| 150 |
built = true; |
|
| 151 |
|
|
| 146 | 152 |
node_num = countNodes(digraph); |
| 147 | 153 |
arc_num = countArcs(digraph); |
| 148 | 154 |
|
| ... | ... |
@@ -205,7 +211,8 @@ |
| 205 | 211 |
e.id = node_first_out[n.id + 1]; |
| 206 | 212 |
} |
| 207 | 213 |
|
| 208 |
|
|
| 214 |
protected: |
|
| 215 |
bool built; |
|
| 209 | 216 |
int node_num; |
| 210 | 217 |
int arc_num; |
| 211 | 218 |
int *node_first_out; |
| ... | ... |
@@ -223,6 +230,15 @@ |
| 223 | 230 |
public: |
| 224 | 231 |
|
| 225 | 232 |
typedef ExtendedStaticDigraphBase Parent; |
| 233 |
|
|
| 234 |
public: |
|
| 235 |
|
|
| 236 |
template <typename Digraph, typename NodeRefMap, typename ArcRefMap> |
|
| 237 |
void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
|
|
| 238 |
if (built) Parent::clear(); |
|
| 239 |
Parent::build(digraph, nodeRef, arcRef); |
|
| 240 |
} |
|
| 241 |
|
|
| 226 | 242 |
|
| 227 | 243 |
protected: |
| 228 | 244 |
|
| ... | ... |
@@ -261,6 +277,22 @@ |
| 261 | 277 |
Arc last; |
| 262 | 278 |
}; |
| 263 | 279 |
|
| 280 |
Node baseNode(const OutArcIt &arc) const {
|
|
| 281 |
return Parent::source(static_cast<const Arc&>(arc)); |
|
| 282 |
} |
|
| 283 |
|
|
| 284 |
Node runningNode(const OutArcIt &arc) const {
|
|
| 285 |
return Parent::target(static_cast<const Arc&>(arc)); |
|
| 286 |
} |
|
| 287 |
|
|
| 288 |
Node baseNode(const InArcIt &arc) const {
|
|
| 289 |
return Parent::target(static_cast<const Arc&>(arc)); |
|
| 290 |
} |
|
| 291 |
|
|
| 292 |
Node runningNode(const InArcIt &arc) const {
|
|
| 293 |
return Parent::source(static_cast<const Arc&>(arc)); |
|
| 294 |
} |
|
| 295 |
|
|
| 264 | 296 |
}; |
| 265 | 297 |
|
| 266 | 298 |
} |
| ... | ... |
@@ -19,6 +19,7 @@ |
| 19 | 19 |
#include <lemon/concepts/digraph.h> |
| 20 | 20 |
#include <lemon/list_graph.h> |
| 21 | 21 |
#include <lemon/smart_graph.h> |
| 22 |
#include <lemon/static_graph.h> |
|
| 22 | 23 |
#include <lemon/full_graph.h> |
| 23 | 24 |
|
| 24 | 25 |
#include "test_tools.h" |
| ... | ... |
@@ -317,6 +318,10 @@ |
| 317 | 318 |
checkConcept<ExtendableDigraphComponent<>, SmartDigraph>(); |
| 318 | 319 |
checkConcept<ClearableDigraphComponent<>, SmartDigraph>(); |
| 319 | 320 |
} |
| 321 |
{ // Checking StaticDigraph
|
|
| 322 |
checkConcept<Digraph, StaticDigraph>(); |
|
| 323 |
checkConcept<ClearableDigraphComponent<>, StaticDigraph>(); |
|
| 324 |
} |
|
| 320 | 325 |
{ // Checking FullDigraph
|
| 321 | 326 |
checkConcept<Digraph, FullDigraph>(); |
| 322 | 327 |
} |
| ... | ... |
@@ -372,6 +377,76 @@ |
| 372 | 377 |
check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); |
| 373 | 378 |
} |
| 374 | 379 |
|
| 380 |
void checkStaticDigraph() {
|
|
| 381 |
SmartDigraph g; |
|
| 382 |
SmartDigraph::NodeMap<StaticDigraph::Node> nref(g); |
|
| 383 |
SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g); |
|
| 384 |
|
|
| 385 |
StaticDigraph G; |
|
| 386 |
|
|
| 387 |
checkGraphNodeList(G, 0); |
|
| 388 |
checkGraphArcList(G, 0); |
|
| 389 |
|
|
| 390 |
G.build(g, nref, aref); |
|
| 391 |
|
|
| 392 |
checkGraphNodeList(G, 0); |
|
| 393 |
checkGraphArcList(G, 0); |
|
| 394 |
|
|
| 395 |
SmartDigraph::Node |
|
| 396 |
n1 = g.addNode(), |
|
| 397 |
n2 = g.addNode(), |
|
| 398 |
n3 = g.addNode(); |
|
| 399 |
|
|
| 400 |
G.build(g, nref, aref); |
|
| 401 |
|
|
| 402 |
checkGraphNodeList(G, 3); |
|
| 403 |
checkGraphArcList(G, 0); |
|
| 404 |
|
|
| 405 |
SmartDigraph::Arc a1 = g.addArc(n1, n2); |
|
| 406 |
|
|
| 407 |
G.build(g, nref, aref); |
|
| 408 |
|
|
| 409 |
check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2], |
|
| 410 |
"Wrong arc or wrong references"); |
|
| 411 |
checkGraphNodeList(G, 3); |
|
| 412 |
checkGraphArcList(G, 1); |
|
| 413 |
|
|
| 414 |
checkGraphOutArcList(G, nref[n1], 1); |
|
| 415 |
checkGraphOutArcList(G, nref[n2], 0); |
|
| 416 |
checkGraphOutArcList(G, nref[n3], 0); |
|
| 417 |
|
|
| 418 |
checkGraphInArcList(G, nref[n1], 0); |
|
| 419 |
checkGraphInArcList(G, nref[n2], 1); |
|
| 420 |
checkGraphInArcList(G, nref[n3], 0); |
|
| 421 |
|
|
| 422 |
checkGraphConArcList(G, 1); |
|
| 423 |
|
|
| 424 |
SmartDigraph::Arc |
|
| 425 |
a2 = g.addArc(n2, n1), |
|
| 426 |
a3 = g.addArc(n2, n3), |
|
| 427 |
a4 = g.addArc(n2, n3); |
|
| 428 |
|
|
| 429 |
digraphCopy(g, G).nodeRef(nref).run(); |
|
| 430 |
|
|
| 431 |
checkGraphNodeList(G, 3); |
|
| 432 |
checkGraphArcList(G, 4); |
|
| 433 |
|
|
| 434 |
checkGraphOutArcList(G, nref[n1], 1); |
|
| 435 |
checkGraphOutArcList(G, nref[n2], 3); |
|
| 436 |
checkGraphOutArcList(G, nref[n3], 0); |
|
| 437 |
|
|
| 438 |
checkGraphInArcList(G, nref[n1], 1); |
|
| 439 |
checkGraphInArcList(G, nref[n2], 1); |
|
| 440 |
checkGraphInArcList(G, nref[n3], 2); |
|
| 441 |
|
|
| 442 |
checkGraphConArcList(G, 4); |
|
| 443 |
|
|
| 444 |
checkNodeIds(G); |
|
| 445 |
checkArcIds(G); |
|
| 446 |
checkGraphNodeMap(G); |
|
| 447 |
checkGraphArcMap(G); |
|
| 448 |
} |
|
| 449 |
|
|
| 375 | 450 |
void checkFullDigraph(int num) {
|
| 376 | 451 |
typedef FullDigraph Digraph; |
| 377 | 452 |
DIGRAPH_TYPEDEFS(Digraph); |
| ... | ... |
@@ -419,6 +494,9 @@ |
| 419 | 494 |
checkDigraphSnapshot<SmartDigraph>(); |
| 420 | 495 |
checkDigraphValidity<SmartDigraph>(); |
| 421 | 496 |
} |
| 497 |
{ // Checking StaticDigraph
|
|
| 498 |
checkStaticDigraph(); |
|
| 499 |
} |
|
| 422 | 500 |
{ // Checking FullDigraph
|
| 423 | 501 |
checkFullDigraph(8); |
| 424 | 502 |
} |
0 comments (0 inline)