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