Changeset 1962:c1c3a0fae8a1 in lemon-0.x
- Timestamp:
- 02/06/06 17:58:39 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2538
- Files:
-
- 1 added
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/edge_set.h
r1956 r1962 20 20 #define LEMON_EDGE_SET_H 21 21 22 #include <lemon/bits/erasable_graph_extender.h> 23 #include <lemon/bits/clearable_graph_extender.h> 24 #include <lemon/bits/extendable_graph_extender.h> 25 #include <lemon/bits/iterable_graph_extender.h> 26 #include <lemon/bits/alteration_notifier.h> 27 #include <lemon/bits/default_map.h> 28 #include <lemon/bits/graph_extender.h> 29 22 30 /// \ingroup graphs 23 31 /// \file … … 93 101 } 94 102 edges[n].next_in = (*nodes)[target].first_in; 103 if ((*nodes)[target].first_in != -1) { 104 edges[(*nodes)[target].first_in].prev_in = n; 105 } 95 106 (*nodes)[target].first_in = n; 96 107 edges[n].next_out = (*nodes)[source].first_out; 108 if ((*nodes)[source].first_out != -1) { 109 edges[(*nodes)[source].first_out].prev_out = n; 110 } 97 111 (*nodes)[source].first_out = n; 98 112 edges[n].source = source; … … 124 138 125 139 void clear() { 140 Node node; 141 for (first(node); node != INVALID; next(node)) { 142 (*nodes)[node].first_in = -1; 143 (*nodes)[node].first_out = -1; 144 } 126 145 edges.clear(); 127 146 first_edge = -1; … … 174 193 int id(const Edge& edge) const { return edge.id; } 175 194 176 Node nodeFromId(int id) const { return graph-> fromId(id, Node()); }195 Node nodeFromId(int id) const { return graph->nodeFromId(id); } 177 196 Edge edgeFromId(int id) const { return Edge(id); } 178 197 179 int maxNodeId() const { return graph->max Id(Node()); };198 int maxNodeId() const { return graph->maxNodeId(); }; 180 199 int maxEdgeId() const { return edges.size() - 1; } 181 200 … … 209 228 /// 210 229 /// In the edge extension and removing it conforms to the 211 /// \ref concept::E xtendableGraph "ExtendableGraph" concept.230 /// \ref concept::ErasableGraph "ErasableGraph" concept. 212 231 template <typename _Graph> 213 232 class ListEdgeSet : … … 265 284 NodesImpl(const Graph& graph, ListEdgeSet& edgeset) 266 285 : Parent(graph), _edgeset(edgeset) {} 286 287 virtual ~NodesImpl() {} 267 288 268 289 protected: … … 271 292 _edgeset.eraseNode(node); 272 293 Parent::erase(node); 294 } 295 virtual void erase(const std::vector<Node>& nodes) { 296 for (int i = 0; i < (int)nodes.size(); ++i) { 297 _edgeset.eraseNode(nodes[i]); 298 } 299 Parent::erase(nodes); 273 300 } 274 301 virtual void clear() { … … 308 335 /// 309 336 /// In the edge extension and removing it conforms to the 310 /// \ref concept::E xtendableGraph "ExtendableGraph" concept.337 /// \ref concept::ErasableUGraph "ErasableUGraph" concept. 311 338 template <typename _Graph> 312 339 class ListUEdgeSet : … … 359 386 NodesImpl(const Graph& graph, ListUEdgeSet& edgeset) 360 387 : Parent(graph), _edgeset(edgeset) {} 388 389 virtual ~NodesImpl() {} 361 390 362 391 protected: … … 367 396 } 368 397 virtual void erase(const std::vector<Node>& nodes) { 369 for (int i = 0; i < nodes.size(); ++i) {398 for (int i = 0; i < (int)nodes.size(); ++i) { 370 399 _edgeset.eraseNode(nodes[i]); 371 400 } … … 394 423 }; 395 424 425 template <typename _Graph> 426 class SmartEdgeSetBase { 427 public: 428 429 typedef _Graph Graph; 430 typedef typename Graph::Node Node; 431 typedef typename Graph::NodeIt NodeIt; 432 433 protected: 434 435 struct NodeT { 436 int first_out, first_in; 437 NodeT() : first_out(-1), first_in(-1) {} 438 }; 439 440 typedef typename Graph::template NodeMap<NodeT> NodesImplBase; 441 442 NodesImplBase* nodes; 443 444 struct EdgeT { 445 Node source, target; 446 int next_out, next_in; 447 EdgeT() {} 448 }; 449 450 std::vector<EdgeT> edges; 451 452 const Graph* graph; 453 454 void initalize(const Graph& _graph, NodesImplBase& _nodes) { 455 graph = &_graph; 456 nodes = &_nodes; 457 } 458 459 public: 460 461 class Edge { 462 friend class SmartEdgeSetBase<Graph>; 463 protected: 464 Edge(int _id) : id(_id) {} 465 int id; 466 public: 467 Edge() {} 468 Edge(Invalid) : id(-1) {} 469 bool operator==(const Edge& edge) const { return id == edge.id; } 470 bool operator!=(const Edge& edge) const { return id != edge.id; } 471 bool operator<(const Edge& edge) const { return id < edge.id; } 472 }; 473 474 SmartEdgeSetBase() {} 475 476 Edge addEdge(const Node& source, const Node& target) { 477 int n = edges.size(); 478 edges.push_back(EdgeT()); 479 edges[n].next_in = (*nodes)[target].first_in; 480 (*nodes)[target].first_in = n; 481 edges[n].next_out = (*nodes)[source].first_out; 482 (*nodes)[source].first_out = n; 483 edges[n].source = source; 484 edges[n].target = target; 485 return Edge(n); 486 } 487 488 void clear() { 489 Node node; 490 for (first(node); node != INVALID; next(node)) { 491 (*nodes)[node].first_in = -1; 492 (*nodes)[node].first_out = -1; 493 } 494 edges.clear(); 495 } 496 497 void first(Node& node) const { 498 graph->first(node); 499 } 500 501 void next(Node& node) const { 502 graph->next(node); 503 } 504 505 void first(Edge& edge) const { 506 edge.id = edges.size() - 1; 507 } 508 509 void next(Edge& edge) const { 510 --edge.id; 511 } 512 513 void firstOut(Edge& edge, const Node& node) const { 514 edge.id = (*nodes)[node].first_out; 515 } 516 517 void nextOut(Edge& edge) const { 518 edge.id = edges[edge.id].next_out; 519 } 520 521 void firstIn(Edge& edge, const Node& node) const { 522 edge.id = (*nodes)[node].first_in; 523 } 524 525 void nextIn(Edge& edge) const { 526 edge.id = edges[edge.id].next_in; 527 } 528 529 int id(const Node& node) const { return graph->id(node); } 530 int id(const Edge& edge) const { return edge.id; } 531 532 Node nodeFromId(int id) const { return graph->nodeFromId(id); } 533 Edge edgeFromId(int id) const { return Edge(id); } 534 535 int maxNodeId() const { return graph->maxNodeId(); }; 536 int maxEdgeId() const { return edges.size() - 1; } 537 538 Node source(const Edge& edge) const { return edges[edge.id].source;} 539 Node target(const Edge& edge) const { return edges[edge.id].target;} 540 541 template <typename _Value> 542 class NodeMap : public Graph::template NodeMap<_Value> { 543 public: 544 typedef typename _Graph::template NodeMap<_Value> Parent; 545 explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset) 546 : Parent(*edgeset.graph) { } 547 NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value) 548 : Parent(*edgeset.graph, value) { } 549 }; 550 551 }; 552 553 554 /// \ingroup semi_adaptors 555 /// 556 /// \brief Graph using a node set of another graph and an 557 /// own edge set. 558 /// 559 /// This structure can be used to establish another graph over a node set 560 /// of an existing one. The node iterator will go through the nodes of the 561 /// original graph. 562 /// 563 /// \param _Graph The type of the graph which shares its node set with 564 /// this class. Its interface must conform to the \ref concept::StaticGraph 565 /// "StaticGraph" concept. 566 /// 567 /// In the edge extension and removing it conforms to the 568 /// \ref concept::ExtendableGraph "ExtendableGraph" concept. 569 template <typename _Graph> 570 class SmartEdgeSet : 571 public ClearableEdgeSetExtender< 572 ExtendableEdgeSetExtender< 573 MappableEdgeSetExtender< 574 IterableGraphExtender< 575 AlterableEdgeSetExtender< 576 GraphExtender< 577 SmartEdgeSetBase<_Graph> > > > > > > { 578 579 public: 580 581 typedef ClearableEdgeSetExtender< 582 ExtendableEdgeSetExtender< 583 MappableEdgeSetExtender< 584 IterableGraphExtender< 585 AlterableEdgeSetExtender< 586 GraphExtender< 587 SmartEdgeSetBase<_Graph> > > > > > > Parent; 588 589 typedef typename Parent::Node Node; 590 typedef typename Parent::Edge Edge; 591 592 typedef _Graph Graph; 593 594 class UnsupportedOperation : public LogicError { 595 public: 596 virtual const char* exceptionName() const { 597 return "lemon::SmartEdgeSet::UnsupportedOperation"; 598 } 599 }; 600 601 602 603 protected: 604 605 typedef typename Parent::NodesImplBase NodesImplBase; 606 607 void eraseNode(const Node&) { 608 throw UnsupportedOperation(); 609 } 610 611 void clearNodes() { 612 Parent::clear(); 613 } 614 615 class NodesImpl : public NodesImplBase { 616 public: 617 typedef NodesImplBase Parent; 618 619 NodesImpl(const Graph& graph, SmartEdgeSet& edgeset) 620 : Parent(graph), _edgeset(edgeset) {} 621 622 virtual ~NodesImpl() {} 623 624 protected: 625 626 virtual void erase(const Node& node) { 627 _edgeset.eraseNode(node); 628 Parent::erase(node); 629 } 630 virtual void erase(const std::vector<Node>& nodes) { 631 for (int i = 0; i < (int)nodes.size(); ++i) { 632 _edgeset.eraseNode(nodes[i]); 633 } 634 Parent::erase(nodes); 635 } 636 virtual void clear() { 637 _edgeset.clearNodes(); 638 Parent::clear(); 639 } 640 641 private: 642 SmartEdgeSet& _edgeset; 643 }; 644 645 NodesImpl nodes; 646 647 public: 648 649 /// \brief Constructor of the adaptor. 650 /// 651 /// Constructor of the adaptor. 652 SmartEdgeSet(const Graph& graph) : nodes(graph, *this) { 653 Parent::initalize(graph, nodes); 654 } 655 656 }; 657 658 /// \ingroup semi_adaptors 659 /// 660 /// \brief Graph using a node set of another graph and an 661 /// own uedge set. 662 /// 663 /// This structure can be used to establish another graph over a node set 664 /// of an existing one. The node iterator will go through the nodes of the 665 /// original graph. 666 /// 667 /// \param _Graph The type of the graph which shares its node set with 668 /// this class. Its interface must conform to the \ref concept::StaticGraph 669 /// "StaticGraph" concept. 670 /// 671 /// In the edge extension and removing it conforms to the 672 /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept. 673 template <typename _Graph> 674 class SmartUEdgeSet : 675 public ClearableUEdgeSetExtender< 676 ExtendableUEdgeSetExtender< 677 MappableUEdgeSetExtender< 678 IterableUGraphExtender< 679 AlterableUEdgeSetExtender< 680 UGraphExtender< 681 SmartEdgeSetBase<_Graph> > > > > > > { 682 683 public: 684 685 typedef ClearableUEdgeSetExtender< 686 ExtendableUEdgeSetExtender< 687 MappableUEdgeSetExtender< 688 IterableUGraphExtender< 689 AlterableUEdgeSetExtender< 690 UGraphExtender< 691 SmartEdgeSetBase<_Graph> > > > > > > Parent; 692 693 typedef typename Parent::Node Node; 694 typedef typename Parent::Edge Edge; 695 696 typedef _Graph Graph; 697 698 class UnsupportedOperation : public LogicError { 699 public: 700 virtual const char* exceptionName() const { 701 return "lemon::SmartUEdgeSet::UnsupportedOperation"; 702 } 703 }; 704 705 protected: 706 707 typedef typename Parent::NodesImplBase NodesImplBase; 708 709 void eraseNode(const Node&) { 710 throw UnsupportedOperation(); 711 } 712 713 void clearNodes() { 714 Parent::clear(); 715 } 716 717 class NodesImpl : public NodesImplBase { 718 public: 719 typedef NodesImplBase Parent; 720 721 NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset) 722 : Parent(graph), _edgeset(edgeset) {} 723 724 virtual ~NodesImpl() {} 725 726 protected: 727 728 virtual void erase(const Node& node) { 729 _edgeset.eraseNode(node); 730 Parent::erase(node); 731 } 732 virtual void erase(const std::vector<Node>& nodes) { 733 for (int i = 0; i < (int)nodes.size(); ++i) { 734 _edgeset.eraseNode(nodes[i]); 735 } 736 Parent::erase(nodes); 737 } 738 virtual void clear() { 739 _edgeset.clearNodes(); 740 Parent::clear(); 741 } 742 743 private: 744 SmartUEdgeSet& _edgeset; 745 }; 746 747 NodesImpl nodes; 748 749 public: 750 751 /// \brief Constructor of the adaptor. 752 /// 753 /// Constructor of the adaptor. 754 SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) { 755 Parent::initalize(graph, nodes); 756 } 757 758 }; 759 396 760 } 397 761 -
test/Makefile.am
r1921 r1962 18 18 dfs_test \ 19 19 dijkstra_test \ 20 edge_set_test \ 20 21 graph_test \ 21 22 graph_adaptor_test \ … … 55 56 dfs_test_SOURCES = dfs_test.cc 56 57 dijkstra_test_SOURCES = dijkstra_test.cc 58 edge_set_test_SOURCES = edge_set_test.cc 57 59 graph_test_SOURCES = graph_test.cc 58 60 graph_utils_test_SOURCES = graph_utils_test.cc
Note: See TracChangeset
for help on using the changeset viewer.