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 } |