COIN-OR::LEMON - Graph Library

Changeset 2087:67258b5a057b in lemon-0.x


Ignore:
Timestamp:
05/16/06 19:13:42 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2754
Message:

DirUGraphAdaptor documentation

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/ugraph_adaptor.h

    r2084 r2087  
    880880  }
    881881
     882  /// \brief Base of direct undirected graph adaptor
     883  ///
     884  /// Base class of the direct undirected graph adaptor. All public member
     885  /// of this class can be used with the DirUGraphAdaptor too.
     886  /// \sa DirUGraphAdaptor
    882887  template <typename _UGraph, typename _DirectionMap>
    883888  class DirUGraphAdaptorBase {
     
    890895    typedef typename _UGraph::UEdge Edge;
    891896   
     897    /// \brief Reverse edge
     898    ///
     899    /// It reverse the given edge. It simply negate the direction in the map.
    892900    void reverseEdge(const Edge& edge) {
    893901      direction->set(edge, !(*direction)[edge]);
     902    }
     903
     904    /// \brief Returns the original direction in the undirected graph.
     905    ///
     906    /// Returns the original direction in the undirected graph.
     907    bool direction(const Edge& edge) const {
     908      return (*direction)[edge];
    894909    }
    895910
     
    10581073  /// \brief A directed graph is made from an undirected graph by an adaptor
    10591074  ///
    1060   /// This adaptor gives a direction for each uedge in the undirected graph.
    1061   /// The direction of the edges stored in the DirectionMap. This map is
    1062   /// a bool map on the undirected edges. If the uedge is mapped to true
    1063   /// then the direction of the directed edge will be the same as the
    1064   /// default direction of the uedge. The edges can be easily reverted
    1065   /// by the reverseEdge member in the adaptor. 
     1075  /// This adaptor gives a direction for each uedge in the undirected
     1076  /// graph. The direction of the edges stored in the
     1077  /// DirectionMap. This map is a bool map on the undirected edges. If
     1078  /// the uedge is mapped to true then the direction of the directed
     1079  /// edge will be the same as the default direction of the uedge. The
     1080  /// edges can be easily reverted by the \ref
     1081  /// DirUGraphAdaptorBase::reverseEdge "reverseEdge()" member in the
     1082  /// adaptor.
     1083  ///
     1084  /// It can be used to solve orientation problems on directed graphs.
     1085  /// By example how can we orient an undirected graph to get the minimum
     1086  /// number of strongly connected components. If we orient the edges with
     1087  /// the dfs algorithm out from the source then we will get such an
     1088  /// orientation.
     1089  ///
     1090  /// We use the \ref DfsVisitor "visitor" interface of the
     1091  /// \ref DfsVisit "dfs" algorithm:
     1092  ///\code
     1093  /// template <typename DirMap>
     1094  /// class OrientVisitor : public DfsVisitor<UGraph> {
     1095  /// public:
     1096  ///
     1097  ///   OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
     1098  ///     : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
     1099  ///
     1100  ///   void discover(const Edge& edge) {
     1101  ///     _processed.set(edge, true);
     1102  ///     _dirMap.set(edge, _ugraph.direction(edge));
     1103  ///   }
     1104  ///
     1105  ///   void examine(const Edge& edge) {
     1106  ///     if (_processed[edge]) return;
     1107  ///     _processed.set(edge, true);
     1108  ///     _dirMap.set(edge, _ugraph.direction(edge));
     1109  ///   } 
     1110  ///
     1111  /// private:
     1112  ///   const UGraph& _ugraph; 
     1113  ///   DirMap& _dirMap;
     1114  ///   UGraph::UEdgeMap<bool> _processed;
     1115  /// };
     1116  ///\endcode
     1117  ///
     1118  /// And now we can use the orientation:
     1119  ///\code
     1120  /// UGraph::UEdgeMap<bool> dmap(ugraph);
     1121  ///
     1122  /// typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
     1123  /// Visitor visitor(ugraph, dmap);
     1124  ///
     1125  /// DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
     1126  ///
     1127  /// dfs.run();
     1128  ///
     1129  /// typedef DirUGraphAdaptor<UGraph> DGraph;
     1130  /// DGraph dgraph(ugraph, dmap);
     1131  ///
     1132  /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==
     1133  ///              countBiEdgeConnectedComponents(ugraph), "Wrong Orientation");
     1134  ///\endcode
     1135  ///
     1136  /// The number of the bi-connected components is a lower bound for
     1137  /// the number of the strongly connected components in the directed
     1138  /// graph because if we contract the bi-connected components to
     1139  /// nodes we will get a tree therefore we cannot orient edges in
     1140  /// both direction between bi-connected components. In the other way
     1141  /// the algorithm will orient one component to be strongly
     1142  /// connected. The two relations proof that the assertion will
     1143  /// be always true and the found solution is optimal.
     1144  ///
     1145  /// \sa DirUGraphAdaptorBase
     1146  /// \sa dirUGraphAdaptor
    10661147  template<typename _Graph,
    10671148           typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
     
    10761157    DirUGraphAdaptor() { }
    10771158  public:
     1159   
     1160    /// \brief Constructor of the adaptor
     1161    ///
     1162    /// Constructor of the adaptor
    10781163    DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
    10791164      setGraph(_graph);
     
    10821167  };
    10831168
     1169  /// \brief Just gives back a DirUGraphAdaptor
     1170  ///
     1171  /// Just gives back a DirUGraphAdaptor
    10841172  template<typename UGraph, typename DirectionMap>
    10851173  DirUGraphAdaptor<const UGraph, DirectionMap>
Note: See TracChangeset for help on using the changeset viewer.