Changeset 909:6a22e0dfd453 in lemon-0.x for src/hugo/smart_graph.h
- Timestamp:
- 09/26/04 23:43:38 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1220
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/smart_graph.h
r906 r909 28 28 29 29 #include <hugo/array_map.h> 30 #include <hugo/sym_map.h>31 32 30 #include <hugo/map_registry.h> 33 31 … … 299 297 }; 300 298 299 300 301 class SymSmartGraph : public SmartGraph { 302 typedef SmartGraph Parent; 303 public: 304 305 typedef SymSmartGraph Graph; 306 307 typedef SmartGraph::Node Node; 308 typedef SmartGraph::NodeIt NodeIt; 309 310 class SymEdge; 311 class SymEdgeIt; 312 313 class Edge; 314 class EdgeIt; 315 class OutEdgeIt; 316 class InEdgeIt; 317 318 template <typename Value> 319 class NodeMap : public Parent::NodeMap<Value> { 320 public: 321 NodeMap(const SymSmartGraph& g) 322 : SymSmartGraph::Parent::NodeMap<Value>(g) {} 323 NodeMap(const SymSmartGraph& g, Value v) 324 : SymSmartGraph::Parent::NodeMap<Value>(g, v) {} 325 template<typename TT> 326 NodeMap(const NodeMap<TT>& copy) 327 : SymSmartGraph::Parent::NodeMap<Value>(copy) { } 328 }; 329 330 template <typename Value> 331 class SymEdgeMap : public Parent::EdgeMap<Value> { 332 public: 333 typedef SymEdge KeyType; 334 335 SymEdgeMap(const SymSmartGraph& g) 336 : SymSmartGraph::Parent::EdgeMap<Value>(g) {} 337 SymEdgeMap(const SymSmartGraph& g, Value v) 338 : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {} 339 template<typename TT> 340 SymEdgeMap(const SymEdgeMap<TT>& copy) 341 : SymSmartGraph::Parent::EdgeMap<Value>(copy) { } 342 343 }; 344 345 // Create edge map registry. 346 CREATE_EDGE_MAP_REGISTRY; 347 // Create edge maps. 348 CREATE_EDGE_MAP(ArrayMap); 349 350 class Edge { 351 friend class SymSmartGraph; 352 friend class SymSmartGraph::EdgeIt; 353 friend class SymSmartGraph::OutEdgeIt; 354 friend class SymSmartGraph::InEdgeIt; 355 356 protected: 357 int id; 358 359 Edge(int pid) { id = pid; } 360 361 public: 362 /// An Edge with id \c n. 363 364 Edge() { } 365 Edge (Invalid) { id = -1; } 366 367 operator SymEdge(){ return SymEdge(id >> 1);} 368 369 bool operator==(const Edge i) const {return id == i.id;} 370 bool operator!=(const Edge i) const {return id != i.id;} 371 bool operator<(const Edge i) const {return id < i.id;} 372 // ///Validity check 373 // operator bool() { return n!=-1; } 374 }; 375 376 class SymEdge : public SmartGraph::Edge { 377 friend class SymSmartGraph; 378 friend class SymSmartGraph::Edge; 379 typedef SmartGraph::Edge Parent; 380 381 protected: 382 SymEdge(int pid) : Parent(pid) {} 383 public: 384 385 SymEdge() { } 386 SymEdge(const SmartGraph::Edge& i) : Parent(i) {} 387 SymEdge (Invalid) : Parent(INVALID) {} 388 389 }; 390 391 class OutEdgeIt { 392 Parent::OutEdgeIt out; 393 Parent::InEdgeIt in; 394 public: 395 OutEdgeIt() {} 396 OutEdgeIt(const SymSmartGraph& g, Edge e) { 397 if (e.id & 1 == 0) { 398 out = Parent::OutEdgeIt(g, SymEdge(e)); 399 in = Parent::InEdgeIt(g, g.tail(e)); 400 } else { 401 out = Parent::OutEdgeIt(INVALID); 402 in = Parent::InEdgeIt(g, SymEdge(e)); 403 } 404 } 405 OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } 406 407 OutEdgeIt(const SymSmartGraph& g, const Node v) 408 : out(g, v), in(g, v) {} 409 OutEdgeIt &operator++() { 410 if (out != INVALID) { 411 ++out; 412 } else { 413 ++in; 414 } 415 return *this; 416 } 417 418 operator Edge() const { 419 if (out == INVALID && in == INVALID) return INVALID; 420 return out != INVALID ? forward(out) : backward(in); 421 } 422 423 bool operator==(const Edge i) const {return Edge(*this) == i;} 424 bool operator!=(const Edge i) const {return Edge(*this) != i;} 425 bool operator<(const Edge i) const {return Edge(*this) < i;} 426 }; 427 428 class InEdgeIt { 429 Parent::OutEdgeIt out; 430 Parent::InEdgeIt in; 431 public: 432 InEdgeIt() {} 433 InEdgeIt(const SymSmartGraph& g, Edge e) { 434 if (e.id & 1 == 0) { 435 out = Parent::OutEdgeIt(g, SymEdge(e)); 436 in = Parent::InEdgeIt(g, g.tail(e)); 437 } else { 438 out = Parent::OutEdgeIt(INVALID); 439 in = Parent::InEdgeIt(g, SymEdge(e)); 440 } 441 } 442 InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } 443 444 InEdgeIt(const SymSmartGraph& g, const Node v) 445 : out(g, v), in(g, v) {} 446 447 InEdgeIt &operator++() { 448 if (out != INVALID) { 449 ++out; 450 } else { 451 ++in; 452 } 453 return *this; 454 } 455 456 operator Edge() const { 457 if (out == INVALID && in == INVALID) return INVALID; 458 return out != INVALID ? backward(out) : forward(in); 459 } 460 461 bool operator==(const Edge i) const {return Edge(*this) == i;} 462 bool operator!=(const Edge i) const {return Edge(*this) != i;} 463 bool operator<(const Edge i) const {return Edge(*this) < i;} 464 }; 465 466 class SymEdgeIt : public Parent::EdgeIt { 467 468 public: 469 SymEdgeIt() {} 470 471 SymEdgeIt(const SymSmartGraph& g) 472 : SymSmartGraph::Parent::EdgeIt(g) {} 473 474 SymEdgeIt(const SymSmartGraph& g, SymEdge e) 475 : SymSmartGraph::Parent::EdgeIt(g, e) {} 476 477 SymEdgeIt(Invalid i) 478 : SymSmartGraph::Parent::EdgeIt(INVALID) {} 479 480 SymEdgeIt& operator++() { 481 SymSmartGraph::Parent::EdgeIt::operator++(); 482 return *this; 483 } 484 485 operator SymEdge() const { 486 return SymEdge 487 (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this)); 488 } 489 bool operator==(const SymEdge i) const {return SymEdge(*this) == i;} 490 bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;} 491 bool operator<(const SymEdge i) const {return SymEdge(*this) < i;} 492 }; 493 494 class EdgeIt { 495 SymEdgeIt it; 496 bool fw; 497 public: 498 EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {} 499 EdgeIt (Invalid i) : it(i) { } 500 EdgeIt(const SymSmartGraph& g, Edge e) 501 : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { } 502 EdgeIt() { } 503 EdgeIt& operator++() { 504 fw = !fw; 505 if (fw) ++it; 506 return *this; 507 } 508 operator Edge() const { 509 if (it == INVALID) return INVALID; 510 return fw ? forward(it) : backward(it); 511 } 512 bool operator==(const Edge i) const {return Edge(*this) == i;} 513 bool operator!=(const Edge i) const {return Edge(*this) != i;} 514 bool operator<(const Edge i) const {return Edge(*this) < i;} 515 516 }; 517 518 ///Number of nodes. 519 int nodeNum() const { return Parent::nodeNum(); } 520 ///Number of edges. 521 int edgeNum() const { return 2*Parent::edgeNum(); } 522 ///Number of symmetric edges. 523 int symEdgeNum() const { return Parent::edgeNum(); } 524 525 /// Maximum node ID. 526 527 /// Maximum node ID. 528 ///\sa id(Node) 529 int maxNodeId() const { return Parent::maxNodeId(); } 530 /// Maximum edge ID. 531 532 /// Maximum edge ID. 533 ///\sa id(Edge) 534 int maxEdgeId() const { return 2*Parent::maxEdgeId(); } 535 /// Maximum symmetric edge ID. 536 537 /// Maximum symmetric edge ID. 538 ///\sa id(SymEdge) 539 int maxSymEdgeId() const { return Parent::maxEdgeId(); } 540 541 542 Node tail(Edge e) const { 543 return e.id & 1 == 0 ? 544 Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e)); 545 } 546 547 Node head(Edge e) const { 548 return e.id & 1 == 0 ? 549 Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e)); 550 } 551 552 Node tail(SymEdge e) const { 553 return Parent::tail(e); 554 } 555 556 Node head(SymEdge e) const { 557 return Parent::head(e); 558 } 559 560 NodeIt& first(NodeIt& v) const { 561 v=NodeIt(*this); return v; } 562 EdgeIt& first(EdgeIt& e) const { 563 e=EdgeIt(*this); return e; } 564 SymEdgeIt& first(SymEdgeIt& e) const { 565 e=SymEdgeIt(*this); return e; } 566 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 567 e=OutEdgeIt(*this,v); return e; } 568 InEdgeIt& first(InEdgeIt& e, const Node v) const { 569 e=InEdgeIt(*this,v); return e; } 570 571 /// Node ID. 572 573 /// The ID of a valid Node is a nonnegative integer not greater than 574 /// \ref maxNodeId(). The range of the ID's is not surely continuous 575 /// and the greatest node ID can be actually less then \ref maxNodeId(). 576 /// 577 /// The ID of the \ref INVALID node is -1. 578 ///\return The ID of the node \c v. 579 static int id(Node v) { return Parent::id(v); } 580 /// Edge ID. 581 582 /// The ID of a valid Edge is a nonnegative integer not greater than 583 /// \ref maxEdgeId(). The range of the ID's is not surely continuous 584 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). 585 /// 586 /// The ID of the \ref INVALID edge is -1. 587 ///\return The ID of the edge \c e. 588 static int id(Edge e) { return e.id; } 589 590 /// The ID of a valid SymEdge is a nonnegative integer not greater than 591 /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous 592 /// and the greatest edge ID can be actually less then \ref maxSymEdgeId(). 593 /// 594 /// The ID of the \ref INVALID symmetric edge is -1. 595 ///\return The ID of the edge \c e. 596 static int id(SymEdge e) { return Parent::id(e); } 597 598 /// Adds a new node to the graph. 599 600 /// \warning It adds the new node to the front of the list. 601 /// (i.e. the lastly added node becomes the first.) 602 Node addNode() { 603 return Parent::addNode(); 604 } 605 606 SymEdge addEdge(Node u, Node v) { 607 SymEdge se = Parent::addEdge(u, v); 608 edge_maps.add(forward(se)); 609 edge_maps.add(backward(se)); 610 return se; 611 } 612 613 /// Finds an edge between two nodes. 614 615 /// Finds an edge from node \c u to node \c v. 616 /// 617 /// If \c prev is \ref INVALID (this is the default value), then 618 /// It finds the first edge from \c u to \c v. Otherwise it looks for 619 /// the next edge from \c u to \c v after \c prev. 620 /// \return The found edge or INVALID if there is no such an edge. 621 Edge findEdge(Node u, Node v, Edge prev = INVALID) 622 { 623 if (prev == INVALID || id(prev) & 1 == 0) { 624 SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); 625 if (se != INVALID) return forward(se); 626 } else { 627 SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); 628 if (se != INVALID) return backward(se); 629 } 630 return INVALID; 631 } 632 633 /// Finds an symmetric edge between two nodes. 634 635 /// Finds an symmetric edge from node \c u to node \c v. 636 /// 637 /// If \c prev is \ref INVALID (this is the default value), then 638 /// It finds the first edge from \c u to \c v. Otherwise it looks for 639 /// the next edge from \c u to \c v after \c prev. 640 /// \return The found edge or INVALID if there is no such an edge. 641 642 // SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID) 643 // { 644 // if (prev == INVALID || id(prev) & 1 == 0) { 645 // SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); 646 // if (se != INVALID) return se; 647 // } else { 648 // SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); 649 // if (se != INVALID) return se; 650 // } 651 // return INVALID; 652 // } 653 654 public: 655 656 void clear() { 657 edge_maps.clear(); 658 Parent::clear(); 659 } 660 661 static Edge opposite(Edge e) { 662 return Edge(id(e) ^ 1); 663 } 664 665 static Edge forward(SymEdge e) { 666 return Edge(id(e) << 1); 667 } 668 669 static Edge backward(SymEdge e) { 670 return Edge((id(e) << 1) & 1); 671 } 672 673 }; 301 674 ///Graph for bidirectional edges. 302 675 … … 319 692 //\sa SmartGraph. 320 693 321 class SymSmartGraph : public SmartGraph694 /* class SymSmartGraph : public SmartGraph 322 695 { 323 696 public: … … 354 727 355 728 356 };729 };*/ 357 730 358 731 /// @}
Note: See TracChangeset
for help on using the changeset viewer.