Changeset 209:765619b7cbb2 in lemon1.2 for lemon/graph_utils.h
 Timestamp:
 07/13/08 20:51:02 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_utils.h
r199 r209 1 /* * C++*1 /* * mode: C++; indenttabsmode: nil; * 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 20032008 … … 47 47 ///This \c \#define creates convenience typedefs for the following types 48 48 ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt, 49 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 49 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 50 50 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. 51 51 /// … … 53 53 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() 54 54 ///macro. 55 #define DIGRAPH_TYPEDEFS(Digraph) 56 typedef Digraph::Node Node; 57 typedef Digraph::NodeIt NodeIt; 58 typedef Digraph::Arc Arc; 59 typedef Digraph::ArcIt ArcIt; 60 typedef Digraph::InArcIt InArcIt; 61 typedef Digraph::OutArcIt OutArcIt; 62 typedef Digraph::NodeMap<bool> BoolNodeMap; 63 typedef Digraph::NodeMap<int> IntNodeMap; 64 typedef Digraph::NodeMap<double> DoubleNodeMap; 65 typedef Digraph::ArcMap<bool> BoolArcMap; 66 typedef Digraph::ArcMap<int> IntArcMap; 55 #define DIGRAPH_TYPEDEFS(Digraph) \ 56 typedef Digraph::Node Node; \ 57 typedef Digraph::NodeIt NodeIt; \ 58 typedef Digraph::Arc Arc; \ 59 typedef Digraph::ArcIt ArcIt; \ 60 typedef Digraph::InArcIt InArcIt; \ 61 typedef Digraph::OutArcIt OutArcIt; \ 62 typedef Digraph::NodeMap<bool> BoolNodeMap; \ 63 typedef Digraph::NodeMap<int> IntNodeMap; \ 64 typedef Digraph::NodeMap<double> DoubleNodeMap; \ 65 typedef Digraph::ArcMap<bool> BoolArcMap; \ 66 typedef Digraph::ArcMap<int> IntArcMap; \ 67 67 typedef Digraph::ArcMap<double> DoubleArcMap 68 68 … … 73 73 ///\note Use this macro, if the graph type is a dependent type, 74 74 ///ie. the graph type depend on a template parameter. 75 #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) 76 typedef typename Digraph::Node Node; 77 typedef typename Digraph::NodeIt NodeIt; 78 typedef typename Digraph::Arc Arc; 79 typedef typename Digraph::ArcIt ArcIt; 80 typedef typename Digraph::InArcIt InArcIt; 81 typedef typename Digraph::OutArcIt OutArcIt; 82 typedef typename Digraph::template NodeMap<bool> BoolNodeMap; 83 typedef typename Digraph::template NodeMap<int> IntNodeMap; 84 typedef typename Digraph::template NodeMap<double> DoubleNodeMap; 85 typedef typename Digraph::template ArcMap<bool> BoolArcMap; 86 typedef typename Digraph::template ArcMap<int> IntArcMap; 75 #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \ 76 typedef typename Digraph::Node Node; \ 77 typedef typename Digraph::NodeIt NodeIt; \ 78 typedef typename Digraph::Arc Arc; \ 79 typedef typename Digraph::ArcIt ArcIt; \ 80 typedef typename Digraph::InArcIt InArcIt; \ 81 typedef typename Digraph::OutArcIt OutArcIt; \ 82 typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \ 83 typedef typename Digraph::template NodeMap<int> IntNodeMap; \ 84 typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \ 85 typedef typename Digraph::template ArcMap<bool> BoolArcMap; \ 86 typedef typename Digraph::template ArcMap<int> IntArcMap; \ 87 87 typedef typename Digraph::template ArcMap<double> DoubleArcMap 88 88 89 89 ///Creates convenience typedefs for the graph types and iterators 90 90 … … 97 97 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() 98 98 ///macro. 99 #define GRAPH_TYPEDEFS(Graph) 100 DIGRAPH_TYPEDEFS(Graph); 101 typedef Graph::Edge Edge; 102 typedef Graph::EdgeIt EdgeIt; 103 typedef Graph::IncEdgeIt IncEdgeIt; 104 typedef Graph::EdgeMap<bool> BoolEdgeMap; 105 typedef Graph::EdgeMap<int> IntEdgeMap; 99 #define GRAPH_TYPEDEFS(Graph) \ 100 DIGRAPH_TYPEDEFS(Graph); \ 101 typedef Graph::Edge Edge; \ 102 typedef Graph::EdgeIt EdgeIt; \ 103 typedef Graph::IncEdgeIt IncEdgeIt; \ 104 typedef Graph::EdgeMap<bool> BoolEdgeMap; \ 105 typedef Graph::EdgeMap<int> IntEdgeMap; \ 106 106 typedef Graph::EdgeMap<double> DoubleEdgeMap 107 107 … … 112 112 ///\note Use this macro, if the graph type is a dependent type, 113 113 ///ie. the graph type depend on a template parameter. 114 #define TEMPLATE_GRAPH_TYPEDEFS(Graph) 115 TEMPLATE_DIGRAPH_TYPEDEFS(Graph); 116 typedef typename Graph::Edge Edge; 117 typedef typename Graph::EdgeIt EdgeIt; 118 typedef typename Graph::IncEdgeIt IncEdgeIt; 119 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; 120 typedef typename Graph::template EdgeMap<int> IntEdgeMap; 114 #define TEMPLATE_GRAPH_TYPEDEFS(Graph) \ 115 TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \ 116 typedef typename Graph::Edge Edge; \ 117 typedef typename Graph::EdgeIt EdgeIt; \ 118 typedef typename Graph::IncEdgeIt IncEdgeIt; \ 119 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \ 120 typedef typename Graph::template EdgeMap<int> IntEdgeMap; \ 121 121 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap 122 122 … … 139 139 140 140 namespace _graph_utils_bits { 141 141 142 142 template <typename Graph, typename Enable = void> 143 143 struct CountNodesSelector { … … 149 149 template <typename Graph> 150 150 struct CountNodesSelector< 151 Graph, typename 152 enable_if<typename Graph::NodeNumTag, void>::type> 151 Graph, typename 152 enable_if<typename Graph::NodeNumTag, void>::type> 153 153 { 154 154 static int count(const Graph &g) { 155 155 return g.nodeNum(); 156 156 } 157 }; 157 }; 158 158 } 159 159 … … 164 164 /// graph structures it is specialized to run in O(1). 165 165 /// 166 /// If the graph contains a \e nodeNum() member function and a 166 /// If the graph contains a \e nodeNum() member function and a 167 167 /// \e NodeNumTag tag then this function calls directly the member 168 168 /// function to query the cardinality of the node set. … … 175 175 176 176 namespace _graph_utils_bits { 177 177 178 178 template <typename Graph, typename Enable = void> 179 179 struct CountArcsSelector { … … 185 185 template <typename Graph> 186 186 struct CountArcsSelector< 187 Graph, 188 typename enable_if<typename Graph::ArcNumTag, void>::type> 187 Graph, 188 typename enable_if<typename Graph::ArcNumTag, void>::type> 189 189 { 190 190 static int count(const Graph &g) { 191 191 return g.arcNum(); 192 192 } 193 }; 193 }; 194 194 } 195 195 … … 200 200 /// graph structures it is specialized to run in O(1). 201 201 /// 202 /// If the graph contains a \e arcNum() member function and a 202 /// If the graph contains a \e arcNum() member function and a 203 203 /// \e EdgeNumTag tag then this function calls directly the member 204 204 /// function to query the cardinality of the arc set. … … 210 210 // Edge counting: 211 211 namespace _graph_utils_bits { 212 212 213 213 template <typename Graph, typename Enable = void> 214 214 struct CountEdgesSelector { … … 220 220 template <typename Graph> 221 221 struct CountEdgesSelector< 222 Graph, 223 typename enable_if<typename Graph::EdgeNumTag, void>::type> 222 Graph, 223 typename enable_if<typename Graph::EdgeNumTag, void>::type> 224 224 { 225 225 static int count(const Graph &g) { 226 226 return g.edgeNum(); 227 227 } 228 }; 228 }; 229 229 } 230 230 … … 235 235 /// graph structures it is specialized to run in O(1). 236 236 /// 237 /// If the graph contains a \e edgeNum() member function and a 237 /// If the graph contains a \e edgeNum() member function and a 238 238 /// \e EdgeNumTag tag then this function calls directly the member 239 239 /// function to query the cardinality of the edge set. … … 257 257 /// 258 258 /// This function counts the number of the outarcs from node \c n 259 /// in the graph. 259 /// in the graph. 260 260 template <typename Graph> 261 261 inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) { … … 266 266 /// 267 267 /// This function counts the number of the inarcs to node \c n 268 /// in the graph. 268 /// in the graph. 269 269 template <typename Graph> 270 270 inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) { … … 275 275 /// 276 276 /// This function counts the number of the incedges to node \c n 277 /// in the graph. 277 /// in the graph. 278 278 template <typename Graph> 279 279 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { … … 282 282 283 283 namespace _graph_utils_bits { 284 284 285 285 template <typename Graph, typename Enable = void> 286 286 struct FindArcSelector { … … 302 302 template <typename Graph> 303 303 struct FindArcSelector< 304 Graph, 305 typename enable_if<typename Graph::FindEdgeTag, void>::type> 304 Graph, 305 typename enable_if<typename Graph::FindEdgeTag, void>::type> 306 306 { 307 307 typedef typename Graph::Node Node; … … 310 310 return g.findArc(u, v, prev); 311 311 } 312 }; 312 }; 313 313 } 314 314 … … 334 334 ///\sa ConArcIt 335 335 template <typename Graph> 336 inline typename Graph::Arc 336 inline typename Graph::Arc 337 337 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v, 338 338 typename Graph::Arc prev = INVALID) { … … 342 342 /// \brief Iterator for iterating on arcs connected the same nodes. 343 343 /// 344 /// Iterator for iterating on arcs connected the same nodes. It is 344 /// Iterator for iterating on arcs connected the same nodes. It is 345 345 /// higher level interface for the findArc() function. You can 346 346 /// use it the following way: … … 350 350 /// } 351 351 ///\endcode 352 /// 352 /// 353 353 ///\sa findArc() 354 354 ///\sa ArcLookUp … … 375 375 /// \brief Constructor. 376 376 /// 377 /// Construct a new ConArcIt which continues the iterating from 377 /// Construct a new ConArcIt which continues the iterating from 378 378 /// the \c e arc. 379 379 ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {} 380 380 381 381 /// \brief Increment operator. 382 382 /// 383 383 /// It increments the iterator and gives back the next arc. 384 384 ConArcIt& operator++() { 385 Parent::operator=(findArc(_graph, _graph.source(*this), 386 385 Parent::operator=(findArc(_graph, _graph.source(*this), 386 _graph.target(*this), *this)); 387 387 return *this; 388 388 } … … 392 392 393 393 namespace _graph_utils_bits { 394 394 395 395 template <typename Graph, typename Enable = void> 396 396 struct FindEdgeSelector { … … 426 426 template <typename Graph> 427 427 struct FindEdgeSelector< 428 Graph, 429 typename enable_if<typename Graph::FindEdgeTag, void>::type> 428 Graph, 429 typename enable_if<typename Graph::FindEdgeTag, void>::type> 430 430 { 431 431 typedef typename Graph::Node Node; … … 434 434 return g.findEdge(u, v, prev); 435 435 } 436 }; 436 }; 437 437 } 438 438 … … 450 450 /// Thus you can iterate through each arc from \c u to \c v as it follows. 451 451 ///\code 452 /// for(Edge e = findEdge(g,u,v); e != INVALID; 452 /// for(Edge e = findEdge(g,u,v); e != INVALID; 453 453 /// e = findEdge(g,u,v,e)) { 454 454 /// ... … … 459 459 460 460 template <typename Graph> 461 inline typename Graph::Edge 461 inline typename Graph::Edge 462 462 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v, 463 463 typename Graph::Edge p = INVALID) { … … 467 467 /// \brief Iterator for iterating on edges connected the same nodes. 468 468 /// 469 /// Iterator for iterating on edges connected the same nodes. It is 469 /// Iterator for iterating on edges connected the same nodes. It is 470 470 /// higher level interface for the findEdge() function. You can 471 471 /// use it the following way: … … 497 497 /// \brief Constructor. 498 498 /// 499 /// Construct a new ConEdgeIt which continues the iterating from 499 /// Construct a new ConEdgeIt which continues the iterating from 500 500 /// the \c e edge. 501 501 ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {} 502 502 503 503 /// \brief Increment operator. 504 504 /// 505 505 /// It increments the iterator and gives back the next edge. 506 506 ConEdgeIt& operator++() { 507 Parent::operator=(findEdge(_graph, _graph.u(*this), 508 507 Parent::operator=(findEdge(_graph, _graph.u(*this), 508 _graph.v(*this), *this)); 509 509 return *this; 510 510 } … … 519 519 public: 520 520 virtual void copy(const Digraph& from, const RefMap& refMap) = 0; 521 521 522 522 virtual ~MapCopyBase() {} 523 523 }; 524 524 525 template <typename Digraph, typename Item, typename RefMap, 525 template <typename Digraph, typename Item, typename RefMap, 526 526 typename ToMap, typename FromMap> 527 527 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> { 528 528 public: 529 529 530 MapCopy(ToMap& tmap, const FromMap& map) 530 MapCopy(ToMap& tmap, const FromMap& map) 531 531 : _tmap(tmap), _map(map) {} 532 532 533 533 virtual void copy(const Digraph& digraph, const RefMap& refMap) { 534 534 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt; … … 548 548 549 549 ItemCopy(It& it, const Item& item) : _it(it), _item(item) {} 550 550 551 551 virtual void copy(const Digraph&, const RefMap& refMap) { 552 552 _it = refMap[_item]; … … 563 563 564 564 RefCopy(Ref& map) : _map(map) {} 565 565 566 566 virtual void copy(const Digraph& digraph, const RefMap& refMap) { 567 567 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt; … … 575 575 }; 576 576 577 template <typename Digraph, typename Item, typename RefMap, 577 template <typename Digraph, typename Item, typename RefMap, 578 578 typename CrossRef> 579 579 class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> { … … 581 581 582 582 CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {} 583 583 584 584 virtual void copy(const Digraph& digraph, const RefMap& refMap) { 585 585 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt; … … 602 602 } 603 603 for (typename From::ArcIt it(from); it != INVALID; ++it) { 604 arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)], 605 604 arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)], 605 nodeRefMap[from.target(it)]); 606 606 } 607 607 } … … 610 610 template <typename Digraph> 611 611 struct DigraphCopySelector< 612 Digraph, 613 typename enable_if<typename Digraph::BuildTag, void>::type> 612 Digraph, 613 typename enable_if<typename Digraph::BuildTag, void>::type> 614 614 { 615 615 template <typename From, typename NodeRefMap, typename ArcRefMap> … … 629 629 } 630 630 for (typename From::EdgeIt it(from); it != INVALID; ++it) { 631 edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)], 632 631 edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)], 632 nodeRefMap[from.v(it)]); 633 633 } 634 634 } … … 637 637 template <typename Graph> 638 638 struct GraphCopySelector< 639 Graph, 640 typename enable_if<typename Graph::BuildTag, void>::type> 639 Graph, 640 typename enable_if<typename Graph::BuildTag, void>::type> 641 641 { 642 642 template <typename From, typename NodeRefMap, typename EdgeRefMap> … … 698 698 typedef typename From::template NodeMap<TNode> NodeRefMap; 699 699 typedef typename From::template ArcMap<TArc> ArcRefMap; 700 701 702 public: 700 701 702 public: 703 703 704 704 … … 707 707 /// It copies the content of the \c _from digraph into the 708 708 /// \c _to digraph. 709 DigraphCopy(To& to, const From& from) 709 DigraphCopy(To& to, const From& from) 710 710 : _from(from), _to(to) {} 711 711 … … 731 731 template <typename NodeRef> 732 732 DigraphCopy& nodeRef(NodeRef& map) { 733 _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, 734 733 _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, 734 NodeRefMap, NodeRef>(map)); 735 735 return *this; 736 736 } … … 745 745 DigraphCopy& nodeCrossRef(NodeCrossRef& map) { 746 746 _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node, 747 747 NodeRefMap, NodeCrossRef>(map)); 748 748 return *this; 749 749 } … … 756 756 template <typename ToMap, typename FromMap> 757 757 DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { 758 _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, 759 758 _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, 759 NodeRefMap, ToMap, FromMap>(tmap, map)); 760 760 return *this; 761 761 } … … 765 765 /// Make a copy of the given node. 766 766 DigraphCopy& node(TNode& tnode, const Node& snode) { 767 _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, 768 767 _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, 768 NodeRefMap, TNode>(tnode, snode)); 769 769 return *this; 770 770 } … … 775 775 template <typename ArcRef> 776 776 DigraphCopy& arcRef(ArcRef& map) { 777 _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, 778 777 _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, 778 ArcRefMap, ArcRef>(map)); 779 779 return *this; 780 780 } … … 787 787 DigraphCopy& arcCrossRef(ArcCrossRef& map) { 788 788 _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc, 789 789 ArcRefMap, ArcCrossRef>(map)); 790 790 return *this; 791 791 } … … 793 793 /// \brief Make copy of the given map. 794 794 /// 795 /// Makes copy of the given map for the newly created digraph. 795 /// Makes copy of the given map for the newly created digraph. 796 796 /// The new map's key type is the to digraph's arc type, 797 797 /// and the copied map's key type is the from digraph's arc 798 /// type. 798 /// type. 799 799 template <typename ToMap, typename FromMap> 800 800 DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) { 801 _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, 802 801 _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, 802 ArcRefMap, ToMap, FromMap>(tmap, map)); 803 803 return *this; 804 804 } … … 808 808 /// Make a copy of the given arc. 809 809 DigraphCopy& arc(TArc& tarc, const Arc& sarc) { 810 _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, 811 810 _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, 811 ArcRefMap, TArc>(tarc, sarc)); 812 812 return *this; 813 813 } … … 826 826 for (int i = 0; i < int(_arc_maps.size()); ++i) { 827 827 _arc_maps[i]>copy(_from, arcRefMap); 828 } 828 } 829 829 } 830 830 … … 835 835 To& _to; 836 836 837 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 837 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 838 838 _node_maps; 839 839 840 std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 840 std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 841 841 _arc_maps; 842 842 … … 851 851 /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); 852 852 ///\endcode 853 /// 853 /// 854 854 /// After the copy the \c nr map will contain the mapping from the 855 855 /// nodes of the \c from digraph to the nodes of the \c to digraph and … … 857 857 /// to the arcs of the \c from digraph. 858 858 /// 859 /// \see DigraphCopy 859 /// \see DigraphCopy 860 860 template <typename To, typename From> 861 861 DigraphCopy<To, From> copyDigraph(To& to, const From& from) { … … 918 918 struct ArcRefMap { 919 919 ArcRefMap(const To& to, const From& from, 920 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) 921 : _to(to), _from(from), 920 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) 921 : _to(to), _from(from), 922 922 _edge_ref(edge_ref), _node_ref(node_ref) {} 923 923 … … 927 927 Value operator[](const Key& key) const { 928 928 bool forward = _from.u(key) != _from.v(key) ? 929 _node_ref[_from.source(key)] == 930 931 932 return _to.direct(_edge_ref[key], forward); 933 } 934 929 _node_ref[_from.source(key)] == 930 _to.source(_to.direct(_edge_ref[key], true)) : 931 _from.direction(key); 932 return _to.direct(_edge_ref[key], forward); 933 } 934 935 935 const To& _to; 936 936 const From& _from; … … 939 939 }; 940 940 941 942 public: 941 942 public: 943 943 944 944 … … 947 947 /// It copies the content of the \c _from graph into the 948 948 /// \c _to graph. 949 GraphCopy(To& to, const From& from) 949 GraphCopy(To& to, const From& from) 950 950 : _from(from), _to(to) {} 951 951 … … 971 971 template <typename NodeRef> 972 972 GraphCopy& nodeRef(NodeRef& map) { 973 _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, 974 973 _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, 974 NodeRefMap, NodeRef>(map)); 975 975 return *this; 976 976 } … … 983 983 GraphCopy& nodeCrossRef(NodeCrossRef& map) { 984 984 _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node, 985 985 NodeRefMap, NodeCrossRef>(map)); 986 986 return *this; 987 987 } … … 989 989 /// \brief Make copy of the given map. 990 990 /// 991 /// Makes copy of the given map for the newly created graph. 991 /// Makes copy of the given map for the newly created graph. 992 992 /// The new map's key type is the to graph's node type, 993 993 /// and the copied map's key type is the from graph's node 994 /// type. 994 /// type. 995 995 template <typename ToMap, typename FromMap> 996 996 GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { 997 _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, 998 997 _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, 998 NodeRefMap, ToMap, FromMap>(tmap, map)); 999 999 return *this; 1000 1000 } … … 1004 1004 /// Make a copy of the given node. 1005 1005 GraphCopy& node(TNode& tnode, const Node& snode) { 1006 _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, 1007 1006 _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, 1007 NodeRefMap, TNode>(tnode, snode)); 1008 1008 return *this; 1009 1009 } … … 1014 1014 template <typename ArcRef> 1015 1015 GraphCopy& arcRef(ArcRef& map) { 1016 _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, 1017 1016 _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, 1017 ArcRefMap, ArcRef>(map)); 1018 1018 return *this; 1019 1019 } … … 1026 1026 GraphCopy& arcCrossRef(ArcCrossRef& map) { 1027 1027 _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc, 1028 1028 ArcRefMap, ArcCrossRef>(map)); 1029 1029 return *this; 1030 1030 } … … 1032 1032 /// \brief Make copy of the given map. 1033 1033 /// 1034 /// Makes copy of the given map for the newly created graph. 1034 /// Makes copy of the given map for the newly created graph. 1035 1035 /// The new map's key type is the to graph's arc type, 1036 1036 /// and the copied map's key type is the from graph's arc 1037 /// type. 1037 /// type. 1038 1038 template <typename ToMap, typename FromMap> 1039 1039 GraphCopy& arcMap(ToMap& tmap, const FromMap& map) { 1040 _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, 1041 1040 _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, 1041 ArcRefMap, ToMap, FromMap>(tmap, map)); 1042 1042 return *this; 1043 1043 } … … 1047 1047 /// Make a copy of the given arc. 1048 1048 GraphCopy& arc(TArc& tarc, const Arc& sarc) { 1049 _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, 1050 1049 _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, 1050 ArcRefMap, TArc>(tarc, sarc)); 1051 1051 return *this; 1052 1052 } … … 1057 1057 template <typename EdgeRef> 1058 1058 GraphCopy& edgeRef(EdgeRef& map) { 1059 _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge, 1060 1059 _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge, 1060 EdgeRefMap, EdgeRef>(map)); 1061 1061 return *this; 1062 1062 } … … 1068 1068 template <typename EdgeCrossRef> 1069 1069 GraphCopy& edgeCrossRef(EdgeCrossRef& map) { 1070 _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, 1071 1070 _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, 1071 Edge, EdgeRefMap, EdgeCrossRef>(map)); 1072 1072 return *this; 1073 1073 } … … 1075 1075 /// \brief Make copy of the given map. 1076 1076 /// 1077 /// Makes copy of the given map for the newly created graph. 1077 /// Makes copy of the given map for the newly created graph. 1078 1078 /// The new map's key type is the to graph's edge type, 1079 1079 /// and the copied map's key type is the from graph's edge 1080 /// type. 1080 /// type. 1081 1081 template <typename ToMap, typename FromMap> 1082 1082 GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) { 1083 _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge, 1084 1083 _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge, 1084 EdgeRefMap, ToMap, FromMap>(tmap, map)); 1085 1085 return *this; 1086 1086 } … … 1090 1090 /// Make a copy of the given edge. 1091 1091 GraphCopy& edge(TEdge& tedge, const Edge& sedge) { 1092 _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge, 1093 1092 _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge, 1093 EdgeRefMap, TEdge>(tedge, sedge)); 1094 1094 return *this; 1095 1095 } … … 1116 1116 1117 1117 private: 1118 1118 1119 1119 const From& _from; 1120 1120 To& _to; 1121 1121 1122 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 1122 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 1123 1123 _node_maps; 1124 1124 1125 std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 1125 std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 1126 1126 _arc_maps; 1127 1127 1128 std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 1128 std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 1129 1129 _edge_maps; 1130 1130 … … 1139 1139 /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); 1140 1140 ///\endcode 1141 /// 1141 /// 1142 1142 /// After the copy the \c nr map will contain the mapping from the 1143 1143 /// nodes of the \c from graph to the nodes of the \c to graph and … … 1145 1145 /// to the arcs of the \c from graph. 1146 1146 /// 1147 /// \see GraphCopy 1147 /// \see GraphCopy 1148 1148 template <typename To, typename From> 1149 GraphCopy<To, From> 1149 GraphCopy<To, From> 1150 1150 copyGraph(To& to, const From& from) { 1151 1151 return GraphCopy<To, From>(to, from); … … 1215 1215 /// 1216 1216 /// Gives back the given item from its id. 1217 /// 1217 /// 1218 1218 Item operator[](int id) const { return _graph>fromId(id, Item());} 1219 1219 … … 1225 1225 /// 1226 1226 /// Gives back the inverse of the IdMap. 1227 InverseMap inverse() const { return InverseMap(*_graph);} 1227 InverseMap inverse() const { return InverseMap(*_graph);} 1228 1228 1229 1229 }; 1230 1230 1231 1231 1232 1232 /// \brief General invertable graphmap type. 1233 1233 1234 /// This type provides simple invertable graphmaps. 1235 /// The InvertableMap wraps an arbitrary ReadWriteMap 1234 /// This type provides simple invertable graphmaps. 1235 /// The InvertableMap wraps an arbitrary ReadWriteMap 1236 1236 /// and if a key is set to a new value then store it 1237 1237 /// in the inverse map. … … 1248 1248 class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> { 1249 1249 private: 1250 1250 1251 1251 typedef DefaultMap<_Graph, _Item, _Value> Map; 1252 1252 typedef _Graph Graph; 1253 1253 1254 1254 typedef std::map<_Value, _Item> Container; 1255 Container _inv_map; 1255 Container _inv_map; 1256 1256 1257 1257 public: 1258 1258 1259 1259 /// The key type of InvertableMap (Node, Arc, Edge). 1260 1260 typedef typename Map::Key Key; … … 1268 1268 /// Construct a new InvertableMap for the graph. 1269 1269 /// 1270 explicit InvertableMap(const Graph& graph) : Map(graph) {} 1270 explicit InvertableMap(const Graph& graph) : Map(graph) {} 1271 1271 1272 1272 /// \brief Forward iterator for values. … … 1276 1276 /// be accessed in the [beginValue, endValue) range. 1277 1277 /// 1278 class ValueIterator 1278 class ValueIterator 1279 1279 : public std::iterator<std::forward_iterator_tag, Value> { 1280 1280 friend class InvertableMap; 1281 1281 private: 1282 ValueIterator(typename Container::const_iterator _it) 1282 ValueIterator(typename Container::const_iterator _it) 1283 1283 : it(_it) {} 1284 1284 public: 1285 1285 1286 1286 ValueIterator() {} 1287 1287 1288 1288 ValueIterator& operator++() { ++it; return *this; } 1289 ValueIterator operator++(int) { 1290 ValueIterator tmp(*this); 1289 ValueIterator operator++(int) { 1290 ValueIterator tmp(*this); 1291 1291 operator++(); 1292 return tmp; 1292 return tmp; 1293 1293 } 1294 1294 … … 1298 1298 bool operator==(ValueIterator jt) const { return it == jt.it; } 1299 1299 bool operator!=(ValueIterator jt) const { return it != jt.it; } 1300 1300 1301 1301 private: 1302 1302 typename Container::const_iterator it; … … 1305 1305 /// \brief Returns an iterator to the first value. 1306 1306 /// 1307 /// Returns an stl compatible iterator to the 1307 /// Returns an stl compatible iterator to the 1308 1308 /// first value of the map. The values of the 1309 1309 /// map can be accessed in the [beginValue, endValue) … … 1315 1315 /// \brief Returns an iterator after the last value. 1316 1316 /// 1317 /// Returns an stl compatible iterator after the 1317 /// Returns an stl compatible iterator after the 1318 1318 /// last value of the map. The values of the 1319 1319 /// map can be accessed in the [beginValue, endValue) … … 1322 1322 return ValueIterator(_inv_map.end()); 1323 1323 } 1324 1324 1325 1325 /// \brief The setter function of the map. 1326 1326 /// … … 1330 1330 typename Container::iterator it = _inv_map.find(oldval); 1331 1331 if (it != _inv_map.end() && it>second == key) { 1332 1333 } 1332 _inv_map.erase(it); 1333 } 1334 1334 _inv_map.insert(make_pair(val, key)); 1335 1335 Map::set(key, val); … … 1339 1339 /// 1340 1340 /// It gives back the value associated with the key. 1341 typename MapTraits<Map>::ConstReturnValue 1341 typename MapTraits<Map>::ConstReturnValue 1342 1342 operator[](const Key& key) const { 1343 1343 return Map::operator[](key); … … 1362 1362 typename Container::iterator it = _inv_map.find(val); 1363 1363 if (it != _inv_map.end() && it>second == key) { 1364 1364 _inv_map.erase(it); 1365 1365 } 1366 1366 Map::erase(key); … … 1373 1373 virtual void erase(const std::vector<Key>& keys) { 1374 1374 for (int i = 0; i < int(keys.size()); ++i) { 1375 1376 1377 1378 1379 1375 Value val = Map::operator[](keys[i]); 1376 typename Container::iterator it = _inv_map.find(val); 1377 if (it != _inv_map.end() && it>second == keys[i]) { 1378 _inv_map.erase(it); 1379 } 1380 1380 } 1381 1381 Map::erase(keys); … … 1396 1396 /// 1397 1397 /// The inverse of this map. The subscript operator of the map 1398 /// gives back always the item what was last assigned to the value. 1398 /// gives back always the item what was last assigned to the value. 1399 1399 class InverseMap { 1400 1400 public: … … 1402 1402 /// 1403 1403 /// Constructor of the InverseMap. 1404 explicit InverseMap(const InvertableMap& inverted) 1404 explicit InverseMap(const InvertableMap& inverted) 1405 1405 : _inverted(inverted) {} 1406 1406 … … 1408 1408 typedef typename InvertableMap::Key Value; 1409 1409 /// The key type of the InverseMap. 1410 typedef typename InvertableMap::Value Key; 1411 1412 /// \brief Subscript operator. 1410 typedef typename InvertableMap::Value Key; 1411 1412 /// \brief Subscript operator. 1413 1413 /// 1414 /// Subscript operator. It gives back always the item 1414 /// Subscript operator. It gives back always the item 1415 1415 /// what was last assigned to the value. 1416 1416 Value operator[](const Key& key) const { 1417 1418 } 1419 1417 return _inverted(key); 1418 } 1419 1420 1420 private: 1421 1421 const InvertableMap& _inverted; … … 1427 1427 InverseMap inverse() const { 1428 1428 return InverseMap(*this); 1429 } 1430 1431 1432 1429 } 1430 1431 1432 1433 1433 }; 1434 1434 1435 /// \brief Provides a mutable, continuous and unique descriptor for each 1435 /// \brief Provides a mutable, continuous and unique descriptor for each 1436 1436 /// item in the graph. 1437 1437 /// … … 1446 1446 /// 1447 1447 /// \tparam _Graph The graph class the \c DescriptorMap belongs to. 1448 /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or 1448 /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or 1449 1449 /// Edge. 1450 1450 template <typename _Graph, typename _Item> … … 1468 1468 explicit DescriptorMap(const Graph& _graph) : Map(_graph) { 1469 1469 Item it; 1470 const typename Map::Notifier* nf = Map::notifier(); 1470 const typename Map::Notifier* nf = Map::notifier(); 1471 1471 for (nf>first(it); it != INVALID; nf>next(it)) { 1472 1473 _inv_map.push_back(it); 1474 } 1472 Map::set(it, _inv_map.size()); 1473 _inv_map.push_back(it); 1474 } 1475 1475 } 1476 1476 … … 1494 1494 Map::add(items); 1495 1495 for (int i = 0; i < int(items.size()); ++i) { 1496 1497 1496 Map::set(items[i], _inv_map.size()); 1497 _inv_map.push_back(items[i]); 1498 1498 } 1499 1499 } … … 1516 1516 virtual void erase(const std::vector<Item>& items) { 1517 1517 for (int i = 0; i < int(items.size()); ++i) { 1518 1519 1520 1518 Map::set(_inv_map.back(), Map::operator[](items[i])); 1519 _inv_map[Map::operator[](items[i])] = _inv_map.back(); 1520 _inv_map.pop_back(); 1521 1521 } 1522 1522 Map::erase(items); … … 1530 1530 Map::build(); 1531 1531 Item it; 1532 const typename Map::Notifier* nf = Map::notifier(); 1532 const typename Map::Notifier* nf = Map::notifier(); 1533 1533 for (nf>first(it); it != INVALID; nf>next(it)) { 1534 1535 _inv_map.push_back(it); 1536 } 1537 } 1538 1534 Map::set(it, _inv_map.size()); 1535 _inv_map.push_back(it); 1536 } 1537 } 1538 1539 1539 /// \brief Clear the keys from the map. 1540 1540 /// … … 1580 1580 return _inv_map[id]; 1581 1581 } 1582 1582 1583 1583 private: 1584 1584 … … 1595 1595 /// 1596 1596 /// Constructor of the InverseMap. 1597 explicit InverseMap(const DescriptorMap& inverted) 1598 1597 explicit InverseMap(const DescriptorMap& inverted) 1598 : _inverted(inverted) {} 1599 1599 1600 1600 … … 1602 1602 typedef typename DescriptorMap::Key Value; 1603 1603 /// The key type of the InverseMap. 1604 typedef typename DescriptorMap::Value Key; 1605 1606 /// \brief Subscript operator. 1604 typedef typename DescriptorMap::Value Key; 1605 1606 /// \brief Subscript operator. 1607 1607 /// 1608 /// Subscript operator. It gives back the item 1608 /// Subscript operator. It gives back the item 1609 1609 /// that the descriptor belongs to currently. 1610 1610 Value operator[](const Key& key) const { 1611 1611 return _inverted(key); 1612 1612 } 1613 1613 … … 1616 1616 /// Returns the size of the map. 1617 1617 unsigned int size() const { 1618 1619 } 1620 1618 return _inverted.size(); 1619 } 1620 1621 1621 private: 1622 1622 const DescriptorMap& _inverted; … … 1633 1633 /// \brief Returns the source of the given arc. 1634 1634 /// 1635 /// The SourceMap gives back the source Node of the given arc. 1635 /// The SourceMap gives back the source Node of the given arc. 1636 1636 /// \see TargetMap 1637 1637 template <typename Digraph> … … 1651 1651 /// 1652 1652 /// The subscript operator. 1653 /// \param arc The arc 1654 /// \return The source of the arc 1653 /// \param arc The arc 1654 /// \return The source of the arc 1655 1655 Value operator[](const Key& arc) const { 1656 1656 return _digraph.source(arc); … … 1668 1668 inline SourceMap<Digraph> sourceMap(const Digraph& digraph) { 1669 1669 return SourceMap<Digraph>(digraph); 1670 } 1670 } 1671 1671 1672 1672 /// \brief Returns the target of the given arc. 1673 1673 /// 1674 /// The TargetMap gives back the target Node of the given arc. 1674 /// The TargetMap gives back the target Node of the given arc. 1675 1675 /// \see SourceMap 1676 1676 template <typename Digraph> … … 1690 1690 /// 1691 1691 /// The subscript operator. 1692 /// \param e The arc 1693 /// \return The target of the arc 1692 /// \param e The arc 1693 /// \return The target of the arc 1694 1694 Value operator[](const Key& e) const { 1695 1695 return _digraph.target(e); … … 1729 1729 /// 1730 1730 /// The subscript operator. 1731 /// \param key An edge 1732 /// \return The "forward" directed arc view of edge 1731 /// \param key An edge 1732 /// \return The "forward" directed arc view of edge 1733 1733 Value operator[](const Key& key) const { 1734 1734 return _graph.direct(key, true); … … 1768 1768 /// 1769 1769 /// The subscript operator. 1770 /// \param key An edge 1771 /// \return The "backward" directed arc view of edge 1770 /// \param key An edge 1771 /// \return The "backward" directed arc view of edge 1772 1772 Value operator[](const Key& key) const { 1773 1773 return _graph.direct(key, false); … … 1801 1801 /// 1802 1802 /// Contructor of the map 1803 explicit PotentialDifferenceMap(const Digraph& digraph, 1804 const NodeMap& potential) 1803 explicit PotentialDifferenceMap(const Digraph& digraph, 1804 const NodeMap& potential) 1805 1805 : _digraph(digraph), _potential(potential) {} 1806 1806 … … 1809 1809 /// Const subscription operator 1810 1810 Value operator[](const Key& arc) const { 1811 return _potential[_digraph.target(arc)]  1812 1811 return _potential[_digraph.target(arc)]  1812 _potential[_digraph.source(arc)]; 1813 1813 } 1814 1814 … … 1823 1823 /// \relates PotentialDifferenceMap 1824 1824 template <typename Digraph, typename NodeMap> 1825 PotentialDifferenceMap<Digraph, NodeMap> 1825 PotentialDifferenceMap<Digraph, NodeMap> 1826 1826 potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) { 1827 1827 return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential); … … 1846 1846 1847 1847 template <typename _Digraph> 1848 class InDegMap 1848 class InDegMap 1849 1849 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc> 1850 1850 ::ItemNotifier::ObserverBase { 1851 1851 1852 1852 public: 1853 1853 1854 1854 typedef _Digraph Digraph; 1855 1855 typedef int Value; … … 1867 1867 1868 1868 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} 1869 1869 1870 1870 virtual void add(const Key& key) { 1871 1872 1871 Parent::add(key); 1872 Parent::set(key, 0); 1873 1873 } 1874 1874 1875 1875 virtual void add(const std::vector<Key>& keys) { 1876 1877 1878 1879 1876 Parent::add(keys); 1877 for (int i = 0; i < int(keys.size()); ++i) { 1878 Parent::set(keys[i], 0); 1879 } 1880 1880 } 1881 1881 1882 1882 virtual void build() { 1883 1884 1885 1886 1887 1888 1883 Parent::build(); 1884 Key it; 1885 typename Parent::Notifier* nf = Parent::notifier(); 1886 for (nf>first(it); it != INVALID; nf>next(it)) { 1887 Parent::set(it, 0); 1888 } 1889 1889 } 1890 1890 }; … … 1895 1895 /// 1896 1896 /// Constructor for creating indegree map. 1897 explicit InDegMap(const Digraph& digraph) 1897 explicit InDegMap(const Digraph& digraph) 1898 1898 : _digraph(digraph), _deg(digraph) { 1899 1899 Parent::attach(_digraph.notifier(typename Digraph::Arc())); 1900 1900 1901 1901 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 1902 1903 } 1904 } 1905 1902 _deg[it] = countInArcs(_digraph, it); 1903 } 1904 } 1905 1906 1906 /// Gives back the indegree of a Node. 1907 1907 int operator[](const Key& key) const { … … 1910 1910 1911 1911 protected: 1912 1912 1913 1913 typedef typename Digraph::Arc Arc; 1914 1914 … … 1935 1935 virtual void build() { 1936 1936 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 1937 1938 } 1937 _deg[it] = countInArcs(_digraph, it); 1938 } 1939 1939 } 1940 1940 1941 1941 virtual void clear() { 1942 1942 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 1943 1943 _deg[it] = 0; 1944 1944 } 1945 1945 } 1946 1946 private: 1947 1947 1948 1948 const Digraph& _digraph; 1949 1949 AutoNodeMap _deg; … … 1968 1968 1969 1969 template <typename _Digraph> 1970 class OutDegMap 1970 class OutDegMap 1971 1971 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc> 1972 1972 ::ItemNotifier::ObserverBase { 1973 1973 1974 1974 public: 1975 1975 1976 1976 typedef _Digraph Digraph; 1977 1977 typedef int Value; … … 1989 1989 1990 1990 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} 1991 1991 1992 1992 virtual void add(const Key& key) { 1993 1994 1993 Parent::add(key); 1994 Parent::set(key, 0); 1995 1995 } 1996 1996 virtual void add(const std::vector<Key>& keys) { 1997 1998 1999 2000 1997 Parent::add(keys); 1998 for (int i = 0; i < int(keys.size()); ++i) { 1999 Parent::set(keys[i], 0); 2000 } 2001 2001 } 2002 2002 virtual void build() { 2003 2004 2005 2006 2007 2008 2003 Parent::build(); 2004 Key it; 2005 typename Parent::Notifier* nf = Parent::notifier(); 2006 for (nf>first(it); it != INVALID; nf>next(it)) { 2007 Parent::set(it, 0); 2008 } 2009 2009 } 2010 2010 }; … … 2015 2015 /// 2016 2016 /// Constructor for creating outdegree map. 2017 explicit OutDegMap(const Digraph& digraph) 2017 explicit OutDegMap(const Digraph& digraph) 2018 2018 : _digraph(digraph), _deg(digraph) { 2019 2019 Parent::attach(_digraph.notifier(typename Digraph::Arc())); 2020 2020 2021 2021 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2022 2022 _deg[it] = countOutArcs(_digraph, it); 2023 2023 } 2024 2024 } … … 2030 2030 2031 2031 protected: 2032 2032 2033 2033 typedef typename Digraph::Arc Arc; 2034 2034 … … 2055 2055 virtual void build() { 2056 2056 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2057 2058 } 2057 _deg[it] = countOutArcs(_digraph, it); 2058 } 2059 2059 } 2060 2060 2061 2061 virtual void clear() { 2062 2062 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2063 2063 _deg[it] = 0; 2064 2064 } 2065 2065 } 2066 2066 private: 2067 2067 2068 2068 const Digraph& _digraph; 2069 2069 AutoNodeMap _deg; … … 2072 2072 2073 2073 ///Dynamic arc look up between given endpoints. 2074 2074 2075 2075 ///\ingroup gutils 2076 2076 ///Using this class, you can find an arc in a digraph from a given … … 2090 2090 ///queries. 2091 2091 /// 2092 ///\tparam G The type of the underlying digraph. 2093 /// 2094 ///\sa ArcLookUp 2095 ///\sa AllArcLookUp 2092 ///\tparam G The type of the underlying digraph. 2093 /// 2094 ///\sa ArcLookUp 2095 ///\sa AllArcLookUp 2096 2096 template<class G> 2097 class DynArcLookUp 2097 class DynArcLookUp 2098 2098 : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase 2099 2099 { … … 2113 2113 2114 2114 AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {} 2115 2115 2116 2116 virtual void add(const Node& node) { 2117 2118 2117 Parent::add(node); 2118 Parent::set(node, INVALID); 2119 2119 } 2120 2120 2121 2121 virtual void add(const std::vector<Node>& nodes) { 2122 2123 2124 2125 2122 Parent::add(nodes); 2123 for (int i = 0; i < int(nodes.size()); ++i) { 2124 Parent::set(nodes[i], INVALID); 2125 } 2126 2126 } 2127 2127 2128 2128 virtual void build() { 2129 2130 2131 2132 2133 2134 2129 Parent::build(); 2130 Node it; 2131 typename Parent::Notifier* nf = Parent::notifier(); 2132 for (nf>first(it); it != INVALID; nf>next(it)) { 2133 Parent::set(it, INVALID); 2134 } 2135 2135 } 2136 2136 }; … … 2141 2141 typename Digraph::template ArcMap<Arc> _left; 2142 2142 typename Digraph::template ArcMap<Arc> _right; 2143 2143 2144 2144 class ArcLess { 2145 2145 const Digraph &g; 2146 2146 public: 2147 2147 ArcLess(const Digraph &_g) : g(_g) {} 2148 bool operator()(Arc a,Arc b) const 2148 bool operator()(Arc a,Arc b) const 2149 2149 { 2150 2151 } 2152 }; 2153 2150 return g.target(a)<g.target(b); 2151 } 2152 }; 2153 2154 2154 public: 2155 2155 2156 2156 ///Constructor 2157 2157 … … 2159 2159 /// 2160 2160 ///It builds up the search database. 2161 DynArcLookUp(const Digraph &g) 2162 : _g(g),_head(g),_parent(g),_left(g),_right(g) 2163 { 2161 DynArcLookUp(const Digraph &g) 2162 : _g(g),_head(g),_parent(g),_left(g),_right(g) 2163 { 2164 2164 Parent::attach(_g.notifier(typename Digraph::Arc())); 2165 refresh(); 2166 } 2167 2165 refresh(); 2166 } 2167 2168 2168 protected: 2169 2169 … … 2174 2174 virtual void add(const std::vector<Arc>& arcs) { 2175 2175 for (int i = 0; i < int(arcs.size()); ++i) { 2176 2176 insert(arcs[i]); 2177 2177 } 2178 2178 } … … 2184 2184 virtual void erase(const std::vector<Arc>& arcs) { 2185 2185 for (int i = 0; i < int(arcs.size()); ++i) { 2186 2187 } 2186 remove(arcs[i]); 2187 } 2188 2188 } 2189 2189 … … 2194 2194 virtual void clear() { 2195 2195 for(NodeIt n(_g);n!=INVALID;++n) { 2196 2196 _head.set(n, INVALID); 2197 2197 } 2198 2198 } … … 2203 2203 _left.set(arc, INVALID); 2204 2204 _right.set(arc, INVALID); 2205 2205 2206 2206 Arc e = _head[s]; 2207 2207 if (e == INVALID) { 2208 2209 2210 2208 _head.set(s, arc); 2209 _parent.set(arc, INVALID); 2210 return; 2211 2211 } 2212 2212 while (true) { 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2213 if (t < _g.target(e)) { 2214 if (_left[e] == INVALID) { 2215 _left.set(e, arc); 2216 _parent.set(arc, e); 2217 splay(arc); 2218 return; 2219 } else { 2220 e = _left[e]; 2221 } 2222 } else { 2223 if (_right[e] == INVALID) { 2224 _right.set(e, arc); 2225 _parent.set(arc, e); 2226 splay(arc); 2227 return; 2228 } else { 2229 e = _right[e]; 2230 } 2231 } 2232 2232 } 2233 2233 } … … 2235 2235 void remove(Arc arc) { 2236 2236 if (_left[arc] == INVALID) { 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2237 if (_right[arc] != INVALID) { 2238 _parent.set(_right[arc], _parent[arc]); 2239 } 2240 if (_parent[arc] != INVALID) { 2241 if (_left[_parent[arc]] == arc) { 2242 _left.set(_parent[arc], _right[arc]); 2243 } else { 2244 _right.set(_parent[arc], _right[arc]); 2245 } 2246 } else { 2247 _head.set(_g.source(arc), _right[arc]); 2248 } 2249 2249 } else if (_right[arc] == INVALID) { 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2250 _parent.set(_left[arc], _parent[arc]); 2251 if (_parent[arc] != INVALID) { 2252 if (_left[_parent[arc]] == arc) { 2253 _left.set(_parent[arc], _left[arc]); 2254 } else { 2255 _right.set(_parent[arc], _left[arc]); 2256 } 2257 } else { 2258 _head.set(_g.source(arc), _left[arc]); 2259 } 2260 2260 } else { 2261 2262 2263 e = _right[e]; 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 } 2302 } 2303 2304 Arc refreshRec(std::vector<Arc> &v,int a,int b) 2261 Arc e = _left[arc]; 2262 if (_right[e] != INVALID) { 2263 e = _right[e]; 2264 while (_right[e] != INVALID) { 2265 e = _right[e]; 2266 } 2267 Arc s = _parent[e]; 2268 _right.set(_parent[e], _left[e]); 2269 if (_left[e] != INVALID) { 2270 _parent.set(_left[e], _parent[e]); 2271 } 2272 2273 _left.set(e, _left[arc]); 2274 _parent.set(_left[arc], e); 2275 _right.set(e, _right[arc]); 2276 _parent.set(_right[arc], e); 2277 2278 _parent.set(e, _parent[arc]); 2279 if (_parent[arc] != INVALID) { 2280 if (_left[_parent[arc]] == arc) { 2281 _left.set(_parent[arc], e); 2282 } else { 2283 _right.set(_parent[arc], e); 2284 } 2285 } 2286 splay(s); 2287 } else { 2288 _right.set(e, _right[arc]); 2289 _parent.set(_right[arc], e); 2290 2291 if (_parent[arc] != INVALID) { 2292 if (_left[_parent[arc]] == arc) { 2293 _left.set(_parent[arc], e); 2294 } else { 2295 _right.set(_parent[arc], e); 2296 } 2297 } else { 2298 _head.set(_g.source(arc), e); 2299 } 2300 } 2301 } 2302 } 2303 2304 Arc refreshRec(std::vector<Arc> &v,int a,int b) 2305 2305 { 2306 2306 int m=(a+b)/2; 2307 2307 Arc me=v[m]; 2308 2308 if (a < m) { 2309 2310 2311 2309 Arc left = refreshRec(v,a,m1); 2310 _left.set(me, left); 2311 _parent.set(left, me); 2312 2312 } else { 2313 2313 _left.set(me, INVALID); 2314 2314 } 2315 2315 if (m < b) { 2316 2317 2318 2316 Arc right = refreshRec(v,m+1,b); 2317 _right.set(me, right); 2318 _parent.set(right, me); 2319 2319 } else { 2320 2320 _right.set(me, INVALID); 2321 2321 } 2322 2322 return me; … … 2325 2325 void refresh() { 2326 2326 for(NodeIt n(_g);n!=INVALID;++n) { 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 } 2337 } 2338 2339 void zig(Arc v) { 2327 std::vector<Arc> v; 2328 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e); 2329 if(v.size()) { 2330 std::sort(v.begin(),v.end(),ArcLess(_g)); 2331 Arc head = refreshRec(v,0,v.size()1); 2332 _head.set(n, head); 2333 _parent.set(head, INVALID); 2334 } 2335 else _head.set(n, INVALID); 2336 } 2337 } 2338 2339 void zig(Arc v) { 2340 2340 Arc w = _parent[v]; 2341 2341 _parent.set(v, _parent[w]); … … 2344 2344 _right.set(v, w); 2345 2345 if (_parent[v] != INVALID) { 2346 2347 2348 2349 2350 2346 if (_right[_parent[v]] == w) { 2347 _right.set(_parent[v], v); 2348 } else { 2349 _left.set(_parent[v], v); 2350 } 2351 2351 } 2352 2352 if (_left[w] != INVALID){ 2353 2354 } 2355 } 2356 2357 void zag(Arc v) { 2353 _parent.set(_left[w], w); 2354 } 2355 } 2356 2357 void zag(Arc v) { 2358 2358 Arc w = _parent[v]; 2359 2359 _parent.set(v, _parent[w]); … … 2362 2362 _left.set(v, w); 2363 2363 if (_parent[v] != INVALID){ 2364 2365 2366 2367 2368 2364 if (_left[_parent[v]] == w) { 2365 _left.set(_parent[v], v); 2366 } else { 2367 _right.set(_parent[v], v); 2368 } 2369 2369 } 2370 2370 if (_right[w] != INVALID){ 2371 2371 _parent.set(_right[w], w); 2372 2372 } 2373 2373 } … … 2375 2375 void splay(Arc v) { 2376 2376 while (_parent[v] != INVALID) { 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2377 if (v == _left[_parent[v]]) { 2378 if (_parent[_parent[v]] == INVALID) { 2379 zig(v); 2380 } else { 2381 if (_parent[v] == _left[_parent[_parent[v]]]) { 2382 zig(_parent[v]); 2383 zig(v); 2384 } else { 2385 zig(v); 2386 zag(v); 2387 } 2388 } 2389 } else { 2390 if (_parent[_parent[v]] == INVALID) { 2391 zag(v); 2392 } else { 2393 if (_parent[v] == _left[_parent[_parent[v]]]) { 2394 zag(v); 2395 zig(v); 2396 } else { 2397 zag(_parent[v]); 2398 zag(v); 2399 } 2400 } 2401 } 2402 2402 } 2403 2403 _head[_g.source(v)] = v; … … 2406 2406 2407 2407 public: 2408 2408 2409 2409 ///Find an arc between two nodes. 2410 2410 2411 2411 ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where 2412 2412 /// <em>d</em> is the number of outgoing arcs of \c s. … … 2419 2419 Arc a = _head[s]; 2420 2420 while (true) { 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2421 if (_g.target(a) == t) { 2422 const_cast<DynArcLookUp&>(*this).splay(a); 2423 return a; 2424 } else if (t < _g.target(a)) { 2425 if (_left[a] == INVALID) { 2426 const_cast<DynArcLookUp&>(*this).splay(a); 2427 return INVALID; 2428 } else { 2429 a = _left[a]; 2430 } 2431 } else { 2432 if (_right[a] == INVALID) { 2433 const_cast<DynArcLookUp&>(*this).splay(a); 2434 return INVALID; 2435 } else { 2436 a = _right[a]; 2437 } 2438 } 2439 2439 } 2440 2440 } 2441 2441 2442 2442 ///Find the first arc between two nodes. 2443 2443 2444 2444 ///Find the first arc between two nodes in time 2445 2445 /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of 2446 /// outgoing arcs of \c s. 2447 ///\param s The source node 2446 /// outgoing arcs of \c s. 2447 ///\param s The source node 2448 2448 ///\param t The target node 2449 2449 ///\return An arc from \c s to \c t if there exists, \ref INVALID … … 2454 2454 Arc r = INVALID; 2455 2455 while (true) { 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2456 if (_g.target(a) < t) { 2457 if (_right[a] == INVALID) { 2458 const_cast<DynArcLookUp&>(*this).splay(a); 2459 return r; 2460 } else { 2461 a = _right[a]; 2462 } 2463 } else { 2464 if (_g.target(a) == t) { 2465 r = a; 2466 } 2467 if (_left[a] == INVALID) { 2468 const_cast<DynArcLookUp&>(*this).splay(a); 2469 return r; 2470 } else { 2471 a = _left[a]; 2472 } 2473 } 2474 2474 } 2475 2475 } 2476 2476 2477 2477 ///Find the next arc between two nodes. 2478 2478 2479 2479 ///Find the next arc between two nodes in time 2480 2480 /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of 2481 /// outgoing arcs of \c s. 2482 ///\param s The source node 2481 /// outgoing arcs of \c s. 2482 ///\param s The source node 2483 2483 ///\param t The target node 2484 2484 ///\return An arc from \c s to \c t if there exists, \ref INVALID … … 2494 2494 { 2495 2495 if (_right[a] != INVALID) { 2496 2497 2498 2499 2500 2496 a = _right[a]; 2497 while (_left[a] != INVALID) { 2498 a = _left[a]; 2499 } 2500 const_cast<DynArcLookUp&>(*this).splay(a); 2501 2501 } else { 2502 2503 2504 2505 2506 2507 2508 2509 2510 2502 while (_parent[a] != INVALID && _right[_parent[a]] == a) { 2503 a = _parent[a]; 2504 } 2505 if (_parent[a] == INVALID) { 2506 return INVALID; 2507 } else { 2508 a = _parent[a]; 2509 const_cast<DynArcLookUp&>(*this).splay(a); 2510 } 2511 2511 } 2512 2512 if (_g.target(a) == t) return a; 2513 else return INVALID; 2513 else return INVALID; 2514 2514 } 2515 2515 … … 2517 2517 2518 2518 ///Fast arc look up between given endpoints. 2519 2519 2520 2520 ///\ingroup gutils 2521 2521 ///Using this class, you can find an arc in a digraph from a given … … 2534 2534 /// 2535 2535 ///\sa DynArcLookUp 2536 ///\sa AllArcLookUp 2536 ///\sa AllArcLookUp 2537 2537 template<class G> 2538 class ArcLookUp 2538 class ArcLookUp 2539 2539 { 2540 2540 public: … … 2547 2547 typename Digraph::template ArcMap<Arc> _left; 2548 2548 typename Digraph::template ArcMap<Arc> _right; 2549 2549 2550 2550 class ArcLess { 2551 2551 const Digraph &g; 2552 2552 public: 2553 2553 ArcLess(const Digraph &_g) : g(_g) {} 2554 bool operator()(Arc a,Arc b) const 2554 bool operator()(Arc a,Arc b) const 2555 2555 { 2556 2557 } 2558 }; 2559 2556 return g.target(a)<g.target(b); 2557 } 2558 }; 2559 2560 2560 public: 2561 2561 2562 2562 ///Constructor 2563 2563 … … 2567 2567 ///changes. 2568 2568 ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();} 2569 2569 2570 2570 private: 2571 Arc refreshRec(std::vector<Arc> &v,int a,int b) 2571 Arc refreshRec(std::vector<Arc> &v,int a,int b) 2572 2572 { 2573 2573 int m=(a+b)/2; … … 2584 2584 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is 2585 2585 ///the number of the outgoing arcs of \c n. 2586 void refresh(Node n) 2586 void refresh(Node n) 2587 2587 { 2588 2588 std::vector<Arc> v; 2589 2589 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e); 2590 2590 if(v.size()) { 2591 2592 2591 std::sort(v.begin(),v.end(),ArcLess(_g)); 2592 _head[n]=refreshRec(v,0,v.size()1); 2593 2593 } 2594 2594 else _head[n]=INVALID; … … 2603 2603 ///outdegree of the digraph. 2604 2604 2605 void refresh() 2605 void refresh() 2606 2606 { 2607 2607 for(NodeIt n(_g);n!=INVALID;++n) refresh(n); 2608 2608 } 2609 2609 2610 2610 ///Find an arc between two nodes. 2611 2611 2612 2612 ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where 2613 2613 /// <em>d</em> is the number of outgoing arcs of \c s. … … 2626 2626 Arc e; 2627 2627 for(e=_head[s]; 2628 2629 2628 e!=INVALID&&_g.target(e)!=t; 2629 e = t < _g.target(e)?_left[e]:_right[e]) ; 2630 2630 return e; 2631 2631 } … … 2634 2634 2635 2635 ///Fast look up of all arcs between given endpoints. 2636 2636 2637 2637 ///\ingroup gutils 2638 2638 ///This class is the same as \ref ArcLookUp, with the addition … … 2647 2647 /// 2648 2648 ///\sa DynArcLookUp 2649 ///\sa ArcLookUp 2649 ///\sa ArcLookUp 2650 2650 template<class G> 2651 2651 class AllArcLookUp : public ArcLookUp<G> … … 2658 2658 TEMPLATE_DIGRAPH_TYPEDEFS(G); 2659 2659 typedef G Digraph; 2660 2660 2661 2661 typename Digraph::template ArcMap<Arc> _next; 2662 2662 2663 2663 Arc refreshNext(Arc head,Arc next=INVALID) 2664 2664 { 2665 2665 if(head==INVALID) return next; 2666 2666 else { 2667 2668 // 2669 2670 2671 2672 } 2673 } 2674 2667 next=refreshNext(_right[head],next); 2668 // _next[head]=next; 2669 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head)) 2670 ? next : INVALID; 2671 return refreshNext(_left[head],head); 2672 } 2673 } 2674 2675 2675 void refreshNext() 2676 2676 { 2677 2677 for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]); 2678 2678 } 2679 2679 2680 2680 public: 2681 2681 ///Constructor … … 2693 2693 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is 2694 2694 ///the number of the outgoing arcs of \c n. 2695 2696 void refresh(Node n) 2695 2696 void refresh(Node n) 2697 2697 { 2698 2698 ArcLookUp<G>::refresh(n); 2699 2699 refreshNext(_head[n]); 2700 2700 } 2701 2701 2702 2702 ///Refresh the full data structure. 2703 2703 … … 2709 2709 ///outdegree of the digraph. 2710 2710 2711 void refresh() 2711 void refresh() 2712 2712 { 2713 2713 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]); 2714 2714 } 2715 2715 2716 2716 ///Find an arc between two nodes. 2717 2717 2718 2718 ///Find an arc between two nodes. 2719 2719 ///\param s The source node … … 2751 2751 } 2752 2752 #endif 2753 2753 2754 2754 }; 2755 2755
Note: See TracChangeset
for help on using the changeset viewer.