25 #include <gtsam/config.h> 36 namespace treeTraversal {
41 template<
typename NODE,
typename DATA>
42 struct TraversalNode {
47 TraversalNode(
const std::shared_ptr<NODE>& _treeNode, DATA& _parentData) :
48 expanded(false), treeNode(_treeNode), parentData(_parentData) {
54 template<
typename NODE,
typename DATA>
55 void operator()(
const std::shared_ptr<NODE>& node,
const DATA&
data) {
75 template<
class FOREST,
typename DATA,
typename VISITOR_PRE,
76 typename VISITOR_POST>
78 VISITOR_POST& visitorPost) {
84 typedef TraversalNode<typename FOREST::Node, DATA> TraversalNode;
91 typename Stack::iterator insertLocation = stack.begin();
92 for(
const sharedNode& root: forest.roots())
93 stack.insert(insertLocation, TraversalNode(root, rootData));
97 while (!stack.empty()) {
99 TraversalNode& node = stack.front();
104 (void) visitorPost(node.treeNode, *node.dataPointer);
105 dataList.erase(node.dataPointer);
110 node.dataPointer = dataList.insert(dataList.end(),
111 visitorPre(node.treeNode, node.parentData));
112 typename Stack::iterator insertLocation = stack.begin();
113 for(
const sharedNode& child: node.treeNode->children)
114 stack.insert(insertLocation, TraversalNode(child, *node.dataPointer));
115 node.expanded =
true;
118 assert(dataList.empty());
132 template<
class FOREST,
typename DATA,
typename VISITOR_PRE>
152 template<
class FOREST,
typename DATA,
typename VISITOR_PRE,
153 typename VISITOR_POST>
155 VISITOR_PRE& visitorPre, VISITOR_POST& visitorPost,
156 int problemSizeThreshold = 10) {
161 internal::CreateRootTask<Node>(forest.roots(), rootData, visitorPre,
162 visitorPost, problemSizeThreshold);
171 template<
typename NODE>
172 std::shared_ptr<NODE> CloneForestVisitorPre(
173 const std::shared_ptr<NODE>& node,
174 const std::shared_ptr<NODE>& parentPointer) {
176 std::shared_ptr<NODE> clone = std::make_shared<NODE>(*node);
177 clone->children.clear();
178 parentPointer->children.push_back(clone);
188 template<
class FOREST>
190 const FOREST& forest) {
192 std::shared_ptr<Node> rootContainer = std::make_shared<Node>();
195 rootContainer->children.end());
201 struct PrintForestVisitorPre {
204 formatter(formatter) {
206 template<
typename NODE> std::string
operator()(
207 const std::shared_ptr<NODE>& node,
const std::string& parentString) {
209 node->print(parentString +
"-", formatter);
211 return parentString +
"| ";
218 template<
class FOREST>
221 PrintForestVisitorPre visitor(keyFormatter);
SymbolicEliminationTree::sharedNode sharedNode
A thin wrapper around std::list that uses boost's fast_pool_allocator.
std::vector< T, typename internal::FastDefaultVectorAllocator< T >::type > FastVector
Tools for gathering statistics about a forest to aid tuning parallel traversal.
const KeyFormatter & formatter
void DepthFirstForest(FOREST &forest, DATA &rootData, VISITOR_PRE &visitorPre, VISITOR_POST &visitorPost)
void DepthFirstForestParallel(FOREST &forest, DATA &rootData, VISITOR_PRE &visitorPre, VISITOR_POST &visitorPost, int problemSizeThreshold=10)
Matrix stack(size_t nrMatrices,...)
void PrintForest(const FOREST &forest, std::string str, const KeyFormatter &keyFormatter)
static sharedNode Node(Key key, const SymbolicFactorGraph &factors, const ChildNodes::Result &children)
std::function< std::string(Key)> KeyFormatter
Typedef for a function to format a key, i.e. to convert it to a string.
A thin wrapper around std::vector that uses a custom allocator.
FastVector< std::shared_ptr< typename FOREST::Node > > CloneForest(const FOREST &forest)
const std::shared_ptr< NODE > & treeNode
FastList< DATA >::iterator dataPointer
internal::enable_if< internal::valid_indexed_view_overload< RowIndices, ColIndices >::value &&internal::traits< typename EIGEN_INDEXED_VIEW_METHOD_TYPE< RowIndices, ColIndices >::type >::ReturnAsIndexedView, typename EIGEN_INDEXED_VIEW_METHOD_TYPE< RowIndices, ColIndices >::type >::type operator()(const RowIndices &rowIndices, const ColIndices &colIndices) EIGEN_INDEXED_VIEW_METHOD_CONST