Changeset 2087:67258b5a057b in lemon-0.x

Timestamp:

05/16/06 19:13:42 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2754

Message:

DirUGraphAdaptor documentation

File:

• lemon/ugraph_adaptor.h (modified) (5 diffs)

lemon/ugraph_adaptor.h

@@ -880 +880 @@
   }
 
+  /// \brief Base of direct undirected graph adaptor
+  ///
+  /// Base class of the direct undirected graph adaptor. All public member
+  /// of this class can be used with the DirUGraphAdaptor too.
+  /// \sa DirUGraphAdaptor
   template <typename _UGraph, typename _DirectionMap>
   class DirUGraphAdaptorBase {
@@ -890 +895 @@
     typedef typename _UGraph::UEdge Edge;
    
+    /// \brief Reverse edge
+    /// 
+    /// It reverse the given edge. It simply negate the direction in the map.
     void reverseEdge(const Edge& edge) {
       direction->set(edge, !(*direction)[edge]);
+    }
+
+    /// \brief Returns the original direction in the undirected graph.
+    ///
+    /// Returns the original direction in the undirected graph.
+    bool direction(const Edge& edge) const {
+      return (*direction)[edge];
     }
 
@@ -1058 +1073 @@
   /// \brief A directed graph is made from an undirected graph by an adaptor
   ///
-  /// 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.  
+  /// 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 \ref
+  /// DirUGraphAdaptorBase::reverseEdge "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 \ref DfsVisitor "visitor" interface of the 
+  /// \ref DfsVisit "dfs" algorithm:
+  ///\code
+  /// 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;
+  /// };
+  ///\endcode
+  ///
+  /// And now we can use the orientation:
+  ///\code
+  /// 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");
+  ///\endcode
+  ///
+  /// 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.
+  ///
+  /// \sa DirUGraphAdaptorBase
+  /// \sa dirUGraphAdaptor
   template<typename _Graph, 
            typename DirectionMap = typename _Graph::template UEdgeMap<bool> > 
@@ -1076 +1157 @@
     DirUGraphAdaptor() { }
   public:
+    
+    /// \brief Constructor of the adaptor
+    ///
+    /// Constructor of the adaptor
     DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) { 
       setGraph(_graph);
@@ -1082 +1167 @@
   };
 
+  /// \brief Just gives back a DirUGraphAdaptor
+  ///
+  /// Just gives back a DirUGraphAdaptor
   template<typename UGraph, typename DirectionMap>
   DirUGraphAdaptor<const UGraph, DirectionMap>