BALL 1.5.0
Loading...
Searching...
No Matches
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
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
41namespace 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
52namespace BALL
53{
54 template <class EditableGraph> class TreeWidthImplementation;
58 template <class UndirectedGraph>
60 {
61 public:
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
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);
226
227 protected:
228 UndirectedGraph& graph_;
229 };
230
235 {
236 public:
237 MinorMinWidthCriterion(UndirectedGraph const& graph);
238
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>
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> >
317 {
318 public:
330
334 QuickBB(UndirectedGraph const& graph);
335
340
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
418
426
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
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
vertex_bag_special_t
Definition treeWidth.h:44
@ vertex_bag_special
Definition treeWidth.h:44
vertex_bag_content_t
Definition treeWidth.h:43
@ vertex_bag_content
Definition treeWidth.h:43
vertex_bag_type_t
Definition treeWidth.h:45
@ vertex_bag_type
Definition treeWidth.h:45
BOOST_INSTALL_PROPERTY(vertex, atom_ptr)
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
GeneralLowerBoundAlgorithm< MinorMinWidthCriterion, MinorMinWidthReducer > MinorMinWidth
Definition treeWidth.h:268
boost::graph_traits< UndirectedGraph >::adjacency_iterator NeighbourIterator
Definition treeWidth.h:182
std::pair< std::vector< Size >, Size > EliminationOrder
Definition treeWidth.h:191
GreedyX< FillInHeuristic > GreedyFillIn
Definition treeWidth.h:445
boost::graph_traits< UndirectedGraph >::vertex_iterator VertexIterator
Definition treeWidth.h:183
boost::graph_traits< UndirectedGraph >::vertex_descriptor VertexType
Definition treeWidth.h:181
std::vector< boost::shared_ptr< TreeDecompositionGraph > > nice_tree_decomposition_graphs_
Definition treeWidth.h:173
std::set< OriginalVertexType > TreeDecompositionContent
Definition treeWidth.h:99
boost::iterator_property_map< typename std::vector< TreeDecompositionBag >::iterator, typename boost::property_map< TreeDecompositionGraph, boost::vertex_index_t >::type > TreeDecompositionParentMap
Definition treeWidth.h:111
TreeWidth(UndirectedGraph const &input)
boost::graph_traits< TreeDecompositionGraph >::vertex_descriptor TreeDecompositionBag
Definition treeWidth.h:107
GRAPH::GraphTraits< UndirectedGraph >::EditableGraph EditableGraph
Definition treeWidth.h:96
boost::graph_as_tree< TreeDecompositionGraph, TreeDecompositionParentMap > TreeDecomposition
Definition treeWidth.h:112
std::vector< boost::shared_ptr< TreeDecomposition > > nice_tree_decompositions_
Definition treeWidth.h:172
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
MolecularGraph const * input_
Definition treeWidth.h:168
std::vector< boost::shared_ptr< TreeDecomposition > > & getNiceTreeDecompositions()
Definition treeWidth.h:127
static Size computeTreeWidth(TreeDecomposition const &td)
void writeGraphvizFile(std::ostream &out, TreeDecomposition const &td)
boost::graph_traits< UndirectedGraph >::vertex_descriptor OriginalVertexType
Definition treeWidth.h:97
std::vector< boost::shared_ptr< EditableGraph > > components_
Definition treeWidth.h:170
std::vector< boost::shared_ptr< EditableGraph > > & getComponents()
Definition treeWidth.h:126
ComponentFilter_(ComponentMap cm, Position i)
Definition treeWidth.h:134
bool operator()(const Vertex &e) const
Definition treeWidth.h:140
TreeDecomposition const * td_
Definition treeWidth.h:163
BagContentWriter(TreeDecomposition const *td, UndirectedGraph const *original_graph)
Definition treeWidth.h:155
UndirectedGraph const * original_graph_
Definition treeWidth.h:164
void operator()(std::ostream &out, const TreeDecompositionBag &v) const
Generic lower bound algorithm on graphs.
Definition treeWidth.h:206
virtual Size operator()(UndirectedGraph const &originalGraph)
void contractEdge(VertexType &u, VertexType &v)
MinorMinWidthCriterion(UndirectedGraph const &graph)
EliminationOrder operator()(UndirectedGraph &original_graph)
VertexType & operator()(UndirectedGraph &graph)
Size edgeIncreaseByEliminating(VertexIterator vertex, UndirectedGraph &graph)
QuickBB(UndirectedGraph const &graph)
SIMPLICIAL_TYPE isSimplicial(VertexType &vertex) const
void branchAndBound(QuickBBState &nstate)
std::map< VertexType, bool > BitSet
Definition treeWidth.h:370
std::map< int, VertexType > index_to_vertex_
Definition treeWidth.h:433
std::pair< BitSet, Size > MapEntry
Definition treeWidth.h:373
std::map< BitSet, Size > GraphMap
Definition treeWidth.h:371
std::pair< typename GraphMap::iterator, bool > MapPos
Definition treeWidth.h:372
TreeWidth< OriginalGraphType >::OriginalVertexType OriginalVertexType
Definition treeWidth.h:455
TreeDecompositionBag buildLinkage_(TreeDecompositionBag node, TreeDecompositionBag child)
boost::shared_ptr< TreeDecompositionGraph > tree_graph_
Definition treeWidth.h:500
boost::shared_ptr< TreeDecomposition > tree_
Definition treeWidth.h:499
TreeWidth< OriginalGraphType >::TreeDecompositionBag TreeDecompositionBag
Definition treeWidth.h:452
TreeDecompositionBag buildJoin_(TreeDecompositionBag node, TreeDecompositionBag left, TreeDecompositionBag right, bool do_forget)
TreeDecompositionBag linkWithForgetNodes_(TreeDecompositionContent parent_set, TreeDecompositionBag child)
TreeDecompositionBag buildLeaf_(TreeDecompositionBag child)
boost::shared_ptr< TreeDecomposition > makeNice(boost::shared_ptr< TreeDecompositionGraph > &nice_tree)
boost::shared_ptr< TreeDecomposition > operator()(UndirectedGraph const &graph, EliminationOrder const &permutation)
TreeDecompositionBag linkWithIntroduceNodes_(TreeDecompositionContent parent_set, TreeDecompositionBag child)
std::set< OriginalVertexType > TreeDecompositionContent
Definition treeWidth.h:457
boost::shared_ptr< TreeDecompositionGraph > nice_tree_
Definition treeWidth.h:501
TreeWidth< OriginalGraphType >::TreeDecomposition TreeDecomposition
Definition treeWidth.h:451
TreeDecompositionBag branch_(TreeDecompositionBag node, int node_type, typename std::vector< TreeDecompositionBag >::iterator begin, typename std::vector< TreeDecompositionBag >::iterator end)
TreeWidth< OriginalGraphType >::TreeDecompositionGraph TreeDecompositionGraph
Definition treeWidth.h:453
TreeDecompositionBag buildRoot_(TreeDecompositionBag child)
TreeDecompositionBag buildSingle_(TreeDecompositionBag node, int node_type, TreeDecompositionBag child)