Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
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
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
00171
00172
00173
00174
00175
00176
00177
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
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
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
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 }