Changeset 282:dc9e8d2c0df9 in lemon1.2 for lemon/core.h
 Timestamp:
 09/26/08 13:46:49 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/core.h
r233 r282 59 59 /// @{ 60 60 61 ///Create s conveniencetypedefs for the digraph types and iterators62 63 ///This \c \#define creates convenien ce typedefs for the following types64 /// of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,61 ///Create convenient typedefs for the digraph types and iterators 62 63 ///This \c \#define creates convenient type definitions for the following 64 ///types of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt, 65 65 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 66 66 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. … … 81 81 typedef Digraph::ArcMap<bool> BoolArcMap; \ 82 82 typedef Digraph::ArcMap<int> IntArcMap; \ 83 typedef Digraph::ArcMap<double> DoubleArcMap 84 85 ///Create s conveniencetypedefs for the digraph types and iterators83 typedef Digraph::ArcMap<double> DoubleArcMap; 84 85 ///Create convenient typedefs for the digraph types and iterators 86 86 87 87 ///\see DIGRAPH_TYPEDEFS … … 101 101 typedef typename Digraph::template ArcMap<bool> BoolArcMap; \ 102 102 typedef typename Digraph::template ArcMap<int> IntArcMap; \ 103 typedef typename Digraph::template ArcMap<double> DoubleArcMap 104 105 ///Create s conveniencetypedefs for the graph types and iterators106 107 ///This \c \#define creates the same convenien ce typedefs as defined103 typedef typename Digraph::template ArcMap<double> DoubleArcMap; 104 105 ///Create convenient typedefs for the graph types and iterators 106 107 ///This \c \#define creates the same convenient type definitions as defined 108 108 ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates 109 109 ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap, … … 111 111 /// 112 112 ///\note If the graph type is a dependent type, ie. the graph type depend 113 ///on a template parameter, then use \c TEMPLATE_ DIGRAPH_TYPEDEFS()113 ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS() 114 114 ///macro. 115 115 #define GRAPH_TYPEDEFS(Graph) \ … … 120 120 typedef Graph::EdgeMap<bool> BoolEdgeMap; \ 121 121 typedef Graph::EdgeMap<int> IntEdgeMap; \ 122 typedef Graph::EdgeMap<double> DoubleEdgeMap 123 124 ///Create s conveniencetypedefs for the graph types and iterators122 typedef Graph::EdgeMap<double> DoubleEdgeMap; 123 124 ///Create convenient typedefs for the graph types and iterators 125 125 126 126 ///\see GRAPH_TYPEDEFS … … 135 135 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \ 136 136 typedef typename Graph::template EdgeMap<int> IntEdgeMap; \ 137 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap 138 139 /// \brief Function to count the items in thegraph.140 /// 141 /// This function counts the items (nodes, arcs etc ) in thegraph.142 /// The complexity of the function is O(n)because137 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap; 138 139 /// \brief Function to count the items in a graph. 140 /// 141 /// This function counts the items (nodes, arcs etc.) in a graph. 142 /// The complexity of the function is linear because 143 143 /// it iterates on all of the items. 144 144 template <typename Graph, typename Item> … … 177 177 /// 178 178 /// This function counts the nodes in the graph. 179 /// The complexity of the function is O(n)but for some180 /// graph structures it is specialized to run in O(1).181 /// 182 /// If the graph contains a \enodeNum() member function and a183 /// \ eNodeNumTag tag then this function calls directly the member179 /// The complexity of the function is <em>O</em>(<em>n</em>), but for some 180 /// graph structures it is specialized to run in <em>O</em>(1). 181 /// 182 /// \note If the graph contains a \c nodeNum() member function and a 183 /// \c NodeNumTag tag then this function calls directly the member 184 184 /// function to query the cardinality of the node set. 185 185 template <typename Graph> … … 213 213 /// 214 214 /// This function counts the arcs in the graph. 215 /// The complexity of the function is O(e)but for some216 /// graph structures it is specialized to run in O(1).217 /// 218 /// If the graph contains a \earcNum() member function and a219 /// \ e EdgeNumTag tag then this function calls directly the member215 /// The complexity of the function is <em>O</em>(<em>m</em>), but for some 216 /// graph structures it is specialized to run in <em>O</em>(1). 217 /// 218 /// \note If the graph contains a \c arcNum() member function and a 219 /// \c ArcNumTag tag then this function calls directly the member 220 220 /// function to query the cardinality of the arc set. 221 221 template <typename Graph> … … 225 225 226 226 // Edge counting: 227 227 228 namespace _core_bits { 228 229 … … 248 249 /// 249 250 /// This function counts the edges in the graph. 250 /// The complexity of the function is O(m)but for some251 /// graph structures it is specialized to run in O(1).252 /// 253 /// If the graph contains a \eedgeNum() member function and a254 /// \ eEdgeNumTag tag then this function calls directly the member251 /// The complexity of the function is <em>O</em>(<em>m</em>), but for some 252 /// graph structures it is specialized to run in <em>O</em>(1). 253 /// 254 /// \note If the graph contains a \c edgeNum() member function and a 255 /// \c EdgeNumTag tag then this function calls directly the member 255 256 /// function to query the cardinality of the edge set. 256 257 template <typename Graph> … … 273 274 /// 274 275 /// This function counts the number of the outarcs from node \c n 275 /// in the graph .276 /// in the graph \c g. 276 277 template <typename Graph> 277 inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {278 return countNodeDegree<Graph, typename Graph::OutArcIt>( _g, _n);278 inline int countOutArcs(const Graph& g, const typename Graph::Node& n) { 279 return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n); 279 280 } 280 281 … … 282 283 /// 283 284 /// This function counts the number of the inarcs to node \c n 284 /// in the graph .285 /// in the graph \c g. 285 286 template <typename Graph> 286 inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {287 return countNodeDegree<Graph, typename Graph::InArcIt>( _g, _n);287 inline int countInArcs(const Graph& g, const typename Graph::Node& n) { 288 return countNodeDegree<Graph, typename Graph::InArcIt>(g, n); 288 289 } 289 290 … … 291 292 /// 292 293 /// This function counts the number of the incedges to node \c n 293 /// in the graph.294 /// in the undirected graph \c g. 294 295 template <typename Graph> 295 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {296 return countNodeDegree<Graph, typename Graph::IncEdgeIt>( _g, _n);296 inline int countIncEdges(const Graph& g, const typename Graph::Node& n) { 297 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n); 297 298 } 298 299 … … 308 309 309 310 template <typename Digraph, typename Item, typename RefMap, 310 typename ToMap, typename FromMap>311 typename FromMap, typename ToMap> 311 312 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> { 312 313 public: 313 314 314 MapCopy( ToMap& tmap, const FromMap&map)315 : _ tmap(tmap), _map(map) {}315 MapCopy(const FromMap& map, ToMap& tmap) 316 : _map(map), _tmap(tmap) {} 316 317 317 318 virtual void copy(const Digraph& digraph, const RefMap& refMap) { … … 323 324 324 325 private: 326 const FromMap& _map; 325 327 ToMap& _tmap; 326 const FromMap& _map;327 328 }; 328 329 … … 331 332 public: 332 333 333 ItemCopy( It& it, const Item& item) : _it(it), _item(item) {}334 ItemCopy(const Item& item, It& it) : _item(item), _it(it) {} 334 335 335 336 virtual void copy(const Digraph&, const RefMap& refMap) { … … 338 339 339 340 private: 341 Item _item; 340 342 It& _it; 341 Item _item;342 343 }; 343 344 … … 380 381 struct DigraphCopySelector { 381 382 template <typename From, typename NodeRefMap, typename ArcRefMap> 382 static void copy( Digraph &to, const From& from,383 static void copy(const From& from, Digraph &to, 383 384 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 384 385 for (typename From::NodeIt it(from); it != INVALID; ++it) { … … 398 399 { 399 400 template <typename From, typename NodeRefMap, typename ArcRefMap> 400 static void copy( Digraph &to, const From& from,401 static void copy(const From& from, Digraph &to, 401 402 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 402 403 to.build(from, nodeRefMap, arcRefMap); … … 407 408 struct GraphCopySelector { 408 409 template <typename From, typename NodeRefMap, typename EdgeRefMap> 409 static void copy( Graph &to, const From& from,410 static void copy(const From& from, Graph &to, 410 411 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 411 412 for (typename From::NodeIt it(from); it != INVALID; ++it) { … … 425 426 { 426 427 template <typename From, typename NodeRefMap, typename EdgeRefMap> 427 static void copy( Graph &to, const From& from,428 static void copy(const From& from, Graph &to, 428 429 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 429 430 to.build(from, nodeRefMap, edgeRefMap); … … 436 437 /// 437 438 /// Class to copy a digraph to another digraph (duplicate a digraph). The 438 /// simplest way of using it is through the \c copyDigraph() function.439 /// 440 /// This class not just make a copy of agraph, but it can create439 /// simplest way of using it is through the \c digraphCopy() function. 440 /// 441 /// This class not only make a copy of a digraph, but it can create 441 442 /// references and cross references between the nodes and arcs of 442 /// the two graphs, it can copy maps foruse with the newly created443 /// graph and copy nodes and arcs.444 /// 445 /// To make a copy from a graph, first an instance of DigraphCopy446 /// should be created, then the data belongs to the graph should443 /// the two digraphs, and it can copy maps to use with the newly created 444 /// digraph. 445 /// 446 /// To make a copy from a digraph, first an instance of DigraphCopy 447 /// should be created, then the data belongs to the digraph should 447 448 /// assigned to copy. In the end, the \c run() member should be 448 449 /// called. 449 450 /// 450 /// The next code copies a graph with several data:451 /// The next code copies a digraph with several data: 451 452 ///\code 452 /// DigraphCopy< NewGraph, OrigGraph> dc(new_graph, orig_graph);453 /// // create a referencefor the nodes453 /// DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph); 454 /// // Create references for the nodes 454 455 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); 455 /// dc.nodeRef(nr);456 /// // create a cross reference(inverse) for the arcs456 /// cg.nodeRef(nr); 457 /// // Create cross references (inverse) for the arcs 457 458 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph); 458 /// dc.arcCrossRef(acr);459 /// // copy an arc map459 /// cg.arcCrossRef(acr); 460 /// // Copy an arc map 460 461 /// OrigGraph::ArcMap<double> oamap(orig_graph); 461 462 /// NewGraph::ArcMap<double> namap(new_graph); 462 /// dc.arcMap(namap, oamap);463 /// // copy a node463 /// cg.arcMap(oamap, namap); 464 /// // Copy a node 464 465 /// OrigGraph::Node on; 465 466 /// NewGraph::Node nn; 466 /// dc.node(nn, on);467 /// // Execut ions of copy468 /// dc.run();467 /// cg.node(on, nn); 468 /// // Execute copying 469 /// cg.run(); 469 470 ///\endcode 470 template <typename To, typename From>471 template <typename From, typename To> 471 472 class DigraphCopy { 472 473 private: … … 483 484 typedef typename From::template ArcMap<TArc> ArcRefMap; 484 485 485 486 486 public: 487 487 488 489 /// \brief Constructor for the DigraphCopy. 490 /// 491 /// It copies the content of the \c _from digraph into the 492 /// \c _to digraph. 493 DigraphCopy(To& to, const From& from) 488 /// \brief Constructor of DigraphCopy. 489 /// 490 /// Constructor of DigraphCopy for copying the content of the 491 /// \c from digraph into the \c to digraph. 492 DigraphCopy(const From& from, To& to) 494 493 : _from(from), _to(to) {} 495 494 496 /// \brief Destructor of theDigraphCopy497 /// 498 /// Destructor of the DigraphCopy495 /// \brief Destructor of DigraphCopy 496 /// 497 /// Destructor of DigraphCopy. 499 498 ~DigraphCopy() { 500 499 for (int i = 0; i < int(_node_maps.size()); ++i) { … … 507 506 } 508 507 509 /// \brief Cop iesthe node references into the given map.510 /// 511 /// Copies the node references into the given map. The parameter512 /// should be a map, which key type is the Node type of the source513 /// graph, while the value type is the Node type of the514 /// destination graph.508 /// \brief Copy the node references into the given map. 509 /// 510 /// This function copies the node references into the given map. 511 /// The parameter should be a map, whose key type is the Node type of 512 /// the source digraph, while the value type is the Node type of the 513 /// destination digraph. 515 514 template <typename NodeRef> 516 515 DigraphCopy& nodeRef(NodeRef& map) { … … 520 519 } 521 520 522 /// \brief Cop iesthe node cross references into the given map.523 /// 524 /// Copies the node cross references (reverse references) into525 /// the given map. The parameter should be a map, whichkey type526 /// is the Node type of the destinationgraph, while the value type is527 /// the Node type of the sourcegraph.521 /// \brief Copy the node cross references into the given map. 522 /// 523 /// This function copies the node cross references (reverse references) 524 /// into the given map. The parameter should be a map, whose key type 525 /// is the Node type of the destination digraph, while the value type is 526 /// the Node type of the source digraph. 528 527 template <typename NodeCrossRef> 529 528 DigraphCopy& nodeCrossRef(NodeCrossRef& map) { … … 533 532 } 534 533 535 /// \brief Make copy of the given map. 536 /// 537 /// Makes copy of the given map for the newly created digraph. 538 /// The new map's key type is the destination graph's node type, 539 /// and the copied map's key type is the source graph's node type. 540 template <typename ToMap, typename FromMap> 541 DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { 534 /// \brief Make a copy of the given node map. 535 /// 536 /// This function makes a copy of the given node map for the newly 537 /// created digraph. 538 /// The key type of the new map \c tmap should be the Node type of the 539 /// destination digraph, and the key type of the original map \c map 540 /// should be the Node type of the source digraph. 541 template <typename FromMap, typename ToMap> 542 DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { 542 543 _node_maps.push_back(new _core_bits::MapCopy<From, Node, 543 NodeRefMap, ToMap, FromMap>(tmap,map));544 NodeRefMap, FromMap, ToMap>(map, tmap)); 544 545 return *this; 545 546 } … … 547 548 /// \brief Make a copy of the given node. 548 549 /// 549 /// Makea copy of the given node.550 DigraphCopy& node( TNode& tnode, const Node& snode) {550 /// This function makes a copy of the given node. 551 DigraphCopy& node(const Node& node, TNode& tnode) { 551 552 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, 552 NodeRefMap, TNode>(tnode, snode)); 553 return *this; 554 } 555 556 /// \brief Copies the arc references into the given map. 557 /// 558 /// Copies the arc references into the given map. 553 NodeRefMap, TNode>(node, tnode)); 554 return *this; 555 } 556 557 /// \brief Copy the arc references into the given map. 558 /// 559 /// This function copies the arc references into the given map. 560 /// The parameter should be a map, whose key type is the Arc type of 561 /// the source digraph, while the value type is the Arc type of the 562 /// destination digraph. 559 563 template <typename ArcRef> 560 564 DigraphCopy& arcRef(ArcRef& map) { … … 564 568 } 565 569 566 /// \brief Copies the arc cross references into the given map. 567 /// 568 /// Copies the arc cross references (reverse references) into 569 /// the given map. 570 /// \brief Copy the arc cross references into the given map. 571 /// 572 /// This function copies the arc cross references (reverse references) 573 /// into the given map. The parameter should be a map, whose key type 574 /// is the Arc type of the destination digraph, while the value type is 575 /// the Arc type of the source digraph. 570 576 template <typename ArcCrossRef> 571 577 DigraphCopy& arcCrossRef(ArcCrossRef& map) { … … 575 581 } 576 582 577 /// \brief Make copy of the given map. 578 /// 579 /// Makes copy of the given map for the newly created digraph. 580 /// The new map's key type is the to digraph's arc type, 581 /// and the copied map's key type is the from digraph's arc 582 /// type. 583 template <typename ToMap, typename FromMap> 584 DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) { 583 /// \brief Make a copy of the given arc map. 584 /// 585 /// This function makes a copy of the given arc map for the newly 586 /// created digraph. 587 /// The key type of the new map \c tmap should be the Arc type of the 588 /// destination digraph, and the key type of the original map \c map 589 /// should be the Arc type of the source digraph. 590 template <typename FromMap, typename ToMap> 591 DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) { 585 592 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, 586 ArcRefMap, ToMap, FromMap>(tmap,map));593 ArcRefMap, FromMap, ToMap>(map, tmap)); 587 594 return *this; 588 595 } … … 590 597 /// \brief Make a copy of the given arc. 591 598 /// 592 /// Makea copy of the given arc.593 DigraphCopy& arc( TArc& tarc, const Arc& sarc) {599 /// This function makes a copy of the given arc. 600 DigraphCopy& arc(const Arc& arc, TArc& tarc) { 594 601 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, 595 ArcRefMap, TArc>(tarc, sarc)); 596 return *this; 597 } 598 599 /// \brief Executes the copies. 600 /// 601 /// Executes the copies. 602 ArcRefMap, TArc>(arc, tarc)); 603 return *this; 604 } 605 606 /// \brief Execute copying. 607 /// 608 /// This function executes the copying of the digraph along with the 609 /// copying of the assigned data. 602 610 void run() { 603 611 NodeRefMap nodeRefMap(_from); 604 612 ArcRefMap arcRefMap(_from); 605 613 _core_bits::DigraphCopySelector<To>:: 606 copy(_ to, _from, nodeRefMap, arcRefMap);614 copy(_from, _to, nodeRefMap, arcRefMap); 607 615 for (int i = 0; i < int(_node_maps.size()); ++i) { 608 616 _node_maps[i]>copy(_from, nodeRefMap); … … 615 623 protected: 616 624 617 618 625 const From& _from; 619 626 To& _to; 620 627 621 628 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > 622 _node_maps;629 _node_maps; 623 630 624 631 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > 625 _arc_maps;632 _arc_maps; 626 633 627 634 }; … … 629 636 /// \brief Copy a digraph to another digraph. 630 637 /// 631 /// Copy a digraph to another digraph. The complete usage of the632 /// function is detailed in the DigraphCopy class, but a short633 /// example shows a basic work:638 /// This function copies a digraph to another digraph. 639 /// The complete usage of it is detailed in the DigraphCopy class, but 640 /// a short example shows a basic work: 634 641 ///\code 635 /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();642 /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run(); 636 643 ///\endcode 637 644 /// 638 645 /// After the copy the \c nr map will contain the mapping from the 639 646 /// nodes of the \c from digraph to the nodes of the \c to digraph and 640 /// \c ecr will contain the mapping from the arcs of the \c to digraph647 /// \c acr will contain the mapping from the arcs of the \c to digraph 641 648 /// to the arcs of the \c from digraph. 642 649 /// 643 650 /// \see DigraphCopy 644 template <typename To, typename From>645 DigraphCopy< To, From> copyDigraph(To& to, const From& from) {646 return DigraphCopy< To, From>(to, from);651 template <typename From, typename To> 652 DigraphCopy<From, To> digraphCopy(const From& from, To& to) { 653 return DigraphCopy<From, To>(from, to); 647 654 } 648 655 … … 650 657 /// 651 658 /// Class to copy a graph to another graph (duplicate a graph). The 652 /// simplest way of using it is through the \c copyGraph() function.653 /// 654 /// This class not justmake a copy of a graph, but it can create659 /// simplest way of using it is through the \c graphCopy() function. 660 /// 661 /// This class not only make a copy of a graph, but it can create 655 662 /// references and cross references between the nodes, edges and arcs of 656 /// the two graphs, it can copy maps for usewith the newly created657 /// graph and copy nodes, edges and arcs.663 /// the two graphs, and it can copy maps for using with the newly created 664 /// graph. 658 665 /// 659 666 /// To make a copy from a graph, first an instance of GraphCopy … … 664 671 /// The next code copies a graph with several data: 665 672 ///\code 666 /// GraphCopy< NewGraph, OrigGraph> dc(new_graph, orig_graph);667 /// // create a referencefor the nodes673 /// GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph); 674 /// // Create references for the nodes 668 675 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); 669 /// dc.nodeRef(nr);670 /// // create a cross reference(inverse) for the edges671 /// NewGraph::EdgeMap<OrigGraph:: Arc> ecr(new_graph);672 /// dc.edgeCrossRef(ecr);673 /// // copy an arcmap674 /// OrigGraph:: ArcMap<double> oamap(orig_graph);675 /// NewGraph:: ArcMap<double> namap(new_graph);676 /// dc.arcMap(namap, oamap);677 /// // copy a node676 /// cg.nodeRef(nr); 677 /// // Create cross references (inverse) for the edges 678 /// NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph); 679 /// cg.edgeCrossRef(ecr); 680 /// // Copy an edge map 681 /// OrigGraph::EdgeMap<double> oemap(orig_graph); 682 /// NewGraph::EdgeMap<double> nemap(new_graph); 683 /// cg.edgeMap(oemap, nemap); 684 /// // Copy a node 678 685 /// OrigGraph::Node on; 679 686 /// NewGraph::Node nn; 680 /// dc.node(nn, on);681 /// // Execut ions of copy682 /// dc.run();687 /// cg.node(on, nn); 688 /// // Execute copying 689 /// cg.run(); 683 690 ///\endcode 684 template <typename To, typename From>691 template <typename From, typename To> 685 692 class GraphCopy { 686 693 private: … … 701 708 702 709 struct ArcRefMap { 703 ArcRefMap(const To& to, const From& from,710 ArcRefMap(const From& from, const To& to, 704 711 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) 705 : _ to(to), _from(from),712 : _from(from), _to(to), 706 713 _edge_ref(edge_ref), _node_ref(node_ref) {} 707 714 … … 717 724 } 718 725 726 const From& _from; 719 727 const To& _to; 720 const From& _from;721 728 const EdgeRefMap& _edge_ref; 722 729 const NodeRefMap& _node_ref; 723 730 }; 724 731 725 726 732 public: 727 733 728 729 /// \brief Constructor for the GraphCopy. 730 /// 731 /// It copies the content of the \c _from graph into the 732 /// \c _to graph. 733 GraphCopy(To& to, const From& from) 734 /// \brief Constructor of GraphCopy. 735 /// 736 /// Constructor of GraphCopy for copying the content of the 737 /// \c from graph into the \c to graph. 738 GraphCopy(const From& from, To& to) 734 739 : _from(from), _to(to) {} 735 740 736 /// \brief Destructor of theGraphCopy737 /// 738 /// Destructor of the GraphCopy741 /// \brief Destructor of GraphCopy 742 /// 743 /// Destructor of GraphCopy. 739 744 ~GraphCopy() { 740 745 for (int i = 0; i < int(_node_maps.size()); ++i) { … … 747 752 delete _edge_maps[i]; 748 753 } 749 750 } 751 752 /// \brief Copies the node references into the given map. 753 /// 754 /// Copies the node references into the given map. 754 } 755 756 /// \brief Copy the node references into the given map. 757 /// 758 /// This function copies the node references into the given map. 759 /// The parameter should be a map, whose key type is the Node type of 760 /// the source graph, while the value type is the Node type of the 761 /// destination graph. 755 762 template <typename NodeRef> 756 763 GraphCopy& nodeRef(NodeRef& map) { … … 760 767 } 761 768 762 /// \brief Copies the node cross references into the given map. 763 /// 764 /// Copies the node cross references (reverse references) into 765 /// the given map. 769 /// \brief Copy the node cross references into the given map. 770 /// 771 /// This function copies the node cross references (reverse references) 772 /// into the given map. The parameter should be a map, whose key type 773 /// is the Node type of the destination graph, while the value type is 774 /// the Node type of the source graph. 766 775 template <typename NodeCrossRef> 767 776 GraphCopy& nodeCrossRef(NodeCrossRef& map) { … … 771 780 } 772 781 773 /// \brief Make copy of the given map. 774 /// 775 /// Makes copy of the given map for the newly created graph. 776 /// The new map's key type is the to graph's node type, 777 /// and the copied map's key type is the from graph's node 778 /// type. 779 template <typename ToMap, typename FromMap> 780 GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { 782 /// \brief Make a copy of the given node map. 783 /// 784 /// This function makes a copy of the given node map for the newly 785 /// created graph. 786 /// The key type of the new map \c tmap should be the Node type of the 787 /// destination graph, and the key type of the original map \c map 788 /// should be the Node type of the source graph. 789 template <typename FromMap, typename ToMap> 790 GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { 781 791 _node_maps.push_back(new _core_bits::MapCopy<From, Node, 782 NodeRefMap, ToMap, FromMap>(tmap,map));792 NodeRefMap, FromMap, ToMap>(map, tmap)); 783 793 return *this; 784 794 } … … 786 796 /// \brief Make a copy of the given node. 787 797 /// 788 /// Makea copy of the given node.789 GraphCopy& node( TNode& tnode, const Node& snode) {798 /// This function makes a copy of the given node. 799 GraphCopy& node(const Node& node, TNode& tnode) { 790 800 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, 791 NodeRefMap, TNode>(tnode, snode)); 792 return *this; 793 } 794 795 /// \brief Copies the arc references into the given map. 796 /// 797 /// Copies the arc references into the given map. 801 NodeRefMap, TNode>(node, tnode)); 802 return *this; 803 } 804 805 /// \brief Copy the arc references into the given map. 806 /// 807 /// This function copies the arc references into the given map. 808 /// The parameter should be a map, whose key type is the Arc type of 809 /// the source graph, while the value type is the Arc type of the 810 /// destination graph. 798 811 template <typename ArcRef> 799 812 GraphCopy& arcRef(ArcRef& map) { … … 803 816 } 804 817 805 /// \brief Copies the arc cross references into the given map. 806 /// 807 /// Copies the arc cross references (reverse references) into 808 /// the given map. 818 /// \brief Copy the arc cross references into the given map. 819 /// 820 /// This function copies the arc cross references (reverse references) 821 /// into the given map. The parameter should be a map, whose key type 822 /// is the Arc type of the destination graph, while the value type is 823 /// the Arc type of the source graph. 809 824 template <typename ArcCrossRef> 810 825 GraphCopy& arcCrossRef(ArcCrossRef& map) { … … 814 829 } 815 830 816 /// \brief Make copy of the given map. 817 /// 818 /// Makes copy of the given map for the newly created graph. 819 /// The new map's key type is the to graph's arc type, 820 /// and the copied map's key type is the from graph's arc 821 /// type. 822 template <typename ToMap, typename FromMap> 823 GraphCopy& arcMap(ToMap& tmap, const FromMap& map) { 831 /// \brief Make a copy of the given arc map. 832 /// 833 /// This function makes a copy of the given arc map for the newly 834 /// created graph. 835 /// The key type of the new map \c tmap should be the Arc type of the 836 /// destination graph, and the key type of the original map \c map 837 /// should be the Arc type of the source graph. 838 template <typename FromMap, typename ToMap> 839 GraphCopy& arcMap(const FromMap& map, ToMap& tmap) { 824 840 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, 825 ArcRefMap, ToMap, FromMap>(tmap,map));841 ArcRefMap, FromMap, ToMap>(map, tmap)); 826 842 return *this; 827 843 } … … 829 845 /// \brief Make a copy of the given arc. 830 846 /// 831 /// Makea copy of the given arc.832 GraphCopy& arc( TArc& tarc, const Arc& sarc) {847 /// This function makes a copy of the given arc. 848 GraphCopy& arc(const Arc& arc, TArc& tarc) { 833 849 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, 834 ArcRefMap, TArc>(tarc, sarc)); 835 return *this; 836 } 837 838 /// \brief Copies the edge references into the given map. 839 /// 840 /// Copies the edge references into the given map. 850 ArcRefMap, TArc>(arc, tarc)); 851 return *this; 852 } 853 854 /// \brief Copy the edge references into the given map. 855 /// 856 /// This function copies the edge references into the given map. 857 /// The parameter should be a map, whose key type is the Edge type of 858 /// the source graph, while the value type is the Edge type of the 859 /// destination graph. 841 860 template <typename EdgeRef> 842 861 GraphCopy& edgeRef(EdgeRef& map) { … … 846 865 } 847 866 848 /// \brief Copies the edge cross references into the given map. 849 /// 850 /// Copies the edge cross references (reverse 851 /// references) into the given map. 867 /// \brief Copy the edge cross references into the given map. 868 /// 869 /// This function copies the edge cross references (reverse references) 870 /// into the given map. The parameter should be a map, whose key type 871 /// is the Edge type of the destination graph, while the value type is 872 /// the Edge type of the source graph. 852 873 template <typename EdgeCrossRef> 853 874 GraphCopy& edgeCrossRef(EdgeCrossRef& map) { … … 857 878 } 858 879 859 /// \brief Make copy of the given map. 860 /// 861 /// Makes copy of the given map for the newly created graph. 862 /// The new map's key type is the to graph's edge type, 863 /// and the copied map's key type is the from graph's edge 864 /// type. 865 template <typename ToMap, typename FromMap> 866 GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) { 880 /// \brief Make a copy of the given edge map. 881 /// 882 /// This function makes a copy of the given edge map for the newly 883 /// created graph. 884 /// The key type of the new map \c tmap should be the Edge type of the 885 /// destination graph, and the key type of the original map \c map 886 /// should be the Edge type of the source graph. 887 template <typename FromMap, typename ToMap> 888 GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) { 867 889 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge, 868 EdgeRefMap, ToMap, FromMap>(tmap,map));890 EdgeRefMap, FromMap, ToMap>(map, tmap)); 869 891 return *this; 870 892 } … … 872 894 /// \brief Make a copy of the given edge. 873 895 /// 874 /// Makea copy of the given edge.875 GraphCopy& edge( TEdge& tedge, const Edge& sedge) {896 /// This function makes a copy of the given edge. 897 GraphCopy& edge(const Edge& edge, TEdge& tedge) { 876 898 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge, 877 EdgeRefMap, TEdge>(tedge, sedge)); 878 return *this; 879 } 880 881 /// \brief Executes the copies. 882 /// 883 /// Executes the copies. 899 EdgeRefMap, TEdge>(edge, tedge)); 900 return *this; 901 } 902 903 /// \brief Execute copying. 904 /// 905 /// This function executes the copying of the graph along with the 906 /// copying of the assigned data. 884 907 void run() { 885 908 NodeRefMap nodeRefMap(_from); 886 909 EdgeRefMap edgeRefMap(_from); 887 ArcRefMap arcRefMap(_ to, _from, edgeRefMap, nodeRefMap);910 ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap); 888 911 _core_bits::GraphCopySelector<To>:: 889 copy(_ to, _from, nodeRefMap, edgeRefMap);912 copy(_from, _to, nodeRefMap, edgeRefMap); 890 913 for (int i = 0; i < int(_node_maps.size()); ++i) { 891 914 _node_maps[i]>copy(_from, nodeRefMap); … … 905 928 906 929 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > 907 _node_maps;930 _node_maps; 908 931 909 932 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > 910 _arc_maps;933 _arc_maps; 911 934 912 935 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 913 _edge_maps;936 _edge_maps; 914 937 915 938 }; … … 917 940 /// \brief Copy a graph to another graph. 918 941 /// 919 /// Copy a graph to another graph. The complete usage of the920 /// function is detailed in the GraphCopy class, but a short921 /// example shows a basic work:942 /// This function copies a graph to another graph. 943 /// The complete usage of it is detailed in the GraphCopy class, 944 /// but a short example shows a basic work: 922 945 ///\code 923 /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();946 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run(); 924 947 ///\endcode 925 948 /// 926 949 /// After the copy the \c nr map will contain the mapping from the 927 950 /// nodes of the \c from graph to the nodes of the \c to graph and 928 /// \c ecr will contain the mapping from the arcs of the \c to graph929 /// to the arcs of the \c from graph.951 /// \c ecr will contain the mapping from the edges of the \c to graph 952 /// to the edges of the \c from graph. 930 953 /// 931 954 /// \see GraphCopy 932 template <typename To, typename From>933 GraphCopy< To, From>934 copyGraph(To& to, const From& from) {935 return GraphCopy< To, From>(to, from);955 template <typename From, typename To> 956 GraphCopy<From, To> 957 graphCopy(const From& from, To& to) { 958 return GraphCopy<From, To>(from, to); 936 959 } 937 960 … … 958 981 struct FindArcSelector< 959 982 Graph, 960 typename enable_if<typename Graph::Find EdgeTag, void>::type>983 typename enable_if<typename Graph::FindArcTag, void>::type> 961 984 { 962 985 typedef typename Graph::Node Node; … … 968 991 } 969 992 970 /// \brief Finds an arc between two nodes of a graph. 971 /// 972 /// Finds an arc from node \c u to node \c v in graph \c g. 993 /// \brief Find an arc between two nodes of a digraph. 994 /// 995 /// This function finds an arc from node \c u to node \c v in the 996 /// digraph \c g. 973 997 /// 974 998 /// If \c prev is \ref INVALID (this is the default value), then … … 979 1003 /// Thus you can iterate through each arc from \c u to \c v as it follows. 980 1004 ///\code 981 /// for(Arc e =findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {1005 /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) { 982 1006 /// ... 983 1007 /// } 984 1008 ///\endcode 985 1009 /// 986 /// \sa ArcLookUp987 /// \sa AllArcLookUp988 /// \sa DynArcLookUp1010 /// \note \ref ConArcIt provides iterator interface for the same 1011 /// functionality. 1012 /// 989 1013 ///\sa ConArcIt 1014 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp 990 1015 template <typename Graph> 991 1016 inline typename Graph::Arc … … 995 1020 } 996 1021 997 /// \brief Iterator for iterating on arcs connectedthe same nodes.998 /// 999 /// Iterator for iterating on arcs connectedthe same nodes. It is1000 /// higher level interface for thefindArc() function. You can1022 /// \brief Iterator for iterating on parallel arcs connecting the same nodes. 1023 /// 1024 /// Iterator for iterating on parallel arcs connecting the same nodes. It is 1025 /// a higher level interface for the \ref findArc() function. You can 1001 1026 /// use it the following way: 1002 1027 ///\code … … 1007 1032 /// 1008 1033 ///\sa findArc() 1009 ///\sa ArcLookUp 1010 ///\sa AllArcLookUp 1011 ///\sa DynArcLookUp 1034 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp 1012 1035 template <typename _Graph> 1013 1036 class ConArcIt : public _Graph::Arc { … … 1022 1045 /// \brief Constructor. 1023 1046 /// 1024 /// Construct a new ConArcIt iterating on the arcs which1025 /// connects the \c u and \c v node.1047 /// Construct a new ConArcIt iterating on the arcs that 1048 /// connects nodes \c u and \c v. 1026 1049 ConArcIt(const Graph& g, Node u, Node v) : _graph(g) { 1027 1050 Parent::operator=(findArc(_graph, u, v)); … … 1030 1053 /// \brief Constructor. 1031 1054 /// 1032 /// Construct a new ConArcIt which continues the iterating from 1033 /// the \c e arc. 1055 /// Construct a new ConArcIt that continues the iterating from arc \c a. 1034 1056 ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {} 1035 1057 … … 1092 1114 } 1093 1115 1094 /// \brief Find san edge between two nodes of a graph.1095 /// 1096 /// Finds an edge from node \c u to node \c v in graph \c g.1097 /// If thenode \c u and node \c v is equal then each loop edge1116 /// \brief Find an edge between two nodes of a graph. 1117 /// 1118 /// This function finds an edge from node \c u to node \c v in graph \c g. 1119 /// If node \c u and node \c v is equal then each loop edge 1098 1120 /// will be enumerated once. 1099 1121 /// 1100 1122 /// If \c prev is \ref INVALID (this is the default value), then 1101 /// it finds the first arc from \c u to \c v. Otherwise it looks for 1102 /// the next arc from \c u to \c v after \c prev. 1103 /// \return The found arc or \ref INVALID if there is no such an arc. 1104 /// 1105 /// Thus you can iterate through each arc from \c u to \c v as it follows. 1123 /// it finds the first edge from \c u to \c v. Otherwise it looks for 1124 /// the next edge from \c u to \c v after \c prev. 1125 /// \return The found edge or \ref INVALID if there is no such an edge. 1126 /// 1127 /// Thus you can iterate through each edge between \c u and \c v 1128 /// as it follows. 1106 1129 ///\code 1107 /// for(Edge e = findEdge(g,u,v); e != INVALID; 1108 /// e = findEdge(g,u,v,e)) { 1130 /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) { 1109 1131 /// ... 1110 1132 /// } 1111 1133 ///\endcode 1112 1134 /// 1135 /// \note \ref ConEdgeIt provides iterator interface for the same 1136 /// functionality. 1137 /// 1113 1138 ///\sa ConEdgeIt 1114 1115 1139 template <typename Graph> 1116 1140 inline typename Graph::Edge … … 1120 1144 } 1121 1145 1122 /// \brief Iterator for iterating on edges connectedthe same nodes.1123 /// 1124 /// Iterator for iterating on edges connected the same nodes. It is1125 /// higher level interface for the findEdge() function. You can1146 /// \brief Iterator for iterating on parallel edges connecting the same nodes. 1147 /// 1148 /// Iterator for iterating on parallel edges connecting the same nodes. 1149 /// It is a higher level interface for the findEdge() function. You can 1126 1150 /// use it the following way: 1127 1151 ///\code 1128 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {1152 /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) { 1129 1153 /// ... 1130 1154 /// } … … 1144 1168 /// \brief Constructor. 1145 1169 /// 1146 /// Construct a new ConEdgeIt iterating on the edges which1147 /// connects the \c u and \c v node.1170 /// Construct a new ConEdgeIt iterating on the edges that 1171 /// connects nodes \c u and \c v. 1148 1172 ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) { 1149 1173 Parent::operator=(findEdge(_graph, u, v)); … … 1152 1176 /// \brief Constructor. 1153 1177 /// 1154 /// Construct a new ConEdgeIt which continues the iterating from 1155 /// the \c e edge. 1178 /// Construct a new ConEdgeIt that continues iterating from edge \c e. 1156 1179 ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {} 1157 1180 … … 1169 1192 1170 1193 1171 ///Dynamic arc look 1194 ///Dynamic arc lookup between given endpoints. 1172 1195 1173 1196 ///Using this class, you can find an arc in a digraph from a given 1174 ///source to a given target in amortized time <em>O (log</em>d<em>)</em>,1197 ///source to a given target in amortized time <em>O</em>(log<em>d</em>), 1175 1198 ///where <em>d</em> is the outdegree of the source node. 1176 1199 /// … … 1178 1201 ///the \c operator() member. 1179 1202 /// 1180 /// See the \ref ArcLookUp and \ref AllArcLookUp classes if your1181 /// digraph is not changed so frequently.1182 /// 1183 ///This class uses a selfadjusting binary search tree, Sleator's1184 /// and Tarjan's Splay tree forguarantee the logarithmic amortized1185 ///time bound for arc look ups. This class also guarantees the1203 ///This is a dynamic data structure. Consider to use \ref ArcLookUp or 1204 ///\ref AllArcLookUp if your digraph is not changed so frequently. 1205 /// 1206 ///This class uses a selfadjusting binary search tree, the Splay tree 1207 ///of Sleator and Tarjan to guarantee the logarithmic amortized 1208 ///time bound for arc lookups. This class also guarantees the 1186 1209 ///optimal time bound in a constant factor for any distribution of 1187 1210 ///queries. … … 1508 1531 1509 1532 ///Find an arc between two nodes. 1510 ///\param s The source node 1511 ///\param t The target node 1533 ///\param s The source node. 1534 ///\param t The target node. 1512 1535 ///\param p The previous arc between \c s and \c t. It it is INVALID or 1513 1536 ///not given, the operator finds the first appropriate arc. … … 1520 1543 ///DynArcLookUp<ListDigraph> ae(g); 1521 1544 ///... 1522 ///int n =0;1523 ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;1545 ///int n = 0; 1546 ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++; 1524 1547 ///\endcode 1525 1548 /// 1526 ///Finding the arcs take at most <em>O (</em>log<em>d)</em>1549 ///Finding the arcs take at most <em>O</em>(log<em>d</em>) 1527 1550 ///amortized time, specifically, the time complexity of the lookups 1528 1551 ///is equal to the optimal search tree implementation for the … … 1530 1553 /// 1531 1554 ///\note This is a dynamic data structure, therefore the data 1532 ///structure is updated after each graph alteration. However,1533 ///th eoretically this data structure is faster than \cArcLookUp1534 /// or AllEdgeLookup, butit often provides worse performance than1555 ///structure is updated after each graph alteration. Thus although 1556 ///this data structure is theoretically faster than \ref ArcLookUp 1557 ///and \ref AllArcLookup, it often provides worse performance than 1535 1558 ///them. 1536 ///1537 1559 Arc operator()(Node s, Node t, Arc p = INVALID) const { 1538 1560 if (p == INVALID) { … … 1586 1608 }; 1587 1609 1588 ///Fast arc look 1610 ///Fast arc lookup between given endpoints. 1589 1611 1590 1612 ///Using this class, you can find an arc in a digraph from a given 1591 ///source to a given target in time <em>O (log d)</em>,1613 ///source to a given target in time <em>O</em>(log<em>d</em>), 1592 1614 ///where <em>d</em> is the outdegree of the source node. 1593 1615 /// … … 1595 1617 ///Use \ref AllArcLookUp for this purpose. 1596 1618 /// 1597 ///\warning This class is static, so you should refresh() (or at least1598 /// refresh(Node)) this data structure1599 /// whenever the digraph changes. This is a time consuming (superlinearly1600 /// proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).1619 ///\warning This class is static, so you should call refresh() (or at 1620 ///least refresh(Node)) to refresh this data structure whenever the 1621 ///digraph changes. This is a time consuming (superlinearly proportional 1622 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1601 1623 /// 1602 1624 ///\tparam G The type of the underlying digraph. … … 1647 1669 } 1648 1670 public: 1649 ///Refresh the data structure at a node.1671 ///Refresh the search data structure at a node. 1650 1672 1651 1673 ///Build up the search database of node \c n. 1652 1674 /// 1653 ///It runs in time <em>O (d</em>log<em>d)</em>, where <em>d</em> is1654 /// the number of the outgoing arcs of \c n.1675 ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> 1676 ///is the number of the outgoing arcs of \c n. 1655 1677 void refresh(Node n) 1656 1678 { … … 1668 1690 ///\ref refresh(Node) "refresh(n)" for each node \c n. 1669 1691 /// 1670 ///It runs in time <em>O (m</em>log<em>D)</em>, where <em>m</em> is1671 ///the number of the arcs of \c nand <em>D</em> is the maximum1692 ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is 1693 ///the number of the arcs in the digraph and <em>D</em> is the maximum 1672 1694 ///outdegree of the digraph. 1673 1674 1695 void refresh() 1675 1696 { … … 1679 1700 ///Find an arc between two nodes. 1680 1701 1681 ///Find an arc between two nodes in time <em>O (</em>log<em>d)</em>, where1682 /// 1683 ///\param s The source node 1684 ///\param t The target node 1702 ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>), where 1703 ///<em>d</em> is the number of outgoing arcs of \c s. 1704 ///\param s The source node. 1705 ///\param t The target node. 1685 1706 ///\return An arc from \c s to \c t if there exists, 1686 1707 ///\ref INVALID otherwise. … … 1688 1709 ///\warning If you change the digraph, refresh() must be called before using 1689 1710 ///this operator. If you change the outgoing arcs of 1690 ///a single node \c n, then 1691 ///\ref refresh(Node) "refresh(n)" is enough. 1692 /// 1711 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. 1693 1712 Arc operator()(Node s, Node t) const 1694 1713 { … … 1702 1721 }; 1703 1722 1704 ///Fast look 1723 ///Fast lookup of all arcs between given endpoints. 1705 1724 1706 1725 ///This class is the same as \ref ArcLookUp, with the addition 1707 ///that it makes it possible to find all arcs between given endpoints. 1708 /// 1709 ///\warning This class is static, so you should refresh() (or at least 1710 ///refresh(Node)) this data structure 1711 ///whenever the digraph changes. This is a time consuming (superlinearly 1712 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs). 1726 ///that it makes it possible to find all parallel arcs between given 1727 ///endpoints. 1728 /// 1729 ///\warning This class is static, so you should call refresh() (or at 1730 ///least refresh(Node)) to refresh this data structure whenever the 1731 ///digraph changes. This is a time consuming (superlinearly proportional 1732 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1713 1733 /// 1714 1734 ///\tparam G The type of the underlying digraph. … … 1734 1754 else { 1735 1755 next=refreshNext(_right[head],next); 1736 // _next[head]=next;1737 1756 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head)) 1738 1757 ? next : INVALID; … … 1759 1778 ///Build up the search database of node \c n. 1760 1779 /// 1761 ///It runs in time <em>O (d</em>log<em>d)</em>, where <em>d</em> is1780 ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is 1762 1781 ///the number of the outgoing arcs of \c n. 1763 1764 1782 void refresh(Node n) 1765 1783 { … … 1773 1791 ///\ref refresh(Node) "refresh(n)" for each node \c n. 1774 1792 /// 1775 ///It runs in time <em>O (m</em>log<em>D)</em>, where <em>m</em> is1776 ///the number of the arcs of \c nand <em>D</em> is the maximum1793 ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is 1794 ///the number of the arcs in the digraph and <em>D</em> is the maximum 1777 1795 ///outdegree of the digraph. 1778 1779 1796 void refresh() 1780 1797 { … … 1785 1802 1786 1803 ///Find an arc between two nodes. 1787 ///\param s The source node 1788 ///\param t The target node 1804 ///\param s The source node. 1805 ///\param t The target node. 1789 1806 ///\param prev The previous arc between \c s and \c t. It it is INVALID or 1790 1807 ///not given, the operator finds the first appropriate arc. … … 1797 1814 ///AllArcLookUp<ListDigraph> ae(g); 1798 1815 ///... 1799 ///int n =0;1800 ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;1816 ///int n = 0; 1817 ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++; 1801 1818 ///\endcode 1802 1819 /// 1803 ///Finding the first arc take <em>O (</em>log<em>d)</em>time, where1804 /// 1820 ///Finding the first arc take <em>O</em>(log<em>d</em>) time, where 1821 ///<em>d</em> is the number of outgoing arcs of \c s. Then, the 1805 1822 ///consecutive arcs are found in constant time. 1806 1823 /// 1807 1824 ///\warning If you change the digraph, refresh() must be called before using 1808 1825 ///this operator. If you change the outgoing arcs of 1809 ///a single node \c n, then 1810 ///\ref refresh(Node) "refresh(n)" is enough. 1826 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. 1811 1827 /// 1812 1828 #ifdef DOXYGEN
Note: See TracChangeset
for help on using the changeset viewer.