Changeset 2087:67258b5a057b in lemon-0.x
- Timestamp:
- 05/16/06 19:13:42 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2754
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/ugraph_adaptor.h
r2084 r2087 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 887 template <typename _UGraph, typename _DirectionMap> 883 888 class DirUGraphAdaptorBase { … … 890 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 900 void reverseEdge(const Edge& edge) { 893 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 … … 1058 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. 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 1066 1147 template<typename _Graph, 1067 1148 typename DirectionMap = typename _Graph::template UEdgeMap<bool> > … … 1076 1157 DirUGraphAdaptor() { } 1077 1158 public: 1159 1160 /// \brief Constructor of the adaptor 1161 /// 1162 /// Constructor of the adaptor 1078 1163 DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) { 1079 1164 setGraph(_graph); … … 1082 1167 }; 1083 1168 1169 /// \brief Just gives back a DirUGraphAdaptor 1170 /// 1171 /// Just gives back a DirUGraphAdaptor 1084 1172 template<typename UGraph, typename DirectionMap> 1085 1173 DirUGraphAdaptor<const UGraph, DirectionMap>
Note: See TracChangeset
for help on using the changeset viewer.