1.1 --- a/lemon/graph_utils.h Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/lemon/graph_utils.h Sun Jul 13 19:51:02 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -46,24 +46,24 @@
1.13
1.14 ///This \c \#define creates convenience typedefs for the following types
1.15 ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
1.16 - ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
1.17 + ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
1.18 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
1.19 ///
1.20 ///\note If the graph type is a dependent type, ie. the graph type depend
1.21 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
1.22 ///macro.
1.23 -#define DIGRAPH_TYPEDEFS(Digraph) \
1.24 - typedef Digraph::Node Node; \
1.25 - typedef Digraph::NodeIt NodeIt; \
1.26 - typedef Digraph::Arc Arc; \
1.27 - typedef Digraph::ArcIt ArcIt; \
1.28 - typedef Digraph::InArcIt InArcIt; \
1.29 - typedef Digraph::OutArcIt OutArcIt; \
1.30 - typedef Digraph::NodeMap<bool> BoolNodeMap; \
1.31 - typedef Digraph::NodeMap<int> IntNodeMap; \
1.32 - typedef Digraph::NodeMap<double> DoubleNodeMap; \
1.33 - typedef Digraph::ArcMap<bool> BoolArcMap; \
1.34 - typedef Digraph::ArcMap<int> IntArcMap; \
1.35 +#define DIGRAPH_TYPEDEFS(Digraph) \
1.36 + typedef Digraph::Node Node; \
1.37 + typedef Digraph::NodeIt NodeIt; \
1.38 + typedef Digraph::Arc Arc; \
1.39 + typedef Digraph::ArcIt ArcIt; \
1.40 + typedef Digraph::InArcIt InArcIt; \
1.41 + typedef Digraph::OutArcIt OutArcIt; \
1.42 + typedef Digraph::NodeMap<bool> BoolNodeMap; \
1.43 + typedef Digraph::NodeMap<int> IntNodeMap; \
1.44 + typedef Digraph::NodeMap<double> DoubleNodeMap; \
1.45 + typedef Digraph::ArcMap<bool> BoolArcMap; \
1.46 + typedef Digraph::ArcMap<int> IntArcMap; \
1.47 typedef Digraph::ArcMap<double> DoubleArcMap
1.48
1.49 ///Creates convenience typedefs for the digraph types and iterators
1.50 @@ -72,20 +72,20 @@
1.51 ///
1.52 ///\note Use this macro, if the graph type is a dependent type,
1.53 ///ie. the graph type depend on a template parameter.
1.54 -#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \
1.55 - typedef typename Digraph::Node Node; \
1.56 - typedef typename Digraph::NodeIt NodeIt; \
1.57 - typedef typename Digraph::Arc Arc; \
1.58 - typedef typename Digraph::ArcIt ArcIt; \
1.59 - typedef typename Digraph::InArcIt InArcIt; \
1.60 - typedef typename Digraph::OutArcIt OutArcIt; \
1.61 - typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \
1.62 - typedef typename Digraph::template NodeMap<int> IntNodeMap; \
1.63 - typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
1.64 - typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
1.65 - typedef typename Digraph::template ArcMap<int> IntArcMap; \
1.66 +#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \
1.67 + typedef typename Digraph::Node Node; \
1.68 + typedef typename Digraph::NodeIt NodeIt; \
1.69 + typedef typename Digraph::Arc Arc; \
1.70 + typedef typename Digraph::ArcIt ArcIt; \
1.71 + typedef typename Digraph::InArcIt InArcIt; \
1.72 + typedef typename Digraph::OutArcIt OutArcIt; \
1.73 + typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \
1.74 + typedef typename Digraph::template NodeMap<int> IntNodeMap; \
1.75 + typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
1.76 + typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
1.77 + typedef typename Digraph::template ArcMap<int> IntArcMap; \
1.78 typedef typename Digraph::template ArcMap<double> DoubleArcMap
1.79 -
1.80 +
1.81 ///Creates convenience typedefs for the graph types and iterators
1.82
1.83 ///This \c \#define creates the same convenience typedefs as defined
1.84 @@ -96,13 +96,13 @@
1.85 ///\note If the graph type is a dependent type, ie. the graph type depend
1.86 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
1.87 ///macro.
1.88 -#define GRAPH_TYPEDEFS(Graph) \
1.89 - DIGRAPH_TYPEDEFS(Graph); \
1.90 - typedef Graph::Edge Edge; \
1.91 - typedef Graph::EdgeIt EdgeIt; \
1.92 - typedef Graph::IncEdgeIt IncEdgeIt; \
1.93 - typedef Graph::EdgeMap<bool> BoolEdgeMap; \
1.94 - typedef Graph::EdgeMap<int> IntEdgeMap; \
1.95 +#define GRAPH_TYPEDEFS(Graph) \
1.96 + DIGRAPH_TYPEDEFS(Graph); \
1.97 + typedef Graph::Edge Edge; \
1.98 + typedef Graph::EdgeIt EdgeIt; \
1.99 + typedef Graph::IncEdgeIt IncEdgeIt; \
1.100 + typedef Graph::EdgeMap<bool> BoolEdgeMap; \
1.101 + typedef Graph::EdgeMap<int> IntEdgeMap; \
1.102 typedef Graph::EdgeMap<double> DoubleEdgeMap
1.103
1.104 ///Creates convenience typedefs for the graph types and iterators
1.105 @@ -111,13 +111,13 @@
1.106 ///
1.107 ///\note Use this macro, if the graph type is a dependent type,
1.108 ///ie. the graph type depend on a template parameter.
1.109 -#define TEMPLATE_GRAPH_TYPEDEFS(Graph) \
1.110 - TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \
1.111 - typedef typename Graph::Edge Edge; \
1.112 - typedef typename Graph::EdgeIt EdgeIt; \
1.113 - typedef typename Graph::IncEdgeIt IncEdgeIt; \
1.114 - typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
1.115 - typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
1.116 +#define TEMPLATE_GRAPH_TYPEDEFS(Graph) \
1.117 + TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \
1.118 + typedef typename Graph::Edge Edge; \
1.119 + typedef typename Graph::EdgeIt EdgeIt; \
1.120 + typedef typename Graph::IncEdgeIt IncEdgeIt; \
1.121 + typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
1.122 + typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
1.123 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
1.124
1.125 /// \brief Function to count the items in the graph.
1.126 @@ -138,7 +138,7 @@
1.127 // Node counting:
1.128
1.129 namespace _graph_utils_bits {
1.130 -
1.131 +
1.132 template <typename Graph, typename Enable = void>
1.133 struct CountNodesSelector {
1.134 static int count(const Graph &g) {
1.135 @@ -148,13 +148,13 @@
1.136
1.137 template <typename Graph>
1.138 struct CountNodesSelector<
1.139 - Graph, typename
1.140 - enable_if<typename Graph::NodeNumTag, void>::type>
1.141 + Graph, typename
1.142 + enable_if<typename Graph::NodeNumTag, void>::type>
1.143 {
1.144 static int count(const Graph &g) {
1.145 return g.nodeNum();
1.146 }
1.147 - };
1.148 + };
1.149 }
1.150
1.151 /// \brief Function to count the nodes in the graph.
1.152 @@ -163,7 +163,7 @@
1.153 /// The complexity of the function is O(n) but for some
1.154 /// graph structures it is specialized to run in O(1).
1.155 ///
1.156 - /// If the graph contains a \e nodeNum() member function and a
1.157 + /// If the graph contains a \e nodeNum() member function and a
1.158 /// \e NodeNumTag tag then this function calls directly the member
1.159 /// function to query the cardinality of the node set.
1.160 template <typename Graph>
1.161 @@ -174,7 +174,7 @@
1.162 // Arc counting:
1.163
1.164 namespace _graph_utils_bits {
1.165 -
1.166 +
1.167 template <typename Graph, typename Enable = void>
1.168 struct CountArcsSelector {
1.169 static int count(const Graph &g) {
1.170 @@ -184,13 +184,13 @@
1.171
1.172 template <typename Graph>
1.173 struct CountArcsSelector<
1.174 - Graph,
1.175 - typename enable_if<typename Graph::ArcNumTag, void>::type>
1.176 + Graph,
1.177 + typename enable_if<typename Graph::ArcNumTag, void>::type>
1.178 {
1.179 static int count(const Graph &g) {
1.180 return g.arcNum();
1.181 }
1.182 - };
1.183 + };
1.184 }
1.185
1.186 /// \brief Function to count the arcs in the graph.
1.187 @@ -199,7 +199,7 @@
1.188 /// The complexity of the function is O(e) but for some
1.189 /// graph structures it is specialized to run in O(1).
1.190 ///
1.191 - /// If the graph contains a \e arcNum() member function and a
1.192 + /// If the graph contains a \e arcNum() member function and a
1.193 /// \e EdgeNumTag tag then this function calls directly the member
1.194 /// function to query the cardinality of the arc set.
1.195 template <typename Graph>
1.196 @@ -209,7 +209,7 @@
1.197
1.198 // Edge counting:
1.199 namespace _graph_utils_bits {
1.200 -
1.201 +
1.202 template <typename Graph, typename Enable = void>
1.203 struct CountEdgesSelector {
1.204 static int count(const Graph &g) {
1.205 @@ -219,13 +219,13 @@
1.206
1.207 template <typename Graph>
1.208 struct CountEdgesSelector<
1.209 - Graph,
1.210 - typename enable_if<typename Graph::EdgeNumTag, void>::type>
1.211 + Graph,
1.212 + typename enable_if<typename Graph::EdgeNumTag, void>::type>
1.213 {
1.214 static int count(const Graph &g) {
1.215 return g.edgeNum();
1.216 }
1.217 - };
1.218 + };
1.219 }
1.220
1.221 /// \brief Function to count the edges in the graph.
1.222 @@ -234,7 +234,7 @@
1.223 /// The complexity of the function is O(m) but for some
1.224 /// graph structures it is specialized to run in O(1).
1.225 ///
1.226 - /// If the graph contains a \e edgeNum() member function and a
1.227 + /// If the graph contains a \e edgeNum() member function and a
1.228 /// \e EdgeNumTag tag then this function calls directly the member
1.229 /// function to query the cardinality of the edge set.
1.230 template <typename Graph>
1.231 @@ -256,7 +256,7 @@
1.232 /// \brief Function to count the number of the out-arcs from node \c n.
1.233 ///
1.234 /// This function counts the number of the out-arcs from node \c n
1.235 - /// in the graph.
1.236 + /// in the graph.
1.237 template <typename Graph>
1.238 inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {
1.239 return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
1.240 @@ -265,7 +265,7 @@
1.241 /// \brief Function to count the number of the in-arcs to node \c n.
1.242 ///
1.243 /// This function counts the number of the in-arcs to node \c n
1.244 - /// in the graph.
1.245 + /// in the graph.
1.246 template <typename Graph>
1.247 inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {
1.248 return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
1.249 @@ -274,14 +274,14 @@
1.250 /// \brief Function to count the number of the inc-edges to node \c n.
1.251 ///
1.252 /// This function counts the number of the inc-edges to node \c n
1.253 - /// in the graph.
1.254 + /// in the graph.
1.255 template <typename Graph>
1.256 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
1.257 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
1.258 }
1.259
1.260 namespace _graph_utils_bits {
1.261 -
1.262 +
1.263 template <typename Graph, typename Enable = void>
1.264 struct FindArcSelector {
1.265 typedef typename Graph::Node Node;
1.266 @@ -301,15 +301,15 @@
1.267
1.268 template <typename Graph>
1.269 struct FindArcSelector<
1.270 - Graph,
1.271 - typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.272 + Graph,
1.273 + typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.274 {
1.275 typedef typename Graph::Node Node;
1.276 typedef typename Graph::Arc Arc;
1.277 static Arc find(const Graph &g, Node u, Node v, Arc prev) {
1.278 return g.findArc(u, v, prev);
1.279 }
1.280 - };
1.281 + };
1.282 }
1.283
1.284 /// \brief Finds an arc between two nodes of a graph.
1.285 @@ -333,7 +333,7 @@
1.286 ///\sa DynArcLookUp
1.287 ///\sa ConArcIt
1.288 template <typename Graph>
1.289 - inline typename Graph::Arc
1.290 + inline typename Graph::Arc
1.291 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1.292 typename Graph::Arc prev = INVALID) {
1.293 return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
1.294 @@ -341,7 +341,7 @@
1.295
1.296 /// \brief Iterator for iterating on arcs connected the same nodes.
1.297 ///
1.298 - /// Iterator for iterating on arcs connected the same nodes. It is
1.299 + /// Iterator for iterating on arcs connected the same nodes. It is
1.300 /// higher level interface for the findArc() function. You can
1.301 /// use it the following way:
1.302 ///\code
1.303 @@ -349,7 +349,7 @@
1.304 /// ...
1.305 /// }
1.306 ///\endcode
1.307 - ///
1.308 + ///
1.309 ///\sa findArc()
1.310 ///\sa ArcLookUp
1.311 ///\sa AllArcLookUp
1.312 @@ -374,16 +374,16 @@
1.313
1.314 /// \brief Constructor.
1.315 ///
1.316 - /// Construct a new ConArcIt which continues the iterating from
1.317 + /// Construct a new ConArcIt which continues the iterating from
1.318 /// the \c e arc.
1.319 ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
1.320 -
1.321 +
1.322 /// \brief Increment operator.
1.323 ///
1.324 /// It increments the iterator and gives back the next arc.
1.325 ConArcIt& operator++() {
1.326 - Parent::operator=(findArc(_graph, _graph.source(*this),
1.327 - _graph.target(*this), *this));
1.328 + Parent::operator=(findArc(_graph, _graph.source(*this),
1.329 + _graph.target(*this), *this));
1.330 return *this;
1.331 }
1.332 private:
1.333 @@ -391,7 +391,7 @@
1.334 };
1.335
1.336 namespace _graph_utils_bits {
1.337 -
1.338 +
1.339 template <typename Graph, typename Enable = void>
1.340 struct FindEdgeSelector {
1.341 typedef typename Graph::Node Node;
1.342 @@ -425,15 +425,15 @@
1.343
1.344 template <typename Graph>
1.345 struct FindEdgeSelector<
1.346 - Graph,
1.347 - typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.348 + Graph,
1.349 + typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.350 {
1.351 typedef typename Graph::Node Node;
1.352 typedef typename Graph::Edge Edge;
1.353 static Edge find(const Graph &g, Node u, Node v, Edge prev) {
1.354 return g.findEdge(u, v, prev);
1.355 }
1.356 - };
1.357 + };
1.358 }
1.359
1.360 /// \brief Finds an edge between two nodes of a graph.
1.361 @@ -449,7 +449,7 @@
1.362 ///
1.363 /// Thus you can iterate through each arc from \c u to \c v as it follows.
1.364 ///\code
1.365 - /// for(Edge e = findEdge(g,u,v); e != INVALID;
1.366 + /// for(Edge e = findEdge(g,u,v); e != INVALID;
1.367 /// e = findEdge(g,u,v,e)) {
1.368 /// ...
1.369 /// }
1.370 @@ -458,7 +458,7 @@
1.371 ///\sa ConEdgeIt
1.372
1.373 template <typename Graph>
1.374 - inline typename Graph::Edge
1.375 + inline typename Graph::Edge
1.376 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1.377 typename Graph::Edge p = INVALID) {
1.378 return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
1.379 @@ -466,7 +466,7 @@
1.380
1.381 /// \brief Iterator for iterating on edges connected the same nodes.
1.382 ///
1.383 - /// Iterator for iterating on edges connected the same nodes. It is
1.384 + /// Iterator for iterating on edges connected the same nodes. It is
1.385 /// higher level interface for the findEdge() function. You can
1.386 /// use it the following way:
1.387 ///\code
1.388 @@ -496,16 +496,16 @@
1.389
1.390 /// \brief Constructor.
1.391 ///
1.392 - /// Construct a new ConEdgeIt which continues the iterating from
1.393 + /// Construct a new ConEdgeIt which continues the iterating from
1.394 /// the \c e edge.
1.395 ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
1.396 -
1.397 +
1.398 /// \brief Increment operator.
1.399 ///
1.400 /// It increments the iterator and gives back the next edge.
1.401 ConEdgeIt& operator++() {
1.402 - Parent::operator=(findEdge(_graph, _graph.u(*this),
1.403 - _graph.v(*this), *this));
1.404 + Parent::operator=(findEdge(_graph, _graph.u(*this),
1.405 + _graph.v(*this), *this));
1.406 return *this;
1.407 }
1.408 private:
1.409 @@ -518,18 +518,18 @@
1.410 class MapCopyBase {
1.411 public:
1.412 virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
1.413 -
1.414 +
1.415 virtual ~MapCopyBase() {}
1.416 };
1.417
1.418 - template <typename Digraph, typename Item, typename RefMap,
1.419 + template <typename Digraph, typename Item, typename RefMap,
1.420 typename ToMap, typename FromMap>
1.421 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
1.422 public:
1.423
1.424 - MapCopy(ToMap& tmap, const FromMap& map)
1.425 + MapCopy(ToMap& tmap, const FromMap& map)
1.426 : _tmap(tmap), _map(map) {}
1.427 -
1.428 +
1.429 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
1.430 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
1.431 for (ItemIt it(digraph); it != INVALID; ++it) {
1.432 @@ -547,7 +547,7 @@
1.433 public:
1.434
1.435 ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
1.436 -
1.437 +
1.438 virtual void copy(const Digraph&, const RefMap& refMap) {
1.439 _it = refMap[_item];
1.440 }
1.441 @@ -562,7 +562,7 @@
1.442 public:
1.443
1.444 RefCopy(Ref& map) : _map(map) {}
1.445 -
1.446 +
1.447 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
1.448 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
1.449 for (ItemIt it(digraph); it != INVALID; ++it) {
1.450 @@ -574,13 +574,13 @@
1.451 Ref& _map;
1.452 };
1.453
1.454 - template <typename Digraph, typename Item, typename RefMap,
1.455 + template <typename Digraph, typename Item, typename RefMap,
1.456 typename CrossRef>
1.457 class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
1.458 public:
1.459
1.460 CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
1.461 -
1.462 +
1.463 virtual void copy(const Digraph& digraph, const RefMap& refMap) {
1.464 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
1.465 for (ItemIt it(digraph); it != INVALID; ++it) {
1.466 @@ -601,16 +601,16 @@
1.467 nodeRefMap[it] = to.addNode();
1.468 }
1.469 for (typename From::ArcIt it(from); it != INVALID; ++it) {
1.470 - arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
1.471 - nodeRefMap[from.target(it)]);
1.472 + arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
1.473 + nodeRefMap[from.target(it)]);
1.474 }
1.475 }
1.476 };
1.477
1.478 template <typename Digraph>
1.479 struct DigraphCopySelector<
1.480 - Digraph,
1.481 - typename enable_if<typename Digraph::BuildTag, void>::type>
1.482 + Digraph,
1.483 + typename enable_if<typename Digraph::BuildTag, void>::type>
1.484 {
1.485 template <typename From, typename NodeRefMap, typename ArcRefMap>
1.486 static void copy(Digraph &to, const From& from,
1.487 @@ -628,16 +628,16 @@
1.488 nodeRefMap[it] = to.addNode();
1.489 }
1.490 for (typename From::EdgeIt it(from); it != INVALID; ++it) {
1.491 - edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
1.492 - nodeRefMap[from.v(it)]);
1.493 + edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
1.494 + nodeRefMap[from.v(it)]);
1.495 }
1.496 }
1.497 };
1.498
1.499 template <typename Graph>
1.500 struct GraphCopySelector<
1.501 - Graph,
1.502 - typename enable_if<typename Graph::BuildTag, void>::type>
1.503 + Graph,
1.504 + typename enable_if<typename Graph::BuildTag, void>::type>
1.505 {
1.506 template <typename From, typename NodeRefMap, typename EdgeRefMap>
1.507 static void copy(Graph &to, const From& from,
1.508 @@ -697,16 +697,16 @@
1.509
1.510 typedef typename From::template NodeMap<TNode> NodeRefMap;
1.511 typedef typename From::template ArcMap<TArc> ArcRefMap;
1.512 -
1.513 -
1.514 - public:
1.515 +
1.516 +
1.517 + public:
1.518
1.519
1.520 /// \brief Constructor for the DigraphCopy.
1.521 ///
1.522 /// It copies the content of the \c _from digraph into the
1.523 /// \c _to digraph.
1.524 - DigraphCopy(To& to, const From& from)
1.525 + DigraphCopy(To& to, const From& from)
1.526 : _from(from), _to(to) {}
1.527
1.528 /// \brief Destructor of the DigraphCopy
1.529 @@ -730,8 +730,8 @@
1.530 /// destination graph.
1.531 template <typename NodeRef>
1.532 DigraphCopy& nodeRef(NodeRef& map) {
1.533 - _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
1.534 - NodeRefMap, NodeRef>(map));
1.535 + _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
1.536 + NodeRefMap, NodeRef>(map));
1.537 return *this;
1.538 }
1.539
1.540 @@ -744,7 +744,7 @@
1.541 template <typename NodeCrossRef>
1.542 DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.543 _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
1.544 - NodeRefMap, NodeCrossRef>(map));
1.545 + NodeRefMap, NodeCrossRef>(map));
1.546 return *this;
1.547 }
1.548
1.549 @@ -755,8 +755,8 @@
1.550 /// and the copied map's key type is the source graph's node type.
1.551 template <typename ToMap, typename FromMap>
1.552 DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1.553 - _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
1.554 - NodeRefMap, ToMap, FromMap>(tmap, map));
1.555 + _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
1.556 + NodeRefMap, ToMap, FromMap>(tmap, map));
1.557 return *this;
1.558 }
1.559
1.560 @@ -764,8 +764,8 @@
1.561 ///
1.562 /// Make a copy of the given node.
1.563 DigraphCopy& node(TNode& tnode, const Node& snode) {
1.564 - _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
1.565 - NodeRefMap, TNode>(tnode, snode));
1.566 + _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
1.567 + NodeRefMap, TNode>(tnode, snode));
1.568 return *this;
1.569 }
1.570
1.571 @@ -774,8 +774,8 @@
1.572 /// Copies the arc references into the given map.
1.573 template <typename ArcRef>
1.574 DigraphCopy& arcRef(ArcRef& map) {
1.575 - _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
1.576 - ArcRefMap, ArcRef>(map));
1.577 + _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
1.578 + ArcRefMap, ArcRef>(map));
1.579 return *this;
1.580 }
1.581
1.582 @@ -786,20 +786,20 @@
1.583 template <typename ArcCrossRef>
1.584 DigraphCopy& arcCrossRef(ArcCrossRef& map) {
1.585 _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
1.586 - ArcRefMap, ArcCrossRef>(map));
1.587 + ArcRefMap, ArcCrossRef>(map));
1.588 return *this;
1.589 }
1.590
1.591 /// \brief Make copy of the given map.
1.592 ///
1.593 - /// Makes copy of the given map for the newly created digraph.
1.594 + /// Makes copy of the given map for the newly created digraph.
1.595 /// The new map's key type is the to digraph's arc type,
1.596 /// and the copied map's key type is the from digraph's arc
1.597 - /// type.
1.598 + /// type.
1.599 template <typename ToMap, typename FromMap>
1.600 DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1.601 - _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
1.602 - ArcRefMap, ToMap, FromMap>(tmap, map));
1.603 + _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
1.604 + ArcRefMap, ToMap, FromMap>(tmap, map));
1.605 return *this;
1.606 }
1.607
1.608 @@ -807,8 +807,8 @@
1.609 ///
1.610 /// Make a copy of the given arc.
1.611 DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
1.612 - _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
1.613 - ArcRefMap, TArc>(tarc, sarc));
1.614 + _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
1.615 + ArcRefMap, TArc>(tarc, sarc));
1.616 return *this;
1.617 }
1.618
1.619 @@ -825,7 +825,7 @@
1.620 }
1.621 for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.622 _arc_maps[i]->copy(_from, arcRefMap);
1.623 - }
1.624 + }
1.625 }
1.626
1.627 protected:
1.628 @@ -834,10 +834,10 @@
1.629 const From& _from;
1.630 To& _to;
1.631
1.632 - std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.633 + std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.634 _node_maps;
1.635
1.636 - std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.637 + std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.638 _arc_maps;
1.639
1.640 };
1.641 @@ -850,13 +850,13 @@
1.642 ///\code
1.643 /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1.644 ///\endcode
1.645 - ///
1.646 + ///
1.647 /// After the copy the \c nr map will contain the mapping from the
1.648 /// nodes of the \c from digraph to the nodes of the \c to digraph and
1.649 /// \c ecr will contain the mapping from the arcs of the \c to digraph
1.650 /// to the arcs of the \c from digraph.
1.651 ///
1.652 - /// \see DigraphCopy
1.653 + /// \see DigraphCopy
1.654 template <typename To, typename From>
1.655 DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
1.656 return DigraphCopy<To, From>(to, from);
1.657 @@ -917,8 +917,8 @@
1.658
1.659 struct ArcRefMap {
1.660 ArcRefMap(const To& to, const From& from,
1.661 - const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
1.662 - : _to(to), _from(from),
1.663 + const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
1.664 + : _to(to), _from(from),
1.665 _edge_ref(edge_ref), _node_ref(node_ref) {}
1.666
1.667 typedef typename From::Arc Key;
1.668 @@ -926,27 +926,27 @@
1.669
1.670 Value operator[](const Key& key) const {
1.671 bool forward = _from.u(key) != _from.v(key) ?
1.672 - _node_ref[_from.source(key)] ==
1.673 - _to.source(_to.direct(_edge_ref[key], true)) :
1.674 - _from.direction(key);
1.675 - return _to.direct(_edge_ref[key], forward);
1.676 + _node_ref[_from.source(key)] ==
1.677 + _to.source(_to.direct(_edge_ref[key], true)) :
1.678 + _from.direction(key);
1.679 + return _to.direct(_edge_ref[key], forward);
1.680 }
1.681 -
1.682 +
1.683 const To& _to;
1.684 const From& _from;
1.685 const EdgeRefMap& _edge_ref;
1.686 const NodeRefMap& _node_ref;
1.687 };
1.688
1.689 -
1.690 - public:
1.691 +
1.692 + public:
1.693
1.694
1.695 /// \brief Constructor for the GraphCopy.
1.696 ///
1.697 /// It copies the content of the \c _from graph into the
1.698 /// \c _to graph.
1.699 - GraphCopy(To& to, const From& from)
1.700 + GraphCopy(To& to, const From& from)
1.701 : _from(from), _to(to) {}
1.702
1.703 /// \brief Destructor of the GraphCopy
1.704 @@ -970,8 +970,8 @@
1.705 /// Copies the node references into the given map.
1.706 template <typename NodeRef>
1.707 GraphCopy& nodeRef(NodeRef& map) {
1.708 - _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
1.709 - NodeRefMap, NodeRef>(map));
1.710 + _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
1.711 + NodeRefMap, NodeRef>(map));
1.712 return *this;
1.713 }
1.714
1.715 @@ -982,20 +982,20 @@
1.716 template <typename NodeCrossRef>
1.717 GraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.718 _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
1.719 - NodeRefMap, NodeCrossRef>(map));
1.720 + NodeRefMap, NodeCrossRef>(map));
1.721 return *this;
1.722 }
1.723
1.724 /// \brief Make copy of the given map.
1.725 ///
1.726 - /// Makes copy of the given map for the newly created graph.
1.727 + /// Makes copy of the given map for the newly created graph.
1.728 /// The new map's key type is the to graph's node type,
1.729 /// and the copied map's key type is the from graph's node
1.730 - /// type.
1.731 + /// type.
1.732 template <typename ToMap, typename FromMap>
1.733 GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1.734 - _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
1.735 - NodeRefMap, ToMap, FromMap>(tmap, map));
1.736 + _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
1.737 + NodeRefMap, ToMap, FromMap>(tmap, map));
1.738 return *this;
1.739 }
1.740
1.741 @@ -1003,8 +1003,8 @@
1.742 ///
1.743 /// Make a copy of the given node.
1.744 GraphCopy& node(TNode& tnode, const Node& snode) {
1.745 - _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
1.746 - NodeRefMap, TNode>(tnode, snode));
1.747 + _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
1.748 + NodeRefMap, TNode>(tnode, snode));
1.749 return *this;
1.750 }
1.751
1.752 @@ -1013,8 +1013,8 @@
1.753 /// Copies the arc references into the given map.
1.754 template <typename ArcRef>
1.755 GraphCopy& arcRef(ArcRef& map) {
1.756 - _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
1.757 - ArcRefMap, ArcRef>(map));
1.758 + _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
1.759 + ArcRefMap, ArcRef>(map));
1.760 return *this;
1.761 }
1.762
1.763 @@ -1025,20 +1025,20 @@
1.764 template <typename ArcCrossRef>
1.765 GraphCopy& arcCrossRef(ArcCrossRef& map) {
1.766 _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
1.767 - ArcRefMap, ArcCrossRef>(map));
1.768 + ArcRefMap, ArcCrossRef>(map));
1.769 return *this;
1.770 }
1.771
1.772 /// \brief Make copy of the given map.
1.773 ///
1.774 - /// Makes copy of the given map for the newly created graph.
1.775 + /// Makes copy of the given map for the newly created graph.
1.776 /// The new map's key type is the to graph's arc type,
1.777 /// and the copied map's key type is the from graph's arc
1.778 - /// type.
1.779 + /// type.
1.780 template <typename ToMap, typename FromMap>
1.781 GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1.782 - _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
1.783 - ArcRefMap, ToMap, FromMap>(tmap, map));
1.784 + _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
1.785 + ArcRefMap, ToMap, FromMap>(tmap, map));
1.786 return *this;
1.787 }
1.788
1.789 @@ -1046,8 +1046,8 @@
1.790 ///
1.791 /// Make a copy of the given arc.
1.792 GraphCopy& arc(TArc& tarc, const Arc& sarc) {
1.793 - _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
1.794 - ArcRefMap, TArc>(tarc, sarc));
1.795 + _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
1.796 + ArcRefMap, TArc>(tarc, sarc));
1.797 return *this;
1.798 }
1.799
1.800 @@ -1056,8 +1056,8 @@
1.801 /// Copies the edge references into the given map.
1.802 template <typename EdgeRef>
1.803 GraphCopy& edgeRef(EdgeRef& map) {
1.804 - _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
1.805 - EdgeRefMap, EdgeRef>(map));
1.806 + _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
1.807 + EdgeRefMap, EdgeRef>(map));
1.808 return *this;
1.809 }
1.810
1.811 @@ -1067,21 +1067,21 @@
1.812 /// references) into the given map.
1.813 template <typename EdgeCrossRef>
1.814 GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.815 - _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
1.816 - Edge, EdgeRefMap, EdgeCrossRef>(map));
1.817 + _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
1.818 + Edge, EdgeRefMap, EdgeCrossRef>(map));
1.819 return *this;
1.820 }
1.821
1.822 /// \brief Make copy of the given map.
1.823 ///
1.824 - /// Makes copy of the given map for the newly created graph.
1.825 + /// Makes copy of the given map for the newly created graph.
1.826 /// The new map's key type is the to graph's edge type,
1.827 /// and the copied map's key type is the from graph's edge
1.828 - /// type.
1.829 + /// type.
1.830 template <typename ToMap, typename FromMap>
1.831 GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
1.832 - _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
1.833 - EdgeRefMap, ToMap, FromMap>(tmap, map));
1.834 + _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
1.835 + EdgeRefMap, ToMap, FromMap>(tmap, map));
1.836 return *this;
1.837 }
1.838
1.839 @@ -1089,8 +1089,8 @@
1.840 ///
1.841 /// Make a copy of the given edge.
1.842 GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1.843 - _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
1.844 - EdgeRefMap, TEdge>(tedge, sedge));
1.845 + _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
1.846 + EdgeRefMap, TEdge>(tedge, sedge));
1.847 return *this;
1.848 }
1.849
1.850 @@ -1115,17 +1115,17 @@
1.851 }
1.852
1.853 private:
1.854 -
1.855 +
1.856 const From& _from;
1.857 To& _to;
1.858
1.859 - std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.860 + std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.861 _node_maps;
1.862
1.863 - std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.864 + std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.865 _arc_maps;
1.866
1.867 - std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1.868 + std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1.869 _edge_maps;
1.870
1.871 };
1.872 @@ -1138,15 +1138,15 @@
1.873 ///\code
1.874 /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1.875 ///\endcode
1.876 - ///
1.877 + ///
1.878 /// After the copy the \c nr map will contain the mapping from the
1.879 /// nodes of the \c from graph to the nodes of the \c to graph and
1.880 /// \c ecr will contain the mapping from the arcs of the \c to graph
1.881 /// to the arcs of the \c from graph.
1.882 ///
1.883 - /// \see GraphCopy
1.884 + /// \see GraphCopy
1.885 template <typename To, typename From>
1.886 - GraphCopy<To, From>
1.887 + GraphCopy<To, From>
1.888 copyGraph(To& to, const From& from) {
1.889 return GraphCopy<To, From>(to, from);
1.890 }
1.891 @@ -1214,7 +1214,7 @@
1.892 /// \brief Gives back the given item from its id.
1.893 ///
1.894 /// Gives back the given item from its id.
1.895 - ///
1.896 + ///
1.897 Item operator[](int id) const { return _graph->fromId(id, Item());}
1.898
1.899 private:
1.900 @@ -1224,15 +1224,15 @@
1.901 /// \brief Gives back the inverse of the map.
1.902 ///
1.903 /// Gives back the inverse of the IdMap.
1.904 - InverseMap inverse() const { return InverseMap(*_graph);}
1.905 + InverseMap inverse() const { return InverseMap(*_graph);}
1.906
1.907 };
1.908
1.909 -
1.910 +
1.911 /// \brief General invertable graph-map type.
1.912
1.913 - /// This type provides simple invertable graph-maps.
1.914 - /// The InvertableMap wraps an arbitrary ReadWriteMap
1.915 + /// This type provides simple invertable graph-maps.
1.916 + /// The InvertableMap wraps an arbitrary ReadWriteMap
1.917 /// and if a key is set to a new value then store it
1.918 /// in the inverse map.
1.919 ///
1.920 @@ -1247,15 +1247,15 @@
1.921 template <typename _Graph, typename _Item, typename _Value>
1.922 class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
1.923 private:
1.924 -
1.925 +
1.926 typedef DefaultMap<_Graph, _Item, _Value> Map;
1.927 typedef _Graph Graph;
1.928
1.929 typedef std::map<_Value, _Item> Container;
1.930 - Container _inv_map;
1.931 + Container _inv_map;
1.932
1.933 public:
1.934 -
1.935 +
1.936 /// The key type of InvertableMap (Node, Arc, Edge).
1.937 typedef typename Map::Key Key;
1.938 /// The value type of the InvertableMap.
1.939 @@ -1267,7 +1267,7 @@
1.940 ///
1.941 /// Construct a new InvertableMap for the graph.
1.942 ///
1.943 - explicit InvertableMap(const Graph& graph) : Map(graph) {}
1.944 + explicit InvertableMap(const Graph& graph) : Map(graph) {}
1.945
1.946 /// \brief Forward iterator for values.
1.947 ///
1.948 @@ -1275,21 +1275,21 @@
1.949 /// iterator on the values of the map. The values can
1.950 /// be accessed in the [beginValue, endValue) range.
1.951 ///
1.952 - class ValueIterator
1.953 + class ValueIterator
1.954 : public std::iterator<std::forward_iterator_tag, Value> {
1.955 friend class InvertableMap;
1.956 private:
1.957 - ValueIterator(typename Container::const_iterator _it)
1.958 + ValueIterator(typename Container::const_iterator _it)
1.959 : it(_it) {}
1.960 public:
1.961 -
1.962 +
1.963 ValueIterator() {}
1.964
1.965 ValueIterator& operator++() { ++it; return *this; }
1.966 - ValueIterator operator++(int) {
1.967 - ValueIterator tmp(*this);
1.968 + ValueIterator operator++(int) {
1.969 + ValueIterator tmp(*this);
1.970 operator++();
1.971 - return tmp;
1.972 + return tmp;
1.973 }
1.974
1.975 const Value& operator*() const { return it->first; }
1.976 @@ -1297,14 +1297,14 @@
1.977
1.978 bool operator==(ValueIterator jt) const { return it == jt.it; }
1.979 bool operator!=(ValueIterator jt) const { return it != jt.it; }
1.980 -
1.981 +
1.982 private:
1.983 typename Container::const_iterator it;
1.984 };
1.985
1.986 /// \brief Returns an iterator to the first value.
1.987 ///
1.988 - /// Returns an stl compatible iterator to the
1.989 + /// Returns an stl compatible iterator to the
1.990 /// first value of the map. The values of the
1.991 /// map can be accessed in the [beginValue, endValue)
1.992 /// range.
1.993 @@ -1314,14 +1314,14 @@
1.994
1.995 /// \brief Returns an iterator after the last value.
1.996 ///
1.997 - /// Returns an stl compatible iterator after the
1.998 + /// Returns an stl compatible iterator after the
1.999 /// last value of the map. The values of the
1.1000 /// map can be accessed in the [beginValue, endValue)
1.1001 /// range.
1.1002 ValueIterator endValue() const {
1.1003 return ValueIterator(_inv_map.end());
1.1004 }
1.1005 -
1.1006 +
1.1007 /// \brief The setter function of the map.
1.1008 ///
1.1009 /// Sets the mapped value.
1.1010 @@ -1329,8 +1329,8 @@
1.1011 Value oldval = Map::operator[](key);
1.1012 typename Container::iterator it = _inv_map.find(oldval);
1.1013 if (it != _inv_map.end() && it->second == key) {
1.1014 - _inv_map.erase(it);
1.1015 - }
1.1016 + _inv_map.erase(it);
1.1017 + }
1.1018 _inv_map.insert(make_pair(val, key));
1.1019 Map::set(key, val);
1.1020 }
1.1021 @@ -1338,7 +1338,7 @@
1.1022 /// \brief The getter function of the map.
1.1023 ///
1.1024 /// It gives back the value associated with the key.
1.1025 - typename MapTraits<Map>::ConstReturnValue
1.1026 + typename MapTraits<Map>::ConstReturnValue
1.1027 operator[](const Key& key) const {
1.1028 return Map::operator[](key);
1.1029 }
1.1030 @@ -1361,7 +1361,7 @@
1.1031 Value val = Map::operator[](key);
1.1032 typename Container::iterator it = _inv_map.find(val);
1.1033 if (it != _inv_map.end() && it->second == key) {
1.1034 - _inv_map.erase(it);
1.1035 + _inv_map.erase(it);
1.1036 }
1.1037 Map::erase(key);
1.1038 }
1.1039 @@ -1372,11 +1372,11 @@
1.1040 /// \c AlterationNotifier.
1.1041 virtual void erase(const std::vector<Key>& keys) {
1.1042 for (int i = 0; i < int(keys.size()); ++i) {
1.1043 - Value val = Map::operator[](keys[i]);
1.1044 - typename Container::iterator it = _inv_map.find(val);
1.1045 - if (it != _inv_map.end() && it->second == keys[i]) {
1.1046 - _inv_map.erase(it);
1.1047 - }
1.1048 + Value val = Map::operator[](keys[i]);
1.1049 + typename Container::iterator it = _inv_map.find(val);
1.1050 + if (it != _inv_map.end() && it->second == keys[i]) {
1.1051 + _inv_map.erase(it);
1.1052 + }
1.1053 }
1.1054 Map::erase(keys);
1.1055 }
1.1056 @@ -1395,28 +1395,28 @@
1.1057 /// \brief The inverse map type.
1.1058 ///
1.1059 /// The inverse of this map. The subscript operator of the map
1.1060 - /// gives back always the item what was last assigned to the value.
1.1061 + /// gives back always the item what was last assigned to the value.
1.1062 class InverseMap {
1.1063 public:
1.1064 /// \brief Constructor of the InverseMap.
1.1065 ///
1.1066 /// Constructor of the InverseMap.
1.1067 - explicit InverseMap(const InvertableMap& inverted)
1.1068 + explicit InverseMap(const InvertableMap& inverted)
1.1069 : _inverted(inverted) {}
1.1070
1.1071 /// The value type of the InverseMap.
1.1072 typedef typename InvertableMap::Key Value;
1.1073 /// The key type of the InverseMap.
1.1074 - typedef typename InvertableMap::Value Key;
1.1075 -
1.1076 - /// \brief Subscript operator.
1.1077 + typedef typename InvertableMap::Value Key;
1.1078 +
1.1079 + /// \brief Subscript operator.
1.1080 ///
1.1081 - /// Subscript operator. It gives back always the item
1.1082 + /// Subscript operator. It gives back always the item
1.1083 /// what was last assigned to the value.
1.1084 Value operator[](const Key& key) const {
1.1085 - return _inverted(key);
1.1086 + return _inverted(key);
1.1087 }
1.1088 -
1.1089 +
1.1090 private:
1.1091 const InvertableMap& _inverted;
1.1092 };
1.1093 @@ -1426,13 +1426,13 @@
1.1094 /// It gives back the just readable inverse map.
1.1095 InverseMap inverse() const {
1.1096 return InverseMap(*this);
1.1097 - }
1.1098 -
1.1099 -
1.1100 -
1.1101 + }
1.1102 +
1.1103 +
1.1104 +
1.1105 };
1.1106
1.1107 - /// \brief Provides a mutable, continuous and unique descriptor for each
1.1108 + /// \brief Provides a mutable, continuous and unique descriptor for each
1.1109 /// item in the graph.
1.1110 ///
1.1111 /// The DescriptorMap class provides a unique and continuous (but mutable)
1.1112 @@ -1445,7 +1445,7 @@
1.1113 /// with its member class \c InverseMap, or with the \c operator() member.
1.1114 ///
1.1115 /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
1.1116 - /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
1.1117 + /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
1.1118 /// Edge.
1.1119 template <typename _Graph, typename _Item>
1.1120 class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
1.1121 @@ -1467,11 +1467,11 @@
1.1122 /// Constructor for descriptor map.
1.1123 explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1.1124 Item it;
1.1125 - const typename Map::Notifier* nf = Map::notifier();
1.1126 + const typename Map::Notifier* nf = Map::notifier();
1.1127 for (nf->first(it); it != INVALID; nf->next(it)) {
1.1128 - Map::set(it, _inv_map.size());
1.1129 - _inv_map.push_back(it);
1.1130 - }
1.1131 + Map::set(it, _inv_map.size());
1.1132 + _inv_map.push_back(it);
1.1133 + }
1.1134 }
1.1135
1.1136 protected:
1.1137 @@ -1493,8 +1493,8 @@
1.1138 virtual void add(const std::vector<Item>& items) {
1.1139 Map::add(items);
1.1140 for (int i = 0; i < int(items.size()); ++i) {
1.1141 - Map::set(items[i], _inv_map.size());
1.1142 - _inv_map.push_back(items[i]);
1.1143 + Map::set(items[i], _inv_map.size());
1.1144 + _inv_map.push_back(items[i]);
1.1145 }
1.1146 }
1.1147
1.1148 @@ -1515,9 +1515,9 @@
1.1149 /// \c AlterationNotifier.
1.1150 virtual void erase(const std::vector<Item>& items) {
1.1151 for (int i = 0; i < int(items.size()); ++i) {
1.1152 - Map::set(_inv_map.back(), Map::operator[](items[i]));
1.1153 - _inv_map[Map::operator[](items[i])] = _inv_map.back();
1.1154 - _inv_map.pop_back();
1.1155 + Map::set(_inv_map.back(), Map::operator[](items[i]));
1.1156 + _inv_map[Map::operator[](items[i])] = _inv_map.back();
1.1157 + _inv_map.pop_back();
1.1158 }
1.1159 Map::erase(items);
1.1160 }
1.1161 @@ -1529,13 +1529,13 @@
1.1162 virtual void build() {
1.1163 Map::build();
1.1164 Item it;
1.1165 - const typename Map::Notifier* nf = Map::notifier();
1.1166 + const typename Map::Notifier* nf = Map::notifier();
1.1167 for (nf->first(it); it != INVALID; nf->next(it)) {
1.1168 - Map::set(it, _inv_map.size());
1.1169 - _inv_map.push_back(it);
1.1170 - }
1.1171 + Map::set(it, _inv_map.size());
1.1172 + _inv_map.push_back(it);
1.1173 + }
1.1174 }
1.1175 -
1.1176 +
1.1177 /// \brief Clear the keys from the map.
1.1178 ///
1.1179 /// Clear the keys from the map. It is called by the
1.1180 @@ -1579,7 +1579,7 @@
1.1181 Item operator()(int id) const {
1.1182 return _inv_map[id];
1.1183 }
1.1184 -
1.1185 +
1.1186 private:
1.1187
1.1188 typedef std::vector<Item> Container;
1.1189 @@ -1594,30 +1594,30 @@
1.1190 /// \brief Constructor of the InverseMap.
1.1191 ///
1.1192 /// Constructor of the InverseMap.
1.1193 - explicit InverseMap(const DescriptorMap& inverted)
1.1194 - : _inverted(inverted) {}
1.1195 + explicit InverseMap(const DescriptorMap& inverted)
1.1196 + : _inverted(inverted) {}
1.1197
1.1198
1.1199 /// The value type of the InverseMap.
1.1200 typedef typename DescriptorMap::Key Value;
1.1201 /// The key type of the InverseMap.
1.1202 - typedef typename DescriptorMap::Value Key;
1.1203 -
1.1204 - /// \brief Subscript operator.
1.1205 + typedef typename DescriptorMap::Value Key;
1.1206 +
1.1207 + /// \brief Subscript operator.
1.1208 ///
1.1209 - /// Subscript operator. It gives back the item
1.1210 + /// Subscript operator. It gives back the item
1.1211 /// that the descriptor belongs to currently.
1.1212 Value operator[](const Key& key) const {
1.1213 - return _inverted(key);
1.1214 + return _inverted(key);
1.1215 }
1.1216
1.1217 /// \brief Size of the map.
1.1218 ///
1.1219 /// Returns the size of the map.
1.1220 unsigned int size() const {
1.1221 - return _inverted.size();
1.1222 + return _inverted.size();
1.1223 }
1.1224 -
1.1225 +
1.1226 private:
1.1227 const DescriptorMap& _inverted;
1.1228 };
1.1229 @@ -1632,7 +1632,7 @@
1.1230
1.1231 /// \brief Returns the source of the given arc.
1.1232 ///
1.1233 - /// The SourceMap gives back the source Node of the given arc.
1.1234 + /// The SourceMap gives back the source Node of the given arc.
1.1235 /// \see TargetMap
1.1236 template <typename Digraph>
1.1237 class SourceMap {
1.1238 @@ -1650,8 +1650,8 @@
1.1239 /// \brief The subscript operator.
1.1240 ///
1.1241 /// The subscript operator.
1.1242 - /// \param arc The arc
1.1243 - /// \return The source of the arc
1.1244 + /// \param arc The arc
1.1245 + /// \return The source of the arc
1.1246 Value operator[](const Key& arc) const {
1.1247 return _digraph.source(arc);
1.1248 }
1.1249 @@ -1667,11 +1667,11 @@
1.1250 template <typename Digraph>
1.1251 inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
1.1252 return SourceMap<Digraph>(digraph);
1.1253 - }
1.1254 + }
1.1255
1.1256 /// \brief Returns the target of the given arc.
1.1257 ///
1.1258 - /// The TargetMap gives back the target Node of the given arc.
1.1259 + /// The TargetMap gives back the target Node of the given arc.
1.1260 /// \see SourceMap
1.1261 template <typename Digraph>
1.1262 class TargetMap {
1.1263 @@ -1689,8 +1689,8 @@
1.1264 /// \brief The subscript operator.
1.1265 ///
1.1266 /// The subscript operator.
1.1267 - /// \param e The arc
1.1268 - /// \return The target of the arc
1.1269 + /// \param e The arc
1.1270 + /// \return The target of the arc
1.1271 Value operator[](const Key& e) const {
1.1272 return _digraph.target(e);
1.1273 }
1.1274 @@ -1728,8 +1728,8 @@
1.1275 /// \brief The subscript operator.
1.1276 ///
1.1277 /// The subscript operator.
1.1278 - /// \param key An edge
1.1279 - /// \return The "forward" directed arc view of edge
1.1280 + /// \param key An edge
1.1281 + /// \return The "forward" directed arc view of edge
1.1282 Value operator[](const Key& key) const {
1.1283 return _graph.direct(key, true);
1.1284 }
1.1285 @@ -1767,8 +1767,8 @@
1.1286 /// \brief The subscript operator.
1.1287 ///
1.1288 /// The subscript operator.
1.1289 - /// \param key An edge
1.1290 - /// \return The "backward" directed arc view of edge
1.1291 + /// \param key An edge
1.1292 + /// \return The "backward" directed arc view of edge
1.1293 Value operator[](const Key& key) const {
1.1294 return _graph.direct(key, false);
1.1295 }
1.1296 @@ -1800,16 +1800,16 @@
1.1297 /// \brief Constructor
1.1298 ///
1.1299 /// Contructor of the map
1.1300 - explicit PotentialDifferenceMap(const Digraph& digraph,
1.1301 - const NodeMap& potential)
1.1302 + explicit PotentialDifferenceMap(const Digraph& digraph,
1.1303 + const NodeMap& potential)
1.1304 : _digraph(digraph), _potential(potential) {}
1.1305
1.1306 /// \brief Const subscription operator
1.1307 ///
1.1308 /// Const subscription operator
1.1309 Value operator[](const Key& arc) const {
1.1310 - return _potential[_digraph.target(arc)] -
1.1311 - _potential[_digraph.source(arc)];
1.1312 + return _potential[_digraph.target(arc)] -
1.1313 + _potential[_digraph.source(arc)];
1.1314 }
1.1315
1.1316 private:
1.1317 @@ -1822,7 +1822,7 @@
1.1318 /// This function just returns a PotentialDifferenceMap.
1.1319 /// \relates PotentialDifferenceMap
1.1320 template <typename Digraph, typename NodeMap>
1.1321 - PotentialDifferenceMap<Digraph, NodeMap>
1.1322 + PotentialDifferenceMap<Digraph, NodeMap>
1.1323 potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
1.1324 return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
1.1325 }
1.1326 @@ -1845,12 +1845,12 @@
1.1327 /// \sa OutDegMap
1.1328
1.1329 template <typename _Digraph>
1.1330 - class InDegMap
1.1331 + class InDegMap
1.1332 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
1.1333 ::ItemNotifier::ObserverBase {
1.1334
1.1335 public:
1.1336 -
1.1337 +
1.1338 typedef _Digraph Digraph;
1.1339 typedef int Value;
1.1340 typedef typename Digraph::Node Key;
1.1341 @@ -1866,26 +1866,26 @@
1.1342 typedef DefaultMap<Digraph, Key, int> Parent;
1.1343
1.1344 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
1.1345 -
1.1346 +
1.1347 virtual void add(const Key& key) {
1.1348 - Parent::add(key);
1.1349 - Parent::set(key, 0);
1.1350 + Parent::add(key);
1.1351 + Parent::set(key, 0);
1.1352 }
1.1353
1.1354 virtual void add(const std::vector<Key>& keys) {
1.1355 - Parent::add(keys);
1.1356 - for (int i = 0; i < int(keys.size()); ++i) {
1.1357 - Parent::set(keys[i], 0);
1.1358 - }
1.1359 + Parent::add(keys);
1.1360 + for (int i = 0; i < int(keys.size()); ++i) {
1.1361 + Parent::set(keys[i], 0);
1.1362 + }
1.1363 }
1.1364
1.1365 virtual void build() {
1.1366 - Parent::build();
1.1367 - Key it;
1.1368 - typename Parent::Notifier* nf = Parent::notifier();
1.1369 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.1370 - Parent::set(it, 0);
1.1371 - }
1.1372 + Parent::build();
1.1373 + Key it;
1.1374 + typename Parent::Notifier* nf = Parent::notifier();
1.1375 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.1376 + Parent::set(it, 0);
1.1377 + }
1.1378 }
1.1379 };
1.1380
1.1381 @@ -1894,22 +1894,22 @@
1.1382 /// \brief Constructor.
1.1383 ///
1.1384 /// Constructor for creating in-degree map.
1.1385 - explicit InDegMap(const Digraph& digraph)
1.1386 + explicit InDegMap(const Digraph& digraph)
1.1387 : _digraph(digraph), _deg(digraph) {
1.1388 Parent::attach(_digraph.notifier(typename Digraph::Arc()));
1.1389 -
1.1390 +
1.1391 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.1392 - _deg[it] = countInArcs(_digraph, it);
1.1393 + _deg[it] = countInArcs(_digraph, it);
1.1394 }
1.1395 }
1.1396 -
1.1397 +
1.1398 /// Gives back the in-degree of a Node.
1.1399 int operator[](const Key& key) const {
1.1400 return _deg[key];
1.1401 }
1.1402
1.1403 protected:
1.1404 -
1.1405 +
1.1406 typedef typename Digraph::Arc Arc;
1.1407
1.1408 virtual void add(const Arc& arc) {
1.1409 @@ -1934,17 +1934,17 @@
1.1410
1.1411 virtual void build() {
1.1412 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.1413 - _deg[it] = countInArcs(_digraph, it);
1.1414 - }
1.1415 + _deg[it] = countInArcs(_digraph, it);
1.1416 + }
1.1417 }
1.1418
1.1419 virtual void clear() {
1.1420 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.1421 - _deg[it] = 0;
1.1422 + _deg[it] = 0;
1.1423 }
1.1424 }
1.1425 private:
1.1426 -
1.1427 +
1.1428 const Digraph& _digraph;
1.1429 AutoNodeMap _deg;
1.1430 };
1.1431 @@ -1967,12 +1967,12 @@
1.1432 /// \sa InDegMap
1.1433
1.1434 template <typename _Digraph>
1.1435 - class OutDegMap
1.1436 + class OutDegMap
1.1437 : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
1.1438 ::ItemNotifier::ObserverBase {
1.1439
1.1440 public:
1.1441 -
1.1442 +
1.1443 typedef _Digraph Digraph;
1.1444 typedef int Value;
1.1445 typedef typename Digraph::Node Key;
1.1446 @@ -1988,24 +1988,24 @@
1.1447 typedef DefaultMap<Digraph, Key, int> Parent;
1.1448
1.1449 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
1.1450 -
1.1451 +
1.1452 virtual void add(const Key& key) {
1.1453 - Parent::add(key);
1.1454 - Parent::set(key, 0);
1.1455 + Parent::add(key);
1.1456 + Parent::set(key, 0);
1.1457 }
1.1458 virtual void add(const std::vector<Key>& keys) {
1.1459 - Parent::add(keys);
1.1460 - for (int i = 0; i < int(keys.size()); ++i) {
1.1461 - Parent::set(keys[i], 0);
1.1462 - }
1.1463 + Parent::add(keys);
1.1464 + for (int i = 0; i < int(keys.size()); ++i) {
1.1465 + Parent::set(keys[i], 0);
1.1466 + }
1.1467 }
1.1468 virtual void build() {
1.1469 - Parent::build();
1.1470 - Key it;
1.1471 - typename Parent::Notifier* nf = Parent::notifier();
1.1472 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.1473 - Parent::set(it, 0);
1.1474 - }
1.1475 + Parent::build();
1.1476 + Key it;
1.1477 + typename Parent::Notifier* nf = Parent::notifier();
1.1478 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.1479 + Parent::set(it, 0);
1.1480 + }
1.1481 }
1.1482 };
1.1483
1.1484 @@ -2014,12 +2014,12 @@
1.1485 /// \brief Constructor.
1.1486 ///
1.1487 /// Constructor for creating out-degree map.
1.1488 - explicit OutDegMap(const Digraph& digraph)
1.1489 + explicit OutDegMap(const Digraph& digraph)
1.1490 : _digraph(digraph), _deg(digraph) {
1.1491 Parent::attach(_digraph.notifier(typename Digraph::Arc()));
1.1492 -
1.1493 +
1.1494 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.1495 - _deg[it] = countOutArcs(_digraph, it);
1.1496 + _deg[it] = countOutArcs(_digraph, it);
1.1497 }
1.1498 }
1.1499
1.1500 @@ -2029,7 +2029,7 @@
1.1501 }
1.1502
1.1503 protected:
1.1504 -
1.1505 +
1.1506 typedef typename Digraph::Arc Arc;
1.1507
1.1508 virtual void add(const Arc& arc) {
1.1509 @@ -2054,24 +2054,24 @@
1.1510
1.1511 virtual void build() {
1.1512 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.1513 - _deg[it] = countOutArcs(_digraph, it);
1.1514 - }
1.1515 + _deg[it] = countOutArcs(_digraph, it);
1.1516 + }
1.1517 }
1.1518
1.1519 virtual void clear() {
1.1520 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.1521 - _deg[it] = 0;
1.1522 + _deg[it] = 0;
1.1523 }
1.1524 }
1.1525 private:
1.1526 -
1.1527 +
1.1528 const Digraph& _digraph;
1.1529 AutoNodeMap _deg;
1.1530 };
1.1531
1.1532
1.1533 ///Dynamic arc look up between given endpoints.
1.1534 -
1.1535 +
1.1536 ///\ingroup gutils
1.1537 ///Using this class, you can find an arc in a digraph from a given
1.1538 ///source to a given target in amortized time <em>O(log d)</em>,
1.1539 @@ -2089,12 +2089,12 @@
1.1540 ///optimal time bound in a constant factor for any distribution of
1.1541 ///queries.
1.1542 ///
1.1543 - ///\tparam G The type of the underlying digraph.
1.1544 + ///\tparam G The type of the underlying digraph.
1.1545 ///
1.1546 - ///\sa ArcLookUp
1.1547 - ///\sa AllArcLookUp
1.1548 + ///\sa ArcLookUp
1.1549 + ///\sa AllArcLookUp
1.1550 template<class G>
1.1551 - class DynArcLookUp
1.1552 + class DynArcLookUp
1.1553 : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
1.1554 {
1.1555 public:
1.1556 @@ -2112,26 +2112,26 @@
1.1557 typedef DefaultMap<G, Node, Arc> Parent;
1.1558
1.1559 AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
1.1560 -
1.1561 +
1.1562 virtual void add(const Node& node) {
1.1563 - Parent::add(node);
1.1564 - Parent::set(node, INVALID);
1.1565 + Parent::add(node);
1.1566 + Parent::set(node, INVALID);
1.1567 }
1.1568
1.1569 virtual void add(const std::vector<Node>& nodes) {
1.1570 - Parent::add(nodes);
1.1571 - for (int i = 0; i < int(nodes.size()); ++i) {
1.1572 - Parent::set(nodes[i], INVALID);
1.1573 - }
1.1574 + Parent::add(nodes);
1.1575 + for (int i = 0; i < int(nodes.size()); ++i) {
1.1576 + Parent::set(nodes[i], INVALID);
1.1577 + }
1.1578 }
1.1579
1.1580 virtual void build() {
1.1581 - Parent::build();
1.1582 - Node it;
1.1583 - typename Parent::Notifier* nf = Parent::notifier();
1.1584 - for (nf->first(it); it != INVALID; nf->next(it)) {
1.1585 - Parent::set(it, INVALID);
1.1586 - }
1.1587 + Parent::build();
1.1588 + Node it;
1.1589 + typename Parent::Notifier* nf = Parent::notifier();
1.1590 + for (nf->first(it); it != INVALID; nf->next(it)) {
1.1591 + Parent::set(it, INVALID);
1.1592 + }
1.1593 }
1.1594 };
1.1595
1.1596 @@ -2140,31 +2140,31 @@
1.1597 typename Digraph::template ArcMap<Arc> _parent;
1.1598 typename Digraph::template ArcMap<Arc> _left;
1.1599 typename Digraph::template ArcMap<Arc> _right;
1.1600 -
1.1601 +
1.1602 class ArcLess {
1.1603 const Digraph &g;
1.1604 public:
1.1605 ArcLess(const Digraph &_g) : g(_g) {}
1.1606 - bool operator()(Arc a,Arc b) const
1.1607 + bool operator()(Arc a,Arc b) const
1.1608 {
1.1609 - return g.target(a)<g.target(b);
1.1610 + return g.target(a)<g.target(b);
1.1611 }
1.1612 };
1.1613 -
1.1614 +
1.1615 public:
1.1616 -
1.1617 +
1.1618 ///Constructor
1.1619
1.1620 ///Constructor.
1.1621 ///
1.1622 ///It builds up the search database.
1.1623 - DynArcLookUp(const Digraph &g)
1.1624 - : _g(g),_head(g),_parent(g),_left(g),_right(g)
1.1625 - {
1.1626 + DynArcLookUp(const Digraph &g)
1.1627 + : _g(g),_head(g),_parent(g),_left(g),_right(g)
1.1628 + {
1.1629 Parent::attach(_g.notifier(typename Digraph::Arc()));
1.1630 - refresh();
1.1631 + refresh();
1.1632 }
1.1633 -
1.1634 +
1.1635 protected:
1.1636
1.1637 virtual void add(const Arc& arc) {
1.1638 @@ -2173,7 +2173,7 @@
1.1639
1.1640 virtual void add(const std::vector<Arc>& arcs) {
1.1641 for (int i = 0; i < int(arcs.size()); ++i) {
1.1642 - insert(arcs[i]);
1.1643 + insert(arcs[i]);
1.1644 }
1.1645 }
1.1646
1.1647 @@ -2183,8 +2183,8 @@
1.1648
1.1649 virtual void erase(const std::vector<Arc>& arcs) {
1.1650 for (int i = 0; i < int(arcs.size()); ++i) {
1.1651 - remove(arcs[i]);
1.1652 - }
1.1653 + remove(arcs[i]);
1.1654 + }
1.1655 }
1.1656
1.1657 virtual void build() {
1.1658 @@ -2193,7 +2193,7 @@
1.1659
1.1660 virtual void clear() {
1.1661 for(NodeIt n(_g);n!=INVALID;++n) {
1.1662 - _head.set(n, INVALID);
1.1663 + _head.set(n, INVALID);
1.1664 }
1.1665 }
1.1666
1.1667 @@ -2202,212 +2202,212 @@
1.1668 Node t = _g.target(arc);
1.1669 _left.set(arc, INVALID);
1.1670 _right.set(arc, INVALID);
1.1671 -
1.1672 +
1.1673 Arc e = _head[s];
1.1674 if (e == INVALID) {
1.1675 - _head.set(s, arc);
1.1676 - _parent.set(arc, INVALID);
1.1677 - return;
1.1678 + _head.set(s, arc);
1.1679 + _parent.set(arc, INVALID);
1.1680 + return;
1.1681 }
1.1682 while (true) {
1.1683 - if (t < _g.target(e)) {
1.1684 - if (_left[e] == INVALID) {
1.1685 - _left.set(e, arc);
1.1686 - _parent.set(arc, e);
1.1687 - splay(arc);
1.1688 - return;
1.1689 - } else {
1.1690 - e = _left[e];
1.1691 - }
1.1692 - } else {
1.1693 - if (_right[e] == INVALID) {
1.1694 - _right.set(e, arc);
1.1695 - _parent.set(arc, e);
1.1696 - splay(arc);
1.1697 - return;
1.1698 - } else {
1.1699 - e = _right[e];
1.1700 - }
1.1701 - }
1.1702 + if (t < _g.target(e)) {
1.1703 + if (_left[e] == INVALID) {
1.1704 + _left.set(e, arc);
1.1705 + _parent.set(arc, e);
1.1706 + splay(arc);
1.1707 + return;
1.1708 + } else {
1.1709 + e = _left[e];
1.1710 + }
1.1711 + } else {
1.1712 + if (_right[e] == INVALID) {
1.1713 + _right.set(e, arc);
1.1714 + _parent.set(arc, e);
1.1715 + splay(arc);
1.1716 + return;
1.1717 + } else {
1.1718 + e = _right[e];
1.1719 + }
1.1720 + }
1.1721 }
1.1722 }
1.1723
1.1724 void remove(Arc arc) {
1.1725 if (_left[arc] == INVALID) {
1.1726 - if (_right[arc] != INVALID) {
1.1727 - _parent.set(_right[arc], _parent[arc]);
1.1728 - }
1.1729 - if (_parent[arc] != INVALID) {
1.1730 - if (_left[_parent[arc]] == arc) {
1.1731 - _left.set(_parent[arc], _right[arc]);
1.1732 - } else {
1.1733 - _right.set(_parent[arc], _right[arc]);
1.1734 - }
1.1735 - } else {
1.1736 - _head.set(_g.source(arc), _right[arc]);
1.1737 - }
1.1738 + if (_right[arc] != INVALID) {
1.1739 + _parent.set(_right[arc], _parent[arc]);
1.1740 + }
1.1741 + if (_parent[arc] != INVALID) {
1.1742 + if (_left[_parent[arc]] == arc) {
1.1743 + _left.set(_parent[arc], _right[arc]);
1.1744 + } else {
1.1745 + _right.set(_parent[arc], _right[arc]);
1.1746 + }
1.1747 + } else {
1.1748 + _head.set(_g.source(arc), _right[arc]);
1.1749 + }
1.1750 } else if (_right[arc] == INVALID) {
1.1751 - _parent.set(_left[arc], _parent[arc]);
1.1752 - if (_parent[arc] != INVALID) {
1.1753 - if (_left[_parent[arc]] == arc) {
1.1754 - _left.set(_parent[arc], _left[arc]);
1.1755 - } else {
1.1756 - _right.set(_parent[arc], _left[arc]);
1.1757 - }
1.1758 - } else {
1.1759 - _head.set(_g.source(arc), _left[arc]);
1.1760 - }
1.1761 + _parent.set(_left[arc], _parent[arc]);
1.1762 + if (_parent[arc] != INVALID) {
1.1763 + if (_left[_parent[arc]] == arc) {
1.1764 + _left.set(_parent[arc], _left[arc]);
1.1765 + } else {
1.1766 + _right.set(_parent[arc], _left[arc]);
1.1767 + }
1.1768 + } else {
1.1769 + _head.set(_g.source(arc), _left[arc]);
1.1770 + }
1.1771 } else {
1.1772 - Arc e = _left[arc];
1.1773 - if (_right[e] != INVALID) {
1.1774 - e = _right[e];
1.1775 - while (_right[e] != INVALID) {
1.1776 - e = _right[e];
1.1777 - }
1.1778 - Arc s = _parent[e];
1.1779 - _right.set(_parent[e], _left[e]);
1.1780 - if (_left[e] != INVALID) {
1.1781 - _parent.set(_left[e], _parent[e]);
1.1782 - }
1.1783 -
1.1784 - _left.set(e, _left[arc]);
1.1785 - _parent.set(_left[arc], e);
1.1786 - _right.set(e, _right[arc]);
1.1787 - _parent.set(_right[arc], e);
1.1788 -
1.1789 - _parent.set(e, _parent[arc]);
1.1790 - if (_parent[arc] != INVALID) {
1.1791 - if (_left[_parent[arc]] == arc) {
1.1792 - _left.set(_parent[arc], e);
1.1793 - } else {
1.1794 - _right.set(_parent[arc], e);
1.1795 - }
1.1796 - }
1.1797 - splay(s);
1.1798 - } else {
1.1799 - _right.set(e, _right[arc]);
1.1800 - _parent.set(_right[arc], e);
1.1801 -
1.1802 - if (_parent[arc] != INVALID) {
1.1803 - if (_left[_parent[arc]] == arc) {
1.1804 - _left.set(_parent[arc], e);
1.1805 - } else {
1.1806 - _right.set(_parent[arc], e);
1.1807 - }
1.1808 - } else {
1.1809 - _head.set(_g.source(arc), e);
1.1810 - }
1.1811 - }
1.1812 + Arc e = _left[arc];
1.1813 + if (_right[e] != INVALID) {
1.1814 + e = _right[e];
1.1815 + while (_right[e] != INVALID) {
1.1816 + e = _right[e];
1.1817 + }
1.1818 + Arc s = _parent[e];
1.1819 + _right.set(_parent[e], _left[e]);
1.1820 + if (_left[e] != INVALID) {
1.1821 + _parent.set(_left[e], _parent[e]);
1.1822 + }
1.1823 +
1.1824 + _left.set(e, _left[arc]);
1.1825 + _parent.set(_left[arc], e);
1.1826 + _right.set(e, _right[arc]);
1.1827 + _parent.set(_right[arc], e);
1.1828 +
1.1829 + _parent.set(e, _parent[arc]);
1.1830 + if (_parent[arc] != INVALID) {
1.1831 + if (_left[_parent[arc]] == arc) {
1.1832 + _left.set(_parent[arc], e);
1.1833 + } else {
1.1834 + _right.set(_parent[arc], e);
1.1835 + }
1.1836 + }
1.1837 + splay(s);
1.1838 + } else {
1.1839 + _right.set(e, _right[arc]);
1.1840 + _parent.set(_right[arc], e);
1.1841 +
1.1842 + if (_parent[arc] != INVALID) {
1.1843 + if (_left[_parent[arc]] == arc) {
1.1844 + _left.set(_parent[arc], e);
1.1845 + } else {
1.1846 + _right.set(_parent[arc], e);
1.1847 + }
1.1848 + } else {
1.1849 + _head.set(_g.source(arc), e);
1.1850 + }
1.1851 + }
1.1852 }
1.1853 }
1.1854
1.1855 - Arc refreshRec(std::vector<Arc> &v,int a,int b)
1.1856 + Arc refreshRec(std::vector<Arc> &v,int a,int b)
1.1857 {
1.1858 int m=(a+b)/2;
1.1859 Arc me=v[m];
1.1860 if (a < m) {
1.1861 - Arc left = refreshRec(v,a,m-1);
1.1862 - _left.set(me, left);
1.1863 - _parent.set(left, me);
1.1864 + Arc left = refreshRec(v,a,m-1);
1.1865 + _left.set(me, left);
1.1866 + _parent.set(left, me);
1.1867 } else {
1.1868 - _left.set(me, INVALID);
1.1869 + _left.set(me, INVALID);
1.1870 }
1.1871 if (m < b) {
1.1872 - Arc right = refreshRec(v,m+1,b);
1.1873 - _right.set(me, right);
1.1874 - _parent.set(right, me);
1.1875 + Arc right = refreshRec(v,m+1,b);
1.1876 + _right.set(me, right);
1.1877 + _parent.set(right, me);
1.1878 } else {
1.1879 - _right.set(me, INVALID);
1.1880 + _right.set(me, INVALID);
1.1881 }
1.1882 return me;
1.1883 }
1.1884
1.1885 void refresh() {
1.1886 for(NodeIt n(_g);n!=INVALID;++n) {
1.1887 - std::vector<Arc> v;
1.1888 - for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1.1889 - if(v.size()) {
1.1890 - std::sort(v.begin(),v.end(),ArcLess(_g));
1.1891 - Arc head = refreshRec(v,0,v.size()-1);
1.1892 - _head.set(n, head);
1.1893 - _parent.set(head, INVALID);
1.1894 - }
1.1895 - else _head.set(n, INVALID);
1.1896 + std::vector<Arc> v;
1.1897 + for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1.1898 + if(v.size()) {
1.1899 + std::sort(v.begin(),v.end(),ArcLess(_g));
1.1900 + Arc head = refreshRec(v,0,v.size()-1);
1.1901 + _head.set(n, head);
1.1902 + _parent.set(head, INVALID);
1.1903 + }
1.1904 + else _head.set(n, INVALID);
1.1905 }
1.1906 }
1.1907
1.1908 - void zig(Arc v) {
1.1909 + void zig(Arc v) {
1.1910 Arc w = _parent[v];
1.1911 _parent.set(v, _parent[w]);
1.1912 _parent.set(w, v);
1.1913 _left.set(w, _right[v]);
1.1914 _right.set(v, w);
1.1915 if (_parent[v] != INVALID) {
1.1916 - if (_right[_parent[v]] == w) {
1.1917 - _right.set(_parent[v], v);
1.1918 - } else {
1.1919 - _left.set(_parent[v], v);
1.1920 - }
1.1921 + if (_right[_parent[v]] == w) {
1.1922 + _right.set(_parent[v], v);
1.1923 + } else {
1.1924 + _left.set(_parent[v], v);
1.1925 + }
1.1926 }
1.1927 if (_left[w] != INVALID){
1.1928 - _parent.set(_left[w], w);
1.1929 + _parent.set(_left[w], w);
1.1930 }
1.1931 }
1.1932
1.1933 - void zag(Arc v) {
1.1934 + void zag(Arc v) {
1.1935 Arc w = _parent[v];
1.1936 _parent.set(v, _parent[w]);
1.1937 _parent.set(w, v);
1.1938 _right.set(w, _left[v]);
1.1939 _left.set(v, w);
1.1940 if (_parent[v] != INVALID){
1.1941 - if (_left[_parent[v]] == w) {
1.1942 - _left.set(_parent[v], v);
1.1943 - } else {
1.1944 - _right.set(_parent[v], v);
1.1945 - }
1.1946 + if (_left[_parent[v]] == w) {
1.1947 + _left.set(_parent[v], v);
1.1948 + } else {
1.1949 + _right.set(_parent[v], v);
1.1950 + }
1.1951 }
1.1952 if (_right[w] != INVALID){
1.1953 - _parent.set(_right[w], w);
1.1954 + _parent.set(_right[w], w);
1.1955 }
1.1956 }
1.1957
1.1958 void splay(Arc v) {
1.1959 while (_parent[v] != INVALID) {
1.1960 - if (v == _left[_parent[v]]) {
1.1961 - if (_parent[_parent[v]] == INVALID) {
1.1962 - zig(v);
1.1963 - } else {
1.1964 - if (_parent[v] == _left[_parent[_parent[v]]]) {
1.1965 - zig(_parent[v]);
1.1966 - zig(v);
1.1967 - } else {
1.1968 - zig(v);
1.1969 - zag(v);
1.1970 - }
1.1971 - }
1.1972 - } else {
1.1973 - if (_parent[_parent[v]] == INVALID) {
1.1974 - zag(v);
1.1975 - } else {
1.1976 - if (_parent[v] == _left[_parent[_parent[v]]]) {
1.1977 - zag(v);
1.1978 - zig(v);
1.1979 - } else {
1.1980 - zag(_parent[v]);
1.1981 - zag(v);
1.1982 - }
1.1983 - }
1.1984 - }
1.1985 + if (v == _left[_parent[v]]) {
1.1986 + if (_parent[_parent[v]] == INVALID) {
1.1987 + zig(v);
1.1988 + } else {
1.1989 + if (_parent[v] == _left[_parent[_parent[v]]]) {
1.1990 + zig(_parent[v]);
1.1991 + zig(v);
1.1992 + } else {
1.1993 + zig(v);
1.1994 + zag(v);
1.1995 + }
1.1996 + }
1.1997 + } else {
1.1998 + if (_parent[_parent[v]] == INVALID) {
1.1999 + zag(v);
1.2000 + } else {
1.2001 + if (_parent[v] == _left[_parent[_parent[v]]]) {
1.2002 + zag(v);
1.2003 + zig(v);
1.2004 + } else {
1.2005 + zag(_parent[v]);
1.2006 + zag(v);
1.2007 + }
1.2008 + }
1.2009 + }
1.2010 }
1.2011 _head[_g.source(v)] = v;
1.2012 }
1.2013
1.2014
1.2015 public:
1.2016 -
1.2017 +
1.2018 ///Find an arc between two nodes.
1.2019 -
1.2020 +
1.2021 ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
1.2022 /// <em>d</em> is the number of outgoing arcs of \c s.
1.2023 ///\param s The source node
1.2024 @@ -2418,33 +2418,33 @@
1.2025 {
1.2026 Arc a = _head[s];
1.2027 while (true) {
1.2028 - if (_g.target(a) == t) {
1.2029 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2030 - return a;
1.2031 - } else if (t < _g.target(a)) {
1.2032 - if (_left[a] == INVALID) {
1.2033 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2034 - return INVALID;
1.2035 - } else {
1.2036 - a = _left[a];
1.2037 - }
1.2038 - } else {
1.2039 - if (_right[a] == INVALID) {
1.2040 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2041 - return INVALID;
1.2042 - } else {
1.2043 - a = _right[a];
1.2044 - }
1.2045 - }
1.2046 + if (_g.target(a) == t) {
1.2047 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2048 + return a;
1.2049 + } else if (t < _g.target(a)) {
1.2050 + if (_left[a] == INVALID) {
1.2051 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2052 + return INVALID;
1.2053 + } else {
1.2054 + a = _left[a];
1.2055 + }
1.2056 + } else {
1.2057 + if (_right[a] == INVALID) {
1.2058 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2059 + return INVALID;
1.2060 + } else {
1.2061 + a = _right[a];
1.2062 + }
1.2063 + }
1.2064 }
1.2065 }
1.2066
1.2067 ///Find the first arc between two nodes.
1.2068 -
1.2069 +
1.2070 ///Find the first arc between two nodes in time
1.2071 /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
1.2072 - /// outgoing arcs of \c s.
1.2073 - ///\param s The source node
1.2074 + /// outgoing arcs of \c s.
1.2075 + ///\param s The source node
1.2076 ///\param t The target node
1.2077 ///\return An arc from \c s to \c t if there exists, \ref INVALID
1.2078 /// otherwise.
1.2079 @@ -2453,33 +2453,33 @@
1.2080 Arc a = _head[s];
1.2081 Arc r = INVALID;
1.2082 while (true) {
1.2083 - if (_g.target(a) < t) {
1.2084 - if (_right[a] == INVALID) {
1.2085 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2086 - return r;
1.2087 - } else {
1.2088 - a = _right[a];
1.2089 - }
1.2090 - } else {
1.2091 - if (_g.target(a) == t) {
1.2092 - r = a;
1.2093 - }
1.2094 - if (_left[a] == INVALID) {
1.2095 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2096 - return r;
1.2097 - } else {
1.2098 - a = _left[a];
1.2099 - }
1.2100 - }
1.2101 + if (_g.target(a) < t) {
1.2102 + if (_right[a] == INVALID) {
1.2103 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2104 + return r;
1.2105 + } else {
1.2106 + a = _right[a];
1.2107 + }
1.2108 + } else {
1.2109 + if (_g.target(a) == t) {
1.2110 + r = a;
1.2111 + }
1.2112 + if (_left[a] == INVALID) {
1.2113 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2114 + return r;
1.2115 + } else {
1.2116 + a = _left[a];
1.2117 + }
1.2118 + }
1.2119 }
1.2120 }
1.2121
1.2122 ///Find the next arc between two nodes.
1.2123 -
1.2124 +
1.2125 ///Find the next arc between two nodes in time
1.2126 /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
1.2127 - /// outgoing arcs of \c s.
1.2128 - ///\param s The source node
1.2129 + /// outgoing arcs of \c s.
1.2130 + ///\param s The source node
1.2131 ///\param t The target node
1.2132 ///\return An arc from \c s to \c t if there exists, \ref INVALID
1.2133 /// otherwise.
1.2134 @@ -2493,30 +2493,30 @@
1.2135 #endif
1.2136 {
1.2137 if (_right[a] != INVALID) {
1.2138 - a = _right[a];
1.2139 - while (_left[a] != INVALID) {
1.2140 - a = _left[a];
1.2141 - }
1.2142 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2143 + a = _right[a];
1.2144 + while (_left[a] != INVALID) {
1.2145 + a = _left[a];
1.2146 + }
1.2147 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2148 } else {
1.2149 - while (_parent[a] != INVALID && _right[_parent[a]] == a) {
1.2150 - a = _parent[a];
1.2151 - }
1.2152 - if (_parent[a] == INVALID) {
1.2153 - return INVALID;
1.2154 - } else {
1.2155 - a = _parent[a];
1.2156 - const_cast<DynArcLookUp&>(*this).splay(a);
1.2157 - }
1.2158 + while (_parent[a] != INVALID && _right[_parent[a]] == a) {
1.2159 + a = _parent[a];
1.2160 + }
1.2161 + if (_parent[a] == INVALID) {
1.2162 + return INVALID;
1.2163 + } else {
1.2164 + a = _parent[a];
1.2165 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2166 + }
1.2167 }
1.2168 if (_g.target(a) == t) return a;
1.2169 - else return INVALID;
1.2170 + else return INVALID;
1.2171 }
1.2172
1.2173 };
1.2174
1.2175 ///Fast arc look up between given endpoints.
1.2176 -
1.2177 +
1.2178 ///\ingroup gutils
1.2179 ///Using this class, you can find an arc in a digraph from a given
1.2180 ///source to a given target in time <em>O(log d)</em>,
1.2181 @@ -2533,9 +2533,9 @@
1.2182 ///\tparam G The type of the underlying digraph.
1.2183 ///
1.2184 ///\sa DynArcLookUp
1.2185 - ///\sa AllArcLookUp
1.2186 + ///\sa AllArcLookUp
1.2187 template<class G>
1.2188 - class ArcLookUp
1.2189 + class ArcLookUp
1.2190 {
1.2191 public:
1.2192 TEMPLATE_DIGRAPH_TYPEDEFS(G);
1.2193 @@ -2546,19 +2546,19 @@
1.2194 typename Digraph::template NodeMap<Arc> _head;
1.2195 typename Digraph::template ArcMap<Arc> _left;
1.2196 typename Digraph::template ArcMap<Arc> _right;
1.2197 -
1.2198 +
1.2199 class ArcLess {
1.2200 const Digraph &g;
1.2201 public:
1.2202 ArcLess(const Digraph &_g) : g(_g) {}
1.2203 - bool operator()(Arc a,Arc b) const
1.2204 + bool operator()(Arc a,Arc b) const
1.2205 {
1.2206 - return g.target(a)<g.target(b);
1.2207 + return g.target(a)<g.target(b);
1.2208 }
1.2209 };
1.2210 -
1.2211 +
1.2212 public:
1.2213 -
1.2214 +
1.2215 ///Constructor
1.2216
1.2217 ///Constructor.
1.2218 @@ -2566,9 +2566,9 @@
1.2219 ///It builds up the search database, which remains valid until the digraph
1.2220 ///changes.
1.2221 ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
1.2222 -
1.2223 +
1.2224 private:
1.2225 - Arc refreshRec(std::vector<Arc> &v,int a,int b)
1.2226 + Arc refreshRec(std::vector<Arc> &v,int a,int b)
1.2227 {
1.2228 int m=(a+b)/2;
1.2229 Arc me=v[m];
1.2230 @@ -2583,13 +2583,13 @@
1.2231 ///
1.2232 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
1.2233 ///the number of the outgoing arcs of \c n.
1.2234 - void refresh(Node n)
1.2235 + void refresh(Node n)
1.2236 {
1.2237 std::vector<Arc> v;
1.2238 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1.2239 if(v.size()) {
1.2240 - std::sort(v.begin(),v.end(),ArcLess(_g));
1.2241 - _head[n]=refreshRec(v,0,v.size()-1);
1.2242 + std::sort(v.begin(),v.end(),ArcLess(_g));
1.2243 + _head[n]=refreshRec(v,0,v.size()-1);
1.2244 }
1.2245 else _head[n]=INVALID;
1.2246 }
1.2247 @@ -2602,13 +2602,13 @@
1.2248 ///the number of the arcs of \c n and <em>D</em> is the maximum
1.2249 ///out-degree of the digraph.
1.2250
1.2251 - void refresh()
1.2252 + void refresh()
1.2253 {
1.2254 for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1.2255 }
1.2256 -
1.2257 +
1.2258 ///Find an arc between two nodes.
1.2259 -
1.2260 +
1.2261 ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
1.2262 /// <em>d</em> is the number of outgoing arcs of \c s.
1.2263 ///\param s The source node
1.2264 @@ -2625,15 +2625,15 @@
1.2265 {
1.2266 Arc e;
1.2267 for(e=_head[s];
1.2268 - e!=INVALID&&_g.target(e)!=t;
1.2269 - e = t < _g.target(e)?_left[e]:_right[e]) ;
1.2270 + e!=INVALID&&_g.target(e)!=t;
1.2271 + e = t < _g.target(e)?_left[e]:_right[e]) ;
1.2272 return e;
1.2273 }
1.2274
1.2275 };
1.2276
1.2277 ///Fast look up of all arcs between given endpoints.
1.2278 -
1.2279 +
1.2280 ///\ingroup gutils
1.2281 ///This class is the same as \ref ArcLookUp, with the addition
1.2282 ///that it makes it possible to find all arcs between given endpoints.
1.2283 @@ -2646,7 +2646,7 @@
1.2284 ///\tparam G The type of the underlying digraph.
1.2285 ///
1.2286 ///\sa DynArcLookUp
1.2287 - ///\sa ArcLookUp
1.2288 + ///\sa ArcLookUp
1.2289 template<class G>
1.2290 class AllArcLookUp : public ArcLookUp<G>
1.2291 {
1.2292 @@ -2657,26 +2657,26 @@
1.2293
1.2294 TEMPLATE_DIGRAPH_TYPEDEFS(G);
1.2295 typedef G Digraph;
1.2296 -
1.2297 +
1.2298 typename Digraph::template ArcMap<Arc> _next;
1.2299 -
1.2300 +
1.2301 Arc refreshNext(Arc head,Arc next=INVALID)
1.2302 {
1.2303 if(head==INVALID) return next;
1.2304 else {
1.2305 - next=refreshNext(_right[head],next);
1.2306 -// _next[head]=next;
1.2307 - _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
1.2308 - ? next : INVALID;
1.2309 - return refreshNext(_left[head],head);
1.2310 + next=refreshNext(_right[head],next);
1.2311 +// _next[head]=next;
1.2312 + _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
1.2313 + ? next : INVALID;
1.2314 + return refreshNext(_left[head],head);
1.2315 }
1.2316 }
1.2317 -
1.2318 +
1.2319 void refreshNext()
1.2320 {
1.2321 for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
1.2322 }
1.2323 -
1.2324 +
1.2325 public:
1.2326 ///Constructor
1.2327
1.2328 @@ -2692,13 +2692,13 @@
1.2329 ///
1.2330 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
1.2331 ///the number of the outgoing arcs of \c n.
1.2332 -
1.2333 - void refresh(Node n)
1.2334 +
1.2335 + void refresh(Node n)
1.2336 {
1.2337 ArcLookUp<G>::refresh(n);
1.2338 refreshNext(_head[n]);
1.2339 }
1.2340 -
1.2341 +
1.2342 ///Refresh the full data structure.
1.2343
1.2344 ///Build up the full search database. In fact, it simply calls
1.2345 @@ -2708,13 +2708,13 @@
1.2346 ///the number of the arcs of \c n and <em>D</em> is the maximum
1.2347 ///out-degree of the digraph.
1.2348
1.2349 - void refresh()
1.2350 + void refresh()
1.2351 {
1.2352 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
1.2353 }
1.2354 -
1.2355 +
1.2356 ///Find an arc between two nodes.
1.2357 -
1.2358 +
1.2359 ///Find an arc between two nodes.
1.2360 ///\param s The source node
1.2361 ///\param t The target node
1.2362 @@ -2750,7 +2750,7 @@
1.2363 return prev==INVALID?(*this)(s,t):_next[prev];
1.2364 }
1.2365 #endif
1.2366 -
1.2367 +
1.2368 };
1.2369
1.2370 /// @}