SHOGUN  3.2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
TaskTree.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 {
18  task_tree_node_t(int32_t min, int32_t max, float64_t w)
19  {
20  t_min_index = min;
21  t_max_index = max;
22  weight = w;
23  }
24  int32_t t_min_index, t_max_index;
26 };
27 
28 int32_t count_leaf_tasks_recursive(CTask* subtree_root_block)
29 {
30  CList* sub_tasks = subtree_root_block->get_subtasks();
31  int32_t n_sub_tasks = sub_tasks->get_num_elements();
32  if (n_sub_tasks==0)
33  {
34  SG_UNREF(sub_tasks);
35  return 1;
36  }
37  else
38  {
39  int32_t sum = 0;
40  CTask* iterator = (CTask*)sub_tasks->get_first_element();
41  do
42  {
43  sum += count_leaf_tasks_recursive(iterator);
44  SG_UNREF(iterator);
45  }
46  while ((iterator = (CTask*)sub_tasks->get_next_element()) != NULL);
47 
48  SG_UNREF(sub_tasks);
49  return sum;
50  }
51 }
52 
53 void collect_tree_tasks_recursive(CTask* subtree_root_block, vector<task_tree_node_t>* tree_nodes, int low)
54 {
55  int32_t lower = low;
56  CList* sub_blocks = subtree_root_block->get_subtasks();
57  if (sub_blocks->get_num_elements()>0)
58  {
59  CTask* iterator = (CTask*)sub_blocks->get_first_element();
60  do
61  {
62  if (iterator->get_num_subtasks()>0)
63  {
64  int32_t n_leaves = count_leaf_tasks_recursive(iterator);
65  //SG_SDEBUG("Block [%d %d] has %d leaf childs \n",iterator->get_min_index(), iterator->get_max_index(), n_leaves)
66  tree_nodes->push_back(task_tree_node_t(lower,lower+n_leaves-1,iterator->get_weight()));
67  collect_tree_tasks_recursive(iterator, tree_nodes, lower);
68  lower = lower + n_leaves;
69  }
70  else
71  lower++;
72  SG_UNREF(iterator);
73  }
74  while ((iterator = (CTask*)sub_blocks->get_next_element()) != NULL);
75  }
76  SG_UNREF(sub_blocks);
77 }
78 
79 void collect_leaf_tasks_recursive(CTask* subtree_root_block, CList* list)
80 {
81  CList* sub_blocks = subtree_root_block->get_subtasks();
82  if (sub_blocks->get_num_elements() == 0)
83  {
84  list->append_element(subtree_root_block);
85  }
86  else
87  {
88  CTask* iterator = (CTask*)sub_blocks->get_first_element();
89  do
90  {
91  collect_leaf_tasks_recursive(iterator, list);
92  SG_UNREF(iterator);
93  }
94  while ((iterator = (CTask*)sub_blocks->get_next_element()) != NULL);
95  }
96  SG_UNREF(sub_blocks);
97 }
98 
99 int32_t count_leaft_tasks_recursive(CTask* subtree_root_block)
100 {
101  CList* sub_blocks = subtree_root_block->get_subtasks();
102  int32_t r = 0;
103  if (sub_blocks->get_num_elements() == 0)
104  {
105  return 1;
106  }
107  else
108  {
109  CTask* iterator = (CTask*)sub_blocks->get_first_element();
110  do
111  {
112  r += count_leaf_tasks_recursive(iterator);
113  SG_UNREF(iterator);
114  }
115  while ((iterator = (CTask*)sub_blocks->get_next_element()) != NULL);
116  }
117  SG_UNREF(sub_blocks);
118  return r;
119 }
120 
121 CTaskTree::CTaskTree() : CTaskRelation(),
122  m_root_task(NULL)
123 {
124 
125 }
126 
128  m_root_task(NULL)
129 {
130  set_root_task(root_task);
131 }
132 
134 {
136 }
137 
139 {
140  CList* blocks = new CList(true);
142  SG_DEBUG("Collected %d leaf blocks\n", blocks->get_num_elements())
143  //check_blocks_list(blocks);
144 
145  //SGVector<index_t> ind(blocks->get_num_elements()+1);
146 
147  int t_i = 0;
148  //ind[0] = 0;
149  //
150  SGVector<index_t>* tasks_indices = SG_MALLOC(SGVector<index_t>, blocks->get_num_elements());
151  CTask* iterator = (CTask*)blocks->get_first_element();
152  do
153  {
154  tasks_indices[t_i] = iterator->get_indices();
155  //REQUIRE(iterator->is_contiguous(),"Task is not contiguous")
156  //ind[t_i+1] = iterator->get_indices()[iterator->get_indices().vlen-1] + 1;
157  //SG_DEBUG("Block = [%d,%d]\n", iterator->get_min_index(), iterator->get_max_index())
158  SG_UNREF(iterator);
159  t_i++;
160  }
161  while ((iterator = (CTask*)blocks->get_next_element()) != NULL);
162 
163  SG_UNREF(blocks);
164 
165  return tasks_indices;
166 }
167 
169 {
171 }
172 
174 {
175  int n_blocks = get_num_tasks() - 1;
176  SG_DEBUG("Number of blocks = %d \n", n_blocks)
177 
178  vector<task_tree_node_t> tree_nodes = vector<task_tree_node_t>();
179 
181 
182  SGVector<float64_t> ind_t(3+3*tree_nodes.size());
183  // supernode
184  ind_t[0] = -1;
185  ind_t[1] = -1;
186  ind_t[2] = 1.0;
187 
188  for (int32_t i=0; i<(int32_t)tree_nodes.size(); i++)
189  {
190  ind_t[3+i*3] = tree_nodes[i].t_min_index;
191  ind_t[3+i*3+1] = tree_nodes[i].t_max_index;
192  ind_t[3+i*3+2] = tree_nodes[i].weight;
193  }
194 
195  return ind_t;
196 }

SHOGUN Machine Learning Toolbox - Documentation