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