1.1 --- a/lemon/bits/traits.h Mon Apr 21 17:35:12 2008 +0200
1.2 +++ b/lemon/bits/traits.h Tue Apr 22 15:04:00 2008 +0200
1.3 @@ -216,27 +216,27 @@
1.4 };
1.5
1.6 template <typename Graph, typename Enable = void>
1.7 - struct ArcNumTagIndicator {
1.8 + struct EdgeNumTagIndicator {
1.9 static const bool value = false;
1.10 };
1.11
1.12 template <typename Graph>
1.13 - struct ArcNumTagIndicator<
1.14 + struct EdgeNumTagIndicator<
1.15 Graph,
1.16 - typename enable_if<typename Graph::ArcNumTag, void>::type
1.17 + typename enable_if<typename Graph::EdgeNumTag, void>::type
1.18 > {
1.19 static const bool value = true;
1.20 };
1.21
1.22 template <typename Graph, typename Enable = void>
1.23 - struct FindArcTagIndicator {
1.24 + struct FindEdgeTagIndicator {
1.25 static const bool value = false;
1.26 };
1.27
1.28 template <typename Graph>
1.29 - struct FindArcTagIndicator<
1.30 + struct FindEdgeTagIndicator<
1.31 Graph,
1.32 - typename enable_if<typename Graph::FindArcTag, void>::type
1.33 + typename enable_if<typename Graph::FindEdgeTag, void>::type
1.34 > {
1.35 static const bool value = true;
1.36 };
2.1 --- a/lemon/graph_utils.h Mon Apr 21 17:35:12 2008 +0200
2.2 +++ b/lemon/graph_utils.h Tue Apr 22 15:04:00 2008 +0200
2.3 @@ -35,7 +35,7 @@
2.4
2.5 ///\ingroup gutils
2.6 ///\file
2.7 -///\brief Digraph utilities.
2.8 +///\brief Graph utilities.
2.9
2.10 namespace lemon {
2.11
2.12 @@ -46,71 +46,36 @@
2.13
2.14 ///This \c \#define creates convenience typedefs for the following types
2.15 ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
2.16 - ///\c OutArcIt
2.17 - ///\note If \c G it a template parameter, it should be used in this way.
2.18 - ///\code
2.19 - /// GRAPH_TYPEDEFS(typename G);
2.20 - ///\endcode
2.21 - ///
2.22 - ///\warning There are no typedefs for the digraph maps because of the lack of
2.23 - ///template typedefs in C++.
2.24 -#define GRAPH_TYPEDEFS(Digraph) \
2.25 - typedef Digraph:: Node Node; \
2.26 - typedef Digraph:: NodeIt NodeIt; \
2.27 - typedef Digraph:: Arc Arc; \
2.28 - typedef Digraph:: ArcIt ArcIt; \
2.29 - typedef Digraph:: InArcIt InArcIt; \
2.30 - typedef Digraph::OutArcIt OutArcIt
2.31 + ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
2.32 + ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
2.33 +#define DIGRAPH_TYPEDEFS(Digraph) \
2.34 + typedef Digraph::Node Node; \
2.35 + typedef Digraph::NodeIt NodeIt; \
2.36 + typedef Digraph::Arc Arc; \
2.37 + typedef Digraph::ArcIt ArcIt; \
2.38 + typedef Digraph::InArcIt InArcIt; \
2.39 + typedef Digraph::OutArcIt OutArcIt
2.40
2.41 ///Creates convenience typedefs for the graph types and iterators
2.42
2.43 - ///This \c \#define creates the same convenience typedefs as defined by
2.44 - ///\ref GRAPH_TYPEDEFS(Digraph) and three more, namely it creates
2.45 - ///\c Edge, \c EdgeIt, \c IncArcIt,
2.46 + ///This \c \#define creates the same convenience typedefs as defined
2.47 + ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
2.48 + ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
2.49 + ///\c DoubleEdgeMap.
2.50 +#define GRAPH_TYPEDEFS(Graph) \
2.51 + DIGRAPH_TYPEDEFS(Graph); \
2.52 + typedef Graph::Edge Edge; \
2.53 + typedef Graph::EdgeIt EdgeIt; \
2.54 + typedef Graph::IncEdgeIt IncEdgeIt
2.55 +
2.56 + /// \brief Function to count the items in the graph.
2.57 ///
2.58 - ///\note If \c G it a template parameter, it should be used in this way.
2.59 - ///\code
2.60 - /// UGRAPH_TYPEDEFS(typename G);
2.61 - ///\endcode
2.62 - ///
2.63 - ///\warning There are no typedefs for the digraph maps because of the lack of
2.64 - ///template typedefs in C++.
2.65 -#define UGRAPH_TYPEDEFS(Digraph) \
2.66 - GRAPH_TYPEDEFS(Digraph); \
2.67 - typedef Digraph:: Edge Edge; \
2.68 - typedef Digraph:: EdgeIt EdgeIt; \
2.69 - typedef Digraph:: IncArcIt IncArcIt
2.70 -
2.71 - ///\brief Creates convenience typedefs for the bipartite digraph
2.72 - ///types and iterators
2.73 -
2.74 - ///This \c \#define creates the same convenience typedefs as defined by
2.75 - ///\ref UGRAPH_TYPEDEFS(Digraph) and two more, namely it creates
2.76 - ///\c RedIt, \c BlueIt,
2.77 - ///
2.78 - ///\note If \c G it a template parameter, it should be used in this way.
2.79 - ///\code
2.80 - /// BPUGRAPH_TYPEDEFS(typename G);
2.81 - ///\endcode
2.82 - ///
2.83 - ///\warning There are no typedefs for the digraph maps because of the lack of
2.84 - ///template typedefs in C++.
2.85 -#define BPUGRAPH_TYPEDEFS(Digraph) \
2.86 - UGRAPH_TYPEDEFS(Digraph); \
2.87 - typedef Digraph::Red Red; \
2.88 - typedef Digraph::Blue Blue; \
2.89 - typedef Digraph::RedIt RedIt; \
2.90 - typedef Digraph::BlueIt BlueIt
2.91 -
2.92 - /// \brief Function to count the items in the digraph.
2.93 - ///
2.94 - /// This function counts the items (nodes, arcs etc) in the digraph.
2.95 + /// This function counts the items (nodes, arcs etc) in the graph.
2.96 /// The complexity of the function is O(n) because
2.97 /// it iterates on all of the items.
2.98 -
2.99 - template <typename Digraph, typename Item>
2.100 - inline int countItems(const Digraph& g) {
2.101 - typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
2.102 + template <typename Graph, typename Item>
2.103 + inline int countItems(const Graph& g) {
2.104 + typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
2.105 int num = 0;
2.106 for (ItemIt it(g); it != INVALID; ++it) {
2.107 ++num;
2.108 @@ -120,184 +85,115 @@
2.109
2.110 // Node counting:
2.111
2.112 - namespace _digraph_utils_bits {
2.113 + namespace _graph_utils_bits {
2.114
2.115 - template <typename Digraph, typename Enable = void>
2.116 + template <typename Graph, typename Enable = void>
2.117 struct CountNodesSelector {
2.118 - static int count(const Digraph &g) {
2.119 - return countItems<Digraph, typename Digraph::Node>(g);
2.120 + static int count(const Graph &g) {
2.121 + return countItems<Graph, typename Graph::Node>(g);
2.122 }
2.123 };
2.124
2.125 - template <typename Digraph>
2.126 + template <typename Graph>
2.127 struct CountNodesSelector<
2.128 - Digraph, typename
2.129 - enable_if<typename Digraph::NodeNumTag, void>::type>
2.130 + Graph, typename
2.131 + enable_if<typename Graph::NodeNumTag, void>::type>
2.132 {
2.133 - static int count(const Digraph &g) {
2.134 + static int count(const Graph &g) {
2.135 return g.nodeNum();
2.136 }
2.137 };
2.138 }
2.139
2.140 - /// \brief Function to count the nodes in the digraph.
2.141 + /// \brief Function to count the nodes in the graph.
2.142 ///
2.143 - /// This function counts the nodes in the digraph.
2.144 + /// This function counts the nodes in the graph.
2.145 /// The complexity of the function is O(n) but for some
2.146 - /// digraph structures it is specialized to run in O(1).
2.147 + /// graph structures it is specialized to run in O(1).
2.148 ///
2.149 - /// If the digraph contains a \e nodeNum() member function and a
2.150 + /// If the graph contains a \e nodeNum() member function and a
2.151 /// \e NodeNumTag tag then this function calls directly the member
2.152 /// function to query the cardinality of the node set.
2.153 - template <typename Digraph>
2.154 - inline int countNodes(const Digraph& g) {
2.155 - return _digraph_utils_bits::CountNodesSelector<Digraph>::count(g);
2.156 + template <typename Graph>
2.157 + inline int countNodes(const Graph& g) {
2.158 + return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
2.159 }
2.160
2.161 - namespace _digraph_utils_bits {
2.162 + // Arc counting:
2.163 +
2.164 + namespace _graph_utils_bits {
2.165
2.166 - template <typename Digraph, typename Enable = void>
2.167 - struct CountRedsSelector {
2.168 - static int count(const Digraph &g) {
2.169 - return countItems<Digraph, typename Digraph::Red>(g);
2.170 + template <typename Graph, typename Enable = void>
2.171 + struct CountArcsSelector {
2.172 + static int count(const Graph &g) {
2.173 + return countItems<Graph, typename Graph::Arc>(g);
2.174 }
2.175 };
2.176
2.177 - template <typename Digraph>
2.178 - struct CountRedsSelector<
2.179 - Digraph, typename
2.180 - enable_if<typename Digraph::NodeNumTag, void>::type>
2.181 + template <typename Graph>
2.182 + struct CountArcsSelector<
2.183 + Graph,
2.184 + typename enable_if<typename Graph::ArcNumTag, void>::type>
2.185 {
2.186 - static int count(const Digraph &g) {
2.187 - return g.redNum();
2.188 - }
2.189 - };
2.190 - }
2.191 -
2.192 - /// \brief Function to count the reds in the digraph.
2.193 - ///
2.194 - /// This function counts the reds in the digraph.
2.195 - /// The complexity of the function is O(an) but for some
2.196 - /// digraph structures it is specialized to run in O(1).
2.197 - ///
2.198 - /// If the digraph contains an \e redNum() member function and a
2.199 - /// \e NodeNumTag tag then this function calls directly the member
2.200 - /// function to query the cardinality of the A-node set.
2.201 - template <typename Digraph>
2.202 - inline int countReds(const Digraph& g) {
2.203 - return _digraph_utils_bits::CountRedsSelector<Digraph>::count(g);
2.204 - }
2.205 -
2.206 - namespace _digraph_utils_bits {
2.207 -
2.208 - template <typename Digraph, typename Enable = void>
2.209 - struct CountBluesSelector {
2.210 - static int count(const Digraph &g) {
2.211 - return countItems<Digraph, typename Digraph::Blue>(g);
2.212 - }
2.213 - };
2.214 -
2.215 - template <typename Digraph>
2.216 - struct CountBluesSelector<
2.217 - Digraph, typename
2.218 - enable_if<typename Digraph::NodeNumTag, void>::type>
2.219 - {
2.220 - static int count(const Digraph &g) {
2.221 - return g.blueNum();
2.222 - }
2.223 - };
2.224 - }
2.225 -
2.226 - /// \brief Function to count the blues in the digraph.
2.227 - ///
2.228 - /// This function counts the blues in the digraph.
2.229 - /// The complexity of the function is O(bn) but for some
2.230 - /// digraph structures it is specialized to run in O(1).
2.231 - ///
2.232 - /// If the digraph contains a \e blueNum() member function and a
2.233 - /// \e NodeNumTag tag then this function calls directly the member
2.234 - /// function to query the cardinality of the B-node set.
2.235 - template <typename Digraph>
2.236 - inline int countBlues(const Digraph& g) {
2.237 - return _digraph_utils_bits::CountBluesSelector<Digraph>::count(g);
2.238 - }
2.239 -
2.240 -
2.241 - // Arc counting:
2.242 -
2.243 - namespace _digraph_utils_bits {
2.244 -
2.245 - template <typename Digraph, typename Enable = void>
2.246 - struct CountArcsSelector {
2.247 - static int count(const Digraph &g) {
2.248 - return countItems<Digraph, typename Digraph::Arc>(g);
2.249 - }
2.250 - };
2.251 -
2.252 - template <typename Digraph>
2.253 - struct CountArcsSelector<
2.254 - Digraph,
2.255 - typename enable_if<typename Digraph::ArcNumTag, void>::type>
2.256 - {
2.257 - static int count(const Digraph &g) {
2.258 + static int count(const Graph &g) {
2.259 return g.arcNum();
2.260 }
2.261 };
2.262 }
2.263
2.264 - /// \brief Function to count the arcs in the digraph.
2.265 + /// \brief Function to count the arcs in the graph.
2.266 ///
2.267 - /// This function counts the arcs in the digraph.
2.268 + /// This function counts the arcs in the graph.
2.269 /// The complexity of the function is O(e) but for some
2.270 - /// digraph structures it is specialized to run in O(1).
2.271 + /// graph structures it is specialized to run in O(1).
2.272 ///
2.273 - /// If the digraph contains a \e arcNum() member function and a
2.274 - /// \e ArcNumTag tag then this function calls directly the member
2.275 + /// If the graph contains a \e arcNum() member function and a
2.276 + /// \e EdgeNumTag tag then this function calls directly the member
2.277 /// function to query the cardinality of the arc set.
2.278 - template <typename Digraph>
2.279 - inline int countArcs(const Digraph& g) {
2.280 - return _digraph_utils_bits::CountArcsSelector<Digraph>::count(g);
2.281 + template <typename Graph>
2.282 + inline int countArcs(const Graph& g) {
2.283 + return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
2.284 }
2.285
2.286 - // Undirected arc counting:
2.287 - namespace _digraph_utils_bits {
2.288 + // Edge counting:
2.289 + namespace _graph_utils_bits {
2.290
2.291 - template <typename Digraph, typename Enable = void>
2.292 + template <typename Graph, typename Enable = void>
2.293 struct CountEdgesSelector {
2.294 - static int count(const Digraph &g) {
2.295 - return countItems<Digraph, typename Digraph::Edge>(g);
2.296 + static int count(const Graph &g) {
2.297 + return countItems<Graph, typename Graph::Edge>(g);
2.298 }
2.299 };
2.300
2.301 - template <typename Digraph>
2.302 + template <typename Graph>
2.303 struct CountEdgesSelector<
2.304 - Digraph,
2.305 - typename enable_if<typename Digraph::ArcNumTag, void>::type>
2.306 + Graph,
2.307 + typename enable_if<typename Graph::EdgeNumTag, void>::type>
2.308 {
2.309 - static int count(const Digraph &g) {
2.310 + static int count(const Graph &g) {
2.311 return g.edgeNum();
2.312 }
2.313 };
2.314 }
2.315
2.316 - /// \brief Function to count the edges in the digraph.
2.317 + /// \brief Function to count the edges in the graph.
2.318 ///
2.319 - /// This function counts the edges in the digraph.
2.320 - /// The complexity of the function is O(e) but for some
2.321 - /// digraph structures it is specialized to run in O(1).
2.322 + /// This function counts the edges in the graph.
2.323 + /// The complexity of the function is O(m) but for some
2.324 + /// graph structures it is specialized to run in O(1).
2.325 ///
2.326 - /// If the digraph contains a \e edgeNum() member function and a
2.327 - /// \e ArcNumTag tag then this function calls directly the member
2.328 + /// If the graph contains a \e edgeNum() member function and a
2.329 + /// \e EdgeNumTag tag then this function calls directly the member
2.330 /// function to query the cardinality of the edge set.
2.331 - template <typename Digraph>
2.332 - inline int countEdges(const Digraph& g) {
2.333 - return _digraph_utils_bits::CountEdgesSelector<Digraph>::count(g);
2.334 + template <typename Graph>
2.335 + inline int countEdges(const Graph& g) {
2.336 + return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
2.337
2.338 }
2.339
2.340
2.341 - template <typename Digraph, typename DegIt>
2.342 - inline int countNodeDegree(const Digraph& _g, const typename Digraph::Node& _n) {
2.343 + template <typename Graph, typename DegIt>
2.344 + inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
2.345 int num = 0;
2.346 for (DegIt it(_g, _n); it != INVALID; ++it) {
2.347 ++num;
2.348 @@ -308,37 +204,37 @@
2.349 /// \brief Function to count the number of the out-arcs from node \c n.
2.350 ///
2.351 /// This function counts the number of the out-arcs from node \c n
2.352 - /// in the digraph.
2.353 - template <typename Digraph>
2.354 - inline int countOutArcs(const Digraph& _g, const typename Digraph::Node& _n) {
2.355 - return countNodeDegree<Digraph, typename Digraph::OutArcIt>(_g, _n);
2.356 + /// in the graph.
2.357 + template <typename Graph>
2.358 + inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {
2.359 + return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
2.360 }
2.361
2.362 /// \brief Function to count the number of the in-arcs to node \c n.
2.363 ///
2.364 /// This function counts the number of the in-arcs to node \c n
2.365 - /// in the digraph.
2.366 - template <typename Digraph>
2.367 - inline int countInArcs(const Digraph& _g, const typename Digraph::Node& _n) {
2.368 - return countNodeDegree<Digraph, typename Digraph::InArcIt>(_g, _n);
2.369 + /// in the graph.
2.370 + template <typename Graph>
2.371 + inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {
2.372 + return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
2.373 }
2.374
2.375 - /// \brief Function to count the number of the inc-arcs to node \c n.
2.376 + /// \brief Function to count the number of the inc-edges to node \c n.
2.377 ///
2.378 - /// This function counts the number of the inc-arcs to node \c n
2.379 - /// in the digraph.
2.380 - template <typename Digraph>
2.381 - inline int countIncArcs(const Digraph& _g, const typename Digraph::Node& _n) {
2.382 - return countNodeDegree<Digraph, typename Digraph::IncArcIt>(_g, _n);
2.383 + /// This function counts the number of the inc-edges to node \c n
2.384 + /// in the graph.
2.385 + template <typename Graph>
2.386 + inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
2.387 + return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
2.388 }
2.389
2.390 - namespace _digraph_utils_bits {
2.391 + namespace _graph_utils_bits {
2.392
2.393 - template <typename Digraph, typename Enable = void>
2.394 + template <typename Graph, typename Enable = void>
2.395 struct FindArcSelector {
2.396 - typedef typename Digraph::Node Node;
2.397 - typedef typename Digraph::Arc Arc;
2.398 - static Arc find(const Digraph &g, Node u, Node v, Arc e) {
2.399 + typedef typename Graph::Node Node;
2.400 + typedef typename Graph::Arc Arc;
2.401 + static Arc find(const Graph &g, Node u, Node v, Arc e) {
2.402 if (e == INVALID) {
2.403 g.firstOut(e, u);
2.404 } else {
2.405 @@ -351,22 +247,22 @@
2.406 }
2.407 };
2.408
2.409 - template <typename Digraph>
2.410 + template <typename Graph>
2.411 struct FindArcSelector<
2.412 - Digraph,
2.413 - typename enable_if<typename Digraph::FindArcTag, void>::type>
2.414 + Graph,
2.415 + typename enable_if<typename Graph::FindEdgeTag, void>::type>
2.416 {
2.417 - typedef typename Digraph::Node Node;
2.418 - typedef typename Digraph::Arc Arc;
2.419 - static Arc find(const Digraph &g, Node u, Node v, Arc prev) {
2.420 + typedef typename Graph::Node Node;
2.421 + typedef typename Graph::Arc Arc;
2.422 + static Arc find(const Graph &g, Node u, Node v, Arc prev) {
2.423 return g.findArc(u, v, prev);
2.424 }
2.425 };
2.426 }
2.427
2.428 - /// \brief Finds an arc between two nodes of a digraph.
2.429 + /// \brief Finds an arc between two nodes of a graph.
2.430 ///
2.431 - /// Finds an arc from node \c u to node \c v in digraph \c g.
2.432 + /// Finds an arc from node \c u to node \c v in graph \c g.
2.433 ///
2.434 /// If \c prev is \ref INVALID (this is the default value), then
2.435 /// it finds the first arc from \c u to \c v. Otherwise it looks for
2.436 @@ -384,11 +280,11 @@
2.437 ///\sa AllArcLookUp
2.438 ///\sa DynArcLookUp
2.439 ///\sa ConArcIt
2.440 - template <typename Digraph>
2.441 - inline typename Digraph::Arc
2.442 - findArc(const Digraph &g, typename Digraph::Node u, typename Digraph::Node v,
2.443 - typename Digraph::Arc prev = INVALID) {
2.444 - return _digraph_utils_bits::FindArcSelector<Digraph>::find(g, u, v, prev);
2.445 + template <typename Graph>
2.446 + inline typename Graph::Arc
2.447 + findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
2.448 + typename Graph::Arc prev = INVALID) {
2.449 + return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
2.450 }
2.451
2.452 /// \brief Iterator for iterating on arcs connected the same nodes.
2.453 @@ -397,7 +293,7 @@
2.454 /// higher level interface for the findArc() function. You can
2.455 /// use it the following way:
2.456 ///\code
2.457 - /// for (ConArcIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
2.458 + /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
2.459 /// ...
2.460 /// }
2.461 ///\endcode
2.462 @@ -408,49 +304,49 @@
2.463 ///\sa DynArcLookUp
2.464 ///
2.465 /// \author Balazs Dezso
2.466 - template <typename _Digraph>
2.467 - class ConArcIt : public _Digraph::Arc {
2.468 + template <typename _Graph>
2.469 + class ConArcIt : public _Graph::Arc {
2.470 public:
2.471
2.472 - typedef _Digraph Digraph;
2.473 - typedef typename Digraph::Arc Parent;
2.474 + typedef _Graph Graph;
2.475 + typedef typename Graph::Arc Parent;
2.476
2.477 - typedef typename Digraph::Arc Arc;
2.478 - typedef typename Digraph::Node Node;
2.479 + typedef typename Graph::Arc Arc;
2.480 + typedef typename Graph::Node Node;
2.481
2.482 /// \brief Constructor.
2.483 ///
2.484 /// Construct a new ConArcIt iterating on the arcs which
2.485 /// connects the \c u and \c v node.
2.486 - ConArcIt(const Digraph& g, Node u, Node v) : digraph(g) {
2.487 - Parent::operator=(findArc(digraph, u, v));
2.488 + ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
2.489 + Parent::operator=(findArc(_graph, u, v));
2.490 }
2.491
2.492 /// \brief Constructor.
2.493 ///
2.494 /// Construct a new ConArcIt which continues the iterating from
2.495 /// the \c e arc.
2.496 - ConArcIt(const Digraph& g, Arc e) : Parent(e), digraph(g) {}
2.497 + ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
2.498
2.499 /// \brief Increment operator.
2.500 ///
2.501 /// It increments the iterator and gives back the next arc.
2.502 ConArcIt& operator++() {
2.503 - Parent::operator=(findArc(digraph, digraph.source(*this),
2.504 - digraph.target(*this), *this));
2.505 + Parent::operator=(findArc(_graph, _graph.source(*this),
2.506 + _graph.target(*this), *this));
2.507 return *this;
2.508 }
2.509 private:
2.510 - const Digraph& digraph;
2.511 + const Graph& _graph;
2.512 };
2.513
2.514 - namespace _digraph_utils_bits {
2.515 + namespace _graph_utils_bits {
2.516
2.517 - template <typename Digraph, typename Enable = void>
2.518 + template <typename Graph, typename Enable = void>
2.519 struct FindEdgeSelector {
2.520 - typedef typename Digraph::Node Node;
2.521 - typedef typename Digraph::Edge Edge;
2.522 - static Edge find(const Digraph &g, Node u, Node v, Edge e) {
2.523 + typedef typename Graph::Node Node;
2.524 + typedef typename Graph::Edge Edge;
2.525 + static Edge find(const Graph &g, Node u, Node v, Edge e) {
2.526 bool b;
2.527 if (u != v) {
2.528 if (e == INVALID) {
2.529 @@ -477,24 +373,24 @@
2.530 }
2.531 };
2.532
2.533 - template <typename Digraph>
2.534 + template <typename Graph>
2.535 struct FindEdgeSelector<
2.536 - Digraph,
2.537 - typename enable_if<typename Digraph::FindArcTag, void>::type>
2.538 + Graph,
2.539 + typename enable_if<typename Graph::FindEdgeTag, void>::type>
2.540 {
2.541 - typedef typename Digraph::Node Node;
2.542 - typedef typename Digraph::Edge Edge;
2.543 - static Edge find(const Digraph &g, Node u, Node v, Edge prev) {
2.544 + typedef typename Graph::Node Node;
2.545 + typedef typename Graph::Edge Edge;
2.546 + static Edge find(const Graph &g, Node u, Node v, Edge prev) {
2.547 return g.findEdge(u, v, prev);
2.548 }
2.549 };
2.550 }
2.551
2.552 - /// \brief Finds an edge between two nodes of a digraph.
2.553 + /// \brief Finds an edge between two nodes of a graph.
2.554 ///
2.555 - /// Finds an edge from node \c u to node \c v in digraph \c g.
2.556 - /// If the node \c u and node \c v is equal then each loop arc
2.557 - /// will be enumerated.
2.558 + /// Finds an edge from node \c u to node \c v in graph \c g.
2.559 + /// If the node \c u and node \c v is equal then each loop edge
2.560 + /// will be enumerated once.
2.561 ///
2.562 /// If \c prev is \ref INVALID (this is the default value), then
2.563 /// it finds the first arc from \c u to \c v. Otherwise it looks for
2.564 @@ -511,11 +407,11 @@
2.565 ///
2.566 ///\sa ConArcIt
2.567
2.568 - template <typename Digraph>
2.569 - inline typename Digraph::Edge
2.570 - findEdge(const Digraph &g, typename Digraph::Node u, typename Digraph::Node v,
2.571 - typename Digraph::Edge p = INVALID) {
2.572 - return _digraph_utils_bits::FindEdgeSelector<Digraph>::find(g, u, v, p);
2.573 + template <typename Graph>
2.574 + inline typename Graph::Edge
2.575 + findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
2.576 + typename Graph::Edge p = INVALID) {
2.577 + return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
2.578 }
2.579
2.580 /// \brief Iterator for iterating on edges connected the same nodes.
2.581 @@ -524,7 +420,7 @@
2.582 /// higher level interface for the findEdge() function. You can
2.583 /// use it the following way:
2.584 ///\code
2.585 - /// for (ConEdgeIt<Digraph> it(g, src, trg); it != INVALID; ++it) {
2.586 + /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
2.587 /// ...
2.588 /// }
2.589 ///\endcode
2.590 @@ -532,68 +428,43 @@
2.591 ///\sa findEdge()
2.592 ///
2.593 /// \author Balazs Dezso
2.594 - template <typename _Digraph>
2.595 - class ConEdgeIt : public _Digraph::Edge {
2.596 + template <typename _Graph>
2.597 + class ConEdgeIt : public _Graph::Edge {
2.598 public:
2.599
2.600 - typedef _Digraph Digraph;
2.601 - typedef typename Digraph::Edge Parent;
2.602 + typedef _Graph Graph;
2.603 + typedef typename Graph::Edge Parent;
2.604
2.605 - typedef typename Digraph::Edge Edge;
2.606 - typedef typename Digraph::Node Node;
2.607 + typedef typename Graph::Edge Edge;
2.608 + typedef typename Graph::Node Node;
2.609
2.610 /// \brief Constructor.
2.611 ///
2.612 - /// Construct a new ConEdgeIt iterating on the arcs which
2.613 + /// Construct a new ConEdgeIt iterating on the edges which
2.614 /// connects the \c u and \c v node.
2.615 - ConEdgeIt(const Digraph& g, Node u, Node v) : digraph(g) {
2.616 - Parent::operator=(findEdge(digraph, u, v));
2.617 + ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
2.618 + Parent::operator=(findEdge(_graph, u, v));
2.619 }
2.620
2.621 /// \brief Constructor.
2.622 ///
2.623 /// Construct a new ConEdgeIt which continues the iterating from
2.624 - /// the \c e arc.
2.625 - ConEdgeIt(const Digraph& g, Edge e) : Parent(e), digraph(g) {}
2.626 + /// the \c e edge.
2.627 + ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
2.628
2.629 /// \brief Increment operator.
2.630 ///
2.631 - /// It increments the iterator and gives back the next arc.
2.632 + /// It increments the iterator and gives back the next edge.
2.633 ConEdgeIt& operator++() {
2.634 - Parent::operator=(findEdge(digraph, digraph.source(*this),
2.635 - digraph.target(*this), *this));
2.636 + Parent::operator=(findEdge(_graph, _graph.source(*this),
2.637 + _graph.target(*this), *this));
2.638 return *this;
2.639 }
2.640 private:
2.641 - const Digraph& digraph;
2.642 + const Graph& _graph;
2.643 };
2.644
2.645 - /// \brief Copy a map.
2.646 - ///
2.647 - /// This function copies the \c from map to the \c to map. It uses the
2.648 - /// given iterator to iterate on the data structure and it uses the \c ref
2.649 - /// mapping to convert the from's keys to the to's keys.
2.650 - template <typename To, typename From,
2.651 - typename ItemIt, typename Ref>
2.652 - void copyMap(To& to, const From& from,
2.653 - ItemIt it, const Ref& ref) {
2.654 - for (; it != INVALID; ++it) {
2.655 - to[ref[it]] = from[it];
2.656 - }
2.657 - }
2.658 -
2.659 - /// \brief Copy the from map to the to map.
2.660 - ///
2.661 - /// Copy the \c from map to the \c to map. It uses the given iterator
2.662 - /// to iterate on the data structure.
2.663 - template <typename To, typename From, typename ItemIt>
2.664 - void copyMap(To& to, const From& from, ItemIt it) {
2.665 - for (; it != INVALID; ++it) {
2.666 - to[it] = from[it];
2.667 - }
2.668 - }
2.669 -
2.670 - namespace _digraph_utils_bits {
2.671 + namespace _graph_utils_bits {
2.672
2.673 template <typename Digraph, typename Item, typename RefMap>
2.674 class MapCopyBase {
2.675 @@ -727,47 +598,43 @@
2.676 }
2.677 };
2.678
2.679 - template <typename BpGraph, typename Enable = void>
2.680 - struct BpGraphCopySelector {
2.681 - template <typename From, typename RedRefMap,
2.682 - typename BlueRefMap, typename EdgeRefMap>
2.683 - static void copy(BpGraph &to, const From& from,
2.684 - RedRefMap& redRefMap, BlueRefMap& blueRefMap,
2.685 - EdgeRefMap& edgeRefMap) {
2.686 - for (typename From::RedIt it(from); it != INVALID; ++it) {
2.687 - redRefMap[it] = to.addRed();
2.688 - }
2.689 - for (typename From::BlueIt it(from); it != INVALID; ++it) {
2.690 - blueRefMap[it] = to.addBlue();
2.691 - }
2.692 - for (typename From::EdgeIt it(from); it != INVALID; ++it) {
2.693 - edgeRefMap[it] = to.addArc(redRefMap[from.red(it)],
2.694 - blueRefMap[from.blue(it)]);
2.695 - }
2.696 - }
2.697 - };
2.698 -
2.699 - template <typename BpGraph>
2.700 - struct BpGraphCopySelector<
2.701 - BpGraph,
2.702 - typename enable_if<typename BpGraph::BuildTag, void>::type>
2.703 - {
2.704 - template <typename From, typename RedRefMap,
2.705 - typename BlueRefMap, typename EdgeRefMap>
2.706 - static void copy(BpGraph &to, const From& from,
2.707 - RedRefMap& redRefMap, BlueRefMap& blueRefMap,
2.708 - EdgeRefMap& edgeRefMap) {
2.709 - to.build(from, redRefMap, blueRefMap, edgeRefMap);
2.710 - }
2.711 - };
2.712 -
2.713 -
2.714 }
2.715
2.716 /// \brief Class to copy a digraph.
2.717 ///
2.718 /// Class to copy a digraph to another digraph (duplicate a digraph). The
2.719 /// simplest way of using it is through the \c copyDigraph() function.
2.720 + ///
2.721 + /// This class not just make a copy of a graph, but it can create
2.722 + /// references and cross references between the nodes and arcs of
2.723 + /// the two graphs, it can copy maps for use with the newly created
2.724 + /// graph and copy nodes and arcs.
2.725 + ///
2.726 + /// To make a copy from a graph, first an instance of DigraphCopy
2.727 + /// should be created, then the data belongs to the graph should
2.728 + /// assigned to copy. In the end, the \c run() member should be
2.729 + /// called.
2.730 + ///
2.731 + /// The next code copies a graph with several data:
2.732 + ///\code
2.733 + /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
2.734 + /// // create a reference for the nodes
2.735 + /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
2.736 + /// dc.nodeRef(nr);
2.737 + /// // create a cross reference (inverse) for the arcs
2.738 + /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
2.739 + /// dc.arcCrossRef(acr);
2.740 + /// // copy an arc map
2.741 + /// OrigGraph::ArcMap<double> oamap(orig_graph);
2.742 + /// NewGraph::ArcMap<double> namap(new_graph);
2.743 + /// dc.arcMap(namap, oamap);
2.744 + /// // copy a node
2.745 + /// OrigGraph::Node on;
2.746 + /// NewGraph::Node nn;
2.747 + /// dc.node(nn, on);
2.748 + /// // Executions of copy
2.749 + /// dc.run();
2.750 + ///\endcode
2.751 template <typename To, typename From>
2.752 class DigraphCopy {
2.753 private:
2.754 @@ -791,53 +658,57 @@
2.755 ///
2.756 /// It copies the content of the \c _from digraph into the
2.757 /// \c _to digraph.
2.758 - DigraphCopy(To& _to, const From& _from)
2.759 - : from(_from), to(_to) {}
2.760 + DigraphCopy(To& to, const From& from)
2.761 + : _from(from), _to(to) {}
2.762
2.763 /// \brief Destructor of the DigraphCopy
2.764 ///
2.765 /// Destructor of the DigraphCopy
2.766 ~DigraphCopy() {
2.767 - for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
2.768 - delete nodeMapCopies[i];
2.769 + for (int i = 0; i < int(_node_maps.size()); ++i) {
2.770 + delete _node_maps[i];
2.771 }
2.772 - for (int i = 0; i < int(arcMapCopies.size()); ++i) {
2.773 - delete arcMapCopies[i];
2.774 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
2.775 + delete _arc_maps[i];
2.776 }
2.777
2.778 }
2.779
2.780 /// \brief Copies the node references into the given map.
2.781 ///
2.782 - /// Copies the node references into the given map.
2.783 + /// Copies the node references into the given map. The parameter
2.784 + /// should be a map, which key type is the Node type of the source
2.785 + /// graph, while the value type is the Node type of the
2.786 + /// destination graph.
2.787 template <typename NodeRef>
2.788 DigraphCopy& nodeRef(NodeRef& map) {
2.789 - nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
2.790 - NodeRefMap, NodeRef>(map));
2.791 + _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
2.792 + NodeRefMap, NodeRef>(map));
2.793 return *this;
2.794 }
2.795
2.796 /// \brief Copies the node cross references into the given map.
2.797 ///
2.798 /// Copies the node cross references (reverse references) into
2.799 - /// the given map.
2.800 + /// the given map. The parameter should be a map, which key type
2.801 + /// is the Node type of the destination graph, while the value type is
2.802 + /// the Node type of the source graph.
2.803 template <typename NodeCrossRef>
2.804 DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
2.805 - nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
2.806 - NodeRefMap, NodeCrossRef>(map));
2.807 + _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
2.808 + NodeRefMap, NodeCrossRef>(map));
2.809 return *this;
2.810 }
2.811
2.812 /// \brief Make copy of the given map.
2.813 ///
2.814 - /// Makes copy of the given map for the newly created digraph.
2.815 - /// The new map's key type is the to digraph's node type,
2.816 - /// and the copied map's key type is the from digraph's node
2.817 - /// type.
2.818 + /// Makes copy of the given map for the newly created digraph.
2.819 + /// The new map's key type is the destination graph's node type,
2.820 + /// and the copied map's key type is the source graph's node type.
2.821 template <typename ToMap, typename FromMap>
2.822 DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
2.823 - nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
2.824 - NodeRefMap, ToMap, FromMap>(tmap, map));
2.825 + _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
2.826 + NodeRefMap, ToMap, FromMap>(tmap, map));
2.827 return *this;
2.828 }
2.829
2.830 @@ -845,8 +716,8 @@
2.831 ///
2.832 /// Make a copy of the given node.
2.833 DigraphCopy& node(TNode& tnode, const Node& snode) {
2.834 - nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
2.835 - NodeRefMap, TNode>(tnode, snode));
2.836 + _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
2.837 + NodeRefMap, TNode>(tnode, snode));
2.838 return *this;
2.839 }
2.840
2.841 @@ -855,8 +726,8 @@
2.842 /// Copies the arc references into the given map.
2.843 template <typename ArcRef>
2.844 DigraphCopy& arcRef(ArcRef& map) {
2.845 - arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
2.846 - ArcRefMap, ArcRef>(map));
2.847 + _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
2.848 + ArcRefMap, ArcRef>(map));
2.849 return *this;
2.850 }
2.851
2.852 @@ -866,8 +737,8 @@
2.853 /// the given map.
2.854 template <typename ArcCrossRef>
2.855 DigraphCopy& arcCrossRef(ArcCrossRef& map) {
2.856 - arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
2.857 - ArcRefMap, ArcCrossRef>(map));
2.858 + _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
2.859 + ArcRefMap, ArcCrossRef>(map));
2.860 return *this;
2.861 }
2.862
2.863 @@ -879,8 +750,8 @@
2.864 /// type.
2.865 template <typename ToMap, typename FromMap>
2.866 DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
2.867 - arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
2.868 - ArcRefMap, ToMap, FromMap>(tmap, map));
2.869 + _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
2.870 + ArcRefMap, ToMap, FromMap>(tmap, map));
2.871 return *this;
2.872 }
2.873
2.874 @@ -888,8 +759,8 @@
2.875 ///
2.876 /// Make a copy of the given arc.
2.877 DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
2.878 - arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
2.879 - ArcRefMap, TArc>(tarc, sarc));
2.880 + _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
2.881 + ArcRefMap, TArc>(tarc, sarc));
2.882 return *this;
2.883 }
2.884
2.885 @@ -897,37 +768,37 @@
2.886 ///
2.887 /// Executes the copies.
2.888 void run() {
2.889 - NodeRefMap nodeRefMap(from);
2.890 - ArcRefMap arcRefMap(from);
2.891 - _digraph_utils_bits::DigraphCopySelector<To>::
2.892 - copy(to, from, nodeRefMap, arcRefMap);
2.893 - for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
2.894 - nodeMapCopies[i]->copy(from, nodeRefMap);
2.895 + NodeRefMap nodeRefMap(_from);
2.896 + ArcRefMap arcRefMap(_from);
2.897 + _graph_utils_bits::DigraphCopySelector<To>::
2.898 + copy(_to, _from, nodeRefMap, arcRefMap);
2.899 + for (int i = 0; i < int(_node_maps.size()); ++i) {
2.900 + _node_maps[i]->copy(_from, nodeRefMap);
2.901 }
2.902 - for (int i = 0; i < int(arcMapCopies.size()); ++i) {
2.903 - arcMapCopies[i]->copy(from, arcRefMap);
2.904 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
2.905 + _arc_maps[i]->copy(_from, arcRefMap);
2.906 }
2.907 }
2.908
2.909 protected:
2.910
2.911
2.912 - const From& from;
2.913 - To& to;
2.914 + const From& _from;
2.915 + To& _to;
2.916
2.917 - std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
2.918 - nodeMapCopies;
2.919 + std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
2.920 + _node_maps;
2.921
2.922 - std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
2.923 - arcMapCopies;
2.924 + std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
2.925 + _arc_maps;
2.926
2.927 };
2.928
2.929 /// \brief Copy a digraph to another digraph.
2.930 ///
2.931 - /// Copy a digraph to another digraph.
2.932 - /// The usage of the function:
2.933 - ///
2.934 + /// Copy a digraph to another digraph. The complete usage of the
2.935 + /// function is detailed in the DigraphCopy class, but a short
2.936 + /// example shows a basic work:
2.937 ///\code
2.938 /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
2.939 ///\endcode
2.940 @@ -943,10 +814,41 @@
2.941 return DigraphCopy<To, From>(to, from);
2.942 }
2.943
2.944 - /// \brief Class to copy an graph.
2.945 + /// \brief Class to copy a graph.
2.946 ///
2.947 - /// Class to copy an graph to another digraph (duplicate a digraph).
2.948 - /// The simplest way of using it is through the \c copyGraph() function.
2.949 + /// Class to copy a graph to another graph (duplicate a graph). The
2.950 + /// simplest way of using it is through the \c copyGraph() function.
2.951 + ///
2.952 + /// This class not just make a copy of a graph, but it can create
2.953 + /// references and cross references between the nodes, edges and arcs of
2.954 + /// the two graphs, it can copy maps for use with the newly created
2.955 + /// graph and copy nodes, edges and arcs.
2.956 + ///
2.957 + /// To make a copy from a graph, first an instance of GraphCopy
2.958 + /// should be created, then the data belongs to the graph should
2.959 + /// assigned to copy. In the end, the \c run() member should be
2.960 + /// called.
2.961 + ///
2.962 + /// The next code copies a graph with several data:
2.963 + ///\code
2.964 + /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
2.965 + /// // create a reference for the nodes
2.966 + /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
2.967 + /// dc.nodeRef(nr);
2.968 + /// // create a cross reference (inverse) for the edges
2.969 + /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
2.970 + /// dc.edgeCrossRef(ecr);
2.971 + /// // copy an arc map
2.972 + /// OrigGraph::ArcMap<double> oamap(orig_graph);
2.973 + /// NewGraph::ArcMap<double> namap(new_graph);
2.974 + /// dc.arcMap(namap, oamap);
2.975 + /// // copy a node
2.976 + /// OrigGraph::Node on;
2.977 + /// NewGraph::Node nn;
2.978 + /// dc.node(nn, on);
2.979 + /// // Executions of copy
2.980 + /// dc.run();
2.981 + ///\endcode
2.982 template <typename To, typename From>
2.983 class GraphCopy {
2.984 private:
2.985 @@ -966,51 +868,50 @@
2.986 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
2.987
2.988 struct ArcRefMap {
2.989 - ArcRefMap(const To& _to, const From& _from,
2.990 - const EdgeRefMap& _edge_ref, const NodeRefMap& _node_ref)
2.991 - : to(_to), from(_from),
2.992 - edge_ref(_edge_ref), node_ref(_node_ref) {}
2.993 + ArcRefMap(const To& to, const From& from,
2.994 + const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
2.995 + : _to(to), _from(from),
2.996 + _edge_ref(edge_ref), _node_ref(node_ref) {}
2.997
2.998 typedef typename From::Arc Key;
2.999 typedef typename To::Arc Value;
2.1000
2.1001 Value operator[](const Key& key) const {
2.1002 bool forward =
2.1003 - (from.direction(key) ==
2.1004 - (node_ref[from.source(static_cast<const Edge&>(key))] ==
2.1005 - to.source(edge_ref[static_cast<const Edge&>(key)])));
2.1006 - return to.direct(edge_ref[key], forward);
2.1007 + (_from.direction(key) ==
2.1008 + (_node_ref[_from.source(key)] == _to.source(_edge_ref[key])));
2.1009 + return _to.direct(_edge_ref[key], forward);
2.1010 }
2.1011
2.1012 - const To& to;
2.1013 - const From& from;
2.1014 - const EdgeRefMap& edge_ref;
2.1015 - const NodeRefMap& node_ref;
2.1016 + const To& _to;
2.1017 + const From& _from;
2.1018 + const EdgeRefMap& _edge_ref;
2.1019 + const NodeRefMap& _node_ref;
2.1020 };
2.1021
2.1022
2.1023 public:
2.1024
2.1025
2.1026 - /// \brief Constructor for the DigraphCopy.
2.1027 + /// \brief Constructor for the GraphCopy.
2.1028 ///
2.1029 - /// It copies the content of the \c _from digraph into the
2.1030 - /// \c _to digraph.
2.1031 - GraphCopy(To& _to, const From& _from)
2.1032 - : from(_from), to(_to) {}
2.1033 + /// It copies the content of the \c _from graph into the
2.1034 + /// \c _to graph.
2.1035 + GraphCopy(To& to, const From& from)
2.1036 + : _from(from), _to(to) {}
2.1037
2.1038 - /// \brief Destructor of the DigraphCopy
2.1039 + /// \brief Destructor of the GraphCopy
2.1040 ///
2.1041 - /// Destructor of the DigraphCopy
2.1042 + /// Destructor of the GraphCopy
2.1043 ~GraphCopy() {
2.1044 - for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
2.1045 - delete nodeMapCopies[i];
2.1046 + for (int i = 0; i < int(_node_maps.size()); ++i) {
2.1047 + delete _node_maps[i];
2.1048 }
2.1049 - for (int i = 0; i < int(arcMapCopies.size()); ++i) {
2.1050 - delete arcMapCopies[i];
2.1051 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
2.1052 + delete _arc_maps[i];
2.1053 }
2.1054 - for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
2.1055 - delete edgeMapCopies[i];
2.1056 + for (int i = 0; i < int(_edge_maps.size()); ++i) {
2.1057 + delete _edge_maps[i];
2.1058 }
2.1059
2.1060 }
2.1061 @@ -1020,8 +921,8 @@
2.1062 /// Copies the node references into the given map.
2.1063 template <typename NodeRef>
2.1064 GraphCopy& nodeRef(NodeRef& map) {
2.1065 - nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
2.1066 - NodeRefMap, NodeRef>(map));
2.1067 + _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
2.1068 + NodeRefMap, NodeRef>(map));
2.1069 return *this;
2.1070 }
2.1071
2.1072 @@ -1031,21 +932,21 @@
2.1073 /// the given map.
2.1074 template <typename NodeCrossRef>
2.1075 GraphCopy& nodeCrossRef(NodeCrossRef& map) {
2.1076 - nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
2.1077 - NodeRefMap, NodeCrossRef>(map));
2.1078 + _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
2.1079 + NodeRefMap, NodeCrossRef>(map));
2.1080 return *this;
2.1081 }
2.1082
2.1083 /// \brief Make copy of the given map.
2.1084 ///
2.1085 - /// Makes copy of the given map for the newly created digraph.
2.1086 - /// The new map's key type is the to digraph's node type,
2.1087 - /// and the copied map's key type is the from digraph's node
2.1088 + /// Makes copy of the given map for the newly created graph.
2.1089 + /// The new map's key type is the to graph's node type,
2.1090 + /// and the copied map's key type is the from graph's node
2.1091 /// type.
2.1092 template <typename ToMap, typename FromMap>
2.1093 GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
2.1094 - nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
2.1095 - NodeRefMap, ToMap, FromMap>(tmap, map));
2.1096 + _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
2.1097 + NodeRefMap, ToMap, FromMap>(tmap, map));
2.1098 return *this;
2.1099 }
2.1100
2.1101 @@ -1053,8 +954,8 @@
2.1102 ///
2.1103 /// Make a copy of the given node.
2.1104 GraphCopy& node(TNode& tnode, const Node& snode) {
2.1105 - nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
2.1106 - NodeRefMap, TNode>(tnode, snode));
2.1107 + _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
2.1108 + NodeRefMap, TNode>(tnode, snode));
2.1109 return *this;
2.1110 }
2.1111
2.1112 @@ -1063,8 +964,8 @@
2.1113 /// Copies the arc references into the given map.
2.1114 template <typename ArcRef>
2.1115 GraphCopy& arcRef(ArcRef& map) {
2.1116 - arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
2.1117 - ArcRefMap, ArcRef>(map));
2.1118 + _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
2.1119 + ArcRefMap, ArcRef>(map));
2.1120 return *this;
2.1121 }
2.1122
2.1123 @@ -1074,21 +975,21 @@
2.1124 /// the given map.
2.1125 template <typename ArcCrossRef>
2.1126 GraphCopy& arcCrossRef(ArcCrossRef& map) {
2.1127 - arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
2.1128 - ArcRefMap, ArcCrossRef>(map));
2.1129 + _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
2.1130 + ArcRefMap, ArcCrossRef>(map));
2.1131 return *this;
2.1132 }
2.1133
2.1134 /// \brief Make copy of the given map.
2.1135 ///
2.1136 - /// Makes copy of the given map for the newly created digraph.
2.1137 - /// The new map's key type is the to digraph's arc type,
2.1138 - /// and the copied map's key type is the from digraph's arc
2.1139 + /// Makes copy of the given map for the newly created graph.
2.1140 + /// The new map's key type is the to graph's arc type,
2.1141 + /// and the copied map's key type is the from graph's arc
2.1142 /// type.
2.1143 template <typename ToMap, typename FromMap>
2.1144 GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
2.1145 - arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
2.1146 - ArcRefMap, ToMap, FromMap>(tmap, map));
2.1147 + _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
2.1148 + ArcRefMap, ToMap, FromMap>(tmap, map));
2.1149 return *this;
2.1150 }
2.1151
2.1152 @@ -1096,8 +997,8 @@
2.1153 ///
2.1154 /// Make a copy of the given arc.
2.1155 GraphCopy& arc(TArc& tarc, const Arc& sarc) {
2.1156 - arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
2.1157 - ArcRefMap, TArc>(tarc, sarc));
2.1158 + _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
2.1159 + ArcRefMap, TArc>(tarc, sarc));
2.1160 return *this;
2.1161 }
2.1162
2.1163 @@ -1106,8 +1007,8 @@
2.1164 /// Copies the edge references into the given map.
2.1165 template <typename EdgeRef>
2.1166 GraphCopy& edgeRef(EdgeRef& map) {
2.1167 - edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,
2.1168 - EdgeRefMap, EdgeRef>(map));
2.1169 + _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
2.1170 + EdgeRefMap, EdgeRef>(map));
2.1171 return *this;
2.1172 }
2.1173
2.1174 @@ -1117,21 +1018,21 @@
2.1175 /// references) into the given map.
2.1176 template <typename EdgeCrossRef>
2.1177 GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
2.1178 - edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
2.1179 - Edge, EdgeRefMap, EdgeCrossRef>(map));
2.1180 + _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
2.1181 + Edge, EdgeRefMap, EdgeCrossRef>(map));
2.1182 return *this;
2.1183 }
2.1184
2.1185 /// \brief Make copy of the given map.
2.1186 ///
2.1187 - /// Makes copy of the given map for the newly created digraph.
2.1188 - /// The new map's key type is the to digraph's edge type,
2.1189 - /// and the copied map's key type is the from digraph's edge
2.1190 + /// Makes copy of the given map for the newly created graph.
2.1191 + /// The new map's key type is the to graph's edge type,
2.1192 + /// and the copied map's key type is the from graph's edge
2.1193 /// type.
2.1194 template <typename ToMap, typename FromMap>
2.1195 GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
2.1196 - edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,
2.1197 - EdgeRefMap, ToMap, FromMap>(tmap, map));
2.1198 + _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
2.1199 + EdgeRefMap, ToMap, FromMap>(tmap, map));
2.1200 return *this;
2.1201 }
2.1202
2.1203 @@ -1139,8 +1040,8 @@
2.1204 ///
2.1205 /// Make a copy of the given edge.
2.1206 GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
2.1207 - edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,
2.1208 - EdgeRefMap, TEdge>(tedge, sedge));
2.1209 + _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
2.1210 + EdgeRefMap, TEdge>(tedge, sedge));
2.1211 return *this;
2.1212 }
2.1213
2.1214 @@ -1148,51 +1049,51 @@
2.1215 ///
2.1216 /// Executes the copies.
2.1217 void run() {
2.1218 - NodeRefMap nodeRefMap(from);
2.1219 - EdgeRefMap edgeRefMap(from);
2.1220 - ArcRefMap arcRefMap(to, from, edgeRefMap, nodeRefMap);
2.1221 - _digraph_utils_bits::GraphCopySelector<To>::
2.1222 - copy(to, from, nodeRefMap, edgeRefMap);
2.1223 - for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
2.1224 - nodeMapCopies[i]->copy(from, nodeRefMap);
2.1225 + NodeRefMap nodeRefMap(_from);
2.1226 + EdgeRefMap edgeRefMap(_from);
2.1227 + ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
2.1228 + _graph_utils_bits::GraphCopySelector<To>::
2.1229 + copy(_to, _from, nodeRefMap, edgeRefMap);
2.1230 + for (int i = 0; i < int(_node_maps.size()); ++i) {
2.1231 + _node_maps[i]->copy(_from, nodeRefMap);
2.1232 }
2.1233 - for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
2.1234 - edgeMapCopies[i]->copy(from, edgeRefMap);
2.1235 + for (int i = 0; i < int(_edge_maps.size()); ++i) {
2.1236 + _edge_maps[i]->copy(_from, edgeRefMap);
2.1237 }
2.1238 - for (int i = 0; i < int(arcMapCopies.size()); ++i) {
2.1239 - arcMapCopies[i]->copy(from, arcRefMap);
2.1240 + for (int i = 0; i < int(_arc_maps.size()); ++i) {
2.1241 + _arc_maps[i]->copy(_from, arcRefMap);
2.1242 }
2.1243 }
2.1244
2.1245 private:
2.1246
2.1247 - const From& from;
2.1248 - To& to;
2.1249 + const From& _from;
2.1250 + To& _to;
2.1251
2.1252 - std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
2.1253 - nodeMapCopies;
2.1254 + std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
2.1255 + _node_maps;
2.1256
2.1257 - std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
2.1258 - arcMapCopies;
2.1259 + std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
2.1260 + _arc_maps;
2.1261
2.1262 - std::vector<_digraph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
2.1263 - edgeMapCopies;
2.1264 + std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
2.1265 + _edge_maps;
2.1266
2.1267 };
2.1268
2.1269 - /// \brief Copy an graph to another digraph.
2.1270 + /// \brief Copy a graph to another graph.
2.1271 ///
2.1272 - /// Copy an graph to another digraph.
2.1273 - /// The usage of the function:
2.1274 - ///
2.1275 + /// Copy a graph to another graph. The complete usage of the
2.1276 + /// function is detailed in the GraphCopy class, but a short
2.1277 + /// example shows a basic work:
2.1278 ///\code
2.1279 /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
2.1280 ///\endcode
2.1281 ///
2.1282 /// After the copy the \c nr map will contain the mapping from the
2.1283 - /// nodes of the \c from digraph to the nodes of the \c to digraph and
2.1284 - /// \c ecr will contain the mapping from the arcs of the \c to digraph
2.1285 - /// to the arcs of the \c from digraph.
2.1286 + /// nodes of the \c from graph to the nodes of the \c to graph and
2.1287 + /// \c ecr will contain the mapping from the arcs of the \c to graph
2.1288 + /// to the arcs of the \c from graph.
2.1289 ///
2.1290 /// \see GraphCopy
2.1291 template <typename To, typename From>
2.1292 @@ -1201,391 +1102,25 @@
2.1293 return GraphCopy<To, From>(to, from);
2.1294 }
2.1295
2.1296 - /// \brief Class to copy a bipartite digraph.
2.1297 - ///
2.1298 - /// Class to copy a bipartite digraph to another digraph
2.1299 - /// (duplicate a digraph). The simplest way of using it is through
2.1300 - /// the \c copyBpGraph() function.
2.1301 - template <typename To, typename From>
2.1302 - class BpGraphCopy {
2.1303 - private:
2.1304 -
2.1305 - typedef typename From::Node Node;
2.1306 - typedef typename From::Red Red;
2.1307 - typedef typename From::Blue Blue;
2.1308 - typedef typename From::NodeIt NodeIt;
2.1309 - typedef typename From::Arc Arc;
2.1310 - typedef typename From::ArcIt ArcIt;
2.1311 - typedef typename From::Edge Edge;
2.1312 - typedef typename From::EdgeIt EdgeIt;
2.1313 -
2.1314 - typedef typename To::Node TNode;
2.1315 - typedef typename To::Arc TArc;
2.1316 - typedef typename To::Edge TEdge;
2.1317 -
2.1318 - typedef typename From::template RedMap<TNode> RedRefMap;
2.1319 - typedef typename From::template BlueMap<TNode> BlueRefMap;
2.1320 - typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
2.1321 -
2.1322 - struct NodeRefMap {
2.1323 - NodeRefMap(const From& _from, const RedRefMap& _red_ref,
2.1324 - const BlueRefMap& _blue_ref)
2.1325 - : from(_from), red_ref(_red_ref), blue_ref(_blue_ref) {}
2.1326 -
2.1327 - typedef typename From::Node Key;
2.1328 - typedef typename To::Node Value;
2.1329 -
2.1330 - Value operator[](const Key& key) const {
2.1331 - return from.red(key) ? red_ref[key] : blue_ref[key];
2.1332 - }
2.1333 -
2.1334 - const From& from;
2.1335 - const RedRefMap& red_ref;
2.1336 - const BlueRefMap& blue_ref;
2.1337 - };
2.1338 -
2.1339 - struct ArcRefMap {
2.1340 - ArcRefMap(const To& _to, const From& _from,
2.1341 - const EdgeRefMap& _edge_ref, const NodeRefMap& _node_ref)
2.1342 - : to(_to), from(_from),
2.1343 - edge_ref(_edge_ref), node_ref(_node_ref) {}
2.1344 -
2.1345 - typedef typename From::Arc Key;
2.1346 - typedef typename To::Arc Value;
2.1347 -
2.1348 - Value operator[](const Key& key) const {
2.1349 - bool forward =
2.1350 - (from.direction(key) ==
2.1351 - (node_ref[from.source(static_cast<const Edge&>(key))] ==
2.1352 - to.source(edge_ref[static_cast<const Edge&>(key)])));
2.1353 - return to.direct(edge_ref[key], forward);
2.1354 - }
2.1355 -
2.1356 - const To& to;
2.1357 - const From& from;
2.1358 - const EdgeRefMap& edge_ref;
2.1359 - const NodeRefMap& node_ref;
2.1360 - };
2.1361 -
2.1362 - public:
2.1363 -
2.1364 -
2.1365 - /// \brief Constructor for the DigraphCopy.
2.1366 - ///
2.1367 - /// It copies the content of the \c _from digraph into the
2.1368 - /// \c _to digraph.
2.1369 - BpGraphCopy(To& _to, const From& _from)
2.1370 - : from(_from), to(_to) {}
2.1371 -
2.1372 - /// \brief Destructor of the DigraphCopy
2.1373 - ///
2.1374 - /// Destructor of the DigraphCopy
2.1375 - ~BpGraphCopy() {
2.1376 - for (int i = 0; i < int(redMapCopies.size()); ++i) {
2.1377 - delete redMapCopies[i];
2.1378 - }
2.1379 - for (int i = 0; i < int(blueMapCopies.size()); ++i) {
2.1380 - delete blueMapCopies[i];
2.1381 - }
2.1382 - for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
2.1383 - delete nodeMapCopies[i];
2.1384 - }
2.1385 - for (int i = 0; i < int(arcMapCopies.size()); ++i) {
2.1386 - delete arcMapCopies[i];
2.1387 - }
2.1388 - for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
2.1389 - delete edgeMapCopies[i];
2.1390 - }
2.1391 -
2.1392 - }
2.1393 -
2.1394 - /// \brief Copies the A-node references into the given map.
2.1395 - ///
2.1396 - /// Copies the A-node references into the given map.
2.1397 - template <typename RedRef>
2.1398 - BpGraphCopy& redRef(RedRef& map) {
2.1399 - redMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Red,
2.1400 - RedRefMap, RedRef>(map));
2.1401 - return *this;
2.1402 - }
2.1403 -
2.1404 - /// \brief Copies the A-node cross references into the given map.
2.1405 - ///
2.1406 - /// Copies the A-node cross references (reverse references) into
2.1407 - /// the given map.
2.1408 - template <typename RedCrossRef>
2.1409 - BpGraphCopy& redCrossRef(RedCrossRef& map) {
2.1410 - redMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
2.1411 - Red, RedRefMap, RedCrossRef>(map));
2.1412 - return *this;
2.1413 - }
2.1414 -
2.1415 - /// \brief Make copy of the given A-node map.
2.1416 - ///
2.1417 - /// Makes copy of the given map for the newly created digraph.
2.1418 - /// The new map's key type is the to digraph's node type,
2.1419 - /// and the copied map's key type is the from digraph's node
2.1420 - /// type.
2.1421 - template <typename ToMap, typename FromMap>
2.1422 - BpGraphCopy& redMap(ToMap& tmap, const FromMap& map) {
2.1423 - redMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Red,
2.1424 - RedRefMap, ToMap, FromMap>(tmap, map));
2.1425 - return *this;
2.1426 - }
2.1427 -
2.1428 - /// \brief Copies the B-node references into the given map.
2.1429 - ///
2.1430 - /// Copies the B-node references into the given map.
2.1431 - template <typename BlueRef>
2.1432 - BpGraphCopy& blueRef(BlueRef& map) {
2.1433 - blueMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Blue,
2.1434 - BlueRefMap, BlueRef>(map));
2.1435 - return *this;
2.1436 - }
2.1437 -
2.1438 - /// \brief Copies the B-node cross references into the given map.
2.1439 - ///
2.1440 - /// Copies the B-node cross references (reverse references) into
2.1441 - /// the given map.
2.1442 - template <typename BlueCrossRef>
2.1443 - BpGraphCopy& blueCrossRef(BlueCrossRef& map) {
2.1444 - blueMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
2.1445 - Blue, BlueRefMap, BlueCrossRef>(map));
2.1446 - return *this;
2.1447 - }
2.1448 -
2.1449 - /// \brief Make copy of the given B-node map.
2.1450 - ///
2.1451 - /// Makes copy of the given map for the newly created digraph.
2.1452 - /// The new map's key type is the to digraph's node type,
2.1453 - /// and the copied map's key type is the from digraph's node
2.1454 - /// type.
2.1455 - template <typename ToMap, typename FromMap>
2.1456 - BpGraphCopy& blueMap(ToMap& tmap, const FromMap& map) {
2.1457 - blueMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Blue,
2.1458 - BlueRefMap, ToMap, FromMap>(tmap, map));
2.1459 - return *this;
2.1460 - }
2.1461 - /// \brief Copies the node references into the given map.
2.1462 - ///
2.1463 - /// Copies the node references into the given map.
2.1464 - template <typename NodeRef>
2.1465 - BpGraphCopy& nodeRef(NodeRef& map) {
2.1466 - nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,
2.1467 - NodeRefMap, NodeRef>(map));
2.1468 - return *this;
2.1469 - }
2.1470 -
2.1471 - /// \brief Copies the node cross references into the given map.
2.1472 - ///
2.1473 - /// Copies the node cross references (reverse references) into
2.1474 - /// the given map.
2.1475 - template <typename NodeCrossRef>
2.1476 - BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {
2.1477 - nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,
2.1478 - NodeRefMap, NodeCrossRef>(map));
2.1479 - return *this;
2.1480 - }
2.1481 -
2.1482 - /// \brief Make copy of the given map.
2.1483 - ///
2.1484 - /// Makes copy of the given map for the newly created digraph.
2.1485 - /// The new map's key type is the to digraph's node type,
2.1486 - /// and the copied map's key type is the from digraph's node
2.1487 - /// type.
2.1488 - template <typename ToMap, typename FromMap>
2.1489 - BpGraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
2.1490 - nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,
2.1491 - NodeRefMap, ToMap, FromMap>(tmap, map));
2.1492 - return *this;
2.1493 - }
2.1494 -
2.1495 - /// \brief Make a copy of the given node.
2.1496 - ///
2.1497 - /// Make a copy of the given node.
2.1498 - BpGraphCopy& node(TNode& tnode, const Node& snode) {
2.1499 - nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,
2.1500 - NodeRefMap, TNode>(tnode, snode));
2.1501 - return *this;
2.1502 - }
2.1503 -
2.1504 - /// \brief Copies the arc references into the given map.
2.1505 - ///
2.1506 - /// Copies the arc references into the given map.
2.1507 - template <typename ArcRef>
2.1508 - BpGraphCopy& arcRef(ArcRef& map) {
2.1509 - arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,
2.1510 - ArcRefMap, ArcRef>(map));
2.1511 - return *this;
2.1512 - }
2.1513 -
2.1514 - /// \brief Copies the arc cross references into the given map.
2.1515 - ///
2.1516 - /// Copies the arc cross references (reverse references) into
2.1517 - /// the given map.
2.1518 - template <typename ArcCrossRef>
2.1519 - BpGraphCopy& arcCrossRef(ArcCrossRef& map) {
2.1520 - arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,
2.1521 - ArcRefMap, ArcCrossRef>(map));
2.1522 - return *this;
2.1523 - }
2.1524 -
2.1525 - /// \brief Make copy of the given map.
2.1526 - ///
2.1527 - /// Makes copy of the given map for the newly created digraph.
2.1528 - /// The new map's key type is the to digraph's arc type,
2.1529 - /// and the copied map's key type is the from digraph's arc
2.1530 - /// type.
2.1531 - template <typename ToMap, typename FromMap>
2.1532 - BpGraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
2.1533 - arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,
2.1534 - ArcRefMap, ToMap, FromMap>(tmap, map));
2.1535 - return *this;
2.1536 - }
2.1537 -
2.1538 - /// \brief Make a copy of the given arc.
2.1539 - ///
2.1540 - /// Make a copy of the given arc.
2.1541 - BpGraphCopy& arc(TArc& tarc, const Arc& sarc) {
2.1542 - arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,
2.1543 - ArcRefMap, TArc>(tarc, sarc));
2.1544 - return *this;
2.1545 - }
2.1546 -
2.1547 - /// \brief Copies the edge references into the given map.
2.1548 - ///
2.1549 - /// Copies the edge references into the given map.
2.1550 - template <typename EdgeRef>
2.1551 - BpGraphCopy& edgeRef(EdgeRef& map) {
2.1552 - edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,
2.1553 - EdgeRefMap, EdgeRef>(map));
2.1554 - return *this;
2.1555 - }
2.1556 -
2.1557 - /// \brief Copies the edge cross references into the given map.
2.1558 - ///
2.1559 - /// Copies the edge cross references (reverse
2.1560 - /// references) into the given map.
2.1561 - template <typename EdgeCrossRef>
2.1562 - BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
2.1563 - edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,
2.1564 - Edge, EdgeRefMap, EdgeCrossRef>(map));
2.1565 - return *this;
2.1566 - }
2.1567 -
2.1568 - /// \brief Make copy of the given map.
2.1569 - ///
2.1570 - /// Makes copy of the given map for the newly created digraph.
2.1571 - /// The new map's key type is the to digraph's edge type,
2.1572 - /// and the copied map's key type is the from digraph's edge
2.1573 - /// type.
2.1574 - template <typename ToMap, typename FromMap>
2.1575 - BpGraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
2.1576 - edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,
2.1577 - EdgeRefMap, ToMap, FromMap>(tmap, map));
2.1578 - return *this;
2.1579 - }
2.1580 -
2.1581 - /// \brief Make a copy of the given edge.
2.1582 - ///
2.1583 - /// Make a copy of the given edge.
2.1584 - BpGraphCopy& edge(TEdge& tedge, const Edge& sedge) {
2.1585 - edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,
2.1586 - EdgeRefMap, TEdge>(tedge, sedge));
2.1587 - return *this;
2.1588 - }
2.1589 -
2.1590 - /// \brief Executes the copies.
2.1591 - ///
2.1592 - /// Executes the copies.
2.1593 - void run() {
2.1594 - RedRefMap redRefMap(from);
2.1595 - BlueRefMap blueRefMap(from);
2.1596 - NodeRefMap nodeRefMap(from, redRefMap, blueRefMap);
2.1597 - EdgeRefMap edgeRefMap(from);
2.1598 - ArcRefMap arcRefMap(to, from, edgeRefMap, nodeRefMap);
2.1599 - _digraph_utils_bits::BpGraphCopySelector<To>::
2.1600 - copy(to, from, redRefMap, blueRefMap, edgeRefMap);
2.1601 - for (int i = 0; i < int(redMapCopies.size()); ++i) {
2.1602 - redMapCopies[i]->copy(from, redRefMap);
2.1603 - }
2.1604 - for (int i = 0; i < int(blueMapCopies.size()); ++i) {
2.1605 - blueMapCopies[i]->copy(from, blueRefMap);
2.1606 - }
2.1607 - for (int i = 0; i < int(nodeMapCopies.size()); ++i) {
2.1608 - nodeMapCopies[i]->copy(from, nodeRefMap);
2.1609 - }
2.1610 - for (int i = 0; i < int(edgeMapCopies.size()); ++i) {
2.1611 - edgeMapCopies[i]->copy(from, edgeRefMap);
2.1612 - }
2.1613 - for (int i = 0; i < int(arcMapCopies.size()); ++i) {
2.1614 - arcMapCopies[i]->copy(from, arcRefMap);
2.1615 - }
2.1616 - }
2.1617 -
2.1618 - private:
2.1619 -
2.1620 - const From& from;
2.1621 - To& to;
2.1622 -
2.1623 - std::vector<_digraph_utils_bits::MapCopyBase<From, Red, RedRefMap>* >
2.1624 - redMapCopies;
2.1625 -
2.1626 - std::vector<_digraph_utils_bits::MapCopyBase<From, Blue, BlueRefMap>* >
2.1627 - blueMapCopies;
2.1628 -
2.1629 - std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
2.1630 - nodeMapCopies;
2.1631 -
2.1632 - std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
2.1633 - arcMapCopies;
2.1634 -
2.1635 - std::vector<_digraph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
2.1636 - edgeMapCopies;
2.1637 -
2.1638 - };
2.1639 -
2.1640 - /// \brief Copy a bipartite digraph to another digraph.
2.1641 - ///
2.1642 - /// Copy a bipartite digraph to another digraph.
2.1643 - /// The usage of the function:
2.1644 - ///
2.1645 - ///\code
2.1646 - /// copyBpGraph(trg, src).redRef(anr).arcCrossRef(ecr).run();
2.1647 - ///\endcode
2.1648 - ///
2.1649 - /// After the copy the \c nr map will contain the mapping from the
2.1650 - /// nodes of the \c from digraph to the nodes of the \c to digraph and
2.1651 - /// \c ecr will contain the mapping from the arcs of the \c to digraph
2.1652 - /// to the arcs of the \c from digraph.
2.1653 - ///
2.1654 - /// \see BpGraphCopy
2.1655 - template <typename To, typename From>
2.1656 - BpGraphCopy<To, From>
2.1657 - copyBpGraph(To& to, const From& from) {
2.1658 - return BpGraphCopy<To, From>(to, from);
2.1659 - }
2.1660 -
2.1661 -
2.1662 /// @}
2.1663
2.1664 - /// \addtogroup digraph_maps
2.1665 + /// \addtogroup graph_maps
2.1666 /// @{
2.1667
2.1668 - /// Provides an immutable and unique id for each item in the digraph.
2.1669 + /// Provides an immutable and unique id for each item in the graph.
2.1670
2.1671 /// The IdMap class provides a unique and immutable id for each item of the
2.1672 - /// same type (e.g. node) in the digraph. This id is <ul><li>\b unique:
2.1673 + /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
2.1674 /// different items (nodes) get different ids <li>\b immutable: the id of an
2.1675 /// item (node) does not change (even if you delete other nodes). </ul>
2.1676 /// Through this map you get access (i.e. can read) the inner id values of
2.1677 - /// the items stored in the digraph. This map can be inverted with its member
2.1678 - /// class \c InverseMap.
2.1679 + /// the items stored in the graph. This map can be inverted with its member
2.1680 + /// class \c InverseMap or with the \c operator() member.
2.1681 ///
2.1682 - template <typename _Digraph, typename _Item>
2.1683 + template <typename _Graph, typename _Item>
2.1684 class IdMap {
2.1685 public:
2.1686 - typedef _Digraph Digraph;
2.1687 + typedef _Graph Graph;
2.1688 typedef int Value;
2.1689 typedef _Item Item;
2.1690 typedef _Item Key;
2.1691 @@ -1593,20 +1128,20 @@
2.1692 /// \brief Constructor.
2.1693 ///
2.1694 /// Constructor of the map.
2.1695 - explicit IdMap(const Digraph& _digraph) : digraph(&_digraph) {}
2.1696 + explicit IdMap(const Graph& graph) : _graph(&graph) {}
2.1697
2.1698 /// \brief Gives back the \e id of the item.
2.1699 ///
2.1700 /// Gives back the immutable and unique \e id of the item.
2.1701 - int operator[](const Item& item) const { return digraph->id(item);}
2.1702 + int operator[](const Item& item) const { return _graph->id(item);}
2.1703
2.1704 /// \brief Gives back the item by its id.
2.1705 ///
2.1706 /// Gives back the item by its id.
2.1707 - Item operator()(int id) { return digraph->fromId(id, Item()); }
2.1708 + Item operator()(int id) { return _graph->fromId(id, Item()); }
2.1709
2.1710 private:
2.1711 - const Digraph* digraph;
2.1712 + const Graph* _graph;
2.1713
2.1714 public:
2.1715
2.1716 @@ -1620,34 +1155,34 @@
2.1717 /// \brief Constructor.
2.1718 ///
2.1719 /// Constructor for creating an id-to-item map.
2.1720 - explicit InverseMap(const Digraph& _digraph) : digraph(&_digraph) {}
2.1721 + explicit InverseMap(const Graph& graph) : _graph(&graph) {}
2.1722
2.1723 /// \brief Constructor.
2.1724 ///
2.1725 /// Constructor for creating an id-to-item map.
2.1726 - explicit InverseMap(const IdMap& idMap) : digraph(idMap.digraph) {}
2.1727 + explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
2.1728
2.1729 /// \brief Gives back the given item from its id.
2.1730 ///
2.1731 /// Gives back the given item from its id.
2.1732 ///
2.1733 - Item operator[](int id) const { return digraph->fromId(id, Item());}
2.1734 + Item operator[](int id) const { return _graph->fromId(id, Item());}
2.1735
2.1736 private:
2.1737 - const Digraph* digraph;
2.1738 + const Graph* _graph;
2.1739 };
2.1740
2.1741 /// \brief Gives back the inverse of the map.
2.1742 ///
2.1743 /// Gives back the inverse of the IdMap.
2.1744 - InverseMap inverse() const { return InverseMap(*digraph);}
2.1745 + InverseMap inverse() const { return InverseMap(*_graph);}
2.1746
2.1747 };
2.1748
2.1749
2.1750 - /// \brief General invertable digraph-map type.
2.1751 + /// \brief General invertable graph-map type.
2.1752
2.1753 - /// This type provides simple invertable digraph-maps.
2.1754 + /// This type provides simple invertable graph-maps.
2.1755 /// The InvertableMap wraps an arbitrary ReadWriteMap
2.1756 /// and if a key is set to a new value then store it
2.1757 /// in the inverse map.
2.1758 @@ -1655,20 +1190,20 @@
2.1759 /// The values of the map can be accessed
2.1760 /// with stl compatible forward iterator.
2.1761 ///
2.1762 - /// \param _Digraph The digraph type.
2.1763 - /// \param _Item The item type of the digraph.
2.1764 + /// \param _Graph The graph type.
2.1765 + /// \param _Item The item type of the graph.
2.1766 /// \param _Value The value type of the map.
2.1767 ///
2.1768 /// \see IterableValueMap
2.1769 - template <typename _Digraph, typename _Item, typename _Value>
2.1770 - class InvertableMap : protected DefaultMap<_Digraph, _Item, _Value> {
2.1771 + template <typename _Graph, typename _Item, typename _Value>
2.1772 + class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
2.1773 private:
2.1774
2.1775 - typedef DefaultMap<_Digraph, _Item, _Value> Map;
2.1776 - typedef _Digraph Digraph;
2.1777 + typedef DefaultMap<_Graph, _Item, _Value> Map;
2.1778 + typedef _Graph Graph;
2.1779
2.1780 typedef std::map<_Value, _Item> Container;
2.1781 - Container invMap;
2.1782 + Container _inv_map;
2.1783
2.1784 public:
2.1785
2.1786 @@ -1681,9 +1216,9 @@
2.1787
2.1788 /// \brief Constructor.
2.1789 ///
2.1790 - /// Construct a new InvertableMap for the digraph.
2.1791 + /// Construct a new InvertableMap for the graph.
2.1792 ///
2.1793 - explicit InvertableMap(const Digraph& digraph) : Map(digraph) {}
2.1794 + explicit InvertableMap(const Graph& graph) : Map(graph) {}
2.1795
2.1796 /// \brief Forward iterator for values.
2.1797 ///
2.1798 @@ -1725,7 +1260,7 @@
2.1799 /// map can be accessed in the [beginValue, endValue)
2.1800 /// range.
2.1801 ValueIterator beginValue() const {
2.1802 - return ValueIterator(invMap.begin());
2.1803 + return ValueIterator(_inv_map.begin());
2.1804 }
2.1805
2.1806 /// \brief Returns an iterator after the last value.
2.1807 @@ -1735,7 +1270,7 @@
2.1808 /// map can be accessed in the [beginValue, endValue)
2.1809 /// range.
2.1810 ValueIterator endValue() const {
2.1811 - return ValueIterator(invMap.end());
2.1812 + return ValueIterator(_inv_map.end());
2.1813 }
2.1814
2.1815 /// \brief The setter function of the map.
2.1816 @@ -1743,11 +1278,11 @@
2.1817 /// Sets the mapped value.
2.1818 void set(const Key& key, const Value& val) {
2.1819 Value oldval = Map::operator[](key);
2.1820 - typename Container::iterator it = invMap.find(oldval);
2.1821 - if (it != invMap.end() && it->second == key) {
2.1822 - invMap.erase(it);
2.1823 + typename Container::iterator it = _inv_map.find(oldval);
2.1824 + if (it != _inv_map.end() && it->second == key) {
2.1825 + _inv_map.erase(it);
2.1826 }
2.1827 - invMap.insert(make_pair(val, key));
2.1828 + _inv_map.insert(make_pair(val, key));
2.1829 Map::set(key, val);
2.1830 }
2.1831
2.1832 @@ -1763,8 +1298,8 @@
2.1833 ///
2.1834 /// Gives back the item by its value.
2.1835 Key operator()(const Value& key) const {
2.1836 - typename Container::const_iterator it = invMap.find(key);
2.1837 - return it != invMap.end() ? it->second : INVALID;
2.1838 + typename Container::const_iterator it = _inv_map.find(key);
2.1839 + return it != _inv_map.end() ? it->second : INVALID;
2.1840 }
2.1841
2.1842 protected:
2.1843 @@ -1775,9 +1310,9 @@
2.1844 /// \c AlterationNotifier.
2.1845 virtual void erase(const Key& key) {
2.1846 Value val = Map::operator[](key);
2.1847 - typename Container::iterator it = invMap.find(val);
2.1848 - if (it != invMap.end() && it->second == key) {
2.1849 - invMap.erase(it);
2.1850 + typename Container::iterator it = _inv_map.find(val);
2.1851 + if (it != _inv_map.end() && it->second == key) {
2.1852 + _inv_map.erase(it);
2.1853 }
2.1854 Map::erase(key);
2.1855 }
2.1856 @@ -1789,9 +1324,9 @@
2.1857 virtual void erase(const std::vector<Key>& keys) {
2.1858 for (int i = 0; i < int(keys.size()); ++i) {
2.1859 Value val = Map::operator[](keys[i]);
2.1860 - typename Container::iterator it = invMap.find(val);
2.1861 - if (it != invMap.end() && it->second == keys[i]) {
2.1862 - invMap.erase(it);
2.1863 + typename Container::iterator it = _inv_map.find(val);
2.1864 + if (it != _inv_map.end() && it->second == keys[i]) {
2.1865 + _inv_map.erase(it);
2.1866 }
2.1867 }
2.1868 Map::erase(keys);
2.1869 @@ -1802,7 +1337,7 @@
2.1870 /// Clear the keys from the map and inverse map. It is called by the
2.1871 /// \c AlterationNotifier.
2.1872 virtual void clear() {
2.1873 - invMap.clear();
2.1874 + _inv_map.clear();
2.1875 Map::clear();
2.1876 }
2.1877
2.1878 @@ -1817,8 +1352,8 @@
2.1879 /// \brief Constructor of the InverseMap.
2.1880 ///
2.1881 /// Constructor of the InverseMap.
2.1882 - explicit InverseMap(const InvertableMap& _inverted)
2.1883 - : inverted(_inverted) {}
2.1884 + explicit InverseMap(const InvertableMap& inverted)
2.1885 + : _inverted(inverted) {}
2.1886
2.1887 /// The value type of the InverseMap.
2.1888 typedef typename InvertableMap::Key Value;
2.1889 @@ -1830,11 +1365,11 @@
2.1890 /// Subscript operator. It gives back always the item
2.1891 /// what was last assigned to the value.
2.1892 Value operator[](const Key& key) const {
2.1893 - return inverted(key);
2.1894 + return _inverted(key);
2.1895 }
2.1896
2.1897 private:
2.1898 - const InvertableMap& inverted;
2.1899 + const InvertableMap& _inverted;
2.1900 };
2.1901
2.1902 /// \brief It gives back the just readable inverse map.
2.1903 @@ -1849,29 +1384,29 @@
2.1904 };
2.1905
2.1906 /// \brief Provides a mutable, continuous and unique descriptor for each
2.1907 - /// item in the digraph.
2.1908 + /// item in the graph.
2.1909 ///
2.1910 /// The DescriptorMap class provides a unique and continuous (but mutable)
2.1911 /// descriptor (id) for each item of the same type (e.g. node) in the
2.1912 - /// digraph. This id is <ul><li>\b unique: different items (nodes) get
2.1913 + /// graph. This id is <ul><li>\b unique: different items (nodes) get
2.1914 /// different ids <li>\b continuous: the range of the ids is the set of
2.1915 /// integers between 0 and \c n-1, where \c n is the number of the items of
2.1916 /// this type (e.g. nodes) (so the id of a node can change if you delete an
2.1917 /// other node, i.e. this id is mutable). </ul> This map can be inverted
2.1918 - /// with its member class \c InverseMap.
2.1919 + /// with its member class \c InverseMap, or with the \c operator() member.
2.1920 ///
2.1921 - /// \param _Digraph The digraph class the \c DescriptorMap belongs to.
2.1922 + /// \param _Graph The graph class the \c DescriptorMap belongs to.
2.1923 /// \param _Item The Item is the Key of the Map. It may be Node, Arc or
2.1924 /// Edge.
2.1925 - template <typename _Digraph, typename _Item>
2.1926 - class DescriptorMap : protected DefaultMap<_Digraph, _Item, int> {
2.1927 + template <typename _Graph, typename _Item>
2.1928 + class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
2.1929
2.1930 typedef _Item Item;
2.1931 - typedef DefaultMap<_Digraph, _Item, int> Map;
2.1932 + typedef DefaultMap<_Graph, _Item, int> Map;
2.1933
2.1934 public:
2.1935 - /// The digraph class of DescriptorMap.
2.1936 - typedef _Digraph Digraph;
2.1937 + /// The graph class of DescriptorMap.
2.1938 + typedef _Graph Graph;
2.1939
2.1940 /// The key type of DescriptorMap (Node, Arc, Edge).
2.1941 typedef typename Map::Key Key;
2.1942 @@ -1881,12 +1416,12 @@
2.1943 /// \brief Constructor.
2.1944 ///
2.1945 /// Constructor for descriptor map.
2.1946 - explicit DescriptorMap(const Digraph& _digraph) : Map(_digraph) {
2.1947 + explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
2.1948 Item it;
2.1949 const typename Map::Notifier* nf = Map::notifier();
2.1950 for (nf->first(it); it != INVALID; nf->next(it)) {
2.1951 - Map::set(it, invMap.size());
2.1952 - invMap.push_back(it);
2.1953 + Map::set(it, _inv_map.size());
2.1954 + _inv_map.push_back(it);
2.1955 }
2.1956 }
2.1957
2.1958 @@ -1898,8 +1433,8 @@
2.1959 /// \c AlterationNotifier.
2.1960 virtual void add(const Item& item) {
2.1961 Map::add(item);
2.1962 - Map::set(item, invMap.size());
2.1963 - invMap.push_back(item);
2.1964 + Map::set(item, _inv_map.size());
2.1965 + _inv_map.push_back(item);
2.1966 }
2.1967
2.1968 /// \brief Add more new keys to the map.
2.1969 @@ -1909,8 +1444,8 @@
2.1970 virtual void add(const std::vector<Item>& items) {
2.1971 Map::add(items);
2.1972 for (int i = 0; i < int(items.size()); ++i) {
2.1973 - Map::set(items[i], invMap.size());
2.1974 - invMap.push_back(items[i]);
2.1975 + Map::set(items[i], _inv_map.size());
2.1976 + _inv_map.push_back(items[i]);
2.1977 }
2.1978 }
2.1979
2.1980 @@ -1919,9 +1454,9 @@
2.1981 /// Erase the key from the map. It is called by the
2.1982 /// \c AlterationNotifier.
2.1983 virtual void erase(const Item& item) {
2.1984 - Map::set(invMap.back(), Map::operator[](item));
2.1985 - invMap[Map::operator[](item)] = invMap.back();
2.1986 - invMap.pop_back();
2.1987 + Map::set(_inv_map.back(), Map::operator[](item));
2.1988 + _inv_map[Map::operator[](item)] = _inv_map.back();
2.1989 + _inv_map.pop_back();
2.1990 Map::erase(item);
2.1991 }
2.1992
2.1993 @@ -1931,9 +1466,9 @@
2.1994 /// \c AlterationNotifier.
2.1995 virtual void erase(const std::vector<Item>& items) {
2.1996 for (int i = 0; i < int(items.size()); ++i) {
2.1997 - Map::set(invMap.back(), Map::operator[](items[i]));
2.1998 - invMap[Map::operator[](items[i])] = invMap.back();
2.1999 - invMap.pop_back();
2.2000 + Map::set(_inv_map.back(), Map::operator[](items[i]));
2.2001 + _inv_map[Map::operator[](items[i])] = _inv_map.back();
2.2002 + _inv_map.pop_back();
2.2003 }
2.2004 Map::erase(items);
2.2005 }
2.2006 @@ -1947,8 +1482,8 @@
2.2007 Item it;
2.2008 const typename Map::Notifier* nf = Map::notifier();
2.2009 for (nf->first(it); it != INVALID; nf->next(it)) {
2.2010 - Map::set(it, invMap.size());
2.2011 - invMap.push_back(it);
2.2012 + Map::set(it, _inv_map.size());
2.2013 + _inv_map.push_back(it);
2.2014 }
2.2015 }
2.2016
2.2017 @@ -1957,7 +1492,7 @@
2.2018 /// Clear the keys from the map. It is called by the
2.2019 /// \c AlterationNotifier.
2.2020 virtual void clear() {
2.2021 - invMap.clear();
2.2022 + _inv_map.clear();
2.2023 Map::clear();
2.2024 }
2.2025
2.2026 @@ -1967,7 +1502,7 @@
2.2027 ///
2.2028 /// Returns the maximal value plus one in the map.
2.2029 unsigned int size() const {
2.2030 - return invMap.size();
2.2031 + return _inv_map.size();
2.2032 }
2.2033
2.2034 /// \brief Swaps the position of the two items in the map.
2.2035 @@ -1977,9 +1512,9 @@
2.2036 int pi = Map::operator[](p);
2.2037 int qi = Map::operator[](q);
2.2038 Map::set(p, qi);
2.2039 - invMap[qi] = p;
2.2040 + _inv_map[qi] = p;
2.2041 Map::set(q, pi);
2.2042 - invMap[pi] = q;
2.2043 + _inv_map[pi] = q;
2.2044 }
2.2045
2.2046 /// \brief Gives back the \e descriptor of the item.
2.2047 @@ -1993,13 +1528,13 @@
2.2048 ///
2.2049 /// Gives back th item by its descriptor.
2.2050 Item operator()(int id) const {
2.2051 - return invMap[id];
2.2052 + return _inv_map[id];
2.2053 }
2.2054
2.2055 private:
2.2056
2.2057 typedef std::vector<Item> Container;
2.2058 - Container invMap;
2.2059 + Container _inv_map;
2.2060
2.2061 public:
2.2062 /// \brief The inverse map type of DescriptorMap.
2.2063 @@ -2010,8 +1545,8 @@
2.2064 /// \brief Constructor of the InverseMap.
2.2065 ///
2.2066 /// Constructor of the InverseMap.
2.2067 - explicit InverseMap(const DescriptorMap& _inverted)
2.2068 - : inverted(_inverted) {}
2.2069 + explicit InverseMap(const DescriptorMap& inverted)
2.2070 + : _inverted(inverted) {}
2.2071
2.2072
2.2073 /// The value type of the InverseMap.
2.2074 @@ -2024,18 +1559,18 @@
2.2075 /// Subscript operator. It gives back the item
2.2076 /// that the descriptor belongs to currently.
2.2077 Value operator[](const Key& key) const {
2.2078 - return inverted(key);
2.2079 + return _inverted(key);
2.2080 }
2.2081
2.2082 /// \brief Size of the map.
2.2083 ///
2.2084 /// Returns the size of the map.
2.2085 unsigned int size() const {
2.2086 - return inverted.size();
2.2087 + return _inverted.size();
2.2088 }
2.2089
2.2090 private:
2.2091 - const DescriptorMap& inverted;
2.2092 + const DescriptorMap& _inverted;
2.2093 };
2.2094
2.2095 /// \brief Gives back the inverse of the map.
2.2096 @@ -2062,7 +1597,7 @@
2.2097 ///
2.2098 /// Constructor
2.2099 /// \param _digraph The digraph that the map belongs to.
2.2100 - explicit SourceMap(const Digraph& _digraph) : digraph(_digraph) {}
2.2101 + explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
2.2102
2.2103 /// \brief The subscript operator.
2.2104 ///
2.2105 @@ -2070,11 +1605,11 @@
2.2106 /// \param arc The arc
2.2107 /// \return The source of the arc
2.2108 Value operator[](const Key& arc) const {
2.2109 - return digraph.source(arc);
2.2110 + return _digraph.source(arc);
2.2111 }
2.2112
2.2113 private:
2.2114 - const Digraph& digraph;
2.2115 + const Digraph& _digraph;
2.2116 };
2.2117
2.2118 /// \brief Returns a \ref SourceMap class.
2.2119 @@ -2102,7 +1637,7 @@
2.2120 ///
2.2121 /// Constructor
2.2122 /// \param _digraph The digraph that the map belongs to.
2.2123 - explicit TargetMap(const Digraph& _digraph) : digraph(_digraph) {}
2.2124 + explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
2.2125
2.2126 /// \brief The subscript operator.
2.2127 ///
2.2128 @@ -2110,11 +1645,11 @@
2.2129 /// \param e The arc
2.2130 /// \return The target of the arc
2.2131 Value operator[](const Key& e) const {
2.2132 - return digraph.target(e);
2.2133 + return _digraph.target(e);
2.2134 }
2.2135
2.2136 private:
2.2137 - const Digraph& digraph;
2.2138 + const Digraph& _digraph;
2.2139 };
2.2140
2.2141 /// \brief Returns a \ref TargetMap class.
2.2142 @@ -2131,18 +1666,18 @@
2.2143 /// Returns the "forward" directed arc view of an edge.
2.2144 /// \see BackwardMap
2.2145 /// \author Balazs Dezso
2.2146 - template <typename Digraph>
2.2147 + template <typename Graph>
2.2148 class ForwardMap {
2.2149 public:
2.2150
2.2151 - typedef typename Digraph::Arc Value;
2.2152 - typedef typename Digraph::Edge Key;
2.2153 + typedef typename Graph::Arc Value;
2.2154 + typedef typename Graph::Edge Key;
2.2155
2.2156 /// \brief Constructor
2.2157 ///
2.2158 /// Constructor
2.2159 - /// \param _digraph The digraph that the map belongs to.
2.2160 - explicit ForwardMap(const Digraph& _digraph) : digraph(_digraph) {}
2.2161 + /// \param _graph The graph that the map belongs to.
2.2162 + explicit ForwardMap(const Graph& graph) : _graph(graph) {}
2.2163
2.2164 /// \brief The subscript operator.
2.2165 ///
2.2166 @@ -2150,20 +1685,20 @@
2.2167 /// \param key An edge
2.2168 /// \return The "forward" directed arc view of edge
2.2169 Value operator[](const Key& key) const {
2.2170 - return digraph.direct(key, true);
2.2171 + return _graph.direct(key, true);
2.2172 }
2.2173
2.2174 private:
2.2175 - const Digraph& digraph;
2.2176 + const Graph& _graph;
2.2177 };
2.2178
2.2179 /// \brief Returns a \ref ForwardMap class.
2.2180 ///
2.2181 /// This function just returns an \ref ForwardMap class.
2.2182 /// \relates ForwardMap
2.2183 - template <typename Digraph>
2.2184 - inline ForwardMap<Digraph> forwardMap(const Digraph& digraph) {
2.2185 - return ForwardMap<Digraph>(digraph);
2.2186 + template <typename Graph>
2.2187 + inline ForwardMap<Graph> forwardMap(const Graph& graph) {
2.2188 + return ForwardMap<Graph>(graph);
2.2189 }
2.2190
2.2191 /// \brief Returns the "backward" directed arc view of an edge.
2.2192 @@ -2171,18 +1706,18 @@
2.2193 /// Returns the "backward" directed arc view of an edge.
2.2194 /// \see ForwardMap
2.2195 /// \author Balazs Dezso
2.2196 - template <typename Digraph>
2.2197 + template <typename Graph>
2.2198 class BackwardMap {
2.2199 public:
2.2200
2.2201 - typedef typename Digraph::Arc Value;
2.2202 - typedef typename Digraph::Edge Key;
2.2203 + typedef typename Graph::Arc Value;
2.2204 + typedef typename Graph::Edge Key;
2.2205
2.2206 /// \brief Constructor
2.2207 ///
2.2208 /// Constructor
2.2209 - /// \param _digraph The digraph that the map belongs to.
2.2210 - explicit BackwardMap(const Digraph& _digraph) : digraph(_digraph) {}
2.2211 + /// \param _graph The graph that the map belongs to.
2.2212 + explicit BackwardMap(const Graph& graph) : _graph(graph) {}
2.2213
2.2214 /// \brief The subscript operator.
2.2215 ///
2.2216 @@ -2190,20 +1725,20 @@
2.2217 /// \param key An edge
2.2218 /// \return The "backward" directed arc view of edge
2.2219 Value operator[](const Key& key) const {
2.2220 - return digraph.direct(key, false);
2.2221 + return _graph.direct(key, false);
2.2222 }
2.2223
2.2224 private:
2.2225 - const Digraph& digraph;
2.2226 + const Graph& _graph;
2.2227 };
2.2228
2.2229 /// \brief Returns a \ref BackwardMap class
2.2230
2.2231 /// This function just returns a \ref BackwardMap class.
2.2232 /// \relates BackwardMap
2.2233 - template <typename Digraph>
2.2234 - inline BackwardMap<Digraph> backwardMap(const Digraph& digraph) {
2.2235 - return BackwardMap<Digraph>(digraph);
2.2236 + template <typename Graph>
2.2237 + inline BackwardMap<Graph> backwardMap(const Graph& graph) {
2.2238 + return BackwardMap<Graph>(graph);
2.2239 }
2.2240
2.2241 /// \brief Potential difference map
2.2242 @@ -2220,20 +1755,21 @@
2.2243 /// \brief Constructor
2.2244 ///
2.2245 /// Contructor of the map
2.2246 - explicit PotentialDifferenceMap(const Digraph& _digraph,
2.2247 - const NodeMap& _potential)
2.2248 - : digraph(_digraph), potential(_potential) {}
2.2249 + explicit PotentialDifferenceMap(const Digraph& digraph,
2.2250 + const NodeMap& potential)
2.2251 + : _digraph(digraph), _potential(potential) {}
2.2252
2.2253 /// \brief Const subscription operator
2.2254 ///
2.2255 /// Const subscription operator
2.2256 Value operator[](const Key& arc) const {
2.2257 - return potential[digraph.target(arc)] - potential[digraph.source(arc)];
2.2258 + return _potential[_digraph.target(arc)] -
2.2259 + _potential[_digraph.source(arc)];
2.2260 }
2.2261
2.2262 private:
2.2263 - const Digraph& digraph;
2.2264 - const NodeMap& potential;
2.2265 + const Digraph& _digraph;
2.2266 + const NodeMap& _potential;
2.2267 };
2.2268
2.2269 /// \brief Returns a PotentialDifferenceMap.
2.2270 @@ -2274,16 +1810,15 @@
2.2271 typedef int Value;
2.2272 typedef typename Digraph::Node Key;
2.2273
2.2274 - typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
2.2275 + typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
2.2276 ::ItemNotifier::ObserverBase Parent;
2.2277
2.2278 private:
2.2279
2.2280 - class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
2.2281 + class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
2.2282 public:
2.2283
2.2284 - typedef DefaultMap<_Digraph, Key, int> Parent;
2.2285 - typedef typename Parent::Digraph Digraph;
2.2286 + typedef DefaultMap<Digraph, Key, int> Parent;
2.2287
2.2288 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
2.2289
2.2290 @@ -2314,17 +1849,18 @@
2.2291 /// \brief Constructor.
2.2292 ///
2.2293 /// Constructor for creating in-degree map.
2.2294 - explicit InDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
2.2295 - Parent::attach(digraph.notifier(typename _Digraph::Arc()));
2.2296 + explicit InDegMap(const Digraph& digraph)
2.2297 + : _digraph(digraph), _deg(digraph) {
2.2298 + Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2.2299
2.2300 - for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
2.2301 - deg[it] = countInArcs(digraph, it);
2.2302 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2.2303 + _deg[it] = countInArcs(_digraph, it);
2.2304 }
2.2305 }
2.2306
2.2307 /// Gives back the in-degree of a Node.
2.2308 int operator[](const Key& key) const {
2.2309 - return deg[key];
2.2310 + return _deg[key];
2.2311 }
2.2312
2.2313 protected:
2.2314 @@ -2332,40 +1868,40 @@
2.2315 typedef typename Digraph::Arc Arc;
2.2316
2.2317 virtual void add(const Arc& arc) {
2.2318 - ++deg[digraph.target(arc)];
2.2319 + ++_deg[_digraph.target(arc)];
2.2320 }
2.2321
2.2322 virtual void add(const std::vector<Arc>& arcs) {
2.2323 for (int i = 0; i < int(arcs.size()); ++i) {
2.2324 - ++deg[digraph.target(arcs[i])];
2.2325 + ++_deg[_digraph.target(arcs[i])];
2.2326 }
2.2327 }
2.2328
2.2329 virtual void erase(const Arc& arc) {
2.2330 - --deg[digraph.target(arc)];
2.2331 + --_deg[_digraph.target(arc)];
2.2332 }
2.2333
2.2334 virtual void erase(const std::vector<Arc>& arcs) {
2.2335 for (int i = 0; i < int(arcs.size()); ++i) {
2.2336 - --deg[digraph.target(arcs[i])];
2.2337 + --_deg[_digraph.target(arcs[i])];
2.2338 }
2.2339 }
2.2340
2.2341 virtual void build() {
2.2342 - for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
2.2343 - deg[it] = countInArcs(digraph, it);
2.2344 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2.2345 + _deg[it] = countInArcs(_digraph, it);
2.2346 }
2.2347 }
2.2348
2.2349 virtual void clear() {
2.2350 - for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
2.2351 - deg[it] = 0;
2.2352 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2.2353 + _deg[it] = 0;
2.2354 }
2.2355 }
2.2356 private:
2.2357
2.2358 - const _Digraph& digraph;
2.2359 - AutoNodeMap deg;
2.2360 + const Digraph& _digraph;
2.2361 + AutoNodeMap _deg;
2.2362 };
2.2363
2.2364 /// \brief Map of the node out-degrees.
2.2365 @@ -2391,21 +1927,20 @@
2.2366 ::ItemNotifier::ObserverBase {
2.2367
2.2368 public:
2.2369 -
2.2370 - typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>
2.2371 - ::ItemNotifier::ObserverBase Parent;
2.2372
2.2373 typedef _Digraph Digraph;
2.2374 typedef int Value;
2.2375 typedef typename Digraph::Node Key;
2.2376
2.2377 + typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
2.2378 + ::ItemNotifier::ObserverBase Parent;
2.2379 +
2.2380 private:
2.2381
2.2382 - class AutoNodeMap : public DefaultMap<_Digraph, Key, int> {
2.2383 + class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
2.2384 public:
2.2385
2.2386 - typedef DefaultMap<_Digraph, Key, int> Parent;
2.2387 - typedef typename Parent::Digraph Digraph;
2.2388 + typedef DefaultMap<Digraph, Key, int> Parent;
2.2389
2.2390 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
2.2391
2.2392 @@ -2434,17 +1969,18 @@
2.2393 /// \brief Constructor.
2.2394 ///
2.2395 /// Constructor for creating out-degree map.
2.2396 - explicit OutDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) {
2.2397 - Parent::attach(digraph.notifier(typename _Digraph::Arc()));
2.2398 + explicit OutDegMap(const Digraph& digraph)
2.2399 + : _digraph(digraph), _deg(digraph) {
2.2400 + Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2.2401
2.2402 - for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
2.2403 - deg[it] = countOutArcs(digraph, it);
2.2404 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2.2405 + _deg[it] = countOutArcs(_digraph, it);
2.2406 }
2.2407 }
2.2408
2.2409 /// Gives back the out-degree of a Node.
2.2410 int operator[](const Key& key) const {
2.2411 - return deg[key];
2.2412 + return _deg[key];
2.2413 }
2.2414
2.2415 protected:
2.2416 @@ -2452,40 +1988,40 @@
2.2417 typedef typename Digraph::Arc Arc;
2.2418
2.2419 virtual void add(const Arc& arc) {
2.2420 - ++deg[digraph.source(arc)];
2.2421 + ++_deg[_digraph.source(arc)];
2.2422 }
2.2423
2.2424 virtual void add(const std::vector<Arc>& arcs) {
2.2425 for (int i = 0; i < int(arcs.size()); ++i) {
2.2426 - ++deg[digraph.source(arcs[i])];
2.2427 + ++_deg[_digraph.source(arcs[i])];
2.2428 }
2.2429 }
2.2430
2.2431 virtual void erase(const Arc& arc) {
2.2432 - --deg[digraph.source(arc)];
2.2433 + --_deg[_digraph.source(arc)];
2.2434 }
2.2435
2.2436 virtual void erase(const std::vector<Arc>& arcs) {
2.2437 for (int i = 0; i < int(arcs.size()); ++i) {
2.2438 - --deg[digraph.source(arcs[i])];
2.2439 + --_deg[_digraph.source(arcs[i])];
2.2440 }
2.2441 }
2.2442
2.2443 virtual void build() {
2.2444 - for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
2.2445 - deg[it] = countOutArcs(digraph, it);
2.2446 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2.2447 + _deg[it] = countOutArcs(_digraph, it);
2.2448 }
2.2449 }
2.2450
2.2451 virtual void clear() {
2.2452 - for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {
2.2453 - deg[it] = 0;
2.2454 + for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2.2455 + _deg[it] = 0;
2.2456 }
2.2457 }
2.2458 private:
2.2459
2.2460 - const _Digraph& digraph;
2.2461 - AutoNodeMap deg;
2.2462 + const Digraph& _digraph;
2.2463 + AutoNodeMap _deg;
2.2464 };
2.2465
2.2466
2.2467 @@ -2500,7 +2036,7 @@
2.2468 ///the \c findFirst() and \c findNext() members.
2.2469 ///
2.2470 ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
2.2471 - ///digraph do not changed so frequently.
2.2472 + ///digraph is not changed so frequently.
2.2473 ///
2.2474 ///This class uses a self-adjusting binary search tree, Sleator's
2.2475 ///and Tarjan's Splay tree for guarantee the logarithmic amortized
2.2476 @@ -2520,7 +2056,7 @@
2.2477 typedef typename ItemSetTraits<G, typename G::Arc>
2.2478 ::ItemNotifier::ObserverBase Parent;
2.2479
2.2480 - GRAPH_TYPEDEFS(typename G);
2.2481 + DIGRAPH_TYPEDEFS(typename G);
2.2482 typedef G Digraph;
2.2483
2.2484 protected:
2.2485 @@ -2835,24 +2371,24 @@
2.2486 ///\ref INVALID otherwise.
2.2487 Arc operator()(Node s, Node t) const
2.2488 {
2.2489 - Arc e = _head[s];
2.2490 + Arc a = _head[s];
2.2491 while (true) {
2.2492 - if (_g.target(e) == t) {
2.2493 - const_cast<DynArcLookUp&>(*this).splay(e);
2.2494 - return e;
2.2495 - } else if (t < _g.target(e)) {
2.2496 - if (_left[e] == INVALID) {
2.2497 - const_cast<DynArcLookUp&>(*this).splay(e);
2.2498 + if (_g.target(a) == t) {
2.2499 + const_cast<DynArcLookUp&>(*this).splay(a);
2.2500 + return a;
2.2501 + } else if (t < _g.target(a)) {
2.2502 + if (_left[a] == INVALID) {
2.2503 + const_cast<DynArcLookUp&>(*this).splay(a);
2.2504 return INVALID;
2.2505 } else {
2.2506 - e = _left[e];
2.2507 + a = _left[a];
2.2508 }
2.2509 } else {
2.2510 - if (_right[e] == INVALID) {
2.2511 - const_cast<DynArcLookUp&>(*this).splay(e);
2.2512 + if (_right[a] == INVALID) {
2.2513 + const_cast<DynArcLookUp&>(*this).splay(a);
2.2514 return INVALID;
2.2515 } else {
2.2516 - e = _right[e];
2.2517 + a = _right[a];
2.2518 }
2.2519 }
2.2520 }
2.2521 @@ -2869,25 +2405,25 @@
2.2522 /// otherwise.
2.2523 Arc findFirst(Node s, Node t) const
2.2524 {
2.2525 - Arc e = _head[s];
2.2526 + Arc a = _head[s];
2.2527 Arc r = INVALID;
2.2528 while (true) {
2.2529 - if (_g.target(e) < t) {
2.2530 - if (_right[e] == INVALID) {
2.2531 - const_cast<DynArcLookUp&>(*this).splay(e);
2.2532 + if (_g.target(a) < t) {
2.2533 + if (_right[a] == INVALID) {
2.2534 + const_cast<DynArcLookUp&>(*this).splay(a);
2.2535 return r;
2.2536 } else {
2.2537 - e = _right[e];
2.2538 + a = _right[a];
2.2539 }
2.2540 } else {
2.2541 - if (_g.target(e) == t) {
2.2542 - r = e;
2.2543 + if (_g.target(a) == t) {
2.2544 + r = a;
2.2545 }
2.2546 - if (_left[e] == INVALID) {
2.2547 - const_cast<DynArcLookUp&>(*this).splay(e);
2.2548 + if (_left[a] == INVALID) {
2.2549 + const_cast<DynArcLookUp&>(*this).splay(a);
2.2550 return r;
2.2551 } else {
2.2552 - e = _left[e];
2.2553 + a = _left[a];
2.2554 }
2.2555 }
2.2556 }
2.2557 @@ -2906,29 +2442,29 @@
2.2558 ///\note If \c e is not the result of the previous \c findFirst()
2.2559 ///operation then the amorized time bound can not be guaranteed.
2.2560 #ifdef DOXYGEN
2.2561 - Arc findNext(Node s, Node t, Arc e) const
2.2562 + Arc findNext(Node s, Node t, Arc a) const
2.2563 #else
2.2564 - Arc findNext(Node, Node t, Arc e) const
2.2565 + Arc findNext(Node, Node t, Arc a) const
2.2566 #endif
2.2567 {
2.2568 - if (_right[e] != INVALID) {
2.2569 - e = _right[e];
2.2570 - while (_left[e] != INVALID) {
2.2571 - e = _left[e];
2.2572 + if (_right[a] != INVALID) {
2.2573 + a = _right[a];
2.2574 + while (_left[a] != INVALID) {
2.2575 + a = _left[a];
2.2576 }
2.2577 - const_cast<DynArcLookUp&>(*this).splay(e);
2.2578 + const_cast<DynArcLookUp&>(*this).splay(a);
2.2579 } else {
2.2580 - while (_parent[e] != INVALID && _right[_parent[e]] == e) {
2.2581 - e = _parent[e];
2.2582 + while (_parent[a] != INVALID && _right[_parent[a]] == a) {
2.2583 + a = _parent[a];
2.2584 }
2.2585 - if (_parent[e] == INVALID) {
2.2586 + if (_parent[a] == INVALID) {
2.2587 return INVALID;
2.2588 } else {
2.2589 - e = _parent[e];
2.2590 - const_cast<DynArcLookUp&>(*this).splay(e);
2.2591 + a = _parent[a];
2.2592 + const_cast<DynArcLookUp&>(*this).splay(a);
2.2593 }
2.2594 }
2.2595 - if (_g.target(e) == t) return e;
2.2596 + if (_g.target(a) == t) return a;
2.2597 else return INVALID;
2.2598 }
2.2599
2.2600 @@ -2957,7 +2493,7 @@
2.2601 class ArcLookUp
2.2602 {
2.2603 public:
2.2604 - GRAPH_TYPEDEFS(typename G);
2.2605 + DIGRAPH_TYPEDEFS(typename G);
2.2606 typedef G Digraph;
2.2607
2.2608 protected:
2.2609 @@ -3074,7 +2610,7 @@
2.2610 using ArcLookUp<G>::_left;
2.2611 using ArcLookUp<G>::_head;
2.2612
2.2613 - GRAPH_TYPEDEFS(typename G);
2.2614 + DIGRAPH_TYPEDEFS(typename G);
2.2615 typedef G Digraph;
2.2616
2.2617 typename Digraph::template ArcMap<Arc> _next;
3.1 --- a/lemon/lgf_reader.h Mon Apr 21 17:35:12 2008 +0200
3.2 +++ b/lemon/lgf_reader.h Tue Apr 22 15:04:00 2008 +0200
3.3 @@ -302,7 +302,7 @@
3.4 public:
3.5
3.6 typedef _Digraph Digraph;
3.7 - GRAPH_TYPEDEFS(typename Digraph);
3.8 + DIGRAPH_TYPEDEFS(typename Digraph);
3.9
3.10 private:
3.11
4.1 --- a/lemon/lgf_writer.h Mon Apr 21 17:35:12 2008 +0200
4.2 +++ b/lemon/lgf_writer.h Tue Apr 22 15:04:00 2008 +0200
4.3 @@ -237,7 +237,7 @@
4.4 public:
4.5
4.6 typedef _Digraph Digraph;
4.7 - GRAPH_TYPEDEFS(typename Digraph);
4.8 + DIGRAPH_TYPEDEFS(typename Digraph);
4.9
4.10 private:
4.11
5.1 --- a/lemon/smart_graph.h Mon Apr 21 17:35:12 2008 +0200
5.2 +++ b/lemon/smart_graph.h Tue Apr 22 15:04:00 2008 +0200
5.3 @@ -73,7 +73,7 @@
5.4 : nodes(_g.nodes), arcs(_g.arcs) { }
5.5
5.6 typedef True NodeNumTag;
5.7 - typedef True ArcNumTag;
5.8 + typedef True EdgeNumTag;
5.9
5.10 int nodeNum() const { return nodes.size(); }
5.11 int arcNum() const { return arcs.size(); }
6.1 --- a/test/Makefile.am Mon Apr 21 17:35:12 2008 +0200
6.2 +++ b/test/Makefile.am Tue Apr 22 15:04:00 2008 +0200
6.3 @@ -3,6 +3,7 @@
6.4
6.5 noinst_HEADERS += \
6.6 test/digraph_test.h \
6.7 + test/graph_utils_test.h \
6.8 test/heap_test.h \
6.9 test/map_test.h \
6.10 test/test_tools.h
6.11 @@ -15,6 +16,7 @@
6.12 test/dim_test \
6.13 test/error_test \
6.14 test/graph_test \
6.15 + test/graph_utils_test \
6.16 test/kruskal_test \
6.17 test/maps_test \
6.18 test/random_test \
6.19 @@ -34,6 +36,7 @@
6.20 test_dim_test_SOURCES = test/dim_test.cc
6.21 test_error_test_SOURCES = test/error_test.cc
6.22 test_graph_test_SOURCES = test/graph_test.cc
6.23 +test_graph_utils_test_SOURCES = test/graph_utils_test.cc
6.24 # test_heap_test_SOURCES = test/heap_test.cc
6.25 test_kruskal_test_SOURCES = test/kruskal_test.cc
6.26 test_maps_test_SOURCES = test/maps_test.cc
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/test/graph_utils_test.cc Tue Apr 22 15:04:00 2008 +0200
7.3 @@ -0,0 +1,141 @@
7.4 +/* -*- C++ -*-
7.5 + *
7.6 + * This file is a part of LEMON, a generic C++ optimization library
7.7 + *
7.8 + * Copyright (C) 2003-2008
7.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
7.11 + *
7.12 + * Permission to use, modify and distribute this software is granted
7.13 + * provided that this copyright notice appears in all copies. For
7.14 + * precise terms see the accompanying LICENSE file.
7.15 + *
7.16 + * This software is provided "AS IS" with no warranty of any kind,
7.17 + * express or implied, and with no claim as to its suitability for any
7.18 + * purpose.
7.19 + *
7.20 + */
7.21 +
7.22 +#include <iostream>
7.23 +#include <vector>
7.24 +
7.25 +#include <lemon/graph_utils.h>
7.26 +
7.27 +#include <lemon/list_graph.h>
7.28 +#include <lemon/smart_graph.h>
7.29 +
7.30 +#include "test_tools.h"
7.31 +#include "graph_utils_test.h"
7.32 +
7.33 +
7.34 +using namespace lemon;
7.35 +
7.36 +template <class Graph>
7.37 +void checkSnapDeg()
7.38 +{
7.39 + Graph g;
7.40 + typename Graph::Node n1=g.addNode();
7.41 + typename Graph::Node n2=g.addNode();
7.42 +
7.43 + InDegMap<Graph> ind(g);
7.44 +
7.45 + g.addArc(n1,n2);
7.46 +
7.47 + typename Graph::Snapshot snap(g);
7.48 +
7.49 + OutDegMap<Graph> outd(g);
7.50 +
7.51 + check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
7.52 + check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
7.53 +
7.54 + g.addArc(n1,n2);
7.55 + g.addArc(n2,n1);
7.56 +
7.57 + check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
7.58 + check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
7.59 +
7.60 + snap.restore();
7.61 +
7.62 + check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
7.63 + check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
7.64 +
7.65 +}
7.66 +
7.67 +int main() {
7.68 + ///\file
7.69 + { // checking list graph
7.70 + checkDigraphCounters<ListDigraph>();
7.71 + checkFindArc<ListDigraph>();
7.72 + }
7.73 + { // checking smart graph
7.74 + checkDigraphCounters<SmartDigraph>();
7.75 + checkFindArc<SmartDigraph>();
7.76 + }
7.77 + {
7.78 + int num = 5;
7.79 + SmartDigraph fg;
7.80 + std::vector<SmartDigraph::Node> nodes;
7.81 + for (int i = 0; i < num; ++i) {
7.82 + nodes.push_back(fg.addNode());
7.83 + }
7.84 + for (int i = 0; i < num * num; ++i) {
7.85 + fg.addArc(nodes[i / num], nodes[i % num]);
7.86 + }
7.87 + check(countNodes(fg) == num, "FullGraph: wrong node number.");
7.88 + check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
7.89 + for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
7.90 + for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
7.91 + ConArcIt<SmartDigraph> con(fg, src, trg);
7.92 + check(con != INVALID, "There is no connecting arc.");
7.93 + check(fg.source(con) == src, "Wrong source.");
7.94 + check(fg.target(con) == trg, "Wrong target.");
7.95 + check(++con == INVALID, "There is more connecting arc.");
7.96 + }
7.97 + }
7.98 + AllArcLookUp<SmartDigraph> el(fg);
7.99 + for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
7.100 + for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
7.101 + SmartDigraph::Arc con = el(src, trg);
7.102 + check(con != INVALID, "There is no connecting arc.");
7.103 + check(fg.source(con) == src, "Wrong source.");
7.104 + check(fg.target(con) == trg, "Wrong target.");
7.105 + check(el(src,trg,con) == INVALID, "There is more connecting arc.");
7.106 + }
7.107 + }
7.108 + }
7.109 +
7.110 + //check In/OutDegMap (and Snapshot feature)
7.111 +
7.112 + checkSnapDeg<ListDigraph>();
7.113 + checkSnapDeg<SmartDigraph>();
7.114 +
7.115 + {
7.116 + const int nodeNum = 10;
7.117 + const int arcNum = 100;
7.118 + ListDigraph digraph;
7.119 + InDegMap<ListDigraph> inDeg(digraph);
7.120 + OutDegMap<ListDigraph> outDeg(digraph);
7.121 + std::vector<ListDigraph::Node> nodes(nodeNum);
7.122 + for (int i = 0; i < nodeNum; ++i) {
7.123 + nodes[i] = digraph.addNode();
7.124 + }
7.125 + std::vector<ListDigraph::Arc> arcs(arcNum);
7.126 + for (int i = 0; i < arcNum; ++i) {
7.127 + arcs[i] =
7.128 + digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
7.129 + }
7.130 + for (int i = 0; i < nodeNum; ++i) {
7.131 + check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
7.132 + "Wrong in degree map");
7.133 + }
7.134 + for (int i = 0; i < nodeNum; ++i) {
7.135 + check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
7.136 + "Wrong in degree map");
7.137 + }
7.138 + }
7.139 +
7.140 + ///Everything is OK
7.141 + std::cout << __FILE__ ": All tests passed.\n";
7.142 +
7.143 + return 0;
7.144 +}
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/test/graph_utils_test.h Tue Apr 22 15:04:00 2008 +0200
8.3 @@ -0,0 +1,83 @@
8.4 +/* -*- C++ -*-
8.5 + *
8.6 + * This file is a part of LEMON, a generic C++ optimization library
8.7 + *
8.8 + * Copyright (C) 2003-2008
8.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
8.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
8.11 + *
8.12 + * Permission to use, modify and distribute this software is granted
8.13 + * provided that this copyright notice appears in all copies. For
8.14 + * precise terms see the accompanying LICENSE file.
8.15 + *
8.16 + * This software is provided "AS IS" with no warranty of any kind,
8.17 + * express or implied, and with no claim as to its suitability for any
8.18 + * purpose.
8.19 + *
8.20 + */
8.21 +
8.22 +#ifndef LEMON_TEST_GRAPH_UTILS_TEST_H
8.23 +#define LEMON_TEST_GRAPH_UTILS_TEST_H
8.24 +
8.25 +
8.26 +#include "test_tools.h"
8.27 +#include <cstdlib>
8.28 +#include <ctime>
8.29 +
8.30 +//! \ingroup misc
8.31 +//! \file
8.32 +//! \brief Test cases for graph utils.
8.33 +namespace lemon {
8.34 +
8.35 + template <typename Digraph>
8.36 + void checkDigraphCounters() {
8.37 + const int num = 5;
8.38 + Digraph digraph;
8.39 + addPetersen(digraph, num);
8.40 + bidirDigraph(digraph);
8.41 + check(countNodes(digraph) == 2*num, "Wrong node number.");
8.42 + check(countArcs(digraph) == 6*num, "Wrong arc number.");
8.43 + for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {
8.44 + check(countOutArcs(digraph, it) == 3, "Wrong out degree number.");
8.45 + check(countInArcs(digraph, it) == 3, "Wrong in degree number.");
8.46 + }
8.47 + }
8.48 +
8.49 + template <typename Digraph>
8.50 + void checkFindArc() {
8.51 + typedef typename Digraph::Node Node;
8.52 + typedef typename Digraph::Arc Arc;
8.53 + typedef typename Digraph::NodeIt NodeIt;
8.54 + typedef typename Digraph::ArcIt ArcIt;
8.55 + Digraph digraph;
8.56 + for (int i = 0; i < 10; ++i) {
8.57 + digraph.addNode();
8.58 + }
8.59 + DescriptorMap<Digraph, Node> nodes(digraph);
8.60 + typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
8.61 + for (int i = 0; i < 100; ++i) {
8.62 + int src = rnd[invNodes.size()];
8.63 + int trg = rnd[invNodes.size()];
8.64 + digraph.addArc(invNodes[src], invNodes[trg]);
8.65 + }
8.66 + typename Digraph::template ArcMap<bool> found(digraph, false);
8.67 + DescriptorMap<Digraph, Arc> arcs(digraph);
8.68 + for (NodeIt src(digraph); src != INVALID; ++src) {
8.69 + for (NodeIt trg(digraph); trg != INVALID; ++trg) {
8.70 + for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
8.71 + check(digraph.source(con) == src, "Wrong source.");
8.72 + check(digraph.target(con) == trg, "Wrong target.");
8.73 + check(found[con] == false, "The arc found already.");
8.74 + found[con] = true;
8.75 + }
8.76 + }
8.77 + }
8.78 + for (ArcIt it(digraph); it != INVALID; ++it) {
8.79 + check(found[it] == true, "The arc is not found.");
8.80 + }
8.81 + }
8.82 +
8.83 +} //namespace lemon
8.84 +
8.85 +
8.86 +#endif