24 using namespace shogun;
26 #ifndef DOXYGEN_SHOULD_SKIP_THIS
29 struct DIJKSTRA_THREAD_PARAM
38 const int32_t* edges_idx_matrix;
101 SG_ERROR(
"Given distance matrix is not square.\n");
106 SG_ERROR(
"K parameter should be less than number of given vectors (k=%d, N=%d)\n",
m_k, N);
114 CFibonacciHeap* heap =
new CFibonacciHeap(N);
119 heap->insert(j,D_matrix[i*N+j]);
122 heap->extract_min(tmp);
125 for (j=0; j<
m_k; j++)
127 edges_idx_matrix[i*m_k+j] = heap->extract_min(tmp);
128 edges_matrix[i*m_k+j] = tmp;
142 pthread_t* threads =
SG_MALLOC(pthread_t, num_threads);
143 DIJKSTRA_THREAD_PARAM* parameters =
SG_MALLOC(DIJKSTRA_THREAD_PARAM, num_threads);
145 CFibonacciHeap** heaps =
SG_MALLOC(CFibonacciHeap*, num_threads);
146 for (t=0; t<num_threads; t++)
147 heaps[t] =
new CFibonacciHeap(N);
150 int32_t num_threads = 1;
163 pthread_attr_init(&attr);
164 pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
165 for (t=0; t<num_threads; t++)
167 parameters[t].i_start = t;
168 parameters[t].i_stop = N;
169 parameters[t].i_step = num_threads;
170 parameters[t].heap = heaps[t];
171 parameters[t].edges_matrix = edges_matrix;
172 parameters[t].edges_idx_matrix = edges_idx_matrix;
173 parameters[t].s = s+t*N;
174 parameters[t].f = f+t*N;
175 parameters[t].m_k =
m_k;
176 parameters[t].shortest_D = shortest_D;
179 for (t=0; t<num_threads; t++)
180 pthread_join(threads[t], NULL);
181 pthread_attr_destroy(&attr);
182 for (t=0; t<num_threads; t++)
188 D_THREAD_PARAM single_thread_param;
189 single_thread_param.i_start = 0;
190 single_thread_param.i_stop = N;
191 single_thread_param.i_step = 1;
192 single_thread_param.m_k =
m_k;
193 single_thread_param.heap =
new CFibonacciHeap(N);
194 single_thread_param.edges_matrix = edges_matrix;
195 single_thread_param.edges_idx_matrix = edges_idx_matrix;
196 single_thread_param.s = s;
197 single_thread_param.f = f;
198 single_thread_param.shortest_D = shortest_D;
200 delete single_thread_param.heap;
214 DIJKSTRA_THREAD_PARAM* parameters = (DIJKSTRA_THREAD_PARAM*)p;
215 CFibonacciHeap* heap = parameters->heap;
216 int32_t i_start = parameters->i_start;
217 int32_t i_stop = parameters->i_stop;
218 int32_t i_step = parameters->i_step;
219 bool* s = parameters->s;
220 bool* f = parameters->f;
221 const float64_t* edges_matrix = parameters->edges_matrix;
222 const int32_t* edges_idx_matrix = parameters->edges_idx_matrix;
223 float64_t* shortest_D = parameters->shortest_D;
224 int32_t
m_k = parameters->m_k;
225 int32_t k,j,i,min_item,w;
232 for (k=i_start; k<i_stop; k+=i_step)
242 shortest_D[k*N+k] = 0.0;
249 while (heap->get_num_nodes()>0)
252 min_item = heap->extract_min(tmp);
257 for (i=0; i<
m_k; i++)
260 w = edges_idx_matrix[min_item*m_k+i];
265 dist = shortest_D[k*N+min_item] + edges_matrix[min_item*m_k+i];
267 if (dist < shortest_D[k*N+w])
270 shortest_D[k*N+w] = dist;
275 heap->decrease_key(w, dist);
280 heap->insert(w, dist);