DirUGraphAdaptor< _Graph, DirectionMap > Class Template Reference
[Adaptor Classes for Graphs]

---

Detailed Description

template<typename _Graph, typename DirectionMap = typename _Graph::template UEdgeMap<bool>>
class lemon::DirUGraphAdaptor< _Graph, DirectionMap >

This adaptor gives a direction for each uedge in the undirected graph. The direction of the edges stored in the DirectionMap. This map is a bool map on the undirected edges. If the uedge is mapped to true then the direction of the directed edge will be the same as the default direction of the uedge. The edges can be easily reverted by the reverseEdge() member in the adaptor.

It can be used to solve orientation problems on directed graphs. By example how can we orient an undirected graph to get the minimum number of strongly connected components. If we orient the edges with the dfs algorithm out from the source then we will get such an orientation.

We use the visitor interface of the dfs algorithm:

      template <typename DirMap>
      class OrientVisitor : public DfsVisitor<UGraph> {
      public:
     
        OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
          : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
     
        void discover(const Edge& edge) {
          _processed.set(edge, true);
          _dirMap.set(edge, _ugraph.direction(edge));
        }
     
        void examine(const Edge& edge) {
          if (_processed[edge]) return;
          _processed.set(edge, true);
          _dirMap.set(edge, _ugraph.direction(edge));
        }  
      
      private:
        const UGraph& _ugraph;  
        DirMap& _dirMap;
        UGraph::UEdgeMap<bool> _processed;
      };

And now we can use the orientation:

      UGraph::UEdgeMap<bool> dmap(ugraph);
     
      typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
      Visitor visitor(ugraph, dmap);
     
      DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
     
      dfs.run();
     
      typedef DirUGraphAdaptor<UGraph> DGraph;
      DGraph dgraph(ugraph, dmap);
     
      LEMON_ASSERT(countStronglyConnectedComponents(dgraph) == 
                   countBiEdgeConnectedComponents(ugraph), "Wrong Orientation");

The number of the bi-connected components is a lower bound for the number of the strongly connected components in the directed graph because if we contract the bi-connected components to nodes we will get a tree therefore we cannot orient edges in both direction between bi-connected components. In the other way the algorithm will orient one component to be strongly connected. The two relations proof that the assertion will be always true and the found solution is optimal.

See also:

DirUGraphAdaptorBase

dirUGraphAdaptor

#include <lemon/ugraph_adaptor.h>

Inheritance diagram for DirUGraphAdaptor< _Graph, DirectionMap >:

[legend]

List of all members.

Public Member Functions
	DirUGraphAdaptor (_Graph &_graph, DirectionMap &_direction_map)
	Constructor of the adaptor.

---

Constructor & Destructor Documentation

DirUGraphAdaptor	(	_Graph &	_graph,
		DirectionMap &	_direction_map
	)			[inline]

Constructor of the adaptor