r821:f4b5c2d5449d
Tue, 25 Aug 2009 13:58:43
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -29,19 +29,19 @@ |
| 29 | 29 |
namespace lemon {
|
| 30 | 30 |
|
| 31 | 31 |
class StaticDigraphBase {
|
| 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; |
| 45 | 45 |
delete[] arc_target; |
| 46 | 46 |
delete[] arc_next_out; |
| 47 | 47 |
delete[] arc_next_in; |
| ... | ... |
@@ -125,27 +125,33 @@ |
| 125 | 125 |
}; |
| 126 | 126 |
|
| 127 | 127 |
public: |
| 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; |
| 138 | 136 |
delete[] arc_target; |
| 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 |
|
| 149 | 155 |
node_first_out = new int[node_num + 1]; |
| 150 | 156 |
node_first_in = new int[node_num]; |
| 151 | 157 |
|
| ... | ... |
@@ -202,13 +208,14 @@ |
| 202 | 208 |
++e.id; |
| 203 | 209 |
} |
| 204 | 210 |
void fastLastOut(Arc& e, const Node& n) const {
|
| 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; |
| 212 | 219 |
int *node_first_in; |
| 213 | 220 |
int *arc_source; |
| 214 | 221 |
int *arc_target; |
| ... | ... |
@@ -220,12 +227,21 @@ |
| 220 | 227 |
|
| 221 | 228 |
|
| 222 | 229 |
class StaticDigraph : public ExtendedStaticDigraphBase {
|
| 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 |
|
| 229 | 245 |
using Parent::fastFirstOut; |
| 230 | 246 |
using Parent::fastNextOut; |
| 231 | 247 |
using Parent::fastLastOut; |
| ... | ... |
@@ -258,11 +274,27 @@ |
| 258 | 274 |
} |
| 259 | 275 |
|
| 260 | 276 |
private: |
| 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 |
} |
| 267 | 299 |
|
| 268 | 300 |
#endif |
| ... | ... |
@@ -16,12 +16,13 @@ |
| 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 |
#include <lemon/static_graph.h> |
|
| 22 | 23 |
#include <lemon/full_graph.h> |
| 23 | 24 |
|
| 24 | 25 |
#include "test_tools.h" |
| 25 | 26 |
#include "graph_test.h" |
| 26 | 27 |
|
| 27 | 28 |
using namespace lemon; |
| ... | ... |
@@ -314,12 +315,16 @@ |
| 314 | 315 |
{ // Checking SmartDigraph
|
| 315 | 316 |
checkConcept<Digraph, SmartDigraph>(); |
| 316 | 317 |
checkConcept<AlterableDigraphComponent<>, SmartDigraph>(); |
| 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 |
} |
| 323 | 328 |
} |
| 324 | 329 |
|
| 325 | 330 |
template <typename Digraph> |
| ... | ... |
@@ -369,12 +374,82 @@ |
| 369 | 374 |
check(g.valid(e2), "Wrong validity check"); |
| 370 | 375 |
|
| 371 | 376 |
check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); |
| 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); |
| 378 | 453 |
Digraph G(num); |
| 379 | 454 |
|
| 380 | 455 |
checkGraphNodeList(G, num); |
| ... | ... |
@@ -416,12 +491,15 @@ |
| 416 | 491 |
{ // Checking SmartDigraph
|
| 417 | 492 |
checkDigraphBuild<SmartDigraph>(); |
| 418 | 493 |
checkDigraphSplit<SmartDigraph>(); |
| 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 |
} |
| 425 | 503 |
} |
| 426 | 504 |
|
| 427 | 505 |
int main() {
|
0 comments (0 inline)