1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 * 5 * Copyright (C) 2003-2013 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). 8 * 9 * Permission to use, modify and distribute this software is granted 10 * provided that this copyright notice appears in all copies. For 11 * precise terms see the accompanying LICENSE file. 12 * 13 * This software is provided "AS IS" with no warranty of any kind, 14 * express or implied, and with no claim as to its suitability for any 15 * purpose. 16 * 17 */ 18 19 #ifndef LEMON_CORE_H 20 #define LEMON_CORE_H 21 22 #include <vector> 23 #include <algorithm> 24 25 #include <lemon/config.h> 26 #include <lemon/bits/enable_if.h> 27 #include <lemon/bits/traits.h> 28 #include <lemon/assert.h> 29 30 // Disable the following warnings when compiling with MSVC: 31 // C4250: 'class1' : inherits 'class2::member' via dominance 32 // C4355: 'this' : used in base member initializer list 33 // C4503: 'function' : decorated name length exceeded, name was truncated 34 // C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning) 35 // C4996: 'function': was declared deprecated 36 #ifdef _MSC_VER 37 #pragma warning( disable : 4250 4355 4503 4800 4996 ) 38 #endif 39 40 #ifdef __GNUC__ 41 #define GCC_VERSION (__GNUC__ * 10000 \ 42 + __GNUC_MINOR__ * 100 \ 43 + __GNUC_PATCHLEVEL__) 44 #endif 45 46 #if GCC_VERSION >= 40800 47 // Needed by the [DI]GRAPH_TYPEDEFS marcos for gcc 4.8 48 #pragma GCC diagnostic ignored "-Wunused-local-typedefs" 49 #endif 50 51 ///\file 52 ///\brief LEMON core utilities. 53 /// 54 ///This header file contains core utilities for LEMON. 55 ///It is automatically included by all graph types, therefore it usually 56 ///do not have to be included directly. 57 58 namespace lemon { 59 60 /// \brief Dummy type to make it easier to create invalid iterators. 61 /// 62 /// Dummy type to make it easier to create invalid iterators. 63 /// See \ref INVALID for the usage. 64 struct Invalid { 65 public: 66 bool operator==(Invalid) { return true; } 67 bool operator!=(Invalid) { return false; } 68 bool operator< (Invalid) { return false; } 69 }; 70 71 /// \brief Invalid iterators. 72 /// 73 /// \ref Invalid is a global type that converts to each iterator 74 /// in such a way that the value of the target iterator will be invalid. 75 #ifdef LEMON_ONLY_TEMPLATES 76 const Invalid INVALID = Invalid(); 77 #else 78 extern const Invalid INVALID; 79 #endif 80 81 /// \addtogroup gutils 82 /// @{ 83 84 ///Create convenience typedefs for the digraph types and iterators 85 86 ///This \c \#define creates convenient type definitions for the following 87 ///types of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt, 88 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 89 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. 90 /// 91 ///\note If the graph type is a dependent type, ie. the graph type depend 92 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() 93 ///macro. 94 #define DIGRAPH_TYPEDEFS(Digraph) \ 95 typedef Digraph::Node Node; \ 96 typedef Digraph::NodeIt NodeIt; \ 97 typedef Digraph::Arc Arc; \ 98 typedef Digraph::ArcIt ArcIt; \ 99 typedef Digraph::InArcIt InArcIt; \ 100 typedef Digraph::OutArcIt OutArcIt; \ 101 typedef Digraph::NodeMap<bool> BoolNodeMap; \ 102 typedef Digraph::NodeMap<int> IntNodeMap; \ 103 typedef Digraph::NodeMap<double> DoubleNodeMap; \ 104 typedef Digraph::ArcMap<bool> BoolArcMap; \ 105 typedef Digraph::ArcMap<int> IntArcMap; \ 106 typedef Digraph::ArcMap<double> DoubleArcMap 107 108 ///Create convenience typedefs for the digraph types and iterators 109 110 ///\see DIGRAPH_TYPEDEFS 111 /// 112 ///\note Use this macro, if the graph type is a dependent type, 113 ///ie. the graph type depend on a template parameter. 114 #define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \ 115 typedef typename Digraph::Node Node; \ 116 typedef typename Digraph::NodeIt NodeIt; \ 117 typedef typename Digraph::Arc Arc; \ 118 typedef typename Digraph::ArcIt ArcIt; \ 119 typedef typename Digraph::InArcIt InArcIt; \ 120 typedef typename Digraph::OutArcIt OutArcIt; \ 121 typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \ 122 typedef typename Digraph::template NodeMap<int> IntNodeMap; \ 123 typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \ 124 typedef typename Digraph::template ArcMap<bool> BoolArcMap; \ 125 typedef typename Digraph::template ArcMap<int> IntArcMap; \ 126 typedef typename Digraph::template ArcMap<double> DoubleArcMap 127 128 ///Create convenience typedefs for the graph types and iterators 129 130 ///This \c \#define creates the same convenient type definitions as defined 131 ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates 132 ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap, 133 ///\c DoubleEdgeMap. 134 /// 135 ///\note If the graph type is a dependent type, ie. the graph type depend 136 ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS() 137 ///macro. 138 #define GRAPH_TYPEDEFS(Graph) \ 139 DIGRAPH_TYPEDEFS(Graph); \ 140 typedef Graph::Edge Edge; \ 141 typedef Graph::EdgeIt EdgeIt; \ 142 typedef Graph::IncEdgeIt IncEdgeIt; \ 143 typedef Graph::EdgeMap<bool> BoolEdgeMap; \ 144 typedef Graph::EdgeMap<int> IntEdgeMap; \ 145 typedef Graph::EdgeMap<double> DoubleEdgeMap 146 147 ///Create convenience typedefs for the graph types and iterators 148 149 ///\see GRAPH_TYPEDEFS 150 /// 151 ///\note Use this macro, if the graph type is a dependent type, 152 ///ie. the graph type depend on a template parameter. 153 #define TEMPLATE_GRAPH_TYPEDEFS(Graph) \ 154 TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \ 155 typedef typename Graph::Edge Edge; \ 156 typedef typename Graph::EdgeIt EdgeIt; \ 157 typedef typename Graph::IncEdgeIt IncEdgeIt; \ 158 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \ 159 typedef typename Graph::template EdgeMap<int> IntEdgeMap; \ 160 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap 161 162 ///Create convenience typedefs for the bipartite graph types and iterators 163 164 ///This \c \#define creates the same convenient type definitions as 165 ///defined by \ref GRAPH_TYPEDEFS(BpGraph) and ten more, namely it 166 ///creates \c RedNode, \c RedNodeIt, \c BoolRedNodeMap, 167 ///\c IntRedNodeMap, \c DoubleRedNodeMap, \c BlueNode, \c BlueNodeIt, 168 ///\c BoolBlueNodeMap, \c IntBlueNodeMap, \c DoubleBlueNodeMap. 169 /// 170 ///\note If the graph type is a dependent type, ie. the graph type depend 171 ///on a template parameter, then use \c TEMPLATE_BPGRAPH_TYPEDEFS() 172 ///macro. 173 #define BPGRAPH_TYPEDEFS(BpGraph) \ 174 GRAPH_TYPEDEFS(BpGraph); \ 175 typedef BpGraph::RedNode RedNode; \ 176 typedef BpGraph::RedNodeIt RedNodeIt; \ 177 typedef BpGraph::RedNodeMap<bool> BoolRedNodeMap; \ 178 typedef BpGraph::RedNodeMap<int> IntRedNodeMap; \ 179 typedef BpGraph::RedNodeMap<double> DoubleRedNodeMap; \ 180 typedef BpGraph::BlueNode BlueNode; \ 181 typedef BpGraph::BlueNodeIt BlueNodeIt; \ 182 typedef BpGraph::BlueNodeMap<bool> BoolBlueNodeMap; \ 183 typedef BpGraph::BlueNodeMap<int> IntBlueNodeMap; \ 184 typedef BpGraph::BlueNodeMap<double> DoubleBlueNodeMap 185 186 ///Create convenience typedefs for the bipartite graph types and iterators 187 188 ///\see BPGRAPH_TYPEDEFS 189 /// 190 ///\note Use this macro, if the graph type is a dependent type, 191 ///ie. the graph type depend on a template parameter. 192 #define TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph) \ 193 TEMPLATE_GRAPH_TYPEDEFS(BpGraph); \ 194 typedef typename BpGraph::RedNode RedNode; \ 195 typedef typename BpGraph::RedNodeIt RedNodeIt; \ 196 typedef typename BpGraph::template RedNodeMap<bool> BoolRedNodeMap; \ 197 typedef typename BpGraph::template RedNodeMap<int> IntRedNodeMap; \ 198 typedef typename BpGraph::template RedNodeMap<double> DoubleRedNodeMap; \ 199 typedef typename BpGraph::BlueNode BlueNode; \ 200 typedef typename BpGraph::BlueNodeIt BlueNodeIt; \ 201 typedef typename BpGraph::template BlueNodeMap<bool> BoolBlueNodeMap; \ 202 typedef typename BpGraph::template BlueNodeMap<int> IntBlueNodeMap; \ 203 typedef typename BpGraph::template BlueNodeMap<double> DoubleBlueNodeMap 204 205 /// \brief Function to count the items in a graph. 206 /// 207 /// This function counts the items (nodes, arcs etc.) in a graph. 208 /// The complexity of the function is linear because 209 /// it iterates on all of the items. 210 template <typename Graph, typename Item> countItems(const Graph & g)211 inline int countItems(const Graph& g) { 212 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; 213 int num = 0; 214 for (ItemIt it(g); it != INVALID; ++it) { 215 ++num; 216 } 217 return num; 218 } 219 220 // Node counting: 221 222 namespace _core_bits { 223 224 template <typename Graph, typename Enable = void> 225 struct CountNodesSelector { countCountNodesSelector226 static int count(const Graph &g) { 227 return countItems<Graph, typename Graph::Node>(g); 228 } 229 }; 230 231 template <typename Graph> 232 struct CountNodesSelector< 233 Graph, typename 234 enable_if<typename Graph::NodeNumTag, void>::type> 235 { 236 static int count(const Graph &g) { 237 return g.nodeNum(); 238 } 239 }; 240 } 241 242 /// \brief Function to count the nodes in the graph. 243 /// 244 /// This function counts the nodes in the graph. 245 /// The complexity of the function is <em>O</em>(<em>n</em>), but for some 246 /// graph structures it is specialized to run in <em>O</em>(1). 247 /// 248 /// \note If the graph contains a \c nodeNum() member function and a 249 /// \c NodeNumTag tag then this function calls directly the member 250 /// function to query the cardinality of the node set. 251 template <typename Graph> 252 inline int countNodes(const Graph& g) { 253 return _core_bits::CountNodesSelector<Graph>::count(g); 254 } 255 256 namespace _graph_utils_bits { 257 258 template <typename Graph, typename Enable = void> 259 struct CountRedNodesSelector { 260 static int count(const Graph &g) { 261 return countItems<Graph, typename Graph::RedNode>(g); 262 } 263 }; 264 265 template <typename Graph> 266 struct CountRedNodesSelector< 267 Graph, typename 268 enable_if<typename Graph::NodeNumTag, void>::type> 269 { 270 static int count(const Graph &g) { 271 return g.redNum(); 272 } 273 }; 274 } 275 276 /// \brief Function to count the red nodes in the graph. 277 /// 278 /// This function counts the red nodes in the graph. 279 /// The complexity of the function is O(n) but for some 280 /// graph structures it is specialized to run in O(1). 281 /// 282 /// If the graph contains a \e redNum() member function and a 283 /// \e NodeNumTag tag then this function calls directly the member 284 /// function to query the cardinality of the node set. 285 template <typename Graph> 286 inline int countRedNodes(const Graph& g) { 287 return _graph_utils_bits::CountRedNodesSelector<Graph>::count(g); 288 } 289 290 namespace _graph_utils_bits { 291 292 template <typename Graph, typename Enable = void> 293 struct CountBlueNodesSelector { 294 static int count(const Graph &g) { 295 return countItems<Graph, typename Graph::BlueNode>(g); 296 } 297 }; 298 299 template <typename Graph> 300 struct CountBlueNodesSelector< 301 Graph, typename 302 enable_if<typename Graph::NodeNumTag, void>::type> 303 { 304 static int count(const Graph &g) { 305 return g.blueNum(); 306 } 307 }; 308 } 309 310 /// \brief Function to count the blue nodes in the graph. 311 /// 312 /// This function counts the blue nodes in the graph. 313 /// The complexity of the function is O(n) but for some 314 /// graph structures it is specialized to run in O(1). 315 /// 316 /// If the graph contains a \e blueNum() member function and a 317 /// \e NodeNumTag tag then this function calls directly the member 318 /// function to query the cardinality of the node set. 319 template <typename Graph> 320 inline int countBlueNodes(const Graph& g) { 321 return _graph_utils_bits::CountBlueNodesSelector<Graph>::count(g); 322 } 323 324 // Arc counting: 325 326 namespace _core_bits { 327 328 template <typename Graph, typename Enable = void> 329 struct CountArcsSelector { 330 static int count(const Graph &g) { 331 return countItems<Graph, typename Graph::Arc>(g); 332 } 333 }; 334 335 template <typename Graph> 336 struct CountArcsSelector< 337 Graph, 338 typename enable_if<typename Graph::ArcNumTag, void>::type> 339 { 340 static int count(const Graph &g) { 341 return g.arcNum(); 342 } 343 }; 344 } 345 346 /// \brief Function to count the arcs in the graph. 347 /// 348 /// This function counts the arcs in the graph. 349 /// The complexity of the function is <em>O</em>(<em>m</em>), but for some 350 /// graph structures it is specialized to run in <em>O</em>(1). 351 /// 352 /// \note If the graph contains a \c arcNum() member function and a 353 /// \c ArcNumTag tag then this function calls directly the member 354 /// function to query the cardinality of the arc set. 355 template <typename Graph> 356 inline int countArcs(const Graph& g) { 357 return _core_bits::CountArcsSelector<Graph>::count(g); 358 } 359 360 // Edge counting: 361 362 namespace _core_bits { 363 364 template <typename Graph, typename Enable = void> 365 struct CountEdgesSelector { 366 static int count(const Graph &g) { 367 return countItems<Graph, typename Graph::Edge>(g); 368 } 369 }; 370 371 template <typename Graph> 372 struct CountEdgesSelector< 373 Graph, 374 typename enable_if<typename Graph::EdgeNumTag, void>::type> 375 { 376 static int count(const Graph &g) { 377 return g.edgeNum(); 378 } 379 }; 380 } 381 382 /// \brief Function to count the edges in the graph. 383 /// 384 /// This function counts the edges in the graph. 385 /// The complexity of the function is <em>O</em>(<em>m</em>), but for some 386 /// graph structures it is specialized to run in <em>O</em>(1). 387 /// 388 /// \note If the graph contains a \c edgeNum() member function and a 389 /// \c EdgeNumTag tag then this function calls directly the member 390 /// function to query the cardinality of the edge set. 391 template <typename Graph> 392 inline int countEdges(const Graph& g) { 393 return _core_bits::CountEdgesSelector<Graph>::count(g); 394 395 } 396 397 398 template <typename Graph, typename DegIt> 399 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { 400 int num = 0; 401 for (DegIt it(_g, _n); it != INVALID; ++it) { 402 ++num; 403 } 404 return num; 405 } 406 407 /// \brief Function to count the number of the out-arcs from node \c n. 408 /// 409 /// This function counts the number of the out-arcs from node \c n 410 /// in the graph \c g. 411 template <typename Graph> 412 inline int countOutArcs(const Graph& g, const typename Graph::Node& n) { 413 return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n); 414 } 415 416 /// \brief Function to count the number of the in-arcs to node \c n. 417 /// 418 /// This function counts the number of the in-arcs to node \c n 419 /// in the graph \c g. 420 template <typename Graph> 421 inline int countInArcs(const Graph& g, const typename Graph::Node& n) { 422 return countNodeDegree<Graph, typename Graph::InArcIt>(g, n); 423 } 424 425 /// \brief Function to count the number of the inc-edges to node \c n. 426 /// 427 /// This function counts the number of the inc-edges to node \c n 428 /// in the undirected graph \c g. 429 template <typename Graph> 430 inline int countIncEdges(const Graph& g, const typename Graph::Node& n) { 431 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n); 432 } 433 434 namespace _core_bits { 435 436 template <typename Digraph, typename Item, typename RefMap> 437 class MapCopyBase { 438 public: 439 virtual void copy(const Digraph& from, const RefMap& refMap) = 0; 440 441 virtual ~MapCopyBase() {} 442 }; 443 444 template <typename Digraph, typename Item, typename RefMap, 445 typename FromMap, typename ToMap> 446 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> { 447 public: 448 449 MapCopy(const FromMap& map, ToMap& tmap) 450 : _map(map), _tmap(tmap) {} 451 452 virtual void copy(const Digraph& digraph, const RefMap& refMap) { 453 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt; 454 for (ItemIt it(digraph); it != INVALID; ++it) { 455 _tmap.set(refMap[it], _map[it]); 456 } 457 } 458 459 private: 460 const FromMap& _map; 461 ToMap& _tmap; 462 }; 463 464 template <typename Digraph, typename Item, typename RefMap, typename It> 465 class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> { 466 public: 467 468 ItemCopy(const Item& item, It& it) : _item(item), _it(it) {} 469 470 virtual void copy(const Digraph&, const RefMap& refMap) { 471 _it = refMap[_item]; 472 } 473 474 private: 475 Item _item; 476 It& _it; 477 }; 478 479 template <typename Digraph, typename Item, typename RefMap, typename Ref> 480 class RefCopy : public MapCopyBase<Digraph, Item, RefMap> { 481 public: 482 483 RefCopy(Ref& map) : _map(map) {} 484 485 virtual void copy(const Digraph& digraph, const RefMap& refMap) { 486 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt; 487 for (ItemIt it(digraph); it != INVALID; ++it) { 488 _map.set(it, refMap[it]); 489 } 490 } 491 492 private: 493 Ref& _map; 494 }; 495 496 template <typename Digraph, typename Item, typename RefMap, 497 typename CrossRef> 498 class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> { 499 public: 500 501 CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {} 502 503 virtual void copy(const Digraph& digraph, const RefMap& refMap) { 504 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt; 505 for (ItemIt it(digraph); it != INVALID; ++it) { 506 _cmap.set(refMap[it], it); 507 } 508 } 509 510 private: 511 CrossRef& _cmap; 512 }; 513 514 template <typename Digraph, typename Enable = void> 515 struct DigraphCopySelector { 516 template <typename From, typename NodeRefMap, typename ArcRefMap> 517 static void copy(const From& from, Digraph &to, 518 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 519 to.clear(); 520 for (typename From::NodeIt it(from); it != INVALID; ++it) { 521 nodeRefMap[it] = to.addNode(); 522 } 523 for (typename From::ArcIt it(from); it != INVALID; ++it) { 524 arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)], 525 nodeRefMap[from.target(it)]); 526 } 527 } 528 }; 529 530 template <typename Digraph> 531 struct DigraphCopySelector< 532 Digraph, 533 typename enable_if<typename Digraph::BuildTag, void>::type> 534 { 535 template <typename From, typename NodeRefMap, typename ArcRefMap> 536 static void copy(const From& from, Digraph &to, 537 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 538 to.build(from, nodeRefMap, arcRefMap); 539 } 540 }; 541 542 template <typename Graph, typename Enable = void> 543 struct GraphCopySelector { 544 template <typename From, typename NodeRefMap, typename EdgeRefMap> 545 static void copy(const From& from, Graph &to, 546 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 547 to.clear(); 548 for (typename From::NodeIt it(from); it != INVALID; ++it) { 549 nodeRefMap[it] = to.addNode(); 550 } 551 for (typename From::EdgeIt it(from); it != INVALID; ++it) { 552 edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)], 553 nodeRefMap[from.v(it)]); 554 } 555 } 556 }; 557 558 template <typename Graph> 559 struct GraphCopySelector< 560 Graph, 561 typename enable_if<typename Graph::BuildTag, void>::type> 562 { 563 template <typename From, typename NodeRefMap, typename EdgeRefMap> 564 static void copy(const From& from, Graph &to, 565 NodeRefMap& nodeRefMap, 566 EdgeRefMap& edgeRefMap) { 567 to.build(from, nodeRefMap, edgeRefMap); 568 } 569 }; 570 571 template <typename BpGraph, typename Enable = void> 572 struct BpGraphCopySelector { 573 template <typename From, typename RedNodeRefMap, 574 typename BlueNodeRefMap, typename EdgeRefMap> 575 static void copy(const From& from, BpGraph &to, 576 RedNodeRefMap& redNodeRefMap, 577 BlueNodeRefMap& blueNodeRefMap, 578 EdgeRefMap& edgeRefMap) { 579 to.clear(); 580 for (typename From::RedNodeIt it(from); it != INVALID; ++it) { 581 redNodeRefMap[it] = to.addRedNode(); 582 } 583 for (typename From::BlueNodeIt it(from); it != INVALID; ++it) { 584 blueNodeRefMap[it] = to.addBlueNode(); 585 } 586 for (typename From::EdgeIt it(from); it != INVALID; ++it) { 587 edgeRefMap[it] = to.addEdge(redNodeRefMap[from.redNode(it)], 588 blueNodeRefMap[from.blueNode(it)]); 589 } 590 } 591 }; 592 593 template <typename BpGraph> 594 struct BpGraphCopySelector< 595 BpGraph, 596 typename enable_if<typename BpGraph::BuildTag, void>::type> 597 { 598 template <typename From, typename RedNodeRefMap, 599 typename BlueNodeRefMap, typename EdgeRefMap> 600 static void copy(const From& from, BpGraph &to, 601 RedNodeRefMap& redNodeRefMap, 602 BlueNodeRefMap& blueNodeRefMap, 603 EdgeRefMap& edgeRefMap) { 604 to.build(from, redNodeRefMap, blueNodeRefMap, edgeRefMap); 605 } 606 }; 607 608 } 609 610 /// \brief Check whether a graph is undirected. 611 /// 612 /// This function returns \c true if the given graph is undirected. 613 #ifdef DOXYGEN 614 template <typename GR> 615 bool undirected(const GR& g) { return false; } 616 #else 617 template <typename GR> 618 typename enable_if<UndirectedTagIndicator<GR>, bool>::type 619 undirected(const GR&) { 620 return true; 621 } 622 template <typename GR> 623 typename disable_if<UndirectedTagIndicator<GR>, bool>::type 624 undirected(const GR&) { 625 return false; 626 } 627 #endif 628 629 /// \brief Class to copy a digraph. 630 /// 631 /// Class to copy a digraph to another digraph (duplicate a digraph). The 632 /// simplest way of using it is through the \c digraphCopy() function. 633 /// 634 /// This class not only make a copy of a digraph, but it can create 635 /// references and cross references between the nodes and arcs of 636 /// the two digraphs, and it can copy maps to use with the newly created 637 /// digraph. 638 /// 639 /// To make a copy from a digraph, first an instance of DigraphCopy 640 /// should be created, then the data belongs to the digraph should 641 /// assigned to copy. In the end, the \c run() member should be 642 /// called. 643 /// 644 /// The next code copies a digraph with several data: 645 ///\code 646 /// DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph); 647 /// // Create references for the nodes 648 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); 649 /// cg.nodeRef(nr); 650 /// // Create cross references (inverse) for the arcs 651 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph); 652 /// cg.arcCrossRef(acr); 653 /// // Copy an arc map 654 /// OrigGraph::ArcMap<double> oamap(orig_graph); 655 /// NewGraph::ArcMap<double> namap(new_graph); 656 /// cg.arcMap(oamap, namap); 657 /// // Copy a node 658 /// OrigGraph::Node on; 659 /// NewGraph::Node nn; 660 /// cg.node(on, nn); 661 /// // Execute copying 662 /// cg.run(); 663 ///\endcode 664 template <typename From, typename To> 665 class DigraphCopy { 666 private: 667 668 typedef typename From::Node Node; 669 typedef typename From::NodeIt NodeIt; 670 typedef typename From::Arc Arc; 671 typedef typename From::ArcIt ArcIt; 672 673 typedef typename To::Node TNode; 674 typedef typename To::Arc TArc; 675 676 typedef typename From::template NodeMap<TNode> NodeRefMap; 677 typedef typename From::template ArcMap<TArc> ArcRefMap; 678 679 public: 680 681 /// \brief Constructor of DigraphCopy. 682 /// 683 /// Constructor of DigraphCopy for copying the content of the 684 /// \c from digraph into the \c to digraph. 685 DigraphCopy(const From& from, To& to) 686 : _from(from), _to(to) {} 687 688 /// \brief Destructor of DigraphCopy 689 /// 690 /// Destructor of DigraphCopy. 691 ~DigraphCopy() { 692 for (int i = 0; i < int(_node_maps.size()); ++i) { 693 delete _node_maps[i]; 694 } 695 for (int i = 0; i < int(_arc_maps.size()); ++i) { 696 delete _arc_maps[i]; 697 } 698 699 } 700 701 /// \brief Copy the node references into the given map. 702 /// 703 /// This function copies the node references into the given map. 704 /// The parameter should be a map, whose key type is the Node type of 705 /// the source digraph, while the value type is the Node type of the 706 /// destination digraph. 707 template <typename NodeRef> 708 DigraphCopy& nodeRef(NodeRef& map) { 709 _node_maps.push_back(new _core_bits::RefCopy<From, Node, 710 NodeRefMap, NodeRef>(map)); 711 return *this; 712 } 713 714 /// \brief Copy the node cross references into the given map. 715 /// 716 /// This function copies the node cross references (reverse references) 717 /// into the given map. The parameter should be a map, whose key type 718 /// is the Node type of the destination digraph, while the value type is 719 /// the Node type of the source digraph. 720 template <typename NodeCrossRef> 721 DigraphCopy& nodeCrossRef(NodeCrossRef& map) { 722 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node, 723 NodeRefMap, NodeCrossRef>(map)); 724 return *this; 725 } 726 727 /// \brief Make a copy of the given node map. 728 /// 729 /// This function makes a copy of the given node map for the newly 730 /// created digraph. 731 /// The key type of the new map \c tmap should be the Node type of the 732 /// destination digraph, and the key type of the original map \c map 733 /// should be the Node type of the source digraph. 734 template <typename FromMap, typename ToMap> 735 DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { 736 _node_maps.push_back(new _core_bits::MapCopy<From, Node, 737 NodeRefMap, FromMap, ToMap>(map, tmap)); 738 return *this; 739 } 740 741 /// \brief Make a copy of the given node. 742 /// 743 /// This function makes a copy of the given node. 744 DigraphCopy& node(const Node& node, TNode& tnode) { 745 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, 746 NodeRefMap, TNode>(node, tnode)); 747 return *this; 748 } 749 750 /// \brief Copy the arc references into the given map. 751 /// 752 /// This function copies the arc references into the given map. 753 /// The parameter should be a map, whose key type is the Arc type of 754 /// the source digraph, while the value type is the Arc type of the 755 /// destination digraph. 756 template <typename ArcRef> 757 DigraphCopy& arcRef(ArcRef& map) { 758 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc, 759 ArcRefMap, ArcRef>(map)); 760 return *this; 761 } 762 763 /// \brief Copy the arc cross references into the given map. 764 /// 765 /// This function copies the arc cross references (reverse references) 766 /// into the given map. The parameter should be a map, whose key type 767 /// is the Arc type of the destination digraph, while the value type is 768 /// the Arc type of the source digraph. 769 template <typename ArcCrossRef> 770 DigraphCopy& arcCrossRef(ArcCrossRef& map) { 771 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc, 772 ArcRefMap, ArcCrossRef>(map)); 773 return *this; 774 } 775 776 /// \brief Make a copy of the given arc map. 777 /// 778 /// This function makes a copy of the given arc map for the newly 779 /// created digraph. 780 /// The key type of the new map \c tmap should be the Arc type of the 781 /// destination digraph, and the key type of the original map \c map 782 /// should be the Arc type of the source digraph. 783 template <typename FromMap, typename ToMap> 784 DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) { 785 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, 786 ArcRefMap, FromMap, ToMap>(map, tmap)); 787 return *this; 788 } 789 790 /// \brief Make a copy of the given arc. 791 /// 792 /// This function makes a copy of the given arc. 793 DigraphCopy& arc(const Arc& arc, TArc& tarc) { 794 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, 795 ArcRefMap, TArc>(arc, tarc)); 796 return *this; 797 } 798 799 /// \brief Execute copying. 800 /// 801 /// This function executes the copying of the digraph along with the 802 /// copying of the assigned data. 803 void run() { 804 NodeRefMap nodeRefMap(_from); 805 ArcRefMap arcRefMap(_from); 806 _core_bits::DigraphCopySelector<To>:: 807 copy(_from, _to, nodeRefMap, arcRefMap); 808 for (int i = 0; i < int(_node_maps.size()); ++i) { 809 _node_maps[i]->copy(_from, nodeRefMap); 810 } 811 for (int i = 0; i < int(_arc_maps.size()); ++i) { 812 _arc_maps[i]->copy(_from, arcRefMap); 813 } 814 } 815 816 protected: 817 818 const From& _from; 819 To& _to; 820 821 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > 822 _node_maps; 823 824 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > 825 _arc_maps; 826 827 }; 828 829 /// \brief Copy a digraph to another digraph. 830 /// 831 /// This function copies a digraph to another digraph. 832 /// The complete usage of it is detailed in the DigraphCopy class, but 833 /// a short example shows a basic work: 834 ///\code 835 /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run(); 836 ///\endcode 837 /// 838 /// After the copy the \c nr map will contain the mapping from the 839 /// nodes of the \c from digraph to the nodes of the \c to digraph and 840 /// \c acr will contain the mapping from the arcs of the \c to digraph 841 /// to the arcs of the \c from digraph. 842 /// 843 /// \see DigraphCopy 844 template <typename From, typename To> 845 DigraphCopy<From, To> digraphCopy(const From& from, To& to) { 846 return DigraphCopy<From, To>(from, to); 847 } 848 849 /// \brief Class to copy a graph. 850 /// 851 /// Class to copy a graph to another graph (duplicate a graph). The 852 /// simplest way of using it is through the \c graphCopy() function. 853 /// 854 /// This class not only make a copy of a graph, but it can create 855 /// references and cross references between the nodes, edges and arcs of 856 /// the two graphs, and it can copy maps for using with the newly created 857 /// graph. 858 /// 859 /// To make a copy from a graph, first an instance of GraphCopy 860 /// should be created, then the data belongs to the graph should 861 /// assigned to copy. In the end, the \c run() member should be 862 /// called. 863 /// 864 /// The next code copies a graph with several data: 865 ///\code 866 /// GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph); 867 /// // Create references for the nodes 868 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); 869 /// cg.nodeRef(nr); 870 /// // Create cross references (inverse) for the edges 871 /// NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph); 872 /// cg.edgeCrossRef(ecr); 873 /// // Copy an edge map 874 /// OrigGraph::EdgeMap<double> oemap(orig_graph); 875 /// NewGraph::EdgeMap<double> nemap(new_graph); 876 /// cg.edgeMap(oemap, nemap); 877 /// // Copy a node 878 /// OrigGraph::Node on; 879 /// NewGraph::Node nn; 880 /// cg.node(on, nn); 881 /// // Execute copying 882 /// cg.run(); 883 ///\endcode 884 template <typename From, typename To> 885 class GraphCopy { 886 private: 887 888 typedef typename From::Node Node; 889 typedef typename From::NodeIt NodeIt; 890 typedef typename From::Arc Arc; 891 typedef typename From::ArcIt ArcIt; 892 typedef typename From::Edge Edge; 893 typedef typename From::EdgeIt EdgeIt; 894 895 typedef typename To::Node TNode; 896 typedef typename To::Arc TArc; 897 typedef typename To::Edge TEdge; 898 899 typedef typename From::template NodeMap<TNode> NodeRefMap; 900 typedef typename From::template EdgeMap<TEdge> EdgeRefMap; 901 902 struct ArcRefMap { 903 ArcRefMap(const From& from, const To& to, 904 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) 905 : _from(from), _to(to), 906 _edge_ref(edge_ref), _node_ref(node_ref) {} 907 908 typedef typename From::Arc Key; 909 typedef typename To::Arc Value; 910 911 Value operator[](const Key& key) const { 912 bool forward = _from.u(key) != _from.v(key) ? 913 _node_ref[_from.source(key)] == 914 _to.source(_to.direct(_edge_ref[key], true)) : 915 _from.direction(key); 916 return _to.direct(_edge_ref[key], forward); 917 } 918 919 const From& _from; 920 const To& _to; 921 const EdgeRefMap& _edge_ref; 922 const NodeRefMap& _node_ref; 923 }; 924 925 public: 926 927 /// \brief Constructor of GraphCopy. 928 /// 929 /// Constructor of GraphCopy for copying the content of the 930 /// \c from graph into the \c to graph. 931 GraphCopy(const From& from, To& to) 932 : _from(from), _to(to) {} 933 934 /// \brief Destructor of GraphCopy 935 /// 936 /// Destructor of GraphCopy. 937 ~GraphCopy() { 938 for (int i = 0; i < int(_node_maps.size()); ++i) { 939 delete _node_maps[i]; 940 } 941 for (int i = 0; i < int(_arc_maps.size()); ++i) { 942 delete _arc_maps[i]; 943 } 944 for (int i = 0; i < int(_edge_maps.size()); ++i) { 945 delete _edge_maps[i]; 946 } 947 } 948 949 /// \brief Copy the node references into the given map. 950 /// 951 /// This function copies the node references into the given map. 952 /// The parameter should be a map, whose key type is the Node type of 953 /// the source graph, while the value type is the Node type of the 954 /// destination graph. 955 template <typename NodeRef> 956 GraphCopy& nodeRef(NodeRef& map) { 957 _node_maps.push_back(new _core_bits::RefCopy<From, Node, 958 NodeRefMap, NodeRef>(map)); 959 return *this; 960 } 961 962 /// \brief Copy the node cross references into the given map. 963 /// 964 /// This function copies the node cross references (reverse references) 965 /// into the given map. The parameter should be a map, whose key type 966 /// is the Node type of the destination graph, while the value type is 967 /// the Node type of the source graph. 968 template <typename NodeCrossRef> 969 GraphCopy& nodeCrossRef(NodeCrossRef& map) { 970 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node, 971 NodeRefMap, NodeCrossRef>(map)); 972 return *this; 973 } 974 975 /// \brief Make a copy of the given node map. 976 /// 977 /// This function makes a copy of the given node map for the newly 978 /// created graph. 979 /// The key type of the new map \c tmap should be the Node type of the 980 /// destination graph, and the key type of the original map \c map 981 /// should be the Node type of the source graph. 982 template <typename FromMap, typename ToMap> 983 GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { 984 _node_maps.push_back(new _core_bits::MapCopy<From, Node, 985 NodeRefMap, FromMap, ToMap>(map, tmap)); 986 return *this; 987 } 988 989 /// \brief Make a copy of the given node. 990 /// 991 /// This function makes a copy of the given node. 992 GraphCopy& node(const Node& node, TNode& tnode) { 993 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, 994 NodeRefMap, TNode>(node, tnode)); 995 return *this; 996 } 997 998 /// \brief Copy the arc references into the given map. 999 /// 1000 /// This function copies the arc references into the given map. 1001 /// The parameter should be a map, whose key type is the Arc type of 1002 /// the source graph, while the value type is the Arc type of the 1003 /// destination graph. 1004 template <typename ArcRef> 1005 GraphCopy& arcRef(ArcRef& map) { 1006 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc, 1007 ArcRefMap, ArcRef>(map)); 1008 return *this; 1009 } 1010 1011 /// \brief Copy the arc cross references into the given map. 1012 /// 1013 /// This function copies the arc cross references (reverse references) 1014 /// into the given map. The parameter should be a map, whose key type 1015 /// is the Arc type of the destination graph, while the value type is 1016 /// the Arc type of the source graph. 1017 template <typename ArcCrossRef> 1018 GraphCopy& arcCrossRef(ArcCrossRef& map) { 1019 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc, 1020 ArcRefMap, ArcCrossRef>(map)); 1021 return *this; 1022 } 1023 1024 /// \brief Make a copy of the given arc map. 1025 /// 1026 /// This function makes a copy of the given arc map for the newly 1027 /// created graph. 1028 /// The key type of the new map \c tmap should be the Arc type of the 1029 /// destination graph, and the key type of the original map \c map 1030 /// should be the Arc type of the source graph. 1031 template <typename FromMap, typename ToMap> 1032 GraphCopy& arcMap(const FromMap& map, ToMap& tmap) { 1033 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, 1034 ArcRefMap, FromMap, ToMap>(map, tmap)); 1035 return *this; 1036 } 1037 1038 /// \brief Make a copy of the given arc. 1039 /// 1040 /// This function makes a copy of the given arc. 1041 GraphCopy& arc(const Arc& arc, TArc& tarc) { 1042 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, 1043 ArcRefMap, TArc>(arc, tarc)); 1044 return *this; 1045 } 1046 1047 /// \brief Copy the edge references into the given map. 1048 /// 1049 /// This function copies the edge references into the given map. 1050 /// The parameter should be a map, whose key type is the Edge type of 1051 /// the source graph, while the value type is the Edge type of the 1052 /// destination graph. 1053 template <typename EdgeRef> 1054 GraphCopy& edgeRef(EdgeRef& map) { 1055 _edge_maps.push_back(new _core_bits::RefCopy<From, Edge, 1056 EdgeRefMap, EdgeRef>(map)); 1057 return *this; 1058 } 1059 1060 /// \brief Copy the edge cross references into the given map. 1061 /// 1062 /// This function copies the edge cross references (reverse references) 1063 /// into the given map. The parameter should be a map, whose key type 1064 /// is the Edge type of the destination graph, while the value type is 1065 /// the Edge type of the source graph. 1066 template <typename EdgeCrossRef> 1067 GraphCopy& edgeCrossRef(EdgeCrossRef& map) { 1068 _edge_maps.push_back(new _core_bits::CrossRefCopy<From, 1069 Edge, EdgeRefMap, EdgeCrossRef>(map)); 1070 return *this; 1071 } 1072 1073 /// \brief Make a copy of the given edge map. 1074 /// 1075 /// This function makes a copy of the given edge map for the newly 1076 /// created graph. 1077 /// The key type of the new map \c tmap should be the Edge type of the 1078 /// destination graph, and the key type of the original map \c map 1079 /// should be the Edge type of the source graph. 1080 template <typename FromMap, typename ToMap> 1081 GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) { 1082 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge, 1083 EdgeRefMap, FromMap, ToMap>(map, tmap)); 1084 return *this; 1085 } 1086 1087 /// \brief Make a copy of the given edge. 1088 /// 1089 /// This function makes a copy of the given edge. 1090 GraphCopy& edge(const Edge& edge, TEdge& tedge) { 1091 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge, 1092 EdgeRefMap, TEdge>(edge, tedge)); 1093 return *this; 1094 } 1095 1096 /// \brief Execute copying. 1097 /// 1098 /// This function executes the copying of the graph along with the 1099 /// copying of the assigned data. 1100 void run() { 1101 NodeRefMap nodeRefMap(_from); 1102 EdgeRefMap edgeRefMap(_from); 1103 ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap); 1104 _core_bits::GraphCopySelector<To>:: 1105 copy(_from, _to, nodeRefMap, edgeRefMap); 1106 for (int i = 0; i < int(_node_maps.size()); ++i) { 1107 _node_maps[i]->copy(_from, nodeRefMap); 1108 } 1109 for (int i = 0; i < int(_edge_maps.size()); ++i) { 1110 _edge_maps[i]->copy(_from, edgeRefMap); 1111 } 1112 for (int i = 0; i < int(_arc_maps.size()); ++i) { 1113 _arc_maps[i]->copy(_from, arcRefMap); 1114 } 1115 } 1116 1117 private: 1118 1119 const From& _from; 1120 To& _to; 1121 1122 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > 1123 _node_maps; 1124 1125 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > 1126 _arc_maps; 1127 1128 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 1129 _edge_maps; 1130 1131 }; 1132 1133 /// \brief Copy a graph to another graph. 1134 /// 1135 /// This function copies a graph to another graph. 1136 /// The complete usage of it is detailed in the GraphCopy class, 1137 /// but a short example shows a basic work: 1138 ///\code 1139 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run(); 1140 ///\endcode 1141 /// 1142 /// After the copy the \c nr map will contain the mapping from the 1143 /// nodes of the \c from graph to the nodes of the \c to graph and 1144 /// \c ecr will contain the mapping from the edges of the \c to graph 1145 /// to the edges of the \c from graph. 1146 /// 1147 /// \see GraphCopy 1148 template <typename From, typename To> 1149 GraphCopy<From, To> 1150 graphCopy(const From& from, To& to) { 1151 return GraphCopy<From, To>(from, to); 1152 } 1153 1154 /// \brief Class to copy a bipartite graph. 1155 /// 1156 /// Class to copy a bipartite graph to another graph (duplicate a 1157 /// graph). The simplest way of using it is through the 1158 /// \c bpGraphCopy() function. 1159 /// 1160 /// This class not only make a copy of a bipartite graph, but it can 1161 /// create references and cross references between the nodes, edges 1162 /// and arcs of the two graphs, and it can copy maps for using with 1163 /// the newly created graph. 1164 /// 1165 /// To make a copy from a graph, first an instance of BpGraphCopy 1166 /// should be created, then the data belongs to the graph should 1167 /// assigned to copy. In the end, the \c run() member should be 1168 /// called. 1169 /// 1170 /// The next code copies a graph with several data: 1171 ///\code 1172 /// BpGraphCopy<OrigBpGraph, NewBpGraph> cg(orig_graph, new_graph); 1173 /// // Create references for the nodes 1174 /// OrigBpGraph::NodeMap<NewBpGraph::Node> nr(orig_graph); 1175 /// cg.nodeRef(nr); 1176 /// // Create cross references (inverse) for the edges 1177 /// NewBpGraph::EdgeMap<OrigBpGraph::Edge> ecr(new_graph); 1178 /// cg.edgeCrossRef(ecr); 1179 /// // Copy a red node map 1180 /// OrigBpGraph::RedNodeMap<double> ormap(orig_graph); 1181 /// NewBpGraph::RedNodeMap<double> nrmap(new_graph); 1182 /// cg.redNodeMap(ormap, nrmap); 1183 /// // Copy a node 1184 /// OrigBpGraph::Node on; 1185 /// NewBpGraph::Node nn; 1186 /// cg.node(on, nn); 1187 /// // Execute copying 1188 /// cg.run(); 1189 ///\endcode 1190 template <typename From, typename To> 1191 class BpGraphCopy { 1192 private: 1193 1194 typedef typename From::Node Node; 1195 typedef typename From::RedNode RedNode; 1196 typedef typename From::BlueNode BlueNode; 1197 typedef typename From::NodeIt NodeIt; 1198 typedef typename From::Arc Arc; 1199 typedef typename From::ArcIt ArcIt; 1200 typedef typename From::Edge Edge; 1201 typedef typename From::EdgeIt EdgeIt; 1202 1203 typedef typename To::Node TNode; 1204 typedef typename To::RedNode TRedNode; 1205 typedef typename To::BlueNode TBlueNode; 1206 typedef typename To::Arc TArc; 1207 typedef typename To::Edge TEdge; 1208 1209 typedef typename From::template RedNodeMap<TRedNode> RedNodeRefMap; 1210 typedef typename From::template BlueNodeMap<TBlueNode> BlueNodeRefMap; 1211 typedef typename From::template EdgeMap<TEdge> EdgeRefMap; 1212 1213 struct NodeRefMap { 1214 NodeRefMap(const From& from, const RedNodeRefMap& red_node_ref, 1215 const BlueNodeRefMap& blue_node_ref) 1216 : _from(from), _red_node_ref(red_node_ref), 1217 _blue_node_ref(blue_node_ref) {} 1218 1219 typedef typename From::Node Key; 1220 typedef typename To::Node Value; 1221 1222 Value operator[](const Key& key) const { 1223 if (_from.red(key)) { 1224 return _red_node_ref[_from.asRedNodeUnsafe(key)]; 1225 } else { 1226 return _blue_node_ref[_from.asBlueNodeUnsafe(key)]; 1227 } 1228 } 1229 1230 const From& _from; 1231 const RedNodeRefMap& _red_node_ref; 1232 const BlueNodeRefMap& _blue_node_ref; 1233 }; 1234 1235 struct ArcRefMap { 1236 ArcRefMap(const From& from, const To& to, const EdgeRefMap& edge_ref) 1237 : _from(from), _to(to), _edge_ref(edge_ref) {} 1238 1239 typedef typename From::Arc Key; 1240 typedef typename To::Arc Value; 1241 1242 Value operator[](const Key& key) const { 1243 return _to.direct(_edge_ref[key], _from.direction(key)); 1244 } 1245 1246 const From& _from; 1247 const To& _to; 1248 const EdgeRefMap& _edge_ref; 1249 }; 1250 1251 public: 1252 1253 /// \brief Constructor of BpGraphCopy. 1254 /// 1255 /// Constructor of BpGraphCopy for copying the content of the 1256 /// \c from graph into the \c to graph. 1257 BpGraphCopy(const From& from, To& to) 1258 : _from(from), _to(to) {} 1259 1260 /// \brief Destructor of BpGraphCopy 1261 /// 1262 /// Destructor of BpGraphCopy. 1263 ~BpGraphCopy() { 1264 for (int i = 0; i < int(_node_maps.size()); ++i) { 1265 delete _node_maps[i]; 1266 } 1267 for (int i = 0; i < int(_red_maps.size()); ++i) { 1268 delete _red_maps[i]; 1269 } 1270 for (int i = 0; i < int(_blue_maps.size()); ++i) { 1271 delete _blue_maps[i]; 1272 } 1273 for (int i = 0; i < int(_arc_maps.size()); ++i) { 1274 delete _arc_maps[i]; 1275 } 1276 for (int i = 0; i < int(_edge_maps.size()); ++i) { 1277 delete _edge_maps[i]; 1278 } 1279 } 1280 1281 /// \brief Copy the node references into the given map. 1282 /// 1283 /// This function copies the node references into the given map. 1284 /// The parameter should be a map, whose key type is the Node type of 1285 /// the source graph, while the value type is the Node type of the 1286 /// destination graph. 1287 template <typename NodeRef> 1288 BpGraphCopy& nodeRef(NodeRef& map) { 1289 _node_maps.push_back(new _core_bits::RefCopy<From, Node, 1290 NodeRefMap, NodeRef>(map)); 1291 return *this; 1292 } 1293 1294 /// \brief Copy the node cross references into the given map. 1295 /// 1296 /// This function copies the node cross references (reverse references) 1297 /// into the given map. The parameter should be a map, whose key type 1298 /// is the Node type of the destination graph, while the value type is 1299 /// the Node type of the source graph. 1300 template <typename NodeCrossRef> 1301 BpGraphCopy& nodeCrossRef(NodeCrossRef& map) { 1302 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node, 1303 NodeRefMap, NodeCrossRef>(map)); 1304 return *this; 1305 } 1306 1307 /// \brief Make a copy of the given node map. 1308 /// 1309 /// This function makes a copy of the given node map for the newly 1310 /// created graph. 1311 /// The key type of the new map \c tmap should be the Node type of the 1312 /// destination graph, and the key type of the original map \c map 1313 /// should be the Node type of the source graph. 1314 template <typename FromMap, typename ToMap> 1315 BpGraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { 1316 _node_maps.push_back(new _core_bits::MapCopy<From, Node, 1317 NodeRefMap, FromMap, ToMap>(map, tmap)); 1318 return *this; 1319 } 1320 1321 /// \brief Make a copy of the given node. 1322 /// 1323 /// This function makes a copy of the given node. 1324 BpGraphCopy& node(const Node& node, TNode& tnode) { 1325 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, 1326 NodeRefMap, TNode>(node, tnode)); 1327 return *this; 1328 } 1329 1330 /// \brief Copy the red node references into the given map. 1331 /// 1332 /// This function copies the red node references into the given 1333 /// map. The parameter should be a map, whose key type is the 1334 /// Node type of the source graph with the red item set, while the 1335 /// value type is the Node type of the destination graph. 1336 template <typename RedRef> 1337 BpGraphCopy& redRef(RedRef& map) { 1338 _red_maps.push_back(new _core_bits::RefCopy<From, RedNode, 1339 RedNodeRefMap, RedRef>(map)); 1340 return *this; 1341 } 1342 1343 /// \brief Copy the red node cross references into the given map. 1344 /// 1345 /// This function copies the red node cross references (reverse 1346 /// references) into the given map. The parameter should be a map, 1347 /// whose key type is the Node type of the destination graph with 1348 /// the red item set, while the value type is the Node type of the 1349 /// source graph. 1350 template <typename RedCrossRef> 1351 BpGraphCopy& redCrossRef(RedCrossRef& map) { 1352 _red_maps.push_back(new _core_bits::CrossRefCopy<From, RedNode, 1353 RedNodeRefMap, RedCrossRef>(map)); 1354 return *this; 1355 } 1356 1357 /// \brief Make a copy of the given red node map. 1358 /// 1359 /// This function makes a copy of the given red node map for the newly 1360 /// created graph. 1361 /// The key type of the new map \c tmap should be the Node type of 1362 /// the destination graph with the red items, and the key type of 1363 /// the original map \c map should be the Node type of the source 1364 /// graph. 1365 template <typename FromMap, typename ToMap> 1366 BpGraphCopy& redNodeMap(const FromMap& map, ToMap& tmap) { 1367 _red_maps.push_back(new _core_bits::MapCopy<From, RedNode, 1368 RedNodeRefMap, FromMap, ToMap>(map, tmap)); 1369 return *this; 1370 } 1371 1372 /// \brief Make a copy of the given red node. 1373 /// 1374 /// This function makes a copy of the given red node. 1375 BpGraphCopy& redNode(const RedNode& node, TRedNode& tnode) { 1376 _red_maps.push_back(new _core_bits::ItemCopy<From, RedNode, 1377 RedNodeRefMap, TRedNode>(node, tnode)); 1378 return *this; 1379 } 1380 1381 /// \brief Copy the blue node references into the given map. 1382 /// 1383 /// This function copies the blue node references into the given 1384 /// map. The parameter should be a map, whose key type is the 1385 /// Node type of the source graph with the blue item set, while the 1386 /// value type is the Node type of the destination graph. 1387 template <typename BlueRef> 1388 BpGraphCopy& blueRef(BlueRef& map) { 1389 _blue_maps.push_back(new _core_bits::RefCopy<From, BlueNode, 1390 BlueNodeRefMap, BlueRef>(map)); 1391 return *this; 1392 } 1393 1394 /// \brief Copy the blue node cross references into the given map. 1395 /// 1396 /// This function copies the blue node cross references (reverse 1397 /// references) into the given map. The parameter should be a map, 1398 /// whose key type is the Node type of the destination graph with 1399 /// the blue item set, while the value type is the Node type of the 1400 /// source graph. 1401 template <typename BlueCrossRef> 1402 BpGraphCopy& blueCrossRef(BlueCrossRef& map) { 1403 _blue_maps.push_back(new _core_bits::CrossRefCopy<From, BlueNode, 1404 BlueNodeRefMap, BlueCrossRef>(map)); 1405 return *this; 1406 } 1407 1408 /// \brief Make a copy of the given blue node map. 1409 /// 1410 /// This function makes a copy of the given blue node map for the newly 1411 /// created graph. 1412 /// The key type of the new map \c tmap should be the Node type of 1413 /// the destination graph with the blue items, and the key type of 1414 /// the original map \c map should be the Node type of the source 1415 /// graph. 1416 template <typename FromMap, typename ToMap> 1417 BpGraphCopy& blueNodeMap(const FromMap& map, ToMap& tmap) { 1418 _blue_maps.push_back(new _core_bits::MapCopy<From, BlueNode, 1419 BlueNodeRefMap, FromMap, ToMap>(map, tmap)); 1420 return *this; 1421 } 1422 1423 /// \brief Make a copy of the given blue node. 1424 /// 1425 /// This function makes a copy of the given blue node. 1426 BpGraphCopy& blueNode(const BlueNode& node, TBlueNode& tnode) { 1427 _blue_maps.push_back(new _core_bits::ItemCopy<From, BlueNode, 1428 BlueNodeRefMap, TBlueNode>(node, tnode)); 1429 return *this; 1430 } 1431 1432 /// \brief Copy the arc references into the given map. 1433 /// 1434 /// This function copies the arc references into the given map. 1435 /// The parameter should be a map, whose key type is the Arc type of 1436 /// the source graph, while the value type is the Arc type of the 1437 /// destination graph. 1438 template <typename ArcRef> 1439 BpGraphCopy& arcRef(ArcRef& map) { 1440 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc, 1441 ArcRefMap, ArcRef>(map)); 1442 return *this; 1443 } 1444 1445 /// \brief Copy the arc cross references into the given map. 1446 /// 1447 /// This function copies the arc cross references (reverse references) 1448 /// into the given map. The parameter should be a map, whose key type 1449 /// is the Arc type of the destination graph, while the value type is 1450 /// the Arc type of the source graph. 1451 template <typename ArcCrossRef> 1452 BpGraphCopy& arcCrossRef(ArcCrossRef& map) { 1453 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc, 1454 ArcRefMap, ArcCrossRef>(map)); 1455 return *this; 1456 } 1457 1458 /// \brief Make a copy of the given arc map. 1459 /// 1460 /// This function makes a copy of the given arc map for the newly 1461 /// created graph. 1462 /// The key type of the new map \c tmap should be the Arc type of the 1463 /// destination graph, and the key type of the original map \c map 1464 /// should be the Arc type of the source graph. 1465 template <typename FromMap, typename ToMap> 1466 BpGraphCopy& arcMap(const FromMap& map, ToMap& tmap) { 1467 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, 1468 ArcRefMap, FromMap, ToMap>(map, tmap)); 1469 return *this; 1470 } 1471 1472 /// \brief Make a copy of the given arc. 1473 /// 1474 /// This function makes a copy of the given arc. 1475 BpGraphCopy& arc(const Arc& arc, TArc& tarc) { 1476 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, 1477 ArcRefMap, TArc>(arc, tarc)); 1478 return *this; 1479 } 1480 1481 /// \brief Copy the edge references into the given map. 1482 /// 1483 /// This function copies the edge references into the given map. 1484 /// The parameter should be a map, whose key type is the Edge type of 1485 /// the source graph, while the value type is the Edge type of the 1486 /// destination graph. 1487 template <typename EdgeRef> 1488 BpGraphCopy& edgeRef(EdgeRef& map) { 1489 _edge_maps.push_back(new _core_bits::RefCopy<From, Edge, 1490 EdgeRefMap, EdgeRef>(map)); 1491 return *this; 1492 } 1493 1494 /// \brief Copy the edge cross references into the given map. 1495 /// 1496 /// This function copies the edge cross references (reverse references) 1497 /// into the given map. The parameter should be a map, whose key type 1498 /// is the Edge type of the destination graph, while the value type is 1499 /// the Edge type of the source graph. 1500 template <typename EdgeCrossRef> 1501 BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) { 1502 _edge_maps.push_back(new _core_bits::CrossRefCopy<From, 1503 Edge, EdgeRefMap, EdgeCrossRef>(map)); 1504 return *this; 1505 } 1506 1507 /// \brief Make a copy of the given edge map. 1508 /// 1509 /// This function makes a copy of the given edge map for the newly 1510 /// created graph. 1511 /// The key type of the new map \c tmap should be the Edge type of the 1512 /// destination graph, and the key type of the original map \c map 1513 /// should be the Edge type of the source graph. 1514 template <typename FromMap, typename ToMap> 1515 BpGraphCopy& edgeMap(const FromMap& map, ToMap& tmap) { 1516 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge, 1517 EdgeRefMap, FromMap, ToMap>(map, tmap)); 1518 return *this; 1519 } 1520 1521 /// \brief Make a copy of the given edge. 1522 /// 1523 /// This function makes a copy of the given edge. 1524 BpGraphCopy& edge(const Edge& edge, TEdge& tedge) { 1525 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge, 1526 EdgeRefMap, TEdge>(edge, tedge)); 1527 return *this; 1528 } 1529 1530 /// \brief Execute copying. 1531 /// 1532 /// This function executes the copying of the graph along with the 1533 /// copying of the assigned data. 1534 void run() { 1535 RedNodeRefMap redNodeRefMap(_from); 1536 BlueNodeRefMap blueNodeRefMap(_from); 1537 NodeRefMap nodeRefMap(_from, redNodeRefMap, blueNodeRefMap); 1538 EdgeRefMap edgeRefMap(_from); 1539 ArcRefMap arcRefMap(_from, _to, edgeRefMap); 1540 _core_bits::BpGraphCopySelector<To>:: 1541 copy(_from, _to, redNodeRefMap, blueNodeRefMap, edgeRefMap); 1542 for (int i = 0; i < int(_node_maps.size()); ++i) { 1543 _node_maps[i]->copy(_from, nodeRefMap); 1544 } 1545 for (int i = 0; i < int(_red_maps.size()); ++i) { 1546 _red_maps[i]->copy(_from, redNodeRefMap); 1547 } 1548 for (int i = 0; i < int(_blue_maps.size()); ++i) { 1549 _blue_maps[i]->copy(_from, blueNodeRefMap); 1550 } 1551 for (int i = 0; i < int(_edge_maps.size()); ++i) { 1552 _edge_maps[i]->copy(_from, edgeRefMap); 1553 } 1554 for (int i = 0; i < int(_arc_maps.size()); ++i) { 1555 _arc_maps[i]->copy(_from, arcRefMap); 1556 } 1557 } 1558 1559 private: 1560 1561 const From& _from; 1562 To& _to; 1563 1564 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > 1565 _node_maps; 1566 1567 std::vector<_core_bits::MapCopyBase<From, RedNode, RedNodeRefMap>* > 1568 _red_maps; 1569 1570 std::vector<_core_bits::MapCopyBase<From, BlueNode, BlueNodeRefMap>* > 1571 _blue_maps; 1572 1573 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > 1574 _arc_maps; 1575 1576 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 1577 _edge_maps; 1578 1579 }; 1580 1581 /// \brief Copy a graph to another graph. 1582 /// 1583 /// This function copies a graph to another graph. 1584 /// The complete usage of it is detailed in the BpGraphCopy class, 1585 /// but a short example shows a basic work: 1586 ///\code 1587 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run(); 1588 ///\endcode 1589 /// 1590 /// After the copy the \c nr map will contain the mapping from the 1591 /// nodes of the \c from graph to the nodes of the \c to graph and 1592 /// \c ecr will contain the mapping from the edges of the \c to graph 1593 /// to the edges of the \c from graph. 1594 /// 1595 /// \see BpGraphCopy 1596 template <typename From, typename To> 1597 BpGraphCopy<From, To> 1598 bpGraphCopy(const From& from, To& to) { 1599 return BpGraphCopy<From, To>(from, to); 1600 } 1601 1602 namespace _core_bits { 1603 1604 template <typename Graph, typename Enable = void> 1605 struct FindArcSelector { 1606 typedef typename Graph::Node Node; 1607 typedef typename Graph::Arc Arc; 1608 static Arc find(const Graph &g, Node u, Node v, Arc e) { 1609 if (e == INVALID) { 1610 g.firstOut(e, u); 1611 } else { 1612 g.nextOut(e); 1613 } 1614 while (e != INVALID && g.target(e) != v) { 1615 g.nextOut(e); 1616 } 1617 return e; 1618 } 1619 }; 1620 1621 template <typename Graph> 1622 struct FindArcSelector< 1623 Graph, 1624 typename enable_if<typename Graph::FindArcTag, void>::type> 1625 { 1626 typedef typename Graph::Node Node; 1627 typedef typename Graph::Arc Arc; 1628 static Arc find(const Graph &g, Node u, Node v, Arc prev) { 1629 return g.findArc(u, v, prev); 1630 } 1631 }; 1632 } 1633 1634 /// \brief Find an arc between two nodes of a digraph. 1635 /// 1636 /// This function finds an arc from node \c u to node \c v in the 1637 /// digraph \c g. 1638 /// 1639 /// If \c prev is \ref INVALID (this is the default value), then 1640 /// it finds the first arc from \c u to \c v. Otherwise it looks for 1641 /// the next arc from \c u to \c v after \c prev. 1642 /// \return The found arc or \ref INVALID if there is no such an arc. 1643 /// 1644 /// Thus you can iterate through each arc from \c u to \c v as it follows. 1645 ///\code 1646 /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) { 1647 /// ... 1648 /// } 1649 ///\endcode 1650 /// 1651 /// \note \ref ConArcIt provides iterator interface for the same 1652 /// functionality. 1653 /// 1654 ///\sa ConArcIt 1655 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp 1656 template <typename Graph> 1657 inline typename Graph::Arc 1658 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v, 1659 typename Graph::Arc prev = INVALID) { 1660 return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev); 1661 } 1662 1663 /// \brief Iterator for iterating on parallel arcs connecting the same nodes. 1664 /// 1665 /// Iterator for iterating on parallel arcs connecting the same nodes. It is 1666 /// a higher level interface for the \ref findArc() function. You can 1667 /// use it the following way: 1668 ///\code 1669 /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) { 1670 /// ... 1671 /// } 1672 ///\endcode 1673 /// 1674 ///\sa findArc() 1675 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp 1676 template <typename GR> 1677 class ConArcIt : public GR::Arc { 1678 typedef typename GR::Arc Parent; 1679 1680 public: 1681 1682 typedef typename GR::Arc Arc; 1683 typedef typename GR::Node Node; 1684 1685 /// \brief Constructor. 1686 /// 1687 /// Construct a new ConArcIt iterating on the arcs that 1688 /// connects nodes \c u and \c v. 1689 ConArcIt(const GR& g, Node u, Node v) : _graph(g) { 1690 Parent::operator=(findArc(_graph, u, v)); 1691 } 1692 1693 /// \brief Constructor. 1694 /// 1695 /// Construct a new ConArcIt that continues the iterating from arc \c a. 1696 ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {} 1697 1698 /// \brief Increment operator. 1699 /// 1700 /// It increments the iterator and gives back the next arc. 1701 ConArcIt& operator++() { 1702 Parent::operator=(findArc(_graph, _graph.source(*this), 1703 _graph.target(*this), *this)); 1704 return *this; 1705 } 1706 private: 1707 const GR& _graph; 1708 }; 1709 1710 namespace _core_bits { 1711 1712 template <typename Graph, typename Enable = void> 1713 struct FindEdgeSelector { 1714 typedef typename Graph::Node Node; 1715 typedef typename Graph::Edge Edge; 1716 static Edge find(const Graph &g, Node u, Node v, Edge e) { 1717 bool b; 1718 if (u != v) { 1719 if (e == INVALID) { 1720 g.firstInc(e, b, u); 1721 } else { 1722 b = g.u(e) == u; 1723 g.nextInc(e, b); 1724 } 1725 while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) { 1726 g.nextInc(e, b); 1727 } 1728 } else { 1729 if (e == INVALID) { 1730 g.firstInc(e, b, u); 1731 } else { 1732 b = true; 1733 g.nextInc(e, b); 1734 } 1735 while (e != INVALID && (!b || g.v(e) != v)) { 1736 g.nextInc(e, b); 1737 } 1738 } 1739 return e; 1740 } 1741 }; 1742 1743 template <typename Graph> 1744 struct FindEdgeSelector< 1745 Graph, 1746 typename enable_if<typename Graph::FindEdgeTag, void>::type> 1747 { 1748 typedef typename Graph::Node Node; 1749 typedef typename Graph::Edge Edge; 1750 static Edge find(const Graph &g, Node u, Node v, Edge prev) { 1751 return g.findEdge(u, v, prev); 1752 } 1753 }; 1754 } 1755 1756 /// \brief Find an edge between two nodes of a graph. 1757 /// 1758 /// This function finds an edge from node \c u to node \c v in graph \c g. 1759 /// If node \c u and node \c v is equal then each loop edge 1760 /// will be enumerated once. 1761 /// 1762 /// If \c prev is \ref INVALID (this is the default value), then 1763 /// it finds the first edge from \c u to \c v. Otherwise it looks for 1764 /// the next edge from \c u to \c v after \c prev. 1765 /// \return The found edge or \ref INVALID if there is no such an edge. 1766 /// 1767 /// Thus you can iterate through each edge between \c u and \c v 1768 /// as it follows. 1769 ///\code 1770 /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) { 1771 /// ... 1772 /// } 1773 ///\endcode 1774 /// 1775 /// \note \ref ConEdgeIt provides iterator interface for the same 1776 /// functionality. 1777 /// 1778 ///\sa ConEdgeIt 1779 template <typename Graph> 1780 inline typename Graph::Edge 1781 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v, 1782 typename Graph::Edge p = INVALID) { 1783 return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p); 1784 } 1785 1786 /// \brief Iterator for iterating on parallel edges connecting the same nodes. 1787 /// 1788 /// Iterator for iterating on parallel edges connecting the same nodes. 1789 /// It is a higher level interface for the findEdge() function. You can 1790 /// use it the following way: 1791 ///\code 1792 /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) { 1793 /// ... 1794 /// } 1795 ///\endcode 1796 /// 1797 ///\sa findEdge() 1798 template <typename GR> 1799 class ConEdgeIt : public GR::Edge { 1800 typedef typename GR::Edge Parent; 1801 1802 public: 1803 1804 typedef typename GR::Edge Edge; 1805 typedef typename GR::Node Node; 1806 1807 /// \brief Constructor. 1808 /// 1809 /// Construct a new ConEdgeIt iterating on the edges that 1810 /// connects nodes \c u and \c v. 1811 ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) { 1812 Parent::operator=(findEdge(_graph, _u, _v)); 1813 } 1814 1815 /// \brief Constructor. 1816 /// 1817 /// Construct a new ConEdgeIt that continues iterating from edge \c e. 1818 ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {} 1819 1820 /// \brief Increment operator. 1821 /// 1822 /// It increments the iterator and gives back the next edge. 1823 ConEdgeIt& operator++() { 1824 Parent::operator=(findEdge(_graph, _u, _v, *this)); 1825 return *this; 1826 } 1827 private: 1828 const GR& _graph; 1829 Node _u, _v; 1830 }; 1831 1832 1833 ///Dynamic arc look-up between given endpoints. 1834 1835 ///Using this class, you can find an arc in a digraph from a given 1836 ///source to a given target in amortized time <em>O</em>(log<em>d</em>), 1837 ///where <em>d</em> is the out-degree of the source node. 1838 /// 1839 ///It is possible to find \e all parallel arcs between two nodes with 1840 ///the \c operator() member. 1841 /// 1842 ///This is a dynamic data structure. Consider to use \ref ArcLookUp or 1843 ///\ref AllArcLookUp if your digraph is not changed so frequently. 1844 /// 1845 ///This class uses a self-adjusting binary search tree, the Splay tree 1846 ///of Sleator and Tarjan to guarantee the logarithmic amortized 1847 ///time bound for arc look-ups. This class also guarantees the 1848 ///optimal time bound in a constant factor for any distribution of 1849 ///queries. 1850 /// 1851 ///\tparam GR The type of the underlying digraph. 1852 /// 1853 ///\sa ArcLookUp 1854 ///\sa AllArcLookUp 1855 template <typename GR> 1856 class DynArcLookUp 1857 : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase 1858 { 1859 typedef typename ItemSetTraits<GR, typename GR::Arc> 1860 ::ItemNotifier::ObserverBase Parent; 1861 1862 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1863 1864 public: 1865 1866 /// The Digraph type 1867 typedef GR Digraph; 1868 1869 protected: 1870 1871 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type 1872 { 1873 typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent; 1874 1875 public: 1876 1877 AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {} 1878 1879 virtual void add(const Node& node) { 1880 Parent::add(node); 1881 Parent::set(node, INVALID); 1882 } 1883 1884 virtual void add(const std::vector<Node>& nodes) { 1885 Parent::add(nodes); 1886 for (int i = 0; i < int(nodes.size()); ++i) { 1887 Parent::set(nodes[i], INVALID); 1888 } 1889 } 1890 1891 virtual void build() { 1892 Parent::build(); 1893 Node it; 1894 typename Parent::Notifier* nf = Parent::notifier(); 1895 for (nf->first(it); it != INVALID; nf->next(it)) { 1896 Parent::set(it, INVALID); 1897 } 1898 } 1899 }; 1900 1901 class ArcLess { 1902 const Digraph &g; 1903 public: 1904 ArcLess(const Digraph &_g) : g(_g) {} 1905 bool operator()(Arc a,Arc b) const 1906 { 1907 return g.target(a)<g.target(b); 1908 } 1909 }; 1910 1911 protected: 1912 1913 const Digraph &_g; 1914 AutoNodeMap _head; 1915 typename Digraph::template ArcMap<Arc> _parent; 1916 typename Digraph::template ArcMap<Arc> _left; 1917 typename Digraph::template ArcMap<Arc> _right; 1918 1919 public: 1920 1921 ///Constructor 1922 1923 ///Constructor. 1924 /// 1925 ///It builds up the search database. 1926 DynArcLookUp(const Digraph &g) 1927 : _g(g),_head(g),_parent(g),_left(g),_right(g) 1928 { 1929 Parent::attach(_g.notifier(typename Digraph::Arc())); 1930 refresh(); 1931 } 1932 1933 protected: 1934 1935 virtual void add(const Arc& arc) { 1936 insert(arc); 1937 } 1938 1939 virtual void add(const std::vector<Arc>& arcs) { 1940 for (int i = 0; i < int(arcs.size()); ++i) { 1941 insert(arcs[i]); 1942 } 1943 } 1944 1945 virtual void erase(const Arc& arc) { 1946 remove(arc); 1947 } 1948 1949 virtual void erase(const std::vector<Arc>& arcs) { 1950 for (int i = 0; i < int(arcs.size()); ++i) { 1951 remove(arcs[i]); 1952 } 1953 } 1954 1955 virtual void build() { 1956 refresh(); 1957 } 1958 1959 virtual void clear() { 1960 for(NodeIt n(_g);n!=INVALID;++n) { 1961 _head[n] = INVALID; 1962 } 1963 } 1964 1965 void insert(Arc arc) { 1966 Node s = _g.source(arc); 1967 Node t = _g.target(arc); 1968 _left[arc] = INVALID; 1969 _right[arc] = INVALID; 1970 1971 Arc e = _head[s]; 1972 if (e == INVALID) { 1973 _head[s] = arc; 1974 _parent[arc] = INVALID; 1975 return; 1976 } 1977 while (true) { 1978 if (t < _g.target(e)) { 1979 if (_left[e] == INVALID) { 1980 _left[e] = arc; 1981 _parent[arc] = e; 1982 splay(arc); 1983 return; 1984 } else { 1985 e = _left[e]; 1986 } 1987 } else { 1988 if (_right[e] == INVALID) { 1989 _right[e] = arc; 1990 _parent[arc] = e; 1991 splay(arc); 1992 return; 1993 } else { 1994 e = _right[e]; 1995 } 1996 } 1997 } 1998 } 1999 2000 void remove(Arc arc) { 2001 if (_left[arc] == INVALID) { 2002 if (_right[arc] != INVALID) { 2003 _parent[_right[arc]] = _parent[arc]; 2004 } 2005 if (_parent[arc] != INVALID) { 2006 if (_left[_parent[arc]] == arc) { 2007 _left[_parent[arc]] = _right[arc]; 2008 } else { 2009 _right[_parent[arc]] = _right[arc]; 2010 } 2011 } else { 2012 _head[_g.source(arc)] = _right[arc]; 2013 } 2014 } else if (_right[arc] == INVALID) { 2015 _parent[_left[arc]] = _parent[arc]; 2016 if (_parent[arc] != INVALID) { 2017 if (_left[_parent[arc]] == arc) { 2018 _left[_parent[arc]] = _left[arc]; 2019 } else { 2020 _right[_parent[arc]] = _left[arc]; 2021 } 2022 } else { 2023 _head[_g.source(arc)] = _left[arc]; 2024 } 2025 } else { 2026 Arc e = _left[arc]; 2027 if (_right[e] != INVALID) { 2028 e = _right[e]; 2029 while (_right[e] != INVALID) { 2030 e = _right[e]; 2031 } 2032 Arc s = _parent[e]; 2033 _right[_parent[e]] = _left[e]; 2034 if (_left[e] != INVALID) { 2035 _parent[_left[e]] = _parent[e]; 2036 } 2037 2038 _left[e] = _left[arc]; 2039 _parent[_left[arc]] = e; 2040 _right[e] = _right[arc]; 2041 _parent[_right[arc]] = e; 2042 2043 _parent[e] = _parent[arc]; 2044 if (_parent[arc] != INVALID) { 2045 if (_left[_parent[arc]] == arc) { 2046 _left[_parent[arc]] = e; 2047 } else { 2048 _right[_parent[arc]] = e; 2049 } 2050 } 2051 splay(s); 2052 } else { 2053 _right[e] = _right[arc]; 2054 _parent[_right[arc]] = e; 2055 _parent[e] = _parent[arc]; 2056 2057 if (_parent[arc] != INVALID) { 2058 if (_left[_parent[arc]] == arc) { 2059 _left[_parent[arc]] = e; 2060 } else { 2061 _right[_parent[arc]] = e; 2062 } 2063 } else { 2064 _head[_g.source(arc)] = e; 2065 } 2066 } 2067 } 2068 } 2069 2070 Arc refreshRec(std::vector<Arc> &v,int a,int b) 2071 { 2072 int m=(a+b)/2; 2073 Arc me=v[m]; 2074 if (a < m) { 2075 Arc left = refreshRec(v,a,m-1); 2076 _left[me] = left; 2077 _parent[left] = me; 2078 } else { 2079 _left[me] = INVALID; 2080 } 2081 if (m < b) { 2082 Arc right = refreshRec(v,m+1,b); 2083 _right[me] = right; 2084 _parent[right] = me; 2085 } else { 2086 _right[me] = INVALID; 2087 } 2088 return me; 2089 } 2090 2091 void refresh() { 2092 for(NodeIt n(_g);n!=INVALID;++n) { 2093 std::vector<Arc> v; 2094 for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a); 2095 if (!v.empty()) { 2096 std::sort(v.begin(),v.end(),ArcLess(_g)); 2097 Arc head = refreshRec(v,0,v.size()-1); 2098 _head[n] = head; 2099 _parent[head] = INVALID; 2100 } 2101 else _head[n] = INVALID; 2102 } 2103 } 2104 2105 void zig(Arc v) { 2106 Arc w = _parent[v]; 2107 _parent[v] = _parent[w]; 2108 _parent[w] = v; 2109 _left[w] = _right[v]; 2110 _right[v] = w; 2111 if (_parent[v] != INVALID) { 2112 if (_right[_parent[v]] == w) { 2113 _right[_parent[v]] = v; 2114 } else { 2115 _left[_parent[v]] = v; 2116 } 2117 } 2118 if (_left[w] != INVALID){ 2119 _parent[_left[w]] = w; 2120 } 2121 } 2122 2123 void zag(Arc v) { 2124 Arc w = _parent[v]; 2125 _parent[v] = _parent[w]; 2126 _parent[w] = v; 2127 _right[w] = _left[v]; 2128 _left[v] = w; 2129 if (_parent[v] != INVALID){ 2130 if (_left[_parent[v]] == w) { 2131 _left[_parent[v]] = v; 2132 } else { 2133 _right[_parent[v]] = v; 2134 } 2135 } 2136 if (_right[w] != INVALID){ 2137 _parent[_right[w]] = w; 2138 } 2139 } 2140 2141 void splay(Arc v) { 2142 while (_parent[v] != INVALID) { 2143 if (v == _left[_parent[v]]) { 2144 if (_parent[_parent[v]] == INVALID) { 2145 zig(v); 2146 } else { 2147 if (_parent[v] == _left[_parent[_parent[v]]]) { 2148 zig(_parent[v]); 2149 zig(v); 2150 } else { 2151 zig(v); 2152 zag(v); 2153 } 2154 } 2155 } else { 2156 if (_parent[_parent[v]] == INVALID) { 2157 zag(v); 2158 } else { 2159 if (_parent[v] == _left[_parent[_parent[v]]]) { 2160 zag(v); 2161 zig(v); 2162 } else { 2163 zag(_parent[v]); 2164 zag(v); 2165 } 2166 } 2167 } 2168 } 2169 _head[_g.source(v)] = v; 2170 } 2171 2172 2173 public: 2174 2175 ///Find an arc between two nodes. 2176 2177 ///Find an arc between two nodes. 2178 ///\param s The source node. 2179 ///\param t The target node. 2180 ///\param p The previous arc between \c s and \c t. It it is INVALID or 2181 ///not given, the operator finds the first appropriate arc. 2182 ///\return An arc from \c s to \c t after \c p or 2183 ///\ref INVALID if there is no more. 2184 /// 2185 ///For example, you can count the number of arcs from \c u to \c v in the 2186 ///following way. 2187 ///\code 2188 ///DynArcLookUp<ListDigraph> ae(g); 2189 ///... 2190 ///int n = 0; 2191 ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++; 2192 ///\endcode 2193 /// 2194 ///Finding the arcs take at most <em>O</em>(log<em>d</em>) 2195 ///amortized time, specifically, the time complexity of the lookups 2196 ///is equal to the optimal search tree implementation for the 2197 ///current query distribution in a constant factor. 2198 /// 2199 ///\note This is a dynamic data structure, therefore the data 2200 ///structure is updated after each graph alteration. Thus although 2201 ///this data structure is theoretically faster than \ref ArcLookUp 2202 ///and \ref AllArcLookUp, it often provides worse performance than 2203 ///them. 2204 Arc operator()(Node s, Node t, Arc p = INVALID) const { 2205 if (p == INVALID) { 2206 Arc a = _head[s]; 2207 if (a == INVALID) return INVALID; 2208 Arc r = INVALID; 2209 while (true) { 2210 if (_g.target(a) < t) { 2211 if (_right[a] == INVALID) { 2212 const_cast<DynArcLookUp&>(*this).splay(a); 2213 return r; 2214 } else { 2215 a = _right[a]; 2216 } 2217 } else { 2218 if (_g.target(a) == t) { 2219 r = a; 2220 } 2221 if (_left[a] == INVALID) { 2222 const_cast<DynArcLookUp&>(*this).splay(a); 2223 return r; 2224 } else { 2225 a = _left[a]; 2226 } 2227 } 2228 } 2229 } else { 2230 Arc a = p; 2231 if (_right[a] != INVALID) { 2232 a = _right[a]; 2233 while (_left[a] != INVALID) { 2234 a = _left[a]; 2235 } 2236 const_cast<DynArcLookUp&>(*this).splay(a); 2237 } else { 2238 while (_parent[a] != INVALID && _right[_parent[a]] == a) { 2239 a = _parent[a]; 2240 } 2241 if (_parent[a] == INVALID) { 2242 return INVALID; 2243 } else { 2244 a = _parent[a]; 2245 const_cast<DynArcLookUp&>(*this).splay(a); 2246 } 2247 } 2248 if (_g.target(a) == t) return a; 2249 else return INVALID; 2250 } 2251 } 2252 2253 }; 2254 2255 ///Fast arc look-up between given endpoints. 2256 2257 ///Using this class, you can find an arc in a digraph from a given 2258 ///source to a given target in time <em>O</em>(log<em>d</em>), 2259 ///where <em>d</em> is the out-degree of the source node. 2260 /// 2261 ///It is not possible to find \e all parallel arcs between two nodes. 2262 ///Use \ref AllArcLookUp for this purpose. 2263 /// 2264 ///\warning This class is static, so you should call refresh() (or at 2265 ///least refresh(Node)) to refresh this data structure whenever the 2266 ///digraph changes. This is a time consuming (superlinearly proportional 2267 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 2268 /// 2269 ///\tparam GR The type of the underlying digraph. 2270 /// 2271 ///\sa DynArcLookUp 2272 ///\sa AllArcLookUp 2273 template<class GR> 2274 class ArcLookUp 2275 { 2276 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 2277 2278 public: 2279 2280 /// The Digraph type 2281 typedef GR Digraph; 2282 2283 protected: 2284 const Digraph &_g; 2285 typename Digraph::template NodeMap<Arc> _head; 2286 typename Digraph::template ArcMap<Arc> _left; 2287 typename Digraph::template ArcMap<Arc> _right; 2288 2289 class ArcLess { 2290 const Digraph &g; 2291 public: 2292 ArcLess(const Digraph &_g) : g(_g) {} 2293 bool operator()(Arc a,Arc b) const 2294 { 2295 return g.target(a)<g.target(b); 2296 } 2297 }; 2298 2299 public: 2300 2301 ///Constructor 2302 2303 ///Constructor. 2304 /// 2305 ///It builds up the search database, which remains valid until the digraph 2306 ///changes. 2307 ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();} 2308 2309 private: 2310 Arc refreshRec(std::vector<Arc> &v,int a,int b) 2311 { 2312 int m=(a+b)/2; 2313 Arc me=v[m]; 2314 _left[me] = a<m?refreshRec(v,a,m-1):INVALID; 2315 _right[me] = m<b?refreshRec(v,m+1,b):INVALID; 2316 return me; 2317 } 2318 public: 2319 ///Refresh the search data structure at a node. 2320 2321 ///Build up the search database of node \c n. 2322 /// 2323 ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> 2324 ///is the number of the outgoing arcs of \c n. 2325 void refresh(Node n) 2326 { 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 _head[n]=refreshRec(v,0,v.size()-1); 2332 } 2333 else _head[n]=INVALID; 2334 } 2335 ///Refresh the full data structure. 2336 2337 ///Build up the full search database. In fact, it simply calls 2338 ///\ref refresh(Node) "refresh(n)" for each node \c n. 2339 /// 2340 ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is 2341 ///the number of the arcs in the digraph and <em>D</em> is the maximum 2342 ///out-degree of the digraph. 2343 void refresh() 2344 { 2345 for(NodeIt n(_g);n!=INVALID;++n) refresh(n); 2346 } 2347 2348 ///Find an arc between two nodes. 2349 2350 ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>), 2351 ///where <em>d</em> is the number of outgoing arcs of \c s. 2352 ///\param s The source node. 2353 ///\param t The target node. 2354 ///\return An arc from \c s to \c t if there exists, 2355 ///\ref INVALID otherwise. 2356 /// 2357 ///\warning If you change the digraph, refresh() must be called before using 2358 ///this operator. If you change the outgoing arcs of 2359 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. 2360 Arc operator()(Node s, Node t) const 2361 { 2362 Arc e; 2363 for(e=_head[s]; 2364 e!=INVALID&&_g.target(e)!=t; 2365 e = t < _g.target(e)?_left[e]:_right[e]) ; 2366 return e; 2367 } 2368 2369 }; 2370 2371 ///Fast look-up of all arcs between given endpoints. 2372 2373 ///This class is the same as \ref ArcLookUp, with the addition 2374 ///that it makes it possible to find all parallel arcs between given 2375 ///endpoints. 2376 /// 2377 ///\warning This class is static, so you should call refresh() (or at 2378 ///least refresh(Node)) to refresh this data structure whenever the 2379 ///digraph changes. This is a time consuming (superlinearly proportional 2380 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 2381 /// 2382 ///\tparam GR The type of the underlying digraph. 2383 /// 2384 ///\sa DynArcLookUp 2385 ///\sa ArcLookUp 2386 template<class GR> 2387 class AllArcLookUp : public ArcLookUp<GR> 2388 { 2389 using ArcLookUp<GR>::_g; 2390 using ArcLookUp<GR>::_right; 2391 using ArcLookUp<GR>::_left; 2392 using ArcLookUp<GR>::_head; 2393 2394 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 2395 2396 typename GR::template ArcMap<Arc> _next; 2397 2398 Arc refreshNext(Arc head,Arc next=INVALID) 2399 { 2400 if(head==INVALID) return next; 2401 else { 2402 next=refreshNext(_right[head],next); 2403 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head)) 2404 ? next : INVALID; 2405 return refreshNext(_left[head],head); 2406 } 2407 } 2408 2409 void refreshNext() 2410 { 2411 for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]); 2412 } 2413 2414 public: 2415 2416 /// The Digraph type 2417 typedef GR Digraph; 2418 2419 ///Constructor 2420 2421 ///Constructor. 2422 /// 2423 ///It builds up the search database, which remains valid until the digraph 2424 ///changes. 2425 AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();} 2426 2427 ///Refresh the data structure at a node. 2428 2429 ///Build up the search database of node \c n. 2430 /// 2431 ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is 2432 ///the number of the outgoing arcs of \c n. 2433 void refresh(Node n) 2434 { 2435 ArcLookUp<GR>::refresh(n); 2436 refreshNext(_head[n]); 2437 } 2438 2439 ///Refresh the full data structure. 2440 2441 ///Build up the full search database. In fact, it simply calls 2442 ///\ref refresh(Node) "refresh(n)" for each node \c n. 2443 /// 2444 ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is 2445 ///the number of the arcs in the digraph and <em>D</em> is the maximum 2446 ///out-degree of the digraph. 2447 void refresh() 2448 { 2449 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]); 2450 } 2451 2452 ///Find an arc between two nodes. 2453 2454 ///Find an arc between two nodes. 2455 ///\param s The source node. 2456 ///\param t The target node. 2457 ///\param prev The previous arc between \c s and \c t. It it is INVALID or 2458 ///not given, the operator finds the first appropriate arc. 2459 ///\return An arc from \c s to \c t after \c prev or 2460 ///\ref INVALID if there is no more. 2461 /// 2462 ///For example, you can count the number of arcs from \c u to \c v in the 2463 ///following way. 2464 ///\code 2465 ///AllArcLookUp<ListDigraph> ae(g); 2466 ///... 2467 ///int n = 0; 2468 ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++; 2469 ///\endcode 2470 /// 2471 ///Finding the first arc take <em>O</em>(log<em>d</em>) time, 2472 ///where <em>d</em> is the number of outgoing arcs of \c s. Then the 2473 ///consecutive arcs are found in constant time. 2474 /// 2475 ///\warning If you change the digraph, refresh() must be called before using 2476 ///this operator. If you change the outgoing arcs of 2477 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. 2478 /// 2479 Arc operator()(Node s, Node t, Arc prev=INVALID) const 2480 { 2481 if(prev==INVALID) 2482 { 2483 Arc f=INVALID; 2484 Arc e; 2485 for(e=_head[s]; 2486 e!=INVALID&&_g.target(e)!=t; 2487 e = t < _g.target(e)?_left[e]:_right[e]) ; 2488 while(e!=INVALID) 2489 if(_g.target(e)==t) 2490 { 2491 f = e; 2492 e = _left[e]; 2493 } 2494 else e = _right[e]; 2495 return f; 2496 } 2497 else return _next[prev]; 2498 } 2499 2500 }; 2501 2502 /// @} 2503 2504 } //namespace lemon 2505 2506 #endif 2507