COIN-OR::LEMON - Graph Library

Changeset 282:dc9e8d2c0df9 in lemon


Ignore:
Timestamp:
09/26/08 13:46:49 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Using from-to order in graph copying tools + doc improvements (ticket #150)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/core.h

    r233 r282  
    5959  /// @{ 
    6060 
    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, 
     61  ///Create convenient typedefs for the digraph types and iterators 
     62 
     63  ///This \c \#define creates convenient type definitions for the following 
     64  ///types of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt, 
    6565  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 
    6666  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. 
     
    8181  typedef Digraph::ArcMap<bool> BoolArcMap;                             \ 
    8282  typedef Digraph::ArcMap<int> IntArcMap;                               \ 
    83   typedef Digraph::ArcMap<double> DoubleArcMap 
    84  
    85   ///Creates convenience typedefs for the digraph types and iterators 
     83  typedef Digraph::ArcMap<double> DoubleArcMap; 
     84 
     85  ///Create convenient typedefs for the digraph types and iterators 
    8686 
    8787  ///\see DIGRAPH_TYPEDEFS 
     
    101101  typedef typename Digraph::template ArcMap<bool> BoolArcMap;           \ 
    102102  typedef typename Digraph::template ArcMap<int> IntArcMap;             \ 
    103   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 
     103  typedef typename Digraph::template ArcMap<double> DoubleArcMap; 
     104 
     105  ///Create convenient typedefs for the graph types and iterators 
     106 
     107  ///This \c \#define creates the same convenient type definitions as defined 
    108108  ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates 
    109109  ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap, 
     
    111111  /// 
    112112  ///\note If the graph type is a dependent type, ie. the graph type depend 
    113   ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() 
     113  ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS() 
    114114  ///macro. 
    115115#define GRAPH_TYPEDEFS(Graph)                                           \ 
     
    120120  typedef Graph::EdgeMap<bool> BoolEdgeMap;                             \ 
    121121  typedef Graph::EdgeMap<int> IntEdgeMap;                               \ 
    122   typedef Graph::EdgeMap<double> DoubleEdgeMap 
    123  
    124   ///Creates convenience typedefs for the graph types and iterators 
     122  typedef Graph::EdgeMap<double> DoubleEdgeMap; 
     123 
     124  ///Create convenient typedefs for the graph types and iterators 
    125125 
    126126  ///\see GRAPH_TYPEDEFS 
     
    135135  typedef typename Graph::template EdgeMap<bool> BoolEdgeMap;           \ 
    136136  typedef typename Graph::template EdgeMap<int> IntEdgeMap;             \ 
    137   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 
     137  typedef typename Graph::template EdgeMap<double> DoubleEdgeMap; 
     138 
     139  /// \brief Function to count the items in a graph. 
     140  /// 
     141  /// This function counts the items (nodes, arcs etc.) in a graph. 
     142  /// The complexity of the function is linear because 
    143143  /// it iterates on all of the items. 
    144144  template <typename Graph, typename Item> 
     
    177177  /// 
    178178  /// This function counts the nodes in the graph. 
    179   /// 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 
     179  /// The complexity of the function is <em>O</em>(<em>n</em>), but for some 
     180  /// graph structures it is specialized to run in <em>O</em>(1). 
     181  /// 
     182  /// \note If the graph contains a \c nodeNum() member function and a 
     183  /// \c NodeNumTag tag then this function calls directly the member 
    184184  /// function to query the cardinality of the node set. 
    185185  template <typename Graph> 
     
    213213  /// 
    214214  /// This function counts the arcs in the graph. 
    215   /// 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 
     215  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some 
     216  /// graph structures it is specialized to run in <em>O</em>(1). 
     217  /// 
     218  /// \note If the graph contains a \c arcNum() member function and a 
     219  /// \c ArcNumTag tag then this function calls directly the member 
    220220  /// function to query the cardinality of the arc set. 
    221221  template <typename Graph> 
     
    225225 
    226226  // Edge counting: 
     227 
    227228  namespace _core_bits { 
    228229 
     
    248249  /// 
    249250  /// This function counts the edges in the graph. 
    250   /// 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 
     251  /// The complexity of the function is <em>O</em>(<em>m</em>), but for some 
     252  /// graph structures it is specialized to run in <em>O</em>(1). 
     253  /// 
     254  /// \note If the graph contains a \c edgeNum() member function and a 
     255  /// \c EdgeNumTag tag then this function calls directly the member 
    255256  /// function to query the cardinality of the edge set. 
    256257  template <typename Graph> 
     
    273274  /// 
    274275  /// This function counts the number of the out-arcs from node \c n 
    275   /// in the graph. 
     276  /// in the graph \c g. 
    276277  template <typename Graph> 
    277   inline int countOutArcs(const Graph& _g,  const typename Graph::Node& _n) { 
    278     return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n); 
     278  inline int countOutArcs(const Graph& g,  const typename Graph::Node& n) { 
     279    return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n); 
    279280  } 
    280281 
     
    282283  /// 
    283284  /// This function counts the number of the in-arcs to node \c n 
    284   /// in the graph. 
     285  /// in the graph \c g. 
    285286  template <typename Graph> 
    286   inline int countInArcs(const Graph& _g,  const typename Graph::Node& _n) { 
    287     return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n); 
     287  inline int countInArcs(const Graph& g,  const typename Graph::Node& n) { 
     288    return countNodeDegree<Graph, typename Graph::InArcIt>(g, n); 
    288289  } 
    289290 
     
    291292  /// 
    292293  /// This function counts the number of the inc-edges to node \c n 
    293   /// in the graph. 
     294  /// in the undirected graph \c g. 
    294295  template <typename Graph> 
    295   inline int countIncEdges(const Graph& _g,  const typename Graph::Node& _n) { 
    296     return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n); 
     296  inline int countIncEdges(const Graph& g,  const typename Graph::Node& n) { 
     297    return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n); 
    297298  } 
    298299 
     
    308309 
    309310    template <typename Digraph, typename Item, typename RefMap, 
    310               typename ToMap, typename FromMap> 
     311              typename FromMap, typename ToMap> 
    311312    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> { 
    312313    public: 
    313314 
    314       MapCopy(ToMap& tmap, const FromMap& map) 
    315         : _tmap(tmap), _map(map) {} 
     315      MapCopy(const FromMap& map, ToMap& tmap) 
     316        : _map(map), _tmap(tmap) {} 
    316317 
    317318      virtual void copy(const Digraph& digraph, const RefMap& refMap) { 
     
    323324 
    324325    private: 
     326      const FromMap& _map; 
    325327      ToMap& _tmap; 
    326       const FromMap& _map; 
    327328    }; 
    328329 
     
    331332    public: 
    332333 
    333       ItemCopy(It& it, const Item& item) : _it(it), _item(item) {} 
     334      ItemCopy(const Item& item, It& it) : _item(item), _it(it) {} 
    334335 
    335336      virtual void copy(const Digraph&, const RefMap& refMap) { 
     
    338339 
    339340    private: 
     341      Item _item; 
    340342      It& _it; 
    341       Item _item; 
    342343    }; 
    343344 
     
    380381    struct DigraphCopySelector { 
    381382      template <typename From, typename NodeRefMap, typename ArcRefMap> 
    382       static void copy(Digraph &to, const From& from, 
     383      static void copy(const From& from, Digraph &to, 
    383384                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 
    384385        for (typename From::NodeIt it(from); it != INVALID; ++it) { 
     
    398399    { 
    399400      template <typename From, typename NodeRefMap, typename ArcRefMap> 
    400       static void copy(Digraph &to, const From& from, 
     401      static void copy(const From& from, Digraph &to, 
    401402                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 
    402403        to.build(from, nodeRefMap, arcRefMap); 
     
    407408    struct GraphCopySelector { 
    408409      template <typename From, typename NodeRefMap, typename EdgeRefMap> 
    409       static void copy(Graph &to, const From& from, 
     410      static void copy(const From& from, Graph &to, 
    410411                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 
    411412        for (typename From::NodeIt it(from); it != INVALID; ++it) { 
     
    425426    { 
    426427      template <typename From, typename NodeRefMap, typename EdgeRefMap> 
    427       static void copy(Graph &to, const From& from, 
     428      static void copy(const From& from, Graph &to, 
    428429                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 
    429430        to.build(from, nodeRefMap, edgeRefMap); 
     
    436437  /// 
    437438  /// 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 a graph, but it can create 
     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 create 
    441442  /// references and cross references between the nodes and arcs of 
    442   /// 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 
     443  /// the two digraphs, and it can copy maps to use with the newly created 
     444  /// digraph. 
     445  /// 
     446  /// To make a copy from a digraph, first an instance of DigraphCopy 
     447  /// should be created, then the data belongs to the digraph should 
    447448  /// assigned to copy. In the end, the \c run() member should be 
    448449  /// called. 
    449450  /// 
    450   /// The next code copies a graph with several data: 
     451  /// The next code copies a digraph with several data: 
    451452  ///\code 
    452   ///  DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); 
    453   ///  // create a reference for the nodes 
     453  ///  DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph); 
     454  ///  // Create references for the nodes 
    454455  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); 
    455   ///  dc.nodeRef(nr); 
    456   ///  // create a cross reference (inverse) for the arcs 
     456  ///  cg.nodeRef(nr); 
     457  ///  // Create cross references (inverse) for the arcs 
    457458  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph); 
    458   ///  dc.arcCrossRef(acr); 
    459   ///  // copy an arc map 
     459  ///  cg.arcCrossRef(acr); 
     460  ///  // Copy an arc map 
    460461  ///  OrigGraph::ArcMap<double> oamap(orig_graph); 
    461462  ///  NewGraph::ArcMap<double> namap(new_graph); 
    462   ///  dc.arcMap(namap, oamap); 
    463   ///  // copy a node 
     463  ///  cg.arcMap(oamap, namap); 
     464  ///  // Copy a node 
    464465  ///  OrigGraph::Node on; 
    465466  ///  NewGraph::Node nn; 
    466   ///  dc.node(nn, on); 
    467   ///  // Executions of copy 
    468   ///  dc.run(); 
     467  ///  cg.node(on, nn); 
     468  ///  // Execute copying 
     469  ///  cg.run(); 
    469470  ///\endcode 
    470   template <typename To, typename From> 
     471  template <typename From, typename To> 
    471472  class DigraphCopy { 
    472473  private: 
     
    483484    typedef typename From::template ArcMap<TArc> ArcRefMap; 
    484485 
    485  
    486486  public: 
    487487 
    488  
    489     /// \brief Constructor for the DigraphCopy. 
    490     /// 
    491     /// It copies the content of the \c _from digraph into the 
    492     /// \c _to digraph. 
    493     DigraphCopy(To& to, const From& from) 
     488    /// \brief Constructor of DigraphCopy. 
     489    /// 
     490    /// Constructor of DigraphCopy for copying the content of the 
     491    /// \c from digraph into the \c to digraph. 
     492    DigraphCopy(const From& from, To& to) 
    494493      : _from(from), _to(to) {} 
    495494 
    496     /// \brief Destructor of the DigraphCopy 
    497     /// 
    498     /// Destructor of the DigraphCopy 
     495    /// \brief Destructor of DigraphCopy 
     496    /// 
     497    /// Destructor of DigraphCopy. 
    499498    ~DigraphCopy() { 
    500499      for (int i = 0; i < int(_node_maps.size()); ++i) { 
     
    507506    } 
    508507 
    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. 
     508    /// \brief Copy the node references into the given map. 
     509    /// 
     510    /// This function copies the node references into the given map. 
     511    /// The parameter should be a map, whose key type is the Node type of 
     512    /// the source digraph, while the value type is the Node type of the 
     513    /// destination digraph. 
    515514    template <typename NodeRef> 
    516515    DigraphCopy& nodeRef(NodeRef& map) { 
     
    520519    } 
    521520 
    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. 
     521    /// \brief Copy the node cross references into the given map. 
     522    /// 
     523    /// This function copies the node cross references (reverse references) 
     524    /// into the given map. The parameter should be a map, whose key type 
     525    /// is the Node type of the destination digraph, while the value type is 
     526    /// the Node type of the source digraph. 
    528527    template <typename NodeCrossRef> 
    529528    DigraphCopy& nodeCrossRef(NodeCrossRef& map) { 
     
    533532    } 
    534533 
    535     /// \brief Make copy of the given map. 
    536     /// 
    537     /// Makes copy of the given map for the newly created digraph. 
    538     /// The new map's key type is the destination graph's node type, 
    539     /// and the copied map's key type is the source graph's node type. 
    540     template <typename ToMap, typename FromMap> 
    541     DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { 
     534    /// \brief Make a copy of the given node map. 
     535    /// 
     536    /// This function makes a copy of the given node map for the newly 
     537    /// created digraph. 
     538    /// The key type of the new map \c tmap should be the Node type of the 
     539    /// destination digraph, and the key type of the original map \c map 
     540    /// should be the Node type of the source digraph. 
     541    template <typename FromMap, typename ToMap> 
     542    DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { 
    542543      _node_maps.push_back(new _core_bits::MapCopy<From, Node, 
    543                            NodeRefMap, ToMap, FromMap>(tmap, map)); 
     544                           NodeRefMap, FromMap, ToMap>(map, tmap)); 
    544545      return *this; 
    545546    } 
     
    547548    /// \brief Make a copy of the given node. 
    548549    /// 
    549     /// Make a copy of the given node. 
    550     DigraphCopy& node(TNode& tnode, const Node& snode) { 
     550    /// This function makes a copy of the given node. 
     551    DigraphCopy& node(const Node& node, TNode& tnode) { 
    551552      _node_maps.push_back(new _core_bits::ItemCopy<From, Node, 
    552                            NodeRefMap, TNode>(tnode, snode)); 
    553       return *this; 
    554     } 
    555  
    556     /// \brief Copies the arc references into the given map. 
    557     /// 
    558     /// Copies the arc references into the given map. 
     553                           NodeRefMap, TNode>(node, tnode)); 
     554      return *this; 
     555    } 
     556 
     557    /// \brief Copy the arc references into the given map. 
     558    /// 
     559    /// This function copies the arc references into the given map. 
     560    /// The parameter should be a map, whose key type is the Arc type of 
     561    /// the source digraph, while the value type is the Arc type of the 
     562    /// destination digraph. 
    559563    template <typename ArcRef> 
    560564    DigraphCopy& arcRef(ArcRef& map) { 
     
    564568    } 
    565569 
    566     /// \brief Copies the arc cross references into the given map. 
    567     /// 
    568     ///  Copies the arc cross references (reverse references) into 
    569     ///  the given map. 
     570    /// \brief Copy the arc cross references into the given map. 
     571    /// 
     572    /// This function copies the arc cross references (reverse references) 
     573    /// into the given map. The parameter should be a map, whose key type 
     574    /// is the Arc type of the destination digraph, while the value type is 
     575    /// the Arc type of the source digraph. 
    570576    template <typename ArcCrossRef> 
    571577    DigraphCopy& arcCrossRef(ArcCrossRef& map) { 
     
    575581    } 
    576582 
    577     /// \brief Make copy of the given map. 
    578     /// 
    579     /// Makes copy of the given map for the newly created digraph. 
    580     /// The new map's key type is the to digraph's arc type, 
    581     /// and the copied map's key type is the from digraph's arc 
    582     /// type. 
    583     template <typename ToMap, typename FromMap> 
    584     DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) { 
     583    /// \brief Make a copy of the given arc map. 
     584    /// 
     585    /// This function makes a copy of the given arc map for the newly 
     586    /// created digraph. 
     587    /// The key type of the new map \c tmap should be the Arc type of the 
     588    /// destination digraph, and the key type of the original map \c map 
     589    /// should be the Arc type of the source digraph. 
     590    template <typename FromMap, typename ToMap> 
     591    DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) { 
    585592      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, 
    586                           ArcRefMap, ToMap, FromMap>(tmap, map)); 
     593                          ArcRefMap, FromMap, ToMap>(map, tmap)); 
    587594      return *this; 
    588595    } 
     
    590597    /// \brief Make a copy of the given arc. 
    591598    /// 
    592     /// Make a copy of the given arc. 
    593     DigraphCopy& arc(TArc& tarc, const Arc& sarc) { 
     599    /// This function makes a copy of the given arc. 
     600    DigraphCopy& arc(const Arc& arc, TArc& tarc) { 
    594601      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, 
    595                           ArcRefMap, TArc>(tarc, sarc)); 
    596       return *this; 
    597     } 
    598  
    599     /// \brief Executes the copies. 
    600     /// 
    601     /// Executes the copies. 
     602                          ArcRefMap, TArc>(arc, tarc)); 
     603      return *this; 
     604    } 
     605 
     606    /// \brief Execute copying. 
     607    /// 
     608    /// This function executes the copying of the digraph along with the 
     609    /// copying of the assigned data. 
    602610    void run() { 
    603611      NodeRefMap nodeRefMap(_from); 
    604612      ArcRefMap arcRefMap(_from); 
    605613      _core_bits::DigraphCopySelector<To>:: 
    606         copy(_to, _from, nodeRefMap, arcRefMap); 
     614        copy(_from, _to, nodeRefMap, arcRefMap); 
    607615      for (int i = 0; i < int(_node_maps.size()); ++i) { 
    608616        _node_maps[i]->copy(_from, nodeRefMap); 
     
    615623  protected: 
    616624 
    617  
    618625    const From& _from; 
    619626    To& _to; 
    620627 
    621628    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > 
    622     _node_maps; 
     629      _node_maps; 
    623630 
    624631    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > 
    625     _arc_maps; 
     632      _arc_maps; 
    626633 
    627634  }; 
     
    629636  /// \brief Copy a digraph to another digraph. 
    630637  /// 
    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: 
     638  /// This function copies a digraph to another digraph. 
     639  /// The complete usage of it is detailed in the DigraphCopy class, but 
     640  /// a short example shows a basic work: 
    634641  ///\code 
    635   /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); 
     642  /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run(); 
    636643  ///\endcode 
    637644  /// 
    638645  /// After the copy the \c nr map will contain the mapping from the 
    639646  /// 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 digraph 
     647  /// \c acr will contain the mapping from the arcs of the \c to digraph 
    641648  /// to the arcs of the \c from digraph. 
    642649  /// 
    643650  /// \see DigraphCopy 
    644   template <typename To, typename From> 
    645   DigraphCopy<To, From> copyDigraph(To& to, const From& from) { 
    646     return DigraphCopy<To, From>(to, from); 
     651  template <typename From, typename To> 
     652  DigraphCopy<From, To> digraphCopy(const From& from, To& to) { 
     653    return DigraphCopy<From, To>(from, to); 
    647654  } 
    648655 
     
    650657  /// 
    651658  /// 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 just make a copy of a graph, but it can create 
     659  /// simplest way of using it is through the \c graphCopy() function. 
     660  /// 
     661  /// This class not only make a copy of a graph, but it can create 
    655662  /// references and cross references between the nodes, edges and arcs of 
    656   /// the two graphs, it can copy maps for use with the newly created 
    657   /// graph and copy nodes, edges and arcs. 
     663  /// the two graphs, and it can copy maps for using with the newly created 
     664  /// graph. 
    658665  /// 
    659666  /// To make a copy from a graph, first an instance of GraphCopy 
     
    664671  /// The next code copies a graph with several data: 
    665672  ///\code 
    666   ///  GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); 
    667   ///  // create a reference for the nodes 
     673  ///  GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph); 
     674  ///  // Create references for the nodes 
    668675  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); 
    669   ///  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 
     676  ///  cg.nodeRef(nr); 
     677  ///  // Create cross references (inverse) for the edges 
     678  ///  NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph); 
     679  ///  cg.edgeCrossRef(ecr); 
     680  ///  // Copy an edge map 
     681  ///  OrigGraph::EdgeMap<double> oemap(orig_graph); 
     682  ///  NewGraph::EdgeMap<double> nemap(new_graph); 
     683  ///  cg.edgeMap(oemap, nemap); 
     684  ///  // Copy a node 
    678685  ///  OrigGraph::Node on; 
    679686  ///  NewGraph::Node nn; 
    680   ///  dc.node(nn, on); 
    681   ///  // Executions of copy 
    682   ///  dc.run(); 
     687  ///  cg.node(on, nn); 
     688  ///  // Execute copying 
     689  ///  cg.run(); 
    683690  ///\endcode 
    684   template <typename To, typename From> 
     691  template <typename From, typename To> 
    685692  class GraphCopy { 
    686693  private: 
     
    701708 
    702709    struct ArcRefMap { 
    703       ArcRefMap(const To& to, const From& from, 
     710      ArcRefMap(const From& from, const To& to, 
    704711                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) 
    705         : _to(to), _from(from), 
     712        : _from(from), _to(to), 
    706713          _edge_ref(edge_ref), _node_ref(node_ref) {} 
    707714 
     
    717724      } 
    718725 
     726      const From& _from; 
    719727      const To& _to; 
    720       const From& _from; 
    721728      const EdgeRefMap& _edge_ref; 
    722729      const NodeRefMap& _node_ref; 
    723730    }; 
    724731 
    725  
    726732  public: 
    727733 
    728  
    729     /// \brief Constructor for the GraphCopy. 
    730     /// 
    731     /// It copies the content of the \c _from graph into the 
    732     /// \c _to graph. 
    733     GraphCopy(To& to, const From& from) 
     734    /// \brief Constructor of GraphCopy. 
     735    /// 
     736    /// Constructor of GraphCopy for copying the content of the 
     737    /// \c from graph into the \c to graph. 
     738    GraphCopy(const From& from, To& to) 
    734739      : _from(from), _to(to) {} 
    735740 
    736     /// \brief Destructor of the GraphCopy 
    737     /// 
    738     /// Destructor of the GraphCopy 
     741    /// \brief Destructor of GraphCopy 
     742    /// 
     743    /// Destructor of GraphCopy. 
    739744    ~GraphCopy() { 
    740745      for (int i = 0; i < int(_node_maps.size()); ++i) { 
     
    747752        delete _edge_maps[i]; 
    748753      } 
    749  
    750     } 
    751  
    752     /// \brief Copies the node references into the given map. 
    753     /// 
    754     /// Copies the node references into the given map. 
     754    } 
     755 
     756    /// \brief Copy the node references into the given map. 
     757    /// 
     758    /// This function copies the node references into the given map. 
     759    /// The parameter should be a map, whose key type is the Node type of 
     760    /// the source graph, while the value type is the Node type of the 
     761    /// destination graph. 
    755762    template <typename NodeRef> 
    756763    GraphCopy& nodeRef(NodeRef& map) { 
     
    760767    } 
    761768 
    762     /// \brief Copies the node cross references into the given map. 
    763     /// 
    764     ///  Copies the node cross references (reverse references) into 
    765     ///  the given map. 
     769    /// \brief Copy the node cross references into the given map. 
     770    /// 
     771    /// This function copies the node cross references (reverse references) 
     772    /// into the given map. The parameter should be a map, whose key type 
     773    /// is the Node type of the destination graph, while the value type is 
     774    /// the Node type of the source graph. 
    766775    template <typename NodeCrossRef> 
    767776    GraphCopy& nodeCrossRef(NodeCrossRef& map) { 
     
    771780    } 
    772781 
    773     /// \brief Make copy of the given map. 
    774     /// 
    775     /// Makes copy of the given map for the newly created graph. 
    776     /// The new map's key type is the to graph's node type, 
    777     /// and the copied map's key type is the from graph's node 
    778     /// type. 
    779     template <typename ToMap, typename FromMap> 
    780     GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { 
     782    /// \brief Make a copy of the given node map. 
     783    /// 
     784    /// This function makes a copy of the given node map for the newly 
     785    /// created graph. 
     786    /// The key type of the new map \c tmap should be the Node type of the 
     787    /// destination graph, and the key type of the original map \c map 
     788    /// should be the Node type of the source graph. 
     789    template <typename FromMap, typename ToMap> 
     790    GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { 
    781791      _node_maps.push_back(new _core_bits::MapCopy<From, Node, 
    782                            NodeRefMap, ToMap, FromMap>(tmap, map)); 
     792                           NodeRefMap, FromMap, ToMap>(map, tmap)); 
    783793      return *this; 
    784794    } 
     
    786796    /// \brief Make a copy of the given node. 
    787797    /// 
    788     /// Make a copy of the given node. 
    789     GraphCopy& node(TNode& tnode, const Node& snode) { 
     798    /// This function makes a copy of the given node. 
     799    GraphCopy& node(const Node& node, TNode& tnode) { 
    790800      _node_maps.push_back(new _core_bits::ItemCopy<From, Node, 
    791                            NodeRefMap, TNode>(tnode, snode)); 
    792       return *this; 
    793     } 
    794  
    795     /// \brief Copies the arc references into the given map. 
    796     /// 
    797     /// Copies the arc references into the given map. 
     801                           NodeRefMap, TNode>(node, tnode)); 
     802      return *this; 
     803    } 
     804 
     805    /// \brief Copy the arc references into the given map. 
     806    /// 
     807    /// This function copies the arc references into the given map. 
     808    /// The parameter should be a map, whose key type is the Arc type of 
     809    /// the source graph, while the value type is the Arc type of the 
     810    /// destination graph. 
    798811    template <typename ArcRef> 
    799812    GraphCopy& arcRef(ArcRef& map) { 
     
    803816    } 
    804817 
    805     /// \brief Copies the arc cross references into the given map. 
    806     /// 
    807     ///  Copies the arc cross references (reverse references) into 
    808     ///  the given map. 
     818    /// \brief Copy the arc cross references into the given map. 
     819    /// 
     820    /// This function copies the arc cross references (reverse references) 
     821    /// into the given map. The parameter should be a map, whose key type 
     822    /// is the Arc type of the destination graph, while the value type is 
     823    /// the Arc type of the source graph. 
    809824    template <typename ArcCrossRef> 
    810825    GraphCopy& arcCrossRef(ArcCrossRef& map) { 
     
    814829    } 
    815830 
    816     /// \brief Make copy of the given map. 
    817     /// 
    818     /// Makes copy of the given map for the newly created graph. 
    819     /// The new map's key type is the to graph's arc type, 
    820     /// and the copied map's key type is the from graph's arc 
    821     /// type. 
    822     template <typename ToMap, typename FromMap> 
    823     GraphCopy& arcMap(ToMap& tmap, const FromMap& map) { 
     831    /// \brief Make a copy of the given arc map. 
     832    /// 
     833    /// This function makes a copy of the given arc map for the newly 
     834    /// created graph. 
     835    /// The key type of the new map \c tmap should be the Arc type of the 
     836    /// destination graph, and the key type of the original map \c map 
     837    /// should be the Arc type of the source graph. 
     838    template <typename FromMap, typename ToMap> 
     839    GraphCopy& arcMap(const FromMap& map, ToMap& tmap) { 
    824840      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, 
    825                           ArcRefMap, ToMap, FromMap>(tmap, map)); 
     841                          ArcRefMap, FromMap, ToMap>(map, tmap)); 
    826842      return *this; 
    827843    } 
     
    829845    /// \brief Make a copy of the given arc. 
    830846    /// 
    831     /// Make a copy of the given arc. 
    832     GraphCopy& arc(TArc& tarc, const Arc& sarc) { 
     847    /// This function makes a copy of the given arc. 
     848    GraphCopy& arc(const Arc& arc, TArc& tarc) { 
    833849      _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, 
    834                           ArcRefMap, TArc>(tarc, sarc)); 
    835       return *this; 
    836     } 
    837  
    838     /// \brief Copies the edge references into the given map. 
    839     /// 
    840     /// Copies the edge references into the given map. 
     850                          ArcRefMap, TArc>(arc, tarc)); 
     851      return *this; 
     852    } 
     853 
     854    /// \brief Copy the edge references into the given map. 
     855    /// 
     856    /// This function copies the edge references into the given map. 
     857    /// The parameter should be a map, whose key type is the Edge type of 
     858    /// the source graph, while the value type is the Edge type of the 
     859    /// destination graph. 
    841860    template <typename EdgeRef> 
    842861    GraphCopy& edgeRef(EdgeRef& map) { 
     
    846865    } 
    847866 
    848     /// \brief Copies the edge cross references into the given map. 
    849     /// 
    850     /// Copies the edge cross references (reverse 
    851     /// references) into the given map. 
     867    /// \brief Copy the edge cross references into the given map. 
     868    /// 
     869    /// This function copies the edge cross references (reverse references) 
     870    /// into the given map. The parameter should be a map, whose key type 
     871    /// is the Edge type of the destination graph, while the value type is 
     872    /// the Edge type of the source graph. 
    852873    template <typename EdgeCrossRef> 
    853874    GraphCopy& edgeCrossRef(EdgeCrossRef& map) { 
     
    857878    } 
    858879 
    859     /// \brief Make copy of the given map. 
    860     /// 
    861     /// Makes copy of the given map for the newly created graph. 
    862     /// The new map's key type is the to graph's edge type, 
    863     /// and the copied map's key type is the from graph's edge 
    864     /// type. 
    865     template <typename ToMap, typename FromMap> 
    866     GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) { 
     880    /// \brief Make a copy of the given edge map. 
     881    /// 
     882    /// This function makes a copy of the given edge map for the newly 
     883    /// created graph. 
     884    /// The key type of the new map \c tmap should be the Edge type of the 
     885    /// destination graph, and the key type of the original map \c map 
     886    /// should be the Edge type of the source graph. 
     887    template <typename FromMap, typename ToMap> 
     888    GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) { 
    867889      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge, 
    868                            EdgeRefMap, ToMap, FromMap>(tmap, map)); 
     890                           EdgeRefMap, FromMap, ToMap>(map, tmap)); 
    869891      return *this; 
    870892    } 
     
    872894    /// \brief Make a copy of the given edge. 
    873895    /// 
    874     /// Make a copy of the given edge. 
    875     GraphCopy& edge(TEdge& tedge, const Edge& sedge) { 
     896    /// This function makes a copy of the given edge. 
     897    GraphCopy& edge(const Edge& edge, TEdge& tedge) { 
    876898      _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge, 
    877                            EdgeRefMap, TEdge>(tedge, sedge)); 
    878       return *this; 
    879     } 
    880  
    881     /// \brief Executes the copies. 
    882     /// 
    883     /// Executes the copies. 
     899                           EdgeRefMap, TEdge>(edge, tedge)); 
     900      return *this; 
     901    } 
     902 
     903    /// \brief Execute copying. 
     904    /// 
     905    /// This function executes the copying of the graph along with the 
     906    /// copying of the assigned data. 
    884907    void run() { 
    885908      NodeRefMap nodeRefMap(_from); 
    886909      EdgeRefMap edgeRefMap(_from); 
    887       ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap); 
     910      ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap); 
    888911      _core_bits::GraphCopySelector<To>:: 
    889         copy(_to, _from, nodeRefMap, edgeRefMap); 
     912        copy(_from, _to, nodeRefMap, edgeRefMap); 
    890913      for (int i = 0; i < int(_node_maps.size()); ++i) { 
    891914        _node_maps[i]->copy(_from, nodeRefMap); 
     
    905928 
    906929    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > 
    907     _node_maps; 
     930      _node_maps; 
    908931 
    909932    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > 
    910     _arc_maps; 
     933      _arc_maps; 
    911934 
    912935    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 
    913     _edge_maps; 
     936      _edge_maps; 
    914937 
    915938  }; 
     
    917940  /// \brief Copy a graph to another graph. 
    918941  /// 
    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: 
     942  /// This function copies a graph to another graph. 
     943  /// The complete usage of it is detailed in the GraphCopy class, 
     944  /// but a short example shows a basic work: 
    922945  ///\code 
    923   /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); 
     946  /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run(); 
    924947  ///\endcode 
    925948  /// 
    926949  /// After the copy the \c nr map will contain the mapping from the 
    927950  /// 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 graph 
    929   /// to the arcs of the \c from graph. 
     951  /// \c ecr will contain the mapping from the edges of the \c to graph 
     952  /// to the edges of the \c from graph. 
    930953  /// 
    931954  /// \see GraphCopy 
    932   template <typename To, typename From> 
    933   GraphCopy<To, From> 
    934   copyGraph(To& to, const From& from) { 
    935     return GraphCopy<To, From>(to, from); 
     955  template <typename From, typename To> 
     956  GraphCopy<From, To> 
     957  graphCopy(const From& from, To& to) { 
     958    return GraphCopy<From, To>(from, to); 
    936959  } 
    937960 
     
    958981    struct FindArcSelector< 
    959982      Graph, 
    960       typename enable_if<typename Graph::FindEdgeTag, void>::type> 
     983      typename enable_if<typename Graph::FindArcTag, void>::type> 
    961984    { 
    962985      typedef typename Graph::Node Node; 
     
    968991  } 
    969992 
    970   /// \brief Finds an arc between two nodes of a graph. 
    971   /// 
    972   /// Finds an arc from node \c u to node \c v in graph \c g. 
     993  /// \brief Find an arc between two nodes of a digraph. 
     994  /// 
     995  /// This function finds an arc from node \c u to node \c v in the 
     996  /// digraph \c g. 
    973997  /// 
    974998  /// If \c prev is \ref INVALID (this is the default value), then 
     
    9791003  /// Thus you can iterate through each arc from \c u to \c v as it follows. 
    9801004  ///\code 
    981   /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) { 
     1005  /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) { 
    9821006  ///   ... 
    9831007  /// } 
    9841008  ///\endcode 
    9851009  /// 
    986   ///\sa ArcLookUp 
    987   ///\sa AllArcLookUp 
    988   ///\sa DynArcLookUp 
     1010  /// \note \ref ConArcIt provides iterator interface for the same 
     1011  /// functionality. 
     1012  /// 
    9891013  ///\sa ConArcIt 
     1014  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp 
    9901015  template <typename Graph> 
    9911016  inline typename Graph::Arc 
     
    9951020  } 
    9961021 
    997   /// \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 
     1022  /// \brief Iterator for iterating on parallel arcs connecting the same nodes. 
     1023  /// 
     1024  /// Iterator for iterating on parallel arcs connecting the same nodes. It is 
     1025  /// a higher level interface for the \ref findArc() function. You can 
    10011026  /// use it the following way: 
    10021027  ///\code 
     
    10071032  /// 
    10081033  ///\sa findArc() 
    1009   ///\sa ArcLookUp 
    1010   ///\sa AllArcLookUp 
    1011   ///\sa DynArcLookUp 
     1034  ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp 
    10121035  template <typename _Graph> 
    10131036  class ConArcIt : public _Graph::Arc { 
     
    10221045    /// \brief Constructor. 
    10231046    /// 
    1024     /// Construct a new ConArcIt iterating on the arcs which 
    1025     /// connects the \c u and \c v node. 
     1047    /// Construct a new ConArcIt iterating on the arcs that 
     1048    /// connects nodes \c u and \c v. 
    10261049    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) { 
    10271050      Parent::operator=(findArc(_graph, u, v)); 
     
    10301053    /// \brief Constructor. 
    10311054    /// 
    1032     /// Construct a new ConArcIt which continues the iterating from 
    1033     /// the \c e arc. 
     1055    /// Construct a new ConArcIt that continues the iterating from arc \c a. 
    10341056    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {} 
    10351057 
     
    10921114  } 
    10931115 
    1094   /// \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 
     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 edge 
    10981120  /// will be enumerated once. 
    10991121  /// 
    11001122  /// If \c prev is \ref INVALID (this is the default value), then 
    1101   /// it finds the first arc from \c u to \c v. Otherwise it looks for 
    1102   /// the next arc from \c u to \c v after \c prev. 
    1103   /// \return The found arc or \ref INVALID if there is no such an arc. 
    1104   /// 
    1105   /// Thus you can iterate through each arc from \c u to \c v as it follows. 
     1123  /// it finds the first edge from \c u to \c v. Otherwise it looks for 
     1124  /// the next edge from \c u to \c v after \c prev. 
     1125  /// \return The found edge or \ref INVALID if there is no such an edge. 
     1126  /// 
     1127  /// Thus you can iterate through each edge between \c u and \c v 
     1128  /// as it follows. 
    11061129  ///\code 
    1107   /// for(Edge e = findEdge(g,u,v); e != INVALID; 
    1108   ///     e = findEdge(g,u,v,e)) { 
     1130  /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) { 
    11091131  ///   ... 
    11101132  /// } 
    11111133  ///\endcode 
    11121134  /// 
     1135  /// \note \ref ConEdgeIt provides iterator interface for the same 
     1136  /// functionality. 
     1137  /// 
    11131138  ///\sa ConEdgeIt 
    1114  
    11151139  template <typename Graph> 
    11161140  inline typename Graph::Edge 
     
    11201144  } 
    11211145 
    1122   /// \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 
     1146  /// \brief Iterator for iterating on parallel edges connecting the same nodes. 
     1147  /// 
     1148  /// Iterator for iterating on parallel edges connecting the same nodes. 
     1149  /// It is a higher level interface for the findEdge() function. You can 
    11261150  /// use it the following way: 
    11271151  ///\code 
    1128   /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) { 
     1152  /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) { 
    11291153  ///   ... 
    11301154  /// } 
     
    11441168    /// \brief Constructor. 
    11451169    /// 
    1146     /// Construct a new ConEdgeIt iterating on the edges which 
    1147     /// connects the \c u and \c v node. 
     1170    /// Construct a new ConEdgeIt iterating on the edges that 
     1171    /// connects nodes \c u and \c v. 
    11481172    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) { 
    11491173      Parent::operator=(findEdge(_graph, u, v)); 
     
    11521176    /// \brief Constructor. 
    11531177    /// 
    1154     /// Construct a new ConEdgeIt which continues the iterating from 
    1155     /// the \c e edge. 
     1178    /// Construct a new ConEdgeIt that continues iterating from edge \c e. 
    11561179    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {} 
    11571180 
     
    11691192 
    11701193 
    1171   ///Dynamic arc look up between given endpoints. 
     1194  ///Dynamic arc look-up between given endpoints. 
    11721195 
    11731196  ///Using this class, you can find an arc in a digraph from a given 
    1174   ///source to a given target in amortized time <em>O(log</em>d<em>)</em>, 
     1197  ///source to a given target in amortized time <em>O</em>(log<em>d</em>), 
    11751198  ///where <em>d</em> is the out-degree of the source node. 
    11761199  /// 
     
    11781201  ///the \c operator() member. 
    11791202  /// 
    1180   ///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 
     1203  ///This is a dynamic data structure. Consider to use \ref ArcLookUp or 
     1204  ///\ref AllArcLookUp if your digraph is not changed so frequently. 
     1205  /// 
     1206  ///This class uses a self-adjusting binary search tree, the Splay tree 
     1207  ///of Sleator and Tarjan to guarantee the logarithmic amortized 
     1208  ///time bound for arc look-ups. This class also guarantees the 
    11861209  ///optimal time bound in a constant factor for any distribution of 
    11871210  ///queries. 
     
    15081531 
    15091532    ///Find an arc between two nodes. 
    1510     ///\param s The source node 
    1511     ///\param t The target node 
     1533    ///\param s The source node. 
     1534    ///\param t The target node. 
    15121535    ///\param p The previous arc between \c s and \c t. It it is INVALID or 
    15131536    ///not given, the operator finds the first appropriate arc. 
     
    15201543    ///DynArcLookUp<ListDigraph> ae(g); 
    15211544    ///... 
    1522     ///int n=0; 
    1523     ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++; 
     1545    ///int n = 0; 
     1546    ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++; 
    15241547    ///\endcode 
    15251548    /// 
    1526     ///Finding the arcs take at most <em>O(</em>log<em>d)</em> 
     1549    ///Finding the arcs take at most <em>O</em>(log<em>d</em>) 
    15271550    ///amortized time, specifically, the time complexity of the lookups 
    15281551    ///is equal to the optimal search tree implementation for the 
     
    15301553    /// 
    15311554    ///\note This is a dynamic data structure, therefore the data 
    1532     ///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 
     1555    ///structure is updated after each graph alteration. Thus although 
     1556    ///this data structure is theoretically faster than \ref ArcLookUp 
     1557    ///and \ref AllArcLookup, it often provides worse performance than 
    15351558    ///them. 
    1536     /// 
    15371559    Arc operator()(Node s, Node t, Arc p = INVALID) const  { 
    15381560      if (p == INVALID) { 
     
    15861608  }; 
    15871609 
    1588   ///Fast arc look up between given endpoints. 
     1610  ///Fast arc look-up between given endpoints. 
    15891611 
    15901612  ///Using this class, you can find an arc in a digraph from a given 
    1591   ///source to a given target in time <em>O(log d)</em>, 
     1613  ///source to a given target in time <em>O</em>(log<em>d</em>), 
    15921614  ///where <em>d</em> is the out-degree of the source node. 
    15931615  /// 
     
    15951617  ///Use \ref AllArcLookUp for this purpose. 
    15961618  /// 
    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). 
     1619  ///\warning This class is static, so you should call refresh() (or at 
     1620  ///least refresh(Node)) to refresh this data structure whenever the 
     1621  ///digraph changes. This is a time consuming (superlinearly proportional 
     1622  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 
    16011623  /// 
    16021624  ///\tparam G The type of the underlying digraph. 
     
    16471669    } 
    16481670  public: 
    1649     ///Refresh the data structure at a node. 
     1671    ///Refresh the search data structure at a node. 
    16501672 
    16511673    ///Build up the search database of node \c n. 
    16521674    /// 
    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. 
     1675    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> 
     1676    ///is the number of the outgoing arcs of \c n. 
    16551677    void refresh(Node n) 
    16561678    { 
     
    16681690    ///\ref refresh(Node) "refresh(n)" for each node \c n. 
    16691691    /// 
    1670     ///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 
     1692    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is 
     1693    ///the number of the arcs in the digraph and <em>D</em> is the maximum 
    16721694    ///out-degree of the digraph. 
    1673  
    16741695    void refresh() 
    16751696    { 
     
    16791700    ///Find an arc between two nodes. 
    16801701 
    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 
     1702    ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>), where 
     1703    ///<em>d</em> is the number of outgoing arcs of \c s. 
     1704    ///\param s The source node. 
     1705    ///\param t The target node. 
    16851706    ///\return An arc from \c s to \c t if there exists, 
    16861707    ///\ref INVALID otherwise. 
     
    16881709    ///\warning If you change the digraph, refresh() must be called before using 
    16891710    ///this operator. If you change the outgoing arcs of 
    1690     ///a single node \c n, then 
    1691     ///\ref refresh(Node) "refresh(n)" is enough. 
    1692     /// 
     1711    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. 
    16931712    Arc operator()(Node s, Node t) const 
    16941713    { 
     
    17021721  }; 
    17031722 
    1704   ///Fast look up of all arcs between given endpoints. 
     1723  ///Fast look-up of all arcs between given endpoints. 
    17051724 
    17061725  ///This class is the same as \ref ArcLookUp, with the addition 
    1707   ///that it makes it possible to find all arcs between given endpoints. 
    1708   /// 
    1709   ///\warning This class is static, so you should refresh() (or at least 
    1710   ///refresh(Node)) this data structure 
    1711   ///whenever the digraph changes. This is a time consuming (superlinearly 
    1712   ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs). 
     1726  ///that it makes it possible to find all parallel arcs between given 
     1727  ///endpoints. 
     1728  /// 
     1729  ///\warning This class is static, so you should call refresh() (or at 
     1730  ///least refresh(Node)) to refresh this data structure whenever the 
     1731  ///digraph changes. This is a time consuming (superlinearly proportional 
     1732  ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 
    17131733  /// 
    17141734  ///\tparam G The type of the underlying digraph. 
     
    17341754      else { 
    17351755        next=refreshNext(_right[head],next); 
    1736 //         _next[head]=next; 
    17371756        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head)) 
    17381757          ? next : INVALID; 
     
    17591778    ///Build up the search database of node \c n. 
    17601779    /// 
    1761     ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is 
     1780    ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is 
    17621781    ///the number of the outgoing arcs of \c n. 
    1763  
    17641782    void refresh(Node n) 
    17651783    { 
     
    17731791    ///\ref refresh(Node) "refresh(n)" for each node \c n. 
    17741792    /// 
    1775     ///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 
     1793    ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is 
     1794    ///the number of the arcs in the digraph and <em>D</em> is the maximum 
    17771795    ///out-degree of the digraph. 
    1778  
    17791796    void refresh() 
    17801797    { 
     
    17851802 
    17861803    ///Find an arc between two nodes. 
    1787     ///\param s The source node 
    1788     ///\param t The target node 
     1804    ///\param s The source node. 
     1805    ///\param t The target node. 
    17891806    ///\param prev The previous arc between \c s and \c t. It it is INVALID or 
    17901807    ///not given, the operator finds the first appropriate arc. 
     
    17971814    ///AllArcLookUp<ListDigraph> ae(g); 
    17981815    ///... 
    1799     ///int n=0; 
    1800     ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++; 
     1816    ///int n = 0; 
     1817    ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++; 
    18011818    ///\endcode 
    18021819    /// 
    1803     ///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 
     1820    ///Finding the first arc take <em>O</em>(log<em>d</em>) time, where 
     1821    ///<em>d</em> is the number of outgoing arcs of \c s. Then, the 
    18051822    ///consecutive arcs are found in constant time. 
    18061823    /// 
    18071824    ///\warning If you change the digraph, refresh() must be called before using 
    18081825    ///this operator. If you change the outgoing arcs of 
    1809     ///a single node \c n, then 
    1810     ///\ref refresh(Node) "refresh(n)" is enough. 
     1826    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. 
    18111827    /// 
    18121828#ifdef DOXYGEN 
  • test/graph_copy_test.cc

    r220 r282  
    6464  ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to); 
    6565 
    66   DigraphCopy<ListDigraph, SmartDigraph>(to, from). 
    67     nodeMap(tnm, fnm).arcMap(tam, fam). 
     66  digraphCopy(from, to). 
     67    nodeMap(fnm, tnm).arcMap(fam, tam). 
    6868    nodeRef(nr).arcRef(er). 
    6969    nodeCrossRef(ncr).arcCrossRef(ecr). 
    70     node(tn, fn).arc(ta, fa).run(); 
     70    node(fn, tn).arc(fa, ta).run(); 
    7171 
    7272  for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) { 
     
    139139  ListGraph::EdgeMap<SmartGraph::Edge> ecr(to); 
    140140 
    141   GraphCopy<ListGraph, SmartGraph>(to, from). 
    142     nodeMap(tnm, fnm).arcMap(tam, fam).edgeMap(tem, fem). 
     141  graphCopy(from, to). 
     142    nodeMap(fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem). 
    143143    nodeRef(nr).arcRef(ar).edgeRef(er). 
    144144    nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr). 
    145     node(tn, fn).arc(ta, fa).edge(te, fe).run(); 
     145    node(fn, tn).arc(fa, ta).edge(fe, te).run(); 
    146146 
    147147  for (SmartGraph::NodeIt it(from); it != INVALID; ++it) { 
Note: See TracChangeset for help on using the changeset viewer.