BALL
1.4.1
|
00001 // -*- Mode: C++; tab-width: 2; -*- 00002 // vi: set ts=2: 00003 // 00004 00005 #ifndef BALL_DATATYPE_GRAPH_TREEWIDTH_H 00006 #define BALL_DATATYPE_GRAPH_TREEWIDTH_H 00007 00008 #ifndef BALL_COMMON_GLOBAL_H 00009 # include <BALL/COMMON/global.h> 00010 #endif 00011 00012 #ifndef BALL_COMMON_EXCEPTION_H 00013 # include <BALL/COMMON/exception.h> 00014 #endif 00015 00016 #ifndef BALL_CONCEPT_BASEFUNCTOR_H 00017 # include <BALL/CONCEPT/baseFunctor.h> 00018 #endif 00019 00020 #ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H 00021 # include <BALL/DATATYPE/GRAPH/graphAlgorithms.h> 00022 #endif 00023 00024 #ifndef BALL_DATATYPE_GRAPH_MOLECULARGRAPH_H 00025 # include <BALL/DATATYPE/GRAPH/molecularGraph.h> 00026 #endif 00027 00028 #include <algorithm> 00029 #include <functional> 00030 #include <map> 00031 #include <set> 00032 #include <vector> 00033 00034 #include <boost/graph/connected_components.hpp> 00035 #include <boost/graph/filtered_graph.hpp> 00036 #include <boost/graph/graph_as_tree.hpp> 00037 #include <boost/graph/copy.hpp> 00038 00039 namespace boost 00040 { 00041 enum vertex_bag_content_t { vertex_bag_content }; 00042 enum vertex_bag_special_t { vertex_bag_special }; 00043 enum vertex_bag_type_t { vertex_bag_type }; 00044 00045 BOOST_INSTALL_PROPERTY(vertex, bag_content); 00046 BOOST_INSTALL_PROPERTY(vertex, bag_special); 00047 BOOST_INSTALL_PROPERTY(vertex, bag_type); 00048 } 00049 00050 namespace BALL 00051 { 00052 template <class EditableGraph> class TreeWidthImplementation; 00056 template <class UndirectedGraph> 00057 class TreeWidth 00058 { 00059 public: 00063 enum BagType { 00067 INTRODUCE_BAG, 00071 LEAF_BAG, 00075 FORGET_BAG, 00079 ROOT_BAG, 00083 JOIN_BAG, 00087 INNER_BAG, 00091 END_BAG 00092 }; 00093 00094 typedef typename GRAPH::GraphTraits<UndirectedGraph>::EditableGraph EditableGraph; 00095 typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor OriginalVertexType; 00096 00097 typedef std::set<OriginalVertexType> TreeDecompositionContent; 00098 00099 typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, 00100 boost::property<boost::vertex_bag_content_t, std::set<OriginalVertexType>, 00101 boost::property<boost::vertex_bag_special_t, OriginalVertexType, 00102 boost::property<boost::vertex_bag_type_t, int> > >, 00103 boost::no_property> TreeDecompositionGraph; 00104 00105 typedef typename boost::graph_traits<TreeDecompositionGraph>::vertex_descriptor TreeDecompositionBag; 00106 00107 typedef boost::iterator_property_map<typename std::vector<TreeDecompositionBag>::iterator, 00108 typename boost::property_map<TreeDecompositionGraph, boost::vertex_index_t>::type> 00109 TreeDecompositionParentMap; 00110 typedef boost::graph_as_tree<TreeDecompositionGraph, TreeDecompositionParentMap> TreeDecomposition; 00111 00112 TreeWidth(UndirectedGraph const& input); 00113 00114 std::vector<boost::shared_ptr<EditableGraph> >& getComponents() { return components_; } 00115 std::vector<boost::shared_ptr<TreeDecomposition> >& getNiceTreeDecompositions() { return nice_tree_decompositions_; } 00116 00117 protected: 00118 template <typename ComponentMap> 00119 class ComponentFilter_ 00120 { 00121 public: 00122 ComponentFilter_(ComponentMap cm, Position i) 00123 : cm_(&cm), 00124 component_(i) 00125 { } 00126 00127 template <typename Vertex> 00128 bool operator() (const Vertex& e) const 00129 { 00130 return ((*cm_)[e] == component_); 00131 } 00132 00133 protected: 00134 ComponentMap* cm_; 00135 Position component_; 00136 }; 00137 00138 MolecularGraph const* input_; 00139 std::vector<boost::shared_ptr<EditableGraph> > components_; 00140 00141 std::vector<boost::shared_ptr<TreeDecomposition> > nice_tree_decompositions_; 00142 std::vector<boost::shared_ptr<TreeDecompositionGraph> > nice_tree_decomposition_graphs_; 00143 }; 00144 00145 template <class UndirectedGraph> 00146 class TreeWidthImplementation 00147 { 00148 public: 00149 00150 typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor VertexType; 00151 typedef typename boost::graph_traits<UndirectedGraph>::adjacency_iterator NeighbourIterator; 00152 typedef typename boost::graph_traits<UndirectedGraph>::vertex_iterator VertexIterator; 00153 00160 typedef std::pair<std::vector<Size>, Size> EliminationOrder; 00161 00172 template<class Criterion, class Reducer> 00173 class GeneralLowerBoundAlgorithm 00174 : public UnaryFunctor<UndirectedGraph, Size> 00175 { 00176 public: 00177 GeneralLowerBoundAlgorithm() {} 00178 00179 virtual Size operator() (UndirectedGraph const& originalGraph); 00180 }; 00181 00188 class MinorMinWidthReducer 00189 { 00190 public: 00191 MinorMinWidthReducer(UndirectedGraph& graph); 00192 00193 void operator() (VertexType& vertex); 00194 void contractEdge(VertexType& u, VertexType& v); 00195 00196 protected: 00197 UndirectedGraph& graph_; 00198 }; 00199 00203 class MinorMinWidthCriterion 00204 { 00205 public: 00206 MinorMinWidthCriterion(UndirectedGraph const& graph); 00207 00208 Size operator() (VertexType& vertex) const; 00209 00210 protected: 00211 UndirectedGraph const& graph_; 00212 }; 00213 00230 /*template <class UndirectedGraph> 00231 class MinorMinWidth 00232 : public GeneralLowerBoundAlgorithm<UndirectedGraph, MinorMinWidthCriterion<UndirectedGraph>, 00233 MinorMinWidthReducer<UndirectedGraph> > 00234 { 00235 }; 00236 */ 00237 typedef GeneralLowerBoundAlgorithm<MinorMinWidthCriterion, MinorMinWidthReducer> MinorMinWidth; 00238 00239 00255 template<class Criterion> 00256 class GreedyX 00257 : public UnaryFunctor<UndirectedGraph, typename std::pair< 00258 std::vector<boost::graph_traits<typename UndirectedGraph::vertex_descriptor> >, Size> > 00259 { 00260 public: 00261 EliminationOrder operator() (UndirectedGraph& original_graph); 00262 }; 00263 00268 struct FillInHeuristic 00269 { 00270 VertexType& operator() (UndirectedGraph& graph); 00271 00272 Size edgeIncreaseByEliminating(VertexIterator vertex, UndirectedGraph& graph); 00273 }; 00274 00284 template <class Lowerbound=MinorMinWidth, class Upperbound=GreedyX<FillInHeuristic> > 00285 class QuickBB 00286 { 00287 public: 00293 enum SIMPLICIAL_TYPE 00294 { 00295 NOT_SIMPLICIAL, 00296 ALMOST_SIMPLICIAL, 00297 IS_SIMPLICIAL 00298 }; 00299 00303 QuickBB(UndirectedGraph const& graph); 00304 00308 EliminationOrder compute(); 00309 00310 SIMPLICIAL_TYPE isSimplicial(VertexType& vertex) const; 00311 00312 protected: 00316 struct QuickBBState 00317 { 00321 unsigned int g; 00322 00326 unsigned int h; 00327 00331 unsigned int f; 00332 00336 std::vector<Size> permutation; 00337 }; 00338 00339 typedef std::map<VertexType, bool> BitSet; 00340 typedef std::map<BitSet, Size> GraphMap; 00341 typedef std::pair<typename GraphMap::iterator, bool> MapPos; 00342 typedef std::pair<BitSet, Size> MapEntry; 00343 00347 UndirectedGraph graph_; 00348 00352 QuickBBState state; 00353 00357 EliminationOrder greedy_solution; 00358 00362 EliminationOrder own_solution; 00363 00368 GraphMap visitedSubgraphs; 00369 00375 Size upper_bound; 00376 00386 void branchAndBound(QuickBBState& nstate); 00387 00394 void prune(QuickBBState&); 00395 00399 BitSet buildBitset() const; 00400 }; 00401 00411 typedef GreedyX<FillInHeuristic> GreedyFillIn; 00412 00413 template <class OriginalGraphType> 00414 class TreeDecompositionBuilder 00415 { 00416 public: 00417 typedef typename TreeWidth<OriginalGraphType>::TreeDecomposition TreeDecomposition; 00418 typedef typename TreeWidth<OriginalGraphType>::TreeDecompositionBag TreeDecompositionBag; 00419 typedef typename TreeWidth<OriginalGraphType>::TreeDecompositionGraph TreeDecompositionGraph; 00420 00421 typedef typename TreeWidth<OriginalGraphType>::OriginalVertexType OriginalVertexType; 00422 00423 typedef std::set<OriginalVertexType> TreeDecompositionContent; 00424 00431 boost::shared_ptr<TreeDecomposition> operator() (UndirectedGraph const& graph, EliminationOrder const& permutation); 00432 00442 boost::shared_ptr<TreeDecomposition> makeNice(boost::shared_ptr<TreeDecompositionGraph>& nice_tree); 00443 00444 TreeDecompositionBag operator() (TreeDecompositionBag n, 00445 typename std::vector<TreeDecompositionBag>::iterator c_i, typename std::vector<TreeDecompositionBag>::iterator c_end); 00446 00447 protected: 00448 TreeDecompositionBag buildRoot_(TreeDecompositionBag child); 00449 TreeDecompositionBag buildLeaf_(TreeDecompositionBag child); 00450 TreeDecompositionBag buildJoin_(TreeDecompositionBag node, TreeDecompositionBag left, 00451 TreeDecompositionBag right, bool do_forget); 00452 00453 TreeDecompositionBag buildSingle_(TreeDecompositionBag node, int node_type, 00454 TreeDecompositionBag child); 00455 00456 TreeDecompositionBag buildLinkage_(TreeDecompositionBag node, TreeDecompositionBag child); 00457 00458 TreeDecompositionBag linkWithIntroduceNodes_(TreeDecompositionContent parent_set, TreeDecompositionBag child); 00459 TreeDecompositionBag linkWithForgetNodes_ (TreeDecompositionContent parent_set, TreeDecompositionBag child); 00460 00461 TreeDecompositionBag branch_(TreeDecompositionBag node, int node_type, 00462 typename std::vector<TreeDecompositionBag>::iterator begin, 00463 typename std::vector<TreeDecompositionBag>::iterator end); 00464 00465 boost::shared_ptr<TreeDecomposition> tree_; 00466 boost::shared_ptr<TreeDecompositionGraph> tree_graph_; 00467 boost::shared_ptr<TreeDecompositionGraph> nice_tree_; 00468 00469 TreeDecompositionBag root_; 00470 }; 00471 00472 }; 00473 } 00474 00475 #include <BALL/DATATYPE/GRAPH/treeWidth.iC> 00476 00477 #endif // BALL_DATATYPE_GRAPH_TREEWIDTH_H