lemon/ugraph_adaptor.h
changeset 2087 67258b5a057b
parent 2084 59769591eb60
child 2096 dbe860a83dc9
equal deleted inserted replaced
9:989676e541fe 10:58210a084a0a
   877   EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
   877   EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
   878   edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
   878   edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
   879     return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
   879     return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
   880   }
   880   }
   881 
   881 
       
   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
   882   template <typename _UGraph, typename _DirectionMap>
   887   template <typename _UGraph, typename _DirectionMap>
   883   class DirUGraphAdaptorBase {
   888   class DirUGraphAdaptorBase {
   884   public:
   889   public:
   885     
   890     
   886     typedef _UGraph Graph;
   891     typedef _UGraph Graph;
   887     typedef _DirectionMap DirectionMap;
   892     typedef _DirectionMap DirectionMap;
   888 
   893 
   889     typedef typename _UGraph::Node Node;
   894     typedef typename _UGraph::Node Node;
   890     typedef typename _UGraph::UEdge Edge;
   895     typedef typename _UGraph::UEdge Edge;
   891    
   896    
       
   897     /// \brief Reverse edge
       
   898     /// 
       
   899     /// It reverse the given edge. It simply negate the direction in the map.
   892     void reverseEdge(const Edge& edge) {
   900     void reverseEdge(const Edge& edge) {
   893       direction->set(edge, !(*direction)[edge]);
   901       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];
   894     }
   909     }
   895 
   910 
   896     void first(Node& i) const { graph->first(i); }
   911     void first(Node& i) const { graph->first(i); }
   897     void first(Edge& i) const { graph->first(i); }
   912     void first(Edge& i) const { graph->first(i); }
   898     void firstIn(Edge& i, const Node& n) const {
   913     void firstIn(Edge& i, const Node& n) const {
  1055 
  1070 
  1056   /// \ingroup graph_adaptors
  1071   /// \ingroup graph_adaptors
  1057   ///
  1072   ///
  1058   /// \brief A directed graph is made from an undirected graph by an adaptor
  1073   /// \brief A directed graph is made from an undirected graph by an adaptor
  1059   ///
  1074   ///
  1060   /// This adaptor gives a direction for each uedge in the undirected graph.
  1075   /// This adaptor gives a direction for each uedge in the undirected
  1061   /// The direction of the edges stored in the DirectionMap. This map is
  1076   /// graph. The direction of the edges stored in the
  1062   /// a bool map on the undirected edges. If the uedge is mapped to true
  1077   /// DirectionMap. This map is a bool map on the undirected edges. If
  1063   /// then the direction of the directed edge will be the same as the
  1078   /// the uedge is mapped to true then the direction of the directed
  1064   /// default direction of the uedge. The edges can be easily reverted
  1079   /// edge will be the same as the default direction of the uedge. The
  1065   /// by the reverseEdge member in the adaptor.  
  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
  1066   template<typename _Graph, 
  1147   template<typename _Graph, 
  1067            typename DirectionMap = typename _Graph::template UEdgeMap<bool> > 
  1148            typename DirectionMap = typename _Graph::template UEdgeMap<bool> > 
  1068   class DirUGraphAdaptor : 
  1149   class DirUGraphAdaptor : 
  1069     public GraphAdaptorExtender<
  1150     public GraphAdaptorExtender<
  1070     DirUGraphAdaptorBase<_Graph, DirectionMap> > {
  1151     DirUGraphAdaptorBase<_Graph, DirectionMap> > {
  1073     typedef GraphAdaptorExtender<
  1154     typedef GraphAdaptorExtender<
  1074       DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
  1155       DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
  1075   protected:
  1156   protected:
  1076     DirUGraphAdaptor() { }
  1157     DirUGraphAdaptor() { }
  1077   public:
  1158   public:
       
  1159     
       
  1160     /// \brief Constructor of the adaptor
       
  1161     ///
       
  1162     /// Constructor of the adaptor
  1078     DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) { 
  1163     DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) { 
  1079       setGraph(_graph);
  1164       setGraph(_graph);
  1080       setDirectionMap(_direction_map);
  1165       setDirectionMap(_direction_map);
  1081     }
  1166     }
  1082   };
  1167   };
  1083 
  1168 
       
  1169   /// \brief Just gives back a DirUGraphAdaptor
       
  1170   ///
       
  1171   /// Just gives back a DirUGraphAdaptor
  1084   template<typename UGraph, typename DirectionMap>
  1172   template<typename UGraph, typename DirectionMap>
  1085   DirUGraphAdaptor<const UGraph, DirectionMap>
  1173   DirUGraphAdaptor<const UGraph, DirectionMap>
  1086   dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
  1174   dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
  1087     return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
  1175     return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
  1088   }
  1176   }