RevGraphAdaptor< _Graph > Class Template Reference
[Adaptor Classes for Graphs]

---

Detailed Description

template<typename _Graph>
class lemon::RevGraphAdaptor< _Graph >

If g is defined as

      ListGraph g;

then

      RevGraphAdaptor<ListGraph> ga(g);

implements the graph obtained from g by reversing the orientation of its edges.

A good example of using RevGraphAdaptor is to decide that the directed graph is wheter strongly connected or not. If from one node each node is reachable and from each node is reachable this node then and just then the graph is strongly connected. Instead of this condition we use a little bit different. From one node each node ahould be reachable in the graph and in the reversed graph. Now this condition can be checked with the Dfs algorithm class and the RevGraphAdaptor algorithm class.

And look at the code:

      bool stronglyConnected(const Graph& graph) {
        if (NodeIt(graph) == INVALID) return true;
        Dfs<Graph> dfs(graph);
        dfs.run(NodeIt(graph));
        for (NodeIt it(graph); it != INVALID; ++it) {
          if (!dfs.reached(it)) {
            return false;
          }
        }
        typedef RevGraphAdaptor<const Graph> RGraph;
        RGraph rgraph(graph);
        DfsVisit<RGraph> rdfs(rgraph);
        rdfs.run(NodeIt(graph));
        for (NodeIt it(graph); it != INVALID; ++it) {
          if (!rdfs.reached(it)) {
            return false;
          }
        }
        return true;
      }

#include <lemon/graph_adaptor.h>

Inheritance diagram for RevGraphAdaptor< _Graph >:

[legend]

List of all members.