DirUGraphAdaptor documentation
authordeba
Tue, 16 May 2006 17:13:42 +0000
changeset 208767258b5a057b
parent 2086 3fc072264f77
child 2088 68f8d17ced51
DirUGraphAdaptor documentation
lemon/ugraph_adaptor.h
     1.1 --- a/lemon/ugraph_adaptor.h	Tue May 16 16:59:57 2006 +0000
     1.2 +++ b/lemon/ugraph_adaptor.h	Tue May 16 17:13:42 2006 +0000
     1.3 @@ -879,6 +879,11 @@
     1.4      return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
     1.5    }
     1.6  
     1.7 +  /// \brief Base of direct undirected graph adaptor
     1.8 +  ///
     1.9 +  /// Base class of the direct undirected graph adaptor. All public member
    1.10 +  /// of this class can be used with the DirUGraphAdaptor too.
    1.11 +  /// \sa DirUGraphAdaptor
    1.12    template <typename _UGraph, typename _DirectionMap>
    1.13    class DirUGraphAdaptorBase {
    1.14    public:
    1.15 @@ -889,10 +894,20 @@
    1.16      typedef typename _UGraph::Node Node;
    1.17      typedef typename _UGraph::UEdge Edge;
    1.18     
    1.19 +    /// \brief Reverse edge
    1.20 +    /// 
    1.21 +    /// It reverse the given edge. It simply negate the direction in the map.
    1.22      void reverseEdge(const Edge& edge) {
    1.23        direction->set(edge, !(*direction)[edge]);
    1.24      }
    1.25  
    1.26 +    /// \brief Returns the original direction in the undirected graph.
    1.27 +    ///
    1.28 +    /// Returns the original direction in the undirected graph.
    1.29 +    bool direction(const Edge& edge) const {
    1.30 +      return (*direction)[edge];
    1.31 +    }
    1.32 +
    1.33      void first(Node& i) const { graph->first(i); }
    1.34      void first(Edge& i) const { graph->first(i); }
    1.35      void firstIn(Edge& i, const Node& n) const {
    1.36 @@ -1057,12 +1072,78 @@
    1.37    ///
    1.38    /// \brief A directed graph is made from an undirected graph by an adaptor
    1.39    ///
    1.40 -  /// This adaptor gives a direction for each uedge in the undirected graph.
    1.41 -  /// The direction of the edges stored in the DirectionMap. This map is
    1.42 -  /// a bool map on the undirected edges. If the uedge is mapped to true
    1.43 -  /// then the direction of the directed edge will be the same as the
    1.44 -  /// default direction of the uedge. The edges can be easily reverted
    1.45 -  /// by the reverseEdge member in the adaptor.  
    1.46 +  /// This adaptor gives a direction for each uedge in the undirected
    1.47 +  /// graph. The direction of the edges stored in the
    1.48 +  /// DirectionMap. This map is a bool map on the undirected edges. If
    1.49 +  /// the uedge is mapped to true then the direction of the directed
    1.50 +  /// edge will be the same as the default direction of the uedge. The
    1.51 +  /// edges can be easily reverted by the \ref
    1.52 +  /// DirUGraphAdaptorBase::reverseEdge "reverseEdge()" member in the
    1.53 +  /// adaptor.
    1.54 +  ///
    1.55 +  /// It can be used to solve orientation problems on directed graphs.
    1.56 +  /// By example how can we orient an undirected graph to get the minimum
    1.57 +  /// number of strongly connected components. If we orient the edges with
    1.58 +  /// the dfs algorithm out from the source then we will get such an 
    1.59 +  /// orientation. 
    1.60 +  ///
    1.61 +  /// We use the \ref DfsVisitor "visitor" interface of the 
    1.62 +  /// \ref DfsVisit "dfs" algorithm:
    1.63 +  ///\code
    1.64 +  /// template <typename DirMap>
    1.65 +  /// class OrientVisitor : public DfsVisitor<UGraph> {
    1.66 +  /// public:
    1.67 +  ///
    1.68 +  ///   OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
    1.69 +  ///     : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
    1.70 +  ///
    1.71 +  ///   void discover(const Edge& edge) {
    1.72 +  ///     _processed.set(edge, true);
    1.73 +  ///     _dirMap.set(edge, _ugraph.direction(edge));
    1.74 +  ///   }
    1.75 +  ///
    1.76 +  ///   void examine(const Edge& edge) {
    1.77 +  ///     if (_processed[edge]) return;
    1.78 +  ///     _processed.set(edge, true);
    1.79 +  ///     _dirMap.set(edge, _ugraph.direction(edge));
    1.80 +  ///   }  
    1.81 +  /// 
    1.82 +  /// private:
    1.83 +  ///   const UGraph& _ugraph;  
    1.84 +  ///   DirMap& _dirMap;
    1.85 +  ///   UGraph::UEdgeMap<bool> _processed;
    1.86 +  /// };
    1.87 +  ///\endcode
    1.88 +  ///
    1.89 +  /// And now we can use the orientation:
    1.90 +  ///\code
    1.91 +  /// UGraph::UEdgeMap<bool> dmap(ugraph);
    1.92 +  ///
    1.93 +  /// typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
    1.94 +  /// Visitor visitor(ugraph, dmap);
    1.95 +  ///
    1.96 +  /// DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
    1.97 +  ///
    1.98 +  /// dfs.run();
    1.99 +  ///
   1.100 +  /// typedef DirUGraphAdaptor<UGraph> DGraph;
   1.101 +  /// DGraph dgraph(ugraph, dmap);
   1.102 +  ///
   1.103 +  /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) == 
   1.104 +  ///              countBiEdgeConnectedComponents(ugraph), "Wrong Orientation");
   1.105 +  ///\endcode
   1.106 +  ///
   1.107 +  /// The number of the bi-connected components is a lower bound for
   1.108 +  /// the number of the strongly connected components in the directed
   1.109 +  /// graph because if we contract the bi-connected components to
   1.110 +  /// nodes we will get a tree therefore we cannot orient edges in
   1.111 +  /// both direction between bi-connected components. In the other way
   1.112 +  /// the algorithm will orient one component to be strongly
   1.113 +  /// connected. The two relations proof that the assertion will
   1.114 +  /// be always true and the found solution is optimal.
   1.115 +  ///
   1.116 +  /// \sa DirUGraphAdaptorBase
   1.117 +  /// \sa dirUGraphAdaptor
   1.118    template<typename _Graph, 
   1.119             typename DirectionMap = typename _Graph::template UEdgeMap<bool> > 
   1.120    class DirUGraphAdaptor : 
   1.121 @@ -1075,12 +1156,19 @@
   1.122    protected:
   1.123      DirUGraphAdaptor() { }
   1.124    public:
   1.125 +    
   1.126 +    /// \brief Constructor of the adaptor
   1.127 +    ///
   1.128 +    /// Constructor of the adaptor
   1.129      DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) { 
   1.130        setGraph(_graph);
   1.131        setDirectionMap(_direction_map);
   1.132      }
   1.133    };
   1.134  
   1.135 +  /// \brief Just gives back a DirUGraphAdaptor
   1.136 +  ///
   1.137 +  /// Just gives back a DirUGraphAdaptor
   1.138    template<typename UGraph, typename DirectionMap>
   1.139    DirUGraphAdaptor<const UGraph, DirectionMap>
   1.140    dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {