Changes in / [287:bb40b6db0a58:286:da414906fe21] in lemon-1.1
- Files:
-
- 18 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r287 r286 55 55 ///\param g is the digraph, to which we would like to define the 56 56 ///\ref PredMap. 57 ///\todo The digraph alone may be insufficient to initialize 57 58 static PredMap *createPredMap(const Digraph &g) 58 59 { … … 64 65 ///The type of the map that indicates which nodes are processed. 65 66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 67 ///By default it is a NullMap. 66 68 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 69 ///Instantiates a \ref ProcessedMap. … … 195 197 int _curr_dist; 196 198 197 //Creates the maps if necessary. 199 ///Creates the maps if necessary. 200 ///\todo Better memory allocation (instead of new). 198 201 void create_maps() 199 202 { … … 846 849 ///\param g is the digraph, to which we would like to define the 847 850 ///\ref PredMap. 851 ///\todo The digraph alone may be insufficient to initialize 848 852 static PredMap *createPredMap(const Digraph &g) 849 853 { … … 1367 1371 int _list_front, _list_back; 1368 1372 1369 //Creates the maps if necessary. 1373 ///Creates the maps if necessary. 1374 ///\todo Better memory allocation (instead of new). 1370 1375 void create_maps() { 1371 1376 if(!_reached) { -
lemon/bits/base_extender.h
r280 r256 106 106 /// Returns whether the given directed arc has the same orientation 107 107 /// as the corresponding edge. 108 /// 109 /// \todo reference to the corresponding point of the undirected digraph 110 /// concept. "What does the direction of an edge mean?" 108 111 static bool direction(const Arc &a) { return a.forward; } 109 112 -
lemon/bits/vector_map.h
r280 r263 43 43 /// the map. This map type uses the std::vector to store the values. 44 44 /// 45 /// \tparam _ Graph The graph this map is attached to.45 /// \tparam _Notifier The AlterationNotifier that will notify this map. 46 46 /// \tparam _Item The item type of the graph items. 47 47 /// \tparam _Value The value type of the map. 48 /// \todo Fix the doc: there is _Graph parameter instead of _Notifier. 48 49 template <typename _Graph, typename _Item, typename _Value> 49 50 class VectorMap -
lemon/concept_check.h
r285 r209 17 17 */ 18 18 19 // The contents of this file was inspired by the concept checking 20 // utility of the BOOST library (http://www.boost.org). 19 // This file contains a modified version of the concept checking 20 // utility from BOOST. 21 // See the appropriate copyright notice below. 22 23 // (C) Copyright Jeremy Siek 2000. 24 // Distributed under the Boost Software License, Version 1.0. (See 25 // accompanying file LICENSE_1_0.txt or copy at 26 // http://www.boost.org/LICENSE_1_0.txt) 27 // 28 // Revision History: 29 // 05 May 2001: Workarounds for HP aCC from Thomas Matelich. (Jeremy Siek) 30 // 02 April 2001: Removed limits header altogether. (Jeremy Siek) 31 // 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock) 32 // 33 34 // See http://www.boost.org/libs/concept_check for documentation. 21 35 22 36 ///\file 23 37 ///\brief Basic utilities for concept checking. 24 38 /// 39 ///\todo Are we still using BOOST concept checking utility? 40 ///Is the BOOST copyright notice necessary? 25 41 26 42 #ifndef LEMON_CONCEPT_CHECK_H -
lemon/concepts/path.h
r281 r278 21 21 ///\brief Classes for representing paths in digraphs. 22 22 /// 23 ///\todo Iterators have obsolete style 23 24 24 25 #ifndef LEMON_CONCEPT_PATH_H -
lemon/core.h
r282 r233 59 59 /// @{ 60 60 61 ///Create convenienttypedefs for the digraph types and iterators62 63 ///This \c \#define creates convenien t type definitions for the following64 /// typesof \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,61 ///Creates convenience typedefs for the digraph types and iterators 62 63 ///This \c \#define creates convenience typedefs for the following types 64 ///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 convenienttypedefs for the digraph types and iterators83 typedef Digraph::ArcMap<double> DoubleArcMap 84 85 ///Creates convenience 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 convenienttypedefs for the graph types and iterators106 107 ///This \c \#define creates the same convenien t type definitions as defined103 typedef typename Digraph::template ArcMap<double> DoubleArcMap 104 105 ///Creates convenience typedefs for the graph types and iterators 106 107 ///This \c \#define creates the same convenience typedefs 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_ GRAPH_TYPEDEFS()113 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_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 convenienttypedefs for the graph types and iterators122 typedef Graph::EdgeMap<double> DoubleEdgeMap 123 124 ///Creates convenience 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 agraph.140 /// 141 /// This function counts the items (nodes, arcs etc .) in agraph.142 /// The complexity of the function is linearbecause137 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap 138 139 /// \brief Function to count the items in the graph. 140 /// 141 /// This function counts the items (nodes, arcs etc) in the graph. 142 /// The complexity of the function is O(n) 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 <em>O</em>(<em>n</em>),but for some180 /// graph structures it is specialized to run in <em>O</em>(1).181 /// 182 /// \note If the graph contains a \cnodeNum() member function and a183 /// \ cNodeNumTag tag then this function calls directly the member179 /// The complexity of the function is O(n) but for some 180 /// graph structures it is specialized to run in O(1). 181 /// 182 /// If the graph contains a \e nodeNum() member function and a 183 /// \e 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 <em>O</em>(<em>m</em>),but for some216 /// graph structures it is specialized to run in <em>O</em>(1).217 /// 218 /// \note If the graph contains a \carcNum() member function and a219 /// \ c ArcNumTag tag then this function calls directly the member215 /// The complexity of the function is O(e) but for some 216 /// graph structures it is specialized to run in O(1). 217 /// 218 /// If the graph contains a \e arcNum() member function and a 219 /// \e EdgeNumTag 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 228 227 namespace _core_bits { 229 228 … … 249 248 /// 250 249 /// This function counts the edges in the graph. 251 /// The complexity of the function is <em>O</em>(<em>m</em>),but for some252 /// graph structures it is specialized to run in <em>O</em>(1).253 /// 254 /// \note If the graph contains a \cedgeNum() member function and a255 /// \ cEdgeNumTag tag then this function calls directly the member250 /// The complexity of the function is O(m) but for some 251 /// graph structures it is specialized to run in O(1). 252 /// 253 /// If the graph contains a \e edgeNum() member function and a 254 /// \e EdgeNumTag tag then this function calls directly the member 256 255 /// function to query the cardinality of the edge set. 257 256 template <typename Graph> … … 274 273 /// 275 274 /// This function counts the number of the out-arcs from node \c n 276 /// in the graph \c g.275 /// in the graph. 277 276 template <typename Graph> 278 inline int countOutArcs(const Graph& g, const typename Graph::Node&n) {279 return countNodeDegree<Graph, typename Graph::OutArcIt>( g,n);277 inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) { 278 return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n); 280 279 } 281 280 … … 283 282 /// 284 283 /// This function counts the number of the in-arcs to node \c n 285 /// in the graph \c g.284 /// in the graph. 286 285 template <typename Graph> 287 inline int countInArcs(const Graph& g, const typename Graph::Node&n) {288 return countNodeDegree<Graph, typename Graph::InArcIt>( g,n);286 inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) { 287 return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n); 289 288 } 290 289 … … 292 291 /// 293 292 /// This function counts the number of the inc-edges to node \c n 294 /// in the undirected graph \c g.293 /// in the graph. 295 294 template <typename Graph> 296 inline int countIncEdges(const Graph& g, const typename Graph::Node&n) {297 return countNodeDegree<Graph, typename Graph::IncEdgeIt>( g,n);295 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { 296 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n); 298 297 } 299 298 … … 309 308 310 309 template <typename Digraph, typename Item, typename RefMap, 311 typename FromMap, typename ToMap>310 typename ToMap, typename FromMap> 312 311 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> { 313 312 public: 314 313 315 MapCopy( const FromMap& map, ToMap& tmap)316 : _ map(map), _tmap(tmap) {}314 MapCopy(ToMap& tmap, const FromMap& map) 315 : _tmap(tmap), _map(map) {} 317 316 318 317 virtual void copy(const Digraph& digraph, const RefMap& refMap) { … … 324 323 325 324 private: 325 ToMap& _tmap; 326 326 const FromMap& _map; 327 ToMap& _tmap;328 327 }; 329 328 … … 332 331 public: 333 332 334 ItemCopy( const Item& item, It& it) : _item(item), _it(it) {}333 ItemCopy(It& it, const Item& item) : _it(it), _item(item) {} 335 334 336 335 virtual void copy(const Digraph&, const RefMap& refMap) { … … 339 338 340 339 private: 340 It& _it; 341 341 Item _item; 342 It& _it;343 342 }; 344 343 … … 381 380 struct DigraphCopySelector { 382 381 template <typename From, typename NodeRefMap, typename ArcRefMap> 383 static void copy( const From& from, Digraph &to,382 static void copy(Digraph &to, const From& from, 384 383 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 385 384 for (typename From::NodeIt it(from); it != INVALID; ++it) { … … 399 398 { 400 399 template <typename From, typename NodeRefMap, typename ArcRefMap> 401 static void copy( const From& from, Digraph &to,400 static void copy(Digraph &to, const From& from, 402 401 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 403 402 to.build(from, nodeRefMap, arcRefMap); … … 408 407 struct GraphCopySelector { 409 408 template <typename From, typename NodeRefMap, typename EdgeRefMap> 410 static void copy( const From& from, Graph &to,409 static void copy(Graph &to, const From& from, 411 410 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 412 411 for (typename From::NodeIt it(from); it != INVALID; ++it) { … … 426 425 { 427 426 template <typename From, typename NodeRefMap, typename EdgeRefMap> 428 static void copy( const From& from, Graph &to,427 static void copy(Graph &to, const From& from, 429 428 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 430 429 to.build(from, nodeRefMap, edgeRefMap); … … 437 436 /// 438 437 /// Class to copy a digraph to another digraph (duplicate a digraph). The 439 /// 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 create438 /// simplest way of using it is through the \c copyDigraph() function. 439 /// 440 /// This class not just make a copy of a graph, but it can create 442 441 /// references and cross references between the nodes and arcs of 443 /// the two digraphs, and it can copy maps touse with the newly created444 /// digraph.445 /// 446 /// To make a copy from a digraph, first an instance of DigraphCopy447 /// should be created, then the data belongs to the digraph should442 /// the two graphs, it can copy maps for use with the newly created 443 /// graph and copy nodes and arcs. 444 /// 445 /// To make a copy from a graph, first an instance of DigraphCopy 446 /// should be created, then the data belongs to the graph should 448 447 /// assigned to copy. In the end, the \c run() member should be 449 448 /// called. 450 449 /// 451 /// The next code copies a digraph with several data:450 /// The next code copies a graph with several data: 452 451 ///\code 453 /// DigraphCopy< OrigGraph, NewGraph> cg(orig_graph, new_graph);454 /// // Create referencesfor the nodes452 /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); 453 /// // create a reference for the nodes 455 454 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); 456 /// cg.nodeRef(nr);457 /// // Create cross references(inverse) for the arcs455 /// dc.nodeRef(nr); 456 /// // create a cross reference (inverse) for the arcs 458 457 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph); 459 /// cg.arcCrossRef(acr);460 /// // Copy an arc map458 /// dc.arcCrossRef(acr); 459 /// // copy an arc map 461 460 /// OrigGraph::ArcMap<double> oamap(orig_graph); 462 461 /// NewGraph::ArcMap<double> namap(new_graph); 463 /// cg.arcMap(oamap, namap);464 /// // Copy a node462 /// dc.arcMap(namap, oamap); 463 /// // copy a node 465 464 /// OrigGraph::Node on; 466 465 /// NewGraph::Node nn; 467 /// cg.node(on, nn);468 /// // Execut e copying469 /// cg.run();466 /// dc.node(nn, on); 467 /// // Executions of copy 468 /// dc.run(); 470 469 ///\endcode 471 template <typename From, typename To>470 template <typename To, typename From> 472 471 class DigraphCopy { 473 472 private: … … 484 483 typedef typename From::template ArcMap<TArc> ArcRefMap; 485 484 485 486 486 public: 487 487 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) 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) 493 494 : _from(from), _to(to) {} 494 495 495 /// \brief Destructor of DigraphCopy496 /// 497 /// Destructor of DigraphCopy.496 /// \brief Destructor of the DigraphCopy 497 /// 498 /// Destructor of the DigraphCopy 498 499 ~DigraphCopy() { 499 500 for (int i = 0; i < int(_node_maps.size()); ++i) { … … 506 507 } 507 508 508 /// \brief Cop ythe 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 of512 /// the source digraph, while the value type is the Node type of the513 /// destination digraph.509 /// \brief Copies the node references into the given map. 510 /// 511 /// Copies the node references into the given map. The parameter 512 /// should be a map, which key type is the Node type of the source 513 /// graph, while the value type is the Node type of the 514 /// destination graph. 514 515 template <typename NodeRef> 515 516 DigraphCopy& nodeRef(NodeRef& map) { … … 519 520 } 520 521 521 /// \brief Cop ythe 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, whosekey type525 /// is the Node type of the destination digraph, while the value type is526 /// the Node type of the source digraph.522 /// \brief Copies the node cross references into the given map. 523 /// 524 /// Copies the node cross references (reverse references) into 525 /// the given map. The parameter should be a map, which key type 526 /// is the Node type of the destination graph, while the value type is 527 /// the Node type of the source graph. 527 528 template <typename NodeCrossRef> 528 529 DigraphCopy& nodeCrossRef(NodeCrossRef& map) { … … 532 533 } 533 534 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) { 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) { 543 542 _node_maps.push_back(new _core_bits::MapCopy<From, Node, 544 NodeRefMap, FromMap, ToMap>(map, tmap));543 NodeRefMap, ToMap, FromMap>(tmap, map)); 545 544 return *this; 546 545 } … … 548 547 /// \brief Make a copy of the given node. 549 548 /// 550 /// This function makesa copy of the given node.551 DigraphCopy& node( const Node& node, TNode& tnode) {549 /// Make a copy of the given node. 550 DigraphCopy& node(TNode& tnode, const Node& snode) { 552 551 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, 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. 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. 563 559 template <typename ArcRef> 564 560 DigraphCopy& arcRef(ArcRef& map) { … … 568 564 } 569 565 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. 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. 576 570 template <typename ArcCrossRef> 577 571 DigraphCopy& arcCrossRef(ArcCrossRef& map) { … … 581 575 } 582 576 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) { 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) { 592 585 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, 593 ArcRefMap, FromMap, ToMap>(map, tmap));586 ArcRefMap, ToMap, FromMap>(tmap, map)); 594 587 return *this; 595 588 } … … 597 590 /// \brief Make a copy of the given arc. 598 591 /// 599 /// This function makesa copy of the given arc.600 DigraphCopy& arc( const Arc& arc, TArc& tarc) {592 /// Make a copy of the given arc. 593 DigraphCopy& arc(TArc& tarc, const Arc& sarc) { 601 594 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, 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. 595 ArcRefMap, TArc>(tarc, sarc)); 596 return *this; 597 } 598 599 /// \brief Executes the copies. 600 /// 601 /// Executes the copies. 610 602 void run() { 611 603 NodeRefMap nodeRefMap(_from); 612 604 ArcRefMap arcRefMap(_from); 613 605 _core_bits::DigraphCopySelector<To>:: 614 copy(_ from, _to, nodeRefMap, arcRefMap);606 copy(_to, _from, nodeRefMap, arcRefMap); 615 607 for (int i = 0; i < int(_node_maps.size()); ++i) { 616 608 _node_maps[i]->copy(_from, nodeRefMap); … … 623 615 protected: 624 616 617 625 618 const From& _from; 626 619 To& _to; 627 620 628 621 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > 629 622 _node_maps; 630 623 631 624 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > 632 625 _arc_maps; 633 626 634 627 }; … … 636 629 /// \brief Copy a digraph to another digraph. 637 630 /// 638 /// This function copies a digraph to another digraph.639 /// The complete usage of it is detailed in the DigraphCopy class, but640 /// a shortexample shows a basic work:631 /// Copy a digraph to another digraph. The complete usage of the 632 /// function is detailed in the DigraphCopy class, but a short 633 /// example shows a basic work: 641 634 ///\code 642 /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();635 /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); 643 636 ///\endcode 644 637 /// 645 638 /// After the copy the \c nr map will contain the mapping from the 646 639 /// nodes of the \c from digraph to the nodes of the \c to digraph and 647 /// \c acr will contain the mapping from the arcs of the \c to digraph640 /// \c ecr will contain the mapping from the arcs of the \c to digraph 648 641 /// to the arcs of the \c from digraph. 649 642 /// 650 643 /// \see DigraphCopy 651 template <typename From, typename To>652 DigraphCopy< From, To> digraphCopy(const From& from, To& to) {653 return DigraphCopy< From, To>(from, to);644 template <typename To, typename From> 645 DigraphCopy<To, From> copyDigraph(To& to, const From& from) { 646 return DigraphCopy<To, From>(to, from); 654 647 } 655 648 … … 657 650 /// 658 651 /// Class to copy a graph to another graph (duplicate a graph). The 659 /// simplest way of using it is through the \c graphCopy() function.660 /// 661 /// This class not onlymake a copy of a graph, but it can create652 /// simplest way of using it is through the \c copyGraph() function. 653 /// 654 /// This class not just make a copy of a graph, but it can create 662 655 /// references and cross references between the nodes, edges and arcs of 663 /// the two graphs, and it can copy maps for usingwith the newly created664 /// graph .656 /// the two graphs, it can copy maps for use with the newly created 657 /// graph and copy nodes, edges and arcs. 665 658 /// 666 659 /// To make a copy from a graph, first an instance of GraphCopy … … 671 664 /// The next code copies a graph with several data: 672 665 ///\code 673 /// GraphCopy< OrigGraph, NewGraph> cg(orig_graph, new_graph);674 /// // Create referencesfor the nodes666 /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); 667 /// // create a reference for the nodes 675 668 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); 676 /// cg.nodeRef(nr);677 /// // Create cross references(inverse) for the edges678 /// NewGraph::EdgeMap<OrigGraph:: Edge> ecr(new_graph);679 /// cg.edgeCrossRef(ecr);680 /// // Copy an edgemap681 /// OrigGraph:: EdgeMap<double> oemap(orig_graph);682 /// NewGraph:: EdgeMap<double> nemap(new_graph);683 /// cg.edgeMap(oemap, nemap);684 /// // Copy a node669 /// dc.nodeRef(nr); 670 /// // create a cross reference (inverse) for the edges 671 /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph); 672 /// dc.edgeCrossRef(ecr); 673 /// // copy an arc map 674 /// OrigGraph::ArcMap<double> oamap(orig_graph); 675 /// NewGraph::ArcMap<double> namap(new_graph); 676 /// dc.arcMap(namap, oamap); 677 /// // copy a node 685 678 /// OrigGraph::Node on; 686 679 /// NewGraph::Node nn; 687 /// cg.node(on, nn);688 /// // Execut e copying689 /// cg.run();680 /// dc.node(nn, on); 681 /// // Executions of copy 682 /// dc.run(); 690 683 ///\endcode 691 template <typename From, typename To>684 template <typename To, typename From> 692 685 class GraphCopy { 693 686 private: … … 708 701 709 702 struct ArcRefMap { 710 ArcRefMap(const From& from, const To& to,703 ArcRefMap(const To& to, const From& from, 711 704 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) 712 : _ from(from), _to(to),705 : _to(to), _from(from), 713 706 _edge_ref(edge_ref), _node_ref(node_ref) {} 714 707 … … 724 717 } 725 718 719 const To& _to; 726 720 const From& _from; 727 const To& _to;728 721 const EdgeRefMap& _edge_ref; 729 722 const NodeRefMap& _node_ref; 730 723 }; 731 724 725 732 726 public: 733 727 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) 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) 739 734 : _from(from), _to(to) {} 740 735 741 /// \brief Destructor of GraphCopy742 /// 743 /// Destructor of GraphCopy.736 /// \brief Destructor of the GraphCopy 737 /// 738 /// Destructor of the GraphCopy 744 739 ~GraphCopy() { 745 740 for (int i = 0; i < int(_node_maps.size()); ++i) { … … 752 747 delete _edge_maps[i]; 753 748 } 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. 749 750 } 751 752 /// \brief Copies the node references into the given map. 753 /// 754 /// Copies the node references into the given map. 762 755 template <typename NodeRef> 763 756 GraphCopy& nodeRef(NodeRef& map) { … … 767 760 } 768 761 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. 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. 775 766 template <typename NodeCrossRef> 776 767 GraphCopy& nodeCrossRef(NodeCrossRef& map) { … … 780 771 } 781 772 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) { 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) { 791 781 _node_maps.push_back(new _core_bits::MapCopy<From, Node, 792 NodeRefMap, FromMap, ToMap>(map, tmap));782 NodeRefMap, ToMap, FromMap>(tmap, map)); 793 783 return *this; 794 784 } … … 796 786 /// \brief Make a copy of the given node. 797 787 /// 798 /// This function makesa copy of the given node.799 GraphCopy& node( const Node& node, TNode& tnode) {788 /// Make a copy of the given node. 789 GraphCopy& node(TNode& tnode, const Node& snode) { 800 790 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, 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. 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. 811 798 template <typename ArcRef> 812 799 GraphCopy& arcRef(ArcRef& map) { … … 816 803 } 817 804 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. 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. 824 809 template <typename ArcCrossRef> 825 810 GraphCopy& arcCrossRef(ArcCrossRef& map) { … … 829 814 } 830 815 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) { 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) { 840 824 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, 841 ArcRefMap, FromMap, ToMap>(map, tmap));825 ArcRefMap, ToMap, FromMap>(tmap, map)); 842 826 return *this; 843 827 } … … 845 829 /// \brief Make a copy of the given arc. 846 830 /// 847 /// This function makesa copy of the given arc.848 GraphCopy& arc( const Arc& arc, TArc& tarc) {831 /// Make a copy of the given arc. 832 GraphCopy& arc(TArc& tarc, const Arc& sarc) { 849 833 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, 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. 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. 860 841 template <typename EdgeRef> 861 842 GraphCopy& edgeRef(EdgeRef& map) { … … 865 846 } 866 847 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. 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. 873 852 template <typename EdgeCrossRef> 874 853 GraphCopy& edgeCrossRef(EdgeCrossRef& map) { … … 878 857 } 879 858 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) { 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) { 889 867 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge, 890 EdgeRefMap, FromMap, ToMap>(map, tmap));868 EdgeRefMap, ToMap, FromMap>(tmap, map)); 891 869 return *this; 892 870 } … … 894 872 /// \brief Make a copy of the given edge. 895 873 /// 896 /// This function makesa copy of the given edge.897 GraphCopy& edge( const Edge& edge, TEdge& tedge) {874 /// Make a copy of the given edge. 875 GraphCopy& edge(TEdge& tedge, const Edge& sedge) { 898 876 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge, 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. 877 EdgeRefMap, TEdge>(tedge, sedge)); 878 return *this; 879 } 880 881 /// \brief Executes the copies. 882 /// 883 /// Executes the copies. 907 884 void run() { 908 885 NodeRefMap nodeRefMap(_from); 909 886 EdgeRefMap edgeRefMap(_from); 910 ArcRefMap arcRefMap(_ from, _to, edgeRefMap, nodeRefMap);887 ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap); 911 888 _core_bits::GraphCopySelector<To>:: 912 copy(_ from, _to, nodeRefMap, edgeRefMap);889 copy(_to, _from, nodeRefMap, edgeRefMap); 913 890 for (int i = 0; i < int(_node_maps.size()); ++i) { 914 891 _node_maps[i]->copy(_from, nodeRefMap); … … 928 905 929 906 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > 930 907 _node_maps; 931 908 932 909 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > 933 910 _arc_maps; 934 911 935 912 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 936 913 _edge_maps; 937 914 938 915 }; … … 940 917 /// \brief Copy a graph to another graph. 941 918 /// 942 /// This function copies a graph to another graph.943 /// The complete usage of it is detailed in the GraphCopy class,944 /// but a shortexample shows a basic work:919 /// Copy a graph to another graph. The complete usage of the 920 /// function is detailed in the GraphCopy class, but a short 921 /// example shows a basic work: 945 922 ///\code 946 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();923 /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); 947 924 ///\endcode 948 925 /// 949 926 /// After the copy the \c nr map will contain the mapping from the 950 927 /// nodes of the \c from graph to the nodes of the \c to graph and 951 /// \c ecr will contain the mapping from the edges of the \c to graph952 /// to the edges of the \c from graph.928 /// \c ecr will contain the mapping from the arcs of the \c to graph 929 /// to the arcs of the \c from graph. 953 930 /// 954 931 /// \see GraphCopy 955 template <typename From, typename To>956 GraphCopy< From, To>957 graphCopy(const From& from, To& to) {958 return GraphCopy< From, To>(from, to);932 template <typename To, typename From> 933 GraphCopy<To, From> 934 copyGraph(To& to, const From& from) { 935 return GraphCopy<To, From>(to, from); 959 936 } 960 937 … … 981 958 struct FindArcSelector< 982 959 Graph, 983 typename enable_if<typename Graph::Find ArcTag, void>::type>960 typename enable_if<typename Graph::FindEdgeTag, void>::type> 984 961 { 985 962 typedef typename Graph::Node Node; … … 991 968 } 992 969 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. 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. 997 973 /// 998 974 /// If \c prev is \ref INVALID (this is the default value), then … … 1003 979 /// Thus you can iterate through each arc from \c u to \c v as it follows. 1004 980 ///\code 1005 /// for(Arc e = findArc(g,u,v); e != INVALID; e =findArc(g,u,v,e)) {981 /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) { 1006 982 /// ... 1007 983 /// } 1008 984 ///\endcode 1009 985 /// 1010 /// \note \ref ConArcIt provides iterator interface for the same1011 /// functionality.1012 /// 986 ///\sa ArcLookUp 987 ///\sa AllArcLookUp 988 ///\sa DynArcLookUp 1013 989 ///\sa ConArcIt 1014 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp1015 990 template <typename Graph> 1016 991 inline typename Graph::Arc … … 1020 995 } 1021 996 1022 /// \brief Iterator for iterating on parallel arcs connectingthe same nodes.1023 /// 1024 /// Iterator for iterating on parallel arcs connectingthe same nodes. It is1025 /// a higher level interface for the \reffindArc() function. You can997 /// \brief Iterator for iterating on arcs connected the same nodes. 998 /// 999 /// Iterator for iterating on arcs connected the same nodes. It is 1000 /// higher level interface for the findArc() function. You can 1026 1001 /// use it the following way: 1027 1002 ///\code … … 1032 1007 /// 1033 1008 ///\sa findArc() 1034 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp 1009 ///\sa ArcLookUp 1010 ///\sa AllArcLookUp 1011 ///\sa DynArcLookUp 1035 1012 template <typename _Graph> 1036 1013 class ConArcIt : public _Graph::Arc { … … 1045 1022 /// \brief Constructor. 1046 1023 /// 1047 /// Construct a new ConArcIt iterating on the arcs that1048 /// connects nodes \c u and \c v.1024 /// Construct a new ConArcIt iterating on the arcs which 1025 /// connects the \c u and \c v node. 1049 1026 ConArcIt(const Graph& g, Node u, Node v) : _graph(g) { 1050 1027 Parent::operator=(findArc(_graph, u, v)); … … 1053 1030 /// \brief Constructor. 1054 1031 /// 1055 /// Construct a new ConArcIt that continues the iterating from arc \c a. 1032 /// Construct a new ConArcIt which continues the iterating from 1033 /// the \c e arc. 1056 1034 ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {} 1057 1035 … … 1114 1092 } 1115 1093 1116 /// \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 edge1094 /// \brief Finds an 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 the node \c u and node \c v is equal then each loop edge 1120 1098 /// will be enumerated once. 1121 1099 /// 1122 1100 /// If \c prev is \ref INVALID (this is the default value), then 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. 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. 1129 1106 ///\code 1130 /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) { 1107 /// for(Edge e = findEdge(g,u,v); e != INVALID; 1108 /// e = findEdge(g,u,v,e)) { 1131 1109 /// ... 1132 1110 /// } 1133 1111 ///\endcode 1134 1112 /// 1135 /// \note \ref ConEdgeIt provides iterator interface for the same1136 /// functionality.1137 ///1138 1113 ///\sa ConEdgeIt 1114 1139 1115 template <typename Graph> 1140 1116 inline typename Graph::Edge … … 1144 1120 } 1145 1121 1146 /// \brief Iterator for iterating on parallel edges connectingthe same nodes.1147 /// 1148 /// Iterator for iterating on parallel edges connecting the same nodes.1149 /// It is ahigher level interface for the findEdge() function. You can1122 /// \brief Iterator for iterating on edges connected the same nodes. 1123 /// 1124 /// Iterator for iterating on edges connected the same nodes. It is 1125 /// higher level interface for the findEdge() function. You can 1150 1126 /// use it the following way: 1151 1127 ///\code 1152 /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {1128 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) { 1153 1129 /// ... 1154 1130 /// } … … 1168 1144 /// \brief Constructor. 1169 1145 /// 1170 /// Construct a new ConEdgeIt iterating on the edges that1171 /// connects nodes \c u and \c v.1146 /// Construct a new ConEdgeIt iterating on the edges which 1147 /// connects the \c u and \c v node. 1172 1148 ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) { 1173 1149 Parent::operator=(findEdge(_graph, u, v)); … … 1176 1152 /// \brief Constructor. 1177 1153 /// 1178 /// Construct a new ConEdgeIt that continues iterating from edge \c e. 1154 /// Construct a new ConEdgeIt which continues the iterating from 1155 /// the \c e edge. 1179 1156 ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {} 1180 1157 … … 1192 1169 1193 1170 1194 ///Dynamic arc look -up between given endpoints.1171 ///Dynamic arc look up between given endpoints. 1195 1172 1196 1173 ///Using this class, you can find an arc in a digraph from a given 1197 ///source to a given target in amortized time <em>O </em>(log<em>d</em>),1174 ///source to a given target in amortized time <em>O(log</em>d<em>)</em>, 1198 1175 ///where <em>d</em> is the out-degree of the source node. 1199 1176 /// … … 1201 1178 ///the \c operator() member. 1202 1179 /// 1203 /// This is a dynamic data structure. Consider to use \ref ArcLookUp or1204 /// \ref AllArcLookUp if yourdigraph is not changed so frequently.1205 /// 1206 ///This class uses a self-adjusting binary search tree, the Splay tree1207 /// of Sleator and Tarjan toguarantee the logarithmic amortized1208 ///time bound for arc look -ups. This class also guarantees the1180 ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your 1181 ///digraph is not changed so frequently. 1182 /// 1183 ///This class uses a self-adjusting binary search tree, Sleator's 1184 ///and Tarjan's Splay tree for guarantee the logarithmic amortized 1185 ///time bound for arc lookups. This class also guarantees the 1209 1186 ///optimal time bound in a constant factor for any distribution of 1210 1187 ///queries. … … 1531 1508 1532 1509 ///Find an arc between two nodes. 1533 ///\param s The source node .1534 ///\param t The target node .1510 ///\param s The source node 1511 ///\param t The target node 1535 1512 ///\param p The previous arc between \c s and \c t. It it is INVALID or 1536 1513 ///not given, the operator finds the first appropriate arc. … … 1543 1520 ///DynArcLookUp<ListDigraph> ae(g); 1544 1521 ///... 1545 ///int n =0;1546 ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;1522 ///int n=0; 1523 ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++; 1547 1524 ///\endcode 1548 1525 /// 1549 ///Finding the arcs take at most <em>O </em>(log<em>d</em>)1526 ///Finding the arcs take at most <em>O(</em>log<em>d)</em> 1550 1527 ///amortized time, specifically, the time complexity of the lookups 1551 1528 ///is equal to the optimal search tree implementation for the … … 1553 1530 /// 1554 1531 ///\note This is a dynamic data structure, therefore the data 1555 ///structure is updated after each graph alteration. Thus although1556 ///th is data structure is theoretically faster than \refArcLookUp1557 /// and \ref AllArcLookup,it often provides worse performance than1532 ///structure is updated after each graph alteration. However, 1533 ///theoretically this data structure is faster than \c ArcLookUp 1534 ///or AllEdgeLookup, but it often provides worse performance than 1558 1535 ///them. 1536 /// 1559 1537 Arc operator()(Node s, Node t, Arc p = INVALID) const { 1560 1538 if (p == INVALID) { … … 1608 1586 }; 1609 1587 1610 ///Fast arc look -up between given endpoints.1588 ///Fast arc look up between given endpoints. 1611 1589 1612 1590 ///Using this class, you can find an arc in a digraph from a given 1613 ///source to a given target in time <em>O </em>(log<em>d</em>),1591 ///source to a given target in time <em>O(log d)</em>, 1614 1592 ///where <em>d</em> is the out-degree of the source node. 1615 1593 /// … … 1617 1595 ///Use \ref AllArcLookUp for this purpose. 1618 1596 /// 1619 ///\warning This class is static, so you should call refresh() (or at1620 /// least refresh(Node)) to refresh this data structure whenever the1621 /// digraph changes. This is a time consuming (superlinearly proportional1622 /// (<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).1597 ///\warning This class is static, so you should refresh() (or at least 1598 ///refresh(Node)) this data structure 1599 ///whenever the digraph changes. This is a time consuming (superlinearly 1600 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs). 1623 1601 /// 1624 1602 ///\tparam G The type of the underlying digraph. … … 1669 1647 } 1670 1648 public: 1671 ///Refresh the searchdata structure at a node.1649 ///Refresh the data structure at a node. 1672 1650 1673 1651 ///Build up the search database of node \c n. 1674 1652 /// 1675 ///It runs in time <em>O </em>(<em>d</em> log<em>d</em>), where <em>d</em>1676 /// isthe number of the outgoing arcs of \c n.1653 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is 1654 ///the number of the outgoing arcs of \c n. 1677 1655 void refresh(Node n) 1678 1656 { … … 1690 1668 ///\ref refresh(Node) "refresh(n)" for each node \c n. 1691 1669 /// 1692 ///It runs in time <em>O </em>(<em>m</em> log<em>D</em>), where <em>m</em> is1693 ///the number of the arcs in the digraphand <em>D</em> is the maximum1670 ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is 1671 ///the number of the arcs of \c n and <em>D</em> is the maximum 1694 1672 ///out-degree of the digraph. 1673 1695 1674 void refresh() 1696 1675 { … … 1700 1679 ///Find an arc between two nodes. 1701 1680 1702 ///Find an arc between two nodes in time <em>O </em>(log<em>d</em>), where1703 /// <em>d</em> is the number of outgoing arcs of \c s.1704 ///\param s The source node .1705 ///\param t The target node .1681 ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where 1682 /// <em>d</em> is the number of outgoing arcs of \c s. 1683 ///\param s The source node 1684 ///\param t The target node 1706 1685 ///\return An arc from \c s to \c t if there exists, 1707 1686 ///\ref INVALID otherwise. … … 1709 1688 ///\warning If you change the digraph, refresh() must be called before using 1710 1689 ///this operator. If you change the outgoing arcs of 1711 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. 1690 ///a single node \c n, then 1691 ///\ref refresh(Node) "refresh(n)" is enough. 1692 /// 1712 1693 Arc operator()(Node s, Node t) const 1713 1694 { … … 1721 1702 }; 1722 1703 1723 ///Fast look -up of all arcs between given endpoints.1704 ///Fast look up of all arcs between given endpoints. 1724 1705 1725 1706 ///This class is the same as \ref ArcLookUp, with the addition 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). 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). 1733 1713 /// 1734 1714 ///\tparam G The type of the underlying digraph. … … 1754 1734 else { 1755 1735 next=refreshNext(_right[head],next); 1736 // _next[head]=next; 1756 1737 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head)) 1757 1738 ? next : INVALID; … … 1778 1759 ///Build up the search database of node \c n. 1779 1760 /// 1780 ///It runs in time <em>O </em>(<em>d</em> log<em>d</em>), where <em>d</em> is1761 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is 1781 1762 ///the number of the outgoing arcs of \c n. 1763 1782 1764 void refresh(Node n) 1783 1765 { … … 1791 1773 ///\ref refresh(Node) "refresh(n)" for each node \c n. 1792 1774 /// 1793 ///It runs in time <em>O </em>(<em>m</em> log<em>D</em>), where <em>m</em> is1794 ///the number of the arcs in the digraphand <em>D</em> is the maximum1775 ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is 1776 ///the number of the arcs of \c n and <em>D</em> is the maximum 1795 1777 ///out-degree of the digraph. 1778 1796 1779 void refresh() 1797 1780 { … … 1802 1785 1803 1786 ///Find an arc between two nodes. 1804 ///\param s The source node .1805 ///\param t The target node .1787 ///\param s The source node 1788 ///\param t The target node 1806 1789 ///\param prev The previous arc between \c s and \c t. It it is INVALID or 1807 1790 ///not given, the operator finds the first appropriate arc. … … 1814 1797 ///AllArcLookUp<ListDigraph> ae(g); 1815 1798 ///... 1816 ///int n =0;1817 ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;1799 ///int n=0; 1800 ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++; 1818 1801 ///\endcode 1819 1802 /// 1820 ///Finding the first arc take <em>O </em>(log<em>d</em>)time, where1821 /// <em>d</em> is the number of outgoing arcs of \c s. Then, the1803 ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where 1804 /// <em>d</em> is the number of outgoing arcs of \c s. Then, the 1822 1805 ///consecutive arcs are found in constant time. 1823 1806 /// 1824 1807 ///\warning If you change the digraph, refresh() must be called before using 1825 1808 ///this operator. If you change the outgoing arcs of 1826 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. 1809 ///a single node \c n, then 1810 ///\ref refresh(Node) "refresh(n)" is enough. 1827 1811 /// 1828 1812 #ifdef DOXYGEN -
lemon/dfs.h
r287 r286 56 56 ///\param g is the digraph, to which we would like to define the 57 57 ///\ref PredMap. 58 ///\todo The digraph alone may be insufficient to initialize 58 59 static PredMap *createPredMap(const Digraph &g) 59 60 { … … 65 66 ///The type of the map that indicates which nodes are processed. 66 67 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 68 ///By default it is a NullMap. 67 69 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 68 70 ///Instantiates a \ref ProcessedMap. … … 195 197 int _stack_head; 196 198 197 //Creates the maps if necessary. 199 ///Creates the maps if necessary. 200 ///\todo Better memory allocation (instead of new). 198 201 void create_maps() 199 202 { … … 780 783 ///\param g is the digraph, to which we would like to define the 781 784 ///\ref PredMap. 785 ///\todo The digraph alone may be insufficient to initialize 782 786 static PredMap *createPredMap(const Digraph &g) 783 787 { … … 1314 1318 int _stack_head; 1315 1319 1316 //Creates the maps if necessary. 1320 ///Creates the maps if necessary. 1321 ///\todo Better memory allocation (instead of new). 1317 1322 void create_maps() { 1318 1323 if(!_reached) { -
lemon/dijkstra.h
r287 r286 145 145 ///\param g is the digraph, to which we would like to define the 146 146 ///\ref PredMap. 147 ///\todo The digraph alone may be insufficient for the initialization 147 148 static PredMap *createPredMap(const Digraph &g) 148 149 { … … 155 156 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 156 157 ///By default it is a NullMap. 158 ///\todo If it is set to a real map, 159 ///Dijkstra::processed() should read this. 157 160 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 158 161 ///Instantiates a \ref ProcessedMap. … … 295 298 bool local_heap; 296 299 297 //Creates the maps if necessary. 300 ///Creates the maps if necessary. 301 ///\todo Better memory allocation (instead of new). 298 302 void create_maps() 299 303 { … … 962 966 /// \param g is the digraph, to which we would like to define the 963 967 /// HeapCrossRef. 968 /// \todo The digraph alone may be insufficient for the initialization 964 969 static HeapCrossRef *createHeapCrossRef(const Digraph &g) 965 970 { … … 997 1002 ///\param g is the digraph, to which we would like to define the 998 1003 ///\ref PredMap. 1004 ///\todo The digraph alone may be insufficient to initialize 999 1005 static PredMap *createPredMap(const Digraph &g) 1000 1006 { … … 1007 1013 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 1008 1014 ///By default it is a NullMap. 1015 ///\todo If it is set to a real map, 1016 ///Dijkstra::processed() should read this. 1017 ///\todo named parameter to set this type, function to read and write. 1009 1018 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 1010 1019 ///Instantiates a \ref ProcessedMap. … … 1052 1061 /// The \ref DijkstraWizardBase is a class to be the default traits of the 1053 1062 /// \ref DijkstraWizard class. 1063 /// \todo More named parameters are required... 1054 1064 template<class GR,class LM> 1055 1065 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM> -
lemon/error.h
r280 r212 103 103 ///\e 104 104 105 ///\todo The good solution is boost::shared_ptr... 106 /// 105 107 mutable std::auto_ptr<std::ostringstream> buf; 106 108 -
lemon/graph_to_eps.h
r280 r253 667 667 ///it draws the graph. 668 668 void run() { 669 //\todo better 'epsilon' would be nice here. 669 670 const double EPSILON=1e-9; 670 671 if(dontPrint) return; … … 707 708 for(ArcIt e(g);e!=INVALID;++e) 708 709 max_w=std::max(double(_arcWidths[e]),max_w); 710 //\todo better 'epsilon' would be nice here. 709 711 if(max_w>EPSILON) { 710 712 _arcWidthScale/=max_w; … … 716 718 for(NodeIt n(g);n!=INVALID;++n) 717 719 max_s=std::max(double(_nodeSizes[n]),max_s); 720 //\todo better 'epsilon' would be nice here. 718 721 if(max_s>EPSILON) { 719 722 _nodeScale/=max_s; … … 871 874 } 872 875 else { 876 //\todo Verify centering 873 877 double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.width(), 874 878 (A4WIDTH-2*A4BORDER)/bb.height()); … … 903 907 dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]); 904 908 double l=std::sqrt(dvec.normSquare()); 909 //\todo better 'epsilon' would be nice here. 905 910 dim2::Point<double> d(dvec/std::max(l,EPSILON)); 906 911 dim2::Point<double> m; -
lemon/list_graph.h
r280 r239 502 502 ///be invalidated. 503 503 /// 504 ///\warning This functionality cannot be used in conjunctionwith the504 ///\warning This functionality cannot be used together with the 505 505 ///Snapshot feature. 506 /// 507 ///\todo It could be implemented in a bit faster way. 506 508 Node split(Node n, bool connect = true) { 507 509 Node b = addNode(); -
lemon/maps.h
r280 r220 485 485 /// 486 486 /// \sa CombineMap 487 /// 488 /// \todo Check the requirements. 487 489 template <typename M1, typename M2> 488 490 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> { … … 539 541 /// 540 542 /// \sa ComposeMap 543 /// 544 /// \todo Check the requirements. 541 545 template<typename M1, typename M2, typename F, 542 546 typename V = typename F::result_type> -
lemon/random.h
r280 r209 822 822 /// \note The Cartesian form of the Box-Muller 823 823 /// transformation is used to generate a random normal distribution. 824 /// \todo Consider using the "ziggurat" method instead. 824 825 double gauss() 825 826 { -
lemon/smart_graph.h
r280 r238 301 301 ///\warning This functionality cannot be used together with the Snapshot 302 302 ///feature. 303 ///\todo It could be implemented in a bit faster way. 303 304 Node split(Node n, bool connect = true) 304 305 { -
lemon/time_measure.h
r280 r210 293 293 ///function, consider the usage of \ref TimeReport instead. 294 294 /// 295 ///\todo This shouldn't be Unix (Linux) specific. 295 296 ///\sa TimeReport 296 297 class Timer … … 487 488 ///\sa Timer 488 489 ///\sa NoTimeReport 490 ///\todo There is no test case for this 489 491 class TimeReport : public Timer 490 492 { -
lemon/tolerance.h
r280 r209 25 25 ///floating point numbers. 26 26 /// 27 ///\todo It should be in a module like "Basic tools" 28 27 29 28 30 namespace lemon { -
scripts/chg-len.py
r284 r272 10 10 """ 11 11 exit(0) 12 plist = os.popen(" HGRCPATH=''hg parents --template='{rev}\n'").readlines()12 plist = os.popen("hg parents --template='{rev}\n'").readlines() 13 13 if len(plist)>1: 14 14 print "You are in the process of merging" … … 16 16 PAR = int(plist[0]) 17 17 18 f = os.popen("HGRCPATH='' hg log -r 0:tip --template='{rev} {parents}\n'").\ 19 readlines() 18 f = os.popen("hg log -r 0:tip --template='{rev} {parents}\n'").readlines() 20 19 REV = -1 21 20 lengths=[] -
test/graph_copy_test.cc
r282 r220 64 64 ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to); 65 65 66 digraphCopy(from, to).67 nodeMap( fnm, tnm).arcMap(fam, tam).66 DigraphCopy<ListDigraph, SmartDigraph>(to, from). 67 nodeMap(tnm, fnm).arcMap(tam, fam). 68 68 nodeRef(nr).arcRef(er). 69 69 nodeCrossRef(ncr).arcCrossRef(ecr). 70 node( fn, tn).arc(fa, ta).run();70 node(tn, fn).arc(ta, fa).run(); 71 71 72 72 for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) { … … 139 139 ListGraph::EdgeMap<SmartGraph::Edge> ecr(to); 140 140 141 graphCopy(from, to).142 nodeMap( fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem).141 GraphCopy<ListGraph, SmartGraph>(to, from). 142 nodeMap(tnm, fnm).arcMap(tam, fam).edgeMap(tem, fem). 143 143 nodeRef(nr).arcRef(ar).edgeRef(er). 144 144 nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr). 145 node( fn, tn).arc(fa, ta).edge(fe, te).run();145 node(tn, fn).arc(ta, fa).edge(te, fe).run(); 146 146 147 147 for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
Note: See TracChangeset
for help on using the changeset viewer.