SHOGUN
v3.2.0
|
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 }