1.1 --- a/lemon/graph_utils.h Tue Oct 31 14:31:13 2006 +0000
1.2 +++ b/lemon/graph_utils.h Tue Oct 31 14:41:12 2006 +0000
1.3 @@ -83,9 +83,6 @@
1.4 typedef Graph:: UEdge UEdge; \
1.5 typedef Graph:: UEdgeIt UEdgeIt; \
1.6 typedef Graph:: IncEdgeIt IncEdgeIt;
1.7 -// typedef Graph::template UEdgeMap<bool> BoolUEdgeMap;
1.8 -// typedef Graph::template UEdgeMap<int> IntUEdgeMap;
1.9 -// typedef Graph::template UEdgeMap<double> DoubleUEdgeMap;
1.10
1.11 ///\brief Creates convenience typedefs for the bipartite undirected graph
1.12 ///types and iterators
1.13 @@ -103,6 +100,8 @@
1.14 ///template typedefs in C++.
1.15 #define BPUGRAPH_TYPEDEFS(Graph) \
1.16 UGRAPH_TYPEDEFS(Graph) \
1.17 + typedef Graph::ANode ANode; \
1.18 + typedef Graph::BNode BNode; \
1.19 typedef Graph::ANodeIt ANodeIt; \
1.20 typedef Graph::BNodeIt BNodeIt;
1.21
1.22 @@ -379,10 +378,9 @@
1.23 ///\se AllEdgeLookup
1.24 ///\sa ConEdgeIt
1.25 template <typename Graph>
1.26 - inline typename Graph::Edge findEdge(const Graph &g,
1.27 - typename Graph::Node u,
1.28 - typename Graph::Node v,
1.29 - typename Graph::Edge prev = INVALID) {
1.30 + inline typename Graph::Edge
1.31 + findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1.32 + typename Graph::Edge prev = INVALID) {
1.33 return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev);
1.34 }
1.35
1.36 @@ -506,10 +504,9 @@
1.37 ///\sa ConEdgeIt
1.38
1.39 template <typename Graph>
1.40 - inline typename Graph::UEdge findUEdge(const Graph &g,
1.41 - typename Graph::Node u,
1.42 - typename Graph::Node v,
1.43 - typename Graph::UEdge p = INVALID) {
1.44 + inline typename Graph::UEdge
1.45 + findUEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
1.46 + typename Graph::UEdge p = INVALID) {
1.47 return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, p);
1.48 }
1.49
1.50 @@ -588,79 +585,133 @@
1.51 }
1.52 }
1.53
1.54 + namespace _graph_utils_bits {
1.55 +
1.56 + template <typename Graph, typename Item, typename RefMap>
1.57 + class MapCopyBase {
1.58 + public:
1.59 + virtual void copy(const Graph& source, const RefMap& refMap) = 0;
1.60 +
1.61 + virtual ~MapCopyBase() {}
1.62 + };
1.63 +
1.64 + template <typename Graph, typename Item, typename RefMap,
1.65 + typename TargetMap, typename SourceMap>
1.66 + class MapCopy : public MapCopyBase<Graph, Item, RefMap> {
1.67 + public:
1.68 +
1.69 + MapCopy(TargetMap& tmap, const SourceMap& map)
1.70 + : _tmap(tmap), _map(map) {}
1.71 +
1.72 + virtual void copy(const Graph& graph, const RefMap& refMap) {
1.73 + typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
1.74 + for (ItemIt it(graph); it != INVALID; ++it) {
1.75 + _tmap.set(refMap[it], _map[it]);
1.76 + }
1.77 + }
1.78 +
1.79 + private:
1.80 + TargetMap& _tmap;
1.81 + const SourceMap& _map;
1.82 + };
1.83 +
1.84 + template <typename Graph, typename Item, typename RefMap, typename Ref>
1.85 + class RefCopy : public MapCopyBase<Graph, Item, RefMap> {
1.86 + public:
1.87 +
1.88 + RefCopy(Ref& map) : _map(map) {}
1.89 +
1.90 + virtual void copy(const Graph& graph, const RefMap& refMap) {
1.91 + typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
1.92 + for (ItemIt it(graph); it != INVALID; ++it) {
1.93 + _map.set(it, refMap[it]);
1.94 + }
1.95 + }
1.96 +
1.97 + private:
1.98 + Ref& _map;
1.99 + };
1.100 +
1.101 + template <typename Graph, typename Item, typename RefMap,
1.102 + typename CrossRef>
1.103 + class CrossRefCopy : public MapCopyBase<Graph, Item, RefMap> {
1.104 + public:
1.105 +
1.106 + CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
1.107 +
1.108 + virtual void copy(const Graph& graph, const RefMap& refMap) {
1.109 + typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
1.110 + for (ItemIt it(graph); it != INVALID; ++it) {
1.111 + _cmap.set(refMap[it], it);
1.112 + }
1.113 + }
1.114 +
1.115 + private:
1.116 + CrossRef& _cmap;
1.117 + };
1.118 +
1.119 + }
1.120 +
1.121 /// \brief Class to copy a graph.
1.122 ///
1.123 /// Class to copy a graph to another graph (duplicate a graph). The
1.124 /// simplest way of using it is through the \c copyGraph() function.
1.125 template <typename Target, typename Source>
1.126 class GraphCopy {
1.127 - public:
1.128 + private:
1.129 +
1.130 typedef typename Source::Node Node;
1.131 typedef typename Source::NodeIt NodeIt;
1.132 typedef typename Source::Edge Edge;
1.133 typedef typename Source::EdgeIt EdgeIt;
1.134
1.135 - typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
1.136 - typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
1.137 + typedef typename Target::Node TNode;
1.138 + typedef typename Target::Edge TEdge;
1.139 +
1.140 + typedef typename Source::template NodeMap<TNode> NodeRefMap;
1.141 + typedef typename Source::template EdgeMap<TEdge> EdgeRefMap;
1.142 +
1.143 +
1.144 + public:
1.145 +
1.146
1.147 /// \brief Constructor for the GraphCopy.
1.148 ///
1.149 /// It copies the content of the \c _source graph into the
1.150 - /// \c _target graph. It creates also two references, one beetween
1.151 - /// the two nodeset and one beetween the two edgesets.
1.152 + /// \c _target graph.
1.153 GraphCopy(Target& _target, const Source& _source)
1.154 - : source(_source), target(_target),
1.155 - nodeRefMap(_source), edgeRefMap(_source) {
1.156 - for (NodeIt it(source); it != INVALID; ++it) {
1.157 - nodeRefMap[it] = target.addNode();
1.158 + : source(_source), target(_target) {}
1.159 +
1.160 + /// \brief Destructor of the GraphCopy
1.161 + ///
1.162 + /// Destructor of the GraphCopy
1.163 + ~GraphCopy() {
1.164 + for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
1.165 + delete nodeMapCopies[i];
1.166 }
1.167 - for (EdgeIt it(source); it != INVALID; ++it) {
1.168 - edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
1.169 - nodeRefMap[source.target(it)]);
1.170 + for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
1.171 + delete edgeMapCopies[i];
1.172 }
1.173 +
1.174 }
1.175
1.176 /// \brief Copies the node references into the given map.
1.177 ///
1.178 /// Copies the node references into the given map.
1.179 template <typename NodeRef>
1.180 - const GraphCopy& nodeRef(NodeRef& map) const {
1.181 - for (NodeIt it(source); it != INVALID; ++it) {
1.182 - map.set(it, nodeRefMap[it]);
1.183 - }
1.184 + GraphCopy& nodeRef(NodeRef& map) {
1.185 + nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Node,
1.186 + NodeRefMap, NodeRef>(map));
1.187 return *this;
1.188 }
1.189
1.190 /// \brief Reverse and copies the node references into the given map.
1.191 ///
1.192 /// Reverse and copies the node references into the given map.
1.193 - template <typename NodeRef>
1.194 - const GraphCopy& nodeCrossRef(NodeRef& map) const {
1.195 - for (NodeIt it(source); it != INVALID; ++it) {
1.196 - map.set(nodeRefMap[it], it);
1.197 - }
1.198 - return *this;
1.199 - }
1.200 -
1.201 - /// \brief Copies the edge references into the given map.
1.202 - ///
1.203 - /// Copies the edge references into the given map.
1.204 - template <typename EdgeRef>
1.205 - const GraphCopy& edgeRef(EdgeRef& map) const {
1.206 - for (EdgeIt it(source); it != INVALID; ++it) {
1.207 - map.set(it, edgeRefMap[it]);
1.208 - }
1.209 - return *this;
1.210 - }
1.211 -
1.212 - /// \brief Reverse and copies the edge references into the given map.
1.213 - ///
1.214 - /// Reverse and copies the edge references into the given map.
1.215 - template <typename EdgeRef>
1.216 - const GraphCopy& edgeCrossRef(EdgeRef& map) const {
1.217 - for (EdgeIt it(source); it != INVALID; ++it) {
1.218 - map.set(edgeRefMap[it], it);
1.219 - }
1.220 + template <typename NodeCrossRef>
1.221 + GraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.222 + nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
1.223 + NodeRefMap, NodeCrossRef>(map));
1.224 return *this;
1.225 }
1.226
1.227 @@ -671,8 +722,29 @@
1.228 /// and the copied map's key type is the source graph's node
1.229 /// type.
1.230 template <typename TargetMap, typename SourceMap>
1.231 - const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
1.232 - copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
1.233 + GraphCopy& nodeMap(TargetMap& tmap, const SourceMap& map) {
1.234 + nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Node,
1.235 + NodeRefMap, TargetMap, SourceMap>(tmap, map));
1.236 + return *this;
1.237 + }
1.238 +
1.239 + /// \brief Copies the edge references into the given map.
1.240 + ///
1.241 + /// Copies the edge references into the given map.
1.242 + template <typename EdgeRef>
1.243 + GraphCopy& edgeRef(EdgeRef& map) {
1.244 + edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Edge,
1.245 + EdgeRefMap, EdgeRef>(map));
1.246 + return *this;
1.247 + }
1.248 +
1.249 + /// \brief Reverse and copies the edge references into the given map.
1.250 + ///
1.251 + /// Reverse and copies the edge references into the given map.
1.252 + template <typename EdgeCrossRef>
1.253 + GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.254 + edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
1.255 + EdgeRefMap, EdgeCrossRef>(map));
1.256 return *this;
1.257 }
1.258
1.259 @@ -683,34 +755,44 @@
1.260 /// and the copied map's key type is the source graph's edge
1.261 /// type.
1.262 template <typename TargetMap, typename SourceMap>
1.263 - const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
1.264 - copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
1.265 + GraphCopy& edgeMap(TargetMap& tmap, const SourceMap& map) {
1.266 + edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Edge,
1.267 + EdgeRefMap, TargetMap, SourceMap>(tmap, map));
1.268 return *this;
1.269 }
1.270
1.271 - /// \brief Gives back the stored node references.
1.272 + /// \brief Executes the copies.
1.273 ///
1.274 - /// Gives back the stored node references.
1.275 - const NodeRefMap& nodeRef() const {
1.276 - return nodeRefMap;
1.277 + /// Executes the copies.
1.278 + void run() {
1.279 + NodeRefMap nodeRefMap(source);
1.280 + for (NodeIt it(source); it != INVALID; ++it) {
1.281 + nodeRefMap[it] = target.addNode();
1.282 + }
1.283 + for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
1.284 + nodeMapCopies[i]->copy(source, nodeRefMap);
1.285 + }
1.286 + EdgeRefMap edgeRefMap(source);
1.287 + for (EdgeIt it(source); it != INVALID; ++it) {
1.288 + edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
1.289 + nodeRefMap[source.target(it)]);
1.290 + }
1.291 + for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
1.292 + edgeMapCopies[i]->copy(source, edgeRefMap);
1.293 + }
1.294 }
1.295
1.296 - /// \brief Gives back the stored edge references.
1.297 - ///
1.298 - /// Gives back the stored edge references.
1.299 - const EdgeRefMap& edgeRef() const {
1.300 - return edgeRefMap;
1.301 - }
1.302 -
1.303 - void run() const {}
1.304 -
1.305 private:
1.306
1.307 const Source& source;
1.308 Target& target;
1.309
1.310 - NodeRefMap nodeRefMap;
1.311 - EdgeRefMap edgeRefMap;
1.312 + std::vector<_graph_utils_bits::MapCopyBase<Source, Node, NodeRefMap>* >
1.313 + nodeMapCopies;
1.314 +
1.315 + std::vector<_graph_utils_bits::MapCopyBase<Source, Edge, EdgeRefMap>* >
1.316 + edgeMapCopies;
1.317 +
1.318 };
1.319
1.320 /// \brief Copy a graph to another graph.
1.321 @@ -719,7 +801,7 @@
1.322 /// The usage of the function:
1.323 ///
1.324 ///\code
1.325 - /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
1.326 + /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr).run();
1.327 ///\endcode
1.328 ///
1.329 /// After the copy the \c nr map will contain the mapping from the
1.330 @@ -737,7 +819,8 @@
1.331 /// The simplest way of using it is through the \c copyUGraph() function.
1.332 template <typename Target, typename Source>
1.333 class UGraphCopy {
1.334 - public:
1.335 + private:
1.336 +
1.337 typedef typename Source::Node Node;
1.338 typedef typename Source::NodeIt NodeIt;
1.339 typedef typename Source::Edge Edge;
1.340 @@ -745,111 +828,79 @@
1.341 typedef typename Source::UEdge UEdge;
1.342 typedef typename Source::UEdgeIt UEdgeIt;
1.343
1.344 - typedef typename Source::
1.345 - template NodeMap<typename Target::Node> NodeRefMap;
1.346 -
1.347 - typedef typename Source::
1.348 - template UEdgeMap<typename Target::UEdge> UEdgeRefMap;
1.349 + typedef typename Target::Node TNode;
1.350 + typedef typename Target::Edge TEdge;
1.351 + typedef typename Target::UEdge TUEdge;
1.352
1.353 - private:
1.354 + typedef typename Source::template NodeMap<TNode> NodeRefMap;
1.355 + typedef typename Source::template UEdgeMap<TUEdge> UEdgeRefMap;
1.356
1.357 struct EdgeRefMap {
1.358 - EdgeRefMap(UGraphCopy& _gc) : gc(_gc) {}
1.359 + EdgeRefMap(const Target& _target, const Source& _source,
1.360 + const UEdgeRefMap& _uedge_ref, const NodeRefMap& _node_ref)
1.361 + : target(_target), source(_source),
1.362 + uedge_ref(_uedge_ref), node_ref(_node_ref) {}
1.363 +
1.364 typedef typename Source::Edge Key;
1.365 typedef typename Target::Edge Value;
1.366
1.367 - Value operator[](const Key& key) {
1.368 - return gc.target.direct(gc.uEdgeRef[key],
1.369 - gc.target.direction(key));
1.370 + Value operator[](const Key& key) const {
1.371 + bool forward = (source.direction(key) ==
1.372 + (node_ref[source.source((UEdge)key)] ==
1.373 + target.source(uedge_ref[(UEdge)key])));
1.374 + return target.direct(uedge_ref[key], forward);
1.375 }
1.376
1.377 - UGraphCopy& gc;
1.378 + const Target& target;
1.379 + const Source& source;
1.380 + const UEdgeRefMap& uedge_ref;
1.381 + const NodeRefMap& node_ref;
1.382 };
1.383 +
1.384
1.385 - public:
1.386 + public:
1.387
1.388 - /// \brief Constructor for the UGraphCopy.
1.389 +
1.390 + /// \brief Constructor for the GraphCopy.
1.391 ///
1.392 /// It copies the content of the \c _source graph into the
1.393 - /// \c _target graph. It creates also two references, one beetween
1.394 - /// the two nodeset and one beetween the two edgesets.
1.395 + /// \c _target graph.
1.396 UGraphCopy(Target& _target, const Source& _source)
1.397 - : source(_source), target(_target),
1.398 - nodeRefMap(_source), edgeRefMap(*this), uEdgeRefMap(_source) {
1.399 - for (NodeIt it(source); it != INVALID; ++it) {
1.400 - nodeRefMap[it] = target.addNode();
1.401 + : source(_source), target(_target) {}
1.402 +
1.403 + /// \brief Destructor of the GraphCopy
1.404 + ///
1.405 + /// Destructor of the GraphCopy
1.406 + ~UGraphCopy() {
1.407 + for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
1.408 + delete nodeMapCopies[i];
1.409 }
1.410 - for (UEdgeIt it(source); it != INVALID; ++it) {
1.411 - uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
1.412 - nodeRefMap[source.target(it)]);
1.413 + for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
1.414 + delete edgeMapCopies[i];
1.415 }
1.416 + for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
1.417 + delete uEdgeMapCopies[i];
1.418 + }
1.419 +
1.420 }
1.421
1.422 /// \brief Copies the node references into the given map.
1.423 ///
1.424 /// Copies the node references into the given map.
1.425 template <typename NodeRef>
1.426 - const UGraphCopy& nodeRef(NodeRef& map) const {
1.427 - for (NodeIt it(source); it != INVALID; ++it) {
1.428 - map.set(it, nodeRefMap[it]);
1.429 - }
1.430 + UGraphCopy& nodeRef(NodeRef& map) {
1.431 + nodeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Node,
1.432 + NodeRefMap, NodeRef>(map));
1.433 return *this;
1.434 }
1.435
1.436 /// \brief Reverse and copies the node references into the given map.
1.437 ///
1.438 /// Reverse and copies the node references into the given map.
1.439 - template <typename NodeRef>
1.440 - const UGraphCopy& nodeCrossRef(NodeRef& map) const {
1.441 - for (NodeIt it(source); it != INVALID; ++it) {
1.442 - map.set(nodeRefMap[it], it);
1.443 - }
1.444 - return *this;
1.445 - }
1.446 -
1.447 - /// \brief Copies the edge references into the given map.
1.448 - ///
1.449 - /// Copies the edge references into the given map.
1.450 - template <typename EdgeRef>
1.451 - const UGraphCopy& edgeRef(EdgeRef& map) const {
1.452 - for (EdgeIt it(source); it != INVALID; ++it) {
1.453 - map.set(edgeRefMap[it], it);
1.454 - }
1.455 - return *this;
1.456 - }
1.457 -
1.458 - /// \brief Reverse and copies the undirected edge references into the
1.459 - /// given map.
1.460 - ///
1.461 - /// Reverse and copies the undirected edge references into the given map.
1.462 - template <typename EdgeRef>
1.463 - const UGraphCopy& edgeCrossRef(EdgeRef& map) const {
1.464 - for (EdgeIt it(source); it != INVALID; ++it) {
1.465 - map.set(it, edgeRefMap[it]);
1.466 - }
1.467 - return *this;
1.468 - }
1.469 -
1.470 - /// \brief Copies the undirected edge references into the given map.
1.471 - ///
1.472 - /// Copies the undirected edge references into the given map.
1.473 - template <typename EdgeRef>
1.474 - const UGraphCopy& uEdgeRef(EdgeRef& map) const {
1.475 - for (UEdgeIt it(source); it != INVALID; ++it) {
1.476 - map.set(it, uEdgeRefMap[it]);
1.477 - }
1.478 - return *this;
1.479 - }
1.480 -
1.481 - /// \brief Reverse and copies the undirected edge references into the
1.482 - /// given map.
1.483 - ///
1.484 - /// Reverse and copies the undirected edge references into the given map.
1.485 - template <typename EdgeRef>
1.486 - const UGraphCopy& uEdgeCrossRef(EdgeRef& map) const {
1.487 - for (UEdgeIt it(source); it != INVALID; ++it) {
1.488 - map.set(uEdgeRefMap[it], it);
1.489 - }
1.490 + template <typename NodeCrossRef>
1.491 + UGraphCopy& nodeCrossRef(NodeCrossRef& map) {
1.492 + nodeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Node,
1.493 + NodeRefMap, NodeCrossRef>(map));
1.494 return *this;
1.495 }
1.496
1.497 @@ -860,9 +911,29 @@
1.498 /// and the copied map's key type is the source graph's node
1.499 /// type.
1.500 template <typename TargetMap, typename SourceMap>
1.501 - const UGraphCopy& nodeMap(TargetMap& tMap,
1.502 - const SourceMap& sMap) const {
1.503 - copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
1.504 + UGraphCopy& nodeMap(TargetMap& tmap, const SourceMap& map) {
1.505 + nodeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Node,
1.506 + NodeRefMap, TargetMap, SourceMap>(tmap, map));
1.507 + return *this;
1.508 + }
1.509 +
1.510 + /// \brief Copies the edge references into the given map.
1.511 + ///
1.512 + /// Copies the edge references into the given map.
1.513 + template <typename EdgeRef>
1.514 + UGraphCopy& edgeRef(EdgeRef& map) {
1.515 + edgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, Edge,
1.516 + EdgeRefMap, EdgeRef>(map));
1.517 + return *this;
1.518 + }
1.519 +
1.520 + /// \brief Reverse and copies the edge references into the given map.
1.521 + ///
1.522 + /// Reverse and copies the edge references into the given map.
1.523 + template <typename EdgeCrossRef>
1.524 + UGraphCopy& edgeCrossRef(EdgeCrossRef& map) {
1.525 + edgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source, Edge,
1.526 + EdgeRefMap, EdgeCrossRef>(map));
1.527 return *this;
1.528 }
1.529
1.530 @@ -873,56 +944,84 @@
1.531 /// and the copied map's key type is the source graph's edge
1.532 /// type.
1.533 template <typename TargetMap, typename SourceMap>
1.534 - const UGraphCopy& edgeMap(TargetMap& tMap,
1.535 - const SourceMap& sMap) const {
1.536 - copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
1.537 + UGraphCopy& edgeMap(TargetMap& tmap, const SourceMap& map) {
1.538 + edgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, Edge,
1.539 + EdgeRefMap, TargetMap, SourceMap>(tmap, map));
1.540 + return *this;
1.541 + }
1.542 +
1.543 + /// \brief Copies the uEdge references into the given map.
1.544 + ///
1.545 + /// Copies the uEdge references into the given map.
1.546 + template <typename UEdgeRef>
1.547 + UGraphCopy& uEdgeRef(UEdgeRef& map) {
1.548 + uEdgeMapCopies.push_back(new _graph_utils_bits::RefCopy<Source, UEdge,
1.549 + UEdgeRefMap, UEdgeRef>(map));
1.550 + return *this;
1.551 + }
1.552 +
1.553 + /// \brief Reverse and copies the uEdge references into the given map.
1.554 + ///
1.555 + /// Reverse and copies the uEdge references into the given map.
1.556 + template <typename UEdgeCrossRef>
1.557 + UGraphCopy& uEdgeCrossRef(UEdgeCrossRef& map) {
1.558 + uEdgeMapCopies.push_back(new _graph_utils_bits::CrossRefCopy<Source,
1.559 + UEdge, UEdgeRefMap, UEdgeCrossRef>(map));
1.560 return *this;
1.561 }
1.562
1.563 /// \brief Make copy of the given map.
1.564 ///
1.565 /// Makes copy of the given map for the newly created graph.
1.566 - /// The new map's key type is the target graph's edge type,
1.567 - /// and the copied map's key type is the source graph's edge
1.568 + /// The new map's key type is the target graph's uEdge type,
1.569 + /// and the copied map's key type is the source graph's uEdge
1.570 /// type.
1.571 template <typename TargetMap, typename SourceMap>
1.572 - const UGraphCopy& uEdgeMap(TargetMap& tMap,
1.573 - const SourceMap& sMap) const {
1.574 - copyMap(tMap, sMap, UEdgeIt(source), uEdgeRefMap);
1.575 + UGraphCopy& uEdgeMap(TargetMap& tmap, const SourceMap& map) {
1.576 + uEdgeMapCopies.push_back(new _graph_utils_bits::MapCopy<Source, UEdge,
1.577 + UEdgeRefMap, TargetMap, SourceMap>(tmap, map));
1.578 return *this;
1.579 }
1.580
1.581 - /// \brief Gives back the stored node references.
1.582 + /// \brief Executes the copies.
1.583 ///
1.584 - /// Gives back the stored node references.
1.585 - const NodeRefMap& nodeRef() const {
1.586 - return nodeRefMap;
1.587 + /// Executes the copies.
1.588 + void run() {
1.589 + NodeRefMap nodeRefMap(source);
1.590 + for (NodeIt it(source); it != INVALID; ++it) {
1.591 + nodeRefMap[it] = target.addNode();
1.592 + }
1.593 + for (int i = 0; i < (int)nodeMapCopies.size(); ++i) {
1.594 + nodeMapCopies[i]->copy(source, nodeRefMap);
1.595 + }
1.596 + UEdgeRefMap uEdgeRefMap(source);
1.597 + EdgeRefMap edgeRefMap(target, source, uEdgeRefMap, nodeRefMap);
1.598 + for (UEdgeIt it(source); it != INVALID; ++it) {
1.599 + uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
1.600 + nodeRefMap[source.target(it)]);
1.601 + }
1.602 + for (int i = 0; i < (int)uEdgeMapCopies.size(); ++i) {
1.603 + uEdgeMapCopies[i]->copy(source, uEdgeRefMap);
1.604 + }
1.605 + for (int i = 0; i < (int)edgeMapCopies.size(); ++i) {
1.606 + edgeMapCopies[i]->copy(source, edgeRefMap);
1.607 + }
1.608 }
1.609
1.610 - /// \brief Gives back the stored edge references.
1.611 - ///
1.612 - /// Gives back the stored edge references.
1.613 - const EdgeRefMap& edgeRef() const {
1.614 - return edgeRefMap;
1.615 - }
1.616 -
1.617 - /// \brief Gives back the stored uedge references.
1.618 - ///
1.619 - /// Gives back the stored uedge references.
1.620 - const UEdgeRefMap& uEdgeRef() const {
1.621 - return uEdgeRefMap;
1.622 - }
1.623 -
1.624 - void run() const {}
1.625 -
1.626 private:
1.627
1.628 const Source& source;
1.629 Target& target;
1.630
1.631 - NodeRefMap nodeRefMap;
1.632 - EdgeRefMap edgeRefMap;
1.633 - UEdgeRefMap uEdgeRefMap;
1.634 + std::vector<_graph_utils_bits::MapCopyBase<Source, Node, NodeRefMap>* >
1.635 + nodeMapCopies;
1.636 +
1.637 + std::vector<_graph_utils_bits::MapCopyBase<Source, Edge, EdgeRefMap>* >
1.638 + edgeMapCopies;
1.639 +
1.640 + std::vector<_graph_utils_bits::MapCopyBase<Source, UEdge, UEdgeRefMap>* >
1.641 + uEdgeMapCopies;
1.642 +
1.643 };
1.644
1.645 /// \brief Copy a graph to another graph.
1.646 @@ -931,7 +1030,7 @@
1.647 /// The usage of the function:
1.648 ///
1.649 ///\code
1.650 - /// copyUGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
1.651 + /// copyUGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr).run();
1.652 ///\endcode
1.653 ///
1.654 /// After the copy the \c nr map will contain the mapping from the
1.655 @@ -971,7 +1070,7 @@
1.656 /// \brief Constructor.
1.657 ///
1.658 /// Constructor for creating id map.
1.659 - IdMap(const Graph& _graph) : graph(&_graph) {}
1.660 + explicit IdMap(const Graph& _graph) : graph(&_graph) {}
1.661
1.662 /// \brief Gives back the \e id of the item.
1.663 ///
1.664 @@ -994,12 +1093,12 @@
1.665 /// \brief Constructor.
1.666 ///
1.667 /// Constructor for creating an id-to-item map.
1.668 - InverseMap(const Graph& _graph) : graph(&_graph) {}
1.669 + explicit InverseMap(const Graph& _graph) : graph(&_graph) {}
1.670
1.671 /// \brief Constructor.
1.672 ///
1.673 /// Constructor for creating an id-to-item map.
1.674 - InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
1.675 + explicit InverseMap(const IdMap& idMap) : graph(idMap.graph) {}
1.676
1.677 /// \brief Gives back the given item from its id.
1.678 ///
1.679 @@ -1066,7 +1165,7 @@
1.680 ///
1.681 /// Construct a new InvertableMap for the graph.
1.682 ///
1.683 - InvertableMap(const Graph& graph) : Map(graph) {}
1.684 + explicit InvertableMap(const Graph& graph) : Map(graph) {}
1.685
1.686 /// \brief Forward iterator for values.
1.687 ///
1.688 @@ -1192,7 +1291,8 @@
1.689 /// \brief Constructor of the InverseMap.
1.690 ///
1.691 /// Constructor of the InverseMap.
1.692 - InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {}
1.693 + explicit InverseMap(const InvertableMap& _inverted)
1.694 + : inverted(_inverted) {}
1.695
1.696 /// The value type of the InverseMap.
1.697 typedef typename InvertableMap::Key Value;
1.698 @@ -1264,7 +1364,7 @@
1.699 /// \brief Constructor.
1.700 ///
1.701 /// Constructor for descriptor map.
1.702 - DescriptorMap(const Graph& _graph) : Map(_graph) {
1.703 + explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
1.704 Item it;
1.705 const typename Map::Notifier* notifier = Map::getNotifier();
1.706 for (notifier->first(it); it != INVALID; notifier->next(it)) {
1.707 @@ -1273,6 +1373,7 @@
1.708 }
1.709 }
1.710
1.711 +
1.712 protected:
1.713
1.714 /// \brief Add a new key to the map.
1.715 @@ -1386,7 +1487,7 @@
1.716 /// \brief Constructor of the InverseMap.
1.717 ///
1.718 /// Constructor of the InverseMap.
1.719 - InverseMap(const DescriptorMap& _inverted)
1.720 + explicit InverseMap(const DescriptorMap& _inverted)
1.721 : inverted(_inverted) {}
1.722
1.723
1.724 @@ -1437,7 +1538,7 @@
1.725 ///
1.726 /// Constructor
1.727 /// \param _graph The graph that the map belongs to.
1.728 - SourceMap(const Graph& _graph) : graph(_graph) {}
1.729 + explicit SourceMap(const Graph& _graph) : graph(_graph) {}
1.730
1.731 /// \brief The subscript operator.
1.732 ///
1.733 @@ -1476,7 +1577,7 @@
1.734 ///
1.735 /// Constructor
1.736 /// \param _graph The graph that the map belongs to.
1.737 - TargetMap(const Graph& _graph) : graph(_graph) {}
1.738 + explicit TargetMap(const Graph& _graph) : graph(_graph) {}
1.739
1.740 /// \brief The subscript operator.
1.741 ///
1.742 @@ -1515,7 +1616,7 @@
1.743 ///
1.744 /// Constructor
1.745 /// \param _graph The graph that the map belongs to.
1.746 - ForwardMap(const Graph& _graph) : graph(_graph) {}
1.747 + explicit ForwardMap(const Graph& _graph) : graph(_graph) {}
1.748
1.749 /// \brief The subscript operator.
1.750 ///
1.751 @@ -1554,7 +1655,7 @@
1.752 ///
1.753 /// Constructor
1.754 /// \param _graph The graph that the map belongs to.
1.755 - BackwardMap(const Graph& _graph) : graph(_graph) {}
1.756 + explicit BackwardMap(const Graph& _graph) : graph(_graph) {}
1.757
1.758 /// \brief The subscript operator.
1.759 ///
1.760 @@ -1592,7 +1693,8 @@
1.761 /// \brief Constructor
1.762 ///
1.763 /// Contructor of the map
1.764 - PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
1.765 + explicit PotentialDifferenceMap(const Graph& _graph,
1.766 + const NodeMap& _potential)
1.767 : graph(_graph), potential(_potential) {}
1.768
1.769 /// \brief Const subscription operator
1.770 @@ -1676,7 +1778,7 @@
1.771 /// \brief Constructor.
1.772 ///
1.773 /// Constructor for creating in-degree map.
1.774 - InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1.775 + explicit InDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1.776 Parent::attach(graph.getNotifier(typename _Graph::Edge()));
1.777
1.778 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.779 @@ -1788,7 +1890,7 @@
1.780 /// \brief Constructor.
1.781 ///
1.782 /// Constructor for creating out-degree map.
1.783 - OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1.784 + explicit OutDegMap(const Graph& _graph) : graph(_graph), deg(_graph) {
1.785 Parent::attach(graph.getNotifier(typename _Graph::Edge()));
1.786
1.787 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {