IndexBlockTree.cpp

Go to the documentation of this file.
00001 /*
00002  * This program is free software; you can redistribute it and/or modify
00003  * it under the terms of the GNU General Public License as published by
00004  * the Free Software Foundation; either version 3 of the License, or
00005  * (at your option) any later version.
00006  *
00007  * Copyright (C) 2012 Sergey Lisitsyn
00008  */
00009 
00010 #include <shogun/lib/IndexBlockTree.h>
00011 #include <vector>
00012 
00013 using namespace std;
00014 using namespace shogun;
00015 
00016 struct tree_node_t
00017 {
00018     tree_node_t** desc;
00019     int32_t n_desc;
00020     int32_t sub_nodes_count;
00021     int32_t idx;
00022 };
00023 
00024 struct block_tree_node_t
00025 {
00026     block_tree_node_t(int32_t min, int32_t max, float64_t w)
00027     {
00028         t_min_index = min;
00029         t_max_index = max;
00030         weight = w;
00031     }
00032     int32_t t_min_index, t_max_index;
00033     float64_t weight;
00034 };
00035 
00036 int count_sub_nodes_recursive(tree_node_t* node, int32_t self)
00037 {
00038     if (node->n_desc==0)
00039     {
00040         return 1;
00041     }
00042     else
00043     {
00044         int c = 0;
00045         for (int32_t i=0; i<node->n_desc; i++)
00046         {
00047             c += count_sub_nodes_recursive(node->desc[i], self);
00048         }
00049         if (self)
00050             node->sub_nodes_count = c;
00051         return c + self;
00052     }
00053 }
00054 
00055 void print_tree(tree_node_t* node, int tabs)
00056 {
00057     for (int32_t t=0; t<tabs; t++)
00058         SG_SPRINT("  ");
00059     SG_SPRINT("%d %d\n",node->idx, node->sub_nodes_count);
00060     for (int32_t i=0; i<node->n_desc; i++)
00061         print_tree(node->desc[i],tabs+1);
00062 }
00063 
00064 int32_t fill_G_recursive(tree_node_t* node, vector<int32_t>* G)
00065 {
00066     int32_t c=1;
00067     G->push_back(node->idx);
00068     for (int32_t i=0; i<node->n_desc; i++)
00069         c+= fill_G_recursive(node->desc[i], G);
00070     return c;
00071 }
00072 
00073 void fill_ind_recursive(tree_node_t* node, vector<block_tree_node_t>* tree_nodes, int32_t lower)
00074 {
00075     int32_t l = lower;
00076     for (int32_t i=0; i<node->n_desc; i++)
00077     {
00078         int32_t c = node->desc[i]->sub_nodes_count;
00079         if (c>0)
00080         {
00081             tree_nodes->push_back(block_tree_node_t(l,l+c-1,1.0));
00082             fill_ind_recursive(node->desc[i], tree_nodes, l);
00083             l+=c;
00084         }
00085         else
00086             l++;
00087     }
00088 }
00089 
00090 void collect_tree_nodes_recursive(CIndexBlock* subtree_root_block, vector<block_tree_node_t>* tree_nodes)
00091 {
00092     CList* sub_blocks = subtree_root_block->get_sub_blocks();
00093     if (sub_blocks->get_num_elements()>0)
00094     {
00095         CIndexBlock* iterator = (CIndexBlock*)sub_blocks->get_first_element();
00096         do
00097         {
00098             SG_SDEBUG("Block [%d %d] \n",iterator->get_min_index(), iterator->get_max_index());
00099             tree_nodes->push_back(block_tree_node_t(iterator->get_min_index(),iterator->get_max_index(),iterator->get_weight()));
00100             if (iterator->get_num_sub_blocks()>0)
00101                 collect_tree_nodes_recursive(iterator, tree_nodes);
00102             SG_UNREF(iterator);
00103         }
00104         while ((iterator = (CIndexBlock*)sub_blocks->get_next_element()) != NULL);
00105     }
00106     SG_UNREF(sub_blocks);
00107 }
00108 
00109 CIndexBlockTree::CIndexBlockTree() : 
00110     CIndexBlockRelation(), m_root_block(NULL),
00111     m_general(false)
00112 {
00113 
00114 }
00115 
00116 CIndexBlockTree::CIndexBlockTree(CIndexBlock* root_block) : CIndexBlockRelation(),
00117     m_root_block(NULL), m_general(false)
00118 {
00119     set_root_block(root_block);
00120 }
00121 
00122 CIndexBlockTree::CIndexBlockTree(SGMatrix<float64_t> adjacency_matrix, bool include_supernode) : 
00123     CIndexBlockRelation(),
00124     m_root_block(NULL), m_general(true)
00125 {
00126     ASSERT(adjacency_matrix.num_rows == adjacency_matrix.num_cols);
00127     int32_t n_features = adjacency_matrix.num_rows;
00128     
00129     // well ordering is assumed
00130     
00131     tree_node_t* nodes = SG_CALLOC(tree_node_t, n_features);
00132 
00133     int32_t* nz_row = SG_CALLOC(int32_t, n_features);
00134     for (int32_t i=0; i<n_features; i++)
00135     {
00136         nodes[i].idx = i;
00137         nodes[i].sub_nodes_count = 0;
00138         int32_t c = 0;
00139         for (int32_t j=i; j<n_features; j++)
00140         {
00141             if (adjacency_matrix(j,i)!=0.0)
00142                 nz_row[c++] = j;
00143         }
00144         nodes[i].n_desc = c;
00145         nodes[i].desc = SG_MALLOC(tree_node_t*, c);
00146         for (int32_t j=0; j<c; j++)
00147         {
00148             nodes[i].desc[j] = &nodes[nz_row[j]]; 
00149         }
00150         if (nz_row[c] == n_features)
00151             break;
00152     }
00153     SG_FREE(nz_row);
00154 
00155     vector<int32_t> G;
00156     vector<int32_t> ind_t;
00157     int current_l_idx = 1;
00158     for (int32_t i=1; i<n_features; i++)
00159     {
00160         if (nodes[i].n_desc > 0)
00161         {
00162             int sub_count = fill_G_recursive(&nodes[i],&G);
00163             ind_t.push_back(current_l_idx);
00164             ind_t.push_back(current_l_idx+sub_count-1);
00165             ind_t.push_back(1.0);
00166             current_l_idx += sub_count;
00167         }
00168     }
00169     /*
00170     SG_SPRINT("[");
00171     for (int32_t i=0; i<G.size(); i++)
00172         SG_SPRINT(" %d ",G[i]);
00173     SG_SPRINT("]\n");
00174     SG_SPRINT("[");
00175     for (int32_t i=0; i<ind_t.size(); i++)
00176         SG_SPRINT(" %d ",ind_t[i]);
00177     SG_SPRINT("]\n");
00178     */
00179 
00180     int32_t supernode_offset = include_supernode ? 3 : 0;
00181     m_precomputed_ind_t = SGVector<float64_t>((int32_t)ind_t.size()+supernode_offset);
00182     if (include_supernode)
00183     {
00184         m_precomputed_ind_t[0] = -1;
00185         m_precomputed_ind_t[1] = -1;
00186         m_precomputed_ind_t[2] = 1.0;
00187     }
00188     for (int32_t i=0; i<(int32_t)ind_t.size(); i++)
00189         m_precomputed_ind_t[i+supernode_offset] = ind_t[i];
00190     m_precomputed_G = SGVector<float64_t>((int32_t)G.size());
00191     for (int32_t i=0; i<(int32_t)G.size(); i++)
00192         m_precomputed_G[i] = G[i] + 1;
00193     m_general = true;
00194     /*
00195     count_sub_nodes_recursive(nodes,1);
00196     print_tree(nodes,0);
00197     int32_t n_leaves = count_sub_nodes_recursive(nodes,0);
00198     m_precomputed_ind_t = SGVector<float64_t>((n_features-n_leaves)*3);
00199     SG_PRINT("n_leaves = %d\n",n_leaves);
00200     vector<block_tree_node_t> blocks;
00201     fill_ind_recursive(nodes, &blocks, 1);
00202     m_precomputed_ind_t[0] = -1;
00203     m_precomputed_ind_t[1] = -1;
00204     m_precomputed_ind_t[2] = 1.0;
00205     
00206     for (int32_t i=0; i<(int)blocks.size(); i++)
00207     {
00208         m_precomputed_ind_t[3+3*i+0] = blocks[i].t_min_index; 
00209         m_precomputed_ind_t[3+3*i+1] = blocks[i].t_max_index;
00210         m_precomputed_ind_t[3+3*i+2] = blocks[i].weight;
00211     }
00212     */
00213     for (int32_t i=0; i<n_features; i++)
00214         SG_FREE(nodes[i].desc);
00215     SG_FREE(nodes);
00216 }
00217 
00218 CIndexBlockTree::CIndexBlockTree(SGVector<float64_t> G, SGVector<float64_t> ind_t) : 
00219     CIndexBlockRelation(),
00220     m_root_block(NULL), m_general(true)
00221 {
00222     m_precomputed_G = G;
00223     m_precomputed_ind_t = ind_t;
00224 }
00225 
00226 CIndexBlockTree::CIndexBlockTree(SGVector<float64_t> ind_t) :
00227     CIndexBlockRelation(),
00228     m_root_block(NULL), m_general(false)
00229 {
00230     m_precomputed_ind_t = ind_t;
00231 }
00232 
00233 CIndexBlockTree::~CIndexBlockTree()
00234 {
00235     SG_UNREF(m_root_block);
00236 }
00237 
00238 CIndexBlock* CIndexBlockTree::get_root_block() const
00239 {
00240     SG_REF(m_root_block);
00241     return m_root_block;
00242 }
00243 
00244 void CIndexBlockTree::set_root_block(CIndexBlock* root_block)
00245 {
00246     SG_REF(root_block);
00247     SG_UNREF(m_root_block);
00248     m_root_block = root_block;
00249 }
00250 
00251 SGVector<index_t> CIndexBlockTree::get_SLEP_ind()
00252 {
00253     SG_SNOTIMPLEMENTED;
00254     return SGVector<index_t>();
00255 }
00256 
00257 SGVector<float64_t> CIndexBlockTree::get_SLEP_G()
00258 {
00259     return m_precomputed_G;
00260 }
00261 
00262 bool CIndexBlockTree::is_general() const
00263 {
00264     return m_general;
00265 }
00266 
00267 SGVector<float64_t> CIndexBlockTree::get_SLEP_ind_t() const
00268 {
00269     if (m_precomputed_ind_t.vlen)
00270         return m_precomputed_ind_t;
00271 
00272     else
00273     {
00274         ASSERT(m_root_block);
00275         CList* blocks = new CList(true);
00276 
00277         vector<block_tree_node_t> tree_nodes = vector<block_tree_node_t>();
00278         
00279         collect_tree_nodes_recursive(m_root_block, &tree_nodes);
00280 
00281         SGVector<float64_t> ind_t(3+3*tree_nodes.size());
00282         // supernode
00283         ind_t[0] = -1;
00284         ind_t[1] = -1;
00285         ind_t[2] = 1.0;
00286 
00287         for (int32_t i=0; i<(int32_t)tree_nodes.size(); i++)
00288         {
00289             ind_t[3+i*3] = tree_nodes[i].t_min_index + 1;
00290             ind_t[3+i*3+1] = tree_nodes[i].t_max_index;
00291             ind_t[3+i*3+2] = tree_nodes[i].weight;
00292         }
00293 
00294         SG_UNREF(blocks);
00295 
00296         return ind_t;
00297     }
00298 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation