SHOGUN  v2.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
IndexBlockTree.cpp
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Copyright (C) 2012 Sergey Lisitsyn
8  */
9 
11 #include <vector>
12 
13 using namespace std;
14 using namespace shogun;
15 
17 {
19  int32_t n_desc;
20  int32_t sub_nodes_count;
21  int32_t idx;
22 };
23 
25 {
26  block_tree_node_t(int32_t min, int32_t max, float64_t w)
27  {
28  t_min_index = min;
29  t_max_index = max;
30  weight = w;
31  }
32  int32_t t_min_index, t_max_index;
34 };
35 
37 {
38  if (node->n_desc==0)
39  {
40  return 1;
41  }
42  else
43  {
44  int c = 0;
45  for (int32_t i=0; i<node->n_desc; i++)
46  {
47  c += count_sub_nodes_recursive(node->desc[i], self);
48  }
49  if (self)
50  node->sub_nodes_count = c;
51  return c + self;
52  }
53 }
54 
55 void print_tree(tree_node_t* node, int tabs)
56 {
57  for (int32_t t=0; t<tabs; t++)
58  SG_SPRINT(" ");
59  SG_SPRINT("%d %d\n",node->idx, node->sub_nodes_count);
60  for (int32_t i=0; i<node->n_desc; i++)
61  print_tree(node->desc[i],tabs+1);
62 }
63 
64 int32_t fill_G_recursive(tree_node_t* node, vector<int32_t>* G)
65 {
66  int32_t c=1;
67  G->push_back(node->idx);
68  for (int32_t i=0; i<node->n_desc; i++)
69  c+= fill_G_recursive(node->desc[i], G);
70  return c;
71 }
72 
73 void fill_ind_recursive(tree_node_t* node, vector<block_tree_node_t>* tree_nodes, int32_t lower)
74 {
75  int32_t l = lower;
76  for (int32_t i=0; i<node->n_desc; i++)
77  {
78  int32_t c = node->desc[i]->sub_nodes_count;
79  if (c>0)
80  {
81  tree_nodes->push_back(block_tree_node_t(l,l+c-1,1.0));
82  fill_ind_recursive(node->desc[i], tree_nodes, l);
83  l+=c;
84  }
85  else
86  l++;
87  }
88 }
89 
90 void collect_tree_nodes_recursive(CIndexBlock* subtree_root_block, vector<block_tree_node_t>* tree_nodes)
91 {
92  CList* sub_blocks = subtree_root_block->get_sub_blocks();
93  if (sub_blocks->get_num_elements()>0)
94  {
95  CIndexBlock* iterator = (CIndexBlock*)sub_blocks->get_first_element();
96  do
97  {
98  SG_SDEBUG("Block [%d %d] \n",iterator->get_min_index(), iterator->get_max_index());
99  tree_nodes->push_back(block_tree_node_t(iterator->get_min_index(),iterator->get_max_index(),iterator->get_weight()));
100  if (iterator->get_num_sub_blocks()>0)
101  collect_tree_nodes_recursive(iterator, tree_nodes);
102  SG_UNREF(iterator);
103  }
104  while ((iterator = (CIndexBlock*)sub_blocks->get_next_element()) != NULL);
105  }
106  SG_UNREF(sub_blocks);
107 }
108 
109 CIndexBlockTree::CIndexBlockTree() :
110  CIndexBlockRelation(), m_root_block(NULL),
111  m_general(false)
112 {
113 
114 }
115 
117  m_root_block(NULL), m_general(false)
118 {
119  set_root_block(root_block);
120 }
121 
122 CIndexBlockTree::CIndexBlockTree(SGMatrix<float64_t> adjacency_matrix, bool include_supernode) :
124  m_root_block(NULL), m_general(true)
125 {
126  ASSERT(adjacency_matrix.num_rows == adjacency_matrix.num_cols);
127  int32_t n_features = adjacency_matrix.num_rows;
128 
129  // well ordering is assumed
130 
131  tree_node_t* nodes = SG_CALLOC(tree_node_t, n_features);
132 
133  int32_t* nz_row = SG_CALLOC(int32_t, n_features);
134  for (int32_t i=0; i<n_features; i++)
135  {
136  nodes[i].idx = i;
137  nodes[i].sub_nodes_count = 0;
138  int32_t c = 0;
139  for (int32_t j=i; j<n_features; j++)
140  {
141  if (adjacency_matrix(j,i)!=0.0)
142  nz_row[c++] = j;
143  }
144  nodes[i].n_desc = c;
145  nodes[i].desc = SG_MALLOC(tree_node_t*, c);
146  for (int32_t j=0; j<c; j++)
147  {
148  nodes[i].desc[j] = &nodes[nz_row[j]];
149  }
150  if (nz_row[c] == n_features)
151  break;
152  }
153  SG_FREE(nz_row);
154 
155  vector<int32_t> G;
156  vector<int32_t> ind_t;
157  int current_l_idx = 1;
158  for (int32_t i=1; i<n_features; i++)
159  {
160  if (nodes[i].n_desc > 0)
161  {
162  int sub_count = fill_G_recursive(&nodes[i],&G);
163  ind_t.push_back(current_l_idx);
164  ind_t.push_back(current_l_idx+sub_count-1);
165  ind_t.push_back(1.0);
166  current_l_idx += sub_count;
167  }
168  }
169  /*
170  SG_SPRINT("[");
171  for (int32_t i=0; i<G.size(); i++)
172  SG_SPRINT(" %d ",G[i]);
173  SG_SPRINT("]\n");
174  SG_SPRINT("[");
175  for (int32_t i=0; i<ind_t.size(); i++)
176  SG_SPRINT(" %d ",ind_t[i]);
177  SG_SPRINT("]\n");
178  */
179 
180  int32_t supernode_offset = include_supernode ? 3 : 0;
181  m_precomputed_ind_t = SGVector<float64_t>((int32_t)ind_t.size()+supernode_offset);
182  if (include_supernode)
183  {
184  m_precomputed_ind_t[0] = -1;
185  m_precomputed_ind_t[1] = -1;
186  m_precomputed_ind_t[2] = 1.0;
187  }
188  for (int32_t i=0; i<(int32_t)ind_t.size(); i++)
189  m_precomputed_ind_t[i+supernode_offset] = ind_t[i];
190  m_precomputed_G = SGVector<float64_t>((int32_t)G.size());
191  for (int32_t i=0; i<(int32_t)G.size(); i++)
192  m_precomputed_G[i] = G[i] + 1;
193  m_general = true;
194  /*
195  count_sub_nodes_recursive(nodes,1);
196  print_tree(nodes,0);
197  int32_t n_leaves = count_sub_nodes_recursive(nodes,0);
198  m_precomputed_ind_t = SGVector<float64_t>((n_features-n_leaves)*3);
199  SG_PRINT("n_leaves = %d\n",n_leaves);
200  vector<block_tree_node_t> blocks;
201  fill_ind_recursive(nodes, &blocks, 1);
202  m_precomputed_ind_t[0] = -1;
203  m_precomputed_ind_t[1] = -1;
204  m_precomputed_ind_t[2] = 1.0;
205 
206  for (int32_t i=0; i<(int)blocks.size(); i++)
207  {
208  m_precomputed_ind_t[3+3*i+0] = blocks[i].t_min_index;
209  m_precomputed_ind_t[3+3*i+1] = blocks[i].t_max_index;
210  m_precomputed_ind_t[3+3*i+2] = blocks[i].weight;
211  }
212  */
213  for (int32_t i=0; i<n_features; i++)
214  SG_FREE(nodes[i].desc);
215  SG_FREE(nodes);
216 }
217 
220  m_root_block(NULL), m_general(true)
221 {
222  m_precomputed_G = G;
223  m_precomputed_ind_t = ind_t;
224 }
225 
228  m_root_block(NULL), m_general(false)
229 {
230  m_precomputed_ind_t = ind_t;
231 }
232 
234 {
236 }
237 
239 {
241  return m_root_block;
242 }
243 
245 {
246  SG_REF(root_block);
248  m_root_block = root_block;
249 }
250 
252 {
254  return SGVector<index_t>();
255 }
256 
258 {
259  return m_precomputed_G;
260 }
261 
263 {
264  return m_general;
265 }
266 
268 {
270  return m_precomputed_ind_t;
271 
272  else
273  {
275  CList* blocks = new CList(true);
276 
277  vector<block_tree_node_t> tree_nodes = vector<block_tree_node_t>();
278 
280 
281  SGVector<float64_t> ind_t(3+3*tree_nodes.size());
282  // supernode
283  ind_t[0] = -1;
284  ind_t[1] = -1;
285  ind_t[2] = 1.0;
286 
287  for (int32_t i=0; i<(int32_t)tree_nodes.size(); i++)
288  {
289  ind_t[3+i*3] = tree_nodes[i].t_min_index + 1;
290  ind_t[3+i*3+1] = tree_nodes[i].t_max_index;
291  ind_t[3+i*3+2] = tree_nodes[i].weight;
292  }
293 
294  SG_UNREF(blocks);
295 
296  return ind_t;
297  }
298 }

SHOGUN Machine Learning Toolbox - Documentation