Changeset 1740:4cade8579363 in lemon-0.x
- Timestamp:
- 10/24/05 19:03:02 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2268
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/topology.h
r1739 r1740 19 19 20 20 #include <lemon/dfs.h> 21 #include <lemon/bfs.h> 21 22 #include <lemon/graph_utils.h> 22 23 … … 221 222 ///\param g The graph. In must be undirected. 222 223 ///\return The number of components 223 ///\todo Test required 224 template<class UGraph> 225 int numberOfComponents(const UGraph &g) 226 { 227 int c=0; 228 Bfs<Graph> bfs(g); 224 template <class UndirGraph> 225 int countConnectedComponents(const UndirGraph &g) { 226 checkConcept<concept::UndirGraph, UndirGraph>(); 227 int c = 0; 228 Bfs<UndirGraph> bfs(g); 229 229 bfs.init(); 230 for(typename Graph::NodeIt n(g);n!=INVALID;++n)230 for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) { 231 231 if(!bfs.reached(n)) { 232 c++;233 232 bfs.addSource(n); 234 233 bfs.start(); 235 } 234 ++c; 235 } 236 } 236 237 return c; 237 238 } … … 249 250 ///\return The number of components 250 251 ///\todo Test required 251 template<class UGraph, class WMap> 252 int connectedComponents(const UGraph &g, WMap &comp) 253 { 254 int c=0; 255 Bfs<Graph> bfs(g); 252 template <class UndirGraph, class IntNodeMap> 253 int connectedComponents(const UndirGraph &g, IntNodeMap &comp) { 254 checkConcept<concept::UndirGraph, UndirGraph>(); 255 checkConcept<concept::WriteMap<typename UndirGraph::Node, int>, 256 IntNodeMap>(); 257 int c = 0; 258 Bfs<UndirGraph> bfs(g); 256 259 bfs.init(); 257 for(typename Graph::NodeIt n(g);n!=INVALID;++n)260 for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) { 258 261 if(!bfs.reached(n)) { 259 262 bfs.addSource(n); 260 while ( bfs.nextNode()!=INVALID ) { 261 comp[bfs.nextNode()]=c; 262 processNextNode(); 263 c++; 264 } 263 while (!bfs.emptyQueue()) { 264 comp[bfs.nextNode()] = c; 265 bfs.processNextNode(); 266 } 267 ++c; 268 } 269 } 265 270 return c; 266 271 } 267 272 273 namespace _components_bits { 274 275 template <typename Key, typename IntMap> 276 struct FillWriteMap : public MapBase<Key, bool> { 277 public: 278 FillWriteMap(IntMap& _map, int& _comp) 279 : map(_map), comp(_comp) {} 280 void set(Key key, bool value) { 281 if (value) { map.set(key, comp); } 282 } 283 private: 284 IntMap& map; 285 int& comp; 286 }; 287 288 template <typename Key, typename Container = std::vector<Key> > 289 struct BackInserterWriteMap : public MapBase<Key, bool> { 290 public: 291 BackInserterWriteMap(Container& _container) 292 : container(_container) {} 293 void set(Key key, bool value) { 294 if (value) { container.push_back(key); } 295 } 296 private: 297 Container& container; 298 }; 299 300 } 301 302 /// \brief Count the strongly connected components of a directed graph 303 /// 304 /// Count the strongly connected components of a directed graph 305 /// 306 /// \param g The graph. 307 /// \return The number of components 308 template <typename Graph> 309 int countStronglyConnectedComponents(const Graph& graph) { 310 checkConcept<concept::StaticGraph, Graph>(); 311 312 using namespace _components_bits; 313 314 typedef typename Graph::Node Node; 315 typedef typename Graph::Edge Edge; 316 typedef typename Graph::NodeIt NodeIt; 317 typedef typename Graph::EdgeIt EdgeIt; 318 319 320 typename Dfs<Graph>:: 321 template DefProcessedMap<BackInserterWriteMap<Node> >:: 322 Create dfs(graph); 323 324 std::vector<Node> nodes; 325 BackInserterWriteMap<Node> processed(nodes); 326 dfs.processedMap(processed); 327 328 dfs.init(); 329 for (NodeIt it(graph); it != INVALID; ++it) { 330 if (!dfs.reached(it)) { 331 dfs.addSource(it); 332 dfs.start(); 333 } 334 } 335 336 typedef RevGraphAdaptor<const Graph> RGraph; 337 338 RGraph rgraph(graph); 339 340 Dfs<RGraph> rdfs(rgraph); 341 342 int num = 0; 343 344 rdfs.init(); 345 for (typename std::vector<Node>::reverse_iterator 346 it = nodes.rbegin(); it != nodes.rend(); ++it) { 347 if (!rdfs.reached(*it)) { 348 rdfs.addSource(*it); 349 rdfs.start(); 350 ++num; 351 } 352 } 353 return num; 354 } 355 356 /// \brief Find the strongly connected components of a directed graph 357 /// 358 /// Find the strongly connected components of a directed graph 359 /// 360 /// \param g The graph. 361 /// \retval comp A writable node map. The values will be set from 0 to 362 /// the number of the strongly connected components minus one. Each values 363 /// of the map will be set exactly once, the values of a certain component 364 /// will be set continuously. 365 /// \return The number of components 366 template <typename Graph, typename IntNodeMap> 367 int stronglyConnectedComponents(const Graph& graph, IntNodeMap& comp) { 368 checkConcept<concept::StaticGraph, Graph>(); 369 checkConcept<concept::WriteMap<typename Graph::Node, int>, IntNodeMap>(); 370 371 using namespace _components_bits; 372 373 typedef typename Graph::Node Node; 374 typedef typename Graph::Edge Edge; 375 typedef typename Graph::NodeIt NodeIt; 376 typedef typename Graph::EdgeIt EdgeIt; 377 378 379 typename Dfs<Graph>:: 380 template DefProcessedMap<BackInserterWriteMap<Node> >:: 381 Create dfs(graph); 382 383 std::vector<Node> nodes; 384 BackInserterWriteMap<Node> processed(nodes); 385 dfs.processedMap(processed); 386 387 dfs.init(); 388 for (NodeIt it(graph); it != INVALID; ++it) { 389 if (!dfs.reached(it)) { 390 dfs.addSource(it); 391 dfs.start(); 392 } 393 } 394 395 typedef RevGraphAdaptor<const Graph> RGraph; 396 397 RGraph rgraph(graph); 398 399 typename Dfs<RGraph>:: 400 template DefProcessedMap<FillWriteMap<Node, IntNodeMap> >:: 401 Create rdfs(rgraph); 402 403 int num = 0; 404 FillWriteMap<Node, IntNodeMap> rprocessed(comp, num); 405 rdfs.processedMap(rprocessed); 406 407 rdfs.init(); 408 for (typename std::vector<Node>::reverse_iterator 409 it = nodes.rbegin(); it != nodes.rend(); ++it) { 410 if (!rdfs.reached(*it)) { 411 rdfs.addSource(*it); 412 rdfs.start(); 413 ++num; 414 } 415 } 416 return num; 417 } 418 268 419 } //namespace lemon 269 420
Note: See TracChangeset
for help on using the changeset viewer.