28 std::cout << s <<
" (" << problemSize_ <<
")";
35 std::vector<size_t> nrFrontals;
36 nrFrontals.reserve(nrChildren());
37 for (
const sharedNode& child : children)
38 nrFrontals.push_back(child->nrFrontals());
46 orderedFrontalKeys.insert(orderedFrontalKeys.end(), cluster->orderedFrontalKeys.rbegin(),
47 cluster->orderedFrontalKeys.rend());
48 factors.push_back(cluster->factors);
49 children.insert(children.end(), cluster->children.begin(), cluster->children.end());
51 problemSize_ = std::max(problemSize_, cluster->problemSize_);
57 const std::vector<bool>& merge) {
58 gttic(Cluster_mergeChildren);
59 assert(merge.size() == this->children.size());
62 size_t nrKeys = orderedFrontalKeys.size();
63 size_t nrFactors = factors.size();
64 size_t nrNewChildren = 0;
67 for(
const sharedNode& child: this->children) {
69 nrKeys += child->orderedFrontalKeys.size();
70 nrFactors += child->factors.size();
71 nrNewChildren += child->nrChildren();
79 auto oldChildren = this->children;
80 this->children.clear();
81 this->children.reserve(nrNewChildren);
82 orderedFrontalKeys.reserve(nrKeys);
83 factors.reserve(nrFactors);
85 for (
const sharedNode& child : oldChildren) {
89 this->addChild(child);
93 std::reverse(orderedFrontalKeys.begin(), orderedFrontalKeys.end());
103template <
class GRAPH>
114template<
class CLUSTERTREE>
117 typedef typename CLUSTERTREE::sharedFactor sharedFactor;
118 typedef typename CLUSTERTREE::FactorType FactorType;
119 typedef typename CLUSTERTREE::FactorGraphType FactorGraphType;
120 typedef typename CLUSTERTREE::ConditionalType ConditionalType;
121 typedef typename CLUSTERTREE::BayesTreeType::Node BTNode;
124 size_t myIndexInParent;
126 boost::shared_ptr<BTNode> bayesTreeNode;
128 boost::shared_ptr<std::mutex> writeLock;
132 parentData(_parentData), bayesTreeNode(boost::make_shared<BTNode>())
134 , writeLock(boost::make_shared<std::mutex>())
139 parentData->writeLock->lock();
141 myIndexInParent = parentData->childFactors.size();
144 parentData->writeLock->unlock();
151 if (parentData->parentData)
152 bayesTreeNode->parent_ = parentData->bayesTreeNode;
153 parentData->bayesTreeNode->children.push_back(bayesTreeNode);
158 static EliminationData EliminationPreOrderVisitor(
159 const typename CLUSTERTREE::sharedNode& node,
160 EliminationData& parentData) {
162 EliminationData myData(&parentData, node->nrChildren());
163 myData.bayesTreeNode->problemSize_ = node->problemSize();
170 const typename CLUSTERTREE::Eliminate& eliminationFunction_;
171 typename CLUSTERTREE::BayesTreeType::Nodes& nodesIndex_;
175 EliminationPostOrderVisitor(
176 const typename CLUSTERTREE::Eliminate& eliminationFunction,
177 typename CLUSTERTREE::BayesTreeType::Nodes& nodesIndex) :
178 eliminationFunction_(eliminationFunction), nodesIndex_(nodesIndex) {
182 void operator()(
const typename CLUSTERTREE::sharedNode& node,
EliminationData& myData) {
186 FactorGraphType gatheredFactors;
187 gatheredFactors.reserve(node->factors.size() + node->nrChildren());
188 gatheredFactors += node->factors;
189 gatheredFactors += myData.childFactors;
193 for (
const sharedFactor& factor: node->factors) {
196 myData.bayesTreeNode->children.push_back(asSubtree->clique);
197 asSubtree->clique->parent_ = myData.bayesTreeNode;
202 auto eliminationResult = eliminationFunction_(gatheredFactors, node->orderedFrontalKeys);
207 myData.bayesTreeNode->setEliminationResult(eliminationResult);
212 for (
const Key& j: myData.bayesTreeNode->conditional()->frontals())
213 nodesIndex_.insert(std::make_pair(j, myData.bayesTreeNode));
216 if (!eliminationResult.second->empty()) {
218 myData.parentData->writeLock->lock();
220 myData.parentData->childFactors[myData.myIndexInParent] = eliminationResult.second;
222 myData.parentData->writeLock->unlock();
230template<
class BAYESTREE,
class GRAPH>
237 remainingFactors_ = other.remainingFactors_;
243template <
class BAYESTREE,
class GRAPH>
244std::pair<boost::shared_ptr<BAYESTREE>, boost::shared_ptr<GRAPH> >
246 gttic(ClusterTree_eliminate);
250 boost::shared_ptr<BayesTreeType> result = boost::make_shared<BayesTreeType>();
253 Data rootsContainer(0, this->nrRoots());
255 typename Data::EliminationPostOrderVisitor visitorPost(function, result->nodes_);
263 result->roots_.insert(result->roots_.end(), rootsContainer.bayesTreeNode->children.begin(),
264 rootsContainer.bayesTreeNode->children.end());
267 boost::shared_ptr<FactorGraphType> remaining = boost::make_shared<FactorGraphType>();
268 remaining->reserve(remainingFactors_.size() + rootsContainer.childFactors.size());
269 remaining->push_back(remainingFactors_.begin(), remainingFactors_.end());
270 for (
const sharedFactor& factor : rootsContainer.childFactors) {
272 remaining->push_back(factor);
276 return std::make_pair(result, remaining);
Collects factorgraph fragments defined on variable clusters, arranged in a tree.
Variable ordering for the elimination algorithm.
Bayes Tree is a tree of cliques of a Bayes Chain.
std::vector< T, typename internal::FastDefaultVectorAllocator< T >::type > FastVector
FastVector is a type alias to a std::vector with a custom memory allocator.
Definition FastVector.h:34
Global functions in a separate testing namespace.
Definition chartTesting.h:28
void PrintKeyVector(const KeyVector &keys, const string &s, const KeyFormatter &keyFormatter)
Utility function to print sets of keys with optional prefix.
Definition Key.cpp:77
std::function< std::string(Key)> KeyFormatter
Typedef for a function to format a key, i.e. to convert it to a string.
Definition Key.h:35
FastVector< boost::shared_ptr< typename FOREST::Node > > CloneForest(const FOREST &forest)
Clone a tree, copy-constructing new nodes (calling boost::make_shared) and setting up child pointers ...
Definition treeTraversal-inst.h:189
void PrintForest(const FOREST &forest, std::string str, const KeyFormatter &keyFormatter)
Print a tree, prefixing each line with str, and formatting keys using keyFormatter.
Definition treeTraversal-inst.h:219
void DepthFirstForestParallel(FOREST &forest, DATA &rootData, VISITOR_PRE &visitorPre, VISITOR_POST &visitorPost, int problemSizeThreshold=10)
Traverse a forest depth-first with pre-order and post-order visits.
Definition treeTraversal-inst.h:154
An object whose scope defines a block where TBB and OpenMP parallelism are mixed.
Definition types.h:192
A cluster-tree that eliminates to a Bayes tree.
Definition ClusterTree.h:184
This & operator=(const This &other)
Assignment operator - makes a deep copy of the tree structure, but only pointers to factors are copie...
Definition ClusterTree-inst.h:231
std::pair< boost::shared_ptr< BayesTreeType >, boost::shared_ptr< FactorGraphType > > eliminate(const Eliminate &function) const
Eliminate the factors to a Bayes tree and remaining factor graph.
Definition ClusterTree-inst.h:245
boost::shared_ptr< FactorType > sharedFactor
Shared pointer to a factor.
Definition ClusterTree.h:197
GRAPH::Eliminate Eliminate
Typedef for an eliminate subroutine.
Definition ClusterTree.h:195
Definition BayesTree.h:276
Definition ClusterTree-inst.h:115
Definition ClusterTree-inst.h:169
A cluster-tree is associated with a factor graph and is defined as in Koller-Friedman: each node k re...
Definition ClusterTree.h:25
This & operator=(const This &other)
Assignment operator - makes a deep copy of the tree structure, but only pointers to factors are copie...
Definition ClusterTree-inst.h:104
FastVector< sharedNode > roots_
concept check
Definition ClusterTree.h:116
void print(const std::string &s="", const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
Print the cluster tree.
Definition ClusterTree-inst.h:98
boost::shared_ptr< FactorType > sharedFactor
Shared pointer to a factor.
Definition ClusterTree.h:32
virtual void print(const std::string &s="", const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
print this node
Definition ClusterTree-inst.h:26
Keys orderedFrontalKeys
Frontal keys of this node.
Definition ClusterTree.h:41
void mergeChildren(const std::vector< bool > &merge)
Merge all children for which bit is set into this node.
Definition ClusterTree-inst.h:56
void merge(const boost::shared_ptr< Cluster > &cluster)
Merge in given cluster.
Definition ClusterTree-inst.h:44
std::vector< size_t > nrFrontalsOfChildren() const
Return a vector with nrFrontal keys for each child.
Definition ClusterTree-inst.h:34