BALL  1.5.0
treeWidth.h
Go to the documentation of this file.
1 // -*- Mode: C++; tab-width: 2; -*-
2 // vi: set ts=2:
3 //
4 
5 #ifndef BALL_DATATYPE_GRAPH_TREEWIDTH_H
6 #define BALL_DATATYPE_GRAPH_TREEWIDTH_H
7 
8 #ifndef BALL_COMMON_GLOBAL_H
9 # include <BALL/COMMON/global.h>
10 #endif
11 
12 #ifndef BALL_COMMON_EXCEPTION_H
13 # include <BALL/COMMON/exception.h>
14 #endif
15 
16 #ifndef BALL_CONCEPT_BASEFUNCTOR_H
18 #endif
19 
20 #ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H
22 #endif
23 
24 #ifndef BALL_DATATYPE_GRAPH_MOLECULARGRAPH_H
26 #endif
27 
28 #include <algorithm>
29 #include <functional>
30 #include <map>
31 #include <set>
32 #include <vector>
33 #include <iostream>
34 
35 #include <boost/graph/connected_components.hpp>
36 #include <boost/graph/filtered_graph.hpp>
37 #include <boost/graph/graph_as_tree.hpp>
38 #include <boost/graph/graphviz.hpp>
39 #include <boost/graph/copy.hpp>
40 
41 namespace boost
42 {
46 
47  BOOST_INSTALL_PROPERTY(vertex, bag_content);
48  BOOST_INSTALL_PROPERTY(vertex, bag_special);
49  BOOST_INSTALL_PROPERTY(vertex, bag_type);
50 }
51 
52 namespace BALL
53 {
54  template <class EditableGraph> class TreeWidthImplementation;
58  template <class UndirectedGraph>
59  class TreeWidth
60  {
61  public:
65  enum BagType {
94  };
95 
97  typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor OriginalVertexType;
98 
99  typedef std::set<OriginalVertexType> TreeDecompositionContent;
100 
101  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
102  boost::property<boost::vertex_bag_content_t, std::set<OriginalVertexType>,
104  boost::property<boost::vertex_bag_type_t, int> > >,
105  boost::no_property> TreeDecompositionGraph;
106 
107  typedef typename boost::graph_traits<TreeDecompositionGraph>::vertex_descriptor TreeDecompositionBag;
108 
109  typedef boost::iterator_property_map<typename std::vector<TreeDecompositionBag>::iterator,
110  typename boost::property_map<TreeDecompositionGraph, boost::vertex_index_t>::type>
112  typedef boost::graph_as_tree<TreeDecompositionGraph, TreeDecompositionParentMap> TreeDecomposition;
113 
114  TreeWidth(UndirectedGraph const& input);
115 
120  static Size computeTreeWidth(TreeDecomposition const& td);
121 
124  void writeGraphvizFile(std::ostream& out, TreeDecomposition const& td);
125 
126  std::vector<boost::shared_ptr<EditableGraph> >& getComponents() { return components_; }
127  std::vector<boost::shared_ptr<TreeDecomposition> >& getNiceTreeDecompositions() { return nice_tree_decompositions_; }
128 
129  protected:
130  template <typename ComponentMap>
132  {
133  public:
134  ComponentFilter_(ComponentMap cm, Position i)
135  : cm_(cm),
136  component_(i)
137  { }
138 
139  template <typename Vertex>
140  bool operator() (const Vertex& e) const
141  {
142  return ((cm_)[e] == component_);
143  }
144 
145  protected:
146  ComponentMap cm_;
148  };
149 
153  {
154  public:
155  BagContentWriter(TreeDecomposition const* td, UndirectedGraph const* original_graph)
156  : td_(td),
157  original_graph_(original_graph)
158  { }
159 
160  void operator() (std::ostream& out, const TreeDecompositionBag& v) const;
161 
162  protected:
164  UndirectedGraph const* original_graph_;
165  };
166 
167  // TODO: would UndirectedGraph suffice here?
169 
170  std::vector<boost::shared_ptr<EditableGraph> > components_;
171 
172  std::vector<boost::shared_ptr<TreeDecomposition> > nice_tree_decompositions_;
173  std::vector<boost::shared_ptr<TreeDecompositionGraph> > nice_tree_decomposition_graphs_;
174  };
175 
176  template <class UndirectedGraph>
178  {
179  public:
180 
181  typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor VertexType;
182  typedef typename boost::graph_traits<UndirectedGraph>::adjacency_iterator NeighbourIterator;
183  typedef typename boost::graph_traits<UndirectedGraph>::vertex_iterator VertexIterator;
184 
191  typedef std::pair<std::vector<Size>, Size> EliminationOrder;
192 
203  template<class Criterion, class Reducer>
205  : public UnaryFunctor<UndirectedGraph, Size>
206  {
207  public:
209 
210  virtual Size operator() (UndirectedGraph const& originalGraph);
211  };
212 
220  {
221  public:
222  MinorMinWidthReducer(UndirectedGraph& graph);
223 
224  void operator() (VertexType& vertex);
225  void contractEdge(VertexType& u, VertexType& v);
226 
227  protected:
228  UndirectedGraph& graph_;
229  };
230 
235  {
236  public:
237  MinorMinWidthCriterion(UndirectedGraph const& graph);
238 
239  Size operator() (VertexType& vertex) const;
240 
241  protected:
242  UndirectedGraph const& graph_;
243  };
244 
261  /*template <class UndirectedGraph>
262  class MinorMinWidth
263  : public GeneralLowerBoundAlgorithm<UndirectedGraph, MinorMinWidthCriterion<UndirectedGraph>,
264  MinorMinWidthReducer<UndirectedGraph> >
265  {
266  };
267  */
269 
270 
286  template<class Criterion>
287  class GreedyX
288  : public UnaryFunctor<UndirectedGraph, typename std::pair<
289  std::vector<boost::graph_traits<typename UndirectedGraph::vertex_descriptor> >, Size> >
290  {
291  public:
292  EliminationOrder operator() (UndirectedGraph& original_graph);
293  };
294 
300  {
301  VertexType& operator() (UndirectedGraph& graph);
302 
303  Size edgeIncreaseByEliminating(VertexIterator vertex, UndirectedGraph& graph);
304  };
305 
315  template <class Lowerbound=MinorMinWidth, class Upperbound=GreedyX<FillInHeuristic> >
316  class QuickBB
317  {
318  public:
325  {
329  };
330 
334  QuickBB(UndirectedGraph const& graph);
335 
340 
341  SIMPLICIAL_TYPE isSimplicial(VertexType& vertex) const;
342 
343  protected:
348  {
352  unsigned int g;
353 
357  unsigned int h;
358 
362  unsigned int f;
363 
367  std::vector<Size> permutation;
368  };
369 
370  typedef std::map<VertexType, bool> BitSet;
371  typedef std::map<BitSet, Size> GraphMap;
372  typedef std::pair<typename GraphMap::iterator, bool> MapPos;
373  typedef std::pair<BitSet, Size> MapEntry;
374 
378  UndirectedGraph graph_;
379 
384 
389 
394 
400 
407 
417  void branchAndBound(QuickBBState& nstate);
418 
425  void prune(QuickBBState&);
426 
430  BitSet buildBitset() const;
431 
432  protected:
433  std::map<int, VertexType> index_to_vertex_;
434  };
435 
446 
447  template <class OriginalGraphType>
449  {
450  public:
454 
456 
457  typedef std::set<OriginalVertexType> TreeDecompositionContent;
458 
465  boost::shared_ptr<TreeDecomposition> operator() (UndirectedGraph const& graph, EliminationOrder const& permutation);
466 
476  boost::shared_ptr<TreeDecomposition> makeNice(boost::shared_ptr<TreeDecompositionGraph>& nice_tree);
477 
479  typename std::vector<TreeDecompositionBag>::iterator c_i, typename std::vector<TreeDecompositionBag>::iterator c_end);
480 
481  protected:
485  TreeDecompositionBag right, bool do_forget);
486 
488  TreeDecompositionBag child);
489 
491 
494 
496  typename std::vector<TreeDecompositionBag>::iterator begin,
497  typename std::vector<TreeDecompositionBag>::iterator end);
498 
499  boost::shared_ptr<TreeDecomposition> tree_;
500  boost::shared_ptr<TreeDecompositionGraph> tree_graph_;
501  boost::shared_ptr<TreeDecompositionGraph> nice_tree_;
502 
504  };
505 
506  };
507 }
508 
509 #include <BALL/DATATYPE/GRAPH/treeWidth.iC>
510 
511 #endif // BALL_DATATYPE_GRAPH_TREEWIDTH_H
boost::vertex_bag_special_t
vertex_bag_special_t
Definition: treeWidth.h:44
BALL::TreeWidthImplementation::GreedyFillIn
GreedyX< FillInHeuristic > GreedyFillIn
Definition: treeWidth.h:445
BALL::TreeWidthImplementation::QuickBB::ALMOST_SIMPLICIAL
Definition: treeWidth.h:327
BALL::TreeWidthImplementation::QuickBB::QuickBBState::f
unsigned int f
Definition: treeWidth.h:362
BALL::TreeWidth::EditableGraph
GRAPH::GraphTraits< UndirectedGraph >::EditableGraph EditableGraph
Definition: treeWidth.h:96
BALL::TreeWidth::ComponentFilter_
Definition: treeWidth.h:131
BALL::TreeWidthImplementation::QuickBB::NOT_SIMPLICIAL
Definition: treeWidth.h:326
BALL::TreeWidthImplementation::QuickBB::isSimplicial
SIMPLICIAL_TYPE isSimplicial(VertexType &vertex) const
BALL::TreeWidth::TreeDecompositionContent
std::set< OriginalVertexType > TreeDecompositionContent
Definition: treeWidth.h:99
BALL::TreeWidth::BagContentWriter::original_graph_
UndirectedGraph const * original_graph_
Definition: treeWidth.h:164
BALL::TreeWidthImplementation::QuickBB::GraphMap
std::map< BitSet, Size > GraphMap
Definition: treeWidth.h:371
BALL::TreeWidthImplementation::QuickBB::QuickBBState::permutation
std::vector< Size > permutation
Definition: treeWidth.h:367
BALL::TreeWidth::ComponentFilter_::component_
Position component_
Definition: treeWidth.h:147
BALL::TreeWidthImplementation::QuickBB::branchAndBound
void branchAndBound(QuickBBState &nstate)
BALL::TreeWidthImplementation
Definition: treeWidth.h:54
BALL::TreeWidth::LEAF_BAG
Definition: treeWidth.h:73
BALL::TreeWidthImplementation::TreeDecompositionBuilder
Definition: treeWidth.h:448
BALL::TreeWidthImplementation::TreeDecompositionBuilder::tree_
boost::shared_ptr< TreeDecomposition > tree_
Definition: treeWidth.h:499
BALL::TreeWidthImplementation::QuickBB::prune
void prune(QuickBBState &)
BALL::TreeWidth::input_
MolecularGraph const * input_
Definition: treeWidth.h:168
BALL::TreeWidthImplementation::TreeDecompositionBuilder::root_
TreeDecompositionBag root_
Definition: treeWidth.h:503
BALL::TreeWidth::JOIN_BAG
Definition: treeWidth.h:85
BALL::TreeWidthImplementation::NeighbourIterator
boost::graph_traits< UndirectedGraph >::adjacency_iterator NeighbourIterator
Definition: treeWidth.h:182
BALL::TreeWidthImplementation::QuickBB
Definition: treeWidth.h:316
BALL::VIEW::Vertex
Definition: vertex1.h:31
BALL::TreeWidthImplementation::GreedyX::operator()
EliminationOrder operator()(UndirectedGraph &original_graph)
BALL::TreeWidthImplementation::EliminationOrder
std::pair< std::vector< Size >, Size > EliminationOrder
Definition: treeWidth.h:191
BALL::TreeWidthImplementation::TreeDecompositionBuilder::TreeDecompositionGraph
TreeWidth< OriginalGraphType >::TreeDecompositionGraph TreeDecompositionGraph
Definition: treeWidth.h:453
BALL::TreeWidthImplementation::MinorMinWidthCriterion
Definition: treeWidth.h:234
BALL::TreeWidthImplementation::TreeDecompositionBuilder::buildJoin_
TreeDecompositionBag buildJoin_(TreeDecompositionBag node, TreeDecompositionBag left, TreeDecompositionBag right, bool do_forget)
BALL::TreeWidthImplementation::MinorMinWidthCriterion::MinorMinWidthCriterion
MinorMinWidthCriterion(UndirectedGraph const &graph)
BALL::TreeWidthImplementation::GeneralLowerBoundAlgorithm::GeneralLowerBoundAlgorithm
GeneralLowerBoundAlgorithm()
Definition: treeWidth.h:208
BALL::TreeWidth::TreeWidth
TreeWidth(UndirectedGraph const &input)
BALL_SIZE_TYPE
BALL::TreeWidth::TreeDecompositionBag
boost::graph_traits< TreeDecompositionGraph >::vertex_descriptor TreeDecompositionBag
Definition: treeWidth.h:107
BALL::TreeWidthImplementation::MinorMinWidthReducer::graph_
UndirectedGraph & graph_
Definition: treeWidth.h:228
BALL::TreeWidth::OriginalVertexType
boost::graph_traits< UndirectedGraph >::vertex_descriptor OriginalVertexType
Definition: treeWidth.h:97
boost
Definition: graphAlgorithms.h:26
BALL::TreeWidthImplementation::TreeDecompositionBuilder::linkWithIntroduceNodes_
TreeDecompositionBag linkWithIntroduceNodes_(TreeDecompositionContent parent_set, TreeDecompositionBag child)
BALL::TreeWidthImplementation::MinorMinWidthReducer::MinorMinWidthReducer
MinorMinWidthReducer(UndirectedGraph &graph)
BALL::TreeWidth::TreeDecompositionParentMap
boost::iterator_property_map< typename std::vector< TreeDecompositionBag >::iterator, typename boost::property_map< TreeDecompositionGraph, boost::vertex_index_t >::type > TreeDecompositionParentMap
Definition: treeWidth.h:111
BALL::TreeWidthImplementation::GeneralLowerBoundAlgorithm
Generic lower bound algorithm on graphs.
Definition: treeWidth.h:204
BALL::TreeWidthImplementation::QuickBB::QuickBB
QuickBB(UndirectedGraph const &graph)
graphAlgorithms.h
BALL::TreeWidth::nice_tree_decompositions_
std::vector< boost::shared_ptr< TreeDecomposition > > nice_tree_decompositions_
Definition: treeWidth.h:172
BALL::GRAPH::GraphTraits::EditableGraph
boost::adjacency_list< boost::listS, boost::listS, boost::undirectedS, boost::property< boost::vertex_orig_ptr_t, VertexType, boost::property< boost::vertex_index_t, int > >, boost::property< boost::edge_orig_ptr_t, EdgeType > > EditableGraph
Definition: graphAlgorithms.h:88
BALL
Definition: constants.h:12
BALL::TreeWidthImplementation::FillInHeuristic::edgeIncreaseByEliminating
Size edgeIncreaseByEliminating(VertexIterator vertex, UndirectedGraph &graph)
boost::vertex_bag_type_t
vertex_bag_type_t
Definition: treeWidth.h:45
BALL::TreeWidth::BagContentWriter::operator()
void operator()(std::ostream &out, const TreeDecompositionBag &v) const
BALL::TreeWidth::components_
std::vector< boost::shared_ptr< EditableGraph > > components_
Definition: treeWidth.h:170
BALL::TreeWidth::writeGraphvizFile
void writeGraphvizFile(std::ostream &out, TreeDecomposition const &td)
boost::BOOST_INSTALL_PROPERTY
BOOST_INSTALL_PROPERTY(vertex, atom_ptr)
BALL::TreeWidthImplementation::QuickBB::BitSet
std::map< VertexType, bool > BitSet
Definition: treeWidth.h:370
exception.h
BALL::TreeWidthImplementation::QuickBB::own_solution
EliminationOrder own_solution
Definition: treeWidth.h:393
BALL::TreeWidthImplementation::TreeDecompositionBuilder::tree_graph_
boost::shared_ptr< TreeDecompositionGraph > tree_graph_
Definition: treeWidth.h:500
BALL::TreeWidth::ComponentFilter_::ComponentFilter_
ComponentFilter_(ComponentMap cm, Position i)
Definition: treeWidth.h:134
BALL::TreeWidthImplementation::QuickBB::MapPos
std::pair< typename GraphMap::iterator, bool > MapPos
Definition: treeWidth.h:372
BALL::TreeWidthImplementation::TreeDecompositionBuilder::TreeDecomposition
TreeWidth< OriginalGraphType >::TreeDecomposition TreeDecomposition
Definition: treeWidth.h:451
boost::vertex_bag_special
Definition: treeWidth.h:44
BALL::TreeWidthImplementation::TreeDecompositionBuilder::OriginalVertexType
TreeWidth< OriginalGraphType >::OriginalVertexType OriginalVertexType
Definition: treeWidth.h:455
BALL::TreeWidthImplementation::FillInHeuristic
Definition: treeWidth.h:299
BALL::TreeWidth::BagContentWriter::BagContentWriter
BagContentWriter(TreeDecomposition const *td, UndirectedGraph const *original_graph)
Definition: treeWidth.h:155
BALL::TreeWidthImplementation::MinorMinWidthReducer::contractEdge
void contractEdge(VertexType &u, VertexType &v)
BALL::TreeWidthImplementation::TreeDecompositionBuilder::linkWithForgetNodes_
TreeDecompositionBag linkWithForgetNodes_(TreeDecompositionContent parent_set, TreeDecompositionBag child)
BALL::TreeWidthImplementation::TreeDecompositionBuilder::TreeDecompositionBag
TreeWidth< OriginalGraphType >::TreeDecompositionBag TreeDecompositionBag
Definition: treeWidth.h:452
boost::vertex_bag_content_t
vertex_bag_content_t
Definition: treeWidth.h:43
baseFunctor.h
BALL::TreeWidthImplementation::QuickBB::greedy_solution
EliminationOrder greedy_solution
Definition: treeWidth.h:388
BALL::TreeWidthImplementation::MinorMinWidthCriterion::operator()
Size operator()(VertexType &vertex) const
BALL::TreeWidth::getNiceTreeDecompositions
std::vector< boost::shared_ptr< TreeDecomposition > > & getNiceTreeDecompositions()
Definition: treeWidth.h:127
BALL::TreeWidthImplementation::MinorMinWidthReducer::operator()
void operator()(VertexType &vertex)
BALL::TreeWidthImplementation::QuickBB::QuickBBState::h
unsigned int h
Definition: treeWidth.h:357
BALL::TreeWidth::INNER_BAG
Definition: treeWidth.h:89
BALL::TreeWidth::FORGET_BAG
Definition: treeWidth.h:77
BALL::TreeWidthImplementation::QuickBB::graph_
UndirectedGraph graph_
Definition: treeWidth.h:378
BALL::TreeWidthImplementation::TreeDecompositionBuilder::buildLeaf_
TreeDecompositionBag buildLeaf_(TreeDecompositionBag child)
BALL::TreeWidthImplementation::MinorMinWidth
GeneralLowerBoundAlgorithm< MinorMinWidthCriterion, MinorMinWidthReducer > MinorMinWidth
Definition: treeWidth.h:268
BALL::TreeWidthImplementation::QuickBB::IS_SIMPLICIAL
Definition: treeWidth.h:328
BALL::TreeWidthImplementation::TreeDecompositionBuilder::makeNice
boost::shared_ptr< TreeDecomposition > makeNice(boost::shared_ptr< TreeDecompositionGraph > &nice_tree)
boost::vertex_bag_content
Definition: treeWidth.h:43
BALL::UnaryFunctor
Definition: baseFunctor.h:25
BALL::TreeWidth
Definition: treeWidth.h:59
BALL::TreeWidthImplementation::QuickBB::QuickBBState
Definition: treeWidth.h:347
BALL::TreeWidth::BagContentWriter::td_
TreeDecomposition const * td_
Definition: treeWidth.h:163
molecularGraph.h
BALL::TreeWidthImplementation::GreedyX
Definition: treeWidth.h:287
BALL::MolecularGraph
Definition: molecularGraph.h:46
BALL::TreeWidthImplementation::QuickBB::compute
EliminationOrder compute()
BALL::TreeWidth::getComponents
std::vector< boost::shared_ptr< EditableGraph > > & getComponents()
Definition: treeWidth.h:126
BALL::TreeWidthImplementation::MinorMinWidthReducer
Definition: treeWidth.h:219
BALL::TreeWidthImplementation::QuickBB::upper_bound
Size upper_bound
Definition: treeWidth.h:406
BALL::TreeWidthImplementation::QuickBB::buildBitset
BitSet buildBitset() const
BALL::TreeWidthImplementation::QuickBB::QuickBBState::g
unsigned int g
Definition: treeWidth.h:352
BALL::TreeWidthImplementation::FillInHeuristic::operator()
VertexType & operator()(UndirectedGraph &graph)
BALL::TreeWidthImplementation::QuickBB::index_to_vertex_
std::map< int, VertexType > index_to_vertex_
Definition: treeWidth.h:433
global.h
BALL::TreeWidthImplementation::TreeDecompositionBuilder::operator()
boost::shared_ptr< TreeDecomposition > operator()(UndirectedGraph const &graph, EliminationOrder const &permutation)
BALL::TreeWidth::nice_tree_decomposition_graphs_
std::vector< boost::shared_ptr< TreeDecompositionGraph > > nice_tree_decomposition_graphs_
Definition: treeWidth.h:173
BALL::TreeWidth::INTRODUCE_BAG
Definition: treeWidth.h:69
BALL::TreeWidth::TreeDecomposition
boost::graph_as_tree< TreeDecompositionGraph, TreeDecompositionParentMap > TreeDecomposition
Definition: treeWidth.h:112
BALL::TreeWidth< OriginalGraphType >::BagType
BagType
Definition: treeWidth.h:65
BALL::TreeWidth::TreeDecompositionGraph
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
Definition: treeWidth.h:105
BALL::TreeWidthImplementation::QuickBB::MapEntry
std::pair< BitSet, Size > MapEntry
Definition: treeWidth.h:373
BALL::TreeWidthImplementation::QuickBB::visitedSubgraphs
GraphMap visitedSubgraphs
Definition: treeWidth.h:399
BALL::TreeWidthImplementation::TreeDecompositionBuilder::buildRoot_
TreeDecompositionBag buildRoot_(TreeDecompositionBag child)
BALL::TreeWidthImplementation::VertexIterator
boost::graph_traits< UndirectedGraph >::vertex_iterator VertexIterator
Definition: treeWidth.h:183
BALL::TreeWidth::END_BAG
Definition: treeWidth.h:93
BALL::TreeWidthImplementation::QuickBB::SIMPLICIAL_TYPE
SIMPLICIAL_TYPE
Definition: treeWidth.h:324
BALL::TreeWidth::computeTreeWidth
static Size computeTreeWidth(TreeDecomposition const &td)
BALL::TreeWidthImplementation::QuickBB::state
QuickBBState state
Definition: treeWidth.h:383
BALL::TreeWidthImplementation::MinorMinWidthCriterion::graph_
UndirectedGraph const & graph_
Definition: treeWidth.h:242
BALL::TreeWidthImplementation::TreeDecompositionBuilder::TreeDecompositionContent
std::set< OriginalVertexType > TreeDecompositionContent
Definition: treeWidth.h:457
BALL::TreeWidth::BagContentWriter
Definition: treeWidth.h:152
BALL::TreeWidthImplementation::TreeDecompositionBuilder::buildSingle_
TreeDecompositionBag buildSingle_(TreeDecompositionBag node, int node_type, TreeDecompositionBag child)
boost::vertex_bag_type
Definition: treeWidth.h:45
BALL::TreeWidthImplementation::TreeDecompositionBuilder::buildLinkage_
TreeDecompositionBag buildLinkage_(TreeDecompositionBag node, TreeDecompositionBag child)
BALL::TreeWidthImplementation::GeneralLowerBoundAlgorithm::operator()
virtual Size operator()(UndirectedGraph const &originalGraph)
BALL::TreeWidth::ROOT_BAG
Definition: treeWidth.h:81
BALL::TreeWidth::ComponentFilter_::cm_
ComponentMap cm_
Definition: treeWidth.h:146
BALL::TreeWidthImplementation::TreeDecompositionBuilder::branch_
TreeDecompositionBag branch_(TreeDecompositionBag node, int node_type, typename std::vector< TreeDecompositionBag >::iterator begin, typename std::vector< TreeDecompositionBag >::iterator end)
BALL::TreeWidthImplementation::VertexType
boost::graph_traits< UndirectedGraph >::vertex_descriptor VertexType
Definition: treeWidth.h:181
BALL::TreeWidth::ComponentFilter_::operator()
bool operator()(const Vertex &e) const
Definition: treeWidth.h:140
BALL::TreeWidthImplementation::TreeDecompositionBuilder::nice_tree_
boost::shared_ptr< TreeDecompositionGraph > nice_tree_
Definition: treeWidth.h:501