SHOGUN  3.2.1
 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 <shogun/lib/IndexBlock.h>
12 #include <shogun/lib/SGMatrix.h>
13 #include <shogun/lib/List.h>
14 #include <vector>
15 
16 using namespace std;
17 using namespace shogun;
18 
20 {
22  int32_t n_desc;
23  int32_t sub_nodes_count;
24  int32_t idx;
25 };
26 
28 {
29  block_tree_node_t(int32_t min, int32_t max, float64_t w)
30  {
31  t_min_index = min;
32  t_max_index = max;
33  weight = w;
34  }
35  int32_t t_min_index, t_max_index;
37 };
38 
40 {
41  if (node->n_desc==0)
42  {
43  return 1;
44  }
45  else
46  {
47  int c = 0;
48  for (int32_t i=0; i<node->n_desc; i++)
49  {
50  c += count_sub_nodes_recursive(node->desc[i], self);
51  }
52  if (self)
53  node->sub_nodes_count = c;
54  return c + self;
55  }
56 }
57 
58 void print_tree(tree_node_t* node, int tabs)
59 {
60  for (int32_t t=0; t<tabs; t++)
61  SG_SPRINT(" ")
62  SG_SPRINT("%d %d\n",node->idx, node->sub_nodes_count)
63  for (int32_t i=0; i<node->n_desc; i++)
64  print_tree(node->desc[i],tabs+1);
65 }
66 
67 int32_t fill_G_recursive(tree_node_t* node, vector<int32_t>* G)
68 {
69  int32_t c=1;
70  G->push_back(node->idx);
71  for (int32_t i=0; i<node->n_desc; i++)
72  c+= fill_G_recursive(node->desc[i], G);
73  return c;
74 }
75 
76 void fill_ind_recursive(tree_node_t* node, vector<block_tree_node_t>* tree_nodes, int32_t lower)
77 {
78  int32_t l = lower;
79  for (int32_t i=0; i<node->n_desc; i++)
80  {
81  int32_t c = node->desc[i]->sub_nodes_count;
82  if (c>0)
83  {
84  tree_nodes->push_back(block_tree_node_t(l,l+c-1,1.0));
85  fill_ind_recursive(node->desc[i], tree_nodes, l);
86  l+=c;
87  }
88  else
89  l++;
90  }
91 }
92 
93 void collect_tree_nodes_recursive(CIndexBlock* subtree_root_block, vector<block_tree_node_t>* tree_nodes)
94 {
95  CList* sub_blocks = subtree_root_block->get_sub_blocks();
96  if (sub_blocks->get_num_elements()>0)
97  {
98  CIndexBlock* iterator = (CIndexBlock*)sub_blocks->get_first_element();
99  do
100  {
101  SG_SDEBUG("Block [%d %d] \n",iterator->get_min_index(), iterator->get_max_index())
102  tree_nodes->push_back(block_tree_node_t(iterator->get_min_index(),iterator->get_max_index(),iterator->get_weight()));
103  if (iterator->get_num_sub_blocks()>0)
104  collect_tree_nodes_recursive(iterator, tree_nodes);
105  SG_UNREF(iterator);
106  }
107  while ((iterator = (CIndexBlock*)sub_blocks->get_next_element()) != NULL);
108  }
109  SG_UNREF(sub_blocks);
110 }
111 
112 CIndexBlockTree::CIndexBlockTree() :
113  CIndexBlockRelation(), m_root_block(NULL),
114  m_general(false)
115 {
116 
117 }
118 
120  m_root_block(NULL), m_general(false)
121 {
122  set_root_block(root_block);
123 }
124 
125 CIndexBlockTree::CIndexBlockTree(SGMatrix<float64_t> adjacency_matrix, bool include_supernode) :
127  m_root_block(NULL), m_general(true)
128 {
129  ASSERT(adjacency_matrix.num_rows == adjacency_matrix.num_cols)
130  int32_t n_features = adjacency_matrix.num_rows;
131 
132  // well ordering is assumed
133 
134  tree_node_t* nodes = SG_CALLOC(tree_node_t, n_features);
135 
136  int32_t* nz_row = SG_CALLOC(int32_t, n_features);
137  for (int32_t i=0; i<n_features; i++)
138  {
139  nodes[i].idx = i;
140  nodes[i].sub_nodes_count = 0;
141  int32_t c = 0;
142  for (int32_t j=i; j<n_features; j++)
143  {
144  if (adjacency_matrix(j,i)!=0.0)
145  nz_row[c++] = j;
146  }
147  nodes[i].n_desc = c;
148  nodes[i].desc = SG_MALLOC(tree_node_t*, c);
149  for (int32_t j=0; j<c; j++)
150  {
151  nodes[i].desc[j] = &nodes[nz_row[j]];
152  }
153  if (nz_row[c] == n_features)
154  break;
155  }
156  SG_FREE(nz_row);
157 
158  vector<int32_t> G;
159  vector<int32_t> ind_t;
160  int current_l_idx = 1;
161  for (int32_t i=1; i<n_features; i++)
162  {
163  if (nodes[i].n_desc > 0)
164  {
165  int sub_count = fill_G_recursive(&nodes[i],&G);
166  ind_t.push_back(current_l_idx);
167  ind_t.push_back(current_l_idx+sub_count-1);
168  ind_t.push_back(1.0);
169  current_l_idx += sub_count;
170  }
171  }
172  /*
173  SG_SPRINT("[")
174  for (int32_t i=0; i<G.size(); i++)
175  SG_SPRINT(" %d ",G[i])
176  SG_SPRINT("]\n")
177  SG_SPRINT("[")
178  for (int32_t i=0; i<ind_t.size(); i++)
179  SG_SPRINT(" %d ",ind_t[i])
180  SG_SPRINT("]\n")
181  */
182 
183  int32_t supernode_offset = include_supernode ? 3 : 0;
184  m_precomputed_ind_t = SGVector<float64_t>((int32_t)ind_t.size()+supernode_offset);
185  if (include_supernode)
186  {
187  m_precomputed_ind_t[0] = -1;
188  m_precomputed_ind_t[1] = -1;
189  m_precomputed_ind_t[2] = 1.0;
190  }
191  for (int32_t i=0; i<(int32_t)ind_t.size(); i++)
192  m_precomputed_ind_t[i+supernode_offset] = ind_t[i];
193  m_precomputed_G = SGVector<float64_t>((int32_t)G.size());
194  for (int32_t i=0; i<(int32_t)G.size(); i++)
195  m_precomputed_G[i] = G[i] + 1;
196  m_general = true;
197  /*
198  count_sub_nodes_recursive(nodes,1);
199  print_tree(nodes,0);
200  int32_t n_leaves = count_sub_nodes_recursive(nodes,0);
201  m_precomputed_ind_t = SGVector<float64_t>((n_features-n_leaves)*3);
202  SG_PRINT("n_leaves = %d\n",n_leaves)
203  vector<block_tree_node_t> blocks;
204  fill_ind_recursive(nodes, &blocks, 1);
205  m_precomputed_ind_t[0] = -1;
206  m_precomputed_ind_t[1] = -1;
207  m_precomputed_ind_t[2] = 1.0;
208 
209  for (int32_t i=0; i<(int)blocks.size(); i++)
210  {
211  m_precomputed_ind_t[3+3*i+0] = blocks[i].t_min_index;
212  m_precomputed_ind_t[3+3*i+1] = blocks[i].t_max_index;
213  m_precomputed_ind_t[3+3*i+2] = blocks[i].weight;
214  }
215  */
216  for (int32_t i=0; i<n_features; i++)
217  SG_FREE(nodes[i].desc);
218  SG_FREE(nodes);
219 }
220 
223  m_root_block(NULL), m_general(true)
224 {
225  m_precomputed_G = G;
226  m_precomputed_ind_t = ind_t;
227 }
228 
231  m_root_block(NULL), m_general(false)
232 {
233  m_precomputed_ind_t = ind_t;
234 }
235 
237 {
239 }
240 
242 {
244  return m_root_block;
245 }
246 
248 {
249  SG_REF(root_block);
251  m_root_block = root_block;
252 }
253 
255 {
257  return SGVector<index_t>();
258 }
259 
261 {
262  return m_precomputed_G;
263 }
264 
266 {
267  return m_general;
268 }
269 
271 {
273  return m_precomputed_ind_t;
274 
275  else
276  {
278  CList* blocks = new CList(true);
279 
280  vector<block_tree_node_t> tree_nodes = vector<block_tree_node_t>();
281 
283 
284  SGVector<float64_t> ind_t(3+3*tree_nodes.size());
285  // supernode
286  ind_t[0] = -1;
287  ind_t[1] = -1;
288  ind_t[2] = 1.0;
289 
290  for (int32_t i=0; i<(int32_t)tree_nodes.size(); i++)
291  {
292  ind_t[3+i*3] = tree_nodes[i].t_min_index + 1;
293  ind_t[3+i*3+1] = tree_nodes[i].t_max_index;
294  ind_t[3+i*3+2] = tree_nodes[i].weight;
295  }
296 
297  SG_UNREF(blocks);
298 
299  return ind_t;
300  }
301 }

SHOGUN Machine Learning Toolbox - Documentation