BALL
1.4.1
|
00001 #ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H 00002 #define BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H 00003 00004 #ifndef BALL_COMMON_GLOBAL_H 00005 # include <BALL/COMMON/global.h> 00006 #endif 00007 00008 #ifndef BALL_COMMON_EXCEPTION_H 00009 # include <BALL/COMMON/exception.h> 00010 #endif 00011 00012 #include <boost/graph/properties.hpp> 00013 #include <boost/graph/graph_traits.hpp> 00014 #include <boost/graph/adjacency_list.hpp> 00015 #include <boost/graph/tree_traits.hpp> 00016 #include <boost/graph/iteration_macros.hpp> 00017 #include <boost/graph/copy.hpp> 00018 #include <boost/shared_ptr.hpp> 00019 00020 #include <iostream> 00021 00022 namespace boost 00023 { 00024 enum vertex_atom_ptr_t { vertex_atom_ptr }; 00025 enum vertex_orig_ptr_t { vertex_orig_ptr }; 00026 00027 enum edge_bond_ptr_t { edge_bond_ptr }; 00028 enum edge_orig_ptr_t { edge_orig_ptr }; 00029 00030 BOOST_INSTALL_PROPERTY(vertex, atom_ptr); 00031 BOOST_INSTALL_PROPERTY(vertex, orig_ptr); 00032 00033 BOOST_INSTALL_PROPERTY(edge, bond_ptr); 00034 BOOST_INSTALL_PROPERTY(edge, orig_ptr); 00035 } 00036 00037 namespace BALL 00038 { 00039 namespace GRAPH 00040 { 00041 template <class UndirectedGraph> class UndoEliminateOperation; 00042 00048 class BALL_EXPORT IllegalStateException 00049 : public Exception::GeneralException 00050 { 00051 public: 00052 IllegalStateException(const char* file, int line, String message); 00053 }; 00054 00058 class BALL_EXPORT UnconnectedGraphException 00059 : public Exception::GeneralException 00060 { 00061 public: 00062 UnconnectedGraphException(const char * file, int line); 00063 UnconnectedGraphException(const char * file, int line, BALL::String computation); 00064 }; 00065 00069 template <class Graph> 00070 class GraphTraits 00071 { 00072 public: 00073 typedef typename boost::graph_traits<Graph>::vertex_descriptor VertexType; 00074 typedef typename boost::graph_traits<Graph>::vertex_iterator VertexIterator; 00075 typedef typename boost::graph_traits<Graph>::adjacency_iterator NeighbourIterator; 00076 typedef typename boost::graph_traits<Graph>::edge_descriptor EdgeType; 00077 00078 // this defines an editable version of the graph, i.e., a graph with list-based storage types 00079 // that has property maps on the edges and vertices pointing to edges and vertices of an instance 00080 // of the original graph type 00081 typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, 00082 boost::property<boost::vertex_orig_ptr_t, VertexType, 00083 boost::property<boost::vertex_index_t, int> >, 00084 boost::property<boost::edge_orig_ptr_t, EdgeType> > EditableGraph; 00085 00086 }; 00087 00088 template <typename Graph1, typename Graph2> 00089 struct EditableEdgeCopier 00090 { 00091 EditableEdgeCopier(const Graph1& /*g1*/, Graph2& g2) 00092 : edge_orig_map(get(boost::edge_orig_ptr, g2)) 00093 {} 00094 00095 template <typename Edge1, typename Edge2> 00096 void operator()(const Edge1& e1, Edge2& e2) const 00097 { 00098 put(edge_orig_map, e2, e1); 00099 } 00100 00101 mutable typename boost::property_map<Graph2, boost::edge_orig_ptr_t>::type edge_orig_map; 00102 }; 00103 00104 template <typename Graph1, typename Graph2> 00105 inline EditableEdgeCopier<Graph1,Graph2> 00106 makeEditableEdgeCopier(const Graph1& g1, Graph2& g2) 00107 { 00108 return EditableEdgeCopier<Graph1,Graph2>(g1, g2); 00109 } 00110 00111 template <typename Graph1, typename Graph2> 00112 struct EditableVertexCopier 00113 { 00114 EditableVertexCopier(const Graph1& /*g1*/, Graph2& g2) 00115 : vertex_orig_map(get(boost::vertex_orig_ptr, g2)), 00116 g1(g1), 00117 g2(g2) 00118 {} 00119 00120 template <typename Vertex1, typename Vertex2> 00121 void operator()(const Vertex1& v1, Vertex2& v2) const 00122 { 00123 boost::put(vertex_orig_map, v2, v1); 00124 boost::put(boost::vertex_index, g2, v2, boost::get(boost::vertex_index, g1, v1)); 00125 } 00126 00127 mutable typename boost::property_map<Graph2, boost::vertex_orig_ptr_t>::type vertex_orig_map; 00128 Graph1 const& g1; 00129 Graph2& g2; 00130 }; 00131 00132 template <typename Graph1, typename Graph2> 00133 inline EditableVertexCopier<Graph1,Graph2> 00134 makeEditableVertexCopier(const Graph1& g1, Graph2& g2) 00135 { 00136 return EditableVertexCopier<Graph1,Graph2>(g1, g2); 00137 } 00138 00144 template <class UndirectedGraph> 00145 void eliminateVertex(typename GraphTraits<UndirectedGraph>::VertexType& vertex, UndirectedGraph& graph) 00146 { 00147 typename GraphTraits<UndirectedGraph>::NeighbourIterator ai, bi, ai_end; 00148 00149 for (tie(ai, ai_end) = adjacent_vertices(vertex, graph); ai != ai_end; ++ai) 00150 { 00151 bi = ai; ++bi; 00152 for (; bi != ai_end; ++bi) 00153 if (!boost::edge(*ai, *bi, graph).second) 00154 boost::add_edge(*ai, *bi, graph); 00155 } 00156 00157 boost::clear_vertex(vertex, graph); 00158 boost::remove_vertex(vertex, graph); 00159 } 00160 00169 template <class UndirectedGraph> 00170 UndoEliminateOperation<UndirectedGraph> eliminateVertexUndoable(typename GraphTraits<UndirectedGraph>::VertexType const& vertex, 00171 UndirectedGraph& graph) 00172 { 00173 typename GraphTraits<UndirectedGraph>::NeighbourIterator ai, bi, ai_end; 00174 UndoEliminateOperation<UndirectedGraph> result(graph, vertex); 00175 00176 for (tie(ai, ai_end) = adjacent_vertices(vertex, graph); ai != ai_end; ++ai) 00177 { 00178 result.getNeighbours().push_back(boost::get(boost::vertex_index, graph, *ai)); 00179 00180 typedef typename boost::property_traits<typename boost::property_map<UndirectedGraph, boost::edge_all_t>::type>::value_type EdgeProperties; 00181 00182 EdgeProperties ep = boost::get(boost::edge_all_t(), graph, boost::edge(vertex, *ai, graph).first) ; 00183 result.getEdgeProperties().push_back(boost::get(boost::edge_all_t(), graph, boost::edge(vertex, *ai, graph).first)); 00184 00185 bi = ai; ++bi; 00186 for (; bi != ai_end; ++bi) 00187 { 00188 if (!boost::edge(*ai, *bi, graph).second) 00189 { 00190 boost::add_edge(*ai, *bi, graph); 00191 result.getEdges().push_back(std::make_pair(boost::get(boost::vertex_index, graph, *ai), 00192 boost::get(boost::vertex_index, graph, *bi))); 00193 } 00194 } 00195 } 00196 00197 boost::clear_vertex(vertex, graph); 00198 boost::remove_vertex(vertex, graph); 00199 00200 return result; 00201 } 00202 00212 template <class UndirectedGraph> 00213 class UndoEliminateOperation 00214 { 00215 public: 00216 typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor VertexType; 00217 typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor EdgeType; 00218 typedef typename boost::graph_traits<UndirectedGraph>::adjacency_iterator NeighbourIterator; 00219 00220 typedef typename boost::property_traits<typename boost::property_map<UndirectedGraph, 00221 boost::vertex_all_t>::type>::value_type VertexProperties; 00222 typedef typename boost::property_traits<typename boost::property_map<UndirectedGraph, 00223 boost::edge_all_t>::type>::value_type EdgeProperties; 00224 00228 UndoEliminateOperation(UndirectedGraph& graph, VertexType const& a); 00229 00233 VertexType& getEliminatedVertex(); 00234 00240 VertexType undo(); 00241 00242 std::vector<std::pair<int, int> >& getEdges() { return edges_; } 00243 std::vector<EdgeProperties>& getEdgeProperties() { return edge_properties_; } 00244 std::vector<int>& getNeighbours() { return neighbours_; } 00245 00246 protected: 00247 UndirectedGraph* graph; 00248 VertexType vertex; 00249 VertexProperties vertex_properties_; 00250 std::vector<std::pair<int, int> > edges_; 00251 std::vector<EdgeProperties> edge_properties_; 00252 std::vector<int> neighbours_; 00253 bool applied; 00254 }; 00255 00256 template <class UndirectedGraph> 00257 UndoEliminateOperation<UndirectedGraph>::UndoEliminateOperation(UndirectedGraph& ugraph, VertexType const& a) 00258 : graph(&ugraph), 00259 vertex(a), 00260 edges_(), 00261 neighbours_(), 00262 applied(true) 00263 { 00264 vertex_properties_ = boost::get(boost::vertex_all_t(), ugraph, a); 00265 } 00266 00267 template <class UndirectedGraph> 00268 typename UndoEliminateOperation<UndirectedGraph>::VertexType& 00269 UndoEliminateOperation<UndirectedGraph>::getEliminatedVertex() 00270 { 00271 return vertex; 00272 } 00273 00274 template <class UndirectedGraph> 00275 typename UndoEliminateOperation<UndirectedGraph>::VertexType UndoEliminateOperation<UndirectedGraph>::undo() 00276 { 00277 if (!applied) 00278 { 00279 throw IllegalStateException(__FILE__, __LINE__, "Can't undo an elimination twice"); 00280 } 00281 00282 applied = false; 00283 00284 VertexType v = boost::add_vertex(vertex_properties_, *graph); 00285 00286 std::map<int, VertexType> index_to_vertex; 00287 BGL_FORALL_VERTICES_T(v, *graph, UndirectedGraph) 00288 { 00289 index_to_vertex[boost::get(boost::vertex_index, *graph, v)] = v; 00290 } 00291 00292 for (Position i=0; i<neighbours_.size(); ++i) 00293 { 00294 boost::add_edge(v, index_to_vertex[neighbours_[i]], edge_properties_[i], *graph); 00295 } 00296 00297 for (Position i=0; i<edges_.size(); ++i) 00298 { 00299 boost::remove_edge(index_to_vertex[edges_[i].first], index_to_vertex[edges_[i].second], *graph); 00300 } 00301 00302 return v; 00303 } 00304 00305 template <class UndirectedGraph> 00306 void deepCopy(const UndirectedGraph& src, UndirectedGraph& target) 00307 { 00308 typedef std::map<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor,int> VertexIndexMap; 00309 typedef boost::associative_property_map<VertexIndexMap> VertexIndexPropertyMap; 00310 00311 VertexIndexMap vertex_map; 00312 VertexIndexPropertyMap vertex_property_map(vertex_map); 00313 00314 typename boost::graph_traits<UndirectedGraph>::vertices_size_type count = 0; 00315 00316 typename boost::graph_traits<UndirectedGraph>::vertex_iterator vi, vend; 00317 for (boost::tie(vi, vend) = boost::vertices(src); vi != vend; ++vi) 00318 vertex_map[*vi] = count++; 00319 00320 boost::copy_graph(src, target, vertex_index_map(vertex_property_map)); 00321 } 00322 00323 template <class Tree, class From, class To, class Functor> 00324 class PostOrderFolding 00325 { 00326 public: 00327 typedef typename Tree::children_iterator ChildrenIterator; 00328 00329 typedef typename std::vector<To>::iterator ArgumentIterator; 00330 00331 PostOrderFolding(Tree& tree, Functor& f) 00332 : return_stack_(boost::shared_ptr<std::vector<To> >(new std::vector<To>())), 00333 tree_(&tree), 00334 f_(&f) 00335 { 00336 boost::traverse_tree(root(*tree_), *tree_, *this); 00337 } 00338 00339 To getResult() 00340 { 00341 return *return_stack_->begin(); 00342 } 00343 00344 template <class Node> 00345 void preorder(Node, Tree&) 00346 { 00347 } 00348 00349 template <class Node> 00350 void inorder(Node, Tree&) 00351 { 00352 } 00353 00354 template <class Node> 00355 void postorder(Node n, Tree& t) 00356 { 00357 ChildrenIterator c_i, c_end; 00358 boost::tie(c_i, c_end) = children(n, t); 00359 00360 bool is_leaf = (c_i == c_end); 00361 00362 ArgumentIterator begin_arg = return_stack_->end(); 00363 ArgumentIterator end_arg = return_stack_->end(); 00364 00365 if (!is_leaf) 00366 { 00367 for (; c_i != c_end; ++c_i) 00368 { 00369 --begin_arg; 00370 } 00371 } 00372 00373 To value = (*f_)(n, begin_arg, end_arg); 00374 00375 if (begin_arg != end_arg) 00376 { 00377 return_stack_->erase(begin_arg, end_arg); 00378 } 00379 00380 return_stack_->push_back(value); 00381 } 00382 00383 protected: 00384 boost::shared_ptr<std::vector<To> > return_stack_; 00385 00386 Tree* tree_; 00387 Functor* f_; 00388 }; 00389 00390 } 00391 } 00392 00393 #endif // BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H 00394 00395