Changeset 139:701c529ba737 in lemon for lemon/graph_utils.h
 Timestamp:
 04/22/08 15:04:00 (16 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_utils.h
r100 r139 36 36 ///\ingroup gutils 37 37 ///\file 38 ///\brief Digraph utilities.38 ///\brief Graph utilities. 39 39 40 40 namespace lemon { … … 47 47 ///This \c \#define creates convenience typedefs for the following types 48 48 ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt, 49 ///\c OutArcIt 50 ///\note If \c G it a template parameter, it should be used in this way. 51 ///\code 52 /// GRAPH_TYPEDEFS(typename G); 53 ///\endcode 54 /// 55 ///\warning There are no typedefs for the digraph maps because of the lack of 56 ///template typedefs in C++. 57 #define GRAPH_TYPEDEFS(Digraph) \ 58 typedef Digraph:: Node Node; \ 59 typedef Digraph:: NodeIt NodeIt; \ 60 typedef Digraph:: Arc Arc; \ 61 typedef Digraph:: ArcIt ArcIt; \ 62 typedef Digraph:: InArcIt InArcIt; \ 63 typedef Digraph::OutArcIt OutArcIt 49 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 50 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. 51 #define DIGRAPH_TYPEDEFS(Digraph) \ 52 typedef Digraph::Node Node; \ 53 typedef Digraph::NodeIt NodeIt; \ 54 typedef Digraph::Arc Arc; \ 55 typedef Digraph::ArcIt ArcIt; \ 56 typedef Digraph::InArcIt InArcIt; \ 57 typedef Digraph::OutArcIt OutArcIt 64 58 65 59 ///Creates convenience typedefs for the graph types and iterators 66 60 67 ///This \c \#define creates the same convenience typedefs as defined by 68 ///\ref GRAPH_TYPEDEFS(Digraph) and three more, namely it creates 69 ///\c Edge, \c EdgeIt, \c IncArcIt, 70 /// 71 ///\note If \c G it a template parameter, it should be used in this way. 72 ///\code 73 /// UGRAPH_TYPEDEFS(typename G); 74 ///\endcode 75 /// 76 ///\warning There are no typedefs for the digraph maps because of the lack of 77 ///template typedefs in C++. 78 #define UGRAPH_TYPEDEFS(Digraph) \ 79 GRAPH_TYPEDEFS(Digraph); \ 80 typedef Digraph:: Edge Edge; \ 81 typedef Digraph:: EdgeIt EdgeIt; \ 82 typedef Digraph:: IncArcIt IncArcIt 83 84 ///\brief Creates convenience typedefs for the bipartite digraph 85 ///types and iterators 86 87 ///This \c \#define creates the same convenience typedefs as defined by 88 ///\ref UGRAPH_TYPEDEFS(Digraph) and two more, namely it creates 89 ///\c RedIt, \c BlueIt, 90 /// 91 ///\note If \c G it a template parameter, it should be used in this way. 92 ///\code 93 /// BPUGRAPH_TYPEDEFS(typename G); 94 ///\endcode 95 /// 96 ///\warning There are no typedefs for the digraph maps because of the lack of 97 ///template typedefs in C++. 98 #define BPUGRAPH_TYPEDEFS(Digraph) \ 99 UGRAPH_TYPEDEFS(Digraph); \ 100 typedef Digraph::Red Red; \ 101 typedef Digraph::Blue Blue; \ 102 typedef Digraph::RedIt RedIt; \ 103 typedef Digraph::BlueIt BlueIt 104 105 /// \brief Function to count the items in the digraph. 106 /// 107 /// This function counts the items (nodes, arcs etc) in the digraph. 61 ///This \c \#define creates the same convenience typedefs as defined 62 ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates 63 ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap, 64 ///\c DoubleEdgeMap. 65 #define GRAPH_TYPEDEFS(Graph) \ 66 DIGRAPH_TYPEDEFS(Graph); \ 67 typedef Graph::Edge Edge; \ 68 typedef Graph::EdgeIt EdgeIt; \ 69 typedef Graph::IncEdgeIt IncEdgeIt 70 71 /// \brief Function to count the items in the graph. 72 /// 73 /// This function counts the items (nodes, arcs etc) in the graph. 108 74 /// The complexity of the function is O(n) because 109 75 /// it iterates on all of the items. 110 111 template <typename Digraph, typename Item> 112 inline int countItems(const Digraph& g) { 113 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt; 76 template <typename Graph, typename Item> 77 inline int countItems(const Graph& g) { 78 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; 114 79 int num = 0; 115 80 for (ItemIt it(g); it != INVALID; ++it) { … … 121 86 // Node counting: 122 87 123 namespace _ digraph_utils_bits {124 125 template <typename Digraph, typename Enable = void>88 namespace _graph_utils_bits { 89 90 template <typename Graph, typename Enable = void> 126 91 struct CountNodesSelector { 127 static int count(const Digraph &g) {128 return countItems< Digraph, typename Digraph::Node>(g);92 static int count(const Graph &g) { 93 return countItems<Graph, typename Graph::Node>(g); 129 94 } 130 95 }; 131 96 132 template <typename Digraph>97 template <typename Graph> 133 98 struct CountNodesSelector< 134 Digraph, typename135 enable_if<typename Digraph::NodeNumTag, void>::type>99 Graph, typename 100 enable_if<typename Graph::NodeNumTag, void>::type> 136 101 { 137 static int count(const Digraph &g) {102 static int count(const Graph &g) { 138 103 return g.nodeNum(); 139 104 } … … 141 106 } 142 107 143 /// \brief Function to count the nodes in the digraph.144 /// 145 /// This function counts the nodes in the digraph.108 /// \brief Function to count the nodes in the graph. 109 /// 110 /// This function counts the nodes in the graph. 146 111 /// The complexity of the function is O(n) but for some 147 /// digraph structures it is specialized to run in O(1).148 /// 149 /// If the digraph contains a \e nodeNum() member function and a112 /// graph structures it is specialized to run in O(1). 113 /// 114 /// If the graph contains a \e nodeNum() member function and a 150 115 /// \e NodeNumTag tag then this function calls directly the member 151 116 /// function to query the cardinality of the node set. 152 template <typename Digraph>153 inline int countNodes(const Digraph& g) {154 return _ digraph_utils_bits::CountNodesSelector<Digraph>::count(g);117 template <typename Graph> 118 inline int countNodes(const Graph& g) { 119 return _graph_utils_bits::CountNodesSelector<Graph>::count(g); 155 120 } 156 121 157 namespace _digraph_utils_bits { 158 159 template <typename Digraph, typename Enable = void> 160 struct CountRedsSelector { 161 static int count(const Digraph &g) { 162 return countItems<Digraph, typename Digraph::Red>(g); 122 // Arc counting: 123 124 namespace _graph_utils_bits { 125 126 template <typename Graph, typename Enable = void> 127 struct CountArcsSelector { 128 static int count(const Graph &g) { 129 return countItems<Graph, typename Graph::Arc>(g); 163 130 } 164 131 }; 165 132 166 template <typename Digraph>167 struct Count RedsSelector<168 Digraph, typename169 enable_if<typename Digraph::NodeNumTag, void>::type>133 template <typename Graph> 134 struct CountArcsSelector< 135 Graph, 136 typename enable_if<typename Graph::ArcNumTag, void>::type> 170 137 { 171 static int count(const Digraph &g) {172 return g. redNum();138 static int count(const Graph &g) { 139 return g.arcNum(); 173 140 } 174 141 }; 175 142 } 176 143 177 /// \brief Function to count the reds in the digraph.178 /// 179 /// This function counts the reds in the digraph.180 /// The complexity of the function is O( an) but for some181 /// digraph structures it is specialized to run in O(1).182 /// 183 /// If the digraph contains an \e redNum() member function and a184 /// \e NodeNumTag tag then this function calls directly the member185 /// function to query the cardinality of the Anodeset.186 template <typename Digraph>187 inline int count Reds(const Digraph& g) {188 return _ digraph_utils_bits::CountRedsSelector<Digraph>::count(g);144 /// \brief Function to count the arcs in the graph. 145 /// 146 /// This function counts the arcs in the graph. 147 /// The complexity of the function is O(e) but for some 148 /// graph structures it is specialized to run in O(1). 149 /// 150 /// If the graph contains a \e arcNum() member function and a 151 /// \e EdgeNumTag tag then this function calls directly the member 152 /// function to query the cardinality of the arc set. 153 template <typename Graph> 154 inline int countArcs(const Graph& g) { 155 return _graph_utils_bits::CountArcsSelector<Graph>::count(g); 189 156 } 190 157 191 namespace _digraph_utils_bits { 192 193 template <typename Digraph, typename Enable = void> 194 struct CountBluesSelector { 195 static int count(const Digraph &g) { 196 return countItems<Digraph, typename Digraph::Blue>(g); 158 // Edge counting: 159 namespace _graph_utils_bits { 160 161 template <typename Graph, typename Enable = void> 162 struct CountEdgesSelector { 163 static int count(const Graph &g) { 164 return countItems<Graph, typename Graph::Edge>(g); 197 165 } 198 166 }; 199 167 200 template <typename Digraph>201 struct Count BluesSelector<202 Digraph, typename203 enable_if<typename Digraph::NodeNumTag, void>::type>168 template <typename Graph> 169 struct CountEdgesSelector< 170 Graph, 171 typename enable_if<typename Graph::EdgeNumTag, void>::type> 204 172 { 205 static int count(const Digraph &g) {206 return g. blueNum();173 static int count(const Graph &g) { 174 return g.edgeNum(); 207 175 } 208 176 }; 209 177 } 210 178 211 /// \brief Function to count the blues in the digraph. 212 /// 213 /// This function counts the blues in the digraph. 214 /// The complexity of the function is O(bn) but for some 215 /// digraph structures it is specialized to run in O(1). 216 /// 217 /// If the digraph contains a \e blueNum() member function and a 218 /// \e NodeNumTag tag then this function calls directly the member 219 /// function to query the cardinality of the Bnode set. 220 template <typename Digraph> 221 inline int countBlues(const Digraph& g) { 222 return _digraph_utils_bits::CountBluesSelector<Digraph>::count(g); 179 /// \brief Function to count the edges in the graph. 180 /// 181 /// This function counts the edges in the graph. 182 /// The complexity of the function is O(m) but for some 183 /// graph structures it is specialized to run in O(1). 184 /// 185 /// If the graph contains a \e edgeNum() member function and a 186 /// \e EdgeNumTag tag then this function calls directly the member 187 /// function to query the cardinality of the edge set. 188 template <typename Graph> 189 inline int countEdges(const Graph& g) { 190 return _graph_utils_bits::CountEdgesSelector<Graph>::count(g); 191 223 192 } 224 193 225 194 226 // Arc counting: 227 228 namespace _digraph_utils_bits { 229 230 template <typename Digraph, typename Enable = void> 231 struct CountArcsSelector { 232 static int count(const Digraph &g) { 233 return countItems<Digraph, typename Digraph::Arc>(g); 234 } 235 }; 236 237 template <typename Digraph> 238 struct CountArcsSelector< 239 Digraph, 240 typename enable_if<typename Digraph::ArcNumTag, void>::type> 241 { 242 static int count(const Digraph &g) { 243 return g.arcNum(); 244 } 245 }; 246 } 247 248 /// \brief Function to count the arcs in the digraph. 249 /// 250 /// This function counts the arcs in the digraph. 251 /// The complexity of the function is O(e) but for some 252 /// digraph structures it is specialized to run in O(1). 253 /// 254 /// If the digraph contains a \e arcNum() member function and a 255 /// \e ArcNumTag tag then this function calls directly the member 256 /// function to query the cardinality of the arc set. 257 template <typename Digraph> 258 inline int countArcs(const Digraph& g) { 259 return _digraph_utils_bits::CountArcsSelector<Digraph>::count(g); 260 } 261 262 // Undirected arc counting: 263 namespace _digraph_utils_bits { 264 265 template <typename Digraph, typename Enable = void> 266 struct CountEdgesSelector { 267 static int count(const Digraph &g) { 268 return countItems<Digraph, typename Digraph::Edge>(g); 269 } 270 }; 271 272 template <typename Digraph> 273 struct CountEdgesSelector< 274 Digraph, 275 typename enable_if<typename Digraph::ArcNumTag, void>::type> 276 { 277 static int count(const Digraph &g) { 278 return g.edgeNum(); 279 } 280 }; 281 } 282 283 /// \brief Function to count the edges in the digraph. 284 /// 285 /// This function counts the edges in the digraph. 286 /// The complexity of the function is O(e) but for some 287 /// digraph structures it is specialized to run in O(1). 288 /// 289 /// If the digraph contains a \e edgeNum() member function and a 290 /// \e ArcNumTag tag then this function calls directly the member 291 /// function to query the cardinality of the edge set. 292 template <typename Digraph> 293 inline int countEdges(const Digraph& g) { 294 return _digraph_utils_bits::CountEdgesSelector<Digraph>::count(g); 295 296 } 297 298 299 template <typename Digraph, typename DegIt> 300 inline int countNodeDegree(const Digraph& _g, const typename Digraph::Node& _n) { 195 template <typename Graph, typename DegIt> 196 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { 301 197 int num = 0; 302 198 for (DegIt it(_g, _n); it != INVALID; ++it) { … … 309 205 /// 310 206 /// This function counts the number of the outarcs from node \c n 311 /// in the digraph.312 template <typename Digraph>313 inline int countOutArcs(const Digraph& _g, const typename Digraph::Node& _n) {314 return countNodeDegree< Digraph, typename Digraph::OutArcIt>(_g, _n);207 /// in the graph. 208 template <typename Graph> 209 inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) { 210 return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n); 315 211 } 316 212 … … 318 214 /// 319 215 /// This function counts the number of the inarcs to node \c n 320 /// in the digraph.321 template <typename Digraph>322 inline int countInArcs(const Digraph& _g, const typename Digraph::Node& _n) {323 return countNodeDegree< Digraph, typename Digraph::InArcIt>(_g, _n);216 /// in the graph. 217 template <typename Graph> 218 inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) { 219 return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n); 324 220 } 325 221 326 /// \brief Function to count the number of the inc arcs to node \c n.327 /// 328 /// This function counts the number of the inc arcs to node \c n329 /// in the digraph.330 template <typename Digraph>331 inline int countInc Arcs(const Digraph& _g, const typename Digraph::Node& _n) {332 return countNodeDegree< Digraph, typename Digraph::IncArcIt>(_g, _n);222 /// \brief Function to count the number of the incedges to node \c n. 223 /// 224 /// This function counts the number of the incedges to node \c n 225 /// in the graph. 226 template <typename Graph> 227 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { 228 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n); 333 229 } 334 230 335 namespace _ digraph_utils_bits {336 337 template <typename Digraph, typename Enable = void>231 namespace _graph_utils_bits { 232 233 template <typename Graph, typename Enable = void> 338 234 struct FindArcSelector { 339 typedef typename Digraph::Node Node;340 typedef typename Digraph::Arc Arc;341 static Arc find(const Digraph &g, Node u, Node v, Arc e) {235 typedef typename Graph::Node Node; 236 typedef typename Graph::Arc Arc; 237 static Arc find(const Graph &g, Node u, Node v, Arc e) { 342 238 if (e == INVALID) { 343 239 g.firstOut(e, u); … … 352 248 }; 353 249 354 template <typename Digraph>250 template <typename Graph> 355 251 struct FindArcSelector< 356 Digraph,357 typename enable_if<typename Digraph::FindArcTag, void>::type>252 Graph, 253 typename enable_if<typename Graph::FindEdgeTag, void>::type> 358 254 { 359 typedef typename Digraph::Node Node;360 typedef typename Digraph::Arc Arc;361 static Arc find(const Digraph &g, Node u, Node v, Arc prev) {255 typedef typename Graph::Node Node; 256 typedef typename Graph::Arc Arc; 257 static Arc find(const Graph &g, Node u, Node v, Arc prev) { 362 258 return g.findArc(u, v, prev); 363 259 } … … 365 261 } 366 262 367 /// \brief Finds an arc between two nodes of a digraph.368 /// 369 /// Finds an arc from node \c u to node \c v in digraph \c g.263 /// \brief Finds an arc between two nodes of a graph. 264 /// 265 /// Finds an arc from node \c u to node \c v in graph \c g. 370 266 /// 371 267 /// If \c prev is \ref INVALID (this is the default value), then … … 385 281 ///\sa DynArcLookUp 386 282 ///\sa ConArcIt 387 template <typename Digraph>388 inline typename Digraph::Arc389 findArc(const Digraph &g, typename Digraph::Node u, typename Digraph::Node v,390 typename Digraph::Arc prev = INVALID) {391 return _ digraph_utils_bits::FindArcSelector<Digraph>::find(g, u, v, prev);283 template <typename Graph> 284 inline typename Graph::Arc 285 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v, 286 typename Graph::Arc prev = INVALID) { 287 return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev); 392 288 } 393 289 … … 398 294 /// use it the following way: 399 295 ///\code 400 /// for (ConArcIt< Digraph> it(g, src, trg); it != INVALID; ++it) {296 /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) { 401 297 /// ... 402 298 /// } … … 409 305 /// 410 306 /// \author Balazs Dezso 411 template <typename _ Digraph>412 class ConArcIt : public _ Digraph::Arc {307 template <typename _Graph> 308 class ConArcIt : public _Graph::Arc { 413 309 public: 414 310 415 typedef _ Digraph Digraph;416 typedef typename Digraph::Arc Parent;417 418 typedef typename Digraph::Arc Arc;419 typedef typename Digraph::Node Node;311 typedef _Graph Graph; 312 typedef typename Graph::Arc Parent; 313 314 typedef typename Graph::Arc Arc; 315 typedef typename Graph::Node Node; 420 316 421 317 /// \brief Constructor. … … 423 319 /// Construct a new ConArcIt iterating on the arcs which 424 320 /// connects the \c u and \c v node. 425 ConArcIt(const Digraph& g, Node u, Node v) : digraph(g) {426 Parent::operator=(findArc( digraph, u, v));321 ConArcIt(const Graph& g, Node u, Node v) : _graph(g) { 322 Parent::operator=(findArc(_graph, u, v)); 427 323 } 428 324 … … 431 327 /// Construct a new ConArcIt which continues the iterating from 432 328 /// the \c e arc. 433 ConArcIt(const Digraph& g, Arc e) : Parent(e), digraph(g) {}329 ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {} 434 330 435 331 /// \brief Increment operator. … … 437 333 /// It increments the iterator and gives back the next arc. 438 334 ConArcIt& operator++() { 439 Parent::operator=(findArc( digraph, digraph.source(*this),440 digraph.target(*this), *this));335 Parent::operator=(findArc(_graph, _graph.source(*this), 336 _graph.target(*this), *this)); 441 337 return *this; 442 338 } 443 339 private: 444 const Digraph& digraph;340 const Graph& _graph; 445 341 }; 446 342 447 namespace _ digraph_utils_bits {448 449 template <typename Digraph, typename Enable = void>343 namespace _graph_utils_bits { 344 345 template <typename Graph, typename Enable = void> 450 346 struct FindEdgeSelector { 451 typedef typename Digraph::Node Node;452 typedef typename Digraph::Edge Edge;453 static Edge find(const Digraph &g, Node u, Node v, Edge e) {347 typedef typename Graph::Node Node; 348 typedef typename Graph::Edge Edge; 349 static Edge find(const Graph &g, Node u, Node v, Edge e) { 454 350 bool b; 455 351 if (u != v) { … … 478 374 }; 479 375 480 template <typename Digraph>376 template <typename Graph> 481 377 struct FindEdgeSelector< 482 Digraph,483 typename enable_if<typename Digraph::FindArcTag, void>::type>378 Graph, 379 typename enable_if<typename Graph::FindEdgeTag, void>::type> 484 380 { 485 typedef typename Digraph::Node Node;486 typedef typename Digraph::Edge Edge;487 static Edge find(const Digraph &g, Node u, Node v, Edge prev) {381 typedef typename Graph::Node Node; 382 typedef typename Graph::Edge Edge; 383 static Edge find(const Graph &g, Node u, Node v, Edge prev) { 488 384 return g.findEdge(u, v, prev); 489 385 } … … 491 387 } 492 388 493 /// \brief Finds an edge between two nodes of a digraph.494 /// 495 /// Finds an edge from node \c u to node \c v in digraph \c g.496 /// If the node \c u and node \c v is equal then each loop arc497 /// will be enumerated .389 /// \brief Finds an edge between two nodes of a graph. 390 /// 391 /// Finds an edge from node \c u to node \c v in graph \c g. 392 /// If the node \c u and node \c v is equal then each loop edge 393 /// will be enumerated once. 498 394 /// 499 395 /// If \c prev is \ref INVALID (this is the default value), then … … 512 408 ///\sa ConArcIt 513 409 514 template <typename Digraph>515 inline typename Digraph::Edge516 findEdge(const Digraph &g, typename Digraph::Node u, typename Digraph::Node v,517 typename Digraph::Edge p = INVALID) {518 return _ digraph_utils_bits::FindEdgeSelector<Digraph>::find(g, u, v, p);410 template <typename Graph> 411 inline typename Graph::Edge 412 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v, 413 typename Graph::Edge p = INVALID) { 414 return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p); 519 415 } 520 416 … … 525 421 /// use it the following way: 526 422 ///\code 527 /// for (ConEdgeIt< Digraph> it(g, src, trg); it != INVALID; ++it) {423 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) { 528 424 /// ... 529 425 /// } … … 533 429 /// 534 430 /// \author Balazs Dezso 535 template <typename _ Digraph>536 class ConEdgeIt : public _ Digraph::Edge {431 template <typename _Graph> 432 class ConEdgeIt : public _Graph::Edge { 537 433 public: 538 434 539 typedef _ Digraph Digraph;540 typedef typename Digraph::Edge Parent;541 542 typedef typename Digraph::Edge Edge;543 typedef typename Digraph::Node Node;435 typedef _Graph Graph; 436 typedef typename Graph::Edge Parent; 437 438 typedef typename Graph::Edge Edge; 439 typedef typename Graph::Node Node; 544 440 545 441 /// \brief Constructor. 546 442 /// 547 /// Construct a new ConEdgeIt iterating on the arcs which443 /// Construct a new ConEdgeIt iterating on the edges which 548 444 /// connects the \c u and \c v node. 549 ConEdgeIt(const Digraph& g, Node u, Node v) : digraph(g) {550 Parent::operator=(findEdge( digraph, u, v));445 ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) { 446 Parent::operator=(findEdge(_graph, u, v)); 551 447 } 552 448 … … 554 450 /// 555 451 /// Construct a new ConEdgeIt which continues the iterating from 556 /// the \c e arc.557 ConEdgeIt(const Digraph& g, Edge e) : Parent(e), digraph(g) {}452 /// the \c e edge. 453 ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {} 558 454 559 455 /// \brief Increment operator. 560 456 /// 561 /// It increments the iterator and gives back the next arc.457 /// It increments the iterator and gives back the next edge. 562 458 ConEdgeIt& operator++() { 563 Parent::operator=(findEdge( digraph, digraph.source(*this),564 digraph.target(*this), *this));459 Parent::operator=(findEdge(_graph, _graph.source(*this), 460 _graph.target(*this), *this)); 565 461 return *this; 566 462 } 567 463 private: 568 const Digraph& digraph;464 const Graph& _graph; 569 465 }; 570 466 571 /// \brief Copy a map. 572 /// 573 /// This function copies the \c from map to the \c to map. It uses the 574 /// given iterator to iterate on the data structure and it uses the \c ref 575 /// mapping to convert the from's keys to the to's keys. 576 template <typename To, typename From, 577 typename ItemIt, typename Ref> 578 void copyMap(To& to, const From& from, 579 ItemIt it, const Ref& ref) { 580 for (; it != INVALID; ++it) { 581 to[ref[it]] = from[it]; 582 } 583 } 584 585 /// \brief Copy the from map to the to map. 586 /// 587 /// Copy the \c from map to the \c to map. It uses the given iterator 588 /// to iterate on the data structure. 589 template <typename To, typename From, typename ItemIt> 590 void copyMap(To& to, const From& from, ItemIt it) { 591 for (; it != INVALID; ++it) { 592 to[it] = from[it]; 593 } 594 } 595 596 namespace _digraph_utils_bits { 467 namespace _graph_utils_bits { 597 468 598 469 template <typename Digraph, typename Item, typename RefMap> … … 728 599 }; 729 600 730 template <typename BpGraph, typename Enable = void>731 struct BpGraphCopySelector {732 template <typename From, typename RedRefMap,733 typename BlueRefMap, typename EdgeRefMap>734 static void copy(BpGraph &to, const From& from,735 RedRefMap& redRefMap, BlueRefMap& blueRefMap,736 EdgeRefMap& edgeRefMap) {737 for (typename From::RedIt it(from); it != INVALID; ++it) {738 redRefMap[it] = to.addRed();739 }740 for (typename From::BlueIt it(from); it != INVALID; ++it) {741 blueRefMap[it] = to.addBlue();742 }743 for (typename From::EdgeIt it(from); it != INVALID; ++it) {744 edgeRefMap[it] = to.addArc(redRefMap[from.red(it)],745 blueRefMap[from.blue(it)]);746 }747 }748 };749 750 template <typename BpGraph>751 struct BpGraphCopySelector<752 BpGraph,753 typename enable_if<typename BpGraph::BuildTag, void>::type>754 {755 template <typename From, typename RedRefMap,756 typename BlueRefMap, typename EdgeRefMap>757 static void copy(BpGraph &to, const From& from,758 RedRefMap& redRefMap, BlueRefMap& blueRefMap,759 EdgeRefMap& edgeRefMap) {760 to.build(from, redRefMap, blueRefMap, edgeRefMap);761 }762 };763 764 765 601 } 766 602 … … 769 605 /// Class to copy a digraph to another digraph (duplicate a digraph). The 770 606 /// simplest way of using it is through the \c copyDigraph() function. 607 /// 608 /// This class not just make a copy of a graph, but it can create 609 /// references and cross references between the nodes and arcs of 610 /// the two graphs, it can copy maps for use with the newly created 611 /// graph and copy nodes and arcs. 612 /// 613 /// To make a copy from a graph, first an instance of DigraphCopy 614 /// should be created, then the data belongs to the graph should 615 /// assigned to copy. In the end, the \c run() member should be 616 /// called. 617 /// 618 /// The next code copies a graph with several data: 619 ///\code 620 /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); 621 /// // create a reference for the nodes 622 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); 623 /// dc.nodeRef(nr); 624 /// // create a cross reference (inverse) for the arcs 625 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph); 626 /// dc.arcCrossRef(acr); 627 /// // copy an arc map 628 /// OrigGraph::ArcMap<double> oamap(orig_graph); 629 /// NewGraph::ArcMap<double> namap(new_graph); 630 /// dc.arcMap(namap, oamap); 631 /// // copy a node 632 /// OrigGraph::Node on; 633 /// NewGraph::Node nn; 634 /// dc.node(nn, on); 635 /// // Executions of copy 636 /// dc.run(); 637 ///\endcode 771 638 template <typename To, typename From> 772 639 class DigraphCopy { … … 792 659 /// It copies the content of the \c _from digraph into the 793 660 /// \c _to digraph. 794 DigraphCopy(To& _to, const From& _from)795 : from(_from), to(_to) {}661 DigraphCopy(To& to, const From& from) 662 : _from(from), _to(to) {} 796 663 797 664 /// \brief Destructor of the DigraphCopy … … 799 666 /// Destructor of the DigraphCopy 800 667 ~DigraphCopy() { 801 for (int i = 0; i < int( nodeMapCopies.size()); ++i) {802 delete nodeMapCopies[i];803 } 804 for (int i = 0; i < int( arcMapCopies.size()); ++i) {805 delete arcMapCopies[i];668 for (int i = 0; i < int(_node_maps.size()); ++i) { 669 delete _node_maps[i]; 670 } 671 for (int i = 0; i < int(_arc_maps.size()); ++i) { 672 delete _arc_maps[i]; 806 673 } 807 674 … … 810 677 /// \brief Copies the node references into the given map. 811 678 /// 812 /// Copies the node references into the given map. 679 /// Copies the node references into the given map. The parameter 680 /// should be a map, which key type is the Node type of the source 681 /// graph, while the value type is the Node type of the 682 /// destination graph. 813 683 template <typename NodeRef> 814 684 DigraphCopy& nodeRef(NodeRef& map) { 815 nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,816 685 _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, 686 NodeRefMap, NodeRef>(map)); 817 687 return *this; 818 688 } … … 821 691 /// 822 692 /// Copies the node cross references (reverse references) into 823 /// the given map. 693 /// the given map. The parameter should be a map, which key type 694 /// is the Node type of the destination graph, while the value type is 695 /// the Node type of the source graph. 824 696 template <typename NodeCrossRef> 825 697 DigraphCopy& nodeCrossRef(NodeCrossRef& map) { 826 nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,827 698 _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node, 699 NodeRefMap, NodeCrossRef>(map)); 828 700 return *this; 829 701 } … … 831 703 /// \brief Make copy of the given map. 832 704 /// 833 /// Makes copy of the given map for the newly created digraph. 834 /// The new map's key type is the to digraph's node type, 835 /// and the copied map's key type is the from digraph's node 836 /// type. 705 /// Makes copy of the given map for the newly created digraph. 706 /// The new map's key type is the destination graph's node type, 707 /// and the copied map's key type is the source graph's node type. 837 708 template <typename ToMap, typename FromMap> 838 709 DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { 839 nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,840 710 _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, 711 NodeRefMap, ToMap, FromMap>(tmap, map)); 841 712 return *this; 842 713 } … … 846 717 /// Make a copy of the given node. 847 718 DigraphCopy& node(TNode& tnode, const Node& snode) { 848 nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,849 719 _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, 720 NodeRefMap, TNode>(tnode, snode)); 850 721 return *this; 851 722 } … … 856 727 template <typename ArcRef> 857 728 DigraphCopy& arcRef(ArcRef& map) { 858 arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,859 729 _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, 730 ArcRefMap, ArcRef>(map)); 860 731 return *this; 861 732 } … … 867 738 template <typename ArcCrossRef> 868 739 DigraphCopy& arcCrossRef(ArcCrossRef& map) { 869 arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,870 740 _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc, 741 ArcRefMap, ArcCrossRef>(map)); 871 742 return *this; 872 743 } … … 880 751 template <typename ToMap, typename FromMap> 881 752 DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) { 882 arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,883 753 _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, 754 ArcRefMap, ToMap, FromMap>(tmap, map)); 884 755 return *this; 885 756 } … … 889 760 /// Make a copy of the given arc. 890 761 DigraphCopy& arc(TArc& tarc, const Arc& sarc) { 891 arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,892 762 _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, 763 ArcRefMap, TArc>(tarc, sarc)); 893 764 return *this; 894 765 } … … 898 769 /// Executes the copies. 899 770 void run() { 900 NodeRefMap nodeRefMap( from);901 ArcRefMap arcRefMap( from);902 _ digraph_utils_bits::DigraphCopySelector<To>::903 copy( to,from, nodeRefMap, arcRefMap);904 for (int i = 0; i < int( nodeMapCopies.size()); ++i) {905 nodeMapCopies[i]>copy(from, nodeRefMap);906 } 907 for (int i = 0; i < int( arcMapCopies.size()); ++i) {908 arcMapCopies[i]>copy(from, arcRefMap);771 NodeRefMap nodeRefMap(_from); 772 ArcRefMap arcRefMap(_from); 773 _graph_utils_bits::DigraphCopySelector<To>:: 774 copy(_to, _from, nodeRefMap, arcRefMap); 775 for (int i = 0; i < int(_node_maps.size()); ++i) { 776 _node_maps[i]>copy(_from, nodeRefMap); 777 } 778 for (int i = 0; i < int(_arc_maps.size()); ++i) { 779 _arc_maps[i]>copy(_from, arcRefMap); 909 780 } 910 781 } … … 913 784 914 785 915 const From& from;916 To& to;917 918 std::vector<_ digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >919 nodeMapCopies;920 921 std::vector<_ digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >922 arcMapCopies;786 const From& _from; 787 To& _to; 788 789 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 790 _node_maps; 791 792 std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 793 _arc_maps; 923 794 924 795 }; … … 926 797 /// \brief Copy a digraph to another digraph. 927 798 /// 928 /// Copy a digraph to another digraph. 929 /// The usage of the function:930 /// 799 /// Copy a digraph to another digraph. The complete usage of the 800 /// function is detailed in the DigraphCopy class, but a short 801 /// example shows a basic work: 931 802 ///\code 932 803 /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); … … 944 815 } 945 816 946 /// \brief Class to copy an graph. 947 /// 948 /// Class to copy an graph to another digraph (duplicate a digraph). 949 /// The simplest way of using it is through the \c copyGraph() function. 817 /// \brief Class to copy a graph. 818 /// 819 /// Class to copy a graph to another graph (duplicate a graph). The 820 /// simplest way of using it is through the \c copyGraph() function. 821 /// 822 /// This class not just make a copy of a graph, but it can create 823 /// references and cross references between the nodes, edges and arcs of 824 /// the two graphs, it can copy maps for use with the newly created 825 /// graph and copy nodes, edges and arcs. 826 /// 827 /// To make a copy from a graph, first an instance of GraphCopy 828 /// should be created, then the data belongs to the graph should 829 /// assigned to copy. In the end, the \c run() member should be 830 /// called. 831 /// 832 /// The next code copies a graph with several data: 833 ///\code 834 /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); 835 /// // create a reference for the nodes 836 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); 837 /// dc.nodeRef(nr); 838 /// // create a cross reference (inverse) for the edges 839 /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph); 840 /// dc.edgeCrossRef(ecr); 841 /// // copy an arc map 842 /// OrigGraph::ArcMap<double> oamap(orig_graph); 843 /// NewGraph::ArcMap<double> namap(new_graph); 844 /// dc.arcMap(namap, oamap); 845 /// // copy a node 846 /// OrigGraph::Node on; 847 /// NewGraph::Node nn; 848 /// dc.node(nn, on); 849 /// // Executions of copy 850 /// dc.run(); 851 ///\endcode 950 852 template <typename To, typename From> 951 853 class GraphCopy { … … 967 869 968 870 struct ArcRefMap { 969 ArcRefMap(const To& _to, const From& _from,970 const EdgeRefMap& _edge_ref, const NodeRefMap& _node_ref)971 : to(_to), from(_from),972 edge_ref(_edge_ref), node_ref(_node_ref) {}871 ArcRefMap(const To& to, const From& from, 872 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) 873 : _to(to), _from(from), 874 _edge_ref(edge_ref), _node_ref(node_ref) {} 973 875 974 876 typedef typename From::Arc Key; … … 977 879 Value operator[](const Key& key) const { 978 880 bool forward = 979 (from.direction(key) == 980 (node_ref[from.source(static_cast<const Edge&>(key))] == 981 to.source(edge_ref[static_cast<const Edge&>(key)]))); 982 return to.direct(edge_ref[key], forward); 881 (_from.direction(key) == 882 (_node_ref[_from.source(key)] == _to.source(_edge_ref[key]))); 883 return _to.direct(_edge_ref[key], forward); 983 884 } 984 885 985 const To& to;986 const From& from;987 const EdgeRefMap& edge_ref;988 const NodeRefMap& node_ref;886 const To& _to; 887 const From& _from; 888 const EdgeRefMap& _edge_ref; 889 const NodeRefMap& _node_ref; 989 890 }; 990 891 … … 993 894 994 895 995 /// \brief Constructor for the DigraphCopy.996 /// 997 /// It copies the content of the \c _from digraph into the998 /// \c _to digraph.999 GraphCopy(To& _to, const From& _from)1000 : from(_from), to(_to) {}1001 1002 /// \brief Destructor of the DigraphCopy1003 /// 1004 /// Destructor of the DigraphCopy896 /// \brief Constructor for the GraphCopy. 897 /// 898 /// It copies the content of the \c _from graph into the 899 /// \c _to graph. 900 GraphCopy(To& to, const From& from) 901 : _from(from), _to(to) {} 902 903 /// \brief Destructor of the GraphCopy 904 /// 905 /// Destructor of the GraphCopy 1005 906 ~GraphCopy() { 1006 for (int i = 0; i < int( nodeMapCopies.size()); ++i) {1007 delete nodeMapCopies[i];1008 } 1009 for (int i = 0; i < int( arcMapCopies.size()); ++i) {1010 delete arcMapCopies[i];1011 } 1012 for (int i = 0; i < int( edgeMapCopies.size()); ++i) {1013 delete edgeMapCopies[i];907 for (int i = 0; i < int(_node_maps.size()); ++i) { 908 delete _node_maps[i]; 909 } 910 for (int i = 0; i < int(_arc_maps.size()); ++i) { 911 delete _arc_maps[i]; 912 } 913 for (int i = 0; i < int(_edge_maps.size()); ++i) { 914 delete _edge_maps[i]; 1014 915 } 1015 916 … … 1021 922 template <typename NodeRef> 1022 923 GraphCopy& nodeRef(NodeRef& map) { 1023 nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,1024 924 _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, 925 NodeRefMap, NodeRef>(map)); 1025 926 return *this; 1026 927 } … … 1032 933 template <typename NodeCrossRef> 1033 934 GraphCopy& nodeCrossRef(NodeCrossRef& map) { 1034 nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,1035 935 _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node, 936 NodeRefMap, NodeCrossRef>(map)); 1036 937 return *this; 1037 938 } … … 1039 940 /// \brief Make copy of the given map. 1040 941 /// 1041 /// Makes copy of the given map for the newly created digraph.1042 /// The new map's key type is the to digraph's node type,1043 /// and the copied map's key type is the from digraph's node942 /// Makes copy of the given map for the newly created graph. 943 /// The new map's key type is the to graph's node type, 944 /// and the copied map's key type is the from graph's node 1044 945 /// type. 1045 946 template <typename ToMap, typename FromMap> 1046 947 GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { 1047 nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,1048 948 _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, 949 NodeRefMap, ToMap, FromMap>(tmap, map)); 1049 950 return *this; 1050 951 } … … 1054 955 /// Make a copy of the given node. 1055 956 GraphCopy& node(TNode& tnode, const Node& snode) { 1056 nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,1057 957 _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, 958 NodeRefMap, TNode>(tnode, snode)); 1058 959 return *this; 1059 960 } … … 1064 965 template <typename ArcRef> 1065 966 GraphCopy& arcRef(ArcRef& map) { 1066 arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,1067 967 _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, 968 ArcRefMap, ArcRef>(map)); 1068 969 return *this; 1069 970 } … … 1075 976 template <typename ArcCrossRef> 1076 977 GraphCopy& arcCrossRef(ArcCrossRef& map) { 1077 arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,1078 978 _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc, 979 ArcRefMap, ArcCrossRef>(map)); 1079 980 return *this; 1080 981 } … … 1082 983 /// \brief Make copy of the given map. 1083 984 /// 1084 /// Makes copy of the given map for the newly created digraph.1085 /// The new map's key type is the to digraph's arc type,1086 /// and the copied map's key type is the from digraph's arc985 /// Makes copy of the given map for the newly created graph. 986 /// The new map's key type is the to graph's arc type, 987 /// and the copied map's key type is the from graph's arc 1087 988 /// type. 1088 989 template <typename ToMap, typename FromMap> 1089 990 GraphCopy& arcMap(ToMap& tmap, const FromMap& map) { 1090 arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,1091 991 _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, 992 ArcRefMap, ToMap, FromMap>(tmap, map)); 1092 993 return *this; 1093 994 } … … 1097 998 /// Make a copy of the given arc. 1098 999 GraphCopy& arc(TArc& tarc, const Arc& sarc) { 1099 arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,1100 1000 _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, 1001 ArcRefMap, TArc>(tarc, sarc)); 1101 1002 return *this; 1102 1003 } … … 1107 1008 template <typename EdgeRef> 1108 1009 GraphCopy& edgeRef(EdgeRef& map) { 1109 edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,1110 1010 _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge, 1011 EdgeRefMap, EdgeRef>(map)); 1111 1012 return *this; 1112 1013 } … … 1118 1019 template <typename EdgeCrossRef> 1119 1020 GraphCopy& edgeCrossRef(EdgeCrossRef& map) { 1120 edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,1121 1021 _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, 1022 Edge, EdgeRefMap, EdgeCrossRef>(map)); 1122 1023 return *this; 1123 1024 } … … 1125 1026 /// \brief Make copy of the given map. 1126 1027 /// 1127 /// Makes copy of the given map for the newly created digraph.1128 /// The new map's key type is the to digraph's edge type,1129 /// and the copied map's key type is the from digraph's edge1028 /// Makes copy of the given map for the newly created graph. 1029 /// The new map's key type is the to graph's edge type, 1030 /// and the copied map's key type is the from graph's edge 1130 1031 /// type. 1131 1032 template <typename ToMap, typename FromMap> 1132 1033 GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) { 1133 edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,1134 1034 _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge, 1035 EdgeRefMap, ToMap, FromMap>(tmap, map)); 1135 1036 return *this; 1136 1037 } … … 1140 1041 /// Make a copy of the given edge. 1141 1042 GraphCopy& edge(TEdge& tedge, const Edge& sedge) { 1142 edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,1143 1043 _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge, 1044 EdgeRefMap, TEdge>(tedge, sedge)); 1144 1045 return *this; 1145 1046 } … … 1149 1050 /// Executes the copies. 1150 1051 void run() { 1151 NodeRefMap nodeRefMap( from);1152 EdgeRefMap edgeRefMap( from);1153 ArcRefMap arcRefMap( to,from, edgeRefMap, nodeRefMap);1154 _ digraph_utils_bits::GraphCopySelector<To>::1155 copy( to,from, nodeRefMap, edgeRefMap);1156 for (int i = 0; i < int( nodeMapCopies.size()); ++i) {1157 nodeMapCopies[i]>copy(from, nodeRefMap);1158 } 1159 for (int i = 0; i < int( edgeMapCopies.size()); ++i) {1160 edgeMapCopies[i]>copy(from, edgeRefMap);1161 } 1162 for (int i = 0; i < int( arcMapCopies.size()); ++i) {1163 arcMapCopies[i]>copy(from, arcRefMap);1052 NodeRefMap nodeRefMap(_from); 1053 EdgeRefMap edgeRefMap(_from); 1054 ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap); 1055 _graph_utils_bits::GraphCopySelector<To>:: 1056 copy(_to, _from, nodeRefMap, edgeRefMap); 1057 for (int i = 0; i < int(_node_maps.size()); ++i) { 1058 _node_maps[i]>copy(_from, nodeRefMap); 1059 } 1060 for (int i = 0; i < int(_edge_maps.size()); ++i) { 1061 _edge_maps[i]>copy(_from, edgeRefMap); 1062 } 1063 for (int i = 0; i < int(_arc_maps.size()); ++i) { 1064 _arc_maps[i]>copy(_from, arcRefMap); 1164 1065 } 1165 1066 } … … 1167 1068 private: 1168 1069 1169 const From& from;1170 To& to;1171 1172 std::vector<_ digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >1173 nodeMapCopies;1174 1175 std::vector<_ digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >1176 arcMapCopies;1177 1178 std::vector<_ digraph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >1179 edgeMapCopies;1070 const From& _from; 1071 To& _to; 1072 1073 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 1074 _node_maps; 1075 1076 std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 1077 _arc_maps; 1078 1079 std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 1080 _edge_maps; 1180 1081 1181 1082 }; 1182 1083 1183 /// \brief Copy a n graph to another digraph.1184 /// 1185 /// Copy a n graph to another digraph.1186 /// The usage of the function:1187 /// 1084 /// \brief Copy a graph to another graph. 1085 /// 1086 /// Copy a graph to another graph. The complete usage of the 1087 /// function is detailed in the GraphCopy class, but a short 1088 /// example shows a basic work: 1188 1089 ///\code 1189 1090 /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); … … 1191 1092 /// 1192 1093 /// After the copy the \c nr map will contain the mapping from the 1193 /// nodes of the \c from digraph to the nodes of the \c to digraph and1194 /// \c ecr will contain the mapping from the arcs of the \c to digraph1195 /// to the arcs of the \c from digraph.1094 /// nodes of the \c from graph to the nodes of the \c to graph and 1095 /// \c ecr will contain the mapping from the arcs of the \c to graph 1096 /// to the arcs of the \c from graph. 1196 1097 /// 1197 1098 /// \see GraphCopy … … 1202 1103 } 1203 1104 1204 /// \brief Class to copy a bipartite digraph.1205 ///1206 /// Class to copy a bipartite digraph to another digraph1207 /// (duplicate a digraph). The simplest way of using it is through1208 /// the \c copyBpGraph() function.1209 template <typename To, typename From>1210 class BpGraphCopy {1211 private:1212 1213 typedef typename From::Node Node;1214 typedef typename From::Red Red;1215 typedef typename From::Blue Blue;1216 typedef typename From::NodeIt NodeIt;1217 typedef typename From::Arc Arc;1218 typedef typename From::ArcIt ArcIt;1219 typedef typename From::Edge Edge;1220 typedef typename From::EdgeIt EdgeIt;1221 1222 typedef typename To::Node TNode;1223 typedef typename To::Arc TArc;1224 typedef typename To::Edge TEdge;1225 1226 typedef typename From::template RedMap<TNode> RedRefMap;1227 typedef typename From::template BlueMap<TNode> BlueRefMap;1228 typedef typename From::template EdgeMap<TEdge> EdgeRefMap;1229 1230 struct NodeRefMap {1231 NodeRefMap(const From& _from, const RedRefMap& _red_ref,1232 const BlueRefMap& _blue_ref)1233 : from(_from), red_ref(_red_ref), blue_ref(_blue_ref) {}1234 1235 typedef typename From::Node Key;1236 typedef typename To::Node Value;1237 1238 Value operator[](const Key& key) const {1239 return from.red(key) ? red_ref[key] : blue_ref[key];1240 }1241 1242 const From& from;1243 const RedRefMap& red_ref;1244 const BlueRefMap& blue_ref;1245 };1246 1247 struct ArcRefMap {1248 ArcRefMap(const To& _to, const From& _from,1249 const EdgeRefMap& _edge_ref, const NodeRefMap& _node_ref)1250 : to(_to), from(_from),1251 edge_ref(_edge_ref), node_ref(_node_ref) {}1252 1253 typedef typename From::Arc Key;1254 typedef typename To::Arc Value;1255 1256 Value operator[](const Key& key) const {1257 bool forward =1258 (from.direction(key) ==1259 (node_ref[from.source(static_cast<const Edge&>(key))] ==1260 to.source(edge_ref[static_cast<const Edge&>(key)])));1261 return to.direct(edge_ref[key], forward);1262 }1263 1264 const To& to;1265 const From& from;1266 const EdgeRefMap& edge_ref;1267 const NodeRefMap& node_ref;1268 };1269 1270 public:1271 1272 1273 /// \brief Constructor for the DigraphCopy.1274 ///1275 /// It copies the content of the \c _from digraph into the1276 /// \c _to digraph.1277 BpGraphCopy(To& _to, const From& _from)1278 : from(_from), to(_to) {}1279 1280 /// \brief Destructor of the DigraphCopy1281 ///1282 /// Destructor of the DigraphCopy1283 ~BpGraphCopy() {1284 for (int i = 0; i < int(redMapCopies.size()); ++i) {1285 delete redMapCopies[i];1286 }1287 for (int i = 0; i < int(blueMapCopies.size()); ++i) {1288 delete blueMapCopies[i];1289 }1290 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {1291 delete nodeMapCopies[i];1292 }1293 for (int i = 0; i < int(arcMapCopies.size()); ++i) {1294 delete arcMapCopies[i];1295 }1296 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {1297 delete edgeMapCopies[i];1298 }1299 1300 }1301 1302 /// \brief Copies the Anode references into the given map.1303 ///1304 /// Copies the Anode references into the given map.1305 template <typename RedRef>1306 BpGraphCopy& redRef(RedRef& map) {1307 redMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Red,1308 RedRefMap, RedRef>(map));1309 return *this;1310 }1311 1312 /// \brief Copies the Anode cross references into the given map.1313 ///1314 /// Copies the Anode cross references (reverse references) into1315 /// the given map.1316 template <typename RedCrossRef>1317 BpGraphCopy& redCrossRef(RedCrossRef& map) {1318 redMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,1319 Red, RedRefMap, RedCrossRef>(map));1320 return *this;1321 }1322 1323 /// \brief Make copy of the given Anode map.1324 ///1325 /// Makes copy of the given map for the newly created digraph.1326 /// The new map's key type is the to digraph's node type,1327 /// and the copied map's key type is the from digraph's node1328 /// type.1329 template <typename ToMap, typename FromMap>1330 BpGraphCopy& redMap(ToMap& tmap, const FromMap& map) {1331 redMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Red,1332 RedRefMap, ToMap, FromMap>(tmap, map));1333 return *this;1334 }1335 1336 /// \brief Copies the Bnode references into the given map.1337 ///1338 /// Copies the Bnode references into the given map.1339 template <typename BlueRef>1340 BpGraphCopy& blueRef(BlueRef& map) {1341 blueMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Blue,1342 BlueRefMap, BlueRef>(map));1343 return *this;1344 }1345 1346 /// \brief Copies the Bnode cross references into the given map.1347 ///1348 /// Copies the Bnode cross references (reverse references) into1349 /// the given map.1350 template <typename BlueCrossRef>1351 BpGraphCopy& blueCrossRef(BlueCrossRef& map) {1352 blueMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,1353 Blue, BlueRefMap, BlueCrossRef>(map));1354 return *this;1355 }1356 1357 /// \brief Make copy of the given Bnode map.1358 ///1359 /// Makes copy of the given map for the newly created digraph.1360 /// The new map's key type is the to digraph's node type,1361 /// and the copied map's key type is the from digraph's node1362 /// type.1363 template <typename ToMap, typename FromMap>1364 BpGraphCopy& blueMap(ToMap& tmap, const FromMap& map) {1365 blueMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Blue,1366 BlueRefMap, ToMap, FromMap>(tmap, map));1367 return *this;1368 }1369 /// \brief Copies the node references into the given map.1370 ///1371 /// Copies the node references into the given map.1372 template <typename NodeRef>1373 BpGraphCopy& nodeRef(NodeRef& map) {1374 nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,1375 NodeRefMap, NodeRef>(map));1376 return *this;1377 }1378 1379 /// \brief Copies the node cross references into the given map.1380 ///1381 /// Copies the node cross references (reverse references) into1382 /// the given map.1383 template <typename NodeCrossRef>1384 BpGraphCopy& nodeCrossRef(NodeCrossRef& map) {1385 nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,1386 NodeRefMap, NodeCrossRef>(map));1387 return *this;1388 }1389 1390 /// \brief Make copy of the given map.1391 ///1392 /// Makes copy of the given map for the newly created digraph.1393 /// The new map's key type is the to digraph's node type,1394 /// and the copied map's key type is the from digraph's node1395 /// type.1396 template <typename ToMap, typename FromMap>1397 BpGraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {1398 nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,1399 NodeRefMap, ToMap, FromMap>(tmap, map));1400 return *this;1401 }1402 1403 /// \brief Make a copy of the given node.1404 ///1405 /// Make a copy of the given node.1406 BpGraphCopy& node(TNode& tnode, const Node& snode) {1407 nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,1408 NodeRefMap, TNode>(tnode, snode));1409 return *this;1410 }1411 1412 /// \brief Copies the arc references into the given map.1413 ///1414 /// Copies the arc references into the given map.1415 template <typename ArcRef>1416 BpGraphCopy& arcRef(ArcRef& map) {1417 arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,1418 ArcRefMap, ArcRef>(map));1419 return *this;1420 }1421 1422 /// \brief Copies the arc cross references into the given map.1423 ///1424 /// Copies the arc cross references (reverse references) into1425 /// the given map.1426 template <typename ArcCrossRef>1427 BpGraphCopy& arcCrossRef(ArcCrossRef& map) {1428 arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,1429 ArcRefMap, ArcCrossRef>(map));1430 return *this;1431 }1432 1433 /// \brief Make copy of the given map.1434 ///1435 /// Makes copy of the given map for the newly created digraph.1436 /// The new map's key type is the to digraph's arc type,1437 /// and the copied map's key type is the from digraph's arc1438 /// type.1439 template <typename ToMap, typename FromMap>1440 BpGraphCopy& arcMap(ToMap& tmap, const FromMap& map) {1441 arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,1442 ArcRefMap, ToMap, FromMap>(tmap, map));1443 return *this;1444 }1445 1446 /// \brief Make a copy of the given arc.1447 ///1448 /// Make a copy of the given arc.1449 BpGraphCopy& arc(TArc& tarc, const Arc& sarc) {1450 arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,1451 ArcRefMap, TArc>(tarc, sarc));1452 return *this;1453 }1454 1455 /// \brief Copies the edge references into the given map.1456 ///1457 /// Copies the edge references into the given map.1458 template <typename EdgeRef>1459 BpGraphCopy& edgeRef(EdgeRef& map) {1460 edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,1461 EdgeRefMap, EdgeRef>(map));1462 return *this;1463 }1464 1465 /// \brief Copies the edge cross references into the given map.1466 ///1467 /// Copies the edge cross references (reverse1468 /// references) into the given map.1469 template <typename EdgeCrossRef>1470 BpGraphCopy& edgeCrossRef(EdgeCrossRef& map) {1471 edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,1472 Edge, EdgeRefMap, EdgeCrossRef>(map));1473 return *this;1474 }1475 1476 /// \brief Make copy of the given map.1477 ///1478 /// Makes copy of the given map for the newly created digraph.1479 /// The new map's key type is the to digraph's edge type,1480 /// and the copied map's key type is the from digraph's edge1481 /// type.1482 template <typename ToMap, typename FromMap>1483 BpGraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {1484 edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,1485 EdgeRefMap, ToMap, FromMap>(tmap, map));1486 return *this;1487 }1488 1489 /// \brief Make a copy of the given edge.1490 ///1491 /// Make a copy of the given edge.1492 BpGraphCopy& edge(TEdge& tedge, const Edge& sedge) {1493 edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,1494 EdgeRefMap, TEdge>(tedge, sedge));1495 return *this;1496 }1497 1498 /// \brief Executes the copies.1499 ///1500 /// Executes the copies.1501 void run() {1502 RedRefMap redRefMap(from);1503 BlueRefMap blueRefMap(from);1504 NodeRefMap nodeRefMap(from, redRefMap, blueRefMap);1505 EdgeRefMap edgeRefMap(from);1506 ArcRefMap arcRefMap(to, from, edgeRefMap, nodeRefMap);1507 _digraph_utils_bits::BpGraphCopySelector<To>::1508 copy(to, from, redRefMap, blueRefMap, edgeRefMap);1509 for (int i = 0; i < int(redMapCopies.size()); ++i) {1510 redMapCopies[i]>copy(from, redRefMap);1511 }1512 for (int i = 0; i < int(blueMapCopies.size()); ++i) {1513 blueMapCopies[i]>copy(from, blueRefMap);1514 }1515 for (int i = 0; i < int(nodeMapCopies.size()); ++i) {1516 nodeMapCopies[i]>copy(from, nodeRefMap);1517 }1518 for (int i = 0; i < int(edgeMapCopies.size()); ++i) {1519 edgeMapCopies[i]>copy(from, edgeRefMap);1520 }1521 for (int i = 0; i < int(arcMapCopies.size()); ++i) {1522 arcMapCopies[i]>copy(from, arcRefMap);1523 }1524 }1525 1526 private:1527 1528 const From& from;1529 To& to;1530 1531 std::vector<_digraph_utils_bits::MapCopyBase<From, Red, RedRefMap>* >1532 redMapCopies;1533 1534 std::vector<_digraph_utils_bits::MapCopyBase<From, Blue, BlueRefMap>* >1535 blueMapCopies;1536 1537 std::vector<_digraph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >1538 nodeMapCopies;1539 1540 std::vector<_digraph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >1541 arcMapCopies;1542 1543 std::vector<_digraph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >1544 edgeMapCopies;1545 1546 };1547 1548 /// \brief Copy a bipartite digraph to another digraph.1549 ///1550 /// Copy a bipartite digraph to another digraph.1551 /// The usage of the function:1552 ///1553 ///\code1554 /// copyBpGraph(trg, src).redRef(anr).arcCrossRef(ecr).run();1555 ///\endcode1556 ///1557 /// After the copy the \c nr map will contain the mapping from the1558 /// nodes of the \c from digraph to the nodes of the \c to digraph and1559 /// \c ecr will contain the mapping from the arcs of the \c to digraph1560 /// to the arcs of the \c from digraph.1561 ///1562 /// \see BpGraphCopy1563 template <typename To, typename From>1564 BpGraphCopy<To, From>1565 copyBpGraph(To& to, const From& from) {1566 return BpGraphCopy<To, From>(to, from);1567 }1568 1569 1570 1105 /// @} 1571 1106 1572 /// \addtogroup digraph_maps1107 /// \addtogroup graph_maps 1573 1108 /// @{ 1574 1109 1575 /// Provides an immutable and unique id for each item in the digraph.1110 /// Provides an immutable and unique id for each item in the graph. 1576 1111 1577 1112 /// The IdMap class provides a unique and immutable id for each item of the 1578 /// same type (e.g. node) in the digraph. This id is <ul><li>\b unique:1113 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique: 1579 1114 /// different items (nodes) get different ids <li>\b immutable: the id of an 1580 1115 /// item (node) does not change (even if you delete other nodes). </ul> 1581 1116 /// Through this map you get access (i.e. can read) the inner id values of 1582 /// the items stored in the digraph. This map can be inverted with its member1583 /// class \c InverseMap .1584 /// 1585 template <typename _ Digraph, typename _Item>1117 /// the items stored in the graph. This map can be inverted with its member 1118 /// class \c InverseMap or with the \c operator() member. 1119 /// 1120 template <typename _Graph, typename _Item> 1586 1121 class IdMap { 1587 1122 public: 1588 typedef _ Digraph Digraph;1123 typedef _Graph Graph; 1589 1124 typedef int Value; 1590 1125 typedef _Item Item; … … 1594 1129 /// 1595 1130 /// Constructor of the map. 1596 explicit IdMap(const Digraph& _digraph) : digraph(&_digraph) {}1131 explicit IdMap(const Graph& graph) : _graph(&graph) {} 1597 1132 1598 1133 /// \brief Gives back the \e id of the item. 1599 1134 /// 1600 1135 /// Gives back the immutable and unique \e id of the item. 1601 int operator[](const Item& item) const { return digraph>id(item);}1136 int operator[](const Item& item) const { return _graph>id(item);} 1602 1137 1603 1138 /// \brief Gives back the item by its id. 1604 1139 /// 1605 1140 /// Gives back the item by its id. 1606 Item operator()(int id) { return digraph>fromId(id, Item()); }1141 Item operator()(int id) { return _graph>fromId(id, Item()); } 1607 1142 1608 1143 private: 1609 const Digraph* digraph;1144 const Graph* _graph; 1610 1145 1611 1146 public: … … 1621 1156 /// 1622 1157 /// Constructor for creating an idtoitem map. 1623 explicit InverseMap(const Digraph& _digraph) : digraph(&_digraph) {}1158 explicit InverseMap(const Graph& graph) : _graph(&graph) {} 1624 1159 1625 1160 /// \brief Constructor. 1626 1161 /// 1627 1162 /// Constructor for creating an idtoitem map. 1628 explicit InverseMap(const IdMap& idMap) : digraph(idMap.digraph) {}1163 explicit InverseMap(const IdMap& map) : _graph(map._graph) {} 1629 1164 1630 1165 /// \brief Gives back the given item from its id. … … 1632 1167 /// Gives back the given item from its id. 1633 1168 /// 1634 Item operator[](int id) const { return digraph>fromId(id, Item());}1169 Item operator[](int id) const { return _graph>fromId(id, Item());} 1635 1170 1636 1171 private: 1637 const Digraph* digraph;1172 const Graph* _graph; 1638 1173 }; 1639 1174 … … 1641 1176 /// 1642 1177 /// Gives back the inverse of the IdMap. 1643 InverseMap inverse() const { return InverseMap(* digraph);}1178 InverseMap inverse() const { return InverseMap(*_graph);} 1644 1179 1645 1180 }; 1646 1181 1647 1182 1648 /// \brief General invertable digraphmap type.1649 1650 /// This type provides simple invertable digraphmaps.1183 /// \brief General invertable graphmap type. 1184 1185 /// This type provides simple invertable graphmaps. 1651 1186 /// The InvertableMap wraps an arbitrary ReadWriteMap 1652 1187 /// and if a key is set to a new value then store it … … 1656 1191 /// with stl compatible forward iterator. 1657 1192 /// 1658 /// \param _ Digraph The digraph type.1659 /// \param _Item The item type of the digraph.1193 /// \param _Graph The graph type. 1194 /// \param _Item The item type of the graph. 1660 1195 /// \param _Value The value type of the map. 1661 1196 /// 1662 1197 /// \see IterableValueMap 1663 template <typename _ Digraph, typename _Item, typename _Value>1664 class InvertableMap : protected DefaultMap<_ Digraph, _Item, _Value> {1198 template <typename _Graph, typename _Item, typename _Value> 1199 class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> { 1665 1200 private: 1666 1201 1667 typedef DefaultMap<_ Digraph, _Item, _Value> Map;1668 typedef _ Digraph Digraph;1202 typedef DefaultMap<_Graph, _Item, _Value> Map; 1203 typedef _Graph Graph; 1669 1204 1670 1205 typedef std::map<_Value, _Item> Container; 1671 Container invMap;1206 Container _inv_map; 1672 1207 1673 1208 public: … … 1682 1217 /// \brief Constructor. 1683 1218 /// 1684 /// Construct a new InvertableMap for the digraph.1685 /// 1686 explicit InvertableMap(const Digraph& digraph) : Map(digraph) {}1219 /// Construct a new InvertableMap for the graph. 1220 /// 1221 explicit InvertableMap(const Graph& graph) : Map(graph) {} 1687 1222 1688 1223 /// \brief Forward iterator for values. … … 1726 1261 /// range. 1727 1262 ValueIterator beginValue() const { 1728 return ValueIterator( invMap.begin());1263 return ValueIterator(_inv_map.begin()); 1729 1264 } 1730 1265 … … 1736 1271 /// range. 1737 1272 ValueIterator endValue() const { 1738 return ValueIterator( invMap.end());1273 return ValueIterator(_inv_map.end()); 1739 1274 } 1740 1275 … … 1744 1279 void set(const Key& key, const Value& val) { 1745 1280 Value oldval = Map::operator[](key); 1746 typename Container::iterator it = invMap.find(oldval);1747 if (it != invMap.end() && it>second == key) {1748 invMap.erase(it);1281 typename Container::iterator it = _inv_map.find(oldval); 1282 if (it != _inv_map.end() && it>second == key) { 1283 _inv_map.erase(it); 1749 1284 } 1750 invMap.insert(make_pair(val, key));1285 _inv_map.insert(make_pair(val, key)); 1751 1286 Map::set(key, val); 1752 1287 } … … 1764 1299 /// Gives back the item by its value. 1765 1300 Key operator()(const Value& key) const { 1766 typename Container::const_iterator it = invMap.find(key);1767 return it != invMap.end() ? it>second : INVALID;1301 typename Container::const_iterator it = _inv_map.find(key); 1302 return it != _inv_map.end() ? it>second : INVALID; 1768 1303 } 1769 1304 … … 1776 1311 virtual void erase(const Key& key) { 1777 1312 Value val = Map::operator[](key); 1778 typename Container::iterator it = invMap.find(val);1779 if (it != invMap.end() && it>second == key) {1780 invMap.erase(it);1313 typename Container::iterator it = _inv_map.find(val); 1314 if (it != _inv_map.end() && it>second == key) { 1315 _inv_map.erase(it); 1781 1316 } 1782 1317 Map::erase(key); … … 1790 1325 for (int i = 0; i < int(keys.size()); ++i) { 1791 1326 Value val = Map::operator[](keys[i]); 1792 typename Container::iterator it = invMap.find(val);1793 if (it != invMap.end() && it>second == keys[i]) {1794 invMap.erase(it);1327 typename Container::iterator it = _inv_map.find(val); 1328 if (it != _inv_map.end() && it>second == keys[i]) { 1329 _inv_map.erase(it); 1795 1330 } 1796 1331 } … … 1803 1338 /// \c AlterationNotifier. 1804 1339 virtual void clear() { 1805 invMap.clear();1340 _inv_map.clear(); 1806 1341 Map::clear(); 1807 1342 } … … 1818 1353 /// 1819 1354 /// Constructor of the InverseMap. 1820 explicit InverseMap(const InvertableMap& _inverted)1821 : inverted(_inverted) {}1355 explicit InverseMap(const InvertableMap& inverted) 1356 : _inverted(inverted) {} 1822 1357 1823 1358 /// The value type of the InverseMap. … … 1831 1366 /// what was last assigned to the value. 1832 1367 Value operator[](const Key& key) const { 1833 return inverted(key);1368 return _inverted(key); 1834 1369 } 1835 1370 1836 1371 private: 1837 const InvertableMap& inverted;1372 const InvertableMap& _inverted; 1838 1373 }; 1839 1374 … … 1850 1385 1851 1386 /// \brief Provides a mutable, continuous and unique descriptor for each 1852 /// item in the digraph.1387 /// item in the graph. 1853 1388 /// 1854 1389 /// The DescriptorMap class provides a unique and continuous (but mutable) 1855 1390 /// descriptor (id) for each item of the same type (e.g. node) in the 1856 /// digraph. This id is <ul><li>\b unique: different items (nodes) get1391 /// graph. This id is <ul><li>\b unique: different items (nodes) get 1857 1392 /// different ids <li>\b continuous: the range of the ids is the set of 1858 1393 /// integers between 0 and \c n1, where \c n is the number of the items of 1859 1394 /// this type (e.g. nodes) (so the id of a node can change if you delete an 1860 1395 /// other node, i.e. this id is mutable). </ul> This map can be inverted 1861 /// with its member class \c InverseMap .1862 /// 1863 /// \param _ Digraph The digraph class the \c DescriptorMap belongs to.1396 /// with its member class \c InverseMap, or with the \c operator() member. 1397 /// 1398 /// \param _Graph The graph class the \c DescriptorMap belongs to. 1864 1399 /// \param _Item The Item is the Key of the Map. It may be Node, Arc or 1865 1400 /// Edge. 1866 template <typename _ Digraph, typename _Item>1867 class DescriptorMap : protected DefaultMap<_ Digraph, _Item, int> {1401 template <typename _Graph, typename _Item> 1402 class DescriptorMap : protected DefaultMap<_Graph, _Item, int> { 1868 1403 1869 1404 typedef _Item Item; 1870 typedef DefaultMap<_ Digraph, _Item, int> Map;1405 typedef DefaultMap<_Graph, _Item, int> Map; 1871 1406 1872 1407 public: 1873 /// The digraph class of DescriptorMap.1874 typedef _ Digraph Digraph;1408 /// The graph class of DescriptorMap. 1409 typedef _Graph Graph; 1875 1410 1876 1411 /// The key type of DescriptorMap (Node, Arc, Edge). … … 1882 1417 /// 1883 1418 /// Constructor for descriptor map. 1884 explicit DescriptorMap(const Digraph& _digraph) : Map(_digraph) {1419 explicit DescriptorMap(const Graph& _graph) : Map(_graph) { 1885 1420 Item it; 1886 1421 const typename Map::Notifier* nf = Map::notifier(); 1887 1422 for (nf>first(it); it != INVALID; nf>next(it)) { 1888 Map::set(it, invMap.size());1889 invMap.push_back(it);1423 Map::set(it, _inv_map.size()); 1424 _inv_map.push_back(it); 1890 1425 } 1891 1426 } … … 1899 1434 virtual void add(const Item& item) { 1900 1435 Map::add(item); 1901 Map::set(item, invMap.size());1902 invMap.push_back(item);1436 Map::set(item, _inv_map.size()); 1437 _inv_map.push_back(item); 1903 1438 } 1904 1439 … … 1910 1445 Map::add(items); 1911 1446 for (int i = 0; i < int(items.size()); ++i) { 1912 Map::set(items[i], invMap.size());1913 invMap.push_back(items[i]);1447 Map::set(items[i], _inv_map.size()); 1448 _inv_map.push_back(items[i]); 1914 1449 } 1915 1450 } … … 1920 1455 /// \c AlterationNotifier. 1921 1456 virtual void erase(const Item& item) { 1922 Map::set( invMap.back(), Map::operator[](item));1923 invMap[Map::operator[](item)] = invMap.back();1924 invMap.pop_back();1457 Map::set(_inv_map.back(), Map::operator[](item)); 1458 _inv_map[Map::operator[](item)] = _inv_map.back(); 1459 _inv_map.pop_back(); 1925 1460 Map::erase(item); 1926 1461 } … … 1932 1467 virtual void erase(const std::vector<Item>& items) { 1933 1468 for (int i = 0; i < int(items.size()); ++i) { 1934 Map::set( invMap.back(), Map::operator[](items[i]));1935 invMap[Map::operator[](items[i])] = invMap.back();1936 invMap.pop_back();1469 Map::set(_inv_map.back(), Map::operator[](items[i])); 1470 _inv_map[Map::operator[](items[i])] = _inv_map.back(); 1471 _inv_map.pop_back(); 1937 1472 } 1938 1473 Map::erase(items); … … 1948 1483 const typename Map::Notifier* nf = Map::notifier(); 1949 1484 for (nf>first(it); it != INVALID; nf>next(it)) { 1950 Map::set(it, invMap.size());1951 invMap.push_back(it);1485 Map::set(it, _inv_map.size()); 1486 _inv_map.push_back(it); 1952 1487 } 1953 1488 } … … 1958 1493 /// \c AlterationNotifier. 1959 1494 virtual void clear() { 1960 invMap.clear();1495 _inv_map.clear(); 1961 1496 Map::clear(); 1962 1497 } … … 1968 1503 /// Returns the maximal value plus one in the map. 1969 1504 unsigned int size() const { 1970 return invMap.size();1505 return _inv_map.size(); 1971 1506 } 1972 1507 … … 1978 1513 int qi = Map::operator[](q); 1979 1514 Map::set(p, qi); 1980 invMap[qi] = p;1515 _inv_map[qi] = p; 1981 1516 Map::set(q, pi); 1982 invMap[pi] = q;1517 _inv_map[pi] = q; 1983 1518 } 1984 1519 … … 1994 1529 /// Gives back th item by its descriptor. 1995 1530 Item operator()(int id) const { 1996 return invMap[id];1531 return _inv_map[id]; 1997 1532 } 1998 1533 … … 2000 1535 2001 1536 typedef std::vector<Item> Container; 2002 Container invMap;1537 Container _inv_map; 2003 1538 2004 1539 public: … … 2011 1546 /// 2012 1547 /// Constructor of the InverseMap. 2013 explicit InverseMap(const DescriptorMap& _inverted)2014 : inverted(_inverted) {}1548 explicit InverseMap(const DescriptorMap& inverted) 1549 : _inverted(inverted) {} 2015 1550 2016 1551 … … 2025 1560 /// that the descriptor belongs to currently. 2026 1561 Value operator[](const Key& key) const { 2027 return inverted(key);1562 return _inverted(key); 2028 1563 } 2029 1564 … … 2032 1567 /// Returns the size of the map. 2033 1568 unsigned int size() const { 2034 return inverted.size();1569 return _inverted.size(); 2035 1570 } 2036 1571 2037 1572 private: 2038 const DescriptorMap& inverted;1573 const DescriptorMap& _inverted; 2039 1574 }; 2040 1575 … … 2063 1598 /// Constructor 2064 1599 /// \param _digraph The digraph that the map belongs to. 2065 explicit SourceMap(const Digraph& _digraph) : digraph(_digraph) {}1600 explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {} 2066 1601 2067 1602 /// \brief The subscript operator. … … 2071 1606 /// \return The source of the arc 2072 1607 Value operator[](const Key& arc) const { 2073 return digraph.source(arc);1608 return _digraph.source(arc); 2074 1609 } 2075 1610 2076 1611 private: 2077 const Digraph& digraph;1612 const Digraph& _digraph; 2078 1613 }; 2079 1614 … … 2103 1638 /// Constructor 2104 1639 /// \param _digraph The digraph that the map belongs to. 2105 explicit TargetMap(const Digraph& _digraph) : digraph(_digraph) {}1640 explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {} 2106 1641 2107 1642 /// \brief The subscript operator. … … 2111 1646 /// \return The target of the arc 2112 1647 Value operator[](const Key& e) const { 2113 return digraph.target(e);1648 return _digraph.target(e); 2114 1649 } 2115 1650 2116 1651 private: 2117 const Digraph& digraph;1652 const Digraph& _digraph; 2118 1653 }; 2119 1654 … … 2132 1667 /// \see BackwardMap 2133 1668 /// \author Balazs Dezso 2134 template <typename Digraph>1669 template <typename Graph> 2135 1670 class ForwardMap { 2136 1671 public: 2137 1672 2138 typedef typename Digraph::Arc Value;2139 typedef typename Digraph::Edge Key;1673 typedef typename Graph::Arc Value; 1674 typedef typename Graph::Edge Key; 2140 1675 2141 1676 /// \brief Constructor 2142 1677 /// 2143 1678 /// Constructor 2144 /// \param _ digraph The digraph that the map belongs to.2145 explicit ForwardMap(const Digraph& _digraph) : digraph(_digraph) {}1679 /// \param _graph The graph that the map belongs to. 1680 explicit ForwardMap(const Graph& graph) : _graph(graph) {} 2146 1681 2147 1682 /// \brief The subscript operator. … … 2151 1686 /// \return The "forward" directed arc view of edge 2152 1687 Value operator[](const Key& key) const { 2153 return digraph.direct(key, true);1688 return _graph.direct(key, true); 2154 1689 } 2155 1690 2156 1691 private: 2157 const Digraph& digraph;1692 const Graph& _graph; 2158 1693 }; 2159 1694 … … 2162 1697 /// This function just returns an \ref ForwardMap class. 2163 1698 /// \relates ForwardMap 2164 template <typename Digraph>2165 inline ForwardMap< Digraph> forwardMap(const Digraph& digraph) {2166 return ForwardMap< Digraph>(digraph);1699 template <typename Graph> 1700 inline ForwardMap<Graph> forwardMap(const Graph& graph) { 1701 return ForwardMap<Graph>(graph); 2167 1702 } 2168 1703 … … 2172 1707 /// \see ForwardMap 2173 1708 /// \author Balazs Dezso 2174 template <typename Digraph>1709 template <typename Graph> 2175 1710 class BackwardMap { 2176 1711 public: 2177 1712 2178 typedef typename Digraph::Arc Value;2179 typedef typename Digraph::Edge Key;1713 typedef typename Graph::Arc Value; 1714 typedef typename Graph::Edge Key; 2180 1715 2181 1716 /// \brief Constructor 2182 1717 /// 2183 1718 /// Constructor 2184 /// \param _ digraph The digraph that the map belongs to.2185 explicit BackwardMap(const Digraph& _digraph) : digraph(_digraph) {}1719 /// \param _graph The graph that the map belongs to. 1720 explicit BackwardMap(const Graph& graph) : _graph(graph) {} 2186 1721 2187 1722 /// \brief The subscript operator. … … 2191 1726 /// \return The "backward" directed arc view of edge 2192 1727 Value operator[](const Key& key) const { 2193 return digraph.direct(key, false);1728 return _graph.direct(key, false); 2194 1729 } 2195 1730 2196 1731 private: 2197 const Digraph& digraph;1732 const Graph& _graph; 2198 1733 }; 2199 1734 … … 2202 1737 /// This function just returns a \ref BackwardMap class. 2203 1738 /// \relates BackwardMap 2204 template <typename Digraph>2205 inline BackwardMap< Digraph> backwardMap(const Digraph& digraph) {2206 return BackwardMap< Digraph>(digraph);1739 template <typename Graph> 1740 inline BackwardMap<Graph> backwardMap(const Graph& graph) { 1741 return BackwardMap<Graph>(graph); 2207 1742 } 2208 1743 … … 2221 1756 /// 2222 1757 /// Contructor of the map 2223 explicit PotentialDifferenceMap(const Digraph& _digraph,2224 const NodeMap& _potential)2225 : digraph(_digraph), potential(_potential) {}1758 explicit PotentialDifferenceMap(const Digraph& digraph, 1759 const NodeMap& potential) 1760 : _digraph(digraph), _potential(potential) {} 2226 1761 2227 1762 /// \brief Const subscription operator … … 2229 1764 /// Const subscription operator 2230 1765 Value operator[](const Key& arc) const { 2231 return potential[digraph.target(arc)]  potential[digraph.source(arc)]; 1766 return _potential[_digraph.target(arc)]  1767 _potential[_digraph.source(arc)]; 2232 1768 } 2233 1769 2234 1770 private: 2235 const Digraph& digraph;2236 const NodeMap& potential;1771 const Digraph& _digraph; 1772 const NodeMap& _potential; 2237 1773 }; 2238 1774 … … 2275 1811 typedef typename Digraph::Node Key; 2276 1812 2277 typedef typename ItemSetTraits< _Digraph, typename _Digraph::Arc>1813 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> 2278 1814 ::ItemNotifier::ObserverBase Parent; 2279 1815 2280 1816 private: 2281 1817 2282 class AutoNodeMap : public DefaultMap< _Digraph, Key, int> {1818 class AutoNodeMap : public DefaultMap<Digraph, Key, int> { 2283 1819 public: 2284 1820 2285 typedef DefaultMap<_Digraph, Key, int> Parent; 2286 typedef typename Parent::Digraph Digraph; 1821 typedef DefaultMap<Digraph, Key, int> Parent; 2287 1822 2288 1823 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} … … 2315 1850 /// 2316 1851 /// Constructor for creating indegree map. 2317 explicit InDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) { 2318 Parent::attach(digraph.notifier(typename _Digraph::Arc())); 1852 explicit InDegMap(const Digraph& digraph) 1853 : _digraph(digraph), _deg(digraph) { 1854 Parent::attach(_digraph.notifier(typename Digraph::Arc())); 2319 1855 2320 for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {2321 deg[it] = countInArcs(digraph, it);1856 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 1857 _deg[it] = countInArcs(_digraph, it); 2322 1858 } 2323 1859 } … … 2325 1861 /// Gives back the indegree of a Node. 2326 1862 int operator[](const Key& key) const { 2327 return deg[key];1863 return _deg[key]; 2328 1864 } 2329 1865 … … 2333 1869 2334 1870 virtual void add(const Arc& arc) { 2335 ++ deg[digraph.target(arc)];1871 ++_deg[_digraph.target(arc)]; 2336 1872 } 2337 1873 2338 1874 virtual void add(const std::vector<Arc>& arcs) { 2339 1875 for (int i = 0; i < int(arcs.size()); ++i) { 2340 ++ deg[digraph.target(arcs[i])];1876 ++_deg[_digraph.target(arcs[i])]; 2341 1877 } 2342 1878 } 2343 1879 2344 1880 virtual void erase(const Arc& arc) { 2345  deg[digraph.target(arc)];1881 _deg[_digraph.target(arc)]; 2346 1882 } 2347 1883 2348 1884 virtual void erase(const std::vector<Arc>& arcs) { 2349 1885 for (int i = 0; i < int(arcs.size()); ++i) { 2350  deg[digraph.target(arcs[i])];1886 _deg[_digraph.target(arcs[i])]; 2351 1887 } 2352 1888 } 2353 1889 2354 1890 virtual void build() { 2355 for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {2356 deg[it] = countInArcs(digraph, it);1891 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 1892 _deg[it] = countInArcs(_digraph, it); 2357 1893 } 2358 1894 } 2359 1895 2360 1896 virtual void clear() { 2361 for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {2362 deg[it] = 0;1897 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 1898 _deg[it] = 0; 2363 1899 } 2364 1900 } 2365 1901 private: 2366 1902 2367 const _Digraph&digraph;2368 AutoNodeMap deg;1903 const Digraph& _digraph; 1904 AutoNodeMap _deg; 2369 1905 }; 2370 1906 … … 2392 1928 2393 1929 public: 2394 2395 typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>2396 ::ItemNotifier::ObserverBase Parent;2397 1930 2398 1931 typedef _Digraph Digraph; … … 2400 1933 typedef typename Digraph::Node Key; 2401 1934 1935 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> 1936 ::ItemNotifier::ObserverBase Parent; 1937 2402 1938 private: 2403 1939 2404 class AutoNodeMap : public DefaultMap< _Digraph, Key, int> {1940 class AutoNodeMap : public DefaultMap<Digraph, Key, int> { 2405 1941 public: 2406 1942 2407 typedef DefaultMap<_Digraph, Key, int> Parent; 2408 typedef typename Parent::Digraph Digraph; 1943 typedef DefaultMap<Digraph, Key, int> Parent; 2409 1944 2410 1945 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} … … 2435 1970 /// 2436 1971 /// Constructor for creating outdegree map. 2437 explicit OutDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) { 2438 Parent::attach(digraph.notifier(typename _Digraph::Arc())); 1972 explicit OutDegMap(const Digraph& digraph) 1973 : _digraph(digraph), _deg(digraph) { 1974 Parent::attach(_digraph.notifier(typename Digraph::Arc())); 2439 1975 2440 for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {2441 deg[it] = countOutArcs(digraph, it);1976 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 1977 _deg[it] = countOutArcs(_digraph, it); 2442 1978 } 2443 1979 } … … 2445 1981 /// Gives back the outdegree of a Node. 2446 1982 int operator[](const Key& key) const { 2447 return deg[key];1983 return _deg[key]; 2448 1984 } 2449 1985 … … 2453 1989 2454 1990 virtual void add(const Arc& arc) { 2455 ++ deg[digraph.source(arc)];1991 ++_deg[_digraph.source(arc)]; 2456 1992 } 2457 1993 2458 1994 virtual void add(const std::vector<Arc>& arcs) { 2459 1995 for (int i = 0; i < int(arcs.size()); ++i) { 2460 ++ deg[digraph.source(arcs[i])];1996 ++_deg[_digraph.source(arcs[i])]; 2461 1997 } 2462 1998 } 2463 1999 2464 2000 virtual void erase(const Arc& arc) { 2465  deg[digraph.source(arc)];2001 _deg[_digraph.source(arc)]; 2466 2002 } 2467 2003 2468 2004 virtual void erase(const std::vector<Arc>& arcs) { 2469 2005 for (int i = 0; i < int(arcs.size()); ++i) { 2470  deg[digraph.source(arcs[i])];2006 _deg[_digraph.source(arcs[i])]; 2471 2007 } 2472 2008 } 2473 2009 2474 2010 virtual void build() { 2475 for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {2476 deg[it] = countOutArcs(digraph, it);2011 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2012 _deg[it] = countOutArcs(_digraph, it); 2477 2013 } 2478 2014 } 2479 2015 2480 2016 virtual void clear() { 2481 for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {2482 deg[it] = 0;2017 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2018 _deg[it] = 0; 2483 2019 } 2484 2020 } 2485 2021 private: 2486 2022 2487 const _Digraph&digraph;2488 AutoNodeMap deg;2023 const Digraph& _digraph; 2024 AutoNodeMap _deg; 2489 2025 }; 2490 2026 … … 2501 2037 /// 2502 2038 ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your 2503 ///digraph donot changed so frequently.2039 ///digraph is not changed so frequently. 2504 2040 /// 2505 2041 ///This class uses a selfadjusting binary search tree, Sleator's … … 2521 2057 ::ItemNotifier::ObserverBase Parent; 2522 2058 2523 GRAPH_TYPEDEFS(typename G);2059 DIGRAPH_TYPEDEFS(typename G); 2524 2060 typedef G Digraph; 2525 2061 … … 2836 2372 Arc operator()(Node s, Node t) const 2837 2373 { 2838 Arc e= _head[s];2374 Arc a = _head[s]; 2839 2375 while (true) { 2840 if (_g.target( e) == t) {2841 const_cast<DynArcLookUp&>(*this).splay( e);2842 return e;2843 } else if (t < _g.target( e)) {2844 if (_left[ e] == INVALID) {2845 const_cast<DynArcLookUp&>(*this).splay( e);2376 if (_g.target(a) == t) { 2377 const_cast<DynArcLookUp&>(*this).splay(a); 2378 return a; 2379 } else if (t < _g.target(a)) { 2380 if (_left[a] == INVALID) { 2381 const_cast<DynArcLookUp&>(*this).splay(a); 2846 2382 return INVALID; 2847 2383 } else { 2848 e = _left[e];2384 a = _left[a]; 2849 2385 } 2850 2386 } else { 2851 if (_right[ e] == INVALID) {2852 const_cast<DynArcLookUp&>(*this).splay( e);2387 if (_right[a] == INVALID) { 2388 const_cast<DynArcLookUp&>(*this).splay(a); 2853 2389 return INVALID; 2854 2390 } else { 2855 e = _right[e];2391 a = _right[a]; 2856 2392 } 2857 2393 } … … 2870 2406 Arc findFirst(Node s, Node t) const 2871 2407 { 2872 Arc e= _head[s];2408 Arc a = _head[s]; 2873 2409 Arc r = INVALID; 2874 2410 while (true) { 2875 if (_g.target( e) < t) {2876 if (_right[ e] == INVALID) {2877 const_cast<DynArcLookUp&>(*this).splay( e);2411 if (_g.target(a) < t) { 2412 if (_right[a] == INVALID) { 2413 const_cast<DynArcLookUp&>(*this).splay(a); 2878 2414 return r; 2879 2415 } else { 2880 e = _right[e];2416 a = _right[a]; 2881 2417 } 2882 2418 } else { 2883 if (_g.target( e) == t) {2884 r = e;2419 if (_g.target(a) == t) { 2420 r = a; 2885 2421 } 2886 if (_left[ e] == INVALID) {2887 const_cast<DynArcLookUp&>(*this).splay( e);2422 if (_left[a] == INVALID) { 2423 const_cast<DynArcLookUp&>(*this).splay(a); 2888 2424 return r; 2889 2425 } else { 2890 e = _left[e];2426 a = _left[a]; 2891 2427 } 2892 2428 } … … 2907 2443 ///operation then the amorized time bound can not be guaranteed. 2908 2444 #ifdef DOXYGEN 2909 Arc findNext(Node s, Node t, Arc e) const2445 Arc findNext(Node s, Node t, Arc a) const 2910 2446 #else 2911 Arc findNext(Node, Node t, Arc e) const2447 Arc findNext(Node, Node t, Arc a) const 2912 2448 #endif 2913 2449 { 2914 if (_right[ e] != INVALID) {2915 e = _right[e];2916 while (_left[ e] != INVALID) {2917 e = _left[e];2450 if (_right[a] != INVALID) { 2451 a = _right[a]; 2452 while (_left[a] != INVALID) { 2453 a = _left[a]; 2918 2454 } 2919 const_cast<DynArcLookUp&>(*this).splay( e);2455 const_cast<DynArcLookUp&>(*this).splay(a); 2920 2456 } else { 2921 while (_parent[ e] != INVALID && _right[_parent[e]] == e) {2922 e = _parent[e];2457 while (_parent[a] != INVALID && _right[_parent[a]] == a) { 2458 a = _parent[a]; 2923 2459 } 2924 if (_parent[ e] == INVALID) {2460 if (_parent[a] == INVALID) { 2925 2461 return INVALID; 2926 2462 } else { 2927 e = _parent[e];2928 const_cast<DynArcLookUp&>(*this).splay( e);2463 a = _parent[a]; 2464 const_cast<DynArcLookUp&>(*this).splay(a); 2929 2465 } 2930 2466 } 2931 if (_g.target( e) == t) return e;2467 if (_g.target(a) == t) return a; 2932 2468 else return INVALID; 2933 2469 } … … 2958 2494 { 2959 2495 public: 2960 GRAPH_TYPEDEFS(typename G);2496 DIGRAPH_TYPEDEFS(typename G); 2961 2497 typedef G Digraph; 2962 2498 … … 3075 2611 using ArcLookUp<G>::_head; 3076 2612 3077 GRAPH_TYPEDEFS(typename G);2613 DIGRAPH_TYPEDEFS(typename G); 3078 2614 typedef G Digraph; 3079 2615
Note: See TracChangeset
for help on using the changeset viewer.