5 #ifndef BALL_DATATYPE_GRAPH_TREEWIDTH_H 6 #define BALL_DATATYPE_GRAPH_TREEWIDTH_H 8 #ifndef BALL_COMMON_GLOBAL_H 12 #ifndef BALL_COMMON_EXCEPTION_H 16 #ifndef BALL_CONCEPT_BASEFUNCTOR_H 20 #ifndef BALL_DATATYPE_GRAPH_GRAPHALGORITHMS_H 24 #ifndef BALL_DATATYPE_GRAPH_MOLECULARGRAPH_H 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> 58 template <
class UndirectedGraph>
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> > >,
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;
120 static Size computeTreeWidth(TreeDecomposition
const& td);
124 void writeGraphvizFile(std::ostream& out, TreeDecomposition
const& td);
126 std::vector<boost::shared_ptr<EditableGraph> >&
getComponents() {
return components_; }
130 template <
typename ComponentMap>
139 template <
typename Vertex>
142 return ((cm_)[e] == component_);
157 original_graph_(original_graph)
160 void operator() (std::ostream& out,
const TreeDecompositionBag& v)
const;
163 TreeDecomposition
const*
td_;
176 template <
class UndirectedGraph>
181 typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor
VertexType;
183 typedef typename boost::graph_traits<UndirectedGraph>::vertex_iterator
VertexIterator;
203 template<
class Criterion,
class Reducer>
210 virtual Size operator() (UndirectedGraph
const& originalGraph);
224 void operator() (VertexType& vertex);
225 void contractEdge(VertexType& u, VertexType& v);
239 Size operator() (VertexType& vertex)
const;
286 template<
class Criterion>
288 :
public UnaryFunctor<UndirectedGraph, typename std::pair<
289 std::vector<boost::graph_traits<typename UndirectedGraph::vertex_descriptor> >, Size> >
292 EliminationOrder operator() (UndirectedGraph& original_graph);
301 VertexType& operator() (UndirectedGraph& graph);
303 Size edgeIncreaseByEliminating(VertexIterator vertex, UndirectedGraph& graph);
315 template <
class Lowerbound=MinorMinW
idth,
class Upperbound=GreedyX<FillInHeuristic> >
334 QuickBB(UndirectedGraph
const& graph);
339 EliminationOrder compute();
370 typedef std::map<VertexType, bool>
BitSet;
372 typedef std::pair<typename GraphMap::iterator, bool>
MapPos;
430 BitSet buildBitset()
const;
447 template <
class OriginalGraphType>
465 boost::shared_ptr<TreeDecomposition> operator() (UndirectedGraph
const& graph, EliminationOrder
const& permutation);
476 boost::shared_ptr<TreeDecomposition> makeNice(boost::shared_ptr<TreeDecompositionGraph>& nice_tree);
478 TreeDecompositionBag operator() (TreeDecompositionBag n,
479 typename std::vector<TreeDecompositionBag>::iterator c_i,
typename std::vector<TreeDecompositionBag>::iterator c_end);
482 TreeDecompositionBag buildRoot_(TreeDecompositionBag child);
483 TreeDecompositionBag buildLeaf_(TreeDecompositionBag child);
484 TreeDecompositionBag buildJoin_(TreeDecompositionBag node, TreeDecompositionBag left,
485 TreeDecompositionBag right,
bool do_forget);
487 TreeDecompositionBag buildSingle_(TreeDecompositionBag node,
int node_type,
488 TreeDecompositionBag child);
490 TreeDecompositionBag buildLinkage_(TreeDecompositionBag node, TreeDecompositionBag child);
492 TreeDecompositionBag linkWithIntroduceNodes_(TreeDecompositionContent parent_set, TreeDecompositionBag child);
493 TreeDecompositionBag linkWithForgetNodes_ (TreeDecompositionContent parent_set, TreeDecompositionBag child);
495 TreeDecompositionBag branch_(TreeDecompositionBag node,
int node_type,
496 typename std::vector<TreeDecompositionBag>::iterator begin,
497 typename std::vector<TreeDecompositionBag>::iterator end);
499 boost::shared_ptr<TreeDecomposition>
tree_;
509 #include <BALL/DATATYPE/GRAPH/treeWidth.iC> 511 #endif // BALL_DATATYPE_GRAPH_TREEWIDTH_H std::pair< std::vector< Size >, Size > EliminationOrder
TreeWidth< OriginalGraphType >::OriginalVertexType OriginalVertexType
boost::graph_as_tree< TreeDecompositionGraph, TreeDecompositionParentMap > TreeDecomposition
TreeWidth< OriginalGraphType >::TreeDecompositionBag TreeDecompositionBag
GreedyX< FillInHeuristic > GreedyFillIn
GRAPH::GraphTraits< UndirectedGraph >::EditableGraph EditableGraph
std::vector< boost::shared_ptr< EditableGraph > > & getComponents()
EliminationOrder own_solution
std::vector< boost::shared_ptr< TreeDecompositionGraph > > nice_tree_decomposition_graphs_
std::pair< typename GraphMap::iterator, bool > MapPos
boost::graph_traits< UndirectedGraph >::adjacency_iterator NeighbourIterator
boost::graph_traits< UndirectedGraph >::vertex_iterator VertexIterator
std::vector< boost::shared_ptr< EditableGraph > > components_
boost::shared_ptr< TreeDecompositionGraph > tree_graph_
BOOST_INSTALL_PROPERTY(vertex, atom_ptr)
GraphMap visitedSubgraphs
boost::graph_traits< UndirectedGraph >::vertex_descriptor VertexType
BagContentWriter(TreeDecomposition const *td, UndirectedGraph const *original_graph)
std::map< BitSet, Size > GraphMap
boost::graph_traits< TreeDecompositionGraph >::vertex_descriptor TreeDecompositionBag
EliminationOrder greedy_solution
boost::graph_traits< UndirectedGraph >::vertex_descriptor OriginalVertexType
std::vector< boost::shared_ptr< TreeDecomposition > > & getNiceTreeDecompositions()
boost::shared_ptr< TreeDecompositionGraph > nice_tree_
UndirectedGraph const * original_graph_
std::vector< boost::shared_ptr< TreeDecomposition > > nice_tree_decompositions_
TreeDecompositionBag root_
GeneralLowerBoundAlgorithm< MinorMinWidthCriterion, MinorMinWidthReducer > MinorMinWidth
TreeDecomposition const * td_
ComponentFilter_(ComponentMap cm, Position i)
std::vector< Size > permutation
GeneralLowerBoundAlgorithm()
std::set< OriginalVertexType > TreeDecompositionContent
std::map< VertexType, bool > BitSet
MolecularGraph const * input_
Generic lower bound algorithm on graphs.
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
std::map< int, VertexType > index_to_vertex_
TreeWidth< OriginalGraphType >::TreeDecomposition TreeDecomposition
boost::iterator_property_map< typename std::vector< TreeDecompositionBag >::iterator, typename boost::property_map< TreeDecompositionGraph, boost::vertex_index_t >::type > TreeDecompositionParentMap
UndirectedGraph const & graph_
boost::shared_ptr< TreeDecomposition > tree_
TreeWidth< OriginalGraphType >::TreeDecompositionGraph 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
std::pair< BitSet, Size > MapEntry
std::set< OriginalVertexType > TreeDecompositionContent