262 ///\code |
262 ///\code |
263 /// RevGraphAdaptor<ListGraph> ga(g); |
263 /// RevGraphAdaptor<ListGraph> ga(g); |
264 ///\endcode |
264 ///\endcode |
265 /// implements the graph obtained from \c g by |
265 /// implements the graph obtained from \c g by |
266 /// reversing the orientation of its edges. |
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 template<typename _Graph> |
301 template<typename _Graph> |
268 class RevGraphAdaptor : |
302 class RevGraphAdaptor : |
269 public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > { |
303 public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > { |
270 public: |
304 public: |
271 typedef _Graph Graph; |
305 typedef _Graph Graph; |
2385 /// |
2419 /// |
2386 /// \image html node_disjoint.png |
2420 /// \image html node_disjoint.png |
2387 /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth |
2421 /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth |
2388 /// |
2422 /// |
2389 /// The second solution contains just 3 disjoint paths while the first 4. |
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 /// This graph adaptor is fully conform to the |
2426 /// This graph adaptor is fully conform to the |
2393 /// \ref concept::StaticGraph "StaticGraph" concept and |
2427 /// \ref concept::StaticGraph "StaticGraph" concept and |
2394 /// contains some additional member functions and types. The |
2428 /// contains some additional member functions and types. The |
2395 /// documentation of some member functions may be found just in the |
2429 /// documentation of some member functions may be found just in the |
2585 const GraphNodeMap>(edge_map, node_map); |
2619 const GraphNodeMap>(edge_map, node_map); |
2586 } |
2620 } |
2587 |
2621 |
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 } //namespace lemon |
2634 } //namespace lemon |
2592 |
2635 |
2593 #endif //LEMON_GRAPH_ADAPTOR_H |
2636 #endif //LEMON_GRAPH_ADAPTOR_H |
2594 |
2637 |