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
Phase:
public
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.