Changeset 2084:59769591eb60 in lemon-0.x for lemon/graph_adaptor.h
- Timestamp:
- 05/15/06 11:49:51 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2749
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/graph_adaptor.h
r2081 r2084 265 265 /// implements the graph obtained from \c g by 266 266 /// reversing the orientation of its edges. 267 /// 268 /// A good example of using RevGraphAdaptor is to decide that the 269 /// directed graph is wheter strongly connected or not. If from one 270 /// node each node is reachable and from each node is reachable this 271 /// node then and just then the graph is strongly connected. Instead of 272 /// this condition we use a little bit different. From one node each node 273 /// ahould be reachable in the graph and in the reversed graph. Now this 274 /// condition can be checked with the Dfs algorithm class and the 275 /// RevGraphAdaptor algorithm class. 276 /// 277 /// And look at the code: 278 /// 279 ///\code 280 /// bool stronglyConnected(const Graph& graph) { 281 /// if (NodeIt(graph) == INVALID) return true; 282 /// Dfs<Graph> dfs(graph); 283 /// dfs.run(NodeIt(graph)); 284 /// for (NodeIt it(graph); it != INVALID; ++it) { 285 /// if (!dfs.reached(it)) { 286 /// return false; 287 /// } 288 /// } 289 /// typedef RevGraphAdaptor<const Graph> RGraph; 290 /// RGraph rgraph(graph); 291 /// DfsVisit<RGraph> rdfs(rgraph); 292 /// rdfs.run(NodeIt(graph)); 293 /// for (NodeIt it(graph); it != INVALID; ++it) { 294 /// if (!rdfs.reached(it)) { 295 /// return false; 296 /// } 297 /// } 298 /// return true; 299 /// } 300 ///\endcode 267 301 template<typename _Graph> 268 302 class RevGraphAdaptor : … … 2388 2422 /// 2389 2423 /// The second solution contains just 3 disjoint paths while the first 4. 2390 /// The full code can be found in the \ref disjoint_paths .cc demo file.2424 /// The full code can be found in the \ref disjoint_paths_demo.cc demo file. 2391 2425 /// 2392 2426 /// This graph adaptor is fully conform to the … … 2588 2622 }; 2589 2623 2624 /// \brief Just gives back a split graph adaptor 2625 /// 2626 /// Just gives back a split graph adaptor 2627 template<typename Graph> 2628 SplitGraphAdaptor<Graph> 2629 splitGraphAdaptor(const Graph& graph) { 2630 return SplitGraphAdaptor<Graph>(graph); 2631 } 2632 2590 2633 2591 2634 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.