treeWidth.h

Go to the documentation of this file.

// -*- Mode: C++; tab-width: 2; -*-
// vi: set ts=2:
//

#ifndef BALL_DATATYPE_GRAPH_TREEWIDTH_H
#define BALL_DATATYPE_GRAPH_TREEWIDTH_H

#ifndef BALL_COMMON_GLOBAL_H
# include <BALL/COMMON/global.h>
#endif

#ifndef BALL_COMMON_EXCEPTION_H
# include <BALL/COMMON/exception.h>
#endif

#ifndef BALL_CONCEPT_BASEFUNCTOR_H
# include <BALL/CONCEPT/baseFunctor.h>
#endif

#ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
# include <BALL/DATATYPE/GRAPH/graphAlgorithms.h>
#endif

#ifndef BALL_DATATYPE_GRAPH_MOLECULARGRAPH_H
# include <BALL/DATATYPE/GRAPH/molecularGraph.h>
#endif

#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <vector>
#include <iostream>

#include <boost/graph/connected_components.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_as_tree.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/copy.hpp>

namespace boost
{
  enum vertex_bag_content_t { vertex_bag_content };
  enum vertex_bag_special_t { vertex_bag_special };
  enum vertex_bag_type_t    { vertex_bag_type    };

  BOOST_INSTALL_PROPERTY(vertex, bag_content);
  BOOST_INSTALL_PROPERTY(vertex, bag_special);
  BOOST_INSTALL_PROPERTY(vertex, bag_type);
}

namespace BALL
{
  template <class EditableGraph> class TreeWidthImplementation;
  template <class UndirectedGraph>
  class TreeWidth
  {
    public:
      enum BagType {
        INTRODUCE_BAG,
        LEAF_BAG,
        FORGET_BAG,
        ROOT_BAG,
        JOIN_BAG,
        INNER_BAG,
        END_BAG
      };

      typedef typename GRAPH::GraphTraits<UndirectedGraph>::EditableGraph      EditableGraph;
      typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor OriginalVertexType;

      typedef std::set<OriginalVertexType> TreeDecompositionContent;

      typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                                      boost::property<boost::vertex_bag_content_t, std::set<OriginalVertexType>,
                                      boost::property<boost::vertex_bag_special_t, OriginalVertexType,
                                      boost::property<boost::vertex_bag_type_t, int> > >,
                                    boost::no_property> TreeDecompositionGraph;

      typedef typename boost::graph_traits<TreeDecompositionGraph>::vertex_descriptor TreeDecompositionBag;

      typedef boost::iterator_property_map<typename std::vector<TreeDecompositionBag>::iterator,
                                           typename boost::property_map<TreeDecompositionGraph, boost::vertex_index_t>::type>
                                           TreeDecompositionParentMap;
      typedef boost::graph_as_tree<TreeDecompositionGraph, TreeDecompositionParentMap> TreeDecomposition;

      TreeWidth(UndirectedGraph const& input);

      static Size computeTreeWidth(TreeDecomposition const& td);

      void writeGraphvizFile(std::ostream& out, TreeDecomposition const& td);

      std::vector<boost::shared_ptr<EditableGraph> >& getComponents() { return components_; }
      std::vector<boost::shared_ptr<TreeDecomposition> >& getNiceTreeDecompositions()   { return nice_tree_decompositions_; }

    protected:
      template <typename ComponentMap>
      class ComponentFilter_
      {
        public:
          ComponentFilter_(ComponentMap cm, Position i)
            : cm_(cm),
              component_(i)
          { }

          template <typename Vertex>
          bool operator() (const Vertex& e) const 
          {
            return ((cm_)[e] == component_);
          }

        protected:
          ComponentMap  cm_;
          Position      component_;
      };

      class BagContentWriter 
      {
        public:
          BagContentWriter(TreeDecomposition const* td, UndirectedGraph const* original_graph)
            : td_(td),
              original_graph_(original_graph)
          { }

          void operator() (std::ostream& out, const TreeDecompositionBag& v) const;

        protected:
          TreeDecomposition const* td_;
          UndirectedGraph   const* original_graph_;
      };

      // TODO: would UndirectedGraph suffice here?
      MolecularGraph const* input_;

      std::vector<boost::shared_ptr<EditableGraph> > components_;

      std::vector<boost::shared_ptr<TreeDecomposition> >      nice_tree_decompositions_;
      std::vector<boost::shared_ptr<TreeDecompositionGraph> > nice_tree_decomposition_graphs_;
  };

  template <class UndirectedGraph>
  class TreeWidthImplementation
  {
    public:

    typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor  VertexType;
    typedef typename boost::graph_traits<UndirectedGraph>::adjacency_iterator NeighbourIterator;
    typedef typename boost::graph_traits<UndirectedGraph>::vertex_iterator    VertexIterator;

    typedef std::pair<std::vector<Size>, Size> EliminationOrder;

    template<class Criterion, class Reducer>
    class GeneralLowerBoundAlgorithm
      : public UnaryFunctor<UndirectedGraph, Size>
    {
      public:
        GeneralLowerBoundAlgorithm() {}

        virtual Size operator() (UndirectedGraph const& originalGraph);
    };

    class MinorMinWidthReducer
    {
      public:
        MinorMinWidthReducer(UndirectedGraph& graph);

        void operator() (VertexType& vertex);
        void contractEdge(VertexType& u, VertexType& v);

      protected:
        UndirectedGraph& graph_;
    };

    class MinorMinWidthCriterion
    {
      public:
        MinorMinWidthCriterion(UndirectedGraph const& graph);

        Size operator() (VertexType& vertex) const;

      protected:
        UndirectedGraph const& graph_;
    };

    /*template <class UndirectedGraph>
    class MinorMinWidth
      : public GeneralLowerBoundAlgorithm<UndirectedGraph, MinorMinWidthCriterion<UndirectedGraph>, 
                                          MinorMinWidthReducer<UndirectedGraph> >
    {
    };
    */
    typedef GeneralLowerBoundAlgorithm<MinorMinWidthCriterion, MinorMinWidthReducer> MinorMinWidth;


    template<class Criterion>
    class GreedyX
      : public UnaryFunctor<UndirectedGraph, typename std::pair<
        std::vector<boost::graph_traits<typename UndirectedGraph::vertex_descriptor> >, Size> >
    {
      public:
        EliminationOrder operator() (UndirectedGraph& original_graph);
    };

    struct FillInHeuristic
    {
      VertexType& operator() (UndirectedGraph& graph);

      Size edgeIncreaseByEliminating(VertexIterator vertex, UndirectedGraph& graph);
    };

    template <class Lowerbound=MinorMinWidth, class Upperbound=GreedyX<FillInHeuristic> >
    class QuickBB
    {
      public:
        enum SIMPLICIAL_TYPE
        {
          NOT_SIMPLICIAL,
          ALMOST_SIMPLICIAL,
          IS_SIMPLICIAL
        };

        QuickBB(UndirectedGraph const& graph);

        EliminationOrder compute();

        SIMPLICIAL_TYPE isSimplicial(VertexType& vertex) const;

      protected:
        struct QuickBBState
        {
          unsigned int g;

          unsigned int h;

          unsigned int f;

          std::vector<Size> permutation;
        };

        typedef std::map<VertexType, bool> BitSet;
        typedef std::map<BitSet, Size> GraphMap;
        typedef std::pair<typename GraphMap::iterator, bool> MapPos;
        typedef std::pair<BitSet, Size> MapEntry;

        UndirectedGraph graph_;

        QuickBBState state;

        EliminationOrder greedy_solution;

        EliminationOrder own_solution;

        GraphMap visitedSubgraphs;

        Size upper_bound;

        void branchAndBound(QuickBBState& nstate);

        void prune(QuickBBState&);

        BitSet buildBitset() const;

      protected:
        std::map<int, VertexType> index_to_vertex_;
    };

    typedef GreedyX<FillInHeuristic> GreedyFillIn;

    template <class OriginalGraphType>
    class TreeDecompositionBuilder
    {
      public:
        typedef typename TreeWidth<OriginalGraphType>::TreeDecomposition    TreeDecomposition;
        typedef typename TreeWidth<OriginalGraphType>::TreeDecompositionBag TreeDecompositionBag;
        typedef typename TreeWidth<OriginalGraphType>::TreeDecompositionGraph TreeDecompositionGraph;

        typedef typename TreeWidth<OriginalGraphType>::OriginalVertexType OriginalVertexType;

        typedef std::set<OriginalVertexType> TreeDecompositionContent;

        boost::shared_ptr<TreeDecomposition> operator() (UndirectedGraph const& graph, EliminationOrder const& permutation);

        boost::shared_ptr<TreeDecomposition> makeNice(boost::shared_ptr<TreeDecompositionGraph>& nice_tree);

        TreeDecompositionBag operator() (TreeDecompositionBag n,
          typename std::vector<TreeDecompositionBag>::iterator c_i, typename std::vector<TreeDecompositionBag>::iterator c_end);

      protected:
        TreeDecompositionBag buildRoot_(TreeDecompositionBag child);
        TreeDecompositionBag buildLeaf_(TreeDecompositionBag child);
        TreeDecompositionBag buildJoin_(TreeDecompositionBag node, TreeDecompositionBag left,
                                          TreeDecompositionBag right, bool do_forget);

        TreeDecompositionBag buildSingle_(TreeDecompositionBag node, int node_type,
                                            TreeDecompositionBag child);

        TreeDecompositionBag buildLinkage_(TreeDecompositionBag node, TreeDecompositionBag child);

        TreeDecompositionBag linkWithIntroduceNodes_(TreeDecompositionContent parent_set, TreeDecompositionBag child);
        TreeDecompositionBag linkWithForgetNodes_   (TreeDecompositionContent parent_set, TreeDecompositionBag child);

        TreeDecompositionBag branch_(TreeDecompositionBag node, int node_type,
                                       typename std::vector<TreeDecompositionBag>::iterator begin,
                                       typename std::vector<TreeDecompositionBag>::iterator end);

        boost::shared_ptr<TreeDecomposition> tree_;
        boost::shared_ptr<TreeDecompositionGraph> tree_graph_;
        boost::shared_ptr<TreeDecompositionGraph> nice_tree_;

        TreeDecompositionBag root_;
    };

  };
}

#include <BALL/DATATYPE/GRAPH/treeWidth.iC>

#endif // BALL_DATATYPE_GRAPH_TREEWIDTH_H