Changeset 937:d4e911acef3d in lemon-0.x for src
- Timestamp:
- 10/04/04 19:13:21 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1264
- Location:
- src
- Files:
-
- 3 added
- 1 deleted
- 12 edited
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/Makefile.am
r921 r937 19 19 map_bits.h \ 20 20 maps.h \ 21 min_cost_flow.h \21 min_cost_flow.h \ 22 22 suurballe.h \ 23 23 preflow.h \ 24 24 path.h \ 25 25 smart_graph.h \ 26 sym_map.h \27 26 time_measure.h \ 28 27 unionfind.h \ … … 32 31 noinst_HEADERS = \ 33 32 skeletons/graph.h \ 33 skeletons/sym_graph.h \ 34 34 skeletons/maps.h \ 35 35 skeletons/path.h -
src/lemon/default_map.h
r921 r937 60 60 template <typename TT> \ 61 61 DefaultMap(const DefaultMap<MapRegistry, TT>& copy) \ 62 : { \ 63 Parent::MapBase::operator= \ 64 (static_cast<const typename Parent::MapBase&>(copy)); \ 62 : Parent(*copy.getGraph()) { \ 65 63 if (Parent::getGraph()) { \ 66 64 for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\ 67 Parent::add(it); \68 65 Parent::operator[](it) = copy[it]; \ 69 66 } \ -
src/lemon/list_graph.h
r921 r937 30 30 #include <lemon/array_map.h> 31 31 32 #include <lemon/sym_map.h>33 34 32 #include <lemon/map_defines.h> 35 33 … … 105 103 first_free_edge(_g.first_free_edge) {} 106 104 105 /// \bug In the vector can be hole if a node is erased from the graph. 107 106 ///Number of nodes. 108 107 int nodeNum() const { return nodes.size(); } … … 439 438 ///\todo this date structure need some reconsiderations. Maybe it 440 439 ///should be implemented independently from ListGraph. 441 440 /* 442 441 class SymListGraph : public ListGraph 443 442 { … … 484 483 ListGraph::erase(e); 485 484 } 485 };*/ 486 487 class SymListGraph : public ListGraph { 488 typedef ListGraph Parent; 489 public: 490 491 typedef SymListGraph Graph; 492 493 typedef ListGraph::Node Node; 494 typedef ListGraph::NodeIt NodeIt; 495 496 class SymEdge; 497 class SymEdgeIt; 498 499 class Edge; 500 class EdgeIt; 501 class OutEdgeIt; 502 class InEdgeIt; 503 504 template <typename Value> 505 class NodeMap : public Parent::NodeMap<Value> { 506 public: 507 NodeMap(const SymListGraph& g) 508 : SymListGraph::Parent::NodeMap<Value>(g) {} 509 NodeMap(const SymListGraph& g, Value v) 510 : SymListGraph::Parent::NodeMap<Value>(g, v) {} 511 template<typename TT> 512 NodeMap(const NodeMap<TT>& copy) 513 : SymListGraph::Parent::NodeMap<Value>(copy) { } 514 }; 515 516 template <typename Value> 517 class SymEdgeMap : public Parent::EdgeMap<Value> { 518 public: 519 typedef SymEdge KeyType; 520 521 SymEdgeMap(const SymListGraph& g) 522 : SymListGraph::Parent::EdgeMap<Value>(g) {} 523 SymEdgeMap(const SymListGraph& g, Value v) 524 : SymListGraph::Parent::EdgeMap<Value>(g, v) {} 525 template<typename TT> 526 SymEdgeMap(const SymEdgeMap<TT>& copy) 527 : SymListGraph::Parent::EdgeMap<Value>(copy) { } 528 529 }; 530 531 // Create edge map registry. 532 CREATE_EDGE_MAP_REGISTRY; 533 // Create edge maps. 534 CREATE_EDGE_MAP(ArrayMap); 535 536 class Edge { 537 friend class SymListGraph; 538 friend class SymListGraph::EdgeIt; 539 friend class SymListGraph::OutEdgeIt; 540 friend class SymListGraph::InEdgeIt; 541 542 protected: 543 int id; 544 545 Edge(int pid) { id = pid; } 546 547 public: 548 /// An Edge with id \c n. 549 550 Edge() { } 551 Edge (Invalid) { id = -1; } 552 553 operator SymEdge(){ return SymEdge(id >> 1);} 554 555 bool operator==(const Edge i) const {return id == i.id;} 556 bool operator!=(const Edge i) const {return id != i.id;} 557 bool operator<(const Edge i) const {return id < i.id;} 558 // ///Validity check 559 // operator bool() { return n!=-1; } 560 }; 561 562 class SymEdge : public ListGraph::Edge { 563 friend class SymListGraph; 564 friend class SymListGraph::Edge; 565 typedef ListGraph::Edge Parent; 566 567 protected: 568 SymEdge(int pid) : Parent(pid) {} 569 public: 570 571 SymEdge() { } 572 SymEdge(const ListGraph::Edge& i) : Parent(i) {} 573 SymEdge (Invalid) : Parent(INVALID) {} 574 575 }; 576 577 class OutEdgeIt { 578 Parent::OutEdgeIt out; 579 Parent::InEdgeIt in; 580 public: 581 OutEdgeIt() {} 582 OutEdgeIt(const SymListGraph& g, Edge e) { 583 if ((e.id & 1) == 0) { 584 out = Parent::OutEdgeIt(g, SymEdge(e)); 585 in = Parent::InEdgeIt(g, g.tail(e)); 586 } else { 587 out = Parent::OutEdgeIt(INVALID); 588 in = Parent::InEdgeIt(g, SymEdge(e)); 589 } 590 } 591 OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } 592 593 OutEdgeIt(const SymListGraph& g, const Node v) 594 : out(g, v), in(g, v) {} 595 OutEdgeIt &operator++() { 596 if (out != INVALID) { 597 ++out; 598 } else { 599 ++in; 600 } 601 return *this; 602 } 603 604 operator Edge() const { 605 if (out == INVALID && in == INVALID) return INVALID; 606 return out != INVALID ? forward(out) : backward(in); 607 } 608 609 bool operator==(const Edge i) const {return Edge(*this) == i;} 610 bool operator!=(const Edge i) const {return Edge(*this) != i;} 611 bool operator<(const Edge i) const {return Edge(*this) < i;} 612 }; 613 614 class InEdgeIt { 615 Parent::OutEdgeIt out; 616 Parent::InEdgeIt in; 617 public: 618 InEdgeIt() {} 619 InEdgeIt(const SymListGraph& g, Edge e) { 620 if ((e.id & 1) == 0) { 621 out = Parent::OutEdgeIt(g, SymEdge(e)); 622 in = Parent::InEdgeIt(g, g.tail(e)); 623 } else { 624 out = Parent::OutEdgeIt(INVALID); 625 in = Parent::InEdgeIt(g, SymEdge(e)); 626 } 627 } 628 InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } 629 630 InEdgeIt(const SymListGraph& g, const Node v) 631 : out(g, v), in(g, v) {} 632 633 InEdgeIt &operator++() { 634 if (out != INVALID) { 635 ++out; 636 } else { 637 ++in; 638 } 639 return *this; 640 } 641 642 operator Edge() const { 643 if (out == INVALID && in == INVALID) return INVALID; 644 return out != INVALID ? backward(out) : forward(in); 645 } 646 647 bool operator==(const Edge i) const {return Edge(*this) == i;} 648 bool operator!=(const Edge i) const {return Edge(*this) != i;} 649 bool operator<(const Edge i) const {return Edge(*this) < i;} 650 }; 651 652 class SymEdgeIt : public Parent::EdgeIt { 653 654 public: 655 SymEdgeIt() {} 656 657 SymEdgeIt(const SymListGraph& g) 658 : SymListGraph::Parent::EdgeIt(g) {} 659 660 SymEdgeIt(const SymListGraph& g, SymEdge e) 661 : SymListGraph::Parent::EdgeIt(g, e) {} 662 663 SymEdgeIt(Invalid i) 664 : SymListGraph::Parent::EdgeIt(INVALID) {} 665 666 SymEdgeIt& operator++() { 667 SymListGraph::Parent::EdgeIt::operator++(); 668 return *this; 669 } 670 671 operator SymEdge() const { 672 return SymEdge 673 (static_cast<const SymListGraph::Parent::EdgeIt&>(*this)); 674 } 675 bool operator==(const SymEdge i) const {return SymEdge(*this) == i;} 676 bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;} 677 bool operator<(const SymEdge i) const {return SymEdge(*this) < i;} 678 }; 679 680 class EdgeIt { 681 SymEdgeIt it; 682 bool fw; 683 public: 684 EdgeIt(const SymListGraph& g) : it(g), fw(true) {} 685 EdgeIt (Invalid i) : it(i) { } 686 EdgeIt(const SymListGraph& g, Edge e) 687 : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { } 688 EdgeIt() { } 689 EdgeIt& operator++() { 690 fw = !fw; 691 if (fw) ++it; 692 return *this; 693 } 694 operator Edge() const { 695 if (it == INVALID) return INVALID; 696 return fw ? forward(it) : backward(it); 697 } 698 bool operator==(const Edge i) const {return Edge(*this) == i;} 699 bool operator!=(const Edge i) const {return Edge(*this) != i;} 700 bool operator<(const Edge i) const {return Edge(*this) < i;} 701 702 }; 703 704 ///Number of nodes. 705 int nodeNum() const { return Parent::nodeNum(); } 706 ///Number of edges. 707 int edgeNum() const { return 2*Parent::edgeNum(); } 708 ///Number of symmetric edges. 709 int symEdgeNum() const { return Parent::edgeNum(); } 710 711 ///Set the expected maximum number of edges. 712 713 ///With this function, it is possible to set the expected number of edges. 714 ///The use of this fasten the building of the graph and makes 715 ///it possible to avoid the superfluous memory allocation. 716 void reserveSymEdge(int n) { Parent::reserveEdge(n); }; 717 718 /// Maximum node ID. 719 720 /// Maximum node ID. 721 ///\sa id(Node) 722 int maxNodeId() const { return Parent::maxNodeId(); } 723 /// Maximum edge ID. 724 725 /// Maximum edge ID. 726 ///\sa id(Edge) 727 int maxEdgeId() const { return 2*Parent::maxEdgeId(); } 728 /// Maximum symmetric edge ID. 729 730 /// Maximum symmetric edge ID. 731 ///\sa id(SymEdge) 732 int maxSymEdgeId() const { return Parent::maxEdgeId(); } 733 734 735 Node tail(Edge e) const { 736 return (e.id & 1) == 0 ? 737 Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e)); 738 } 739 740 Node head(Edge e) const { 741 return (e.id & 1) == 0 ? 742 Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e)); 743 } 744 745 Node tail(SymEdge e) const { 746 return Parent::tail(e); 747 } 748 749 Node head(SymEdge e) const { 750 return Parent::head(e); 751 } 752 753 NodeIt& first(NodeIt& v) const { 754 v=NodeIt(*this); return v; } 755 EdgeIt& first(EdgeIt& e) const { 756 e=EdgeIt(*this); return e; } 757 SymEdgeIt& first(SymEdgeIt& e) const { 758 e=SymEdgeIt(*this); return e; } 759 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 760 e=OutEdgeIt(*this,v); return e; } 761 InEdgeIt& first(InEdgeIt& e, const Node v) const { 762 e=InEdgeIt(*this,v); return e; } 763 764 /// Node ID. 765 766 /// The ID of a valid Node is a nonnegative integer not greater than 767 /// \ref maxNodeId(). The range of the ID's is not surely continuous 768 /// and the greatest node ID can be actually less then \ref maxNodeId(). 769 /// 770 /// The ID of the \ref INVALID node is -1. 771 ///\return The ID of the node \c v. 772 static int id(Node v) { return Parent::id(v); } 773 /// Edge ID. 774 775 /// The ID of a valid Edge is a nonnegative integer not greater than 776 /// \ref maxEdgeId(). The range of the ID's is not surely continuous 777 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). 778 /// 779 /// The ID of the \ref INVALID edge is -1. 780 ///\return The ID of the edge \c e. 781 static int id(Edge e) { return e.id; } 782 783 /// The ID of a valid SymEdge is a nonnegative integer not greater than 784 /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous 785 /// and the greatest edge ID can be actually less then \ref maxSymEdgeId(). 786 /// 787 /// The ID of the \ref INVALID symmetric edge is -1. 788 ///\return The ID of the edge \c e. 789 static int id(SymEdge e) { return Parent::id(e); } 790 791 /// Adds a new node to the graph. 792 793 /// \warning It adds the new node to the front of the list. 794 /// (i.e. the lastly added node becomes the first.) 795 Node addNode() { 796 return Parent::addNode(); 797 } 798 799 SymEdge addEdge(Node u, Node v) { 800 SymEdge se = Parent::addEdge(u, v); 801 edge_maps.add(forward(se)); 802 edge_maps.add(backward(se)); 803 return se; 804 } 805 806 /// Finds an edge between two nodes. 807 808 /// Finds an edge from node \c u to node \c v. 809 /// 810 /// If \c prev is \ref INVALID (this is the default value), then 811 /// It finds the first edge from \c u to \c v. Otherwise it looks for 812 /// the next edge from \c u to \c v after \c prev. 813 /// \return The found edge or INVALID if there is no such an edge. 814 Edge findEdge(Node u, Node v, Edge prev = INVALID) 815 { 816 if (prev == INVALID || id(prev) & 1 == 0) { 817 SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); 818 if (se != INVALID) return forward(se); 819 } else { 820 SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); 821 if (se != INVALID) return backward(se); 822 } 823 return INVALID; 824 } 825 826 // /// Finds an symmetric edge between two nodes. 827 828 // /// Finds an symmetric edge from node \c u to node \c v. 829 // /// 830 // /// If \c prev is \ref INVALID (this is the default value), then 831 // /// It finds the first edge from \c u to \c v. Otherwise it looks for 832 // /// the next edge from \c u to \c v after \c prev. 833 // /// \return The found edge or INVALID if there is no such an edge. 834 835 // SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID) 836 // { 837 // if (prev == INVALID || id(prev) & 1 == 0) { 838 // SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); 839 // if (se != INVALID) return se; 840 // } else { 841 // SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); 842 // if (se != INVALID) return se; 843 // } 844 // return INVALID; 845 // } 846 847 public: 848 849 void erase(Node n) { 850 for (OutEdgeIt it(*this, n); it != INVALID; ++it) { 851 edge_maps.erase(it); 852 edge_maps.erase(opposite(it)); 853 } 854 Parent::erase(n); 855 } 856 857 void erase(SymEdge e) { 858 edge_maps.erase(forward(e)); 859 edge_maps.erase(backward(e)); 860 Parent::erase(e); 861 }; 862 863 void clear() { 864 edge_maps.clear(); 865 Parent::clear(); 866 } 867 868 static Edge opposite(Edge e) { 869 return Edge(id(e) ^ 1); 870 } 871 872 static Edge forward(SymEdge e) { 873 return Edge(id(e) << 1); 874 } 875 876 static Edge backward(SymEdge e) { 877 return Edge((id(e) << 1) | 1); 878 } 879 486 880 }; 487 488 881 489 882 ///A graph class containing only nodes. -
src/lemon/map_bits.h
r921 r937 55 55 struct KeyInfo<Graph, typename Graph::SymEdgeIt> { 56 56 static int maxId(const Graph& graph) { 57 return graph.max EdgeId() >> 1;57 return graph.maxSymEdgeId(); 58 58 } 59 static int id(const Graph& graph, const typename Graph:: Edge& edge) {60 return graph.id(edge) >> 1;59 static int id(const Graph& graph, const typename Graph::SymEdge& edge) { 60 return graph.id(edge); 61 61 } 62 62 }; -
src/lemon/map_defines.h
r921 r937 115 115 */ 116 116 #define CREATE_SYM_EDGE_MAP_REGISTRY \ 117 typedef SymEdgeIt<Graph, Edge, EdgeIt> SymEdgeIt; \ 118 typedef MapRegistry<Graph, Edge, SymEdgeIt> SymEdgeMapRegistry; \ 117 typedef MapRegistry<Graph, SymEdge, SymEdgeIt> SymEdgeMapRegistry; \ 119 118 mutable SymEdgeMapRegistry sym_edge_maps; 120 119 … … 128 127 #define CREATE_SYM_EDGE_MAP(DynMap) \ 129 128 template <typename Value> \ 130 class SymEdgeMap : public SymMap<DynMap,SymEdgeMapRegistry, Value> { \131 public: \ 132 typedef SymMap<DynMap,SymEdgeMapRegistry, Value> Parent; \129 class SymEdgeMap : public DynMap<SymEdgeMapRegistry, Value> { \ 130 public: \ 131 typedef DynMap<SymEdgeMapRegistry, Value> Parent; \ 133 132 \ 134 133 SymEdgeMap(const typename Parent::Graph& g) \ -
src/lemon/map_registry.h
r921 r937 28 28 namespace lemon { 29 29 30 /// \addtogroup graphmapfactory 31 /// @{ 32 33 /** 34 * Registry class to register edge or node maps into the graph. The 35 * registry helps you to implement an observer pattern. If you add 36 * or erase an edge or node you must notify all the maps about the 37 * event. 38 */ 30 /// \addtogroup graphmapfactory 31 /// @{ 32 33 /// Map registry for graph maps. 34 35 /** 36 * Registry class to register edge or node maps into the graph. The 37 * registry helps you to implement an observer pattern. If you add 38 * or erase an edge or node you must notify all the maps about the 39 * event. 40 * 41 * \param G The graph type to register maps. 42 * \param K The key type of the maps registered into the registry. 43 * \param KIt The key iterator type iterates on the keys. 44 * 45 * \author Balazs Dezso 46 */ 47 39 48 template <typename G, typename K, typename KIt> 40 49 class MapRegistry { … … 43 52 typedef K KeyType; 44 53 typedef KIt KeyIt; 45 46 /** 47 * MapBase is the base class of the registered maps. 54 55 /// MapBase is the base class of the dynamic maps. 56 57 /** 58 * MapBase is the base class of the dynamic maps. 48 59 * It defines the core modification operations on the maps and 49 60 * implements some helper functions. … … 59 70 friend class MapRegistry<G, K, KIt>; 60 71 72 /// Default constructor. 73 61 74 /** 62 75 * Default constructor for MapBase. … … 64 77 65 78 MapBase() : graph(0), registry(0) {} 66 67 /** 68 * Simple constructor to register into a graph registry. 79 80 /// Constructor to register map into a graph registry. 81 82 /** 83 * Simple constructor to register dynamic map into a graph registry. 69 84 */ 70 85 … … 73 88 } 74 89 90 /// Copy constructor. 91 75 92 /** 76 93 * Copy constructor to register into the registry. 94 * If the copiable map is registered into a registry 95 * the construated map will be registered to the same registry. 77 96 */ 78 97 … … 82 101 } 83 102 } 84 85 /** 86 * Assign operator. 103 104 /// Assign operator. 105 106 /** 107 * Assign operator. This member detach first the map 108 * from the current registry and then it attach to the 109 * copiable map's registry if it exists. 87 110 */ 88 111 const MapBase& operator=(const MapBase& copy) { … … 97 120 } 98 121 99 100 /** 101 * Destructor. 122 /// Destructor 123 124 /** 125 * This member detach the map from the its registry if the 126 * registry exists. 102 127 */ 103 128 … … 108 133 } 109 134 135 /// The graph of the map. 136 110 137 /* 111 138 * Returns the graph that the map belongs to. … … 122 149 123 150 protected: 124 125 /** 126 Helper function to implement constructors in the subclasses. 151 152 /// Helper function to implement constructors in the subclasses. 153 154 /** 155 * Helper function to implement constructors in the subclasses. 156 * It adds all of the nodes or edges to the map via the 157 * \ref MapRegistry::MapBase::add add 158 * member function. 127 159 */ 128 160 … … 133 165 } 134 166 135 /** 136 Helper function to implement the destructor in the subclasses. 167 168 /// Helper function to implement destructors in the subclasses. 169 170 /** 171 * Helper function to implement destructors in the subclasses. 172 * It erases all of the nodes or edges of the map via the 173 * \ref MapRegistry::MapBase::erase erase 174 * member function. It can be used by the clear function also. 137 175 */ 138 176 … … 142 180 } 143 181 } 182 183 /// The member function to add new node or edge to the map. 144 184 145 185 /** 146 186 The add member function should be overloaded in the subclasses. 147 \e Add extends the map with the new node .187 \e Add extends the map with the new node or edge. 148 188 */ 149 189 150 190 virtual void add(const KeyType&) = 0; 191 192 193 /// The member function to erase a node or edge from the map. 194 151 195 /** 152 196 The erase member function should be overloaded in the subclasses. 153 \e Erase removes the node from the map.197 \e Erase removes the node or edge from the map. 154 198 */ 155 199 … … 162 206 163 207 virtual void clear() = 0; 164 165 /** 166 Exception class to throw at unsupported operation. 208 209 /// Exception class to throw at unsupported operation. 210 211 /** 212 * Exception class to throw at unsupported operation. 213 * If the map does not support erasing or adding new 214 * node or key it must be throwed. 167 215 */ 168 216 … … 173 221 protected: 174 222 175 /** 176 * The container type of the maps. 177 */ 223 178 224 typedef std::vector<MapBase*> Container; 179 225 180 /**181 * The container of the registered maps.182 */183 226 Container container; 184 227 185 228 186 229 public: 187 188 /** 189 * Default Constructor of the MapRegistry. It creates an empty registry. 230 231 /// Default constructor. 232 233 /** 234 * Default constructor of the \e MapRegistry. 235 * It creates an empty registry. 190 236 */ 191 237 MapRegistry() {} 192 193 /** 194 * Copy Constructor of the MapRegistry. The new registry does not steal 195 * the maps from the right value. The new registry will be an empty. 238 239 /// Copy Constructor of the MapRegistry. 240 241 /** 242 * Copy constructor of the \e MapRegistry. 243 * The new registry does not steal 244 * the maps from the copiable registry. 245 * The new registry will be empty. 196 246 */ 197 247 MapRegistry(const MapRegistry&) {} 198 199 /** 200 * Assign operator. The left value does not steal the maps 201 * from the right value. The left value will be an empty registry. 248 249 /// Assign operator. 250 251 /** 252 * Assign operator. This registry does not steal the maps 253 * from the copiable registry. This registry will be an empty registry. 254 * This operator will be called when a graph is assigned. 202 255 */ 203 256 MapRegistry& operator=(const MapRegistry&) { 204 257 typename Container::iterator it; 205 258 for (it = container.begin(); it != container.end(); ++it) { 206 (*it)-> destroy();259 (*it)->clear(); 207 260 (*it)->graph = 0; 208 261 (*it)->registry = 0; 209 262 } 210 263 } 264 265 /// Destructor. 211 266 212 267 /** 213 * Destructor of the MapRegistry. 268 * Destructor of the MapRegistry. It makes empty the attached map 269 * first then detachs them. 214 270 */ 215 271 ~MapRegistry() { 216 272 typename Container::iterator it; 217 273 for (it = container.begin(); it != container.end(); ++it) { 218 (*it)-> destroy();274 (*it)->clear(); 219 275 (*it)->registry = 0; 220 276 (*it)->graph = 0; … … 224 280 225 281 public: 226 227 /** 228 * Attach a map into thr registry. If the map has been attached 282 283 /// Attachs a map to the \e MapRegistry. 284 285 /** 286 * Attachs a map into thr registry. If the map has been attached 229 287 * into an other registry it is detached from that automaticly. 230 288 */ … … 237 295 map.registry_index = container.size()-1; 238 296 } 239 240 /** 241 * Detach the map from the registry. 297 298 /// Detachs a map from the \e MapRegistry. 299 300 /** 301 * Detachs a map from the \e MapRegistry. 242 302 */ 243 303 void detach(MapBase& map) { … … 249 309 } 250 310 311 /// Notify all the registered maps about a Key added. 251 312 252 313 /** 253 314 * Notify all the registered maps about a Key added. 254 */ 255 void add(KeyType& key) { 315 * This member should be called whenever a node or edge 316 * is added to the graph. 317 */ 318 void add(const KeyType& key) { 256 319 typename Container::iterator it; 257 320 for (it = container.begin(); it != container.end(); ++it) { … … 259 322 } 260 323 } 324 325 /// Notify all the registered maps about a Key erased. 261 326 262 327 /** 263 328 * Notify all the registered maps about a Key erased. 329 * This member should be called whenever a node or edge 330 * is erased from the graph. 264 331 */ 265 void erase( KeyType& key) {332 void erase(const KeyType& key) { 266 333 typename Container::iterator it; 267 334 for (it = container.begin(); it != container.end(); ++it) { … … 270 337 } 271 338 339 340 /// Notify all the registered maps about all the Keys are erased. 341 272 342 /** 273 343 * Notify all the registered maps about the map should be cleared. 344 * This member should be called whenever all of the nodes or edges 345 * are erased from the graph. 274 346 */ 275 347 void clear() { -
src/lemon/smart_graph.h
r921 r937 27 27 #include <lemon/invalid.h> 28 28 29 29 30 #include <lemon/array_map.h> 30 #include <lemon/sym_map.h>31 31 32 32 #include <lemon/map_registry.h> … … 299 299 }; 300 300 301 302 303 class SymSmartGraph : public SmartGraph { 304 typedef SmartGraph Parent; 305 public: 306 307 typedef SymSmartGraph Graph; 308 309 typedef SmartGraph::Node Node; 310 typedef SmartGraph::NodeIt NodeIt; 311 312 class SymEdge; 313 class SymEdgeIt; 314 315 class Edge; 316 class EdgeIt; 317 class OutEdgeIt; 318 class InEdgeIt; 319 320 template <typename Value> 321 class NodeMap : public Parent::NodeMap<Value> { 322 public: 323 NodeMap(const SymSmartGraph& g) 324 : SymSmartGraph::Parent::NodeMap<Value>(g) {} 325 NodeMap(const SymSmartGraph& g, Value v) 326 : SymSmartGraph::Parent::NodeMap<Value>(g, v) {} 327 template<typename TT> 328 NodeMap(const NodeMap<TT>& copy) 329 : SymSmartGraph::Parent::NodeMap<Value>(copy) { } 330 }; 331 332 template <typename Value> 333 class SymEdgeMap : public Parent::EdgeMap<Value> { 334 public: 335 typedef SymEdge KeyType; 336 337 SymEdgeMap(const SymSmartGraph& g) 338 : SymSmartGraph::Parent::EdgeMap<Value>(g) {} 339 SymEdgeMap(const SymSmartGraph& g, Value v) 340 : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {} 341 template<typename TT> 342 SymEdgeMap(const SymEdgeMap<TT>& copy) 343 : SymSmartGraph::Parent::EdgeMap<Value>(copy) { } 344 345 }; 346 347 // Create edge map registry. 348 CREATE_EDGE_MAP_REGISTRY; 349 // Create edge maps. 350 CREATE_EDGE_MAP(ArrayMap); 351 352 class Edge { 353 friend class SymSmartGraph; 354 friend class SymSmartGraph::EdgeIt; 355 friend class SymSmartGraph::OutEdgeIt; 356 friend class SymSmartGraph::InEdgeIt; 357 358 protected: 359 int id; 360 361 Edge(int pid) { id = pid; } 362 363 public: 364 /// An Edge with id \c n. 365 366 Edge() { } 367 Edge (Invalid) { id = -1; } 368 369 operator SymEdge(){ return SymEdge(id >> 1);} 370 371 bool operator==(const Edge i) const {return id == i.id;} 372 bool operator!=(const Edge i) const {return id != i.id;} 373 bool operator<(const Edge i) const {return id < i.id;} 374 // ///Validity check 375 // operator bool() { return n!=-1; } 376 }; 377 378 class SymEdge : public SmartGraph::Edge { 379 friend class SymSmartGraph; 380 friend class SymSmartGraph::Edge; 381 typedef SmartGraph::Edge Parent; 382 383 protected: 384 SymEdge(int pid) : Parent(pid) {} 385 public: 386 387 SymEdge() { } 388 SymEdge(const SmartGraph::Edge& i) : Parent(i) {} 389 SymEdge (Invalid) : Parent(INVALID) {} 390 391 }; 392 393 class OutEdgeIt { 394 Parent::OutEdgeIt out; 395 Parent::InEdgeIt in; 396 public: 397 OutEdgeIt() {} 398 OutEdgeIt(const SymSmartGraph& g, Edge e) { 399 if ((e.id & 1) == 0) { 400 out = Parent::OutEdgeIt(g, SymEdge(e)); 401 in = Parent::InEdgeIt(g, g.tail(e)); 402 } else { 403 out = Parent::OutEdgeIt(INVALID); 404 in = Parent::InEdgeIt(g, SymEdge(e)); 405 } 406 } 407 OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } 408 409 OutEdgeIt(const SymSmartGraph& g, const Node v) 410 : out(g, v), in(g, v) {} 411 OutEdgeIt &operator++() { 412 if (out != INVALID) { 413 ++out; 414 } else { 415 ++in; 416 } 417 return *this; 418 } 419 420 operator Edge() const { 421 if (out == INVALID && in == INVALID) return INVALID; 422 return out != INVALID ? forward(out) : backward(in); 423 } 424 425 bool operator==(const Edge i) const {return Edge(*this) == i;} 426 bool operator!=(const Edge i) const {return Edge(*this) != i;} 427 bool operator<(const Edge i) const {return Edge(*this) < i;} 428 }; 429 430 class InEdgeIt { 431 Parent::OutEdgeIt out; 432 Parent::InEdgeIt in; 433 public: 434 InEdgeIt() {} 435 InEdgeIt(const SymSmartGraph& g, Edge e) { 436 if ((e.id & 1) == 0) { 437 out = Parent::OutEdgeIt(g, SymEdge(e)); 438 in = Parent::InEdgeIt(g, g.tail(e)); 439 } else { 440 out = Parent::OutEdgeIt(INVALID); 441 in = Parent::InEdgeIt(g, SymEdge(e)); 442 } 443 } 444 InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { } 445 446 InEdgeIt(const SymSmartGraph& g, const Node v) 447 : out(g, v), in(g, v) {} 448 449 InEdgeIt &operator++() { 450 if (out != INVALID) { 451 ++out; 452 } else { 453 ++in; 454 } 455 return *this; 456 } 457 458 operator Edge() const { 459 if (out == INVALID && in == INVALID) return INVALID; 460 return out != INVALID ? backward(out) : forward(in); 461 } 462 463 bool operator==(const Edge i) const {return Edge(*this) == i;} 464 bool operator!=(const Edge i) const {return Edge(*this) != i;} 465 bool operator<(const Edge i) const {return Edge(*this) < i;} 466 }; 467 468 class SymEdgeIt : public Parent::EdgeIt { 469 470 public: 471 SymEdgeIt() {} 472 473 SymEdgeIt(const SymSmartGraph& g) 474 : SymSmartGraph::Parent::EdgeIt(g) {} 475 476 SymEdgeIt(const SymSmartGraph& g, SymEdge e) 477 : SymSmartGraph::Parent::EdgeIt(g, e) {} 478 479 SymEdgeIt(Invalid i) 480 : SymSmartGraph::Parent::EdgeIt(INVALID) {} 481 482 SymEdgeIt& operator++() { 483 SymSmartGraph::Parent::EdgeIt::operator++(); 484 return *this; 485 } 486 487 operator SymEdge() const { 488 return SymEdge 489 (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this)); 490 } 491 bool operator==(const SymEdge i) const {return SymEdge(*this) == i;} 492 bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;} 493 bool operator<(const SymEdge i) const {return SymEdge(*this) < i;} 494 }; 495 496 class EdgeIt { 497 SymEdgeIt it; 498 bool fw; 499 public: 500 EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {} 501 EdgeIt (Invalid i) : it(i) { } 502 EdgeIt(const SymSmartGraph& g, Edge e) 503 : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { } 504 EdgeIt() { } 505 EdgeIt& operator++() { 506 fw = !fw; 507 if (fw) ++it; 508 return *this; 509 } 510 operator Edge() const { 511 if (it == INVALID) return INVALID; 512 return fw ? forward(it) : backward(it); 513 } 514 bool operator==(const Edge i) const {return Edge(*this) == i;} 515 bool operator!=(const Edge i) const {return Edge(*this) != i;} 516 bool operator<(const Edge i) const {return Edge(*this) < i;} 517 518 }; 519 520 ///Number of nodes. 521 int nodeNum() const { return Parent::nodeNum(); } 522 ///Number of edges. 523 int edgeNum() const { return 2*Parent::edgeNum(); } 524 ///Number of symmetric edges. 525 int symEdgeNum() const { return Parent::edgeNum(); } 526 527 /// Maximum node ID. 528 529 /// Maximum node ID. 530 ///\sa id(Node) 531 int maxNodeId() const { return Parent::maxNodeId(); } 532 /// Maximum edge ID. 533 534 /// Maximum edge ID. 535 ///\sa id(Edge) 536 int maxEdgeId() const { return 2*Parent::maxEdgeId(); } 537 /// Maximum symmetric edge ID. 538 539 /// Maximum symmetric edge ID. 540 ///\sa id(SymEdge) 541 int maxSymEdgeId() const { return Parent::maxEdgeId(); } 542 543 544 Node tail(Edge e) const { 545 return (e.id & 1) == 0 ? 546 Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e)); 547 } 548 549 Node head(Edge e) const { 550 return (e.id & 1) == 0 ? 551 Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e)); 552 } 553 554 Node tail(SymEdge e) const { 555 return Parent::tail(e); 556 } 557 558 Node head(SymEdge e) const { 559 return Parent::head(e); 560 } 561 562 NodeIt& first(NodeIt& v) const { 563 v=NodeIt(*this); return v; } 564 EdgeIt& first(EdgeIt& e) const { 565 e=EdgeIt(*this); return e; } 566 SymEdgeIt& first(SymEdgeIt& e) const { 567 e=SymEdgeIt(*this); return e; } 568 OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 569 e=OutEdgeIt(*this,v); return e; } 570 InEdgeIt& first(InEdgeIt& e, const Node v) const { 571 e=InEdgeIt(*this,v); return e; } 572 573 /// Node ID. 574 575 /// The ID of a valid Node is a nonnegative integer not greater than 576 /// \ref maxNodeId(). The range of the ID's is not surely continuous 577 /// and the greatest node ID can be actually less then \ref maxNodeId(). 578 /// 579 /// The ID of the \ref INVALID node is -1. 580 ///\return The ID of the node \c v. 581 static int id(Node v) { return Parent::id(v); } 582 /// Edge ID. 583 584 /// The ID of a valid Edge is a nonnegative integer not greater than 585 /// \ref maxEdgeId(). The range of the ID's is not surely continuous 586 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). 587 /// 588 /// The ID of the \ref INVALID edge is -1. 589 ///\return The ID of the edge \c e. 590 static int id(Edge e) { return e.id; } 591 592 /// The ID of a valid SymEdge is a nonnegative integer not greater than 593 /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous 594 /// and the greatest edge ID can be actually less then \ref maxSymEdgeId(). 595 /// 596 /// The ID of the \ref INVALID symmetric edge is -1. 597 ///\return The ID of the edge \c e. 598 static int id(SymEdge e) { return Parent::id(e); } 599 600 /// Adds a new node to the graph. 601 602 /// \warning It adds the new node to the front of the list. 603 /// (i.e. the lastly added node becomes the first.) 604 Node addNode() { 605 return Parent::addNode(); 606 } 607 608 SymEdge addEdge(Node u, Node v) { 609 SymEdge se = Parent::addEdge(u, v); 610 edge_maps.add(forward(se)); 611 edge_maps.add(backward(se)); 612 return se; 613 } 614 615 /// Finds an edge between two nodes. 616 617 /// Finds an edge from node \c u to node \c v. 618 /// 619 /// If \c prev is \ref INVALID (this is the default value), then 620 /// It finds the first edge from \c u to \c v. Otherwise it looks for 621 /// the next edge from \c u to \c v after \c prev. 622 /// \return The found edge or INVALID if there is no such an edge. 623 Edge findEdge(Node u, Node v, Edge prev = INVALID) 624 { 625 if (prev == INVALID || id(prev) & 1 == 0) { 626 SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); 627 if (se != INVALID) return forward(se); 628 } else { 629 SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); 630 if (se != INVALID) return backward(se); 631 } 632 return INVALID; 633 } 634 635 // /// Finds an symmetric edge between two nodes. 636 637 // /// Finds an symmetric edge from node \c u to node \c v. 638 // /// 639 // /// If \c prev is \ref INVALID (this is the default value), then 640 // /// It finds the first edge from \c u to \c v. Otherwise it looks for 641 // /// the next edge from \c u to \c v after \c prev. 642 // /// \return The found edge or INVALID if there is no such an edge. 643 644 // SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID) 645 // { 646 // if (prev == INVALID || id(prev) & 1 == 0) { 647 // SymEdge se = Parent::findEdge(u, v, SymEdge(prev)); 648 // if (se != INVALID) return se; 649 // } else { 650 // SymEdge se = Parent::findEdge(v, u, SymEdge(prev)); 651 // if (se != INVALID) return se; 652 // } 653 // return INVALID; 654 // } 655 656 public: 657 658 void clear() { 659 edge_maps.clear(); 660 Parent::clear(); 661 } 662 663 static Edge opposite(Edge e) { 664 return Edge(id(e) ^ 1); 665 } 666 667 static Edge forward(SymEdge e) { 668 return Edge(id(e) << 1); 669 } 670 671 static Edge backward(SymEdge e) { 672 return Edge((id(e) << 1) | 1); 673 } 674 675 }; 301 676 ///Graph for bidirectional edges. 302 677 … … 319 694 //\sa SmartGraph. 320 695 321 class SymSmartGraph : public SmartGraph696 /* class SymSmartGraph : public SmartGraph 322 697 { 323 698 public: … … 354 729 355 730 356 };731 };*/ 357 732 358 733 /// @} -
src/lemon/vector_map.h
r921 r937 32 32 /// @{ 33 33 34 /** The ArrayMap template class is graph map structure what34 /** The VectorMap template class is graph map structure what 35 35 * automatically updates the map when a key is added to or erased from 36 36 * the map. This map factory uses the allocators to implement … … 38 38 * uses the std::vector to implement the container function. 39 39 * 40 * The template parameter is the MapRegistry that the maps41 * will belong to and the ValueType.40 * \param MapRegistry The MapRegistry that the maps will belong to. 41 * \param Value The value type of the map. 42 42 * 43 * \todo It should use a faster initialization using the maxNodeId() or 44 * maxEdgeId() function of the graph instead of iterating through each 45 * edge/node. 43 * \author Balazs Dezso 46 44 */ 47 45 … … 85 83 typedef typename Container::const_pointer ConstPointerType; 86 84 87 /** Graph and Registry initialized map constructor. 85 /// Constructor to attach the new map into a registry. 86 87 /** Constructor to attach the new map into a registry. 88 * It adds all the nodes or edges of the graph to the map. 88 89 */ 89 90 VectorMap(const Graph& g, MapRegistry& r) 90 91 : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {} 91 92 92 /** Constructor to use default value to initialize the map. 93 /// Constructor uses given value to initialize the map. 94 95 /** Constructor uses given value to initialize the map. 96 * It adds all the nodes or edges of the graph to the map. 93 97 */ 94 98 VectorMap(const Graph& g, MapRegistry& r, const Value& v) 95 99 : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {} 96 100 101 /// Assign operator to copy a map of an other map type. 102 97 103 /** Assign operator to copy a map of an other map type. 104 * This map's value type must be assignable by the other 105 * map type's value type. 98 106 */ 99 107 template <typename TT> … … 106 114 } 107 115 116 /// Assign operator to copy a map of an other map type. 117 108 118 /** Assign operator to copy a map of an other map type. 119 * This map's value type must be assignable by the other 120 * map type's value type. 109 121 */ 110 122 template <typename TT> … … 120 132 return *this; 121 133 } 134 135 /// The subcript operator. 136 122 137 /** 123 138 * The subscript operator. The map can be subscripted by the … … 129 144 } 130 145 146 /// The const subcript operator. 147 131 148 /** 132 149 * The const subscript operator. The map can be subscripted by the … … 138 155 } 139 156 157 ///Setter function of the map. 158 140 159 /** Setter function of the map. Equivalent with map[key] = val. 141 160 * This is a compatibility feature with the not dereferable maps. … … 145 164 container[id] = val; 146 165 } 147 148 /** Add a new key to the map. It called by the map registry. 166 /// Adds a new key to the map. 167 168 /** Adds a new key to the map. It called by the map registry 169 * and it overrides the \ref MapRegistry::MapBase MapBase's 170 * add() member function. 149 171 */ 150 172 void add(const KeyType& key) { … … 154 176 } 155 177 } 156 157 /** Erase a key from the map. It called by the map registry. 178 179 /// Erases a key from the map. 180 181 /** Erase a key from the map. It called by the map registry 182 * and it overrides the \ref MapRegistry::MapBase MapBase's 183 * erase() member function. 158 184 */ 159 185 void erase(const KeyType& key) {} 160 186 161 /** Clear the data structure. 162 */ 187 /// Makes empty the map. 188 189 /** Makes empty the map. It called by the map registry 190 * and it overrides the \ref MapRegistry::MapBase MapBase's 191 * clear() member function. 192 */ 193 163 194 void clear() { 164 195 container.clear(); -
src/test/Makefile.am
r919 r937 10 10 dijkstra_test \ 11 11 graph_test \ 12 sym_graph_test \ 12 13 graph_wrapper_test \ 13 14 kruskal_test \ … … 29 30 dijkstra_test_SOURCES = dijkstra_test.cc 30 31 graph_test_SOURCES = graph_test.cc 32 sym_graph_test_SOURCES = sym_graph_test.cc 31 33 graph_wrapper_test_SOURCES = graph_wrapper_test.cc 32 34 kruskal_test_SOURCES = kruskal_test.cc -
src/test/graph_test.cc
r921 r937 64 64 checkGraphInEdgeList(G,n,3); 65 65 checkGraphOutEdgeList(G,n,3); 66 ++n;67 66 } 68 67 } … … 83 82 84 83 //Compile SymSmartGraph 85 template void lemon::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);86 template void lemon::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);84 //template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &); 85 //template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &); 87 86 88 87 //Compile ListGraph … … 93 92 94 93 //Compile SymListGraph 95 template void lemon::checkCompileGraph<SymListGraph>(SymListGraph &);96 template void lemon::checkCompileErasableGraph<SymListGraph>(SymListGraph &);97 template void lemon::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);94 //template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &); 95 //template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &); 96 //template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &); 98 97 99 98 //Compile FullGraph … … 132 131 } 133 132 { 134 SymSmartGraph G;135 addPetersen(G);136 checkPetersen(G);133 // SymSmartGraph G; 134 // addPetersen(G); 135 // checkPetersen(G); 137 136 } 138 137 { 139 SymListGraph G;140 addPetersen(G);141 checkPetersen(G);138 // SymListGraph G; 139 // addPetersen(G); 140 // checkPetersen(G); 142 141 } 143 142 -
src/test/graph_test.h
r921 r937 299 299 for(int i=0;i<nn;i++) { 300 300 check(e!=INVALID,"Wrong OutEdge list linking."); 301 check(n==G.tail(e), "Wrong OutEdge list linking."); 301 302 ++e; 302 303 } … … 311 312 for(int i=0;i<nn;i++) { 312 313 check(e!=INVALID,"Wrong InEdge list linking."); 314 check(n==G.head(e), "Wrong InEdge list linking."); 313 315 ++e; 314 316 } -
src/test/test_tools.h
r921 r937 68 68 69 69 ///Adds a Petersen graph to \c G. 70 ///\return The nodes end edges ogthe generated graph.70 ///\return The nodes and edges of the generated graph. 71 71 72 72 template<typename Graph> … … 88 88 } 89 89 90 ///Structure returned by \ref addSymPetersen(). 90 91 92 ///Structure returned by \ref addSymPetersen(). 93 /// 94 template<class Graph> struct SymPetStruct 95 { 96 ///Vector containing the outer nodes. 97 std::vector<typename Graph::Node> outer; 98 ///Vector containing the inner nodes. 99 std::vector<typename Graph::Node> inner; 100 ///Vector containing the edges of the inner circle. 101 std::vector<typename Graph::SymEdge> incir; 102 ///Vector containing the edges of the outer circle. 103 std::vector<typename Graph::SymEdge> outcir; 104 ///Vector containing the chord edges. 105 std::vector<typename Graph::SymEdge> chords; 106 }; 107 108 ///Adds a Petersen graph to the symmetric \c G. 109 110 ///Adds a Petersen graph to the symmetric \c G. 111 ///\return The nodes and edges of the generated graph. 112 113 template<typename Graph> 114 SymPetStruct<Graph> addSymPetersen(Graph &G,int num=5) 115 { 116 SymPetStruct<Graph> n; 117 118 for(int i=0;i<num;i++) { 119 n.outer.push_back(G.addNode()); 120 n.inner.push_back(G.addNode()); 121 } 122 123 for(int i=0;i<num;i++) { 124 n.chords.push_back(G.addEdge(n.outer[i],n.inner[i])); 125 n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5])); 126 n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5])); 127 } 128 return n; 129 } 91 130 92 131 #endif
Note: See TracChangeset
for help on using the changeset viewer.