TreeStats.hpp

Go to the documentation of this file.

/**\file TreeStats.hpp
 * \class moab::TreeStats
 * \brief Traversal statistics accumulating and reporting
 *
 * Class to accumulate statistics on traversal performance. This structure contains the
 * count of nodes visited at each level in a tree, and the count of traversals that ended
 * at each level. One TrvStats structure can be used with multiple trees or multiple
 * queries, or used on only a single tree or a single query.
 *
 * Note that these traversal statistics are not related to the stats() query below,
 * which calculates static information about a tree. These statistics relate
 * to a tree's dynamic behavior on particular operations.
 */
 
#ifndef TREESTATS_HPP
#define TREESTATS_HPP
 
#include "moab/Interface.hpp"
 
#include <vector>
#include <iostream>
#include <string>
 
namespace moab
{
class TreeStats
{
 public:
 //! constructor
 TreeStats()
 {
 reset();
 }
 
 /** \brief Given a root node, compute the stats for a tree
 * \param impl MOAB instance pointer
 * \param root_node Root entity set for the tree
 */
 ErrorCode compute_stats( Interface* impl, EntityHandle root_node );
 
 //! reset traversal counters
 void reset_trav_stats();
 
 //! reset all counters
 void reset();
 
 //! print the contents of this structure
 void print() const;
 
 //! output all the contents of this structure on a single line
 void output_all_stats( const bool with_endl = true ) const;
 
 //! output just the traversal stats of this structure on a single line
 void output_trav_stats( const bool with_endl = true ) const;
 
 // times
 double initTime;
 
 // tree stats that depend only on structure (not traversal)
 unsigned int maxDepth;
 unsigned int numNodes;
 unsigned int numLeaves;
 double avgObjPerLeaf;
 unsigned int minObjPerLeaf;
 unsigned int maxObjPerLeaf;
 
 // traversal statistics
 unsigned int nodesVisited; // number of tree nodes visited since last reset
 unsigned int leavesVisited; // number of tree leaves visited since last reset
 unsigned int numTraversals; // number of tree traversals since last reset
 unsigned int constructLeafObjectTests; // during construction, number of tests of objects (e.g.
 // elements)
 unsigned int traversalLeafObjectTests; // during traversals, number of tests of objects (e.g. elements)
 unsigned int boxElemTests; // during construction, number of calls to
 // GeomUtil::box_elem_overlap (KD tree only)
 
 private:
 ErrorCode traverse( Interface* impl, EntityHandle node, unsigned int& depth );
};
 
inline ErrorCode TreeStats::compute_stats( Interface* impl, EntityHandle root_node )
{
 maxDepth = 0;
 numNodes = 0;
 numLeaves = 0;
 avgObjPerLeaf = 0.0;
 minObjPerLeaf = 0;
 maxObjPerLeaf = 0;
 
 ErrorCode rval = traverse( impl, root_node, maxDepth );
 avgObjPerLeaf = ( avgObjPerLeaf > 0 ? avgObjPerLeaf / (double)numLeaves : 0.0 );
 return rval;
}
 
inline ErrorCode TreeStats::traverse( Interface* impl, EntityHandle node, unsigned int& depth )
{
 depth++;
 numNodes++;
 std::vector< EntityHandle > children;
 children.reserve( 2 );
 ErrorCode rval = impl->get_child_meshsets( node, children );
 if( MB_SUCCESS != rval ) return rval;
 if( children.empty() )
 {
 numLeaves++;
 rval = impl->get_entities_by_handle( node, children );
 if( MB_SUCCESS != rval ) return rval;
 avgObjPerLeaf += children.size();
 minObjPerLeaf = std::min( (unsigned int)children.size(), minObjPerLeaf );
 maxObjPerLeaf = std::max( (unsigned int)children.size(), maxObjPerLeaf );
 return MB_SUCCESS;
 }
 else
 {
 unsigned int right_depth = depth, left_depth = depth;
 rval = traverse( impl, children[0], left_depth );
 if( MB_SUCCESS != rval ) return rval;
 rval = traverse( impl, children[1], right_depth );
 if( MB_SUCCESS != rval ) return rval;
 depth = std::max( left_depth, right_depth );
 return MB_SUCCESS;
 }
}
 
inline void TreeStats::reset()
{
 initTime = 0.0;
 
 maxDepth = 0;
 numNodes = 0;
 numLeaves = 0;
 constructLeafObjectTests = 0;
 boxElemTests = 0;
 avgObjPerLeaf = 0.0;
 minObjPerLeaf = 0.0;
 maxObjPerLeaf = 0.0;
 
 reset_trav_stats();
}
 
inline void TreeStats::reset_trav_stats()
{
 nodesVisited = 0;
 leavesVisited = 0;
 numTraversals = 0;
 traversalLeafObjectTests = 0;
}
 
inline void TreeStats::print() const
{
 std::cout << "Tree initialization time = " << initTime << " seconds" << std::endl;
 
 std::cout << "Num nodes = " << numNodes << std::endl;
 std::cout << "Num leaves = " << numLeaves << std::endl;
 std::cout << "Max depth = " << maxDepth << std::endl << std::endl;
 
 std::cout << "Avg objs per leaf = " << avgObjPerLeaf << std::endl;
 std::cout << "Min objs per leaf = " << minObjPerLeaf << std::endl;
 std::cout << "Max objs per leaf = " << maxObjPerLeaf << std::endl;
 
 std::cout << "Construction Leaf Object Tests = " << constructLeafObjectTests << std::endl;
 std::cout << "Box-Element Tests = " << boxElemTests << std::endl;
 
 std::cout << "NodesVisited = " << nodesVisited << std::endl;
 std::cout << "LeavesVisited = " << leavesVisited << std::endl;
 std::cout << "Num Traversals = " << numTraversals << std::endl;
 std::cout << "Traversal Leaf Object Tests = " << traversalLeafObjectTests << std::endl;
}
 
inline void TreeStats::output_all_stats( const bool with_endl ) const
{
 std::cout << initTime << " " << numNodes << " " << numLeaves << " " << maxDepth << " " << avgObjPerLeaf << " "
 << minObjPerLeaf << " " << maxObjPerLeaf << " " << constructLeafObjectTests << " " << boxElemTests << " "
 << nodesVisited << " " << leavesVisited << " " << numTraversals << " " << traversalLeafObjectTests << " ";
 if( with_endl ) std::cout << std::endl;
}
 
inline void TreeStats::output_trav_stats( const bool with_endl ) const
{
 std::cout << nodesVisited << " " << leavesVisited << " " << numTraversals << " " << traversalLeafObjectTests << " ";
 if( with_endl ) std::cout << std::endl;
}
} // namespace moab
 
#endif