BALL  1.4.1
graphAlgorithms.h
Go to the documentation of this file.
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 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines