Loading...
Searching...
No Matches
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
exception.h
global.h
baseFunctor.h
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::MolecularGraph
Definition molecularGraph.h:48
BALL::TreeWidthImplementation::GeneralLowerBoundAlgorithm
Generic lower bound algorithm on graphs.
Definition treeWidth.h:206
BALL::TreeWidthImplementation::GeneralLowerBoundAlgorithm::operator()
virtual Size operator()(UndirectedGraph const &originalGraph)
BALL::TreeWidthImplementation::GeneralLowerBoundAlgorithm::GeneralLowerBoundAlgorithm
GeneralLowerBoundAlgorithm()
Definition treeWidth.h:208
BALL::TreeWidthImplementation::GreedyX
Definition treeWidth.h:290
BALL::TreeWidthImplementation::GreedyX::operator()
EliminationOrder operator()(UndirectedGraph &original_graph)
BALL::TreeWidthImplementation::MinorMinWidthCriterion::graph_
UndirectedGraph const & graph_
Definition treeWidth.h:242
BALL::TreeWidthImplementation::MinorMinWidthCriterion::operator()
Size operator()(VertexType &vertex) const
BALL::TreeWidthImplementation::MinorMinWidthCriterion::MinorMinWidthCriterion
MinorMinWidthCriterion(UndirectedGraph const &graph)
BALL::TreeWidthImplementation::MinorMinWidthReducer::graph_
UndirectedGraph & graph_
Definition treeWidth.h:228
BALL::TreeWidthImplementation::MinorMinWidthReducer::MinorMinWidthReducer
MinorMinWidthReducer(UndirectedGraph &graph)
BALL::TreeWidthImplementation::MinorMinWidthReducer::contractEdge
void contractEdge(VertexType &u, VertexType &v)
BALL::TreeWidthImplementation::MinorMinWidthReducer::operator()
void operator()(VertexType &vertex)
BALL::TreeWidthImplementation::QuickBB::prune
void prune(QuickBBState &)
BALL::TreeWidthImplementation::QuickBB::QuickBB
QuickBB(UndirectedGraph const &graph)
BALL::TreeWidthImplementation::QuickBB::isSimplicial
SIMPLICIAL_TYPE isSimplicial(VertexType &vertex) const
BALL::TreeWidthImplementation::QuickBB::branchAndBound
void branchAndBound(QuickBBState &nstate)
BALL::TreeWidthImplementation::QuickBB::compute
EliminationOrder compute()
BALL::TreeWidthImplementation::QuickBB::BitSet
std::map< VertexType, bool > BitSet
Definition treeWidth.h:370
BALL::TreeWidthImplementation::QuickBB::greedy_solution
EliminationOrder greedy_solution
Definition treeWidth.h:388
BALL::TreeWidthImplementation::QuickBB::graph_
UndirectedGraph graph_
Definition treeWidth.h:378
BALL::TreeWidthImplementation::QuickBB::visitedSubgraphs
GraphMap visitedSubgraphs
Definition treeWidth.h:399
BALL::TreeWidthImplementation::QuickBB::own_solution
EliminationOrder own_solution
Definition treeWidth.h:393
BALL::TreeWidthImplementation::QuickBB::index_to_vertex_
std::map< int, VertexType > index_to_vertex_
Definition treeWidth.h:433
BALL::TreeWidthImplementation::QuickBB::buildBitset
BitSet buildBitset() const
BALL::TreeWidthImplementation::QuickBB::upper_bound
Size upper_bound
Definition treeWidth.h:406
BALL::TreeWidthImplementation::QuickBB::MapEntry
std::pair< BitSet, Size > MapEntry
Definition treeWidth.h:373
BALL::TreeWidthImplementation::QuickBB::GraphMap
std::map< BitSet, Size > GraphMap
Definition treeWidth.h:371
BALL::TreeWidthImplementation::QuickBB::state
QuickBBState state
Definition treeWidth.h:383
BALL::TreeWidthImplementation::QuickBB::MapPos
std::pair< typename GraphMap::iterator, bool > MapPos
Definition treeWidth.h:372
BALL::TreeWidthImplementation::QuickBB::SIMPLICIAL_TYPE
SIMPLICIAL_TYPE
Definition treeWidth.h:325
BALL::TreeWidthImplementation::QuickBB::IS_SIMPLICIAL
@ IS_SIMPLICIAL
Definition treeWidth.h:328
BALL::TreeWidthImplementation::QuickBB::NOT_SIMPLICIAL
@ NOT_SIMPLICIAL
Definition treeWidth.h:326
BALL::TreeWidthImplementation::QuickBB::ALMOST_SIMPLICIAL
@ ALMOST_SIMPLICIAL
Definition treeWidth.h:327
BALL::TreeWidthImplementation::TreeDecompositionBuilder
Definition treeWidth.h:449
BALL::TreeWidthImplementation::TreeDecompositionBuilder::root_
TreeDecompositionBag root_
Definition treeWidth.h:503
BALL::TreeWidthImplementation::TreeDecompositionBuilder::OriginalVertexType
TreeWidth< OriginalGraphType >::OriginalVertexType OriginalVertexType
Definition treeWidth.h:455
BALL::TreeWidthImplementation::TreeDecompositionBuilder::buildLinkage_
TreeDecompositionBag buildLinkage_(TreeDecompositionBag node, TreeDecompositionBag child)
BALL::TreeWidthImplementation::TreeDecompositionBuilder::tree_graph_
boost::shared_ptr< TreeDecompositionGraph > tree_graph_
Definition treeWidth.h:500
BALL::TreeWidthImplementation::TreeDecompositionBuilder::tree_
boost::shared_ptr< TreeDecomposition > tree_
Definition treeWidth.h:499
BALL::TreeWidthImplementation::TreeDecompositionBuilder::TreeDecompositionBag
TreeWidth< OriginalGraphType >::TreeDecompositionBag TreeDecompositionBag
Definition treeWidth.h:452
BALL::TreeWidthImplementation::TreeDecompositionBuilder::buildJoin_
TreeDecompositionBag buildJoin_(TreeDecompositionBag node, TreeDecompositionBag left, TreeDecompositionBag right, bool do_forget)
BALL::TreeWidthImplementation::TreeDecompositionBuilder::linkWithForgetNodes_
TreeDecompositionBag linkWithForgetNodes_(TreeDecompositionContent parent_set, TreeDecompositionBag child)
BALL::TreeWidthImplementation::TreeDecompositionBuilder::buildLeaf_
TreeDecompositionBag buildLeaf_(TreeDecompositionBag child)
BALL::TreeWidthImplementation::TreeDecompositionBuilder::makeNice
boost::shared_ptr< TreeDecomposition > makeNice(boost::shared_ptr< TreeDecompositionGraph > &nice_tree)
BALL::TreeWidthImplementation::TreeDecompositionBuilder::operator()
boost::shared_ptr< TreeDecomposition > operator()(UndirectedGraph const &graph, EliminationOrder const &permutation)
BALL::TreeWidthImplementation::TreeDecompositionBuilder::linkWithIntroduceNodes_
TreeDecompositionBag linkWithIntroduceNodes_(TreeDecompositionContent parent_set, TreeDecompositionBag child)
BALL::TreeWidthImplementation::TreeDecompositionBuilder::TreeDecompositionContent
std::set< OriginalVertexType > TreeDecompositionContent
Definition treeWidth.h:457
BALL::TreeWidthImplementation::TreeDecompositionBuilder::nice_tree_
boost::shared_ptr< TreeDecompositionGraph > nice_tree_
Definition treeWidth.h:501
BALL::TreeWidthImplementation::TreeDecompositionBuilder::TreeDecomposition
TreeWidth< OriginalGraphType >::TreeDecomposition TreeDecomposition
Definition treeWidth.h:451
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::TreeDecompositionBuilder::TreeDecompositionGraph
TreeWidth< OriginalGraphType >::TreeDecompositionGraph TreeDecompositionGraph
Definition treeWidth.h:453
BALL::TreeWidthImplementation::TreeDecompositionBuilder::buildRoot_
TreeDecompositionBag buildRoot_(TreeDecompositionBag child)
BALL::TreeWidthImplementation::TreeDecompositionBuilder::buildSingle_
TreeDecompositionBag buildSingle_(TreeDecompositionBag node, int node_type, TreeDecompositionBag child)
BALL::TreeWidthImplementation
Definition treeWidth.h:178
BALL::TreeWidthImplementation::MinorMinWidth
GeneralLowerBoundAlgorithm< MinorMinWidthCriterion, MinorMinWidthReducer > MinorMinWidth
Definition treeWidth.h:268
BALL::TreeWidthImplementation::NeighbourIterator
boost::graph_traits< UndirectedGraph >::adjacency_iterator NeighbourIterator
Definition treeWidth.h:182
BALL::TreeWidthImplementation::EliminationOrder
std::pair< std::vector< Size >, Size > EliminationOrder
Definition treeWidth.h:191
BALL::TreeWidthImplementation::GreedyFillIn
GreedyX< FillInHeuristic > GreedyFillIn
Definition treeWidth.h:445
BALL::TreeWidthImplementation::VertexIterator
boost::graph_traits< UndirectedGraph >::vertex_iterator VertexIterator
Definition treeWidth.h:183
BALL::TreeWidthImplementation::VertexType
boost::graph_traits< UndirectedGraph >::vertex_descriptor VertexType
Definition treeWidth.h:181
BALL::TreeWidth::BagContentWriter::td_
TreeDecomposition const * td_
Definition treeWidth.h:163
BALL::TreeWidth::BagContentWriter::BagContentWriter
BagContentWriter(TreeDecomposition const *td, UndirectedGraph const *original_graph)
Definition treeWidth.h:155
BALL::TreeWidth::BagContentWriter::original_graph_
UndirectedGraph const * original_graph_
Definition treeWidth.h:164
BALL::TreeWidth::BagContentWriter::operator()
void operator()(std::ostream &out, const TreeDecompositionBag &v) const
BALL::TreeWidth::ComponentFilter_::component_
Position component_
Definition treeWidth.h:147
BALL::TreeWidth::ComponentFilter_::cm_
ComponentMap cm_
Definition treeWidth.h:146
BALL::TreeWidth::ComponentFilter_::ComponentFilter_
ComponentFilter_(ComponentMap cm, Position i)
Definition treeWidth.h:134
BALL::TreeWidth::ComponentFilter_::operator()
bool operator()(const Vertex &e) const
Definition treeWidth.h:140
BALL::TreeDecomposition::nice_tree_decomposition_graphs_
std::vector< boost::shared_ptr< TreeDecompositionGraph > > nice_tree_decomposition_graphs_
Definition treeWidth.h:173
BALL::TreeWidth::TreeDecompositionContent
std::set< OriginalVertexType > TreeDecompositionContent
Definition treeWidth.h:99
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::TreeWidth::TreeWidth
TreeWidth(UndirectedGraph const &input)
BALL::TreeWidth::TreeDecompositionBag
boost::graph_traits< TreeDecompositionGraph >::vertex_descriptor TreeDecompositionBag
Definition treeWidth.h:107
BALL::TreeWidth::EditableGraph
GRAPH::GraphTraits< UndirectedGraph >::EditableGraph EditableGraph
Definition treeWidth.h:96
BALL::TreeWidth::TreeDecomposition
boost::graph_as_tree< TreeDecompositionGraph, TreeDecompositionParentMap > TreeDecomposition
Definition treeWidth.h:112
BALL::TreeDecomposition::nice_tree_decompositions_
std::vector< boost::shared_ptr< TreeDecomposition > > nice_tree_decompositions_
Definition treeWidth.h:172
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::TreeDecomposition::input_
MolecularGraph const * input_
Definition treeWidth.h:168
BALL::TreeWidth::BagType
BagType
Definition treeWidth.h:65
BALL::TreeDecomposition::JOIN_BAG
@ JOIN_BAG
Definition treeWidth.h:85
BALL::TreeDecomposition::END_BAG
@ END_BAG
Definition treeWidth.h:93
BALL::TreeDecomposition::INNER_BAG
@ INNER_BAG
Definition treeWidth.h:89
BALL::TreeDecomposition::ROOT_BAG
@ ROOT_BAG
Definition treeWidth.h:81
BALL::TreeDecomposition::FORGET_BAG
@ FORGET_BAG
Definition treeWidth.h:77
BALL::TreeDecomposition::INTRODUCE_BAG
@ INTRODUCE_BAG
Definition treeWidth.h:69
BALL::TreeDecomposition::LEAF_BAG
@ LEAF_BAG
Definition treeWidth.h:73
BALL::TreeWidth::getNiceTreeDecompositions
std::vector< boost::shared_ptr< TreeDecomposition > > & getNiceTreeDecompositions()
Definition treeWidth.h:127
BALL::TreeWidth::computeTreeWidth
static Size computeTreeWidth(TreeDecomposition const &td)
BALL::TreeWidth::writeGraphvizFile
void writeGraphvizFile(std::ostream &out, TreeDecomposition const &td)
BALL::TreeWidth::OriginalVertexType
boost::graph_traits< UndirectedGraph >::vertex_descriptor OriginalVertexType
Definition treeWidth.h:97
BALL::TreeDecomposition::components_
std::vector< boost::shared_ptr< EditableGraph > > components_
Definition treeWidth.h:170
BALL::TreeWidth::getComponents
std::vector< boost::shared_ptr< EditableGraph > > & getComponents()
Definition treeWidth.h:126
BALL::UnaryFunctor
Definition baseFunctor.h:26
graphAlgorithms.h
molecularGraph.h
BALL
Definition constants.h:13
BALL::Size
BALL_SIZE_TYPE Size
Definition COMMON/global.h:114
BALL::Position
BALL_SIZE_TYPE Position
Definition COMMON/global.h:140
boost
Definition graphAlgorithms.h:27
boost::vertex_bag_special_t
vertex_bag_special_t
Definition treeWidth.h:44
boost::vertex_bag_special
@ vertex_bag_special
Definition treeWidth.h:44
boost::vertex_bag_content_t
vertex_bag_content_t
Definition treeWidth.h:43
boost::vertex_bag_content
@ vertex_bag_content
Definition treeWidth.h:43
boost::vertex_bag_type_t
vertex_bag_type_t
Definition treeWidth.h:45
boost::vertex_bag_type
@ vertex_bag_type
Definition treeWidth.h:45
boost::BOOST_INSTALL_PROPERTY
BOOST_INSTALL_PROPERTY(vertex, atom_ptr)
BALL::TreeWidthImplementation::FillInHeuristic
Definition treeWidth.h:300
BALL::TreeWidthImplementation::FillInHeuristic::operator()
VertexType & operator()(UndirectedGraph &graph)
BALL::TreeWidthImplementation::FillInHeuristic::edgeIncreaseByEliminating
Size edgeIncreaseByEliminating(VertexIterator vertex, UndirectedGraph &graph)
BALL::TreeWidthImplementation::QuickBB::QuickBBState
Definition treeWidth.h:348
BALL::TreeWidthImplementation::QuickBB::QuickBBState::h
unsigned int h
Definition treeWidth.h:357
BALL::TreeWidthImplementation::QuickBB::QuickBBState::permutation
std::vector< Size > permutation
Definition treeWidth.h:367
BALL::TreeWidthImplementation::QuickBB::QuickBBState::g
unsigned int g
Definition treeWidth.h:352
BALL::TreeWidthImplementation::QuickBB::QuickBBState::f
unsigned int f
Definition treeWidth.h:362