1.1 --- a/lemon/graph_utils.h Mon Apr 21 17:35:12 2008 +0200
1.2 +++ b/lemon/graph_utils.h Tue Apr 22 15:04:00 2008 +0200
1.3 @@ -35,7 +35,7 @@
1.4
1.5 ///\ingroup gutils
1.6 ///\file
1.7 -///\brief Digraph utilities.
1.8 +///\brief Graph utilities.
1.9
1.10 namespace lemon {
1.11
1.12 @@ -46,71 +46,36 @@
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
1.17 - ///\note If \c G it a template parameter, it should be used in this way.
1.18 - ///\code
1.19 - /// GRAPH_TYPEDEFS(typename G);
1.20 - ///\endcode
1.21 - ///
1.22 - ///\warning There are no typedefs for the digraph maps because of the lack of
1.23 - ///template typedefs in C++.
1.24 -#define GRAPH_TYPEDEFS(Digraph) \
1.25 - typedef Digraph:: Node Node; \
1.26 - typedef Digraph:: NodeIt NodeIt; \
1.27 - typedef Digraph:: Arc Arc; \
1.28 - typedef Digraph:: ArcIt ArcIt; \
1.29 - typedef Digraph:: InArcIt InArcIt; \
1.30 - typedef Digraph::OutArcIt OutArcIt
1.31 + ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
1.32 + ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
1.33 +#define DIGRAPH_TYPEDEFS(Digraph) \
1.34 + typedef Digraph::Node Node; \
1.35 + typedef Digraph::NodeIt NodeIt; \
1.36 + typedef Digraph::Arc Arc; \
1.37 + typedef Digraph::ArcIt ArcIt; \
1.38 + typedef Digraph::InArcIt InArcIt; \
1.39 + typedef Digraph::OutArcIt OutArcIt
1.40
1.41 ///Creates convenience typedefs for the graph types and iterators
1.42
1.43 - ///This \c \#define creates the same convenience typedefs as defined by
1.44 - ///\ref GRAPH_TYPEDEFS(Digraph) and three more, namely it creates
1.45 - ///\c Edge, \c EdgeIt, \c IncArcIt,
1.46 + ///This \c \#define creates the same convenience typedefs as defined
1.47 + ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
1.48 + ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
1.49 + ///\c DoubleEdgeMap.
1.50 +#define GRAPH_TYPEDEFS(Graph) \
1.51 + DIGRAPH_TYPEDEFS(Graph); \
1.52 + typedef Graph::Edge Edge; \
1.53 + typedef Graph::EdgeIt EdgeIt; \
1.54 + typedef Graph::IncEdgeIt IncEdgeIt
1.55 +
1.56 + /// \brief Function to count the items in the graph.
1.57 ///
1.58 - ///\note If \c G it a template parameter, it should be used in this way.
1.59 - ///\code
1.60 - /// UGRAPH_TYPEDEFS(typename G);
1.61 - ///\endcode
1.62 - ///
1.63 - ///\warning There are no typedefs for the digraph maps because of the lack of
1.64 - ///template typedefs in C++.
1.65 -#define UGRAPH_TYPEDEFS(Digraph) \
1.66 - GRAPH_TYPEDEFS(Digraph); \
1.67 - typedef Digraph:: Edge Edge; \
1.68 - typedef Digraph:: EdgeIt EdgeIt; \
1.69 - typedef Digraph:: IncArcIt IncArcIt
1.70 -
1.71 - ///\brief Creates convenience typedefs for the bipartite digraph
1.72 - ///types and iterators
1.73 -
1.74 - ///This \c \#define creates the same convenience typedefs as defined by
1.75 - ///\ref UGRAPH_TYPEDEFS(Digraph) and two more, namely it creates
1.76 - ///\c RedIt, \c BlueIt,
1.77 - ///
1.78 - ///\note If \c G it a template parameter, it should be used in this way.
1.79 - ///\code
1.80 - /// BPUGRAPH_TYPEDEFS(typename G);
1.81 - ///\endcode
1.82 - ///
1.83 - ///\warning There are no typedefs for the digraph maps because of the lack of
1.84 - ///template typedefs in C++.
1.85 -#define BPUGRAPH_TYPEDEFS(Digraph) \
1.86 - UGRAPH_TYPEDEFS(Digraph); \
1.87 - typedef Digraph::Red Red; \
1.88 - typedef Digraph::Blue Blue; \
1.89 - typedef Digraph::RedIt RedIt; \
1.90 - typedef Digraph::BlueIt BlueIt
1.91 -
1.92 - /// \brief Function to count the items in the digraph.
1.93 - ///
1.94 - /// This function counts the items (nodes, arcs etc) in the digraph.
1.95 + /// This function counts the items (nodes, arcs etc) in the graph.
1.96 /// The complexity of the function is O(n) because
1.97 /// it iterates on all of the items.
1.98 -
1.99 - template <typename Digraph, typename Item>
1.100 - inline int countItems(const Digraph& g) {
1.101 - typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
1.102 + template <typename Graph, typename Item>
1.103 + inline int countItems(const Graph& g) {
1.104 + typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
1.105 int num = 0;
1.106 for (ItemIt it(g); it != INVALID; ++it) {
1.107 ++num;
1.108 @@ -120,184 +85,115 @@
1.109
1.110 // Node counting:
1.111
1.112 - namespace _digraph_utils_bits {
1.113 + namespace _graph_utils_bits {
1.114
1.115 - template <typename Digraph, typename Enable = void>
1.116 + template <typename Graph, typename Enable = void>
1.117 struct CountNodesSelector {
1.118 - static int count(const Digraph &g) {
1.119 - return countItems<Digraph, typename Digraph::Node>(g);
1.120 + static int count(const Graph &g) {
1.121 + return countItems<Graph, typename Graph::Node>(g);
1.122 }
1.123 };
1.124
1.125 - template <typename Digraph>
1.126 + template <typename Graph>
1.127 struct CountNodesSelector<
1.128 - Digraph, typename
1.129 - enable_if<typename Digraph::NodeNumTag, void>::type>
1.130 + Graph, typename
1.131 + enable_if<typename Graph::NodeNumTag, void>::type>
1.132 {
1.133 - static int count(const Digraph &g) {
1.134 + static int count(const Graph &g) {
1.135 return g.nodeNum();
1.136 }
1.137 };
1.138 }
1.139
1.140 - /// \brief Function to count the nodes in the digraph.
1.141 + /// \brief Function to count the nodes in the graph.
1.142 ///
1.143 - /// This function counts the nodes in the digraph.
1.144 + /// This function counts the nodes in the graph.
1.145 /// The complexity of the function is O(n) but for some
1.146 - /// digraph structures it is specialized to run in O(1).
1.147 + /// graph structures it is specialized to run in O(1).
1.148 ///
1.149 - /// If the digraph contains a \e nodeNum() member function and a
1.150 + /// If the graph contains a \e nodeNum() member function and a
1.151 /// \e NodeNumTag tag then this function calls directly the member
1.152 /// function to query the cardinality of the node set.
1.153 - template <typename Digraph>
1.154 - inline int countNodes(const Digraph& g) {
1.155 - return _digraph_utils_bits::CountNodesSelector<Digraph>::count(g);
1.156 + template <typename Graph>
1.157 + inline int countNodes(const Graph& g) {
1.158 + return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
1.159 }
1.160
1.161 - namespace _digraph_utils_bits {
1.162 + // Arc counting:
1.163 +
1.164 + namespace _graph_utils_bits {
1.165
1.166 - template <typename Digraph, typename Enable = void>
1.167 - struct CountRedsSelector {
1.168 - static int count(const Digraph &g) {
1.169 - return countItems<Digraph, typename Digraph::Red>(g);
1.170 + template <typename Graph, typename Enable = void>
1.171 + struct CountArcsSelector {
1.172 + static int count(const Graph &g) {
1.173 + return countItems<Graph, typename Graph::Arc>(g);
1.174 }
1.175 };
1.176
1.177 - template <typename Digraph>
1.178 - struct CountRedsSelector<
1.179 - Digraph, typename
1.180 - enable_if<typename Digraph::NodeNumTag, void>::type>
1.181 + template <typename Graph>
1.182 + struct CountArcsSelector<
1.183 + Graph,
1.184 + typename enable_if<typename Graph::ArcNumTag, void>::type>
1.185 {
1.186 - static int count(const Digraph &g) {
1.187 - return g.redNum();
1.188 - }
1.189 - };
1.190 - }
1.191 -
1.192 - /// \brief Function to count the reds in the digraph.
1.193 - ///
1.194 - /// This function counts the reds in the digraph.
1.195 - /// The complexity of the function is O(an) but for some
1.196 - /// digraph structures it is specialized to run in O(1).
1.197 - ///
1.198 - /// If the digraph contains an \e redNum() member function and a
1.199 - /// \e NodeNumTag tag then this function calls directly the member
1.200 - /// function to query the cardinality of the A-node set.
1.201 - template <typename Digraph>
1.202 - inline int countReds(const Digraph& g) {
1.203 - return _digraph_utils_bits::CountRedsSelector<Digraph>::count(g);
1.204 - }
1.205 -
1.206 - namespace _digraph_utils_bits {
1.207 -
1.208 - template <typename Digraph, typename Enable = void>
1.209 - struct CountBluesSelector {
1.210 - static int count(const Digraph &g) {
1.211 - return countItems<Digraph, typename Digraph::Blue>(g);
1.212 - }
1.213 - };
1.214 -
1.215 - template <typename Digraph>
1.216 - struct CountBluesSelector<
1.217 - Digraph, typename
1.218 - enable_if<typename Digraph::NodeNumTag, void>::type>
1.219 - {
1.220 - static int count(const Digraph &g) {
1.221 - return g.blueNum();
1.222 - }
1.223 - };
1.224 - }
1.225 -
1.226 - /// \brief Function to count the blues in the digraph.
1.227 - ///
1.228 - /// This function counts the blues in the digraph.
1.229 - /// The complexity of the function is O(bn) but for some
1.230 - /// digraph structures it is specialized to run in O(1).
1.231 - ///
1.232 - /// If the digraph contains a \e blueNum() member function and a
1.233 - /// \e NodeNumTag tag then this function calls directly the member
1.234 - /// function to query the cardinality of the B-node set.
1.235 - template <typename Digraph>
1.236 - inline int countBlues(const Digraph& g) {
1.237 - return _digraph_utils_bits::CountBluesSelector<Digraph>::count(g);
1.238 - }
1.239 -
1.240 -
1.241 - // Arc counting:
1.242 -
1.243 - namespace _digraph_utils_bits {
1.244 -
1.245 - template <typename Digraph, typename Enable = void>
1.246 - struct CountArcsSelector {
1.247 - static int count(const Digraph &g) {
1.248 - return countItems<Digraph, typename Digraph::Arc>(g);
1.249 - }
1.250 - };
1.251 -
1.252 - template <typename Digraph>
1.253 - struct CountArcsSelector<
1.254 - Digraph,
1.255 - typename enable_if<typename Digraph::ArcNumTag, void>::type>
1.256 - {
1.257 - static int count(const Digraph &g) {
1.258 + static int count(const Graph &g) {
1.259 return g.arcNum();
1.260 }
1.261 };
1.262 }
1.263
1.264 - /// \brief Function to count the arcs in the digraph.
1.265 + /// \brief Function to count the arcs in the graph.
1.266 ///
1.267 - /// This function counts the arcs in the digraph.
1.268 + /// This function counts the arcs in the graph.
1.269 /// The complexity of the function is O(e) but for some
1.270 - /// digraph structures it is specialized to run in O(1).
1.271 + /// graph structures it is specialized to run in O(1).
1.272 ///
1.273 - /// If the digraph contains a \e arcNum() member function and a
1.274 - /// \e ArcNumTag tag then this function calls directly the member
1.275 + /// If the graph contains a \e arcNum() member function and a
1.276 + /// \e EdgeNumTag tag then this function calls directly the member
1.277 /// function to query the cardinality of the arc set.
1.278 - template <typename Digraph>
1.279 - inline int countArcs(const Digraph& g) {
1.280 - return _digraph_utils_bits::CountArcsSelector<Digraph>::count(g);
1.281 + template <typename Graph>
1.282 + inline int countArcs(const Graph& g) {
1.283 + return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
1.284 }
1.285
1.286 - // Undirected arc counting:
1.287 - namespace _digraph_utils_bits {
1.288 + // Edge counting:
1.289 + namespace _graph_utils_bits {
1.290
1.291 - template <typename Digraph, typename Enable = void>
1.292 + template <typename Graph, typename Enable = void>
1.293 struct CountEdgesSelector {
1.294 - static int count(const Digraph &g) {
1.295 - return countItems<Digraph, typename Digraph::Edge>(g);
1.296 + static int count(const Graph &g) {
1.297 + return countItems<Graph, typename Graph::Edge>(g);
1.298 }
1.299 };
1.300
1.301 - template <typename Digraph>
1.302 + template <typename Graph>
1.303 struct CountEdgesSelector<
1.304 - Digraph,
1.305 - typename enable_if<typename Digraph::ArcNumTag, void>::type>
1.306 + Graph,
1.307 + typename enable_if<typename Graph::EdgeNumTag, void>::type>
1.308 {
1.309 - static int count(const Digraph &g) {
1.310 + static int count(const Graph &g) {
1.311 return g.edgeNum();
1.312 }
1.313 };
1.314 }
1.315
1.316 - /// \brief Function to count the edges in the digraph.
1.317 + /// \brief Function to count the edges in the graph.
1.318 ///
1.319 - /// This function counts the edges in the digraph.
1.320 - /// The complexity of the function is O(e) but for some
1.321 - /// digraph structures it is specialized to run in O(1).
1.322 + /// This function counts the edges in the graph.
1.323 + /// The complexity of the function is O(m) but for some
1.324 + /// graph structures it is specialized to run in O(1).
1.325 ///
1.326 - /// If the digraph contains a \e edgeNum() member function and a
1.327 - /// \e ArcNumTag tag then this function calls directly the member
1.328 + /// If the graph contains a \e edgeNum() member function and a
1.329 + /// \e EdgeNumTag tag then this function calls directly the member
1.330 /// function to query the cardinality of the edge set.
1.331 - template <typename Digraph>
1.332 - inline int countEdges(const Digraph& g) {
1.333 - return _digraph_utils_bits::CountEdgesSelector<Digraph>::count(g);
1.334 + template <typename Graph>
1.335 + inline int countEdges(const Graph& g) {
1.336 + return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
1.337
1.338 }
1.339
1.340
1.341 - template <typename Digraph, typename DegIt>
1.342 - inline int countNodeDegree(const Digraph& _g, const typename Digraph::Node& _n) {
1.343 + template <typename Graph, typename DegIt>
1.344 + inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
1.345 int num = 0;
1.346 for (DegIt it(_g, _n); it != INVALID; ++it) {
1.347 ++num;
1.348 @@ -308,37 +204,37 @@
1.349 /// \brief Function to count the number of the out-arcs from node \c n.
1.350 ///
1.351 /// This function counts the number of the out-arcs from node \c n
1.352 - /// in the digraph.
1.353 - template <typename Digraph>
1.354 - inline int countOutArcs(const Digraph& _g, const typename Digraph::Node& _n) {
1.355 - return countNodeDegree<Digraph, typename Digraph::OutArcIt>(_g, _n);
1.356 + /// in the graph.
1.357 + template <typename Graph>
1.358 + inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {
1.359 + return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
1.360 }
1.361
1.362 /// \brief Function to count the number of the in-arcs to node \c n.
1.363 ///
1.364 /// This function counts the number of the in-arcs to node \c n
1.365 - /// in the digraph.
1.366 - template <typename Digraph>
1.367 - inline int countInArcs(const Digraph& _g, const typename Digraph::Node& _n) {
1.368 - return countNodeDegree<Digraph, typename Digraph::InArcIt>(_g, _n);
1.369 + /// in the graph.
1.370 + template <typename Graph>
1.371 + inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {
1.372 + return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
1.373 }
1.374
1.375 - /// \brief Function to count the number of the inc-arcs to node \c n.
1.376 + /// \brief Function to count the number of the inc-edges to node \c n.
1.377 ///
1.378 - /// This function counts the number of the inc-arcs to node \c n
1.379 - /// in the digraph.
1.380 - template <typename Digraph>
1.381 - inline int countIncArcs(const Digraph& _g, const typename Digraph::Node& _n) {
1.382 - return countNodeDegree<Digraph, typename Digraph::IncArcIt>(_g, _n);
1.383 + /// This function counts the number of the inc-edges to node \c n
1.384 + /// in the graph.
1.385 + template <typename Graph>
1.386 + inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
1.387 + return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
1.388 }
1.389
1.390 - namespace _digraph_utils_bits {
1.391 + namespace _graph_utils_bits {
1.392
1.393 - template <typename Digraph, typename Enable = void>
1.394 + template <typename Graph, typename Enable = void>
1.395 struct FindArcSelector {
1.396 - typedef typename Digraph::Node Node;
1.397 - typedef typename Digraph::Arc Arc;
1.398 - static Arc find(const Digraph &g, Node u, Node v, Arc e) {
1.399 + typedef typename Graph::Node Node;
1.400 + typedef typename Graph::Arc Arc;
1.401 + static Arc find(const Graph &g, Node u, Node v, Arc e) {
1.402 if (e == INVALID) {
1.403 g.firstOut(e, u);
1.404 } else {
1.405 @@ -351,22 +247,22 @@
1.406 }
1.407 };
1.408
1.409 - template <typename Digraph>
1.410 + template <typename Graph>
1.411 struct FindArcSelector<
1.412 - Digraph,
1.413 - typename enable_if<typename Digraph::FindArcTag, void>::type>
1.414 + Graph,
1.415 + typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.416 {
1.417 - typedef typename Digraph::Node Node;
1.418 - typedef typename Digraph::Arc Arc;
1.419 - static Arc find(const Digraph &g, Node u, Node v, Arc prev) {
1.420 + typedef typename Graph::Node Node;
1.421 + typedef typename Graph::Arc Arc;
1.422 + static Arc find(const Graph &g, Node u, Node v, Arc prev) {
1.423 return g.findArc(u, v, prev);
1.424 }
1.425 };
1.426 }
1.427
1.428 - /// \brief Finds an arc between two nodes of a digraph.
1.429 + /// \brief Finds an arc between two nodes of a graph.
1.430 ///
1.431 - /// Finds an arc from node \c u to node \c v in digraph \c g.
1.432 + /// Finds an arc from node \c u to node \c v in graph \c g.
1.433 ///
1.434 /// If \c prev is \ref INVALID (this is the default value), then
1.435 /// it finds the first arc from \c u to \c v. Otherwise it looks for
1.436 @@ -384,11 +280,11 @@
1.437 ///\sa AllArcLookUp
1.438 ///\sa DynArcLookUp
1.439 ///\sa ConArcIt
1.440 - template <typename Digraph>
1.441 - inline typename Digraph::Arc
1.442 - findArc(const Digraph &g, typename Digraph::Node u, typename Digraph::Node v,
1.443 - typename Digraph::Arc prev = INVALID) {
1.444 - return _digraph_utils_bits::FindArcSelector<Digraph>::find(g, u, v, prev);
1.445 + template <typename Graph>
1.446 + inline typename Graph::Arc
1.447 + findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1.448 + typename Graph::Arc prev = INVALID) {
1.449 + return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
1.450 }
1.451
1.452 /// \brief Iterator for iterating on arcs connected the same nodes.
1.453 @@ -397,7 +293,7 @@
1.454 /// higher level interface for the findArc() function. You can
1.455 /// use it the following way:
1.456 ///\code
1.457 - /// for (ConArcIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
1.458 + /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1.459 /// ...
1.460 /// }
1.461 ///\endcode
1.462 @@ -408,49 +304,49 @@
1.463 ///\sa DynArcLookUp
1.464 ///
1.465 /// \author Balazs Dezso
1.466 - template <typename _Digraph>
1.467 - class ConArcIt : public _Digraph::Arc {
1.468 + template <typename _Graph>
1.469 + class ConArcIt : public _Graph::Arc {
1.470 public:
1.471
1.472 - typedef _Digraph Digraph;
1.473 - typedef typename Digraph::Arc Parent;
1.474 + typedef _Graph Graph;
1.475 + typedef typename Graph::Arc Parent;
1.476
1.477 - typedef typename Digraph::Arc Arc;
1.478 - typedef typename Digraph::Node Node;
1.479 + typedef typename Graph::Arc Arc;
1.480 + typedef typename Graph::Node Node;
1.481
1.482 /// \brief Constructor.
1.483 ///
1.484 /// Construct a new ConArcIt iterating on the arcs which
1.485 /// connects the \c u and \c v node.
1.486 - ConArcIt(const Digraph& g, Node u, Node v) : digraph(g) {
1.487 - Parent::operator=(findArc(digraph, u, v));
1.488 + ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
1.489 + Parent::operator=(findArc(_graph, u, v));
1.490 }
1.491
1.492 /// \brief Constructor.
1.493 ///
1.494 /// Construct a new ConArcIt which continues the iterating from
1.495 /// the \c e arc.
1.496 - ConArcIt(const Digraph& g, Arc e) : Parent(e), digraph(g) {}
1.497 + ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
1.498
1.499 /// \brief Increment operator.
1.500 ///
1.501 /// It increments the iterator and gives back the next arc.
1.502 ConArcIt& operator++() {
1.503 - Parent::operator=(findArc(digraph, digraph.source(*this),
1.504 - digraph.target(*this), *this));
1.505 + Parent::operator=(findArc(_graph, _graph.source(*this),
1.506 + _graph.target(*this), *this));
1.507 return *this;
1.508 }
1.509 private:
1.510 - const Digraph& digraph;
1.511 + const Graph& _graph;
1.512 };
1.513
1.514 - namespace _digraph_utils_bits {
1.515 + namespace _graph_utils_bits {
1.516
1.517 - template <typename Digraph, typename Enable = void>
1.518 + template <typename Graph, typename Enable = void>
1.519 struct FindEdgeSelector {
1.520 - typedef typename Digraph::Node Node;
1.521 - typedef typename Digraph::Edge Edge;
1.522 - static Edge find(const Digraph &g, Node u, Node v, Edge e) {
1.523 + typedef typename Graph::Node Node;
1.524 + typedef typename Graph::Edge Edge;
1.525 + static Edge find(const Graph &g, Node u, Node v, Edge e) {
1.526 bool b;
1.527 if (u != v) {
1.528 if (e == INVALID) {
1.529 @@ -477,24 +373,24 @@
1.530 }
1.531 };
1.532
1.533 - template <typename Digraph>
1.534 + template <typename Graph>
1.535 struct FindEdgeSelector<
1.536 - Digraph,
1.537 - typename enable_if<typename Digraph::FindArcTag, void>::type>
1.538 + Graph,
1.539 + typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.540 {
1.541 - typedef typename Digraph::Node Node;
1.542 - typedef typename Digraph::Edge Edge;
1.543 - static Edge find(const Digraph &g, Node u, Node v, Edge prev) {
1.544 + typedef typename Graph::Node Node;
1.545 + typedef typename Graph::Edge Edge;
1.546 + static Edge find(const Graph &g, Node u, Node v, Edge prev) {
1.547 return g.findEdge(u, v, prev);
1.548 }
1.549 };
1.550 }
1.551
1.552 - /// \brief Finds an edge between two nodes of a digraph.
1.553 + /// \brief Finds an edge between two nodes of a graph.
1.554 ///
1.555 - /// Finds an edge from node \c u to node \c v in digraph \c g.
1.556 - /// If the node \c u and node \c v is equal then each loop arc
1.557 - /// will be enumerated.
1.558 + /// Finds an edge from node \c u to node \c v in graph \c g.
1.559 + /// If the node \c u and node \c v is equal then each loop edge
1.560 + /// will be enumerated once.
1.561 ///
1.562 /// If \c prev is \ref INVALID (this is the default value), then
1.563 /// it finds the first arc from \c u to \c v. Otherwise it looks for
1.564 @@ -511,11 +407,11 @@
1.565 ///
1.566 ///\sa ConArcIt
1.567
1.568 - template <typename Digraph>
1.569 - inline typename Digraph::Edge
1.570 - findEdge(const Digraph &g, typename Digraph::Node u, typename Digraph::Node v,
1.571 - typename Digraph::Edge p = INVALID) {
1.572 - return _digraph_utils_bits::FindEdgeSelector<Digraph>::find(g, u, v, p);
1.573 + template <typename Graph>
1.574 + inline typename Graph::Edge
1.575 + findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1.576 + typename Graph::Edge p = INVALID) {
1.577 + return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
1.578 }
1.579
1.580 /// \brief Iterator for iterating on edges connected the same nodes.
1.581 @@ -524,7 +420,7 @@
1.582 /// higher level interface for the findEdge() function. You can
1.583 /// use it the following way:
1.584 ///\code
1.585 - /// for (ConEdgeIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
1.586 + /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1.587 /// ...
1.588 /// }
1.589 ///\endcode
1.590 @@ -532,68 +428,43 @@
1.591 ///\sa findEdge()
1.592 ///
1.593 /// \author Balazs Dezso
1.594 - template <typename _Digraph>
1.595 - class ConEdgeIt : public _Digraph::Edge {
1.596 + template <typename _Graph>
1.597 + class ConEdgeIt : public _Graph::Edge {
1.598 public:
1.599
1.600 - typedef _Digraph Digraph;
1.601 - typedef typename Digraph::Edge Parent;
1.602 + typedef _Graph Graph;
1.603 + typedef typename Graph::Edge Parent;
1.604
1.605 - typedef typename Digraph::Edge Edge;
1.606 - typedef typename Digraph::Node Node;
1.607 + typedef typename Graph::Edge Edge;
1.608 + typedef typename Graph::Node Node;
1.609
1.610 /// \brief Constructor.
1.611 ///
1.612 - /// Construct a new ConEdgeIt iterating on the arcs which
1.613 + /// Construct a new ConEdgeIt iterating on the edges which
1.614 /// connects the \c u and \c v node.
1.615 - ConEdgeIt(const Digraph& g, Node u, Node v) : digraph(g) {
1.616 - Parent::operator=(findEdge(digraph, u, v));
1.617 + ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
1.618 + Parent::operator=(findEdge(_graph, u, v));
1.619 }
1.620
1.621 /// \brief Constructor.
1.622 ///
1.623 /// Construct a new ConEdgeIt which continues the iterating from
1.624 - /// the \c e arc.
1.625 - ConEdgeIt(const Digraph& g, Edge e) : Parent(e), digraph(g) {}
1.626 + /// the \c e edge.
1.627 + ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
1.628
1.629 /// \brief Increment operator.
1.630 ///
1.631 - /// It increments the iterator and gives back the next arc.
1.632 + /// It increments the iterator and gives back the next edge.
1.633 ConEdgeIt& operator++() {
1.634 - Parent::operator=(findEdge(digraph, digraph.source(*this),
1.635 - digraph.target(*this), *this));
1.636 + Parent::operator=(findEdge(_graph, _graph.source(*this),
1.637 + _graph.target(*this), *this));
1.638 return *this;
1.639 }
1.640 private:
1.641 - const Digraph& digraph;
1.642 + const Graph& _graph;
1.643 };
1.644
1.645 - /// \brief Copy a map.
1.646 - ///
1.647 - /// This function copies the \c from map to the \c to map. It uses the
1.648 - /// given iterator to iterate on the data structure and it uses the \c ref
1.649 - /// mapping to convert the from's keys to the to's keys.
1.650 - template <typename To, typename From,
1.651 - typename ItemIt, typename Ref>
1.652 - void copyMap(To& to, const From& from,
1.653 - ItemIt it, const Ref& ref) {
1.654 - for (; it != INVALID; ++it) {
1.655 - to[ref[it]] = from[it];
1.656 - }
1.657 - }
1.658 -
1.659 - /// \brief Copy the from map to the to map.
1.660 - ///
1.661 - /// Copy the \c from map to the \c to map. It uses the given iterator
1.662 - /// to iterate on the data structure.
1.663 - template <typename To, typename From, typename ItemIt>
1.664 - void copyMap(To& to, const From& from, ItemIt it) {
1.665 - for (; it != INVALID; ++it) {
1.666 - to[it] = from[it];
1.667 - }
1.668 - }
1.669 -
1.670 - namespace _digraph_utils_bits {
1.671 + namespace _graph_utils_bits {
1.672
1.673 template <typename Digraph, typename Item, typename RefMap>
1.674 class MapCopyBase {
1.675 @@ -727,47 +598,43 @@
1.676 }
1.677 };
1.678
1.679 - template <typename BpGraph, typename Enable = void>
1.680 - struct BpGraphCopySelector {
1.681 - template <typename From, typename RedRefMap,
1.682 - typename BlueRefMap, typename EdgeRefMap>
1.683 - static void copy(BpGraph &to, const From& from,
1.684 - RedRefMap& redRefMap, BlueRefMap& blueRefMap,
1.685 - EdgeRefMap& edgeRefMap) {
1.686 - for (typename From::RedIt it(from); it != INVALID; ++it) {
1.687 - redRefMap[it] = to.addRed();
1.688 - }
1.689 - for (typename From::BlueIt it(from); it != INVALID; ++it) {
1.690 - blueRefMap[it] = to.addBlue();
1.691 - }
1.692 - for (typename From::EdgeIt it(from); it != INVALID; ++it) {
1.693 - edgeRefMap[it] = to.addArc(redRefMap[from.red(it)],
1.694 - blueRefMap[from.blue(it)]);
1.695 - }
1.696 - }
1.697 - };
1.698 -
1.699 - template <typename BpGraph>
1.700 - struct BpGraphCopySelector<
1.701 - BpGraph,
1.702 - typename enable_if<typename BpGraph::BuildTag, void>::type>
1.703 - {
1.704 - template <typename From, typename RedRefMap,
1.705 - typename BlueRefMap, typename EdgeRefMap>
1.706 - static void copy(BpGraph &to, const From& from,
1.707 - RedRefMap& redRefMap, BlueRefMap& blueRefMap,
1.708 - EdgeRefMap& edgeRefMap) {
1.709 - to.build(from, redRefMap, blueRefMap, edgeRefMap);
1.710 - }
1.711 - };
1.712 -
1.713 -
1.714 }
1.715
1.716 /// \brief Class to copy a digraph.
1.717 ///
1.718 /// Class to copy a digraph to another digraph (duplicate a digraph). The
1.719 /// simplest way of using it is through the \c copyDigraph() function.
1.720 + ///
1.721 + /// This class not just make a copy of a graph, but it can create
1.722 + /// references and cross references between the nodes and arcs of
1.723 + /// the two graphs, it can copy maps for use with the newly created
1.724 + /// graph and copy nodes and arcs.
1.725 + ///
1.726 + /// To make a copy from a graph, first an instance of DigraphCopy
1.727 + /// should be created, then the data belongs to the graph should
1.728 + /// assigned to copy. In the end, the \c run() member should be
1.729 + /// called.
1.730 + ///
1.731 + /// The next code copies a graph with several data:
1.732 + ///\code
1.733 + /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
1.734 + /// // create a reference for the nodes
1.735 + /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
1.736 + /// dc.nodeRef(nr);
1.737 + /// // create a cross reference (inverse) for the arcs
1.738 + /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
1.739 + /// dc.arcCrossRef(acr);
1.740 + /// // copy an arc map
1.741 + /// OrigGraph::ArcMap<double> oamap(orig_graph);
1.742 + /// NewGraph::ArcMap<double> namap(new_graph);
1.743 + /// dc.arcMap(namap, oamap);
1.744 + /// // copy a node
1.745 + /// OrigGraph::Node on;
1.746 + /// NewGraph::Node nn;
1.747 + /// dc.node(nn, on);
1.748 + /// // Executions of copy
1.749 + /// dc.run();
1.750 + ///\endcode
1.751 template <typename To, typename From>
1.752 class DigraphCopy {
1.753 private:
1.754 @@ -791,53 +658,57 @@
1.755 ///
1.756 /// It copies the content of the \c _from digraph into the
1.757 /// \c _to digraph.
1.758 - DigraphCopy(To& _to, const From& _from)
1.759 - : from(_from), to(_to) {}
1.760 + DigraphCopy(To& to, const From& from)
1.761 + : _from(from), _to(to) {}
1.762
1.763 /// \brief Destructor of the DigraphCopy
1.764 ///
1.765 /// Destructor of the DigraphCopy
1.766 ~DigraphCopy() {
1.767 - for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1.768 - delete nodeMapCopies[i];
1.769 + for (int i = 0; i < int(_node_maps.size()); ++i) {
1.770 + delete _node_maps[i];
1.771 }
1.772 - for (int i = 0; i < int(arcMapCopies.size()); ++i) {
1.773 - delete arcMapCopies[i];
1.774 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.775 + delete _arc_maps[i];
1.776 }
1.777
1.778 }
1.779
1.780 /// \brief Copies the node references into the given map.
1.781 ///
1.782 - /// Copies the node references into the given map.
1.783 + /// Copies the node references into the given map. The parameter
1.784 + /// should be a map, which key type is the Node type of the source
1.785 + /// graph, while the value type is the Node type of the
1.786 + /// destination graph.
1.787 template <typename NodeRef>
1.788 DigraphCopy& nodeRef(NodeRef& map) {
1.789 - nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
1.790 - NodeRefMap, NodeRef>(map));
1.791 + _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
1.792 + NodeRefMap, NodeRef>(map));
1.793 return *this;
1.794 }
1.795
1.796 /// \brief Copies the node cross references into the given map.
1.797 ///
1.798 /// Copies the node cross references (reverse references) into
1.799 - /// the given map.
1.800 + /// the given map. The parameter should be a map, which key type
1.801 + /// is the Node type of the destination graph, while the value type is
1.802 + /// the Node type of the source graph.
1.803 template <typename NodeCrossRef>
1.804 DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.805 - nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
1.806 - NodeRefMap, NodeCrossRef>(map));
1.807 + _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
1.808 + NodeRefMap, NodeCrossRef>(map));
1.809 return *this;
1.810 }
1.811
1.812 /// \brief Make copy of the given map.
1.813 ///
1.814 - /// Makes copy of the given map for the newly created digraph.
1.815 - /// The new map's key type is the to digraph's node type,
1.816 - /// and the copied map's key type is the from digraph's node
1.817 - /// type.
1.818 + /// Makes copy of the given map for the newly created digraph.
1.819 + /// The new map's key type is the destination graph's node type,
1.820 + /// and the copied map's key type is the source graph's node type.
1.821 template <typename ToMap, typename FromMap>
1.822 DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1.823 - nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
1.824 - NodeRefMap, ToMap, FromMap>(tmap, map));
1.825 + _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
1.826 + NodeRefMap, ToMap, FromMap>(tmap, map));
1.827 return *this;
1.828 }
1.829
1.830 @@ -845,8 +716,8 @@
1.831 ///
1.832 /// Make a copy of the given node.
1.833 DigraphCopy& node(TNode& tnode, const Node& snode) {
1.834 - nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
1.835 - NodeRefMap, TNode>(tnode, snode));
1.836 + _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
1.837 + NodeRefMap, TNode>(tnode, snode));
1.838 return *this;
1.839 }
1.840
1.841 @@ -855,8 +726,8 @@
1.842 /// Copies the arc references into the given map.
1.843 template <typename ArcRef>
1.844 DigraphCopy& arcRef(ArcRef& map) {
1.845 - arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
1.846 - ArcRefMap, ArcRef>(map));
1.847 + _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
1.848 + ArcRefMap, ArcRef>(map));
1.849 return *this;
1.850 }
1.851
1.852 @@ -866,8 +737,8 @@
1.853 /// the given map.
1.854 template <typename ArcCrossRef>
1.855 DigraphCopy& arcCrossRef(ArcCrossRef& map) {
1.856 - arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
1.857 - ArcRefMap, ArcCrossRef>(map));
1.858 + _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
1.859 + ArcRefMap, ArcCrossRef>(map));
1.860 return *this;
1.861 }
1.862
1.863 @@ -879,8 +750,8 @@
1.864 /// type.
1.865 template <typename ToMap, typename FromMap>
1.866 DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1.867 - arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
1.868 - ArcRefMap, ToMap, FromMap>(tmap, map));
1.869 + _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
1.870 + ArcRefMap, ToMap, FromMap>(tmap, map));
1.871 return *this;
1.872 }
1.873
1.874 @@ -888,8 +759,8 @@
1.875 ///
1.876 /// Make a copy of the given arc.
1.877 DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
1.878 - arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
1.879 - ArcRefMap, TArc>(tarc, sarc));
1.880 + _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
1.881 + ArcRefMap, TArc>(tarc, sarc));
1.882 return *this;
1.883 }
1.884
1.885 @@ -897,37 +768,37 @@
1.886 ///
1.887 /// Executes the copies.
1.888 void run() {
1.889 - NodeRefMap nodeRefMap(from);
1.890 - ArcRefMap arcRefMap(from);
1.891 - _digraph_utils_bits::DigraphCopySelector<To>::
1.892 - copy(to, from, nodeRefMap, arcRefMap);
1.893 - for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1.894 - nodeMapCopies[i]->copy(from, nodeRefMap);
1.895 + NodeRefMap nodeRefMap(_from);
1.896 + ArcRefMap arcRefMap(_from);
1.897 + _graph_utils_bits::DigraphCopySelector<To>::
1.898 + copy(_to, _from, nodeRefMap, arcRefMap);
1.899 + for (int i = 0; i < int(_node_maps.size()); ++i) {
1.900 + _node_maps[i]->copy(_from, nodeRefMap);
1.901 }
1.902 - for (int i = 0; i < int(arcMapCopies.size()); ++i) {
1.903 - arcMapCopies[i]->copy(from, arcRefMap);
1.904 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.905 + _arc_maps[i]->copy(_from, arcRefMap);
1.906 }
1.907 }
1.908
1.909 protected:
1.910
1.911
1.912 - const From& from;
1.913 - To& to;
1.914 + const From& _from;
1.915 + To& _to;
1.916
1.917 - std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.918 - nodeMapCopies;
1.919 + std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.920 + _node_maps;
1.921
1.922 - std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.923 - arcMapCopies;
1.924 + std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.925 + _arc_maps;
1.926
1.927 };
1.928
1.929 /// \brief Copy a digraph to another digraph.
1.930 ///
1.931 - /// Copy a digraph to another digraph.
1.932 - /// The usage of the function:
1.933 - ///
1.934 + /// Copy a digraph to another digraph. The complete usage of the
1.935 + /// function is detailed in the DigraphCopy class, but a short
1.936 + /// example shows a basic work:
1.937 ///\code
1.938 /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1.939 ///\endcode
1.940 @@ -943,10 +814,41 @@
1.941 return DigraphCopy<To, From>(to, from);
1.942 }
1.943
1.944 - /// \brief Class to copy an graph.
1.945 + /// \brief Class to copy a graph.
1.946 ///
1.947 - /// Class to copy an graph to another digraph (duplicate a digraph).
1.948 - /// The simplest way of using it is through the \c copyGraph() function.
1.949 + /// Class to copy a graph to another graph (duplicate a graph). The
1.950 + /// simplest way of using it is through the \c copyGraph() function.
1.951 + ///
1.952 + /// This class not just make a copy of a graph, but it can create
1.953 + /// references and cross references between the nodes, edges and arcs of
1.954 + /// the two graphs, it can copy maps for use with the newly created
1.955 + /// graph and copy nodes, edges and arcs.
1.956 + ///
1.957 + /// To make a copy from a graph, first an instance of GraphCopy
1.958 + /// should be created, then the data belongs to the graph should
1.959 + /// assigned to copy. In the end, the \c run() member should be
1.960 + /// called.
1.961 + ///
1.962 + /// The next code copies a graph with several data:
1.963 + ///\code
1.964 + /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
1.965 + /// // create a reference for the nodes
1.966 + /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
1.967 + /// dc.nodeRef(nr);
1.968 + /// // create a cross reference (inverse) for the edges
1.969 + /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
1.970 + /// dc.edgeCrossRef(ecr);
1.971 + /// // copy an arc map
1.972 + /// OrigGraph::ArcMap<double> oamap(orig_graph);
1.973 + /// NewGraph::ArcMap<double> namap(new_graph);
1.974 + /// dc.arcMap(namap, oamap);
1.975 + /// // copy a node
1.976 + /// OrigGraph::Node on;
1.977 + /// NewGraph::Node nn;
1.978 + /// dc.node(nn, on);
1.979 + /// // Executions of copy
1.980 + /// dc.run();
1.981 + ///\endcode
1.982 template <typename To, typename From>
1.983 class GraphCopy {
1.984 private:
1.985 @@ -966,51 +868,50 @@
1.986 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
1.987
1.988 struct ArcRefMap {
1.989 - ArcRefMap(const To& _to, const From& _from,
1.990 - const EdgeRefMap& _edge_ref, const NodeRefMap& _node_ref)
1.991 - : to(_to), from(_from),
1.992 - edge_ref(_edge_ref), node_ref(_node_ref) {}
1.993 + ArcRefMap(const To& to, const From& from,
1.994 + const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
1.995 + : _to(to), _from(from),
1.996 + _edge_ref(edge_ref), _node_ref(node_ref) {}
1.997
1.998 typedef typename From::Arc Key;
1.999 typedef typename To::Arc Value;
1.1000
1.1001 Value operator[](const Key& key) const {
1.1002 bool forward =
1.1003 - (from.direction(key) ==
1.1004 - (node_ref[from.source(static_cast<const Edge&>(key))] ==
1.1005 - to.source(edge_ref[static_cast<const Edge&>(key)])));
1.1006 - return to.direct(edge_ref[key], forward);
1.1007 + (_from.direction(key) ==
1.1008 + (_node_ref[_from.source(key)] == _to.source(_edge_ref[key])));
1.1009 + return _to.direct(_edge_ref[key], forward);
1.1010 }
1.1011
1.1012 - const To& to;
1.1013 - const From& from;
1.1014 - const EdgeRefMap& edge_ref;
1.1015 - const NodeRefMap& node_ref;
1.1016 + const To& _to;
1.1017 + const From& _from;
1.1018 + const EdgeRefMap& _edge_ref;
1.1019 + const NodeRefMap& _node_ref;
1.1020 };
1.1021
1.1022
1.1023 public:
1.1024
1.1025
1.1026 - /// \brief Constructor for the DigraphCopy.
1.1027 + /// \brief Constructor for the GraphCopy.
1.1028 ///
1.1029 - /// It copies the content of the \c _from digraph into the
1.1030 - /// \c _to digraph.
1.1031 - GraphCopy(To& _to, const From& _from)
1.1032 - : from(_from), to(_to) {}
1.1033 + /// It copies the content of the \c _from graph into the
1.1034 + /// \c _to graph.
1.1035 + GraphCopy(To& to, const From& from)
1.1036 + : _from(from), _to(to) {}
1.1037
1.1038 - /// \brief Destructor of the DigraphCopy
1.1039 + /// \brief Destructor of the GraphCopy
1.1040 ///
1.1041 - /// Destructor of the DigraphCopy
1.1042 + /// Destructor of the GraphCopy
1.1043 ~GraphCopy() {
1.1044 - for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1.1045 - delete nodeMapCopies[i];
1.1046 + for (int i = 0; i < int(_node_maps.size()); ++i) {
1.1047 + delete _node_maps[i];
1.1048 }
1.1049 - for (int i = 0; i < int(arcMapCopies.size()); ++i) {
1.1050 - delete arcMapCopies[i];
1.1051 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.1052 + delete _arc_maps[i];
1.1053 }
1.1054 - for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1.1055 - delete edgeMapCopies[i];
1.1056 + for (int i = 0; i < int(_edge_maps.size()); ++i) {
1.1057 + delete _edge_maps[i];
1.1058 }
1.1059
1.1060 }
1.1061 @@ -1020,8 +921,8 @@
1.1062 /// Copies the node references into the given map.
1.1063 template <typename NodeRef>
1.1064 GraphCopy& nodeRef(NodeRef& map) {
1.1065 - nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
1.1066 - NodeRefMap, NodeRef>(map));
1.1067 + _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
1.1068 + NodeRefMap, NodeRef>(map));
1.1069 return *this;
1.1070 }
1.1071
1.1072 @@ -1031,21 +932,21 @@
1.1073 /// the given map.
1.1074 template <typename NodeCrossRef>
1.1075 GraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.1076 - nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
1.1077 - NodeRefMap, NodeCrossRef>(map));
1.1078 + _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
1.1079 + NodeRefMap, NodeCrossRef>(map));
1.1080 return *this;
1.1081 }
1.1082
1.1083 /// \brief Make copy of the given map.
1.1084 ///
1.1085 - /// Makes copy of the given map for the newly created digraph.
1.1086 - /// The new map's key type is the to digraph's node type,
1.1087 - /// and the copied map's key type is the from digraph's node
1.1088 + /// Makes copy of the given map for the newly created graph.
1.1089 + /// The new map's key type is the to graph's node type,
1.1090 + /// and the copied map's key type is the from graph's node
1.1091 /// type.
1.1092 template <typename ToMap, typename FromMap>
1.1093 GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1.1094 - nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
1.1095 - NodeRefMap, ToMap, FromMap>(tmap, map));
1.1096 + _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
1.1097 + NodeRefMap, ToMap, FromMap>(tmap, map));
1.1098 return *this;
1.1099 }
1.1100
1.1101 @@ -1053,8 +954,8 @@
1.1102 ///
1.1103 /// Make a copy of the given node.
1.1104 GraphCopy& node(TNode& tnode, const Node& snode) {
1.1105 - nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
1.1106 - NodeRefMap, TNode>(tnode, snode));
1.1107 + _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
1.1108 + NodeRefMap, TNode>(tnode, snode));
1.1109 return *this;
1.1110 }
1.1111
1.1112 @@ -1063,8 +964,8 @@
1.1113 /// Copies the arc references into the given map.
1.1114 template <typename ArcRef>
1.1115 GraphCopy& arcRef(ArcRef& map) {
1.1116 - arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
1.1117 - ArcRefMap, ArcRef>(map));
1.1118 + _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
1.1119 + ArcRefMap, ArcRef>(map));
1.1120 return *this;
1.1121 }
1.1122
1.1123 @@ -1074,21 +975,21 @@
1.1124 /// the given map.
1.1125 template <typename ArcCrossRef>
1.1126 GraphCopy& arcCrossRef(ArcCrossRef& map) {
1.1127 - arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
1.1128 - ArcRefMap, ArcCrossRef>(map));
1.1129 + _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
1.1130 + ArcRefMap, ArcCrossRef>(map));
1.1131 return *this;
1.1132 }
1.1133
1.1134 /// \brief Make copy of the given map.
1.1135 ///
1.1136 - /// Makes copy of the given map for the newly created digraph.
1.1137 - /// The new map's key type is the to digraph's arc type,
1.1138 - /// and the copied map's key type is the from digraph's arc
1.1139 + /// Makes copy of the given map for the newly created graph.
1.1140 + /// The new map's key type is the to graph's arc type,
1.1141 + /// and the copied map's key type is the from graph's arc
1.1142 /// type.
1.1143 template <typename ToMap, typename FromMap>
1.1144 GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1.1145 - arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
1.1146 - ArcRefMap, ToMap, FromMap>(tmap, map));
1.1147 + _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
1.1148 + ArcRefMap, ToMap, FromMap>(tmap, map));
1.1149 return *this;
1.1150 }
1.1151
1.1152 @@ -1096,8 +997,8 @@
1.1153 ///
1.1154 /// Make a copy of the given arc.
1.1155 GraphCopy& arc(TArc& tarc, const Arc& sarc) {
1.1156 - arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
1.1157 - ArcRefMap, TArc>(tarc, sarc));
1.1158 + _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
1.1159 + ArcRefMap, TArc>(tarc, sarc));
1.1160 return *this;
1.1161 }
1.1162
1.1163 @@ -1106,8 +1007,8 @@
1.1164 /// Copies the edge references into the given map.
1.1165 template <typename EdgeRef>
1.1166 GraphCopy& edgeRef(EdgeRef& map) {
1.1167 - edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,
1.1168 - EdgeRefMap, EdgeRef>(map));
1.1169 + _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
1.1170 + EdgeRefMap, EdgeRef>(map));
1.1171 return *this;
1.1172 }
1.1173
1.1174 @@ -1117,21 +1018,21 @@
1.1175 /// references) into the given map.
1.1176 template <typename EdgeCrossRef>
1.1177 GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.1178 - edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
1.1179 - Edge, EdgeRefMap, EdgeCrossRef>(map));
1.1180 + _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
1.1181 + Edge, EdgeRefMap, EdgeCrossRef>(map));
1.1182 return *this;
1.1183 }
1.1184
1.1185 /// \brief Make copy of the given map.
1.1186 ///
1.1187 - /// Makes copy of the given map for the newly created digraph.
1.1188 - /// The new map's key type is the to digraph's edge type,
1.1189 - /// and the copied map's key type is the from digraph's edge
1.1190 + /// Makes copy of the given map for the newly created graph.
1.1191 + /// The new map's key type is the to graph's edge type,
1.1192 + /// and the copied map's key type is the from graph's edge
1.1193 /// type.
1.1194 template <typename ToMap, typename FromMap>
1.1195 GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
1.1196 - edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,
1.1197 - EdgeRefMap, ToMap, FromMap>(tmap, map));
1.1198 + _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
1.1199 + EdgeRefMap, ToMap, FromMap>(tmap, map));
1.1200 return *this;
1.1201 }
1.1202
1.1203 @@ -1139,8 +1040,8 @@
1.1204 ///
1.1205 /// Make a copy of the given edge.
1.1206 GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1.1207 - edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,
1.1208 - EdgeRefMap, TEdge>(tedge, sedge));
1.1209 + _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
1.1210 + EdgeRefMap, TEdge>(tedge, sedge));
1.1211 return *this;
1.1212 }
1.1213
1.1214 @@ -1148,51 +1049,51 @@
1.1215 ///
1.1216 /// Executes the copies.
1.1217 void run() {
1.1218 - NodeRefMap nodeRefMap(from);
1.1219 - EdgeRefMap edgeRefMap(from);
1.1220 - ArcRefMap arcRefMap(to, from, edgeRefMap, nodeRefMap);
1.1221 - _digraph_utils_bits::GraphCopySelector<To>::
1.1222 - copy(to, from, nodeRefMap, edgeRefMap);
1.1223 - for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1.1224 - nodeMapCopies[i]->copy(from, nodeRefMap);
1.1225 + NodeRefMap nodeRefMap(_from);
1.1226 + EdgeRefMap edgeRefMap(_from);
1.1227 + ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
1.1228 + _graph_utils_bits::GraphCopySelector<To>::
1.1229 + copy(_to, _from, nodeRefMap, edgeRefMap);
1.1230 + for (int i = 0; i < int(_node_maps.size()); ++i) {
1.1231 + _node_maps[i]->copy(_from, nodeRefMap);
1.1232 }
1.1233 - for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1.1234 - edgeMapCopies[i]->copy(from, edgeRefMap);
1.1235 + for (int i = 0; i < int(_edge_maps.size()); ++i) {
1.1236 + _edge_maps[i]->copy(_from, edgeRefMap);
1.1237 }
1.1238 - for (int i = 0; i < int(arcMapCopies.size()); ++i) {
1.1239 - arcMapCopies[i]->copy(from, arcRefMap);
1.1240 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
1.1241 + _arc_maps[i]->copy(_from, arcRefMap);
1.1242 }
1.1243 }
1.1244
1.1245 private:
1.1246
1.1247 - const From& from;
1.1248 - To& to;
1.1249 + const From& _from;
1.1250 + To& _to;
1.1251
1.1252 - std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.1253 - nodeMapCopies;
1.1254 + std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.1255 + _node_maps;
1.1256
1.1257 - std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.1258 - arcMapCopies;
1.1259 + std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.1260 + _arc_maps;
1.1261
1.1262 - std::vector<_digraph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1.1263 - edgeMapCopies;
1.1264 + std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1.1265 + _edge_maps;
1.1266
1.1267 };
1.1268
1.1269 - /// \brief Copy an graph to another digraph.
1.1270 + /// \brief Copy a graph to another graph.
1.1271 ///
1.1272 - /// Copy an graph to another digraph.
1.1273 - /// The usage of the function:
1.1274 - ///
1.1275 + /// Copy a graph to another graph. The complete usage of the
1.1276 + /// function is detailed in the GraphCopy class, but a short
1.1277 + /// example shows a basic work:
1.1278 ///\code
1.1279 /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
1.1280 ///\endcode
1.1281 ///
1.1282 /// After the copy the \c nr map will contain the mapping from the
1.1283 - /// nodes of the \c from digraph to the nodes of the \c to digraph and
1.1284 - /// \c ecr will contain the mapping from the arcs of the \c to digraph
1.1285 - /// to the arcs of the \c from digraph.
1.1286 + /// nodes of the \c from graph to the nodes of the \c to graph and
1.1287 + /// \c ecr will contain the mapping from the arcs of the \c to graph
1.1288 + /// to the arcs of the \c from graph.
1.1289 ///
1.1290 /// \see GraphCopy
1.1291 template <typename To, typename From>
1.1292 @@ -1201,391 +1102,25 @@
1.1293 return GraphCopy<To, From>(to, from);
1.1294 }
1.1295
1.1296 - /// \brief Class to copy a bipartite digraph.
1.1297 - ///
1.1298 - /// Class to copy a bipartite digraph to another digraph
1.1299 - /// (duplicate a digraph). The simplest way of using it is through
1.1300 - /// the \c copyBpGraph() function.
1.1301 - template <typename To, typename From>
1.1302 - class BpGraphCopy {
1.1303 - private:
1.1304 -
1.1305 - typedef typename From::Node Node;
1.1306 - typedef typename From::Red Red;
1.1307 - typedef typename From::Blue Blue;
1.1308 - typedef typename From::NodeIt NodeIt;
1.1309 - typedef typename From::Arc Arc;
1.1310 - typedef typename From::ArcIt ArcIt;
1.1311 - typedef typename From::Edge Edge;
1.1312 - typedef typename From::EdgeIt EdgeIt;
1.1313 -
1.1314 - typedef typename To::Node TNode;
1.1315 - typedef typename To::Arc TArc;
1.1316 - typedef typename To::Edge TEdge;
1.1317 -
1.1318 - typedef typename From::template RedMap<TNode> RedRefMap;
1.1319 - typedef typename From::template BlueMap<TNode> BlueRefMap;
1.1320 - typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
1.1321 -
1.1322 - struct NodeRefMap {
1.1323 - NodeRefMap(const From& _from, const RedRefMap& _red_ref,
1.1324 - const BlueRefMap& _blue_ref)
1.1325 - : from(_from), red_ref(_red_ref), blue_ref(_blue_ref) {}
1.1326 -
1.1327 - typedef typename From::Node Key;
1.1328 - typedef typename To::Node Value;
1.1329 -
1.1330 - Value operator[](const Key& key) const {
1.1331 - return from.red(key) ? red_ref[key] : blue_ref[key];
1.1332 - }
1.1333 -
1.1334 - const From& from;
1.1335 - const RedRefMap& red_ref;
1.1336 - const BlueRefMap& blue_ref;
1.1337 - };
1.1338 -
1.1339 - struct ArcRefMap {
1.1340 - ArcRefMap(const To& _to, const From& _from,
1.1341 - const EdgeRefMap& _edge_ref, const NodeRefMap& _node_ref)
1.1342 - : to(_to), from(_from),
1.1343 - edge_ref(_edge_ref), node_ref(_node_ref) {}
1.1344 -
1.1345 - typedef typename From::Arc Key;
1.1346 - typedef typename To::Arc Value;
1.1347 -
1.1348 - Value operator[](const Key& key) const {
1.1349 - bool forward =
1.1350 - (from.direction(key) ==
1.1351 - (node_ref[from.source(static_cast<const Edge&>(key))] ==
1.1352 - to.source(edge_ref[static_cast<const Edge&>(key)])));
1.1353 - return to.direct(edge_ref[key], forward);
1.1354 - }
1.1355 -
1.1356 - const To& to;
1.1357 - const From& from;
1.1358 - const EdgeRefMap& edge_ref;
1.1359 - const NodeRefMap& node_ref;
1.1360 - };
1.1361 -
1.1362 - public:
1.1363 -
1.1364 -
1.1365 - /// \brief Constructor for the DigraphCopy.
1.1366 - ///
1.1367 - /// It copies the content of the \c _from digraph into the
1.1368 - /// \c _to digraph.
1.1369 - BpGraphCopy(To& _to, const From& _from)
1.1370 - : from(_from), to(_to) {}
1.1371 -
1.1372 - /// \brief Destructor of the DigraphCopy
1.1373 - ///
1.1374 - /// Destructor of the DigraphCopy
1.1375 - ~BpGraphCopy() {
1.1376 - for (int i = 0; i < int(redMapCopies.size()); ++i) {
1.1377 - delete redMapCopies[i];
1.1378 - }
1.1379 - for (int i = 0; i < int(blueMapCopies.size()); ++i) {
1.1380 - delete blueMapCopies[i];
1.1381 - }
1.1382 - for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1.1383 - delete nodeMapCopies[i];
1.1384 - }
1.1385 - for (int i = 0; i < int(arcMapCopies.size()); ++i) {
1.1386 - delete arcMapCopies[i];
1.1387 - }
1.1388 - for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1.1389 - delete edgeMapCopies[i];
1.1390 - }
1.1391 -
1.1392 - }
1.1393 -
1.1394 - /// \brief Copies the A-node references into the given map.
1.1395 - ///
1.1396 - /// Copies the A-node references into the given map.
1.1397 - template <typename RedRef>
1.1398 - BpGraphCopy& redRef(RedRef& map) {
1.1399 - redMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Red,
1.1400 - RedRefMap, RedRef>(map));
1.1401 - return *this;
1.1402 - }
1.1403 -
1.1404 - /// \brief Copies the A-node cross references into the given map.
1.1405 - ///
1.1406 - /// Copies the A-node cross references (reverse references) into
1.1407 - /// the given map.
1.1408 - template <typename RedCrossRef>
1.1409 - BpGraphCopy& redCrossRef(RedCrossRef& map) {
1.1410 - redMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
1.1411 - Red, RedRefMap, RedCrossRef>(map));
1.1412 - return *this;
1.1413 - }
1.1414 -
1.1415 - /// \brief Make copy of the given A-node map.
1.1416 - ///
1.1417 - /// Makes copy of the given map for the newly created digraph.
1.1418 - /// The new map's key type is the to digraph's node type,
1.1419 - /// and the copied map's key type is the from digraph's node
1.1420 - /// type.
1.1421 - template <typename ToMap, typename FromMap>
1.1422 - BpGraphCopy& redMap(ToMap& tmap, const FromMap& map) {
1.1423 - redMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Red,
1.1424 - RedRefMap, ToMap, FromMap>(tmap, map));
1.1425 - return *this;
1.1426 - }
1.1427 -
1.1428 - /// \brief Copies the B-node references into the given map.
1.1429 - ///
1.1430 - /// Copies the B-node references into the given map.
1.1431 - template <typename BlueRef>
1.1432 - BpGraphCopy& blueRef(BlueRef& map) {
1.1433 - blueMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Blue,
1.1434 - BlueRefMap, BlueRef>(map));
1.1435 - return *this;
1.1436 - }
1.1437 -
1.1438 - /// \brief Copies the B-node cross references into the given map.
1.1439 - ///
1.1440 - /// Copies the B-node cross references (reverse references) into
1.1441 - /// the given map.
1.1442 - template <typename BlueCrossRef>
1.1443 - BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
1.1444 - blueMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
1.1445 - Blue, BlueRefMap, BlueCrossRef>(map));
1.1446 - return *this;
1.1447 - }
1.1448 -
1.1449 - /// \brief Make copy of the given B-node map.
1.1450 - ///
1.1451 - /// Makes copy of the given map for the newly created digraph.
1.1452 - /// The new map's key type is the to digraph's node type,
1.1453 - /// and the copied map's key type is the from digraph's node
1.1454 - /// type.
1.1455 - template <typename ToMap, typename FromMap>
1.1456 - BpGraphCopy& blueMap(ToMap& tmap, const FromMap& map) {
1.1457 - blueMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Blue,
1.1458 - BlueRefMap, ToMap, FromMap>(tmap, map));
1.1459 - return *this;
1.1460 - }
1.1461 - /// \brief Copies the node references into the given map.
1.1462 - ///
1.1463 - /// Copies the node references into the given map.
1.1464 - template <typename NodeRef>
1.1465 - BpGraphCopy& nodeRef(NodeRef& map) {
1.1466 - nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
1.1467 - NodeRefMap, NodeRef>(map));
1.1468 - return *this;
1.1469 - }
1.1470 -
1.1471 - /// \brief Copies the node cross references into the given map.
1.1472 - ///
1.1473 - /// Copies the node cross references (reverse references) into
1.1474 - /// the given map.
1.1475 - template <typename NodeCrossRef>
1.1476 - BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.1477 - nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
1.1478 - NodeRefMap, NodeCrossRef>(map));
1.1479 - return *this;
1.1480 - }
1.1481 -
1.1482 - /// \brief Make copy of the given map.
1.1483 - ///
1.1484 - /// Makes copy of the given map for the newly created digraph.
1.1485 - /// The new map's key type is the to digraph's node type,
1.1486 - /// and the copied map's key type is the from digraph's node
1.1487 - /// type.
1.1488 - template <typename ToMap, typename FromMap>
1.1489 - BpGraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
1.1490 - nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
1.1491 - NodeRefMap, ToMap, FromMap>(tmap, map));
1.1492 - return *this;
1.1493 - }
1.1494 -
1.1495 - /// \brief Make a copy of the given node.
1.1496 - ///
1.1497 - /// Make a copy of the given node.
1.1498 - BpGraphCopy& node(TNode& tnode, const Node& snode) {
1.1499 - nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
1.1500 - NodeRefMap, TNode>(tnode, snode));
1.1501 - return *this;
1.1502 - }
1.1503 -
1.1504 - /// \brief Copies the arc references into the given map.
1.1505 - ///
1.1506 - /// Copies the arc references into the given map.
1.1507 - template <typename ArcRef>
1.1508 - BpGraphCopy& arcRef(ArcRef& map) {
1.1509 - arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
1.1510 - ArcRefMap, ArcRef>(map));
1.1511 - return *this;
1.1512 - }
1.1513 -
1.1514 - /// \brief Copies the arc cross references into the given map.
1.1515 - ///
1.1516 - /// Copies the arc cross references (reverse references) into
1.1517 - /// the given map.
1.1518 - template <typename ArcCrossRef>
1.1519 - BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
1.1520 - arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
1.1521 - ArcRefMap, ArcCrossRef>(map));
1.1522 - return *this;
1.1523 - }
1.1524 -
1.1525 - /// \brief Make copy of the given map.
1.1526 - ///
1.1527 - /// Makes copy of the given map for the newly created digraph.
1.1528 - /// The new map's key type is the to digraph's arc type,
1.1529 - /// and the copied map's key type is the from digraph's arc
1.1530 - /// type.
1.1531 - template <typename ToMap, typename FromMap>
1.1532 - BpGraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
1.1533 - arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
1.1534 - ArcRefMap, ToMap, FromMap>(tmap, map));
1.1535 - return *this;
1.1536 - }
1.1537 -
1.1538 - /// \brief Make a copy of the given arc.
1.1539 - ///
1.1540 - /// Make a copy of the given arc.
1.1541 - BpGraphCopy& arc(TArc& tarc, const Arc& sarc) {
1.1542 - arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
1.1543 - ArcRefMap, TArc>(tarc, sarc));
1.1544 - return *this;
1.1545 - }
1.1546 -
1.1547 - /// \brief Copies the edge references into the given map.
1.1548 - ///
1.1549 - /// Copies the edge references into the given map.
1.1550 - template <typename EdgeRef>
1.1551 - BpGraphCopy& edgeRef(EdgeRef& map) {
1.1552 - edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,
1.1553 - EdgeRefMap, EdgeRef>(map));
1.1554 - return *this;
1.1555 - }
1.1556 -
1.1557 - /// \brief Copies the edge cross references into the given map.
1.1558 - ///
1.1559 - /// Copies the edge cross references (reverse
1.1560 - /// references) into the given map.
1.1561 - template <typename EdgeCrossRef>
1.1562 - BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.1563 - edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
1.1564 - Edge, EdgeRefMap, EdgeCrossRef>(map));
1.1565 - return *this;
1.1566 - }
1.1567 -
1.1568 - /// \brief Make copy of the given map.
1.1569 - ///
1.1570 - /// Makes copy of the given map for the newly created digraph.
1.1571 - /// The new map's key type is the to digraph's edge type,
1.1572 - /// and the copied map's key type is the from digraph's edge
1.1573 - /// type.
1.1574 - template <typename ToMap, typename FromMap>
1.1575 - BpGraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
1.1576 - edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,
1.1577 - EdgeRefMap, ToMap, FromMap>(tmap, map));
1.1578 - return *this;
1.1579 - }
1.1580 -
1.1581 - /// \brief Make a copy of the given edge.
1.1582 - ///
1.1583 - /// Make a copy of the given edge.
1.1584 - BpGraphCopy& edge(TEdge& tedge, const Edge& sedge) {
1.1585 - edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,
1.1586 - EdgeRefMap, TEdge>(tedge, sedge));
1.1587 - return *this;
1.1588 - }
1.1589 -
1.1590 - /// \brief Executes the copies.
1.1591 - ///
1.1592 - /// Executes the copies.
1.1593 - void run() {
1.1594 - RedRefMap redRefMap(from);
1.1595 - BlueRefMap blueRefMap(from);
1.1596 - NodeRefMap nodeRefMap(from, redRefMap, blueRefMap);
1.1597 - EdgeRefMap edgeRefMap(from);
1.1598 - ArcRefMap arcRefMap(to, from, edgeRefMap, nodeRefMap);
1.1599 - _digraph_utils_bits::BpGraphCopySelector<To>::
1.1600 - copy(to, from, redRefMap, blueRefMap, edgeRefMap);
1.1601 - for (int i = 0; i < int(redMapCopies.size()); ++i) {
1.1602 - redMapCopies[i]->copy(from, redRefMap);
1.1603 - }
1.1604 - for (int i = 0; i < int(blueMapCopies.size()); ++i) {
1.1605 - blueMapCopies[i]->copy(from, blueRefMap);
1.1606 - }
1.1607 - for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
1.1608 - nodeMapCopies[i]->copy(from, nodeRefMap);
1.1609 - }
1.1610 - for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
1.1611 - edgeMapCopies[i]->copy(from, edgeRefMap);
1.1612 - }
1.1613 - for (int i = 0; i < int(arcMapCopies.size()); ++i) {
1.1614 - arcMapCopies[i]->copy(from, arcRefMap);
1.1615 - }
1.1616 - }
1.1617 -
1.1618 - private:
1.1619 -
1.1620 - const From& from;
1.1621 - To& to;
1.1622 -
1.1623 - std::vector<_digraph_utils_bits::MapCopyBase<From, Red, RedRefMap>* >
1.1624 - redMapCopies;
1.1625 -
1.1626 - std::vector<_digraph_utils_bits::MapCopyBase<From, Blue, BlueRefMap>* >
1.1627 - blueMapCopies;
1.1628 -
1.1629 - std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
1.1630 - nodeMapCopies;
1.1631 -
1.1632 - std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
1.1633 - arcMapCopies;
1.1634 -
1.1635 - std::vector<_digraph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
1.1636 - edgeMapCopies;
1.1637 -
1.1638 - };
1.1639 -
1.1640 - /// \brief Copy a bipartite digraph to another digraph.
1.1641 - ///
1.1642 - /// Copy a bipartite digraph to another digraph.
1.1643 - /// The usage of the function:
1.1644 - ///
1.1645 - ///\code
1.1646 - /// copyBpGraph(trg, src).redRef(anr).arcCrossRef(ecr).run();
1.1647 - ///\endcode
1.1648 - ///
1.1649 - /// After the copy the \c nr map will contain the mapping from the
1.1650 - /// nodes of the \c from digraph to the nodes of the \c to digraph and
1.1651 - /// \c ecr will contain the mapping from the arcs of the \c to digraph
1.1652 - /// to the arcs of the \c from digraph.
1.1653 - ///
1.1654 - /// \see BpGraphCopy
1.1655 - template <typename To, typename From>
1.1656 - BpGraphCopy<To, From>
1.1657 - copyBpGraph(To& to, const From& from) {
1.1658 - return BpGraphCopy<To, From>(to, from);
1.1659 - }
1.1660 -
1.1661 -
1.1662 /// @}
1.1663
1.1664 - /// \addtogroup digraph_maps
1.1665 + /// \addtogroup graph_maps
1.1666 /// @{
1.1667
1.1668 - /// Provides an immutable and unique id for each item in the digraph.
1.1669 + /// Provides an immutable and unique id for each item in the graph.
1.1670
1.1671 /// The IdMap class provides a unique and immutable id for each item of the
1.1672 - /// same type (e.g. node) in the digraph. This id is <ul><li>\b unique:
1.1673 + /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
1.1674 /// different items (nodes) get different ids <li>\b immutable: the id of an
1.1675 /// item (node) does not change (even if you delete other nodes). </ul>
1.1676 /// Through this map you get access (i.e. can read) the inner id values of
1.1677 - /// the items stored in the digraph. This map can be inverted with its member
1.1678 - /// class \c InverseMap.
1.1679 + /// the items stored in the graph. This map can be inverted with its member
1.1680 + /// class \c InverseMap or with the \c operator() member.
1.1681 ///
1.1682 - template <typename _Digraph, typename _Item>
1.1683 + template <typename _Graph, typename _Item>
1.1684 class IdMap {
1.1685 public:
1.1686 - typedef _Digraph Digraph;
1.1687 + typedef _Graph Graph;
1.1688 typedef int Value;
1.1689 typedef _Item Item;
1.1690 typedef _Item Key;
1.1691 @@ -1593,20 +1128,20 @@
1.1692 /// \brief Constructor.
1.1693 ///
1.1694 /// Constructor of the map.
1.1695 - explicit IdMap(const Digraph& _digraph) : digraph(&_digraph) {}
1.1696 + explicit IdMap(const Graph& graph) : _graph(&graph) {}
1.1697
1.1698 /// \brief Gives back the \e id of the item.
1.1699 ///
1.1700 /// Gives back the immutable and unique \e id of the item.
1.1701 - int operator[](const Item& item) const { return digraph->id(item);}
1.1702 + int operator[](const Item& item) const { return _graph->id(item);}
1.1703
1.1704 /// \brief Gives back the item by its id.
1.1705 ///
1.1706 /// Gives back the item by its id.
1.1707 - Item operator()(int id) { return digraph->fromId(id, Item()); }
1.1708 + Item operator()(int id) { return _graph->fromId(id, Item()); }
1.1709
1.1710 private:
1.1711 - const Digraph* digraph;
1.1712 + const Graph* _graph;
1.1713
1.1714 public:
1.1715
1.1716 @@ -1620,34 +1155,34 @@
1.1717 /// \brief Constructor.
1.1718 ///
1.1719 /// Constructor for creating an id-to-item map.
1.1720 - explicit InverseMap(const Digraph& _digraph) : digraph(&_digraph) {}
1.1721 + explicit InverseMap(const Graph& graph) : _graph(&graph) {}
1.1722
1.1723 /// \brief Constructor.
1.1724 ///
1.1725 /// Constructor for creating an id-to-item map.
1.1726 - explicit InverseMap(const IdMap& idMap) : digraph(idMap.digraph) {}
1.1727 + explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1.1728
1.1729 /// \brief Gives back the given item from its id.
1.1730 ///
1.1731 /// Gives back the given item from its id.
1.1732 ///
1.1733 - Item operator[](int id) const { return digraph->fromId(id, Item());}
1.1734 + Item operator[](int id) const { return _graph->fromId(id, Item());}
1.1735
1.1736 private:
1.1737 - const Digraph* digraph;
1.1738 + const Graph* _graph;
1.1739 };
1.1740
1.1741 /// \brief Gives back the inverse of the map.
1.1742 ///
1.1743 /// Gives back the inverse of the IdMap.
1.1744 - InverseMap inverse() const { return InverseMap(*digraph);}
1.1745 + InverseMap inverse() const { return InverseMap(*_graph);}
1.1746
1.1747 };
1.1748
1.1749
1.1750 - /// \brief General invertable digraph-map type.
1.1751 + /// \brief General invertable graph-map type.
1.1752
1.1753 - /// This type provides simple invertable digraph-maps.
1.1754 + /// This type provides simple invertable graph-maps.
1.1755 /// The InvertableMap wraps an arbitrary ReadWriteMap
1.1756 /// and if a key is set to a new value then store it
1.1757 /// in the inverse map.
1.1758 @@ -1655,20 +1190,20 @@
1.1759 /// The values of the map can be accessed
1.1760 /// with stl compatible forward iterator.
1.1761 ///
1.1762 - /// \param _Digraph The digraph type.
1.1763 - /// \param _Item The item type of the digraph.
1.1764 + /// \param _Graph The graph type.
1.1765 + /// \param _Item The item type of the graph.
1.1766 /// \param _Value The value type of the map.
1.1767 ///
1.1768 /// \see IterableValueMap
1.1769 - template <typename _Digraph, typename _Item, typename _Value>
1.1770 - class InvertableMap : protected DefaultMap<_Digraph, _Item, _Value> {
1.1771 + template <typename _Graph, typename _Item, typename _Value>
1.1772 + class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
1.1773 private:
1.1774
1.1775 - typedef DefaultMap<_Digraph, _Item, _Value> Map;
1.1776 - typedef _Digraph Digraph;
1.1777 + typedef DefaultMap<_Graph, _Item, _Value> Map;
1.1778 + typedef _Graph Graph;
1.1779
1.1780 typedef std::map<_Value, _Item> Container;
1.1781 - Container invMap;
1.1782 + Container _inv_map;
1.1783
1.1784 public:
1.1785
1.1786 @@ -1681,9 +1216,9 @@
1.1787
1.1788 /// \brief Constructor.
1.1789 ///
1.1790 - /// Construct a new InvertableMap for the digraph.
1.1791 + /// Construct a new InvertableMap for the graph.
1.1792 ///
1.1793 - explicit InvertableMap(const Digraph& digraph) : Map(digraph) {}
1.1794 + explicit InvertableMap(const Graph& graph) : Map(graph) {}
1.1795
1.1796 /// \brief Forward iterator for values.
1.1797 ///
1.1798 @@ -1725,7 +1260,7 @@
1.1799 /// map can be accessed in the [beginValue, endValue)
1.1800 /// range.
1.1801 ValueIterator beginValue() const {
1.1802 - return ValueIterator(invMap.begin());
1.1803 + return ValueIterator(_inv_map.begin());
1.1804 }
1.1805
1.1806 /// \brief Returns an iterator after the last value.
1.1807 @@ -1735,7 +1270,7 @@
1.1808 /// map can be accessed in the [beginValue, endValue)
1.1809 /// range.
1.1810 ValueIterator endValue() const {
1.1811 - return ValueIterator(invMap.end());
1.1812 + return ValueIterator(_inv_map.end());
1.1813 }
1.1814
1.1815 /// \brief The setter function of the map.
1.1816 @@ -1743,11 +1278,11 @@
1.1817 /// Sets the mapped value.
1.1818 void set(const Key& key, const Value& val) {
1.1819 Value oldval = Map::operator[](key);
1.1820 - typename Container::iterator it = invMap.find(oldval);
1.1821 - if (it != invMap.end() && it->second == key) {
1.1822 - invMap.erase(it);
1.1823 + typename Container::iterator it = _inv_map.find(oldval);
1.1824 + if (it != _inv_map.end() && it->second == key) {
1.1825 + _inv_map.erase(it);
1.1826 }
1.1827 - invMap.insert(make_pair(val, key));
1.1828 + _inv_map.insert(make_pair(val, key));
1.1829 Map::set(key, val);
1.1830 }
1.1831
1.1832 @@ -1763,8 +1298,8 @@
1.1833 ///
1.1834 /// Gives back the item by its value.
1.1835 Key operator()(const Value& key) const {
1.1836 - typename Container::const_iterator it = invMap.find(key);
1.1837 - return it != invMap.end() ? it->second : INVALID;
1.1838 + typename Container::const_iterator it = _inv_map.find(key);
1.1839 + return it != _inv_map.end() ? it->second : INVALID;
1.1840 }
1.1841
1.1842 protected:
1.1843 @@ -1775,9 +1310,9 @@
1.1844 /// \c AlterationNotifier.
1.1845 virtual void erase(const Key& key) {
1.1846 Value val = Map::operator[](key);
1.1847 - typename Container::iterator it = invMap.find(val);
1.1848 - if (it != invMap.end() && it->second == key) {
1.1849 - invMap.erase(it);
1.1850 + typename Container::iterator it = _inv_map.find(val);
1.1851 + if (it != _inv_map.end() && it->second == key) {
1.1852 + _inv_map.erase(it);
1.1853 }
1.1854 Map::erase(key);
1.1855 }
1.1856 @@ -1789,9 +1324,9 @@
1.1857 virtual void erase(const std::vector<Key>& keys) {
1.1858 for (int i = 0; i < int(keys.size()); ++i) {
1.1859 Value val = Map::operator[](keys[i]);
1.1860 - typename Container::iterator it = invMap.find(val);
1.1861 - if (it != invMap.end() && it->second == keys[i]) {
1.1862 - invMap.erase(it);
1.1863 + typename Container::iterator it = _inv_map.find(val);
1.1864 + if (it != _inv_map.end() && it->second == keys[i]) {
1.1865 + _inv_map.erase(it);
1.1866 }
1.1867 }
1.1868 Map::erase(keys);
1.1869 @@ -1802,7 +1337,7 @@
1.1870 /// Clear the keys from the map and inverse map. It is called by the
1.1871 /// \c AlterationNotifier.
1.1872 virtual void clear() {
1.1873 - invMap.clear();
1.1874 + _inv_map.clear();
1.1875 Map::clear();
1.1876 }
1.1877
1.1878 @@ -1817,8 +1352,8 @@
1.1879 /// \brief Constructor of the InverseMap.
1.1880 ///
1.1881 /// Constructor of the InverseMap.
1.1882 - explicit InverseMap(const InvertableMap& _inverted)
1.1883 - : inverted(_inverted) {}
1.1884 + explicit InverseMap(const InvertableMap& inverted)
1.1885 + : _inverted(inverted) {}
1.1886
1.1887 /// The value type of the InverseMap.
1.1888 typedef typename InvertableMap::Key Value;
1.1889 @@ -1830,11 +1365,11 @@
1.1890 /// Subscript operator. It gives back always the item
1.1891 /// what was last assigned to the value.
1.1892 Value operator[](const Key& key) const {
1.1893 - return inverted(key);
1.1894 + return _inverted(key);
1.1895 }
1.1896
1.1897 private:
1.1898 - const InvertableMap& inverted;
1.1899 + const InvertableMap& _inverted;
1.1900 };
1.1901
1.1902 /// \brief It gives back the just readable inverse map.
1.1903 @@ -1849,29 +1384,29 @@
1.1904 };
1.1905
1.1906 /// \brief Provides a mutable, continuous and unique descriptor for each
1.1907 - /// item in the digraph.
1.1908 + /// item in the graph.
1.1909 ///
1.1910 /// The DescriptorMap class provides a unique and continuous (but mutable)
1.1911 /// descriptor (id) for each item of the same type (e.g. node) in the
1.1912 - /// digraph. This id is <ul><li>\b unique: different items (nodes) get
1.1913 + /// graph. This id is <ul><li>\b unique: different items (nodes) get
1.1914 /// different ids <li>\b continuous: the range of the ids is the set of
1.1915 /// integers between 0 and \c n-1, where \c n is the number of the items of
1.1916 /// this type (e.g. nodes) (so the id of a node can change if you delete an
1.1917 /// other node, i.e. this id is mutable). </ul> This map can be inverted
1.1918 - /// with its member class \c InverseMap.
1.1919 + /// with its member class \c InverseMap, or with the \c operator() member.
1.1920 ///
1.1921 - /// \param _Digraph The digraph class the \c DescriptorMap belongs to.
1.1922 + /// \param _Graph The graph class the \c DescriptorMap belongs to.
1.1923 /// \param _Item The Item is the Key of the Map. It may be Node, Arc or
1.1924 /// Edge.
1.1925 - template <typename _Digraph, typename _Item>
1.1926 - class DescriptorMap : protected DefaultMap<_Digraph, _Item, int> {
1.1927 + template <typename _Graph, typename _Item>
1.1928 + class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
1.1929
1.1930 typedef _Item Item;
1.1931 - typedef DefaultMap<_Digraph, _Item, int> Map;
1.1932 + typedef DefaultMap<_Graph, _Item, int> Map;
1.1933
1.1934 public:
1.1935 - /// The digraph class of DescriptorMap.
1.1936 - typedef _Digraph Digraph;
1.1937 + /// The graph class of DescriptorMap.
1.1938 + typedef _Graph Graph;
1.1939
1.1940 /// The key type of DescriptorMap (Node, Arc, Edge).
1.1941 typedef typename Map::Key Key;
1.1942 @@ -1881,12 +1416,12 @@
1.1943 /// \brief Constructor.
1.1944 ///
1.1945 /// Constructor for descriptor map.
1.1946 - explicit DescriptorMap(const Digraph& _digraph) : Map(_digraph) {
1.1947 + explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1.1948 Item it;
1.1949 const typename Map::Notifier* nf = Map::notifier();
1.1950 for (nf->first(it); it != INVALID; nf->next(it)) {
1.1951 - Map::set(it, invMap.size());
1.1952 - invMap.push_back(it);
1.1953 + Map::set(it, _inv_map.size());
1.1954 + _inv_map.push_back(it);
1.1955 }
1.1956 }
1.1957
1.1958 @@ -1898,8 +1433,8 @@
1.1959 /// \c AlterationNotifier.
1.1960 virtual void add(const Item& item) {
1.1961 Map::add(item);
1.1962 - Map::set(item, invMap.size());
1.1963 - invMap.push_back(item);
1.1964 + Map::set(item, _inv_map.size());
1.1965 + _inv_map.push_back(item);
1.1966 }
1.1967
1.1968 /// \brief Add more new keys to the map.
1.1969 @@ -1909,8 +1444,8 @@
1.1970 virtual void add(const std::vector<Item>& items) {
1.1971 Map::add(items);
1.1972 for (int i = 0; i < int(items.size()); ++i) {
1.1973 - Map::set(items[i], invMap.size());
1.1974 - invMap.push_back(items[i]);
1.1975 + Map::set(items[i], _inv_map.size());
1.1976 + _inv_map.push_back(items[i]);
1.1977 }
1.1978 }
1.1979
1.1980 @@ -1919,9 +1454,9 @@
1.1981 /// Erase the key from the map. It is called by the
1.1982 /// \c AlterationNotifier.
1.1983 virtual void erase(const Item& item) {
1.1984 - Map::set(invMap.back(), Map::operator[](item));
1.1985 - invMap[Map::operator[](item)] = invMap.back();
1.1986 - invMap.pop_back();
1.1987 + Map::set(_inv_map.back(), Map::operator[](item));
1.1988 + _inv_map[Map::operator[](item)] = _inv_map.back();
1.1989 + _inv_map.pop_back();
1.1990 Map::erase(item);
1.1991 }
1.1992
1.1993 @@ -1931,9 +1466,9 @@
1.1994 /// \c AlterationNotifier.
1.1995 virtual void erase(const std::vector<Item>& items) {
1.1996 for (int i = 0; i < int(items.size()); ++i) {
1.1997 - Map::set(invMap.back(), Map::operator[](items[i]));
1.1998 - invMap[Map::operator[](items[i])] = invMap.back();
1.1999 - invMap.pop_back();
1.2000 + Map::set(_inv_map.back(), Map::operator[](items[i]));
1.2001 + _inv_map[Map::operator[](items[i])] = _inv_map.back();
1.2002 + _inv_map.pop_back();
1.2003 }
1.2004 Map::erase(items);
1.2005 }
1.2006 @@ -1947,8 +1482,8 @@
1.2007 Item it;
1.2008 const typename Map::Notifier* nf = Map::notifier();
1.2009 for (nf->first(it); it != INVALID; nf->next(it)) {
1.2010 - Map::set(it, invMap.size());
1.2011 - invMap.push_back(it);
1.2012 + Map::set(it, _inv_map.size());
1.2013 + _inv_map.push_back(it);
1.2014 }
1.2015 }
1.2016
1.2017 @@ -1957,7 +1492,7 @@
1.2018 /// Clear the keys from the map. It is called by the
1.2019 /// \c AlterationNotifier.
1.2020 virtual void clear() {
1.2021 - invMap.clear();
1.2022 + _inv_map.clear();
1.2023 Map::clear();
1.2024 }
1.2025
1.2026 @@ -1967,7 +1502,7 @@
1.2027 ///
1.2028 /// Returns the maximal value plus one in the map.
1.2029 unsigned int size() const {
1.2030 - return invMap.size();
1.2031 + return _inv_map.size();
1.2032 }
1.2033
1.2034 /// \brief Swaps the position of the two items in the map.
1.2035 @@ -1977,9 +1512,9 @@
1.2036 int pi = Map::operator[](p);
1.2037 int qi = Map::operator[](q);
1.2038 Map::set(p, qi);
1.2039 - invMap[qi] = p;
1.2040 + _inv_map[qi] = p;
1.2041 Map::set(q, pi);
1.2042 - invMap[pi] = q;
1.2043 + _inv_map[pi] = q;
1.2044 }
1.2045
1.2046 /// \brief Gives back the \e descriptor of the item.
1.2047 @@ -1993,13 +1528,13 @@
1.2048 ///
1.2049 /// Gives back th item by its descriptor.
1.2050 Item operator()(int id) const {
1.2051 - return invMap[id];
1.2052 + return _inv_map[id];
1.2053 }
1.2054
1.2055 private:
1.2056
1.2057 typedef std::vector<Item> Container;
1.2058 - Container invMap;
1.2059 + Container _inv_map;
1.2060
1.2061 public:
1.2062 /// \brief The inverse map type of DescriptorMap.
1.2063 @@ -2010,8 +1545,8 @@
1.2064 /// \brief Constructor of the InverseMap.
1.2065 ///
1.2066 /// Constructor of the InverseMap.
1.2067 - explicit InverseMap(const DescriptorMap& _inverted)
1.2068 - : inverted(_inverted) {}
1.2069 + explicit InverseMap(const DescriptorMap& inverted)
1.2070 + : _inverted(inverted) {}
1.2071
1.2072
1.2073 /// The value type of the InverseMap.
1.2074 @@ -2024,18 +1559,18 @@
1.2075 /// Subscript operator. It gives back the item
1.2076 /// that the descriptor belongs to currently.
1.2077 Value operator[](const Key& key) const {
1.2078 - return inverted(key);
1.2079 + return _inverted(key);
1.2080 }
1.2081
1.2082 /// \brief Size of the map.
1.2083 ///
1.2084 /// Returns the size of the map.
1.2085 unsigned int size() const {
1.2086 - return inverted.size();
1.2087 + return _inverted.size();
1.2088 }
1.2089
1.2090 private:
1.2091 - const DescriptorMap& inverted;
1.2092 + const DescriptorMap& _inverted;
1.2093 };
1.2094
1.2095 /// \brief Gives back the inverse of the map.
1.2096 @@ -2062,7 +1597,7 @@
1.2097 ///
1.2098 /// Constructor
1.2099 /// \param _digraph The digraph that the map belongs to.
1.2100 - explicit SourceMap(const Digraph& _digraph) : digraph(_digraph) {}
1.2101 + explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
1.2102
1.2103 /// \brief The subscript operator.
1.2104 ///
1.2105 @@ -2070,11 +1605,11 @@
1.2106 /// \param arc The arc
1.2107 /// \return The source of the arc
1.2108 Value operator[](const Key& arc) const {
1.2109 - return digraph.source(arc);
1.2110 + return _digraph.source(arc);
1.2111 }
1.2112
1.2113 private:
1.2114 - const Digraph& digraph;
1.2115 + const Digraph& _digraph;
1.2116 };
1.2117
1.2118 /// \brief Returns a \ref SourceMap class.
1.2119 @@ -2102,7 +1637,7 @@
1.2120 ///
1.2121 /// Constructor
1.2122 /// \param _digraph The digraph that the map belongs to.
1.2123 - explicit TargetMap(const Digraph& _digraph) : digraph(_digraph) {}
1.2124 + explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
1.2125
1.2126 /// \brief The subscript operator.
1.2127 ///
1.2128 @@ -2110,11 +1645,11 @@
1.2129 /// \param e The arc
1.2130 /// \return The target of the arc
1.2131 Value operator[](const Key& e) const {
1.2132 - return digraph.target(e);
1.2133 + return _digraph.target(e);
1.2134 }
1.2135
1.2136 private:
1.2137 - const Digraph& digraph;
1.2138 + const Digraph& _digraph;
1.2139 };
1.2140
1.2141 /// \brief Returns a \ref TargetMap class.
1.2142 @@ -2131,18 +1666,18 @@
1.2143 /// Returns the "forward" directed arc view of an edge.
1.2144 /// \see BackwardMap
1.2145 /// \author Balazs Dezso
1.2146 - template <typename Digraph>
1.2147 + template <typename Graph>
1.2148 class ForwardMap {
1.2149 public:
1.2150
1.2151 - typedef typename Digraph::Arc Value;
1.2152 - typedef typename Digraph::Edge Key;
1.2153 + typedef typename Graph::Arc Value;
1.2154 + typedef typename Graph::Edge Key;
1.2155
1.2156 /// \brief Constructor
1.2157 ///
1.2158 /// Constructor
1.2159 - /// \param _digraph The digraph that the map belongs to.
1.2160 - explicit ForwardMap(const Digraph& _digraph) : digraph(_digraph) {}
1.2161 + /// \param _graph The graph that the map belongs to.
1.2162 + explicit ForwardMap(const Graph& graph) : _graph(graph) {}
1.2163
1.2164 /// \brief The subscript operator.
1.2165 ///
1.2166 @@ -2150,20 +1685,20 @@
1.2167 /// \param key An edge
1.2168 /// \return The "forward" directed arc view of edge
1.2169 Value operator[](const Key& key) const {
1.2170 - return digraph.direct(key, true);
1.2171 + return _graph.direct(key, true);
1.2172 }
1.2173
1.2174 private:
1.2175 - const Digraph& digraph;
1.2176 + const Graph& _graph;
1.2177 };
1.2178
1.2179 /// \brief Returns a \ref ForwardMap class.
1.2180 ///
1.2181 /// This function just returns an \ref ForwardMap class.
1.2182 /// \relates ForwardMap
1.2183 - template <typename Digraph>
1.2184 - inline ForwardMap<Digraph> forwardMap(const Digraph& digraph) {
1.2185 - return ForwardMap<Digraph>(digraph);
1.2186 + template <typename Graph>
1.2187 + inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1.2188 + return ForwardMap<Graph>(graph);
1.2189 }
1.2190
1.2191 /// \brief Returns the "backward" directed arc view of an edge.
1.2192 @@ -2171,18 +1706,18 @@
1.2193 /// Returns the "backward" directed arc view of an edge.
1.2194 /// \see ForwardMap
1.2195 /// \author Balazs Dezso
1.2196 - template <typename Digraph>
1.2197 + template <typename Graph>
1.2198 class BackwardMap {
1.2199 public:
1.2200
1.2201 - typedef typename Digraph::Arc Value;
1.2202 - typedef typename Digraph::Edge Key;
1.2203 + typedef typename Graph::Arc Value;
1.2204 + typedef typename Graph::Edge Key;
1.2205
1.2206 /// \brief Constructor
1.2207 ///
1.2208 /// Constructor
1.2209 - /// \param _digraph The digraph that the map belongs to.
1.2210 - explicit BackwardMap(const Digraph& _digraph) : digraph(_digraph) {}
1.2211 + /// \param _graph The graph that the map belongs to.
1.2212 + explicit BackwardMap(const Graph& graph) : _graph(graph) {}
1.2213
1.2214 /// \brief The subscript operator.
1.2215 ///
1.2216 @@ -2190,20 +1725,20 @@
1.2217 /// \param key An edge
1.2218 /// \return The "backward" directed arc view of edge
1.2219 Value operator[](const Key& key) const {
1.2220 - return digraph.direct(key, false);
1.2221 + return _graph.direct(key, false);
1.2222 }
1.2223
1.2224 private:
1.2225 - const Digraph& digraph;
1.2226 + const Graph& _graph;
1.2227 };
1.2228
1.2229 /// \brief Returns a \ref BackwardMap class
1.2230
1.2231 /// This function just returns a \ref BackwardMap class.
1.2232 /// \relates BackwardMap
1.2233 - template <typename Digraph>
1.2234 - inline BackwardMap<Digraph> backwardMap(const Digraph& digraph) {
1.2235 - return BackwardMap<Digraph>(digraph);
1.2236 + template <typename Graph>
1.2237 + inline BackwardMap<Graph> backwardMap(const Graph& graph) {
1.2238 + return BackwardMap<Graph>(graph);
1.2239 }
1.2240
1.2241 /// \brief Potential difference map
1.2242 @@ -2220,20 +1755,21 @@
1.2243 /// \brief Constructor
1.2244 ///
1.2245 /// Contructor of the map
1.2246 - explicit PotentialDifferenceMap(const Digraph& _digraph,
1.2247 - const NodeMap& _potential)
1.2248 - : digraph(_digraph), potential(_potential) {}
1.2249 + explicit PotentialDifferenceMap(const Digraph& digraph,
1.2250 + const NodeMap& potential)
1.2251 + : _digraph(digraph), _potential(potential) {}
1.2252
1.2253 /// \brief Const subscription operator
1.2254 ///
1.2255 /// Const subscription operator
1.2256 Value operator[](const Key& arc) const {
1.2257 - return potential[digraph.target(arc)] - potential[digraph.source(arc)];
1.2258 + return _potential[_digraph.target(arc)] -
1.2259 + _potential[_digraph.source(arc)];
1.2260 }
1.2261
1.2262 private:
1.2263 - const Digraph& digraph;
1.2264 - const NodeMap& potential;
1.2265 + const Digraph& _digraph;
1.2266 + const NodeMap& _potential;
1.2267 };
1.2268
1.2269 /// \brief Returns a PotentialDifferenceMap.
1.2270 @@ -2274,16 +1810,15 @@
1.2271 typedef int Value;
1.2272 typedef typename Digraph::Node Key;
1.2273
1.2274 - typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
1.2275 + typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
1.2276 ::ItemNotifier::ObserverBase Parent;
1.2277
1.2278 private:
1.2279
1.2280 - class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
1.2281 + class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
1.2282 public:
1.2283
1.2284 - typedef DefaultMap<_Digraph, Key, int> Parent;
1.2285 - typedef typename Parent::Digraph Digraph;
1.2286 + typedef DefaultMap<Digraph, Key, int> Parent;
1.2287
1.2288 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
1.2289
1.2290 @@ -2314,17 +1849,18 @@
1.2291 /// \brief Constructor.
1.2292 ///
1.2293 /// Constructor for creating in-degree map.
1.2294 - explicit InDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
1.2295 - Parent::attach(digraph.notifier(typename _Digraph::Arc()));
1.2296 + explicit InDegMap(const Digraph& digraph)
1.2297 + : _digraph(digraph), _deg(digraph) {
1.2298 + Parent::attach(_digraph.notifier(typename Digraph::Arc()));
1.2299
1.2300 - for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
1.2301 - deg[it] = countInArcs(digraph, it);
1.2302 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.2303 + _deg[it] = countInArcs(_digraph, it);
1.2304 }
1.2305 }
1.2306
1.2307 /// Gives back the in-degree of a Node.
1.2308 int operator[](const Key& key) const {
1.2309 - return deg[key];
1.2310 + return _deg[key];
1.2311 }
1.2312
1.2313 protected:
1.2314 @@ -2332,40 +1868,40 @@
1.2315 typedef typename Digraph::Arc Arc;
1.2316
1.2317 virtual void add(const Arc& arc) {
1.2318 - ++deg[digraph.target(arc)];
1.2319 + ++_deg[_digraph.target(arc)];
1.2320 }
1.2321
1.2322 virtual void add(const std::vector<Arc>& arcs) {
1.2323 for (int i = 0; i < int(arcs.size()); ++i) {
1.2324 - ++deg[digraph.target(arcs[i])];
1.2325 + ++_deg[_digraph.target(arcs[i])];
1.2326 }
1.2327 }
1.2328
1.2329 virtual void erase(const Arc& arc) {
1.2330 - --deg[digraph.target(arc)];
1.2331 + --_deg[_digraph.target(arc)];
1.2332 }
1.2333
1.2334 virtual void erase(const std::vector<Arc>& arcs) {
1.2335 for (int i = 0; i < int(arcs.size()); ++i) {
1.2336 - --deg[digraph.target(arcs[i])];
1.2337 + --_deg[_digraph.target(arcs[i])];
1.2338 }
1.2339 }
1.2340
1.2341 virtual void build() {
1.2342 - for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
1.2343 - deg[it] = countInArcs(digraph, it);
1.2344 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.2345 + _deg[it] = countInArcs(_digraph, it);
1.2346 }
1.2347 }
1.2348
1.2349 virtual void clear() {
1.2350 - for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
1.2351 - deg[it] = 0;
1.2352 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.2353 + _deg[it] = 0;
1.2354 }
1.2355 }
1.2356 private:
1.2357
1.2358 - const _Digraph& digraph;
1.2359 - AutoNodeMap deg;
1.2360 + const Digraph& _digraph;
1.2361 + AutoNodeMap _deg;
1.2362 };
1.2363
1.2364 /// \brief Map of the node out-degrees.
1.2365 @@ -2391,21 +1927,20 @@
1.2366 ::ItemNotifier::ObserverBase {
1.2367
1.2368 public:
1.2369 -
1.2370 - typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
1.2371 - ::ItemNotifier::ObserverBase Parent;
1.2372
1.2373 typedef _Digraph Digraph;
1.2374 typedef int Value;
1.2375 typedef typename Digraph::Node Key;
1.2376
1.2377 + typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
1.2378 + ::ItemNotifier::ObserverBase Parent;
1.2379 +
1.2380 private:
1.2381
1.2382 - class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
1.2383 + class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
1.2384 public:
1.2385
1.2386 - typedef DefaultMap<_Digraph, Key, int> Parent;
1.2387 - typedef typename Parent::Digraph Digraph;
1.2388 + typedef DefaultMap<Digraph, Key, int> Parent;
1.2389
1.2390 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
1.2391
1.2392 @@ -2434,17 +1969,18 @@
1.2393 /// \brief Constructor.
1.2394 ///
1.2395 /// Constructor for creating out-degree map.
1.2396 - explicit OutDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
1.2397 - Parent::attach(digraph.notifier(typename _Digraph::Arc()));
1.2398 + explicit OutDegMap(const Digraph& digraph)
1.2399 + : _digraph(digraph), _deg(digraph) {
1.2400 + Parent::attach(_digraph.notifier(typename Digraph::Arc()));
1.2401
1.2402 - for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
1.2403 - deg[it] = countOutArcs(digraph, it);
1.2404 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.2405 + _deg[it] = countOutArcs(_digraph, it);
1.2406 }
1.2407 }
1.2408
1.2409 /// Gives back the out-degree of a Node.
1.2410 int operator[](const Key& key) const {
1.2411 - return deg[key];
1.2412 + return _deg[key];
1.2413 }
1.2414
1.2415 protected:
1.2416 @@ -2452,40 +1988,40 @@
1.2417 typedef typename Digraph::Arc Arc;
1.2418
1.2419 virtual void add(const Arc& arc) {
1.2420 - ++deg[digraph.source(arc)];
1.2421 + ++_deg[_digraph.source(arc)];
1.2422 }
1.2423
1.2424 virtual void add(const std::vector<Arc>& arcs) {
1.2425 for (int i = 0; i < int(arcs.size()); ++i) {
1.2426 - ++deg[digraph.source(arcs[i])];
1.2427 + ++_deg[_digraph.source(arcs[i])];
1.2428 }
1.2429 }
1.2430
1.2431 virtual void erase(const Arc& arc) {
1.2432 - --deg[digraph.source(arc)];
1.2433 + --_deg[_digraph.source(arc)];
1.2434 }
1.2435
1.2436 virtual void erase(const std::vector<Arc>& arcs) {
1.2437 for (int i = 0; i < int(arcs.size()); ++i) {
1.2438 - --deg[digraph.source(arcs[i])];
1.2439 + --_deg[_digraph.source(arcs[i])];
1.2440 }
1.2441 }
1.2442
1.2443 virtual void build() {
1.2444 - for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
1.2445 - deg[it] = countOutArcs(digraph, it);
1.2446 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.2447 + _deg[it] = countOutArcs(_digraph, it);
1.2448 }
1.2449 }
1.2450
1.2451 virtual void clear() {
1.2452 - for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
1.2453 - deg[it] = 0;
1.2454 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
1.2455 + _deg[it] = 0;
1.2456 }
1.2457 }
1.2458 private:
1.2459
1.2460 - const _Digraph& digraph;
1.2461 - AutoNodeMap deg;
1.2462 + const Digraph& _digraph;
1.2463 + AutoNodeMap _deg;
1.2464 };
1.2465
1.2466
1.2467 @@ -2500,7 +2036,7 @@
1.2468 ///the \c findFirst() and \c findNext() members.
1.2469 ///
1.2470 ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
1.2471 - ///digraph do not changed so frequently.
1.2472 + ///digraph is not changed so frequently.
1.2473 ///
1.2474 ///This class uses a self-adjusting binary search tree, Sleator's
1.2475 ///and Tarjan's Splay tree for guarantee the logarithmic amortized
1.2476 @@ -2520,7 +2056,7 @@
1.2477 typedef typename ItemSetTraits<G, typename G::Arc>
1.2478 ::ItemNotifier::ObserverBase Parent;
1.2479
1.2480 - GRAPH_TYPEDEFS(typename G);
1.2481 + DIGRAPH_TYPEDEFS(typename G);
1.2482 typedef G Digraph;
1.2483
1.2484 protected:
1.2485 @@ -2835,24 +2371,24 @@
1.2486 ///\ref INVALID otherwise.
1.2487 Arc operator()(Node s, Node t) const
1.2488 {
1.2489 - Arc e = _head[s];
1.2490 + Arc a = _head[s];
1.2491 while (true) {
1.2492 - if (_g.target(e) == t) {
1.2493 - const_cast<DynArcLookUp&>(*this).splay(e);
1.2494 - return e;
1.2495 - } else if (t < _g.target(e)) {
1.2496 - if (_left[e] == INVALID) {
1.2497 - const_cast<DynArcLookUp&>(*this).splay(e);
1.2498 + if (_g.target(a) == t) {
1.2499 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2500 + return a;
1.2501 + } else if (t < _g.target(a)) {
1.2502 + if (_left[a] == INVALID) {
1.2503 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2504 return INVALID;
1.2505 } else {
1.2506 - e = _left[e];
1.2507 + a = _left[a];
1.2508 }
1.2509 } else {
1.2510 - if (_right[e] == INVALID) {
1.2511 - const_cast<DynArcLookUp&>(*this).splay(e);
1.2512 + if (_right[a] == INVALID) {
1.2513 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2514 return INVALID;
1.2515 } else {
1.2516 - e = _right[e];
1.2517 + a = _right[a];
1.2518 }
1.2519 }
1.2520 }
1.2521 @@ -2869,25 +2405,25 @@
1.2522 /// otherwise.
1.2523 Arc findFirst(Node s, Node t) const
1.2524 {
1.2525 - Arc e = _head[s];
1.2526 + Arc a = _head[s];
1.2527 Arc r = INVALID;
1.2528 while (true) {
1.2529 - if (_g.target(e) < t) {
1.2530 - if (_right[e] == INVALID) {
1.2531 - const_cast<DynArcLookUp&>(*this).splay(e);
1.2532 + if (_g.target(a) < t) {
1.2533 + if (_right[a] == INVALID) {
1.2534 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2535 return r;
1.2536 } else {
1.2537 - e = _right[e];
1.2538 + a = _right[a];
1.2539 }
1.2540 } else {
1.2541 - if (_g.target(e) == t) {
1.2542 - r = e;
1.2543 + if (_g.target(a) == t) {
1.2544 + r = a;
1.2545 }
1.2546 - if (_left[e] == INVALID) {
1.2547 - const_cast<DynArcLookUp&>(*this).splay(e);
1.2548 + if (_left[a] == INVALID) {
1.2549 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2550 return r;
1.2551 } else {
1.2552 - e = _left[e];
1.2553 + a = _left[a];
1.2554 }
1.2555 }
1.2556 }
1.2557 @@ -2906,29 +2442,29 @@
1.2558 ///\note If \c e is not the result of the previous \c findFirst()
1.2559 ///operation then the amorized time bound can not be guaranteed.
1.2560 #ifdef DOXYGEN
1.2561 - Arc findNext(Node s, Node t, Arc e) const
1.2562 + Arc findNext(Node s, Node t, Arc a) const
1.2563 #else
1.2564 - Arc findNext(Node, Node t, Arc e) const
1.2565 + Arc findNext(Node, Node t, Arc a) const
1.2566 #endif
1.2567 {
1.2568 - if (_right[e] != INVALID) {
1.2569 - e = _right[e];
1.2570 - while (_left[e] != INVALID) {
1.2571 - e = _left[e];
1.2572 + if (_right[a] != INVALID) {
1.2573 + a = _right[a];
1.2574 + while (_left[a] != INVALID) {
1.2575 + a = _left[a];
1.2576 }
1.2577 - const_cast<DynArcLookUp&>(*this).splay(e);
1.2578 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2579 } else {
1.2580 - while (_parent[e] != INVALID && _right[_parent[e]] == e) {
1.2581 - e = _parent[e];
1.2582 + while (_parent[a] != INVALID && _right[_parent[a]] == a) {
1.2583 + a = _parent[a];
1.2584 }
1.2585 - if (_parent[e] == INVALID) {
1.2586 + if (_parent[a] == INVALID) {
1.2587 return INVALID;
1.2588 } else {
1.2589 - e = _parent[e];
1.2590 - const_cast<DynArcLookUp&>(*this).splay(e);
1.2591 + a = _parent[a];
1.2592 + const_cast<DynArcLookUp&>(*this).splay(a);
1.2593 }
1.2594 }
1.2595 - if (_g.target(e) == t) return e;
1.2596 + if (_g.target(a) == t) return a;
1.2597 else return INVALID;
1.2598 }
1.2599
1.2600 @@ -2957,7 +2493,7 @@
1.2601 class ArcLookUp
1.2602 {
1.2603 public:
1.2604 - GRAPH_TYPEDEFS(typename G);
1.2605 + DIGRAPH_TYPEDEFS(typename G);
1.2606 typedef G Digraph;
1.2607
1.2608 protected:
1.2609 @@ -3074,7 +2610,7 @@
1.2610 using ArcLookUp<G>::_left;
1.2611 using ArcLookUp<G>::_head;
1.2612
1.2613 - GRAPH_TYPEDEFS(typename G);
1.2614 + DIGRAPH_TYPEDEFS(typename G);
1.2615 typedef G Digraph;
1.2616
1.2617 typename Digraph::template ArcMap<Arc> _next;