1.1 --- a/lemon/core.h Tue Sep 23 18:42:49 2008 +0200
1.2 +++ b/lemon/core.h Fri Sep 26 13:46:49 2008 +0200
1.3 @@ -58,10 +58,10 @@
1.4 /// \addtogroup gutils
1.5 /// @{
1.6
1.7 - ///Creates convenience typedefs for the digraph types and iterators
1.8 + ///Create convenient typedefs for the digraph types and iterators
1.9
1.10 - ///This \c \#define creates convenience typedefs for the following types
1.11 - ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
1.12 + ///This \c \#define creates convenient type definitions for the following
1.13 + ///types of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
1.14 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
1.15 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
1.16 ///
1.17 @@ -80,9 +80,9 @@
1.18 typedef Digraph::NodeMap<double> DoubleNodeMap; \
1.19 typedef Digraph::ArcMap<bool> BoolArcMap; \
1.20 typedef Digraph::ArcMap<int> IntArcMap; \
1.21 - typedef Digraph::ArcMap<double> DoubleArcMap
1.22 + typedef Digraph::ArcMap<double> DoubleArcMap;
1.23
1.24 - ///Creates convenience typedefs for the digraph types and iterators
1.25 + ///Create convenient typedefs for the digraph types and iterators
1.26
1.27 ///\see DIGRAPH_TYPEDEFS
1.28 ///
1.29 @@ -100,17 +100,17 @@
1.30 typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
1.31 typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
1.32 typedef typename Digraph::template ArcMap<int> IntArcMap; \
1.33 - typedef typename Digraph::template ArcMap<double> DoubleArcMap
1.34 + typedef typename Digraph::template ArcMap<double> DoubleArcMap;
1.35
1.36 - ///Creates convenience typedefs for the graph types and iterators
1.37 + ///Create convenient typedefs for the graph types and iterators
1.38
1.39 - ///This \c \#define creates the same convenience typedefs as defined
1.40 + ///This \c \#define creates the same convenient type definitions as defined
1.41 ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
1.42 ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
1.43 ///\c DoubleEdgeMap.
1.44 ///
1.45 ///\note If the graph type is a dependent type, ie. the graph type depend
1.46 - ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
1.47 + ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
1.48 ///macro.
1.49 #define GRAPH_TYPEDEFS(Graph) \
1.50 DIGRAPH_TYPEDEFS(Graph); \
1.51 @@ -119,9 +119,9 @@
1.52 typedef Graph::IncEdgeIt IncEdgeIt; \
1.53 typedef Graph::EdgeMap<bool> BoolEdgeMap; \
1.54 typedef Graph::EdgeMap<int> IntEdgeMap; \
1.55 - typedef Graph::EdgeMap<double> DoubleEdgeMap
1.56 + typedef Graph::EdgeMap<double> DoubleEdgeMap;
1.57
1.58 - ///Creates convenience typedefs for the graph types and iterators
1.59 + ///Create convenient typedefs for the graph types and iterators
1.60
1.61 ///\see GRAPH_TYPEDEFS
1.62 ///
1.63 @@ -134,12 +134,12 @@
1.64 typedef typename Graph::IncEdgeIt IncEdgeIt; \
1.65 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
1.66 typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
1.67 - typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
1.68 + typedef typename Graph::template EdgeMap<double> DoubleEdgeMap;
1.69
1.70 - /// \brief Function to count the items in the graph.
1.71 + /// \brief Function to count the items in a graph.
1.72 ///
1.73 - /// This function counts the items (nodes, arcs etc) in the graph.
1.74 - /// The complexity of the function is O(n) because
1.75 + /// This function counts the items (nodes, arcs etc.) in a graph.
1.76 + /// The complexity of the function is linear because
1.77 /// it iterates on all of the items.
1.78 template <typename Graph, typename Item>
1.79 inline int countItems(const Graph& g) {
1.80 @@ -176,11 +176,11 @@
1.81 /// \brief Function to count the nodes in the graph.
1.82 ///
1.83 /// This function counts the nodes in the graph.
1.84 - /// The complexity of the function is O(n) but for some
1.85 - /// graph structures it is specialized to run in O(1).
1.86 + /// The complexity of the function is <em>O</em>(<em>n</em>), but for some
1.87 + /// graph structures it is specialized to run in <em>O</em>(1).
1.88 ///
1.89 - /// If the graph contains a \e nodeNum() member function and a
1.90 - /// \e NodeNumTag tag then this function calls directly the member
1.91 + /// \note If the graph contains a \c nodeNum() member function and a
1.92 + /// \c NodeNumTag tag then this function calls directly the member
1.93 /// function to query the cardinality of the node set.
1.94 template <typename Graph>
1.95 inline int countNodes(const Graph& g) {
1.96 @@ -212,11 +212,11 @@
1.97 /// \brief Function to count the arcs in the graph.
1.98 ///
1.99 /// This function counts the arcs in the graph.
1.100 - /// The complexity of the function is O(e) but for some
1.101 - /// graph structures it is specialized to run in O(1).
1.102 + /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
1.103 + /// graph structures it is specialized to run in <em>O</em>(1).
1.104 ///
1.105 - /// If the graph contains a \e arcNum() member function and a
1.106 - /// \e EdgeNumTag tag then this function calls directly the member
1.107 + /// \note If the graph contains a \c arcNum() member function and a
1.108 + /// \c ArcNumTag tag then this function calls directly the member
1.109 /// function to query the cardinality of the arc set.
1.110 template <typename Graph>
1.111 inline int countArcs(const Graph& g) {
1.112 @@ -224,6 +224,7 @@
1.113 }
1.114
1.115 // Edge counting:
1.116 +
1.117 namespace _core_bits {
1.118
1.119 template <typename Graph, typename Enable = void>
1.120 @@ -247,11 +248,11 @@
1.121 /// \brief Function to count the edges in the graph.
1.122 ///
1.123 /// This function counts the edges in the graph.
1.124 - /// The complexity of the function is O(m) but for some
1.125 - /// graph structures it is specialized to run in O(1).
1.126 + /// The complexity of the function is <em>O</em>(<em>m</em>), but for some
1.127 + /// graph structures it is specialized to run in <em>O</em>(1).
1.128 ///
1.129 - /// If the graph contains a \e edgeNum() member function and a
1.130 - /// \e EdgeNumTag tag then this function calls directly the member
1.131 + /// \note If the graph contains a \c edgeNum() member function and a
1.132 + /// \c EdgeNumTag tag then this function calls directly the member
1.133 /// function to query the cardinality of the edge set.
1.134 template <typename Graph>
1.135 inline int countEdges(const Graph& g) {
1.136 @@ -272,28 +273,28 @@
1.137 /// \brief Function to count the number of the out-arcs from node \c n.
1.138 ///
1.139 /// This function counts the number of the out-arcs from node \c n
1.140 - /// in the graph.
1.141 + /// in the graph \c g.
1.142 template <typename Graph>
1.143 - inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {
1.144 - return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
1.145 + inline int countOutArcs(const Graph& g, const typename Graph::Node& n) {
1.146 + return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);
1.147 }
1.148
1.149 /// \brief Function to count the number of the in-arcs to node \c n.
1.150 ///
1.151 /// This function counts the number of the in-arcs to node \c n
1.152 - /// in the graph.
1.153 + /// in the graph \c g.
1.154 template <typename Graph>
1.155 - inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {
1.156 - return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
1.157 + inline int countInArcs(const Graph& g, const typename Graph::Node& n) {
1.158 + return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);
1.159 }
1.160
1.161 /// \brief Function to count the number of the inc-edges to node \c n.
1.162 ///
1.163 /// This function counts the number of the inc-edges to node \c n
1.164 - /// in the graph.
1.165 + /// in the undirected graph \c g.
1.166 template <typename Graph>
1.167 - inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
1.168 - return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
1.169 + inline int countIncEdges(const Graph& g, const typename Graph::Node& n) {
1.170 + return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);
1.171 }
1.172
1.173 namespace _core_bits {
1.174 @@ -307,12 +308,12 @@
1.175 };
1.176
1.177 template <typename Digraph, typename Item, typename RefMap,
1.178 - typename ToMap, typename FromMap>
1.179 + typename FromMap, typename ToMap>
1.180 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
1.181 public:
1.182
1.183 - MapCopy(ToMap& tmap, const FromMap& map)
1.184 - : _tmap(tmap), _map(map) {}
1.185 + MapCopy(const FromMap& map, ToMap& tmap)
1.186 + : _map(map), _tmap(tmap) {}
1.187
1.188 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
1.189 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
1.190 @@ -322,23 +323,23 @@
1.191 }
1.192
1.193 private:
1.194 + const FromMap& _map;
1.195 ToMap& _tmap;
1.196 - const FromMap& _map;
1.197 };
1.198
1.199 template <typename Digraph, typename Item, typename RefMap, typename It>
1.200 class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
1.201 public:
1.202
1.203 - ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
1.204 + ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
1.205
1.206 virtual void copy(const Digraph&, const RefMap& refMap) {
1.207 _it = refMap[_item];
1.208 }
1.209
1.210 private:
1.211 + Item _item;
1.212 It& _it;
1.213 - Item _item;
1.214 };
1.215
1.216 template <typename Digraph, typename Item, typename RefMap, typename Ref>
1.217 @@ -379,7 +380,7 @@
1.218 template <typename Digraph, typename Enable = void>
1.219 struct DigraphCopySelector {
1.220 template <typename From, typename NodeRefMap, typename ArcRefMap>
1.221 - static void copy(Digraph &to, const From& from,
1.222 + static void copy(const From& from, Digraph &to,
1.223 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
1.224 for (typename From::NodeIt it(from); it != INVALID; ++it) {
1.225 nodeRefMap[it] = to.addNode();
1.226 @@ -397,7 +398,7 @@
1.227 typename enable_if<typename Digraph::BuildTag, void>::type>
1.228 {
1.229 template <typename From, typename NodeRefMap, typename ArcRefMap>
1.230 - static void copy(Digraph &to, const From& from,
1.231 + static void copy(const From& from, Digraph &to,
1.232 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
1.233 to.build(from, nodeRefMap, arcRefMap);
1.234 }
1.235 @@ -406,7 +407,7 @@
1.236 template <typename Graph, typename Enable = void>
1.237 struct GraphCopySelector {
1.238 template <typename From, typename NodeRefMap, typename EdgeRefMap>
1.239 - static void copy(Graph &to, const From& from,
1.240 + static void copy(const From& from, Graph &to,
1.241 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
1.242 for (typename From::NodeIt it(from); it != INVALID; ++it) {
1.243 nodeRefMap[it] = to.addNode();
1.244 @@ -424,7 +425,7 @@
1.245 typename enable_if<typename Graph::BuildTag, void>::type>
1.246 {
1.247 template <typename From, typename NodeRefMap, typename EdgeRefMap>
1.248 - static void copy(Graph &to, const From& from,
1.249 + static void copy(const From& from, Graph &to,
1.250 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
1.251 to.build(from, nodeRefMap, edgeRefMap);
1.252 }
1.253 @@ -435,39 +436,39 @@
1.254 /// \brief Class to copy a digraph.
1.255 ///
1.256 /// Class to copy a digraph to another digraph (duplicate a digraph). The
1.257 - /// simplest way of using it is through the \c copyDigraph() function.
1.258 + /// simplest way of using it is through the \c digraphCopy() function.
1.259 ///
1.260 - /// This class not just make a copy of a graph, but it can create
1.261 + /// This class not only make a copy of a digraph, but it can create
1.262 /// references and cross references between the nodes and arcs of
1.263 - /// the two graphs, it can copy maps for use with the newly created
1.264 - /// graph and copy nodes and arcs.
1.265 + /// the two digraphs, and it can copy maps to use with the newly created
1.266 + /// digraph.
1.267 ///
1.268 - /// To make a copy from a graph, first an instance of DigraphCopy
1.269 - /// should be created, then the data belongs to the graph should
1.270 + /// To make a copy from a digraph, first an instance of DigraphCopy
1.271 + /// should be created, then the data belongs to the digraph should
1.272 /// assigned to copy. In the end, the \c run() member should be
1.273 /// called.
1.274 ///
1.275 - /// The next code copies a graph with several data:
1.276 + /// The next code copies a digraph with several data:
1.277 ///\code
1.278 - /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
1.279 - /// // create a reference for the nodes
1.280 + /// DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
1.281 + /// // Create references for the nodes
1.282 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
1.283 - /// dc.nodeRef(nr);
1.284 - /// // create a cross reference (inverse) for the arcs
1.285 + /// cg.nodeRef(nr);
1.286 + /// // Create cross references (inverse) for the arcs
1.287 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
1.288 - /// dc.arcCrossRef(acr);
1.289 - /// // copy an arc map
1.290 + /// cg.arcCrossRef(acr);
1.291 + /// // Copy an arc map
1.292 /// OrigGraph::ArcMap<double> oamap(orig_graph);
1.293 /// NewGraph::ArcMap<double> namap(new_graph);
1.294 - /// dc.arcMap(namap, oamap);
1.295 - /// // copy a node
1.296 + /// cg.arcMap(oamap, namap);
1.297 + /// // Copy a node
1.298 /// OrigGraph::Node on;
1.299 /// NewGraph::Node nn;
1.300 - /// dc.node(nn, on);
1.301 - /// // Executions of copy
1.302 - /// dc.run();
1.303 + /// cg.node(on, nn);
1.304 + /// // Execute copying
1.305 + /// cg.run();
1.306 ///\endcode
1.307 - template <typename To, typename From>
1.308 + template <typename From, typename To>
1.309 class DigraphCopy {
1.310 private:
1.311
1.312 @@ -482,20 +483,18 @@
1.313 typedef typename From::template NodeMap<TNode> NodeRefMap;
1.314 typedef typename From::template ArcMap<TArc> ArcRefMap;
1.315
1.316 -
1.317 public:
1.318
1.319 -
1.320 - /// \brief Constructor for the DigraphCopy.
1.321 + /// \brief Constructor of DigraphCopy.
1.322 ///
1.323 - /// It copies the content of the \c _from digraph into the
1.324 - /// \c _to digraph.
1.325 - DigraphCopy(To& to, const From& from)
1.326 + /// Constructor of DigraphCopy for copying the content of the
1.327 + /// \c from digraph into the \c to digraph.
1.328 + DigraphCopy(const From& from, To& to)
1.329 : _from(from), _to(to) {}
1.330
1.331 - /// \brief Destructor of the DigraphCopy
1.332 + /// \brief Destructor of DigraphCopy
1.333 ///
1.334 - /// Destructor of the DigraphCopy
1.335 + /// Destructor of DigraphCopy.
1.336 ~DigraphCopy() {
1.337 for (int i = 0; i < int(_node_maps.size()); ++i) {
1.338 delete _node_maps[i];
1.339 @@ -506,12 +505,12 @@
1.340
1.341 }
1.342
1.343 - /// \brief Copies the node references into the given map.
1.344 + /// \brief Copy the node references into the given map.
1.345 ///
1.346 - /// Copies the node references into the given map. The parameter
1.347 - /// should be a map, which key type is the Node type of the source
1.348 - /// graph, while the value type is the Node type of the
1.349 - /// destination graph.
1.350 + /// This function copies the node references into the given map.
1.351 + /// The parameter should be a map, whose key type is the Node type of
1.352 + /// the source digraph, while the value type is the Node type of the
1.353 + /// destination digraph.
1.354 template <typename NodeRef>
1.355 DigraphCopy& nodeRef(NodeRef& map) {
1.356 _node_maps.push_back(new _core_bits::RefCopy<From, Node,
1.357 @@ -519,12 +518,12 @@
1.358 return *this;
1.359 }
1.360
1.361 - /// \brief Copies the node cross references into the given map.
1.362 + /// \brief Copy the node cross references into the given map.
1.363 ///
1.364 - /// Copies the node cross references (reverse references) into
1.365 - /// the given map. The parameter should be a map, which key type
1.366 - /// is the Node type of the destination graph, while the value type is
1.367 - /// the Node type of the source graph.
1.368 + /// This function copies the node cross references (reverse references)
1.369 + /// into the given map. The parameter should be a map, whose key type
1.370 + /// is the Node type of the destination digraph, while the value type is
1.371 + /// the Node type of the source digraph.
1.372 template <typename NodeCrossRef>
1.373 DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.374 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
1.375 @@ -532,30 +531,35 @@
1.376 return *this;
1.377 }
1.378
1.379 - /// \brief Make copy of the given map.
1.380 + /// \brief Make a copy of the given node map.
1.381 ///
1.382 - /// Makes copy of the given map for the newly created digraph.
1.383 - /// The new map's key type is the destination graph's node type,
1.384 - /// and the copied map's key type is the source graph's node type.
1.385 - template <typename ToMap, typename FromMap>
1.386 - DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1.387 + /// This function makes a copy of the given node map for the newly
1.388 + /// created digraph.
1.389 + /// The key type of the new map \c tmap should be the Node type of the
1.390 + /// destination digraph, and the key type of the original map \c map
1.391 + /// should be the Node type of the source digraph.
1.392 + template <typename FromMap, typename ToMap>
1.393 + DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
1.394 _node_maps.push_back(new _core_bits::MapCopy<From, Node,
1.395 - NodeRefMap, ToMap, FromMap>(tmap, map));
1.396 + NodeRefMap, FromMap, ToMap>(map, tmap));
1.397 return *this;
1.398 }
1.399
1.400 /// \brief Make a copy of the given node.
1.401 ///
1.402 - /// Make a copy of the given node.
1.403 - DigraphCopy& node(TNode& tnode, const Node& snode) {
1.404 + /// This function makes a copy of the given node.
1.405 + DigraphCopy& node(const Node& node, TNode& tnode) {
1.406 _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
1.407 - NodeRefMap, TNode>(tnode, snode));
1.408 + NodeRefMap, TNode>(node, tnode));
1.409 return *this;
1.410 }
1.411
1.412 - /// \brief Copies the arc references into the given map.
1.413 + /// \brief Copy the arc references into the given map.
1.414 ///
1.415 - /// Copies the arc references into the given map.
1.416 + /// This function copies the arc references into the given map.
1.417 + /// The parameter should be a map, whose key type is the Arc type of
1.418 + /// the source digraph, while the value type is the Arc type of the
1.419 + /// destination digraph.
1.420 template <typename ArcRef>
1.421 DigraphCopy& arcRef(ArcRef& map) {
1.422 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
1.423 @@ -563,10 +567,12 @@
1.424 return *this;
1.425 }
1.426
1.427 - /// \brief Copies the arc cross references into the given map.
1.428 + /// \brief Copy the arc cross references into the given map.
1.429 ///
1.430 - /// Copies the arc cross references (reverse references) into
1.431 - /// the given map.
1.432 + /// This function copies the arc cross references (reverse references)
1.433 + /// into the given map. The parameter should be a map, whose key type
1.434 + /// is the Arc type of the destination digraph, while the value type is
1.435 + /// the Arc type of the source digraph.
1.436 template <typename ArcCrossRef>
1.437 DigraphCopy& arcCrossRef(ArcCrossRef& map) {
1.438 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
1.439 @@ -574,36 +580,38 @@
1.440 return *this;
1.441 }
1.442
1.443 - /// \brief Make copy of the given map.
1.444 + /// \brief Make a copy of the given arc map.
1.445 ///
1.446 - /// Makes copy of the given map for the newly created digraph.
1.447 - /// The new map's key type is the to digraph's arc type,
1.448 - /// and the copied map's key type is the from digraph's arc
1.449 - /// type.
1.450 - template <typename ToMap, typename FromMap>
1.451 - DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1.452 + /// This function makes a copy of the given arc map for the newly
1.453 + /// created digraph.
1.454 + /// The key type of the new map \c tmap should be the Arc type of the
1.455 + /// destination digraph, and the key type of the original map \c map
1.456 + /// should be the Arc type of the source digraph.
1.457 + template <typename FromMap, typename ToMap>
1.458 + DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
1.459 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
1.460 - ArcRefMap, ToMap, FromMap>(tmap, map));
1.461 + ArcRefMap, FromMap, ToMap>(map, tmap));
1.462 return *this;
1.463 }
1.464
1.465 /// \brief Make a copy of the given arc.
1.466 ///
1.467 - /// Make a copy of the given arc.
1.468 - DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
1.469 + /// This function makes a copy of the given arc.
1.470 + DigraphCopy& arc(const Arc& arc, TArc& tarc) {
1.471 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
1.472 - ArcRefMap, TArc>(tarc, sarc));
1.473 + ArcRefMap, TArc>(arc, tarc));
1.474 return *this;
1.475 }
1.476
1.477 - /// \brief Executes the copies.
1.478 + /// \brief Execute copying.
1.479 ///
1.480 - /// Executes the copies.
1.481 + /// This function executes the copying of the digraph along with the
1.482 + /// copying of the assigned data.
1.483 void run() {
1.484 NodeRefMap nodeRefMap(_from);
1.485 ArcRefMap arcRefMap(_from);
1.486 _core_bits::DigraphCopySelector<To>::
1.487 - copy(_to, _from, nodeRefMap, arcRefMap);
1.488 + copy(_from, _to, nodeRefMap, arcRefMap);
1.489 for (int i = 0; i < int(_node_maps.size()); ++i) {
1.490 _node_maps[i]->copy(_from, nodeRefMap);
1.491 }
1.492 @@ -614,47 +622,46 @@
1.493
1.494 protected:
1.495
1.496 -
1.497 const From& _from;
1.498 To& _to;
1.499
1.500 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.501 - _node_maps;
1.502 + _node_maps;
1.503
1.504 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.505 - _arc_maps;
1.506 + _arc_maps;
1.507
1.508 };
1.509
1.510 /// \brief Copy a digraph to another digraph.
1.511 ///
1.512 - /// Copy a digraph to another digraph. The complete usage of the
1.513 - /// function is detailed in the DigraphCopy class, but a short
1.514 - /// example shows a basic work:
1.515 + /// This function copies a digraph to another digraph.
1.516 + /// The complete usage of it is detailed in the DigraphCopy class, but
1.517 + /// a short example shows a basic work:
1.518 ///\code
1.519 - /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1.520 + /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
1.521 ///\endcode
1.522 ///
1.523 /// After the copy the \c nr map will contain the mapping from the
1.524 /// nodes of the \c from digraph to the nodes of the \c to digraph and
1.525 - /// \c ecr will contain the mapping from the arcs of the \c to digraph
1.526 + /// \c acr will contain the mapping from the arcs of the \c to digraph
1.527 /// to the arcs of the \c from digraph.
1.528 ///
1.529 /// \see DigraphCopy
1.530 - template <typename To, typename From>
1.531 - DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
1.532 - return DigraphCopy<To, From>(to, from);
1.533 + template <typename From, typename To>
1.534 + DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
1.535 + return DigraphCopy<From, To>(from, to);
1.536 }
1.537
1.538 /// \brief Class to copy a graph.
1.539 ///
1.540 /// Class to copy a graph to another graph (duplicate a graph). The
1.541 - /// simplest way of using it is through the \c copyGraph() function.
1.542 + /// simplest way of using it is through the \c graphCopy() function.
1.543 ///
1.544 - /// This class not just make a copy of a graph, but it can create
1.545 + /// This class not only make a copy of a graph, but it can create
1.546 /// references and cross references between the nodes, edges and arcs of
1.547 - /// the two graphs, it can copy maps for use with the newly created
1.548 - /// graph and copy nodes, edges and arcs.
1.549 + /// the two graphs, and it can copy maps for using with the newly created
1.550 + /// graph.
1.551 ///
1.552 /// To make a copy from a graph, first an instance of GraphCopy
1.553 /// should be created, then the data belongs to the graph should
1.554 @@ -663,25 +670,25 @@
1.555 ///
1.556 /// The next code copies a graph with several data:
1.557 ///\code
1.558 - /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
1.559 - /// // create a reference for the nodes
1.560 + /// GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
1.561 + /// // Create references for the nodes
1.562 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
1.563 - /// dc.nodeRef(nr);
1.564 - /// // create a cross reference (inverse) for the edges
1.565 - /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
1.566 - /// dc.edgeCrossRef(ecr);
1.567 - /// // copy an arc map
1.568 - /// OrigGraph::ArcMap<double> oamap(orig_graph);
1.569 - /// NewGraph::ArcMap<double> namap(new_graph);
1.570 - /// dc.arcMap(namap, oamap);
1.571 - /// // copy a node
1.572 + /// cg.nodeRef(nr);
1.573 + /// // Create cross references (inverse) for the edges
1.574 + /// NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);
1.575 + /// cg.edgeCrossRef(ecr);
1.576 + /// // Copy an edge map
1.577 + /// OrigGraph::EdgeMap<double> oemap(orig_graph);
1.578 + /// NewGraph::EdgeMap<double> nemap(new_graph);
1.579 + /// cg.edgeMap(oemap, nemap);
1.580 + /// // Copy a node
1.581 /// OrigGraph::Node on;
1.582 /// NewGraph::Node nn;
1.583 - /// dc.node(nn, on);
1.584 - /// // Executions of copy
1.585 - /// dc.run();
1.586 + /// cg.node(on, nn);
1.587 + /// // Execute copying
1.588 + /// cg.run();
1.589 ///\endcode
1.590 - template <typename To, typename From>
1.591 + template <typename From, typename To>
1.592 class GraphCopy {
1.593 private:
1.594
1.595 @@ -700,9 +707,9 @@
1.596 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
1.597
1.598 struct ArcRefMap {
1.599 - ArcRefMap(const To& to, const From& from,
1.600 + ArcRefMap(const From& from, const To& to,
1.601 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
1.602 - : _to(to), _from(from),
1.603 + : _from(from), _to(to),
1.604 _edge_ref(edge_ref), _node_ref(node_ref) {}
1.605
1.606 typedef typename From::Arc Key;
1.607 @@ -716,26 +723,24 @@
1.608 return _to.direct(_edge_ref[key], forward);
1.609 }
1.610
1.611 + const From& _from;
1.612 const To& _to;
1.613 - const From& _from;
1.614 const EdgeRefMap& _edge_ref;
1.615 const NodeRefMap& _node_ref;
1.616 };
1.617
1.618 -
1.619 public:
1.620
1.621 -
1.622 - /// \brief Constructor for the GraphCopy.
1.623 + /// \brief Constructor of GraphCopy.
1.624 ///
1.625 - /// It copies the content of the \c _from graph into the
1.626 - /// \c _to graph.
1.627 - GraphCopy(To& to, const From& from)
1.628 + /// Constructor of GraphCopy for copying the content of the
1.629 + /// \c from graph into the \c to graph.
1.630 + GraphCopy(const From& from, To& to)
1.631 : _from(from), _to(to) {}
1.632
1.633 - /// \brief Destructor of the GraphCopy
1.634 + /// \brief Destructor of GraphCopy
1.635 ///
1.636 - /// Destructor of the GraphCopy
1.637 + /// Destructor of GraphCopy.
1.638 ~GraphCopy() {
1.639 for (int i = 0; i < int(_node_maps.size()); ++i) {
1.640 delete _node_maps[i];
1.641 @@ -746,12 +751,14 @@
1.642 for (int i = 0; i < int(_edge_maps.size()); ++i) {
1.643 delete _edge_maps[i];
1.644 }
1.645 -
1.646 }
1.647
1.648 - /// \brief Copies the node references into the given map.
1.649 + /// \brief Copy the node references into the given map.
1.650 ///
1.651 - /// Copies the node references into the given map.
1.652 + /// This function copies the node references into the given map.
1.653 + /// The parameter should be a map, whose key type is the Node type of
1.654 + /// the source graph, while the value type is the Node type of the
1.655 + /// destination graph.
1.656 template <typename NodeRef>
1.657 GraphCopy& nodeRef(NodeRef& map) {
1.658 _node_maps.push_back(new _core_bits::RefCopy<From, Node,
1.659 @@ -759,10 +766,12 @@
1.660 return *this;
1.661 }
1.662
1.663 - /// \brief Copies the node cross references into the given map.
1.664 + /// \brief Copy the node cross references into the given map.
1.665 ///
1.666 - /// Copies the node cross references (reverse references) into
1.667 - /// the given map.
1.668 + /// This function copies the node cross references (reverse references)
1.669 + /// into the given map. The parameter should be a map, whose key type
1.670 + /// is the Node type of the destination graph, while the value type is
1.671 + /// the Node type of the source graph.
1.672 template <typename NodeCrossRef>
1.673 GraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.674 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
1.675 @@ -770,31 +779,35 @@
1.676 return *this;
1.677 }
1.678
1.679 - /// \brief Make copy of the given map.
1.680 + /// \brief Make a copy of the given node map.
1.681 ///
1.682 - /// Makes copy of the given map for the newly created graph.
1.683 - /// The new map's key type is the to graph's node type,
1.684 - /// and the copied map's key type is the from graph's node
1.685 - /// type.
1.686 - template <typename ToMap, typename FromMap>
1.687 - GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1.688 + /// This function makes a copy of the given node map for the newly
1.689 + /// created graph.
1.690 + /// The key type of the new map \c tmap should be the Node type of the
1.691 + /// destination graph, and the key type of the original map \c map
1.692 + /// should be the Node type of the source graph.
1.693 + template <typename FromMap, typename ToMap>
1.694 + GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
1.695 _node_maps.push_back(new _core_bits::MapCopy<From, Node,
1.696 - NodeRefMap, ToMap, FromMap>(tmap, map));
1.697 + NodeRefMap, FromMap, ToMap>(map, tmap));
1.698 return *this;
1.699 }
1.700
1.701 /// \brief Make a copy of the given node.
1.702 ///
1.703 - /// Make a copy of the given node.
1.704 - GraphCopy& node(TNode& tnode, const Node& snode) {
1.705 + /// This function makes a copy of the given node.
1.706 + GraphCopy& node(const Node& node, TNode& tnode) {
1.707 _node_maps.push_back(new _core_bits::ItemCopy<From, Node,
1.708 - NodeRefMap, TNode>(tnode, snode));
1.709 + NodeRefMap, TNode>(node, tnode));
1.710 return *this;
1.711 }
1.712
1.713 - /// \brief Copies the arc references into the given map.
1.714 + /// \brief Copy the arc references into the given map.
1.715 ///
1.716 - /// Copies the arc references into the given map.
1.717 + /// This function copies the arc references into the given map.
1.718 + /// The parameter should be a map, whose key type is the Arc type of
1.719 + /// the source graph, while the value type is the Arc type of the
1.720 + /// destination graph.
1.721 template <typename ArcRef>
1.722 GraphCopy& arcRef(ArcRef& map) {
1.723 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
1.724 @@ -802,10 +815,12 @@
1.725 return *this;
1.726 }
1.727
1.728 - /// \brief Copies the arc cross references into the given map.
1.729 + /// \brief Copy the arc cross references into the given map.
1.730 ///
1.731 - /// Copies the arc cross references (reverse references) into
1.732 - /// the given map.
1.733 + /// This function copies the arc cross references (reverse references)
1.734 + /// into the given map. The parameter should be a map, whose key type
1.735 + /// is the Arc type of the destination graph, while the value type is
1.736 + /// the Arc type of the source graph.
1.737 template <typename ArcCrossRef>
1.738 GraphCopy& arcCrossRef(ArcCrossRef& map) {
1.739 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
1.740 @@ -813,31 +828,35 @@
1.741 return *this;
1.742 }
1.743
1.744 - /// \brief Make copy of the given map.
1.745 + /// \brief Make a copy of the given arc map.
1.746 ///
1.747 - /// Makes copy of the given map for the newly created graph.
1.748 - /// The new map's key type is the to graph's arc type,
1.749 - /// and the copied map's key type is the from graph's arc
1.750 - /// type.
1.751 - template <typename ToMap, typename FromMap>
1.752 - GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1.753 + /// This function makes a copy of the given arc map for the newly
1.754 + /// created graph.
1.755 + /// The key type of the new map \c tmap should be the Arc type of the
1.756 + /// destination graph, and the key type of the original map \c map
1.757 + /// should be the Arc type of the source graph.
1.758 + template <typename FromMap, typename ToMap>
1.759 + GraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
1.760 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
1.761 - ArcRefMap, ToMap, FromMap>(tmap, map));
1.762 + ArcRefMap, FromMap, ToMap>(map, tmap));
1.763 return *this;
1.764 }
1.765
1.766 /// \brief Make a copy of the given arc.
1.767 ///
1.768 - /// Make a copy of the given arc.
1.769 - GraphCopy& arc(TArc& tarc, const Arc& sarc) {
1.770 + /// This function makes a copy of the given arc.
1.771 + GraphCopy& arc(const Arc& arc, TArc& tarc) {
1.772 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
1.773 - ArcRefMap, TArc>(tarc, sarc));
1.774 + ArcRefMap, TArc>(arc, tarc));
1.775 return *this;
1.776 }
1.777
1.778 - /// \brief Copies the edge references into the given map.
1.779 + /// \brief Copy the edge references into the given map.
1.780 ///
1.781 - /// Copies the edge references into the given map.
1.782 + /// This function copies the edge references into the given map.
1.783 + /// The parameter should be a map, whose key type is the Edge type of
1.784 + /// the source graph, while the value type is the Edge type of the
1.785 + /// destination graph.
1.786 template <typename EdgeRef>
1.787 GraphCopy& edgeRef(EdgeRef& map) {
1.788 _edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
1.789 @@ -845,10 +864,12 @@
1.790 return *this;
1.791 }
1.792
1.793 - /// \brief Copies the edge cross references into the given map.
1.794 + /// \brief Copy the edge cross references into the given map.
1.795 ///
1.796 - /// Copies the edge cross references (reverse
1.797 - /// references) into the given map.
1.798 + /// This function copies the edge cross references (reverse references)
1.799 + /// into the given map. The parameter should be a map, whose key type
1.800 + /// is the Edge type of the destination graph, while the value type is
1.801 + /// the Edge type of the source graph.
1.802 template <typename EdgeCrossRef>
1.803 GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.804 _edge_maps.push_back(new _core_bits::CrossRefCopy<From,
1.805 @@ -856,37 +877,39 @@
1.806 return *this;
1.807 }
1.808
1.809 - /// \brief Make copy of the given map.
1.810 + /// \brief Make a copy of the given edge map.
1.811 ///
1.812 - /// Makes copy of the given map for the newly created graph.
1.813 - /// The new map's key type is the to graph's edge type,
1.814 - /// and the copied map's key type is the from graph's edge
1.815 - /// type.
1.816 - template <typename ToMap, typename FromMap>
1.817 - GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
1.818 + /// This function makes a copy of the given edge map for the newly
1.819 + /// created graph.
1.820 + /// The key type of the new map \c tmap should be the Edge type of the
1.821 + /// destination graph, and the key type of the original map \c map
1.822 + /// should be the Edge type of the source graph.
1.823 + template <typename FromMap, typename ToMap>
1.824 + GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
1.825 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
1.826 - EdgeRefMap, ToMap, FromMap>(tmap, map));
1.827 + EdgeRefMap, FromMap, ToMap>(map, tmap));
1.828 return *this;
1.829 }
1.830
1.831 /// \brief Make a copy of the given edge.
1.832 ///
1.833 - /// Make a copy of the given edge.
1.834 - GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1.835 + /// This function makes a copy of the given edge.
1.836 + GraphCopy& edge(const Edge& edge, TEdge& tedge) {
1.837 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
1.838 - EdgeRefMap, TEdge>(tedge, sedge));
1.839 + EdgeRefMap, TEdge>(edge, tedge));
1.840 return *this;
1.841 }
1.842
1.843 - /// \brief Executes the copies.
1.844 + /// \brief Execute copying.
1.845 ///
1.846 - /// Executes the copies.
1.847 + /// This function executes the copying of the graph along with the
1.848 + /// copying of the assigned data.
1.849 void run() {
1.850 NodeRefMap nodeRefMap(_from);
1.851 EdgeRefMap edgeRefMap(_from);
1.852 - ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
1.853 + ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
1.854 _core_bits::GraphCopySelector<To>::
1.855 - copy(_to, _from, nodeRefMap, edgeRefMap);
1.856 + copy(_from, _to, nodeRefMap, edgeRefMap);
1.857 for (int i = 0; i < int(_node_maps.size()); ++i) {
1.858 _node_maps[i]->copy(_from, nodeRefMap);
1.859 }
1.860 @@ -904,35 +927,35 @@
1.861 To& _to;
1.862
1.863 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.864 - _node_maps;
1.865 + _node_maps;
1.866
1.867 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.868 - _arc_maps;
1.869 + _arc_maps;
1.870
1.871 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1.872 - _edge_maps;
1.873 + _edge_maps;
1.874
1.875 };
1.876
1.877 /// \brief Copy a graph to another graph.
1.878 ///
1.879 - /// Copy a graph to another graph. The complete usage of the
1.880 - /// function is detailed in the GraphCopy class, but a short
1.881 - /// example shows a basic work:
1.882 + /// This function copies a graph to another graph.
1.883 + /// The complete usage of it is detailed in the GraphCopy class,
1.884 + /// but a short example shows a basic work:
1.885 ///\code
1.886 - /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1.887 + /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
1.888 ///\endcode
1.889 ///
1.890 /// After the copy the \c nr map will contain the mapping from the
1.891 /// nodes of the \c from graph to the nodes of the \c to graph and
1.892 - /// \c ecr will contain the mapping from the arcs of the \c to graph
1.893 - /// to the arcs of the \c from graph.
1.894 + /// \c ecr will contain the mapping from the edges of the \c to graph
1.895 + /// to the edges of the \c from graph.
1.896 ///
1.897 /// \see GraphCopy
1.898 - template <typename To, typename From>
1.899 - GraphCopy<To, From>
1.900 - copyGraph(To& to, const From& from) {
1.901 - return GraphCopy<To, From>(to, from);
1.902 + template <typename From, typename To>
1.903 + GraphCopy<From, To>
1.904 + graphCopy(const From& from, To& to) {
1.905 + return GraphCopy<From, To>(from, to);
1.906 }
1.907
1.908 namespace _core_bits {
1.909 @@ -957,7 +980,7 @@
1.910 template <typename Graph>
1.911 struct FindArcSelector<
1.912 Graph,
1.913 - typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.914 + typename enable_if<typename Graph::FindArcTag, void>::type>
1.915 {
1.916 typedef typename Graph::Node Node;
1.917 typedef typename Graph::Arc Arc;
1.918 @@ -967,9 +990,10 @@
1.919 };
1.920 }
1.921
1.922 - /// \brief Finds an arc between two nodes of a graph.
1.923 + /// \brief Find an arc between two nodes of a digraph.
1.924 ///
1.925 - /// Finds an arc from node \c u to node \c v in graph \c g.
1.926 + /// This function finds an arc from node \c u to node \c v in the
1.927 + /// digraph \c g.
1.928 ///
1.929 /// If \c prev is \ref INVALID (this is the default value), then
1.930 /// it finds the first arc from \c u to \c v. Otherwise it looks for
1.931 @@ -978,15 +1002,16 @@
1.932 ///
1.933 /// Thus you can iterate through each arc from \c u to \c v as it follows.
1.934 ///\code
1.935 - /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
1.936 + /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
1.937 /// ...
1.938 /// }
1.939 ///\endcode
1.940 ///
1.941 - ///\sa ArcLookUp
1.942 - ///\sa AllArcLookUp
1.943 - ///\sa DynArcLookUp
1.944 + /// \note \ref ConArcIt provides iterator interface for the same
1.945 + /// functionality.
1.946 + ///
1.947 ///\sa ConArcIt
1.948 + ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1.949 template <typename Graph>
1.950 inline typename Graph::Arc
1.951 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1.952 @@ -994,10 +1019,10 @@
1.953 return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
1.954 }
1.955
1.956 - /// \brief Iterator for iterating on arcs connected the same nodes.
1.957 + /// \brief Iterator for iterating on parallel arcs connecting the same nodes.
1.958 ///
1.959 - /// Iterator for iterating on arcs connected the same nodes. It is
1.960 - /// higher level interface for the findArc() function. You can
1.961 + /// Iterator for iterating on parallel arcs connecting the same nodes. It is
1.962 + /// a higher level interface for the \ref findArc() function. You can
1.963 /// use it the following way:
1.964 ///\code
1.965 /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1.966 @@ -1006,9 +1031,7 @@
1.967 ///\endcode
1.968 ///
1.969 ///\sa findArc()
1.970 - ///\sa ArcLookUp
1.971 - ///\sa AllArcLookUp
1.972 - ///\sa DynArcLookUp
1.973 + ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1.974 template <typename _Graph>
1.975 class ConArcIt : public _Graph::Arc {
1.976 public:
1.977 @@ -1021,16 +1044,15 @@
1.978
1.979 /// \brief Constructor.
1.980 ///
1.981 - /// Construct a new ConArcIt iterating on the arcs which
1.982 - /// connects the \c u and \c v node.
1.983 + /// Construct a new ConArcIt iterating on the arcs that
1.984 + /// connects nodes \c u and \c v.
1.985 ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
1.986 Parent::operator=(findArc(_graph, u, v));
1.987 }
1.988
1.989 /// \brief Constructor.
1.990 ///
1.991 - /// Construct a new ConArcIt which continues the iterating from
1.992 - /// the \c e arc.
1.993 + /// Construct a new ConArcIt that continues the iterating from arc \c a.
1.994 ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
1.995
1.996 /// \brief Increment operator.
1.997 @@ -1091,27 +1113,29 @@
1.998 };
1.999 }
1.1000
1.1001 - /// \brief Finds an edge between two nodes of a graph.
1.1002 + /// \brief Find an edge between two nodes of a graph.
1.1003 ///
1.1004 - /// Finds an edge from node \c u to node \c v in graph \c g.
1.1005 - /// If the node \c u and node \c v is equal then each loop edge
1.1006 + /// This function finds an edge from node \c u to node \c v in graph \c g.
1.1007 + /// If node \c u and node \c v is equal then each loop edge
1.1008 /// will be enumerated once.
1.1009 ///
1.1010 /// If \c prev is \ref INVALID (this is the default value), then
1.1011 - /// it finds the first arc from \c u to \c v. Otherwise it looks for
1.1012 - /// the next arc from \c u to \c v after \c prev.
1.1013 - /// \return The found arc or \ref INVALID if there is no such an arc.
1.1014 + /// it finds the first edge from \c u to \c v. Otherwise it looks for
1.1015 + /// the next edge from \c u to \c v after \c prev.
1.1016 + /// \return The found edge or \ref INVALID if there is no such an edge.
1.1017 ///
1.1018 - /// Thus you can iterate through each arc from \c u to \c v as it follows.
1.1019 + /// Thus you can iterate through each edge between \c u and \c v
1.1020 + /// as it follows.
1.1021 ///\code
1.1022 - /// for(Edge e = findEdge(g,u,v); e != INVALID;
1.1023 - /// e = findEdge(g,u,v,e)) {
1.1024 + /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
1.1025 /// ...
1.1026 /// }
1.1027 ///\endcode
1.1028 ///
1.1029 + /// \note \ref ConEdgeIt provides iterator interface for the same
1.1030 + /// functionality.
1.1031 + ///
1.1032 ///\sa ConEdgeIt
1.1033 -
1.1034 template <typename Graph>
1.1035 inline typename Graph::Edge
1.1036 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1.1037 @@ -1119,13 +1143,13 @@
1.1038 return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
1.1039 }
1.1040
1.1041 - /// \brief Iterator for iterating on edges connected the same nodes.
1.1042 + /// \brief Iterator for iterating on parallel edges connecting the same nodes.
1.1043 ///
1.1044 - /// Iterator for iterating on edges connected the same nodes. It is
1.1045 - /// higher level interface for the findEdge() function. You can
1.1046 + /// Iterator for iterating on parallel edges connecting the same nodes.
1.1047 + /// It is a higher level interface for the findEdge() function. You can
1.1048 /// use it the following way:
1.1049 ///\code
1.1050 - /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1.1051 + /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
1.1052 /// ...
1.1053 /// }
1.1054 ///\endcode
1.1055 @@ -1143,16 +1167,15 @@
1.1056
1.1057 /// \brief Constructor.
1.1058 ///
1.1059 - /// Construct a new ConEdgeIt iterating on the edges which
1.1060 - /// connects the \c u and \c v node.
1.1061 + /// Construct a new ConEdgeIt iterating on the edges that
1.1062 + /// connects nodes \c u and \c v.
1.1063 ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
1.1064 Parent::operator=(findEdge(_graph, u, v));
1.1065 }
1.1066
1.1067 /// \brief Constructor.
1.1068 ///
1.1069 - /// Construct a new ConEdgeIt which continues the iterating from
1.1070 - /// the \c e edge.
1.1071 + /// Construct a new ConEdgeIt that continues iterating from edge \c e.
1.1072 ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
1.1073
1.1074 /// \brief Increment operator.
1.1075 @@ -1168,21 +1191,21 @@
1.1076 };
1.1077
1.1078
1.1079 - ///Dynamic arc look up between given endpoints.
1.1080 + ///Dynamic arc look-up between given endpoints.
1.1081
1.1082 ///Using this class, you can find an arc in a digraph from a given
1.1083 - ///source to a given target in amortized time <em>O(log</em>d<em>)</em>,
1.1084 + ///source to a given target in amortized time <em>O</em>(log<em>d</em>),
1.1085 ///where <em>d</em> is the out-degree of the source node.
1.1086 ///
1.1087 ///It is possible to find \e all parallel arcs between two nodes with
1.1088 ///the \c operator() member.
1.1089 ///
1.1090 - ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
1.1091 - ///digraph is not changed so frequently.
1.1092 + ///This is a dynamic data structure. Consider to use \ref ArcLookUp or
1.1093 + ///\ref AllArcLookUp if your digraph is not changed so frequently.
1.1094 ///
1.1095 - ///This class uses a self-adjusting binary search tree, Sleator's
1.1096 - ///and Tarjan's Splay tree for guarantee the logarithmic amortized
1.1097 - ///time bound for arc lookups. This class also guarantees the
1.1098 + ///This class uses a self-adjusting binary search tree, the Splay tree
1.1099 + ///of Sleator and Tarjan to guarantee the logarithmic amortized
1.1100 + ///time bound for arc look-ups. This class also guarantees the
1.1101 ///optimal time bound in a constant factor for any distribution of
1.1102 ///queries.
1.1103 ///
1.1104 @@ -1507,8 +1530,8 @@
1.1105 ///Find an arc between two nodes.
1.1106
1.1107 ///Find an arc between two nodes.
1.1108 - ///\param s The source node
1.1109 - ///\param t The target node
1.1110 + ///\param s The source node.
1.1111 + ///\param t The target node.
1.1112 ///\param p The previous arc between \c s and \c t. It it is INVALID or
1.1113 ///not given, the operator finds the first appropriate arc.
1.1114 ///\return An arc from \c s to \c t after \c p or
1.1115 @@ -1519,21 +1542,20 @@
1.1116 ///\code
1.1117 ///DynArcLookUp<ListDigraph> ae(g);
1.1118 ///...
1.1119 - ///int n=0;
1.1120 - ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
1.1121 + ///int n = 0;
1.1122 + ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
1.1123 ///\endcode
1.1124 ///
1.1125 - ///Finding the arcs take at most <em>O(</em>log<em>d)</em>
1.1126 + ///Finding the arcs take at most <em>O</em>(log<em>d</em>)
1.1127 ///amortized time, specifically, the time complexity of the lookups
1.1128 ///is equal to the optimal search tree implementation for the
1.1129 ///current query distribution in a constant factor.
1.1130 ///
1.1131 ///\note This is a dynamic data structure, therefore the data
1.1132 - ///structure is updated after each graph alteration. However,
1.1133 - ///theoretically this data structure is faster than \c ArcLookUp
1.1134 - ///or AllEdgeLookup, but it often provides worse performance than
1.1135 + ///structure is updated after each graph alteration. Thus although
1.1136 + ///this data structure is theoretically faster than \ref ArcLookUp
1.1137 + ///and \ref AllArcLookup, it often provides worse performance than
1.1138 ///them.
1.1139 - ///
1.1140 Arc operator()(Node s, Node t, Arc p = INVALID) const {
1.1141 if (p == INVALID) {
1.1142 Arc a = _head[s];
1.1143 @@ -1585,19 +1607,19 @@
1.1144
1.1145 };
1.1146
1.1147 - ///Fast arc look up between given endpoints.
1.1148 + ///Fast arc look-up between given endpoints.
1.1149
1.1150 ///Using this class, you can find an arc in a digraph from a given
1.1151 - ///source to a given target in time <em>O(log d)</em>,
1.1152 + ///source to a given target in time <em>O</em>(log<em>d</em>),
1.1153 ///where <em>d</em> is the out-degree of the source node.
1.1154 ///
1.1155 ///It is not possible to find \e all parallel arcs between two nodes.
1.1156 ///Use \ref AllArcLookUp for this purpose.
1.1157 ///
1.1158 - ///\warning This class is static, so you should refresh() (or at least
1.1159 - ///refresh(Node)) this data structure
1.1160 - ///whenever the digraph changes. This is a time consuming (superlinearly
1.1161 - ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
1.1162 + ///\warning This class is static, so you should call refresh() (or at
1.1163 + ///least refresh(Node)) to refresh this data structure whenever the
1.1164 + ///digraph changes. This is a time consuming (superlinearly proportional
1.1165 + ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1.1166 ///
1.1167 ///\tparam G The type of the underlying digraph.
1.1168 ///
1.1169 @@ -1646,12 +1668,12 @@
1.1170 return me;
1.1171 }
1.1172 public:
1.1173 - ///Refresh the data structure at a node.
1.1174 + ///Refresh the search data structure at a node.
1.1175
1.1176 ///Build up the search database of node \c n.
1.1177 ///
1.1178 - ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
1.1179 - ///the number of the outgoing arcs of \c n.
1.1180 + ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
1.1181 + ///is the number of the outgoing arcs of \c n.
1.1182 void refresh(Node n)
1.1183 {
1.1184 std::vector<Arc> v;
1.1185 @@ -1667,10 +1689,9 @@
1.1186 ///Build up the full search database. In fact, it simply calls
1.1187 ///\ref refresh(Node) "refresh(n)" for each node \c n.
1.1188 ///
1.1189 - ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
1.1190 - ///the number of the arcs of \c n and <em>D</em> is the maximum
1.1191 + ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
1.1192 + ///the number of the arcs in the digraph and <em>D</em> is the maximum
1.1193 ///out-degree of the digraph.
1.1194 -
1.1195 void refresh()
1.1196 {
1.1197 for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1.1198 @@ -1678,18 +1699,16 @@
1.1199
1.1200 ///Find an arc between two nodes.
1.1201
1.1202 - ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
1.1203 - /// <em>d</em> is the number of outgoing arcs of \c s.
1.1204 - ///\param s The source node
1.1205 - ///\param t The target node
1.1206 + ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>), where
1.1207 + ///<em>d</em> is the number of outgoing arcs of \c s.
1.1208 + ///\param s The source node.
1.1209 + ///\param t The target node.
1.1210 ///\return An arc from \c s to \c t if there exists,
1.1211 ///\ref INVALID otherwise.
1.1212 ///
1.1213 ///\warning If you change the digraph, refresh() must be called before using
1.1214 ///this operator. If you change the outgoing arcs of
1.1215 - ///a single node \c n, then
1.1216 - ///\ref refresh(Node) "refresh(n)" is enough.
1.1217 - ///
1.1218 + ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
1.1219 Arc operator()(Node s, Node t) const
1.1220 {
1.1221 Arc e;
1.1222 @@ -1701,15 +1720,16 @@
1.1223
1.1224 };
1.1225
1.1226 - ///Fast look up of all arcs between given endpoints.
1.1227 + ///Fast look-up of all arcs between given endpoints.
1.1228
1.1229 ///This class is the same as \ref ArcLookUp, with the addition
1.1230 - ///that it makes it possible to find all arcs between given endpoints.
1.1231 + ///that it makes it possible to find all parallel arcs between given
1.1232 + ///endpoints.
1.1233 ///
1.1234 - ///\warning This class is static, so you should refresh() (or at least
1.1235 - ///refresh(Node)) this data structure
1.1236 - ///whenever the digraph changes. This is a time consuming (superlinearly
1.1237 - ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
1.1238 + ///\warning This class is static, so you should call refresh() (or at
1.1239 + ///least refresh(Node)) to refresh this data structure whenever the
1.1240 + ///digraph changes. This is a time consuming (superlinearly proportional
1.1241 + ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1.1242 ///
1.1243 ///\tparam G The type of the underlying digraph.
1.1244 ///
1.1245 @@ -1733,7 +1753,6 @@
1.1246 if(head==INVALID) return next;
1.1247 else {
1.1248 next=refreshNext(_right[head],next);
1.1249 -// _next[head]=next;
1.1250 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
1.1251 ? next : INVALID;
1.1252 return refreshNext(_left[head],head);
1.1253 @@ -1758,9 +1777,8 @@
1.1254
1.1255 ///Build up the search database of node \c n.
1.1256 ///
1.1257 - ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
1.1258 + ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
1.1259 ///the number of the outgoing arcs of \c n.
1.1260 -
1.1261 void refresh(Node n)
1.1262 {
1.1263 ArcLookUp<G>::refresh(n);
1.1264 @@ -1772,10 +1790,9 @@
1.1265 ///Build up the full search database. In fact, it simply calls
1.1266 ///\ref refresh(Node) "refresh(n)" for each node \c n.
1.1267 ///
1.1268 - ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
1.1269 - ///the number of the arcs of \c n and <em>D</em> is the maximum
1.1270 + ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
1.1271 + ///the number of the arcs in the digraph and <em>D</em> is the maximum
1.1272 ///out-degree of the digraph.
1.1273 -
1.1274 void refresh()
1.1275 {
1.1276 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
1.1277 @@ -1784,8 +1801,8 @@
1.1278 ///Find an arc between two nodes.
1.1279
1.1280 ///Find an arc between two nodes.
1.1281 - ///\param s The source node
1.1282 - ///\param t The target node
1.1283 + ///\param s The source node.
1.1284 + ///\param t The target node.
1.1285 ///\param prev The previous arc between \c s and \c t. It it is INVALID or
1.1286 ///not given, the operator finds the first appropriate arc.
1.1287 ///\return An arc from \c s to \c t after \c prev or
1.1288 @@ -1796,18 +1813,17 @@
1.1289 ///\code
1.1290 ///AllArcLookUp<ListDigraph> ae(g);
1.1291 ///...
1.1292 - ///int n=0;
1.1293 - ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
1.1294 + ///int n = 0;
1.1295 + ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
1.1296 ///\endcode
1.1297 ///
1.1298 - ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
1.1299 - /// <em>d</em> is the number of outgoing arcs of \c s. Then, the
1.1300 + ///Finding the first arc take <em>O</em>(log<em>d</em>) time, where
1.1301 + ///<em>d</em> is the number of outgoing arcs of \c s. Then, the
1.1302 ///consecutive arcs are found in constant time.
1.1303 ///
1.1304 ///\warning If you change the digraph, refresh() must be called before using
1.1305 ///this operator. If you change the outgoing arcs of
1.1306 - ///a single node \c n, then
1.1307 - ///\ref refresh(Node) "refresh(n)" is enough.
1.1308 + ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
1.1309 ///
1.1310 #ifdef DOXYGEN
1.1311 Arc operator()(Node s, Node t, Arc prev=INVALID) const {}