- Main Page
- Namespaces
- Classes
- Files

# proto/Source/ntree.cpp

Go to the documentation of this file.

    00001
    00011 #include <algorithm>
    00012 #include <numeric>
    00013 #include <queue>
    00014 #include <vector>
    00015
    00016 // Self header.
    00017 #include "ntree.h"
    00018 // Sum decompositions.
    00019 #include "utils.h"
    00020
    00021 #ifdef _DEPENDENCY_MODE
    00022
    00023 namespace ace {
    00024
    00027 typedef std::vector<subtree_t> subtrees_container_t;
    00030 typedef std::vector<subtrees_container_t> subtrees_to_merge_t;
    00031
    00034 subtrees_to_merge_t::size_type _product(subtrees_to_merge_t::size_type product_so_far, const subtrees_container_t& subtrees) {
    00035     return product_so_far * subtrees.size();
    00036 }
    00037
    00043 void _join_subtrees(const subtrees_to_merge_t& subtrees_by_root_node, subtrees_container_t& results) {
    00044     if ( subtrees_by_root_node.empty() ) {
    00045         return;
    00046     }
    00047
    00048     // The number of results is product of multiplication of counts of various nodes subtrees.
    00049     size_t results_count = std::accumulate(subtrees_by_root_node.begin(), subtrees_by_root_node.end(), 1, _product);
    00050     results.reserve(results_count);
    00051
    00052     // Iterate through vectors of subtrees and create desired subtrees.
    00053     for ( size_t i = 0; i < subtrees_by_root_node.size(); ++i ) { // Loop through different nodes.
    00054         for ( size_t j = 0; j < subtrees_by_root_node[i].size(); ++j ) { // Loop through subtrees of given node.
    00055             // Loop as many times as needed. The more subtrees of given node,
    00056             // the less loops performed (every subtree will be combined with the same number
    00057             // of subtrees of different nodes.
    00058             size_t loop = results_count/subtrees_by_root_node[i].size();
    00059             for ( size_t k = 0; k < loop; ++k ) {
    00060                 if ( i == 0 ) {
    00061                     // First outer loop, init resulting subtree with copy of j-th subtree of first node.
    00062                     results.push_back(subtrees_by_root_node[i][j]);
    00063                 } else {
    00064                     // Not first outer loop (subtree of later than first node), insert into existing subtree.
    00065                     results[j*loop + k].insert(results[j*loop + k].end(), subtrees_by_root_node[i][j].begin(), subtrees_by_root_node[i][j].end());
    00066                 }
    00067             }
    00068         }
    00069     }
    00070 }
    00071
    00072
    00073 /*  Interface item implementation - for info see description in header file.
    00074  */
    00075 void extract_subtrees(ntree_t& nodes, tree_size_t subtree_size, mapped_subtrees_t& results) {
    00076
    00077     if ( nodes.size() <= subtree_size ) {
    00078         // Number of nodes is lesser than required subtree size.
    00079         // Note: `nodes` container have one item more than is the nodes count.
    00080         return;
    00081     }
    00082
    00083     // Utility object which precounts decomposition of all `sums` from 1 up to N
    00084     // with use of M addends.
    00085     // We used this decompositions to iterate through all posibilities how to construct
    00086     // subtree of size N as composition of M smaller subtrees.
    00087     // We are interested only in subtrees of maximum size `subtree_size`, so we only
    00088     // want to get `subtree_size`-1 subtree nodes from childs of certain node.
    00089     static SumDecompositions sum_decompositions(subtree_size-1, subtree_size*2);
    00090
    00091     // Process queue - every node has to be processed once. The queue is initialized
    00092     // with leaf nodes and order of processing of the rest of nodes is determined by
    00093     // tree structure.
    00094     std::queue<tree_size_t> process_queue;
    00095
    00099     std::vector<mapped_subtrees_t> subtrees(nodes.size());
    00103     std::vector<tree_size_t> childs_processed(nodes.size());
    00104
    00105     // Step 0: Init the process queue with leaf nodes.
    00106     // The 0-th node (abstract root) can be safely ignored.
    00107     for ( tree_size_t i = 1; i < nodes.size(); ++i ) {
    00108         if ( nodes[i].is_leaf() ) {
    00109             // Add node to the process queue.
    00110             process_queue.push(nodes[i].index());
    00111         }
    00112     }
    00113
    00114     // Step 1: Cycle processing the queue.
    00115     while ( !process_queue.empty() ) {
    00116         // Current node.
    00117         NTreeNode& current = nodes[process_queue.front()];
    00118         // Parent node.
    00119         NTreeNode& parent = nodes[current.parent()];
    00120
    00121         // Every node is at least root of subtree of size one (containing only
    00122         // the node itself), so...
    00123         subtree_t new_one; // Create.
    00124         new_one.push_back(current.index()); // Fill with current.
    00125         // Subtrees are indexed by root nodes indices and the size of subtree is the map key.
    00126         subtrees[current.index()].insert(mapped_subtrees_t::value_type(new_one.size(), new_one)); // Store.
    00127
    00128         // Leaf or not leaf?:)
    00129         if ( !current.is_leaf() ) {
    00130             // Current node has some childs, process them (find all subtrees).
    00131
    00132             // Few temporary containers...
    00133             // There will be at most `subtree_size` subtrees_to_merge.
    00134             subtrees_to_merge_t subtrees_to_merge;
    00135             subtrees_to_merge.reserve(subtree_size);
    00136             // Prepare container for results.
    00137             subtrees_container_t merge_results;
    00138             //
    00139             subtrees_container_t node_subtrees;
    00140
    00141             for ( tree_size_t n = 2; n <= subtree_size; ++n ) {
    00142                 // Sum to get from childs.
    00143                 tree_size_t sum = n - 1;
    00144
    00145                 // Get decompositions of `sum` into `count_childs` addends
    00146                 const sum_decompositions_t *sd = sum_decompositions.get_decompositions_table(sum, current.count_childs());
    00147
    00148                 // Process them.
    00149                 for ( size_t i = 0; i < sd->size(); ++i ) { // Loop through every decomposition.
    00150                     size_t j = 0;
    00151                     for ( childs_t::const_iterator i_child = current.get_childs().begin(); i_child != current.get_childs().end(); ++i_child, ++j) { // Loop through every child node.
    00152                         if ( (*sd)[i][j] == 0 ) {
    00153                             // There is no such thing like subtree with zero nodes, so go to next.
    00154                             continue;
    00155                         }
    00156                         // Get all of subtrees of required size.
    00157                         std::pair<mapped_subtrees_t::const_iterator, mapped_subtrees_t::const_iterator> range = subtrees[*i_child].equal_range((*sd)[i][j]);
    00158                         // Copy them into `node_subtrees`.
    00159                         std::transform(range.first, range.second, std::back_inserter(node_subtrees), select2nd<mapped_subtrees_t::value_type>());
    00160                         //
    00161                         subtrees_to_merge.push_back(node_subtrees);
    00162                         // Clear for use in next loop.
    00163                         node_subtrees.clear();
    00164                     }
    00165                     // Join subtrees.
    00166                     _join_subtrees(subtrees_to_merge, merge_results);
    00167                     // Clear for use in next loop.
    00168                     subtrees_to_merge.clear();
    00169                     // Store the results as subtrees of current node,
    00170                     // don't forget to insert current node as well!
    00171                     // Also check, if there are any subtrees of size N!
    00172                     // If so, store them in results.
    00173                     for ( size_t n = 0; n < merge_results.size(); ++n ) {
    00174                         // Insert current node as well!
    00175                         merge_results[n].push_back(current.index());
    00176                         subtrees[current.index()].insert(mapped_subtrees_t::value_type(merge_results[n].size(), merge_results[n]));
    00177                         // Any subtree of desired size?
    00178                         if ( merge_results[n].size() == subtree_size ) {
    00179                             // Sort the subtree before copying it to results container!
    00180                             std::sort(merge_results[n].begin(), merge_results[n].end());
    00181                             results.insert(mapped_subtrees_t::value_type(current.index(), merge_results[n]));
    00182                         }
    00183                     }
    00184                     // Clear results for use in next loop.
    00185                     merge_results.clear();
    00186                 }
    00187             }
    00188         }
    00189
    00190         // Node has been processed, so:
    00191         // 1. Pop him from the queue.
    00192         process_queue.pop();
    00193         // 2. Increment processed childs counter of parent node.
    00194         ++(childs_processed[parent.index()]);
    00195
    00196         if ( !parent.is_abstract() && (parent.count_childs() == childs_processed[parent.index()]) ) {
    00197             // Parent node is not the abstract root node and all its childs have been already processed.
    00198             process_queue.push(parent.index());
    00199         }
    00200
    00201     }
    00202
    00203 }
    00204
    00205 } // namespace ace
    00206
    00207 #endif // _DEPENDENCY_MODE