Changeset 2020:332245399dc6 in lemon0.x
 Timestamp:
 03/30/06 10:38:41 (13 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2658
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/graph_utils.h
r2006 r2020 103 103 /// it iterates on all of the items. 104 104 105 template <typename Graph, typename Item It>105 template <typename Graph, typename Item> 106 106 inline int countItems(const Graph& g) { 107 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; 107 108 int num = 0; 108 109 for (ItemIt it(g); it != INVALID; ++it) { … … 114 115 // Node counting: 115 116 116 template <typename Graph> 117 inline typename enable_if<typename Graph::NodeNumTag, int>::type 118 _countNodes(const Graph &g) { 119 return g.nodeNum(); 120 } 121 122 template <typename Graph> 123 inline int _countNodes(Wrap<Graph> w) { 124 return countItems<Graph, typename Graph::NodeIt>(w.value); 117 namespace _graph_utils_bits { 118 119 template <typename Graph, typename Enable = void> 120 struct CountNodesSelector { 121 static int count(const Graph &g) { 122 return countItems<Graph, typename Graph::Node>(g); 123 } 124 }; 125 126 template <typename Graph> 127 struct CountNodesSelector< 128 Graph, typename 129 enable_if<typename Graph::NodeNumTag, void>::type> 130 { 131 static int count(const Graph &g) { 132 return g.nodeNum(); 133 } 134 }; 125 135 } 126 136 … … 135 145 template <typename Graph> 136 146 inline int countNodes(const Graph& g) { 137 return _countNodes<Graph>(g); 138 } 147 return _graph_utils_bits::CountNodesSelector<Graph>::count(g); 148 } 149 139 150 140 151 // Edge counting: 141 152 142 template <typename Graph> 143 inline typename enable_if<typename Graph::EdgeNumTag, int>::type 144 _countEdges(const Graph &g) { 145 return g.edgeNum(); 146 } 147 148 template <typename Graph> 149 inline int _countEdges(Wrap<Graph> w) { 150 return countItems<Graph, typename Graph::EdgeIt>(w.value); 153 namespace _graph_utils_bits { 154 155 template <typename Graph, typename Enable = void> 156 struct CountEdgesSelector { 157 static int count(const Graph &g) { 158 return countItems<Graph, typename Graph::Edge>(g); 159 } 160 }; 161 162 template <typename Graph> 163 struct CountEdgesSelector< 164 Graph, 165 typename enable_if<typename Graph::EdgeNumTag, void>::type> 166 { 167 static int count(const Graph &g) { 168 return g.edgeNum(); 169 } 170 }; 151 171 } 152 172 … … 159 179 template <typename Graph> 160 180 inline int countEdges(const Graph& g) { 161 return _ countEdges<Graph>(g);181 return _graph_utils_bits::CountEdgesSelector<Graph>::count(g); 162 182 } 163 183 164 184 // Undirected edge counting: 165 166 template <typename Graph> 167 inline 168 typename enable_if<typename Graph::EdgeNumTag, int>::type 169 _countUEdges(const Graph &g) { 170 return g.uEdgeNum(); 171 } 172 173 template <typename Graph> 174 inline int _countUEdges(Wrap<Graph> w) { 175 return countItems<Graph, typename Graph::UEdgeIt>(w.value); 185 namespace _graph_utils_bits { 186 187 template <typename Graph, typename Enable = void> 188 struct CountUEdgesSelector { 189 static int count(const Graph &g) { 190 return countItems<Graph, typename Graph::UEdge>(g); 191 } 192 }; 193 194 template <typename Graph> 195 struct CountUEdgesSelector< 196 Graph, 197 typename enable_if<typename Graph::EdgeNumTag, void>::type> 198 { 199 static int count(const Graph &g) { 200 return g.uEdgeNum(); 201 } 202 }; 176 203 } 177 204 … … 184 211 template <typename Graph> 185 212 inline int countUEdges(const Graph& g) { 186 return _ countUEdges<Graph>(g);187 } 188 213 return _graph_utils_bits::CountUEdgesSelector<Graph>::count(g); 214 215 } 189 216 190 217 … … 225 252 } 226 253 227 228 template <typename Graph> 229 inline 230 typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type 231 _findEdge(const Graph &g, 232 typename Graph::Node u, typename Graph::Node v, 233 typename Graph::Edge prev = INVALID) { 234 return g.findEdge(u, v, prev); 235 } 236 237 template <typename Graph> 238 inline typename Graph::Edge 239 _findEdge(Wrap<Graph> w, 240 typename Graph::Node u, 241 typename Graph::Node v, 242 typename Graph::Edge prev = INVALID) { 243 const Graph& g = w.value; 244 if (prev == INVALID) { 245 typename Graph::OutEdgeIt e(g, u); 246 while (e != INVALID && g.target(e) != v) ++e; 247 return e; 248 } else { 249 typename Graph::OutEdgeIt e(g, prev); ++e; 250 while (e != INVALID && g.target(e) != v) ++e; 251 return e; 252 } 254 namespace _graph_utils_bits { 255 256 template <typename Graph, typename Enable = void> 257 struct FindEdgeSelector { 258 typedef typename Graph::Node Node; 259 typedef typename Graph::Edge Edge; 260 static Edge find(const Graph &g, Node u, Node v, Edge e) { 261 if (e == INVALID) { 262 g.firstOut(e, u); 263 } else { 264 g.nextOut(e); 265 } 266 while (e != INVALID && g.target(e) != v) { 267 g.nextOut(e); 268 } 269 return e; 270 } 271 }; 272 273 template <typename Graph> 274 struct FindEdgeSelector< 275 Graph, 276 typename enable_if<typename Graph::FindEdgeTag, void>::type> 277 { 278 typedef typename Graph::Node Node; 279 typedef typename Graph::Edge Edge; 280 static Edge find(const Graph &g, Node u, Node v, Edge prev) { 281 return g.findEdge(u, v, prev); 282 } 283 }; 253 284 } 254 285 … … 268 299 /// } 269 300 ///\endcode 270 // /// \todo We may want to use the "GraphBase"271 // /// interface here...272 301 template <typename Graph> 273 302 inline typename Graph::Edge findEdge(const Graph &g, … … 275 304 typename Graph::Node v, 276 305 typename Graph::Edge prev = INVALID) { 277 return _ findEdge<Graph>(g, u, v, prev);306 return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev); 278 307 } 279 308 … … 326 355 }; 327 356 328 template <typename Graph> 329 inline 330 typename enable_if< 331 typename Graph::FindEdgeTag, 332 typename Graph::UEdge>::type 333 _findUEdge(const Graph &g, 334 typename Graph::Node u, typename Graph::Node v, 335 typename Graph::UEdge prev = INVALID) { 336 return g.findUEdge(u, v, prev); 337 } 338 339 template <typename Graph> 340 inline typename Graph::UEdge 341 _findUEdge(Wrap<Graph> w, 342 typename Graph::Node u, 343 typename Graph::Node v, 344 typename Graph::UEdge prev = INVALID) { 345 const Graph& g = w.value; 346 if (prev == INVALID) { 347 typename Graph::OutEdgeIt e(g, u); 348 while (e != INVALID && g.target(e) != v) ++e; 349 return e; 350 } else { 351 typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e; 352 while (e != INVALID && g.target(e) != v) ++e; 353 return e; 354 } 357 namespace _graph_utils_bits { 358 359 template <typename Graph, typename Enable = void> 360 struct FindUEdgeSelector { 361 typedef typename Graph::Node Node; 362 typedef typename Graph::UEdge UEdge; 363 static UEdge find(const Graph &g, Node u, Node v, UEdge e) { 364 bool b; 365 if (u != v) { 366 if (e == INVALID) { 367 g.firstInc(e, u, b); 368 } else { 369 b = g.source(e) == u; 370 g.nextInc(e, b); 371 } 372 while (e != INVALID && g.target(e) != v) { 373 g.nextInc(e, b); 374 } 375 } else { 376 if (e == INVALID) { 377 g.firstInc(e, u, b); 378 } else { 379 b = true; 380 g.nextInc(e, b); 381 } 382 while (e != INVALID && (!b  g.target(e) != v)) { 383 g.nextInc(e, b); 384 } 385 } 386 return e; 387 } 388 }; 389 390 template <typename Graph> 391 struct FindUEdgeSelector< 392 Graph, 393 typename enable_if<typename Graph::FindEdgeTag, void>::type> 394 { 395 typedef typename Graph::Node Node; 396 typedef typename Graph::UEdge UEdge; 397 static UEdge find(const Graph &g, Node u, Node v, UEdge prev) { 398 return g.findUEdge(u, v, prev); 399 } 400 }; 355 401 } 356 402 … … 358 404 /// 359 405 /// Finds an uedge from node \c u to node \c v in graph \c g. 406 /// If the node \c u and node \c v is equal then each loop edge 407 /// will be enumerated. 360 408 /// 361 409 /// If \c prev is \ref INVALID (this is the default value), then … … 371 419 /// } 372 420 ///\endcode 373 // /// \todo We may want to use the "GraphBase"374 // /// interface here...375 421 template <typename Graph> 376 inline typename Graph::UEdge 377 findUEdge(const Graph &g, 378 typename Graph::Node u, 379 typename Graph::Node v, 380 typename Graph::UEdge prev = INVALID) { 381 return _findUEdge<Graph>(g, u, v, prev); 422 inline typename Graph::UEdge findEdge(const Graph &g, 423 typename Graph::Node u, 424 typename Graph::Node v, 425 typename Graph::UEdge prev = INVALID) { 426 return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, prev); 382 427 } 383 428
Note: See TracChangeset
for help on using the changeset viewer.