COIN-OR::LEMON - Graph Library

Changes in / [287:bb40b6db0a58:286:da414906fe21] in lemon-1.0


Ignore:
Files:
18 edited

Legend:

Unmodified
Added
Removed
  • lemon/bfs.h

    r287 r286  
    5555    ///\param g is the digraph, to which we would like to define the
    5656    ///\ref PredMap.
     57    ///\todo The digraph alone may be insufficient to initialize
    5758    static PredMap *createPredMap(const Digraph &g)
    5859    {
     
    6465    ///The type of the map that indicates which nodes are processed.
    6566    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     67    ///By default it is a NullMap.
    6668    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6769    ///Instantiates a \ref ProcessedMap.
     
    195197    int _curr_dist;
    196198
    197     //Creates the maps if necessary.
     199    ///Creates the maps if necessary.
     200    ///\todo Better memory allocation (instead of new).
    198201    void create_maps()
    199202    {
     
    846849    ///\param g is the digraph, to which we would like to define the
    847850    ///\ref PredMap.
     851    ///\todo The digraph alone may be insufficient to initialize
    848852    static PredMap *createPredMap(const Digraph &g)
    849853    {
     
    13671371    int _list_front, _list_back;
    13681372
    1369     //Creates the maps if necessary.
     1373    ///Creates the maps if necessary.
     1374    ///\todo Better memory allocation (instead of new).
    13701375    void create_maps() {
    13711376      if(!_reached) {
  • lemon/bits/base_extender.h

    r280 r256  
    106106    /// Returns whether the given directed arc has the same orientation
    107107    /// 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?"
    108111    static bool direction(const Arc &a) { return a.forward; }
    109112
  • lemon/bits/vector_map.h

    r280 r263  
    4343  /// the map. This map type uses the std::vector to store the values.
    4444  ///
    45   /// \tparam _Graph The graph this map is attached to.
     45  /// \tparam _Notifier The AlterationNotifier that will notify this map.
    4646  /// \tparam _Item The item type of the graph items.
    4747  /// \tparam _Value The value type of the map.
     48  /// \todo Fix the doc: there is _Graph parameter instead of _Notifier.
    4849  template <typename _Graph, typename _Item, typename _Value>
    4950  class VectorMap
  • lemon/concept_check.h

    r285 r209  
    1717 */
    1818
    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.
    2135
    2236///\file
    2337///\brief Basic utilities for concept checking.
    2438///
     39///\todo Are we still using BOOST concept checking utility?
     40///Is the BOOST copyright notice necessary?
    2541
    2642#ifndef LEMON_CONCEPT_CHECK_H
  • lemon/concepts/path.h

    r281 r278  
    2121///\brief Classes for representing paths in digraphs.
    2222///
     23///\todo Iterators have obsolete style
    2324
    2425#ifndef LEMON_CONCEPT_PATH_H
  • lemon/core.h

    r282 r233  
    5959  /// @{
    6060
    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,
     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,
    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   ///Create convenient typedefs for the digraph types and iterators
     83  typedef Digraph::ArcMap<double> DoubleArcMap
     84
     85  ///Creates convenience 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   ///Create convenient typedefs for the graph types and iterators
    106 
    107   ///This \c \#define creates the same convenient type definitions as defined
     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
    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_GRAPH_TYPEDEFS()
     113  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_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   ///Create convenient typedefs for the graph types and iterators
     122  typedef Graph::EdgeMap<double> DoubleEdgeMap
     123
     124  ///Creates convenience 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 a graph.
    140   ///
    141   /// This function counts the items (nodes, arcs etc.) in a graph.
    142   /// The complexity of the function is linear because
     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
    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 <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
     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
    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 <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
     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
    220220  /// function to query the cardinality of the arc set.
    221221  template <typename Graph>
     
    225225
    226226  // Edge counting:
    227 
    228227  namespace _core_bits {
    229228
     
    249248  ///
    250249  /// This function counts the edges in the graph.
    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
     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
    256255  /// function to query the cardinality of the edge set.
    257256  template <typename Graph>
     
    274273  ///
    275274  /// This function counts the number of the out-arcs from node \c n
    276   /// in the graph \c g.
     275  /// in the graph.
    277276  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);
    280279  }
    281280
     
    283282  ///
    284283  /// This function counts the number of the in-arcs to node \c n
    285   /// in the graph \c g.
     284  /// in the graph.
    286285  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);
    289288  }
    290289
     
    292291  ///
    293292  /// This function counts the number of the inc-edges to node \c n
    294   /// in the undirected graph \c g.
     293  /// in the graph.
    295294  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);
    298297  }
    299298
     
    309308
    310309    template <typename Digraph, typename Item, typename RefMap,
    311               typename FromMap, typename ToMap>
     310              typename ToMap, typename FromMap>
    312311    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
    313312    public:
    314313
    315       MapCopy(const FromMap& map, ToMap& tmap)
    316         : _map(map), _tmap(tmap) {}
     314      MapCopy(ToMap& tmap, const FromMap& map)
     315        : _tmap(tmap), _map(map) {}
    317316
    318317      virtual void copy(const Digraph& digraph, const RefMap& refMap) {
     
    324323
    325324    private:
     325      ToMap& _tmap;
    326326      const FromMap& _map;
    327       ToMap& _tmap;
    328327    };
    329328
     
    332331    public:
    333332
    334       ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
     333      ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
    335334
    336335      virtual void copy(const Digraph&, const RefMap& refMap) {
     
    339338
    340339    private:
     340      It& _it;
    341341      Item _item;
    342       It& _it;
    343342    };
    344343
     
    381380    struct DigraphCopySelector {
    382381      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,
    384383                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
    385384        for (typename From::NodeIt it(from); it != INVALID; ++it) {
     
    399398    {
    400399      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,
    402401                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
    403402        to.build(from, nodeRefMap, arcRefMap);
     
    408407    struct GraphCopySelector {
    409408      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,
    411410                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
    412411        for (typename From::NodeIt it(from); it != INVALID; ++it) {
     
    426425    {
    427426      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,
    429428                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
    430429        to.build(from, nodeRefMap, edgeRefMap);
     
    437436  ///
    438437  /// 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 create
     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
    442441  /// references and cross references between the nodes and arcs of
    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
     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
    448447  /// assigned to copy. In the end, the \c run() member should be
    449448  /// called.
    450449  ///
    451   /// The next code copies a digraph with several data:
     450  /// The next code copies a graph with several data:
    452451  ///\code
    453   ///  DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
    454   ///  // Create references for the nodes
     452  ///  DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
     453  ///  // create a reference for the nodes
    455454  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
    456   ///  cg.nodeRef(nr);
    457   ///  // Create cross references (inverse) for the arcs
     455  ///  dc.nodeRef(nr);
     456  ///  // create a cross reference (inverse) for the arcs
    458457  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
    459   ///  cg.arcCrossRef(acr);
    460   ///  // Copy an arc map
     458  ///  dc.arcCrossRef(acr);
     459  ///  // copy an arc map
    461460  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
    462461  ///  NewGraph::ArcMap<double> namap(new_graph);
    463   ///  cg.arcMap(oamap, namap);
    464   ///  // Copy a node
     462  ///  dc.arcMap(namap, oamap);
     463  ///  // copy a node
    465464  ///  OrigGraph::Node on;
    466465  ///  NewGraph::Node nn;
    467   ///  cg.node(on, nn);
    468   ///  // Execute copying
    469   ///  cg.run();
     466  ///  dc.node(nn, on);
     467  ///  // Executions of copy
     468  ///  dc.run();
    470469  ///\endcode
    471   template <typename From, typename To>
     470  template <typename To, typename From>
    472471  class DigraphCopy {
    473472  private:
     
    484483    typedef typename From::template ArcMap<TArc> ArcRefMap;
    485484
     485
    486486  public:
    487487
    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)
    493494      : _from(from), _to(to) {}
    494495
    495     /// \brief Destructor of DigraphCopy
    496     ///
    497     /// Destructor of DigraphCopy.
     496    /// \brief Destructor of the DigraphCopy
     497    ///
     498    /// Destructor of the DigraphCopy
    498499    ~DigraphCopy() {
    499500      for (int i = 0; i < int(_node_maps.size()); ++i) {
     
    506507    }
    507508
    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.
     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.
    514515    template <typename NodeRef>
    515516    DigraphCopy& nodeRef(NodeRef& map) {
     
    519520    }
    520521
    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.
     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.
    527528    template <typename NodeCrossRef>
    528529    DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
     
    532533    }
    533534
    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) {
    543542      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
    544                            NodeRefMap, FromMap, ToMap>(map, tmap));
     543                           NodeRefMap, ToMap, FromMap>(tmap, map));
    545544      return *this;
    546545    }
     
    548547    /// \brief Make a copy of the given node.
    549548    ///
    550     /// This function makes a 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) {
    552551      _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.
    563559    template <typename ArcRef>
    564560    DigraphCopy& arcRef(ArcRef& map) {
     
    568564    }
    569565
    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.
    576570    template <typename ArcCrossRef>
    577571    DigraphCopy& arcCrossRef(ArcCrossRef& map) {
     
    581575    }
    582576
    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) {
    592585      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
    593                           ArcRefMap, FromMap, ToMap>(map, tmap));
     586                          ArcRefMap, ToMap, FromMap>(tmap, map));
    594587      return *this;
    595588    }
     
    597590    /// \brief Make a copy of the given arc.
    598591    ///
    599     /// This function makes a 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) {
    601594      _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.
    610602    void run() {
    611603      NodeRefMap nodeRefMap(_from);
    612604      ArcRefMap arcRefMap(_from);
    613605      _core_bits::DigraphCopySelector<To>::
    614         copy(_from, _to, nodeRefMap, arcRefMap);
     606        copy(_to, _from, nodeRefMap, arcRefMap);
    615607      for (int i = 0; i < int(_node_maps.size()); ++i) {
    616608        _node_maps[i]->copy(_from, nodeRefMap);
     
    623615  protected:
    624616
     617
    625618    const From& _from;
    626619    To& _to;
    627620
    628621    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
    629       _node_maps;
     622    _node_maps;
    630623
    631624    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
    632       _arc_maps;
     625    _arc_maps;
    633626
    634627  };
     
    636629  /// \brief Copy a digraph to another digraph.
    637630  ///
    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:
     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:
    641634  ///\code
    642   /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
     635  /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
    643636  ///\endcode
    644637  ///
    645638  /// After the copy the \c nr map will contain the mapping from the
    646639  /// 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 digraph
     640  /// \c ecr will contain the mapping from the arcs of the \c to digraph
    648641  /// to the arcs of the \c from digraph.
    649642  ///
    650643  /// \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);
    654647  }
    655648
     
    657650  ///
    658651  /// 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 only make a copy of a graph, but it can create
     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
    662655  /// references and cross references between the nodes, edges and arcs of
    663   /// the two graphs, and it can copy maps for using with the newly created
    664   /// graph.
     656  /// the two graphs, it can copy maps for use with the newly created
     657  /// graph and copy nodes, edges and arcs.
    665658  ///
    666659  /// To make a copy from a graph, first an instance of GraphCopy
     
    671664  /// The next code copies a graph with several data:
    672665  ///\code
    673   ///  GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
    674   ///  // Create references for the nodes
     666  ///  GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
     667  ///  // create a reference for the nodes
    675668  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
    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
     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
    685678  ///  OrigGraph::Node on;
    686679  ///  NewGraph::Node nn;
    687   ///  cg.node(on, nn);
    688   ///  // Execute copying
    689   ///  cg.run();
     680  ///  dc.node(nn, on);
     681  ///  // Executions of copy
     682  ///  dc.run();
    690683  ///\endcode
    691   template <typename From, typename To>
     684  template <typename To, typename From>
    692685  class GraphCopy {
    693686  private:
     
    708701
    709702    struct ArcRefMap {
    710       ArcRefMap(const From& from, const To& to,
     703      ArcRefMap(const To& to, const From& from,
    711704                const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
    712         : _from(from), _to(to),
     705        : _to(to), _from(from),
    713706          _edge_ref(edge_ref), _node_ref(node_ref) {}
    714707
     
    724717      }
    725718
     719      const To& _to;
    726720      const From& _from;
    727       const To& _to;
    728721      const EdgeRefMap& _edge_ref;
    729722      const NodeRefMap& _node_ref;
    730723    };
    731724
     725
    732726  public:
    733727
    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)
    739734      : _from(from), _to(to) {}
    740735
    741     /// \brief Destructor of GraphCopy
    742     ///
    743     /// Destructor of GraphCopy.
     736    /// \brief Destructor of the GraphCopy
     737    ///
     738    /// Destructor of the GraphCopy
    744739    ~GraphCopy() {
    745740      for (int i = 0; i < int(_node_maps.size()); ++i) {
     
    752747        delete _edge_maps[i];
    753748      }
    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.
    762755    template <typename NodeRef>
    763756    GraphCopy& nodeRef(NodeRef& map) {
     
    767760    }
    768761
    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.
    775766    template <typename NodeCrossRef>
    776767    GraphCopy& nodeCrossRef(NodeCrossRef& map) {
     
    780771    }
    781772
    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) {
    791781      _node_maps.push_back(new _core_bits::MapCopy<From, Node,
    792                            NodeRefMap, FromMap, ToMap>(map, tmap));
     782                           NodeRefMap, ToMap, FromMap>(tmap, map));
    793783      return *this;
    794784    }
     
    796786    /// \brief Make a copy of the given node.
    797787    ///
    798     /// This function makes a 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) {
    800790      _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.
    811798    template <typename ArcRef>
    812799    GraphCopy& arcRef(ArcRef& map) {
     
    816803    }
    817804
    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.
    824809    template <typename ArcCrossRef>
    825810    GraphCopy& arcCrossRef(ArcCrossRef& map) {
     
    829814    }
    830815
    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) {
    840824      _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
    841                           ArcRefMap, FromMap, ToMap>(map, tmap));
     825                          ArcRefMap, ToMap, FromMap>(tmap, map));
    842826      return *this;
    843827    }
     
    845829    /// \brief Make a copy of the given arc.
    846830    ///
    847     /// This function makes a 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) {
    849833      _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.
    860841    template <typename EdgeRef>
    861842    GraphCopy& edgeRef(EdgeRef& map) {
     
    865846    }
    866847
    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.
    873852    template <typename EdgeCrossRef>
    874853    GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
     
    878857    }
    879858
    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) {
    889867      _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
    890                            EdgeRefMap, FromMap, ToMap>(map, tmap));
     868                           EdgeRefMap, ToMap, FromMap>(tmap, map));
    891869      return *this;
    892870    }
     
    894872    /// \brief Make a copy of the given edge.
    895873    ///
    896     /// This function makes a 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) {
    898876      _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.
    907884    void run() {
    908885      NodeRefMap nodeRefMap(_from);
    909886      EdgeRefMap edgeRefMap(_from);
    910       ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
     887      ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
    911888      _core_bits::GraphCopySelector<To>::
    912         copy(_from, _to, nodeRefMap, edgeRefMap);
     889        copy(_to, _from, nodeRefMap, edgeRefMap);
    913890      for (int i = 0; i < int(_node_maps.size()); ++i) {
    914891        _node_maps[i]->copy(_from, nodeRefMap);
     
    928905
    929906    std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
    930       _node_maps;
     907    _node_maps;
    931908
    932909    std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
    933       _arc_maps;
     910    _arc_maps;
    934911
    935912    std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
    936       _edge_maps;
     913    _edge_maps;
    937914
    938915  };
     
    940917  /// \brief Copy a graph to another graph.
    941918  ///
    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:
     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:
    945922  ///\code
    946   /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
     923  /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
    947924  ///\endcode
    948925  ///
    949926  /// After the copy the \c nr map will contain the mapping from the
    950927  /// 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 graph
    952   /// 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.
    953930  ///
    954931  /// \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);
    959936  }
    960937
     
    981958    struct FindArcSelector<
    982959      Graph,
    983       typename enable_if<typename Graph::FindArcTag, void>::type>
     960      typename enable_if<typename Graph::FindEdgeTag, void>::type>
    984961    {
    985962      typedef typename Graph::Node Node;
     
    991968  }
    992969
    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.
    997973  ///
    998974  /// If \c prev is \ref INVALID (this is the default value), then
     
    1003979  /// Thus you can iterate through each arc from \c u to \c v as it follows.
    1004980  ///\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)) {
    1006982  ///   ...
    1007983  /// }
    1008984  ///\endcode
    1009985  ///
    1010   /// \note \ref ConArcIt provides iterator interface for the same
    1011   /// functionality.
    1012   ///
     986  ///\sa ArcLookUp
     987  ///\sa AllArcLookUp
     988  ///\sa DynArcLookUp
    1013989  ///\sa ConArcIt
    1014   ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
    1015990  template <typename Graph>
    1016991  inline typename Graph::Arc
     
    1020995  }
    1021996
    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
     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
    10261001  /// use it the following way:
    10271002  ///\code
     
    10321007  ///
    10331008  ///\sa findArc()
    1034   ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
     1009  ///\sa ArcLookUp
     1010  ///\sa AllArcLookUp
     1011  ///\sa DynArcLookUp
    10351012  template <typename _Graph>
    10361013  class ConArcIt : public _Graph::Arc {
     
    10451022    /// \brief Constructor.
    10461023    ///
    1047     /// Construct a new ConArcIt iterating on the arcs that
    1048     /// 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.
    10491026    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
    10501027      Parent::operator=(findArc(_graph, u, v));
     
    10531030    /// \brief Constructor.
    10541031    ///
    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.
    10561034    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
    10571035
     
    11141092  }
    11151093
    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
     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
    11201098  /// will be enumerated once.
    11211099  ///
    11221100  /// 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.
    11291106  ///\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)) {
    11311109  ///   ...
    11321110  /// }
    11331111  ///\endcode
    11341112  ///
    1135   /// \note \ref ConEdgeIt provides iterator interface for the same
    1136   /// functionality.
    1137   ///
    11381113  ///\sa ConEdgeIt
     1114
    11391115  template <typename Graph>
    11401116  inline typename Graph::Edge
     
    11441120  }
    11451121
    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
     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
    11501126  /// use it the following way:
    11511127  ///\code
    1152   /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
     1128  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
    11531129  ///   ...
    11541130  /// }
     
    11681144    /// \brief Constructor.
    11691145    ///
    1170     /// Construct a new ConEdgeIt iterating on the edges that
    1171     /// 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.
    11721148    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
    11731149      Parent::operator=(findEdge(_graph, u, v));
     
    11761152    /// \brief Constructor.
    11771153    ///
    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.
    11791156    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
    11801157
     
    11921169
    11931170
    1194   ///Dynamic arc look-up between given endpoints.
     1171  ///Dynamic arc look up between given endpoints.
    11951172
    11961173  ///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>,
    11981175  ///where <em>d</em> is the out-degree of the source node.
    11991176  ///
     
    12011178  ///the \c operator() member.
    12021179  ///
    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
     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
    12091186  ///optimal time bound in a constant factor for any distribution of
    12101187  ///queries.
     
    15311508
    15321509    ///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
    15351512    ///\param p The previous arc between \c s and \c t. It it is INVALID or
    15361513    ///not given, the operator finds the first appropriate arc.
     
    15431520    ///DynArcLookUp<ListDigraph> ae(g);
    15441521    ///...
    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++;
    15471524    ///\endcode
    15481525    ///
    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>
    15501527    ///amortized time, specifically, the time complexity of the lookups
    15511528    ///is equal to the optimal search tree implementation for the
     
    15531530    ///
    15541531    ///\note This is a dynamic data structure, therefore the data
    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
     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
    15581535    ///them.
     1536    ///
    15591537    Arc operator()(Node s, Node t, Arc p = INVALID) const  {
    15601538      if (p == INVALID) {
     
    16081586  };
    16091587
    1610   ///Fast arc look-up between given endpoints.
     1588  ///Fast arc look up between given endpoints.
    16111589
    16121590  ///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>,
    16141592  ///where <em>d</em> is the out-degree of the source node.
    16151593  ///
     
    16171595  ///Use \ref AllArcLookUp for this purpose.
    16181596  ///
    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).
     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).
    16231601  ///
    16241602  ///\tparam G The type of the underlying digraph.
     
    16691647    }
    16701648  public:
    1671     ///Refresh the search data structure at a node.
     1649    ///Refresh the data structure at a node.
    16721650
    16731651    ///Build up the search database of node \c n.
    16741652    ///
    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.
     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.
    16771655    void refresh(Node n)
    16781656    {
     
    16901668    ///\ref refresh(Node) "refresh(n)" for each node \c n.
    16911669    ///
    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
     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
    16941672    ///out-degree of the digraph.
     1673
    16951674    void refresh()
    16961675    {
     
    17001679    ///Find an arc between two nodes.
    17011680
    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.
     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
    17061685    ///\return An arc from \c s to \c t if there exists,
    17071686    ///\ref INVALID otherwise.
     
    17091688    ///\warning If you change the digraph, refresh() must be called before using
    17101689    ///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    ///
    17121693    Arc operator()(Node s, Node t) const
    17131694    {
     
    17211702  };
    17221703
    1723   ///Fast look-up of all arcs between given endpoints.
     1704  ///Fast look up of all arcs between given endpoints.
    17241705
    17251706  ///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).
    17331713  ///
    17341714  ///\tparam G The type of the underlying digraph.
     
    17541734      else {
    17551735        next=refreshNext(_right[head],next);
     1736//         _next[head]=next;
    17561737        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
    17571738          ? next : INVALID;
     
    17781759    ///Build up the search database of node \c n.
    17791760    ///
    1780     ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
     1761    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
    17811762    ///the number of the outgoing arcs of \c n.
     1763
    17821764    void refresh(Node n)
    17831765    {
     
    17911773    ///\ref refresh(Node) "refresh(n)" for each node \c n.
    17921774    ///
    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
     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
    17951777    ///out-degree of the digraph.
     1778
    17961779    void refresh()
    17971780    {
     
    18021785
    18031786    ///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
    18061789    ///\param prev The previous arc between \c s and \c t. It it is INVALID or
    18071790    ///not given, the operator finds the first appropriate arc.
     
    18141797    ///AllArcLookUp<ListDigraph> ae(g);
    18151798    ///...
    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++;
    18181801    ///\endcode
    18191802    ///
    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
     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
    18221805    ///consecutive arcs are found in constant time.
    18231806    ///
    18241807    ///\warning If you change the digraph, refresh() must be called before using
    18251808    ///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.
    18271811    ///
    18281812#ifdef DOXYGEN
  • lemon/dfs.h

    r287 r286  
    5656    ///\param g is the digraph, to which we would like to define the
    5757    ///\ref PredMap.
     58    ///\todo The digraph alone may be insufficient to initialize
    5859    static PredMap *createPredMap(const Digraph &g)
    5960    {
     
    6566    ///The type of the map that indicates which nodes are processed.
    6667    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     68    ///By default it is a NullMap.
    6769    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6870    ///Instantiates a \ref ProcessedMap.
     
    195197    int _stack_head;
    196198
    197     //Creates the maps if necessary.
     199    ///Creates the maps if necessary.
     200    ///\todo Better memory allocation (instead of new).
    198201    void create_maps()
    199202    {
     
    780783    ///\param g is the digraph, to which we would like to define the
    781784    ///\ref PredMap.
     785    ///\todo The digraph alone may be insufficient to initialize
    782786    static PredMap *createPredMap(const Digraph &g)
    783787    {
     
    13141318    int _stack_head;
    13151319
    1316     //Creates the maps if necessary.
     1320    ///Creates the maps if necessary.
     1321    ///\todo Better memory allocation (instead of new).
    13171322    void create_maps() {
    13181323      if(!_reached) {
  • lemon/dijkstra.h

    r287 r286  
    145145    ///\param g is the digraph, to which we would like to define the
    146146    ///\ref PredMap.
     147    ///\todo The digraph alone may be insufficient for the initialization
    147148    static PredMap *createPredMap(const Digraph &g)
    148149    {
     
    155156    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    156157    ///By default it is a NullMap.
     158    ///\todo If it is set to a real map,
     159    ///Dijkstra::processed() should read this.
    157160    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    158161    ///Instantiates a \ref ProcessedMap.
     
    295298    bool local_heap;
    296299
    297     //Creates the maps if necessary.
     300    ///Creates the maps if necessary.
     301    ///\todo Better memory allocation (instead of new).
    298302    void create_maps()
    299303    {
     
    962966    /// \param g is the digraph, to which we would like to define the
    963967    /// HeapCrossRef.
     968    /// \todo The digraph alone may be insufficient for the initialization
    964969    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
    965970    {
     
    9971002    ///\param g is the digraph, to which we would like to define the
    9981003    ///\ref PredMap.
     1004    ///\todo The digraph alone may be insufficient to initialize
    9991005    static PredMap *createPredMap(const Digraph &g)
    10001006    {
     
    10071013    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    10081014    ///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.
    10091018    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    10101019    ///Instantiates a \ref ProcessedMap.
     
    10521061  /// The \ref DijkstraWizardBase is a class to be the default traits of the
    10531062  /// \ref DijkstraWizard class.
     1063  /// \todo More named parameters are required...
    10541064  template<class GR,class LM>
    10551065  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
  • lemon/error.h

    r280 r212  
    103103    ///\e
    104104
     105    ///\todo The good solution is boost::shared_ptr...
     106    ///
    105107    mutable std::auto_ptr<std::ostringstream> buf;
    106108
  • lemon/graph_to_eps.h

    r280 r253  
    667667  ///it draws the graph.
    668668  void run() {
     669    //\todo better 'epsilon' would be nice here.
    669670    const double EPSILON=1e-9;
    670671    if(dontPrint) return;
     
    707708      for(ArcIt e(g);e!=INVALID;++e)
    708709        max_w=std::max(double(_arcWidths[e]),max_w);
     710      //\todo better 'epsilon' would be nice here.
    709711      if(max_w>EPSILON) {
    710712        _arcWidthScale/=max_w;
     
    716718      for(NodeIt n(g);n!=INVALID;++n)
    717719        max_s=std::max(double(_nodeSizes[n]),max_s);
     720      //\todo better 'epsilon' would be nice here.
    718721      if(max_s>EPSILON) {
    719722        _nodeScale/=max_s;
     
    871874      }
    872875      else {
     876        //\todo Verify centering
    873877        double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.width(),
    874878                  (A4WIDTH-2*A4BORDER)/bb.height());
     
    903907            dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]);
    904908          double l=std::sqrt(dvec.normSquare());
     909          //\todo better 'epsilon' would be nice here.
    905910          dim2::Point<double> d(dvec/std::max(l,EPSILON));
    906911          dim2::Point<double> m;
  • lemon/list_graph.h

    r280 r239  
    502502    ///be invalidated.
    503503    ///
    504     ///\warning This functionality cannot be used in conjunction with the
     504    ///\warning This functionality cannot be used together with the
    505505    ///Snapshot feature.
     506    ///
     507    ///\todo It could be implemented in a bit faster way.
    506508    Node split(Node n, bool connect = true) {
    507509      Node b = addNode();
  • lemon/maps.h

    r280 r220  
    485485  ///
    486486  /// \sa CombineMap
     487  ///
     488  /// \todo Check the requirements.
    487489  template <typename M1, typename M2>
    488490  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
     
    539541  ///
    540542  /// \sa ComposeMap
     543  ///
     544  /// \todo Check the requirements.
    541545  template<typename M1, typename M2, typename F,
    542546           typename V = typename F::result_type>
  • lemon/random.h

    r280 r209  
    822822    /// \note The Cartesian form of the Box-Muller
    823823    /// transformation is used to generate a random normal distribution.
     824    /// \todo Consider using the "ziggurat" method instead.
    824825    double gauss()
    825826    {
  • lemon/smart_graph.h

    r280 r238  
    301301    ///\warning This functionality cannot be used together with the Snapshot
    302302    ///feature.
     303    ///\todo It could be implemented in a bit faster way.
    303304    Node split(Node n, bool connect = true)
    304305    {
  • lemon/time_measure.h

    r280 r210  
    293293  ///function, consider the usage of \ref TimeReport instead.
    294294  ///
     295  ///\todo This shouldn't be Unix (Linux) specific.
    295296  ///\sa TimeReport
    296297  class Timer
     
    487488  ///\sa Timer
    488489  ///\sa NoTimeReport
     490  ///\todo There is no test case for this
    489491  class TimeReport : public Timer
    490492  {
  • lemon/tolerance.h

    r280 r209  
    2525///floating point numbers.
    2626///
     27///\todo It should be in a module like "Basic tools"
     28
    2729
    2830namespace lemon {
  • scripts/chg-len.py

    r284 r272  
    1010"""
    1111    exit(0)
    12 plist = os.popen("HGRCPATH='' hg parents --template='{rev}\n'").readlines()
     12plist = os.popen("hg parents --template='{rev}\n'").readlines()
    1313if len(plist)>1:
    1414    print "You are in the process of merging"
     
    1616PAR = int(plist[0])
    1717
    18 f = os.popen("HGRCPATH='' hg log -r 0:tip --template='{rev} {parents}\n'").\
    19     readlines()
     18f = os.popen("hg log -r 0:tip --template='{rev} {parents}\n'").readlines()
    2019REV = -1
    2120lengths=[]
  • test/graph_copy_test.cc

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