Changes in lemon/graph_utils.h [100:4f754b4cf82b:140:356930927a71] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/graph_utils.h
r100 r140 36 36 ///\ingroup gutils 37 37 ///\file 38 ///\brief Digraph utilities.38 ///\brief Graph utilities. 39 39 40 40 namespace lemon { … … 43 43 /// @{ 44 44 45 namespace _graph_utils_bits { 46 template <typename Graph> 47 struct Node { typedef typename Graph::Node type; }; 48 49 template <typename Graph> 50 struct NodeIt { typedef typename Graph::NodeIt type; }; 51 52 template <typename Graph> 53 struct Arc { typedef typename Graph::Arc type; }; 54 55 template <typename Graph> 56 struct ArcIt { typedef typename Graph::ArcIt type; }; 57 58 template <typename Graph> 59 struct Edge { typedef typename Graph::Edge type; }; 60 61 template <typename Graph> 62 struct EdgeIt { typedef typename Graph::EdgeIt type; }; 63 64 template <typename Graph> 65 struct OutArcIt { typedef typename Graph::OutArcIt type; }; 66 67 template <typename Graph> 68 struct InArcIt { typedef typename Graph::InArcIt type; }; 69 70 template <typename Graph> 71 struct IncEdgeIt { typedef typename Graph::IncEdgeIt type; }; 72 73 template <typename Graph> 74 struct BoolNodeMap { 75 typedef typename Graph::template NodeMap<bool> type; 76 }; 77 78 template <typename Graph> 79 struct IntNodeMap { 80 typedef typename Graph::template NodeMap<int> type; 81 }; 82 83 template <typename Graph> 84 struct DoubleNodeMap { 85 typedef typename Graph::template NodeMap<double> type; 86 }; 87 88 template <typename Graph> 89 struct BoolArcMap { 90 typedef typename Graph::template ArcMap<bool> type; 91 }; 92 93 template <typename Graph> 94 struct IntArcMap { 95 typedef typename Graph::template ArcMap<int> type; 96 }; 97 98 template <typename Graph> 99 struct DoubleArcMap { 100 typedef typename Graph::template ArcMap<double> type; 101 }; 102 103 template <typename Graph> 104 struct BoolEdgeMap { 105 typedef typename Graph::template EdgeMap<bool> type; 106 }; 107 108 template <typename Graph> 109 struct IntEdgeMap { 110 typedef typename Graph::template EdgeMap<int> type; 111 }; 112 113 template <typename Graph> 114 struct DoubleEdgeMap { 115 typedef typename Graph::template EdgeMap<double> type; 116 }; 117 118 119 } 120 45 121 ///Creates convenience typedefs for the digraph types and iterators 46 122 47 123 ///This \c \#define creates convenience typedefs for the following types 48 124 ///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 125 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, 126 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. 127 #define DIGRAPH_TYPEDEFS(Digraph) \ 128 typedef typename ::lemon::_graph_utils_bits:: \ 129 Node<Digraph>::type Node; \ 130 typedef typename ::lemon::_graph_utils_bits:: \ 131 NodeIt<Digraph>::type NodeIt; \ 132 typedef typename ::lemon::_graph_utils_bits:: \ 133 Arc<Digraph>::type Arc; \ 134 typedef typename ::lemon::_graph_utils_bits:: \ 135 ArcIt<Digraph>::type ArcIt; \ 136 typedef typename ::lemon::_graph_utils_bits:: \ 137 OutArcIt<Digraph>::type OutArcIt; \ 138 typedef typename ::lemon::_graph_utils_bits:: \ 139 InArcIt<Digraph>::type InArcIt; \ 140 typedef typename ::lemon::_graph_utils_bits:: \ 141 BoolNodeMap<Digraph>::type BoolNodeMap; \ 142 typedef typename ::lemon::_graph_utils_bits:: \ 143 IntNodeMap<Digraph>::type IntNodeMap; \ 144 typedef typename ::lemon::_graph_utils_bits:: \ 145 DoubleNodeMap<Digraph>::type DoubleNodeMap; \ 146 typedef typename ::lemon::_graph_utils_bits:: \ 147 BoolArcMap<Digraph>::type BoolArcMap; \ 148 typedef typename ::lemon::_graph_utils_bits:: \ 149 IntArcMap<Digraph>::type IntArcMap; \ 150 typedef typename ::lemon::_graph_utils_bits:: \ 151 DoubleArcMap<Digraph>::type DoubleArcMap 152 64 153 65 154 ///Creates convenience typedefs for the graph types and iterators 66 155 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. 156 ///This \c \#define creates the same convenience typedefs as defined 157 ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates 158 ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap, 159 ///\c DoubleEdgeMap. 160 #define GRAPH_TYPEDEFS(Graph) \ 161 DIGRAPH_TYPEDEFS(Graph); \ 162 typedef typename ::lemon::_graph_utils_bits:: \ 163 Edge<Graph>::type Edge; \ 164 typedef typename ::lemon::_graph_utils_bits:: \ 165 EdgeIt<Graph>::type EdgeIt; \ 166 typedef typename ::lemon::_graph_utils_bits:: \ 167 IncEdgeIt<Graph>::type IncEdgeIt \ 168 typedef typename ::lemon::_graph_utils_bits:: \ 169 BoolEdgeMap<Graph>::type BoolEdgeMap; \ 170 typedef typename ::lemon::_graph_utils_bits:: \ 171 IntEdgeMap<Graph>::type IntEdgeMap; \ 172 typedef typename ::lemon::_graph_utils_bits:: \ 173 DoubleEdgeMap<Graph>::type DoubleEdgeMap 174 175 176 /// \brief Function to count the items in the graph. 177 /// 178 /// This function counts the items (nodes, arcs etc) in the graph. 108 179 /// The complexity of the function is O(n) because 109 180 /// 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; 181 template <typename Graph, typename Item> 182 inline int countItems(const Graph& g) { 183 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; 114 184 int num = 0; 115 185 for (ItemIt it(g); it != INVALID; ++it) { … … 121 191 // Node counting: 122 192 123 namespace _ digraph_utils_bits {124 125 template <typename Digraph, typename Enable = void>193 namespace _graph_utils_bits { 194 195 template <typename Graph, typename Enable = void> 126 196 struct CountNodesSelector { 127 static int count(const Digraph &g) {128 return countItems< Digraph, typename Digraph::Node>(g);129 } 130 }; 131 132 template <typename Digraph>197 static int count(const Graph &g) { 198 return countItems<Graph, typename Graph::Node>(g); 199 } 200 }; 201 202 template <typename Graph> 133 203 struct CountNodesSelector< 134 Digraph, typename135 enable_if<typename Digraph::NodeNumTag, void>::type>204 Graph, typename 205 enable_if<typename Graph::NodeNumTag, void>::type> 136 206 { 137 static int count(const Digraph &g) {207 static int count(const Graph &g) { 138 208 return g.nodeNum(); 139 209 } … … 141 211 } 142 212 143 /// \brief Function to count the nodes in the digraph.144 /// 145 /// This function counts the nodes in the digraph.213 /// \brief Function to count the nodes in the graph. 214 /// 215 /// This function counts the nodes in the graph. 146 216 /// 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 a217 /// graph structures it is specialized to run in O(1). 218 /// 219 /// If the graph contains a \e nodeNum() member function and a 150 220 /// \e NodeNumTag tag then this function calls directly the member 151 221 /// 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);222 template <typename Graph> 223 inline int countNodes(const Graph& g) { 224 return _graph_utils_bits::CountNodesSelector<Graph>::count(g); 155 225 } 156 226 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); 163 } 164 }; 165 166 template <typename Digraph> 167 struct CountRedsSelector< 168 Digraph, typename 169 enable_if<typename Digraph::NodeNumTag, void>::type> 227 // Arc counting: 228 229 namespace _graph_utils_bits { 230 231 template <typename Graph, typename Enable = void> 232 struct CountArcsSelector { 233 static int count(const Graph &g) { 234 return countItems<Graph, typename Graph::Arc>(g); 235 } 236 }; 237 238 template <typename Graph> 239 struct CountArcsSelector< 240 Graph, 241 typename enable_if<typename Graph::ArcNumTag, void>::type> 170 242 { 171 static int count(const Digraph &g) {172 return g. redNum();243 static int count(const Graph &g) { 244 return g.arcNum(); 173 245 } 174 246 }; 175 247 } 176 248 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 A-nodeset.186 template <typename Digraph>187 inline int count Reds(const Digraph& g) {188 return _ digraph_utils_bits::CountRedsSelector<Digraph>::count(g);249 /// \brief Function to count the arcs in the graph. 250 /// 251 /// This function counts the arcs in the graph. 252 /// The complexity of the function is O(e) but for some 253 /// graph structures it is specialized to run in O(1). 254 /// 255 /// If the graph contains a \e arcNum() member function and a 256 /// \e EdgeNumTag tag then this function calls directly the member 257 /// function to query the cardinality of the arc set. 258 template <typename Graph> 259 inline int countArcs(const Graph& g) { 260 return _graph_utils_bits::CountArcsSelector<Graph>::count(g); 189 261 } 190 262 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); 197 } 198 }; 199 200 template <typename Digraph> 201 struct CountBluesSelector< 202 Digraph, typename 203 enable_if<typename Digraph::NodeNumTag, void>::type> 263 // Edge counting: 264 namespace _graph_utils_bits { 265 266 template <typename Graph, typename Enable = void> 267 struct CountEdgesSelector { 268 static int count(const Graph &g) { 269 return countItems<Graph, typename Graph::Edge>(g); 270 } 271 }; 272 273 template <typename Graph> 274 struct CountEdgesSelector< 275 Graph, 276 typename enable_if<typename Graph::EdgeNumTag, void>::type> 204 277 { 205 static int count(const Digraph &g) {206 return g. blueNum();278 static int count(const Graph &g) { 279 return g.edgeNum(); 207 280 } 208 281 }; 209 282 } 210 283 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 B-node set. 220 template <typename Digraph> 221 inline int countBlues(const Digraph& g) { 222 return _digraph_utils_bits::CountBluesSelector<Digraph>::count(g); 284 /// \brief Function to count the edges in the graph. 285 /// 286 /// This function counts the edges in the graph. 287 /// The complexity of the function is O(m) but for some 288 /// graph structures it is specialized to run in O(1). 289 /// 290 /// If the graph contains a \e edgeNum() member function and a 291 /// \e EdgeNumTag tag then this function calls directly the member 292 /// function to query the cardinality of the edge set. 293 template <typename Graph> 294 inline int countEdges(const Graph& g) { 295 return _graph_utils_bits::CountEdgesSelector<Graph>::count(g); 296 223 297 } 224 298 225 299 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) { 300 template <typename Graph, typename DegIt> 301 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { 301 302 int num = 0; 302 303 for (DegIt it(_g, _n); it != INVALID; ++it) { … … 309 310 /// 310 311 /// This function counts the number of the out-arcs 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);312 /// in the graph. 313 template <typename Graph> 314 inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) { 315 return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n); 315 316 } 316 317 … … 318 319 /// 319 320 /// This function counts the number of the in-arcs 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);321 /// in the graph. 322 template <typename Graph> 323 inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) { 324 return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n); 324 325 } 325 326 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);327 /// \brief Function to count the number of the inc-edges to node \c n. 328 /// 329 /// This function counts the number of the inc-edges to node \c n 330 /// in the graph. 331 template <typename Graph> 332 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { 333 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n); 333 334 } 334 335 335 namespace _ digraph_utils_bits {336 337 template <typename Digraph, typename Enable = void>336 namespace _graph_utils_bits { 337 338 template <typename Graph, typename Enable = void> 338 339 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) {340 typedef typename Graph::Node Node; 341 typedef typename Graph::Arc Arc; 342 static Arc find(const Graph &g, Node u, Node v, Arc e) { 342 343 if (e == INVALID) { 343 344 g.firstOut(e, u); … … 352 353 }; 353 354 354 template <typename Digraph>355 template <typename Graph> 355 356 struct FindArcSelector< 356 Digraph,357 typename enable_if<typename Digraph::FindArcTag, void>::type>357 Graph, 358 typename enable_if<typename Graph::FindEdgeTag, void>::type> 358 359 { 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) {360 typedef typename Graph::Node Node; 361 typedef typename Graph::Arc Arc; 362 static Arc find(const Graph &g, Node u, Node v, Arc prev) { 362 363 return g.findArc(u, v, prev); 363 364 } … … 365 366 } 366 367 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.368 /// \brief Finds an arc between two nodes of a graph. 369 /// 370 /// Finds an arc from node \c u to node \c v in graph \c g. 370 371 /// 371 372 /// If \c prev is \ref INVALID (this is the default value), then … … 385 386 ///\sa DynArcLookUp 386 387 ///\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);388 template <typename Graph> 389 inline typename Graph::Arc 390 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v, 391 typename Graph::Arc prev = INVALID) { 392 return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev); 392 393 } 393 394 … … 398 399 /// use it the following way: 399 400 ///\code 400 /// for (ConArcIt< Digraph> it(g, src, trg); it != INVALID; ++it) {401 /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) { 401 402 /// ... 402 403 /// } … … 409 410 /// 410 411 /// \author Balazs Dezso 411 template <typename _ Digraph>412 class ConArcIt : public _ Digraph::Arc {412 template <typename _Graph> 413 class ConArcIt : public _Graph::Arc { 413 414 public: 414 415 415 typedef _ Digraph Digraph;416 typedef typename Digraph::Arc Parent;417 418 typedef typename Digraph::Arc Arc;419 typedef typename Digraph::Node Node;416 typedef _Graph Graph; 417 typedef typename Graph::Arc Parent; 418 419 typedef typename Graph::Arc Arc; 420 typedef typename Graph::Node Node; 420 421 421 422 /// \brief Constructor. … … 423 424 /// Construct a new ConArcIt iterating on the arcs which 424 425 /// 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));426 ConArcIt(const Graph& g, Node u, Node v) : _graph(g) { 427 Parent::operator=(findArc(_graph, u, v)); 427 428 } 428 429 … … 431 432 /// Construct a new ConArcIt which continues the iterating from 432 433 /// the \c e arc. 433 ConArcIt(const Digraph& g, Arc e) : Parent(e), digraph(g) {}434 ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {} 434 435 435 436 /// \brief Increment operator. … … 437 438 /// It increments the iterator and gives back the next arc. 438 439 ConArcIt& operator++() { 439 Parent::operator=(findArc( digraph, digraph.source(*this),440 digraph.target(*this), *this));440 Parent::operator=(findArc(_graph, _graph.source(*this), 441 _graph.target(*this), *this)); 441 442 return *this; 442 443 } 443 444 private: 444 const Digraph& digraph;445 const Graph& _graph; 445 446 }; 446 447 447 namespace _ digraph_utils_bits {448 449 template <typename Digraph, typename Enable = void>448 namespace _graph_utils_bits { 449 450 template <typename Graph, typename Enable = void> 450 451 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) {452 typedef typename Graph::Node Node; 453 typedef typename Graph::Edge Edge; 454 static Edge find(const Graph &g, Node u, Node v, Edge e) { 454 455 bool b; 455 456 if (u != v) { … … 478 479 }; 479 480 480 template <typename Digraph>481 template <typename Graph> 481 482 struct FindEdgeSelector< 482 Digraph,483 typename enable_if<typename Digraph::FindArcTag, void>::type>483 Graph, 484 typename enable_if<typename Graph::FindEdgeTag, void>::type> 484 485 { 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) {486 typedef typename Graph::Node Node; 487 typedef typename Graph::Edge Edge; 488 static Edge find(const Graph &g, Node u, Node v, Edge prev) { 488 489 return g.findEdge(u, v, prev); 489 490 } … … 491 492 } 492 493 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 .494 /// \brief Finds an edge between two nodes of a graph. 495 /// 496 /// Finds an edge from node \c u to node \c v in graph \c g. 497 /// If the node \c u and node \c v is equal then each loop edge 498 /// will be enumerated once. 498 499 /// 499 500 /// If \c prev is \ref INVALID (this is the default value), then … … 512 513 ///\sa ConArcIt 513 514 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);515 template <typename Graph> 516 inline typename Graph::Edge 517 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v, 518 typename Graph::Edge p = INVALID) { 519 return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p); 519 520 } 520 521 … … 525 526 /// use it the following way: 526 527 ///\code 527 /// for (ConEdgeIt< Digraph> it(g, src, trg); it != INVALID; ++it) {528 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) { 528 529 /// ... 529 530 /// } … … 533 534 /// 534 535 /// \author Balazs Dezso 535 template <typename _ Digraph>536 class ConEdgeIt : public _ Digraph::Edge {536 template <typename _Graph> 537 class ConEdgeIt : public _Graph::Edge { 537 538 public: 538 539 539 typedef _ Digraph Digraph;540 typedef typename Digraph::Edge Parent;541 542 typedef typename Digraph::Edge Edge;543 typedef typename Digraph::Node Node;540 typedef _Graph Graph; 541 typedef typename Graph::Edge Parent; 542 543 typedef typename Graph::Edge Edge; 544 typedef typename Graph::Node Node; 544 545 545 546 /// \brief Constructor. 546 547 /// 547 /// Construct a new ConEdgeIt iterating on the arcs which548 /// Construct a new ConEdgeIt iterating on the edges which 548 549 /// 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));550 ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) { 551 Parent::operator=(findEdge(_graph, u, v)); 551 552 } 552 553 … … 554 555 /// 555 556 /// 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) {}557 /// the \c e edge. 558 ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {} 558 559 559 560 /// \brief Increment operator. 560 561 /// 561 /// It increments the iterator and gives back the next arc.562 /// It increments the iterator and gives back the next edge. 562 563 ConEdgeIt& operator++() { 563 Parent::operator=(findEdge( digraph, digraph.source(*this),564 digraph.target(*this), *this));564 Parent::operator=(findEdge(_graph, _graph.source(*this), 565 _graph.target(*this), *this)); 565 566 return *this; 566 567 } 567 568 private: 568 const Digraph& digraph;569 const Graph& _graph; 569 570 }; 570 571 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 { 572 namespace _graph_utils_bits { 597 573 598 574 template <typename Digraph, typename Item, typename RefMap> … … 728 704 }; 729 705 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 706 } 766 707 … … 769 710 /// Class to copy a digraph to another digraph (duplicate a digraph). The 770 711 /// simplest way of using it is through the \c copyDigraph() function. 712 /// 713 /// This class not just make a copy of a graph, but it can create 714 /// references and cross references between the nodes and arcs of 715 /// the two graphs, it can copy maps for use with the newly created 716 /// graph and copy nodes and arcs. 717 /// 718 /// To make a copy from a graph, first an instance of DigraphCopy 719 /// should be created, then the data belongs to the graph should 720 /// assigned to copy. In the end, the \c run() member should be 721 /// called. 722 /// 723 /// The next code copies a graph with several data: 724 ///\code 725 /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); 726 /// // create a reference for the nodes 727 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); 728 /// dc.nodeRef(nr); 729 /// // create a cross reference (inverse) for the arcs 730 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph); 731 /// dc.arcCrossRef(acr); 732 /// // copy an arc map 733 /// OrigGraph::ArcMap<double> oamap(orig_graph); 734 /// NewGraph::ArcMap<double> namap(new_graph); 735 /// dc.arcMap(namap, oamap); 736 /// // copy a node 737 /// OrigGraph::Node on; 738 /// NewGraph::Node nn; 739 /// dc.node(nn, on); 740 /// // Executions of copy 741 /// dc.run(); 742 ///\endcode 771 743 template <typename To, typename From> 772 744 class DigraphCopy { … … 792 764 /// It copies the content of the \c _from digraph into the 793 765 /// \c _to digraph. 794 DigraphCopy(To& _to, const From& _from)795 : from(_from), to(_to) {}766 DigraphCopy(To& to, const From& from) 767 : _from(from), _to(to) {} 796 768 797 769 /// \brief Destructor of the DigraphCopy … … 799 771 /// Destructor of the DigraphCopy 800 772 ~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];773 for (int i = 0; i < int(_node_maps.size()); ++i) { 774 delete _node_maps[i]; 775 } 776 for (int i = 0; i < int(_arc_maps.size()); ++i) { 777 delete _arc_maps[i]; 806 778 } 807 779 … … 810 782 /// \brief Copies the node references into the given map. 811 783 /// 812 /// Copies the node references into the given map. 784 /// Copies the node references into the given map. The parameter 785 /// should be a map, which key type is the Node type of the source 786 /// graph, while the value type is the Node type of the 787 /// destination graph. 813 788 template <typename NodeRef> 814 789 DigraphCopy& nodeRef(NodeRef& map) { 815 nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,816 790 _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, 791 NodeRefMap, NodeRef>(map)); 817 792 return *this; 818 793 } … … 821 796 /// 822 797 /// Copies the node cross references (reverse references) into 823 /// the given map. 798 /// the given map. The parameter should be a map, which key type 799 /// is the Node type of the destination graph, while the value type is 800 /// the Node type of the source graph. 824 801 template <typename NodeCrossRef> 825 802 DigraphCopy& nodeCrossRef(NodeCrossRef& map) { 826 nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,827 803 _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node, 804 NodeRefMap, NodeCrossRef>(map)); 828 805 return *this; 829 806 } … … 831 808 /// \brief Make copy of the given map. 832 809 /// 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. 810 /// Makes copy of the given map for the newly created digraph. 811 /// The new map's key type is the destination graph's node type, 812 /// and the copied map's key type is the source graph's node type. 837 813 template <typename ToMap, typename FromMap> 838 814 DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { 839 nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,840 815 _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, 816 NodeRefMap, ToMap, FromMap>(tmap, map)); 841 817 return *this; 842 818 } … … 846 822 /// Make a copy of the given node. 847 823 DigraphCopy& node(TNode& tnode, const Node& snode) { 848 nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,849 824 _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, 825 NodeRefMap, TNode>(tnode, snode)); 850 826 return *this; 851 827 } … … 856 832 template <typename ArcRef> 857 833 DigraphCopy& arcRef(ArcRef& map) { 858 arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,859 834 _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, 835 ArcRefMap, ArcRef>(map)); 860 836 return *this; 861 837 } … … 867 843 template <typename ArcCrossRef> 868 844 DigraphCopy& arcCrossRef(ArcCrossRef& map) { 869 arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,870 845 _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc, 846 ArcRefMap, ArcCrossRef>(map)); 871 847 return *this; 872 848 } … … 880 856 template <typename ToMap, typename FromMap> 881 857 DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) { 882 arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,883 858 _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, 859 ArcRefMap, ToMap, FromMap>(tmap, map)); 884 860 return *this; 885 861 } … … 889 865 /// Make a copy of the given arc. 890 866 DigraphCopy& arc(TArc& tarc, const Arc& sarc) { 891 arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,892 867 _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, 868 ArcRefMap, TArc>(tarc, sarc)); 893 869 return *this; 894 870 } … … 898 874 /// Executes the copies. 899 875 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);876 NodeRefMap nodeRefMap(_from); 877 ArcRefMap arcRefMap(_from); 878 _graph_utils_bits::DigraphCopySelector<To>:: 879 copy(_to, _from, nodeRefMap, arcRefMap); 880 for (int i = 0; i < int(_node_maps.size()); ++i) { 881 _node_maps[i]->copy(_from, nodeRefMap); 882 } 883 for (int i = 0; i < int(_arc_maps.size()); ++i) { 884 _arc_maps[i]->copy(_from, arcRefMap); 909 885 } 910 886 } … … 913 889 914 890 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;891 const From& _from; 892 To& _to; 893 894 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 895 _node_maps; 896 897 std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 898 _arc_maps; 923 899 924 900 }; … … 926 902 /// \brief Copy a digraph to another digraph. 927 903 /// 928 /// Copy a digraph to another digraph. 929 /// The usage of the function:930 /// 904 /// Copy a digraph to another digraph. The complete usage of the 905 /// function is detailed in the DigraphCopy class, but a short 906 /// example shows a basic work: 931 907 ///\code 932 908 /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); … … 944 920 } 945 921 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. 922 /// \brief Class to copy a graph. 923 /// 924 /// Class to copy a graph to another graph (duplicate a graph). The 925 /// simplest way of using it is through the \c copyGraph() function. 926 /// 927 /// This class not just make a copy of a graph, but it can create 928 /// references and cross references between the nodes, edges and arcs of 929 /// the two graphs, it can copy maps for use with the newly created 930 /// graph and copy nodes, edges and arcs. 931 /// 932 /// To make a copy from a graph, first an instance of GraphCopy 933 /// should be created, then the data belongs to the graph should 934 /// assigned to copy. In the end, the \c run() member should be 935 /// called. 936 /// 937 /// The next code copies a graph with several data: 938 ///\code 939 /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); 940 /// // create a reference for the nodes 941 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); 942 /// dc.nodeRef(nr); 943 /// // create a cross reference (inverse) for the edges 944 /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph); 945 /// dc.edgeCrossRef(ecr); 946 /// // copy an arc map 947 /// OrigGraph::ArcMap<double> oamap(orig_graph); 948 /// NewGraph::ArcMap<double> namap(new_graph); 949 /// dc.arcMap(namap, oamap); 950 /// // copy a node 951 /// OrigGraph::Node on; 952 /// NewGraph::Node nn; 953 /// dc.node(nn, on); 954 /// // Executions of copy 955 /// dc.run(); 956 ///\endcode 950 957 template <typename To, typename From> 951 958 class GraphCopy { … … 967 974 968 975 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) {}976 ArcRefMap(const To& to, const From& from, 977 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) 978 : _to(to), _from(from), 979 _edge_ref(edge_ref), _node_ref(node_ref) {} 973 980 974 981 typedef typename From::Arc Key; … … 977 984 Value operator[](const Key& key) const { 978 985 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); 986 (_from.direction(key) == 987 (_node_ref[_from.source(key)] == _to.source(_edge_ref[key]))); 988 return _to.direct(_edge_ref[key], forward); 983 989 } 984 990 985 const To& to;986 const From& from;987 const EdgeRefMap& edge_ref;988 const NodeRefMap& node_ref;991 const To& _to; 992 const From& _from; 993 const EdgeRefMap& _edge_ref; 994 const NodeRefMap& _node_ref; 989 995 }; 990 996 … … 993 999 994 1000 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 DigraphCopy1001 /// \brief Constructor for the GraphCopy. 1002 /// 1003 /// It copies the content of the \c _from graph into the 1004 /// \c _to graph. 1005 GraphCopy(To& to, const From& from) 1006 : _from(from), _to(to) {} 1007 1008 /// \brief Destructor of the GraphCopy 1009 /// 1010 /// Destructor of the GraphCopy 1005 1011 ~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];1012 for (int i = 0; i < int(_node_maps.size()); ++i) { 1013 delete _node_maps[i]; 1014 } 1015 for (int i = 0; i < int(_arc_maps.size()); ++i) { 1016 delete _arc_maps[i]; 1017 } 1018 for (int i = 0; i < int(_edge_maps.size()); ++i) { 1019 delete _edge_maps[i]; 1014 1020 } 1015 1021 … … 1021 1027 template <typename NodeRef> 1022 1028 GraphCopy& nodeRef(NodeRef& map) { 1023 nodeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Node,1024 1029 _node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node, 1030 NodeRefMap, NodeRef>(map)); 1025 1031 return *this; 1026 1032 } … … 1032 1038 template <typename NodeCrossRef> 1033 1039 GraphCopy& nodeCrossRef(NodeCrossRef& map) { 1034 nodeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Node,1035 1040 _node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node, 1041 NodeRefMap, NodeCrossRef>(map)); 1036 1042 return *this; 1037 1043 } … … 1039 1045 /// \brief Make copy of the given map. 1040 1046 /// 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 node1047 /// Makes copy of the given map for the newly created graph. 1048 /// The new map's key type is the to graph's node type, 1049 /// and the copied map's key type is the from graph's node 1044 1050 /// type. 1045 1051 template <typename ToMap, typename FromMap> 1046 1052 GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { 1047 nodeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Node,1048 1053 _node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node, 1054 NodeRefMap, ToMap, FromMap>(tmap, map)); 1049 1055 return *this; 1050 1056 } … … 1054 1060 /// Make a copy of the given node. 1055 1061 GraphCopy& node(TNode& tnode, const Node& snode) { 1056 nodeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Node,1057 1062 _node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node, 1063 NodeRefMap, TNode>(tnode, snode)); 1058 1064 return *this; 1059 1065 } … … 1064 1070 template <typename ArcRef> 1065 1071 GraphCopy& arcRef(ArcRef& map) { 1066 arcMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Arc,1067 1072 _arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc, 1073 ArcRefMap, ArcRef>(map)); 1068 1074 return *this; 1069 1075 } … … 1075 1081 template <typename ArcCrossRef> 1076 1082 GraphCopy& arcCrossRef(ArcCrossRef& map) { 1077 arcMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From, Arc,1078 1083 _arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc, 1084 ArcRefMap, ArcCrossRef>(map)); 1079 1085 return *this; 1080 1086 } … … 1082 1088 /// \brief Make copy of the given map. 1083 1089 /// 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 arc1090 /// Makes copy of the given map for the newly created graph. 1091 /// The new map's key type is the to graph's arc type, 1092 /// and the copied map's key type is the from graph's arc 1087 1093 /// type. 1088 1094 template <typename ToMap, typename FromMap> 1089 1095 GraphCopy& arcMap(ToMap& tmap, const FromMap& map) { 1090 arcMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Arc,1091 1096 _arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc, 1097 ArcRefMap, ToMap, FromMap>(tmap, map)); 1092 1098 return *this; 1093 1099 } … … 1097 1103 /// Make a copy of the given arc. 1098 1104 GraphCopy& arc(TArc& tarc, const Arc& sarc) { 1099 arcMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Arc,1100 1105 _arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc, 1106 ArcRefMap, TArc>(tarc, sarc)); 1101 1107 return *this; 1102 1108 } … … 1107 1113 template <typename EdgeRef> 1108 1114 GraphCopy& edgeRef(EdgeRef& map) { 1109 edgeMapCopies.push_back(new _digraph_utils_bits::RefCopy<From, Edge,1110 1115 _edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge, 1116 EdgeRefMap, EdgeRef>(map)); 1111 1117 return *this; 1112 1118 } … … 1118 1124 template <typename EdgeCrossRef> 1119 1125 GraphCopy& edgeCrossRef(EdgeCrossRef& map) { 1120 edgeMapCopies.push_back(new _digraph_utils_bits::CrossRefCopy<From,1121 1126 _edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, 1127 Edge, EdgeRefMap, EdgeCrossRef>(map)); 1122 1128 return *this; 1123 1129 } … … 1125 1131 /// \brief Make copy of the given map. 1126 1132 /// 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 edge1133 /// Makes copy of the given map for the newly created graph. 1134 /// The new map's key type is the to graph's edge type, 1135 /// and the copied map's key type is the from graph's edge 1130 1136 /// type. 1131 1137 template <typename ToMap, typename FromMap> 1132 1138 GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) { 1133 edgeMapCopies.push_back(new _digraph_utils_bits::MapCopy<From, Edge,1134 1139 _edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge, 1140 EdgeRefMap, ToMap, FromMap>(tmap, map)); 1135 1141 return *this; 1136 1142 } … … 1140 1146 /// Make a copy of the given edge. 1141 1147 GraphCopy& edge(TEdge& tedge, const Edge& sedge) { 1142 edgeMapCopies.push_back(new _digraph_utils_bits::ItemCopy<From, Edge,1143 1148 _edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge, 1149 EdgeRefMap, TEdge>(tedge, sedge)); 1144 1150 return *this; 1145 1151 } … … 1149 1155 /// Executes the copies. 1150 1156 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);1157 NodeRefMap nodeRefMap(_from); 1158 EdgeRefMap edgeRefMap(_from); 1159 ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap); 1160 _graph_utils_bits::GraphCopySelector<To>:: 1161 copy(_to, _from, nodeRefMap, edgeRefMap); 1162 for (int i = 0; i < int(_node_maps.size()); ++i) { 1163 _node_maps[i]->copy(_from, nodeRefMap); 1164 } 1165 for (int i = 0; i < int(_edge_maps.size()); ++i) { 1166 _edge_maps[i]->copy(_from, edgeRefMap); 1167 } 1168 for (int i = 0; i < int(_arc_maps.size()); ++i) { 1169 _arc_maps[i]->copy(_from, arcRefMap); 1164 1170 } 1165 1171 } … … 1167 1173 private: 1168 1174 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;1175 const From& _from; 1176 To& _to; 1177 1178 std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* > 1179 _node_maps; 1180 1181 std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* > 1182 _arc_maps; 1183 1184 std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* > 1185 _edge_maps; 1180 1186 1181 1187 }; 1182 1188 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 /// 1189 /// \brief Copy a graph to another graph. 1190 /// 1191 /// Copy a graph to another graph. The complete usage of the 1192 /// function is detailed in the GraphCopy class, but a short 1193 /// example shows a basic work: 1188 1194 ///\code 1189 1195 /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); … … 1191 1197 /// 1192 1198 /// 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.1199 /// nodes of the \c from graph to the nodes of the \c to graph and 1200 /// \c ecr will contain the mapping from the arcs of the \c to graph 1201 /// to the arcs of the \c from graph. 1196 1202 /// 1197 1203 /// \see GraphCopy … … 1202 1208 } 1203 1209 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 A-node references into the given map.1303 ///1304 /// Copies the A-node 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 A-node cross references into the given map.1313 ///1314 /// Copies the A-node 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 A-node 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 B-node references into the given map.1337 ///1338 /// Copies the B-node 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 B-node cross references into the given map.1347 ///1348 /// Copies the B-node 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 B-node 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 1210 /// @} 1571 1211 1572 /// \addtogroup digraph_maps1212 /// \addtogroup graph_maps 1573 1213 /// @{ 1574 1214 1575 /// Provides an immutable and unique id for each item in the digraph.1215 /// Provides an immutable and unique id for each item in the graph. 1576 1216 1577 1217 /// 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:1218 /// same type (e.g. node) in the graph. This id is <ul><li>\b unique: 1579 1219 /// different items (nodes) get different ids <li>\b immutable: the id of an 1580 1220 /// item (node) does not change (even if you delete other nodes). </ul> 1581 1221 /// 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>1222 /// the items stored in the graph. This map can be inverted with its member 1223 /// class \c InverseMap or with the \c operator() member. 1224 /// 1225 template <typename _Graph, typename _Item> 1586 1226 class IdMap { 1587 1227 public: 1588 typedef _ Digraph Digraph;1228 typedef _Graph Graph; 1589 1229 typedef int Value; 1590 1230 typedef _Item Item; … … 1594 1234 /// 1595 1235 /// Constructor of the map. 1596 explicit IdMap(const Digraph& _digraph) : digraph(&_digraph) {}1236 explicit IdMap(const Graph& graph) : _graph(&graph) {} 1597 1237 1598 1238 /// \brief Gives back the \e id of the item. 1599 1239 /// 1600 1240 /// Gives back the immutable and unique \e id of the item. 1601 int operator[](const Item& item) const { return digraph->id(item);}1241 int operator[](const Item& item) const { return _graph->id(item);} 1602 1242 1603 1243 /// \brief Gives back the item by its id. 1604 1244 /// 1605 1245 /// Gives back the item by its id. 1606 Item operator()(int id) { return digraph->fromId(id, Item()); }1246 Item operator()(int id) { return _graph->fromId(id, Item()); } 1607 1247 1608 1248 private: 1609 const Digraph* digraph;1249 const Graph* _graph; 1610 1250 1611 1251 public: … … 1621 1261 /// 1622 1262 /// Constructor for creating an id-to-item map. 1623 explicit InverseMap(const Digraph& _digraph) : digraph(&_digraph) {}1263 explicit InverseMap(const Graph& graph) : _graph(&graph) {} 1624 1264 1625 1265 /// \brief Constructor. 1626 1266 /// 1627 1267 /// Constructor for creating an id-to-item map. 1628 explicit InverseMap(const IdMap& idMap) : digraph(idMap.digraph) {}1268 explicit InverseMap(const IdMap& map) : _graph(map._graph) {} 1629 1269 1630 1270 /// \brief Gives back the given item from its id. … … 1632 1272 /// Gives back the given item from its id. 1633 1273 /// 1634 Item operator[](int id) const { return digraph->fromId(id, Item());}1274 Item operator[](int id) const { return _graph->fromId(id, Item());} 1635 1275 1636 1276 private: 1637 const Digraph* digraph;1277 const Graph* _graph; 1638 1278 }; 1639 1279 … … 1641 1281 /// 1642 1282 /// Gives back the inverse of the IdMap. 1643 InverseMap inverse() const { return InverseMap(* digraph);}1283 InverseMap inverse() const { return InverseMap(*_graph);} 1644 1284 1645 1285 }; 1646 1286 1647 1287 1648 /// \brief General invertable digraph-map type.1649 1650 /// This type provides simple invertable digraph-maps.1288 /// \brief General invertable graph-map type. 1289 1290 /// This type provides simple invertable graph-maps. 1651 1291 /// The InvertableMap wraps an arbitrary ReadWriteMap 1652 1292 /// and if a key is set to a new value then store it … … 1656 1296 /// with stl compatible forward iterator. 1657 1297 /// 1658 /// \param _ Digraph The digraph type.1659 /// \param _Item The item type of the digraph.1298 /// \param _Graph The graph type. 1299 /// \param _Item The item type of the graph. 1660 1300 /// \param _Value The value type of the map. 1661 1301 /// 1662 1302 /// \see IterableValueMap 1663 template <typename _ Digraph, typename _Item, typename _Value>1664 class InvertableMap : protected DefaultMap<_ Digraph, _Item, _Value> {1303 template <typename _Graph, typename _Item, typename _Value> 1304 class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> { 1665 1305 private: 1666 1306 1667 typedef DefaultMap<_ Digraph, _Item, _Value> Map;1668 typedef _ Digraph Digraph;1307 typedef DefaultMap<_Graph, _Item, _Value> Map; 1308 typedef _Graph Graph; 1669 1309 1670 1310 typedef std::map<_Value, _Item> Container; 1671 Container invMap;1311 Container _inv_map; 1672 1312 1673 1313 public: … … 1682 1322 /// \brief Constructor. 1683 1323 /// 1684 /// Construct a new InvertableMap for the digraph.1685 /// 1686 explicit InvertableMap(const Digraph& digraph) : Map(digraph) {}1324 /// Construct a new InvertableMap for the graph. 1325 /// 1326 explicit InvertableMap(const Graph& graph) : Map(graph) {} 1687 1327 1688 1328 /// \brief Forward iterator for values. … … 1726 1366 /// range. 1727 1367 ValueIterator beginValue() const { 1728 return ValueIterator( invMap.begin());1368 return ValueIterator(_inv_map.begin()); 1729 1369 } 1730 1370 … … 1736 1376 /// range. 1737 1377 ValueIterator endValue() const { 1738 return ValueIterator( invMap.end());1378 return ValueIterator(_inv_map.end()); 1739 1379 } 1740 1380 … … 1744 1384 void set(const Key& key, const Value& val) { 1745 1385 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);1386 typename Container::iterator it = _inv_map.find(oldval); 1387 if (it != _inv_map.end() && it->second == key) { 1388 _inv_map.erase(it); 1749 1389 } 1750 invMap.insert(make_pair(val, key));1390 _inv_map.insert(make_pair(val, key)); 1751 1391 Map::set(key, val); 1752 1392 } … … 1764 1404 /// Gives back the item by its value. 1765 1405 Key operator()(const Value& key) const { 1766 typename Container::const_iterator it = invMap.find(key);1767 return it != invMap.end() ? it->second : INVALID;1406 typename Container::const_iterator it = _inv_map.find(key); 1407 return it != _inv_map.end() ? it->second : INVALID; 1768 1408 } 1769 1409 … … 1776 1416 virtual void erase(const Key& key) { 1777 1417 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);1418 typename Container::iterator it = _inv_map.find(val); 1419 if (it != _inv_map.end() && it->second == key) { 1420 _inv_map.erase(it); 1781 1421 } 1782 1422 Map::erase(key); … … 1790 1430 for (int i = 0; i < int(keys.size()); ++i) { 1791 1431 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);1432 typename Container::iterator it = _inv_map.find(val); 1433 if (it != _inv_map.end() && it->second == keys[i]) { 1434 _inv_map.erase(it); 1795 1435 } 1796 1436 } … … 1803 1443 /// \c AlterationNotifier. 1804 1444 virtual void clear() { 1805 invMap.clear();1445 _inv_map.clear(); 1806 1446 Map::clear(); 1807 1447 } … … 1818 1458 /// 1819 1459 /// Constructor of the InverseMap. 1820 explicit InverseMap(const InvertableMap& _inverted)1821 : inverted(_inverted) {}1460 explicit InverseMap(const InvertableMap& inverted) 1461 : _inverted(inverted) {} 1822 1462 1823 1463 /// The value type of the InverseMap. … … 1831 1471 /// what was last assigned to the value. 1832 1472 Value operator[](const Key& key) const { 1833 return inverted(key);1473 return _inverted(key); 1834 1474 } 1835 1475 1836 1476 private: 1837 const InvertableMap& inverted;1477 const InvertableMap& _inverted; 1838 1478 }; 1839 1479 … … 1850 1490 1851 1491 /// \brief Provides a mutable, continuous and unique descriptor for each 1852 /// item in the digraph.1492 /// item in the graph. 1853 1493 /// 1854 1494 /// The DescriptorMap class provides a unique and continuous (but mutable) 1855 1495 /// 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) get1496 /// graph. This id is <ul><li>\b unique: different items (nodes) get 1857 1497 /// different ids <li>\b continuous: the range of the ids is the set of 1858 1498 /// integers between 0 and \c n-1, where \c n is the number of the items of 1859 1499 /// this type (e.g. nodes) (so the id of a node can change if you delete an 1860 1500 /// 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.1501 /// with its member class \c InverseMap, or with the \c operator() member. 1502 /// 1503 /// \param _Graph The graph class the \c DescriptorMap belongs to. 1864 1504 /// \param _Item The Item is the Key of the Map. It may be Node, Arc or 1865 1505 /// Edge. 1866 template <typename _ Digraph, typename _Item>1867 class DescriptorMap : protected DefaultMap<_ Digraph, _Item, int> {1506 template <typename _Graph, typename _Item> 1507 class DescriptorMap : protected DefaultMap<_Graph, _Item, int> { 1868 1508 1869 1509 typedef _Item Item; 1870 typedef DefaultMap<_ Digraph, _Item, int> Map;1510 typedef DefaultMap<_Graph, _Item, int> Map; 1871 1511 1872 1512 public: 1873 /// The digraph class of DescriptorMap.1874 typedef _ Digraph Digraph;1513 /// The graph class of DescriptorMap. 1514 typedef _Graph Graph; 1875 1515 1876 1516 /// The key type of DescriptorMap (Node, Arc, Edge). … … 1882 1522 /// 1883 1523 /// Constructor for descriptor map. 1884 explicit DescriptorMap(const Digraph& _digraph) : Map(_digraph) {1524 explicit DescriptorMap(const Graph& _graph) : Map(_graph) { 1885 1525 Item it; 1886 1526 const typename Map::Notifier* nf = Map::notifier(); 1887 1527 for (nf->first(it); it != INVALID; nf->next(it)) { 1888 Map::set(it, invMap.size());1889 invMap.push_back(it);1528 Map::set(it, _inv_map.size()); 1529 _inv_map.push_back(it); 1890 1530 } 1891 1531 } … … 1899 1539 virtual void add(const Item& item) { 1900 1540 Map::add(item); 1901 Map::set(item, invMap.size());1902 invMap.push_back(item);1541 Map::set(item, _inv_map.size()); 1542 _inv_map.push_back(item); 1903 1543 } 1904 1544 … … 1910 1550 Map::add(items); 1911 1551 for (int i = 0; i < int(items.size()); ++i) { 1912 Map::set(items[i], invMap.size());1913 invMap.push_back(items[i]);1552 Map::set(items[i], _inv_map.size()); 1553 _inv_map.push_back(items[i]); 1914 1554 } 1915 1555 } … … 1920 1560 /// \c AlterationNotifier. 1921 1561 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();1562 Map::set(_inv_map.back(), Map::operator[](item)); 1563 _inv_map[Map::operator[](item)] = _inv_map.back(); 1564 _inv_map.pop_back(); 1925 1565 Map::erase(item); 1926 1566 } … … 1932 1572 virtual void erase(const std::vector<Item>& items) { 1933 1573 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();1574 Map::set(_inv_map.back(), Map::operator[](items[i])); 1575 _inv_map[Map::operator[](items[i])] = _inv_map.back(); 1576 _inv_map.pop_back(); 1937 1577 } 1938 1578 Map::erase(items); … … 1948 1588 const typename Map::Notifier* nf = Map::notifier(); 1949 1589 for (nf->first(it); it != INVALID; nf->next(it)) { 1950 Map::set(it, invMap.size());1951 invMap.push_back(it);1590 Map::set(it, _inv_map.size()); 1591 _inv_map.push_back(it); 1952 1592 } 1953 1593 } … … 1958 1598 /// \c AlterationNotifier. 1959 1599 virtual void clear() { 1960 invMap.clear();1600 _inv_map.clear(); 1961 1601 Map::clear(); 1962 1602 } … … 1968 1608 /// Returns the maximal value plus one in the map. 1969 1609 unsigned int size() const { 1970 return invMap.size();1610 return _inv_map.size(); 1971 1611 } 1972 1612 … … 1978 1618 int qi = Map::operator[](q); 1979 1619 Map::set(p, qi); 1980 invMap[qi] = p;1620 _inv_map[qi] = p; 1981 1621 Map::set(q, pi); 1982 invMap[pi] = q;1622 _inv_map[pi] = q; 1983 1623 } 1984 1624 … … 1994 1634 /// Gives back th item by its descriptor. 1995 1635 Item operator()(int id) const { 1996 return invMap[id];1636 return _inv_map[id]; 1997 1637 } 1998 1638 … … 2000 1640 2001 1641 typedef std::vector<Item> Container; 2002 Container invMap;1642 Container _inv_map; 2003 1643 2004 1644 public: … … 2011 1651 /// 2012 1652 /// Constructor of the InverseMap. 2013 explicit InverseMap(const DescriptorMap& _inverted)2014 : inverted(_inverted) {}1653 explicit InverseMap(const DescriptorMap& inverted) 1654 : _inverted(inverted) {} 2015 1655 2016 1656 … … 2025 1665 /// that the descriptor belongs to currently. 2026 1666 Value operator[](const Key& key) const { 2027 return inverted(key);1667 return _inverted(key); 2028 1668 } 2029 1669 … … 2032 1672 /// Returns the size of the map. 2033 1673 unsigned int size() const { 2034 return inverted.size();1674 return _inverted.size(); 2035 1675 } 2036 1676 2037 1677 private: 2038 const DescriptorMap& inverted;1678 const DescriptorMap& _inverted; 2039 1679 }; 2040 1680 … … 2063 1703 /// Constructor 2064 1704 /// \param _digraph The digraph that the map belongs to. 2065 explicit SourceMap(const Digraph& _digraph) : digraph(_digraph) {}1705 explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {} 2066 1706 2067 1707 /// \brief The subscript operator. … … 2071 1711 /// \return The source of the arc 2072 1712 Value operator[](const Key& arc) const { 2073 return digraph.source(arc);1713 return _digraph.source(arc); 2074 1714 } 2075 1715 2076 1716 private: 2077 const Digraph& digraph;1717 const Digraph& _digraph; 2078 1718 }; 2079 1719 … … 2103 1743 /// Constructor 2104 1744 /// \param _digraph The digraph that the map belongs to. 2105 explicit TargetMap(const Digraph& _digraph) : digraph(_digraph) {}1745 explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {} 2106 1746 2107 1747 /// \brief The subscript operator. … … 2111 1751 /// \return The target of the arc 2112 1752 Value operator[](const Key& e) const { 2113 return digraph.target(e);1753 return _digraph.target(e); 2114 1754 } 2115 1755 2116 1756 private: 2117 const Digraph& digraph;1757 const Digraph& _digraph; 2118 1758 }; 2119 1759 … … 2132 1772 /// \see BackwardMap 2133 1773 /// \author Balazs Dezso 2134 template <typename Digraph>1774 template <typename Graph> 2135 1775 class ForwardMap { 2136 1776 public: 2137 1777 2138 typedef typename Digraph::Arc Value;2139 typedef typename Digraph::Edge Key;1778 typedef typename Graph::Arc Value; 1779 typedef typename Graph::Edge Key; 2140 1780 2141 1781 /// \brief Constructor 2142 1782 /// 2143 1783 /// Constructor 2144 /// \param _ digraph The digraph that the map belongs to.2145 explicit ForwardMap(const Digraph& _digraph) : digraph(_digraph) {}1784 /// \param _graph The graph that the map belongs to. 1785 explicit ForwardMap(const Graph& graph) : _graph(graph) {} 2146 1786 2147 1787 /// \brief The subscript operator. … … 2151 1791 /// \return The "forward" directed arc view of edge 2152 1792 Value operator[](const Key& key) const { 2153 return digraph.direct(key, true);1793 return _graph.direct(key, true); 2154 1794 } 2155 1795 2156 1796 private: 2157 const Digraph& digraph;1797 const Graph& _graph; 2158 1798 }; 2159 1799 … … 2162 1802 /// This function just returns an \ref ForwardMap class. 2163 1803 /// \relates ForwardMap 2164 template <typename Digraph>2165 inline ForwardMap< Digraph> forwardMap(const Digraph& digraph) {2166 return ForwardMap< Digraph>(digraph);1804 template <typename Graph> 1805 inline ForwardMap<Graph> forwardMap(const Graph& graph) { 1806 return ForwardMap<Graph>(graph); 2167 1807 } 2168 1808 … … 2172 1812 /// \see ForwardMap 2173 1813 /// \author Balazs Dezso 2174 template <typename Digraph>1814 template <typename Graph> 2175 1815 class BackwardMap { 2176 1816 public: 2177 1817 2178 typedef typename Digraph::Arc Value;2179 typedef typename Digraph::Edge Key;1818 typedef typename Graph::Arc Value; 1819 typedef typename Graph::Edge Key; 2180 1820 2181 1821 /// \brief Constructor 2182 1822 /// 2183 1823 /// Constructor 2184 /// \param _ digraph The digraph that the map belongs to.2185 explicit BackwardMap(const Digraph& _digraph) : digraph(_digraph) {}1824 /// \param _graph The graph that the map belongs to. 1825 explicit BackwardMap(const Graph& graph) : _graph(graph) {} 2186 1826 2187 1827 /// \brief The subscript operator. … … 2191 1831 /// \return The "backward" directed arc view of edge 2192 1832 Value operator[](const Key& key) const { 2193 return digraph.direct(key, false);1833 return _graph.direct(key, false); 2194 1834 } 2195 1835 2196 1836 private: 2197 const Digraph& digraph;1837 const Graph& _graph; 2198 1838 }; 2199 1839 … … 2202 1842 /// This function just returns a \ref BackwardMap class. 2203 1843 /// \relates BackwardMap 2204 template <typename Digraph>2205 inline BackwardMap< Digraph> backwardMap(const Digraph& digraph) {2206 return BackwardMap< Digraph>(digraph);1844 template <typename Graph> 1845 inline BackwardMap<Graph> backwardMap(const Graph& graph) { 1846 return BackwardMap<Graph>(graph); 2207 1847 } 2208 1848 … … 2221 1861 /// 2222 1862 /// Contructor of the map 2223 explicit PotentialDifferenceMap(const Digraph& _digraph,2224 const NodeMap& _potential)2225 : digraph(_digraph), potential(_potential) {}1863 explicit PotentialDifferenceMap(const Digraph& digraph, 1864 const NodeMap& potential) 1865 : _digraph(digraph), _potential(potential) {} 2226 1866 2227 1867 /// \brief Const subscription operator … … 2229 1869 /// Const subscription operator 2230 1870 Value operator[](const Key& arc) const { 2231 return potential[digraph.target(arc)] - potential[digraph.source(arc)]; 1871 return _potential[_digraph.target(arc)] - 1872 _potential[_digraph.source(arc)]; 2232 1873 } 2233 1874 2234 1875 private: 2235 const Digraph& digraph;2236 const NodeMap& potential;1876 const Digraph& _digraph; 1877 const NodeMap& _potential; 2237 1878 }; 2238 1879 … … 2275 1916 typedef typename Digraph::Node Key; 2276 1917 2277 typedef typename ItemSetTraits< _Digraph, typename _Digraph::Arc>1918 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> 2278 1919 ::ItemNotifier::ObserverBase Parent; 2279 1920 2280 1921 private: 2281 1922 2282 class AutoNodeMap : public DefaultMap< _Digraph, Key, int> {1923 class AutoNodeMap : public DefaultMap<Digraph, Key, int> { 2283 1924 public: 2284 1925 2285 typedef DefaultMap<_Digraph, Key, int> Parent; 2286 typedef typename Parent::Digraph Digraph; 1926 typedef DefaultMap<Digraph, Key, int> Parent; 2287 1927 2288 1928 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} … … 2315 1955 /// 2316 1956 /// Constructor for creating in-degree map. 2317 explicit InDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) { 2318 Parent::attach(digraph.notifier(typename _Digraph::Arc())); 1957 explicit InDegMap(const Digraph& digraph) 1958 : _digraph(digraph), _deg(digraph) { 1959 Parent::attach(_digraph.notifier(typename Digraph::Arc())); 2319 1960 2320 for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {2321 deg[it] = countInArcs(digraph, it);1961 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 1962 _deg[it] = countInArcs(_digraph, it); 2322 1963 } 2323 1964 } … … 2325 1966 /// Gives back the in-degree of a Node. 2326 1967 int operator[](const Key& key) const { 2327 return deg[key];1968 return _deg[key]; 2328 1969 } 2329 1970 … … 2333 1974 2334 1975 virtual void add(const Arc& arc) { 2335 ++ deg[digraph.target(arc)];1976 ++_deg[_digraph.target(arc)]; 2336 1977 } 2337 1978 2338 1979 virtual void add(const std::vector<Arc>& arcs) { 2339 1980 for (int i = 0; i < int(arcs.size()); ++i) { 2340 ++ deg[digraph.target(arcs[i])];1981 ++_deg[_digraph.target(arcs[i])]; 2341 1982 } 2342 1983 } 2343 1984 2344 1985 virtual void erase(const Arc& arc) { 2345 -- deg[digraph.target(arc)];1986 --_deg[_digraph.target(arc)]; 2346 1987 } 2347 1988 2348 1989 virtual void erase(const std::vector<Arc>& arcs) { 2349 1990 for (int i = 0; i < int(arcs.size()); ++i) { 2350 -- deg[digraph.target(arcs[i])];1991 --_deg[_digraph.target(arcs[i])]; 2351 1992 } 2352 1993 } 2353 1994 2354 1995 virtual void build() { 2355 for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {2356 deg[it] = countInArcs(digraph, it);1996 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 1997 _deg[it] = countInArcs(_digraph, it); 2357 1998 } 2358 1999 } 2359 2000 2360 2001 virtual void clear() { 2361 for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {2362 deg[it] = 0;2002 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2003 _deg[it] = 0; 2363 2004 } 2364 2005 } 2365 2006 private: 2366 2007 2367 const _Digraph&digraph;2368 AutoNodeMap deg;2008 const Digraph& _digraph; 2009 AutoNodeMap _deg; 2369 2010 }; 2370 2011 … … 2392 2033 2393 2034 public: 2394 2395 typedef typename ItemSetTraits<_Digraph, typename _Digraph::Arc>2396 ::ItemNotifier::ObserverBase Parent;2397 2035 2398 2036 typedef _Digraph Digraph; … … 2400 2038 typedef typename Digraph::Node Key; 2401 2039 2040 typedef typename ItemSetTraits<Digraph, typename Digraph::Arc> 2041 ::ItemNotifier::ObserverBase Parent; 2042 2402 2043 private: 2403 2044 2404 class AutoNodeMap : public DefaultMap< _Digraph, Key, int> {2045 class AutoNodeMap : public DefaultMap<Digraph, Key, int> { 2405 2046 public: 2406 2047 2407 typedef DefaultMap<_Digraph, Key, int> Parent; 2408 typedef typename Parent::Digraph Digraph; 2048 typedef DefaultMap<Digraph, Key, int> Parent; 2409 2049 2410 2050 AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {} … … 2435 2075 /// 2436 2076 /// Constructor for creating out-degree map. 2437 explicit OutDegMap(const Digraph& _digraph) : digraph(_digraph), deg(_digraph) { 2438 Parent::attach(digraph.notifier(typename _Digraph::Arc())); 2077 explicit OutDegMap(const Digraph& digraph) 2078 : _digraph(digraph), _deg(digraph) { 2079 Parent::attach(_digraph.notifier(typename Digraph::Arc())); 2439 2080 2440 for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {2441 deg[it] = countOutArcs(digraph, it);2081 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2082 _deg[it] = countOutArcs(_digraph, it); 2442 2083 } 2443 2084 } … … 2445 2086 /// Gives back the out-degree of a Node. 2446 2087 int operator[](const Key& key) const { 2447 return deg[key];2088 return _deg[key]; 2448 2089 } 2449 2090 … … 2453 2094 2454 2095 virtual void add(const Arc& arc) { 2455 ++ deg[digraph.source(arc)];2096 ++_deg[_digraph.source(arc)]; 2456 2097 } 2457 2098 2458 2099 virtual void add(const std::vector<Arc>& arcs) { 2459 2100 for (int i = 0; i < int(arcs.size()); ++i) { 2460 ++ deg[digraph.source(arcs[i])];2101 ++_deg[_digraph.source(arcs[i])]; 2461 2102 } 2462 2103 } 2463 2104 2464 2105 virtual void erase(const Arc& arc) { 2465 -- deg[digraph.source(arc)];2106 --_deg[_digraph.source(arc)]; 2466 2107 } 2467 2108 2468 2109 virtual void erase(const std::vector<Arc>& arcs) { 2469 2110 for (int i = 0; i < int(arcs.size()); ++i) { 2470 -- deg[digraph.source(arcs[i])];2111 --_deg[_digraph.source(arcs[i])]; 2471 2112 } 2472 2113 } 2473 2114 2474 2115 virtual void build() { 2475 for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {2476 deg[it] = countOutArcs(digraph, it);2116 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2117 _deg[it] = countOutArcs(_digraph, it); 2477 2118 } 2478 2119 } 2479 2120 2480 2121 virtual void clear() { 2481 for(typename _Digraph::NodeIt it(digraph); it != INVALID; ++it) {2482 deg[it] = 0;2122 for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) { 2123 _deg[it] = 0; 2483 2124 } 2484 2125 } 2485 2126 private: 2486 2127 2487 const _Digraph&digraph;2488 AutoNodeMap deg;2128 const Digraph& _digraph; 2129 AutoNodeMap _deg; 2489 2130 }; 2490 2131 … … 2501 2142 /// 2502 2143 ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your 2503 ///digraph donot changed so frequently.2144 ///digraph is not changed so frequently. 2504 2145 /// 2505 2146 ///This class uses a self-adjusting binary search tree, Sleator's … … 2521 2162 ::ItemNotifier::ObserverBase Parent; 2522 2163 2523 GRAPH_TYPEDEFS(typenameG);2164 DIGRAPH_TYPEDEFS(G); 2524 2165 typedef G Digraph; 2525 2166 … … 2836 2477 Arc operator()(Node s, Node t) const 2837 2478 { 2838 Arc e= _head[s];2479 Arc a = _head[s]; 2839 2480 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);2481 if (_g.target(a) == t) { 2482 const_cast<DynArcLookUp&>(*this).splay(a); 2483 return a; 2484 } else if (t < _g.target(a)) { 2485 if (_left[a] == INVALID) { 2486 const_cast<DynArcLookUp&>(*this).splay(a); 2846 2487 return INVALID; 2847 2488 } else { 2848 e = _left[e];2489 a = _left[a]; 2849 2490 } 2850 2491 } else { 2851 if (_right[ e] == INVALID) {2852 const_cast<DynArcLookUp&>(*this).splay( e);2492 if (_right[a] == INVALID) { 2493 const_cast<DynArcLookUp&>(*this).splay(a); 2853 2494 return INVALID; 2854 2495 } else { 2855 e = _right[e];2496 a = _right[a]; 2856 2497 } 2857 2498 } … … 2870 2511 Arc findFirst(Node s, Node t) const 2871 2512 { 2872 Arc e= _head[s];2513 Arc a = _head[s]; 2873 2514 Arc r = INVALID; 2874 2515 while (true) { 2875 if (_g.target( e) < t) {2876 if (_right[ e] == INVALID) {2877 const_cast<DynArcLookUp&>(*this).splay( e);2516 if (_g.target(a) < t) { 2517 if (_right[a] == INVALID) { 2518 const_cast<DynArcLookUp&>(*this).splay(a); 2878 2519 return r; 2879 2520 } else { 2880 e = _right[e];2521 a = _right[a]; 2881 2522 } 2882 2523 } else { 2883 if (_g.target( e) == t) {2884 r = e;2524 if (_g.target(a) == t) { 2525 r = a; 2885 2526 } 2886 if (_left[ e] == INVALID) {2887 const_cast<DynArcLookUp&>(*this).splay( e);2527 if (_left[a] == INVALID) { 2528 const_cast<DynArcLookUp&>(*this).splay(a); 2888 2529 return r; 2889 2530 } else { 2890 e = _left[e];2531 a = _left[a]; 2891 2532 } 2892 2533 } … … 2907 2548 ///operation then the amorized time bound can not be guaranteed. 2908 2549 #ifdef DOXYGEN 2909 Arc findNext(Node s, Node t, Arc e) const2550 Arc findNext(Node s, Node t, Arc a) const 2910 2551 #else 2911 Arc findNext(Node, Node t, Arc e) const2552 Arc findNext(Node, Node t, Arc a) const 2912 2553 #endif 2913 2554 { 2914 if (_right[ e] != INVALID) {2915 e = _right[e];2916 while (_left[ e] != INVALID) {2917 e = _left[e];2555 if (_right[a] != INVALID) { 2556 a = _right[a]; 2557 while (_left[a] != INVALID) { 2558 a = _left[a]; 2918 2559 } 2919 const_cast<DynArcLookUp&>(*this).splay( e);2560 const_cast<DynArcLookUp&>(*this).splay(a); 2920 2561 } else { 2921 while (_parent[ e] != INVALID && _right[_parent[e]] == e) {2922 e = _parent[e];2562 while (_parent[a] != INVALID && _right[_parent[a]] == a) { 2563 a = _parent[a]; 2923 2564 } 2924 if (_parent[ e] == INVALID) {2565 if (_parent[a] == INVALID) { 2925 2566 return INVALID; 2926 2567 } else { 2927 e = _parent[e];2928 const_cast<DynArcLookUp&>(*this).splay( e);2568 a = _parent[a]; 2569 const_cast<DynArcLookUp&>(*this).splay(a); 2929 2570 } 2930 2571 } 2931 if (_g.target( e) == t) return e;2572 if (_g.target(a) == t) return a; 2932 2573 else return INVALID; 2933 2574 } … … 2958 2599 { 2959 2600 public: 2960 GRAPH_TYPEDEFS(typenameG);2601 DIGRAPH_TYPEDEFS(G); 2961 2602 typedef G Digraph; 2962 2603 … … 3075 2716 using ArcLookUp<G>::_head; 3076 2717 3077 GRAPH_TYPEDEFS(typenameG);2718 DIGRAPH_TYPEDEFS(G); 3078 2719 typedef G Digraph; 3079 2720
Note: See TracChangeset
for help on using the changeset viewer.