00001 00028 #ifndef MSMAZES_CORE_GRAPH_IN_EDGES_HPP 00029 #define MSMAZES_CORE_GRAPH_IN_EDGES_HPP 00030 00031 // boost::tie 00032 #include <boost/utility.hpp> 00033 // boost::graph_traits and boost::bidirectional_tag 00034 #include <boost/graph/graph_traits.hpp> 00035 //#include <boost/graph/adjacency_list.hpp> must be included before this file. 00036 00037 namespace msmazes { 00038 00039 namespace _detail { 00040 00041 /* 00042 * Invoked if the graph is bidirectional. 00043 */ 00048 template < 00049 typename Graph 00050 > 00051 bool 00052 hasInEdgesImpl( 00053 typename boost::graph_traits<Graph>::vertex_descriptor target_v 00054 , const Graph& g 00055 , boost::bidirectional_tag 00056 ) 00057 { 00058 return (boost::in_degree(target_v, g) > 0); 00059 } 00060 00061 /* 00062 * Invoked if the graph is undirected. 00063 */ 00068 template < 00069 typename Graph 00070 > 00071 bool 00072 hasInEdgesImpl( 00073 typename boost::graph_traits<Graph>::vertex_descriptor target_v 00074 , const Graph& g 00075 , boost::undirected_tag 00076 ) 00077 { 00078 return (boost::out_degree(target_v, g) > 0); 00079 } 00080 00081 /* 00082 * Invoked if the graph is directed. 00083 */ 00088 template < 00089 typename Graph 00090 > 00091 bool 00092 hasInEdgesImpl( 00093 typename boost::graph_traits<Graph>::vertex_descriptor target_v 00094 , const Graph& g 00095 , boost::directed_tag 00096 ) 00097 { 00098 typename boost::graph_traits<Graph>::vertex_iterator vi, vend; 00099 typename boost::graph_traits<Graph>::adjacency_iterator ai, aend; 00100 00101 for (boost::tie(vi, vend) = boost::vertices(g); vi != vend; ++vi) 00102 { 00103 for ( 00104 boost::tie(ai, aend) = boost::adjacent_vertices(*vi, g); 00105 ai != aend; 00106 ++ai 00107 ) 00108 { 00109 if (*ai == target_v) 00110 { 00111 return true; 00112 } 00113 } 00114 } 00115 00116 return false; 00117 } 00118 } // namespace _detail 00119 00162 template < 00163 typename Graph 00164 > 00165 bool 00166 hasInEdges( 00167 typename boost::graph_traits<Graph>::vertex_descriptor target_v 00168 , const Graph& g 00169 ) 00170 { 00171 typename boost::graph_traits<Graph>::directed_category category; 00172 00173 return _detail::hasInEdgesImpl(target_v, g, category); 00174 } 00175 00176 namespace _detail { 00177 00178 /* 00179 * Invoked if the graph is bidirectional. 00180 */ 00185 template < 00186 typename Graph 00187 > 00188 void 00189 removeInEdgesImpl( 00190 typename boost::graph_traits<Graph>::vertex_descriptor target_v 00191 , Graph& g 00192 , boost::bidirectional_tag 00193 ) 00194 { 00195 boost::clear_in_edges(target_v, g); 00196 } 00197 00198 /* 00199 * Invoked if the graph is undirected. 00200 */ 00205 template < 00206 typename Graph 00207 > 00208 void 00209 removeInEdgesImpl( 00210 typename boost::graph_traits<Graph>::vertex_descriptor target_v 00211 , Graph& g 00212 , boost::undirected_tag 00213 ) 00214 { 00215 boost::clear_out_edges(target_v, g); 00216 } 00217 00218 /* 00219 * Invoked if the graph is directed. 00220 */ 00225 template < 00226 typename Graph 00227 > 00228 void 00229 removeInEdgesImpl( 00230 typename boost::graph_traits<Graph>::vertex_descriptor target_v 00231 , Graph& g 00232 , boost::directed_tag 00233 ) 00234 { 00235 typename boost::graph_traits<Graph>::vertex_iterator vi, vend; 00236 typename boost::graph_traits<Graph>::out_edge_iterator oi, oend; 00237 00238 for (boost::tie(vi, vend) = boost::vertices(g); vi != vend; ++vi) 00239 { 00240 boost::tie(oi, oend) = boost::out_edges(*vi, g); 00241 00242 while (oi != oend) 00243 { 00244 if (boost::target(*oi, g) == target_v) 00245 { 00246 boost::remove_edge(oi, g); 00247 boost::tie(oi, oend) = boost::out_edges(*vi, g); 00248 } 00249 else 00250 { 00251 ++oi; 00252 } 00253 } 00254 } 00255 } 00256 } // namespace _detail 00257 00300 template < 00301 typename Graph 00302 > 00303 void 00304 removeInEdges( 00305 typename boost::graph_traits<Graph>::vertex_descriptor target_v 00306 , Graph& g 00307 ) 00308 { 00309 typename boost::graph_traits<Graph>::directed_category category; 00310 00311 _detail::removeInEdgesImpl(target_v, g, category); 00312 } 00313 } // namespace msmazes 00314 00315 #endif /* MSMAZES_CORE_GRAPH_IN_EDGES_HPP */
Multi-State Mazes in C++ is hosted by . Use the Table of Contents for navigation.