Debian Codegraph @

CDistance_matrix.h

raw
1 /* BaitFisher (version 1.2.7) a program for designing DNA target enrichment baits
2 * Copyright 2013-2016 by Christoph Mayer
3 *
4 * This source file is part of the BaitFisher-package.
5 *
6 * This program is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with BaitFisher. If not, see <http://www.gnu.org/licenses/>.
18 *
19 *
20 * For any enquiries send an Email to Christoph Mayer
21 * [email protected]
22 *
23 * When publishing work that is based on the results please cite:
24 * Mayer et al. 2016: BaitFisher: A software package for multi-species target DNA enrichment probe design
25 *
26 */
27 #ifndef CDISTANCE_MATRIX_H
28 #define CDISTANCE_MATRIX_H
29
30 #include <iostream>
31 #include <map>
32 #include "faststring2.h"
33 #include <list>
34 #include <iterator>
35 #include <set>
36
37
38 typedef unsigned long index_distance_map;
39
40 //************************************************
41 // Usage-Restrictions:
42 //
43 // Minimum number of entries:
44 // CDistanceCollection: Number of objects >= 0. Note: 0 and 1 Objects cannot be distinguished.
45 // CDistance_Cluster: Number of objects > 1. 2 Objects: remains to be tested.
46
47 //************************************************
48
49
50 //************************************************
51 // Part I: Distance indices
52 // In order to index pairs of sequences we do the following:
53 // If we have two sequence numbers we assume they are smaller than short integers (16 bits).
54 // We can combine the two short numbers to a 32 bit index of both. This index is unique if
55 // we put the smaller sequence index into the higher bits and the larger index into the lower bits.
56 // Distance indices are of type unsigned and must be 32 bits in size in order to work.
57 //
58 // The following routines handle the index conversions:
59 // makeIndex creates an unsigned combined index from 2 short numbers.
60 // first_index and second_index extract the first and the second index of a pair.
61 //
62 // Note: Initial indices of sequnces: These should be the indices of the sequnces in the file.
63 // They have to be unique in the range 0...taxaNum-1.
64 // During the clustering we create new indices of cluster nodes.
65 // In contrast to the distance indices, cluster indices are of type short.
66 //
67 // How the clustering is done:
68 // cluster_node is the main data structure in the clustering method.
69 // The hierachy of clustering steps are stored in the cluster_hierarchy,
70 // a vector of cluster nodes.
71 // The cluster_hierarchy has a very special form:
72 // The index of each node coincides with the this_nodes_index.
73 // This makes it efficient to obtain the cluster hierachy without
74 // having to search for the correct index.
75 //
76 //
77 //==============
78 // Algorithm:
79 //==============
80 // We start by adding all pairwise distances to the dist_map.
81 // The indices of the pairwise distances are added to the current_cluster_indices
82 // as well as the all_cluster_indices.
83 //
84 // Initially the pairwise distances are added as terminal nodes to the cluster_hierarchy.
85 // This is done by adding the indices of the pairwise distances to the cluster_hierarchy.
86 // Internally, they have children set to -1 and distance 0, indicating that they
87 // do not represent clustering steps.
88 // Note: The cluster_hierarchy is only used to keep track of the clustering steps.
89 // The next step in the algorithm is determined from the sorted_distances,
90 // a list of iterators to the current_cluster_indices. The list of
91 // sorted_distances keeps a list of iterators in accending order of the
92 // distances associated with the index.
93 // Later we add cluster_nodes that have other cluster_nodes as children.
94 // Distances that have been clustered are marked for deletion and are erased permanently later. (For details, read the code.)
95 //************************************************
96
97 inline unsigned makeIndex(short i1, short i2)
98 {
99 unsigned res;
100 if (i1 > i2)
101 {
102 res = i2;
103 res <<= 16;
104 res += i1;
105 return res;
106 }
107 else
108 {
109 res = i1;
110 res <<= 16;
111 res += i2;
112 return res;
113 }
114 }
115
116 inline short first_index(unsigned i)
117 {
118 i >>= 16;
119 return (short) i;
120 }
121
122 inline short second_index(unsigned i)
123 {
124 return (short) i;
125 }
126
127
128
129 // CDistanceCollection collects distance of indexed objects, i.e. objects are referred to by their index.
130 // Distances are stored in a map, which is useful (i) if new objects are introduced regularly, or (ii) if not
131 // all distances are specified.
132
133 class CDistanceCollection
134 {
135 public:
136 typedef std::map<index_distance_map, double> CDistanceCollection_map;
137 typedef std::map<index_distance_map, double>::iterator CDistanceCollection_map_iterator;
138
139 protected:
140 CDistanceCollection_map dist_map;
141
142 public:
143
144 void clear()
145 {
146 dist_map.clear();
147 }
148
149 void add(short i1, short i2, double d)
150 {
151 dist_map[makeIndex(i1, i2)] = d;
152 }
153
154 void print(std::ostream &os)
155 {
156 CDistanceCollection_map_iterator it = dist_map.begin();
157 CDistanceCollection_map_iterator it_end = dist_map.end();
158
159 unsigned u;
160 double d;
161
162 while (it != it_end)
163 {
164 u = it->first;
165 d = it->second;
166
167 os << "d("<< first_index(u) << "," << second_index(u) << ")="<<d << std::endl;
168 ++it;
169 }
170
171 }
172
173 double max_distance()
174 {
175 CDistanceCollection_map_iterator it = dist_map.begin();
176 CDistanceCollection_map_iterator it_end = dist_map.end();
177 double d, d_max;
178
179 if (it == it_end)
180 return 0;
181
182 d_max = it->second;
183
184 while (it != it_end)
185 {
186 d = it->second;
187 d_max = (d_max > d ? d_max:d);
188 ++it;
189 }
190 return d_max;
191 }
192
193
194 };
195
196 struct less_than_distance_iterator
197 {
198 bool operator()(CDistanceCollection::CDistanceCollection_map_iterator it1, CDistanceCollection::CDistanceCollection_map_iterator it2)
199 {
200 return it1->second < it2->second;
201 }
202 };
203
204
205 struct cluster_node
206 {
207 short this_nodes_index; // The index of this node in the cluster_hierarchy vector, but also the index of the node that has the following two children.
208 short child1;
209 short child2;
210 double dist;
211
212 bool unused;
213
214 // constructor
215 cluster_node(short index_this, short ch1, short ch2, double d):
216 this_nodes_index(index_this),child1(ch1), child2(ch2), dist(d), unused(false)
217 {}
218
219 // constructor - terminal node
220 // This node only represents itself and it has no children. So these indices are -1.
221 cluster_node(short index):
222 this_nodes_index(index),child1(-1), child2(-1), dist(0), unused(false)
223 {}
224
225 // cluster_node(): unused(true)
226 // {}
227
228 bool is_terminal()
229 {
230 return (child1 == -1);
231 }
232
233 bool is_unused()
234 {
235 return unused;
236 }
237
238
239 };
240
241
242
243 class CDistance_Cluster : public CDistanceCollection
244 {
245 std::list<CDistanceCollection_map_iterator> sorted_distances;
246
247 // Sets of indices that are known:
248 std::set<short> current_cluster_indices; // Indices of objects added to clustering. (Not indices of distances.)
249 // Keeps track of remaining indices that need to be clustered.
250 // Indices that have been clustered are removed.
251 std::set<short> all_cluster_indices; // Keeps track of all cluster indices that have ever been created.
252
253 std::vector< cluster_node > cluster_hierarchy;
254 unsigned verbosity;
255
256
257 public:
258
259 CDistance_Cluster(unsigned p_verbosity=0):verbosity(p_verbosity)
260 {}
261
262 void clear(unsigned newverbosity=-1u)
263 {
264 sorted_distances.clear();
265 current_cluster_indices.clear();
266 all_cluster_indices.clear();
267 cluster_hierarchy.clear();
268
269 CDistanceCollection::clear();
270
271 if (newverbosity != -1u)
272 verbosity = newverbosity;
273 }
274
275 // At the end of the clustering this is the number of clusters.
276 unsigned get_num_groups_in_current_cluster()
277 {
278 return current_cluster_indices.size();
279 }
280
281
282 void sort()
283 {
284 less_than_distance_iterator lti;
285 sorted_distances.sort(lti);
286 }
287
288 // Add terminal node to cluster hierarchy
289 void addto_cluster_hierarchy(short index)
290 {
291 cluster_hierarchy.push_back(cluster_node(index));
292
293 // The index of this new node should be equal to index.
294 short i = cluster_hierarchy.size();
295
296 if ((i-1) != index)
297 {
298 std::cerr << "Error: Indices must be passed consecutively and 0 based to the cluster hierarchy" << std::endl;
299 }
300 }
301
302 // Add terminal node to cluster hierarchy
303 void addto_cluster_hierarchy(short index, short child1, short child2, double d)
304 {
305 cluster_hierarchy.push_back(cluster_node(index, child1, child2, d));
306
307 // The index of this new node should be equal to index.
308 short i = cluster_hierarchy.size();
309
310 if ((i-1) != index)
311 {
312 std::cerr << "Error: Indices must be passed consecutively and 0 based to the cluster hierarchy" << std::endl;
313 }
314 }
315
316 void add_singleton(short i)
317 {
318 current_cluster_indices.insert(i);
319 all_cluster_indices.insert(i);
320 }
321
322
323 void add(short i1, short i2, double d)
324 {
325 if (i1 == i2)
326 {
327 std::cerr << "Distances of indices to itself cannot be added to the distance matrix. They will always be assumed to be 0" << std::endl;
328 exit(-2);
329 }
330
331 std::pair<CDistanceCollection_map_iterator,bool> ret;
332
333 ret = dist_map.insert(std::make_pair(makeIndex(i1, i2), d));
334 if (ret.second)
335 sorted_distances.push_back(ret.first);
336
337 current_cluster_indices.insert(i1);
338 current_cluster_indices.insert(i2);
339
340 all_cluster_indices.insert(i1);
341 all_cluster_indices.insert(i2);
342 }
343
344 // Do not enter the indices to the sets.
345 // This can be done later.
346 void add_partial(short i1, short i2, double d)
347 {
348 if (i1 == i2)
349 {
350 std::cerr << "Distances of indices to itself cannot be added to the distance matrix. They will always be assumed to be 0" << std::endl;
351 exit(-2);
352 }
353
354 std::pair<CDistanceCollection_map_iterator,bool> ret;
355
356 ret = dist_map.insert(std::make_pair(makeIndex(i1, i2), d));
357 if (ret.second)
358 sorted_distances.push_back(ret.first);
359 }
360
361
362 void print_sorted(std::ostream &os)
363 {
364 sort();
365
366 std::list<CDistanceCollection_map_iterator>::iterator it, it_end;
367
368 it = sorted_distances.begin();
369 it_end = sorted_distances.end();
370
371 unsigned u;
372 double d;
373
374 while (it != it_end)
375 {
376 u = (*it)->first;
377 d = (*it)->second;
378
379 os << "d("<< first_index(u) << "," << second_index(u) << ")="<<d << std::endl;
380 ++it;
381 }
382 }
383
384 void print_current_cluster_indices(std::ostream &os)
385 {
386 std::set<short>::iterator it_cluster_indices = current_cluster_indices.begin();
387 std::set<short>::iterator it_cluster_indices_end = current_cluster_indices.end();
388
389 while (it_cluster_indices != it_cluster_indices_end)
390 {
391 os << *it_cluster_indices << ",";
392 ++it_cluster_indices;
393 }
394 os << std::endl;
395
396
397 }
398
399
400 void run_clustering(double distance_limit)
401 {
402 std::set<short>::iterator it_cluster_indices = current_cluster_indices.begin();
403 std::set<short>::iterator it_cluster_indices_end = current_cluster_indices.end();
404
405 // Add all indices as terminal nodes in cluster_hierarchy.
406 // The cluster_hierarchy is only used to keep track of the clustering steps.
407 while (it_cluster_indices != it_cluster_indices_end)
408 {
409 addto_cluster_hierarchy(*it_cluster_indices);
410 ++it_cluster_indices;
411 }
412
413 if(verbosity > 10)
414 {
415 faststring cluster_string;
416 std::cerr << "Initial cluster string:" << std::endl;
417 get_cluster_string2(cluster_string);
418 std::cerr << cluster_string << std::endl;
419 }
420
421 // The next step in the algorithm is determined from the "sorted_distances",
422 // a list of iterators to the current_cluster_indices. The list of
423 // sorted_distances keeps a list of iterators in accending order of the
424 // distances associated with the index.
425
426 std::list<CDistanceCollection_map_iterator>::iterator it, it_end;
427
428 // sorted_distances is a list of iterators of type CDistanceCollection_map_iterator.
429 // We sort this iterator list such that the iterators to the dist_map (index->distance)
430 // is sorted according to the distance. Smaller distances come first.
431
432 sort();
433 it = sorted_distances.begin();
434 it_end = sorted_distances.end();
435
436 unsigned u;
437 short index1;
438 short index2;
439 short tmp_index;
440
441 short new_cluster_index;
442
443 // We continue to cluster pairs of indices while we still find distances which are less than the threshold
444 while (sorted_distances.size() > 0 && (*it)->second <= distance_limit)
445 {
446 // The pair with the smalles distance is the first one in the sorted_distances list.
447 // We cluster the pair of indices it is pointing to:
448 u = (*it)->first;
449 index1 = first_index(u);
450 index2 = second_index(u);
451
452 // Obsolete: cluster_hierarchy.push_back(std::make_pair(index1, index2));
453 // Determine a new unique index for the next cluster node.
454 new_cluster_index = all_cluster_indices.size();
455
456 if (verbosity > 10)
457 std::cerr << "Outer loop -- Clustering: " << index1 << ", " << index2 << " to " << new_cluster_index << std::endl;
458
459 // Eliminate all distances of index pairs for which one index is equal to index1 or index2.
460
461 it_cluster_indices = current_cluster_indices.begin();
462 it_cluster_indices_end = current_cluster_indices.end();
463
464 // Save within distance of new cluster:
465 double within_distance = dist_map[makeIndex(index1, index2)];
466
467 // Add new cluster to hierarchy.
468 addto_cluster_hierarchy(new_cluster_index, index1, index2, within_distance);
469
470 // Eliminate distance pair index1, index2:
471 dist_map[makeIndex(index1, index2)] = -1; // Mark as unused
472
473 if (verbosity > 10)
474 std::cerr << "Mark unused: " << index1 << " , " << index2 << std::endl;
475
476 // Move through all indices that are not in the new cluster.
477 while (it_cluster_indices != it_cluster_indices_end)
478 {
479 tmp_index = *it_cluster_indices;
480
481 if (verbosity > 10)
482 std::cerr << "**Loop index: " << tmp_index << std::endl;
483
484 if (tmp_index != index1 && tmp_index != index2)
485 {
486 if (verbosity > 10)
487 std::cerr << "**Treat index: " << tmp_index << std::endl;
488
489 double dist1 = dist_map[makeIndex(index1, tmp_index)];
490 double dist2 = dist_map[makeIndex(index2, tmp_index)];
491
492 double max_dist = dist1;
493 // short max_index = index1;
494
495 if (dist2 > max_dist)
496 {
497 // max_index = index2;
498 max_dist = dist2;
499 }
500
501 // Add distance between new cluster and tmp_index
502 add_partial(tmp_index, new_cluster_index, max_dist);
503 /////// dist_map[makeIndex(tmp_index, new_cluster_index)] = max_dist;
504 // The distance between tmp_index (!=index1, != index2) and index1 and index2 are not needed any more.
505 dist_map[makeIndex(tmp_index, index1)] = -1; // Mark as unused
506 dist_map[makeIndex(tmp_index, index2)] = -1; // Mark as unused
507
508 if (verbosity > 10)
509 {
510 std::cerr << "New distance: " << tmp_index << " , " << new_cluster_index << " " << max_dist << std::endl;
511 std::cerr << "Mark unused: " << tmp_index << " , " << index1 << std::endl;
512 std::cerr << "Mark unused: " << tmp_index << " , " << index2 << std::endl;
513 }
514 }
515 ++it_cluster_indices;
516 } // END while (it_cluster_indices != it_cluster_indices_end)
517
518 // Remove index1 and index2 from cluster indices. Add new cluster index.
519
520 if (verbosity > 10)
521 {
522 std::cerr << "Insert new cluster index: " << new_cluster_index << std::endl;
523 std::cerr << "Erase index: " << index1 << std::endl;
524 std::cerr << "Erase index: " << index2 << std::endl;
525 }
526
527 // Now we add the new cluster index to the sets.
528 all_cluster_indices.insert(new_cluster_index);
529 current_cluster_indices.insert(new_cluster_index);
530
531 // We remove the indices we clustered from the current_cluster_indices
532 current_cluster_indices.erase(index1);
533 current_cluster_indices.erase(index2);
534
535 // Adjust sorted_distances:
536 sort();
537
538 it = sorted_distances.begin();
539 it_end = sorted_distances.end();
540
541 // TODO: can be done a bit faster:
542 // Delete items marked for deletion.
543 // Delete them from sorted_distances as well as from the distance_map.
544 // Remember: Distances are sorted from small to large, so the distances
545 // marked for deletion which have distance -1 come first.
546 // If we passed those with distance -1 we are done. (see loop condition)
547
548 while (it != it_end && (*it)->second == -1)
549 {
550 unsigned u = (*it)->first;
551
552 if (verbosity > 10)
553 std::cerr << "Erase permanently: " << first_index(u) << " " << second_index(u) << std::endl;
554
555 dist_map.erase(*it); // it points to the iterator in the dist_map. That is the object we want to remove.
556 sorted_distances.erase(it);
557
558 // Next iteration step:
559 // The next distance with distance -1, if present, should be at the beginning again.
560 it = sorted_distances.begin();
561 // All iterators that are not removed should keep their validity.
562 // it_end = sorted_distances.end();
563 }
564
565 // This completes this clustering step:
566 if(verbosity > 10)
567 {
568 faststring cluster_string;
569 std::cerr << "Cluster string after this step: " << new_cluster_index << std::endl;
570 get_cluster_string2(cluster_string);
571 std::cerr << cluster_string << std::endl;
572 }
573
574 // See above:
575 // Iteration statement: it = sorted_distances.begin();
576
577 } // END while (sorted_distances.size() > 1 && (*it)->second < distance_limit)
578
579 } // run_clustering(double distance_limit)
580
581
582 void append_to_cluster_string(short node, faststring &str, const std::vector<faststring> &names)
583 {
584 short child1 = cluster_hierarchy[node].child1;
585 short child2 = cluster_hierarchy[node].child2;
586 double within_distance = cluster_hierarchy[node].dist;
587 bool isterminal = cluster_hierarchy[node].is_terminal();
588 bool use_names = false;
589
590 if (names.size() > 0)
591 use_names = true;
592
593 if (cluster_hierarchy[node].this_nodes_index != node)
594 {
595 std::cerr << "Error in cluster hierarchy" << std::endl;
596 exit(-1);
597 }
598
599 if (isterminal)
600 {
601 str.append("("); // Bracket terminal nodes. This makes parsing easier.
602 if (use_names)
603 {
604 str.append( names[node] );
605 }
606 else
607 {
608 str.append(faststring(node));
609 }
610 str.append(")");
611 }
612 else
613 {
614 str.append("(");
615 append_to_cluster_string(child1, str, names);
616 str.append(",");
617 append_to_cluster_string(child2, str, names);
618 str.append("):");
619 str.append(faststring(within_distance));
620 }
621 }
622
623
624 void get_cluster_string(faststring &str, const std::vector<faststring> &names)
625 {
626 std::set<short>::iterator it_cluster_indices = current_cluster_indices.begin();
627 std::set<short>::iterator it_cluster_indices_end = current_cluster_indices.end();
628 short tmp_index;
629 short count = 0;
630
631 unsigned remaining_cluster_indices = current_cluster_indices.size();
632
633 if (remaining_cluster_indices > 1)
634 str.append("{");
635 else
636 str.append("(");
637
638 while (it_cluster_indices != it_cluster_indices_end)
639 {
640 if (count > 0)
641 str.append(",");
642 tmp_index = *it_cluster_indices;
643 append_to_cluster_string(tmp_index, str, names);
644 ++it_cluster_indices;
645 ++count;
646 } // END while (it_cluster_indices != it_cluster_indices_end)
647
648 if (remaining_cluster_indices > 1)
649 str.append("}:");
650 else
651 str.append("):");
652
653 str.append(faststring(max_distance()));
654 }
655
656
657 void append_to_cluster_string2(short node, faststring &str)
658 {
659 short child1 = cluster_hierarchy[node].child1;
660 short child2 = cluster_hierarchy[node].child2;
661 double within_distance = cluster_hierarchy[node].dist;
662 bool isterminal = cluster_hierarchy[node].is_terminal();
663
664 if (cluster_hierarchy[node].this_nodes_index != node)
665 {
666 std::cerr << "Error in cluster hierarchy" << std::endl;
667 exit(-1);
668 }
669
670 if (isterminal)
671 {
672 str.append("("); // Bracket terminal nodes. This makes parsing easier.
673 str.append(faststring(node));
674 str.append(")");
675 }
676 else
677 {
678 str.append("(");
679 append_to_cluster_string2(child1, str);
680 str.append(",");
681 append_to_cluster_string2(child2, str);
682 str.append("):");
683 str.append(faststring(within_distance));
684 }
685 }
686
687
688 // As above, but uses indices as names.
689 void get_cluster_string2(faststring &str)
690 {
691 std::set<short>::iterator it_cluster_indices = current_cluster_indices.begin();
692 std::set<short>::iterator it_cluster_indices_end = current_cluster_indices.end();
693 short tmp_index;
694 short count = 0;
695
696 unsigned remaining_cluster_indices = current_cluster_indices.size();
697
698 if (remaining_cluster_indices > 1)
699 str.append("{");
700 else
701 str.append("(");
702
703 // Each (remaining) index in current_cluster_indices
704 // specifies its own cluster which we now print
705 // in hierarchical form.
706 // The current_cluster_indices are the starting point.
707 // Its sub-clusters will be obtained from the cluster_hierarchy
708 // vector.
709
710 while (it_cluster_indices != it_cluster_indices_end)
711 {
712 if (count > 0)
713 str.append(",");
714 tmp_index = *it_cluster_indices;
715 append_to_cluster_string2(tmp_index, str);
716 ++it_cluster_indices;
717 ++count;
718 } // END while (it_cluster_indices != it_cluster_indices_end)
719
720 if (remaining_cluster_indices > 1)
721 str.append("}:");
722 else
723 str.append("):");
724
725 str.append(faststring(max_distance()));
726 }
727
728
729
730 void print_debug(std::ostream &os)
731 {
732 os << "***Debug-stats************************************" << std::endl;
733 os << "sorted_distances.size() " << sorted_distances.size() << std::endl;
734 os << "current_cluster_indices.size() " << current_cluster_indices.size() << std::endl;
735 os << "all_cluster_indices.size() " << all_cluster_indices.size() << std::endl;
736 os << "cluster_hierarchy.size() " << cluster_hierarchy.size() << std::endl;
737 os << "dist_map.size() " << dist_map.size() << std::endl;
738
739
740 os << "Sorted distances:" << std::endl;
741 print_sorted(os);
742
743 os << "Remaining cluster indices:" << std::endl;
744 print_current_cluster_indices(os);
745 os << "**************************************************" << std::endl;
746
747 }
748
749 // How to write an adapter to get the clustering result:
750 // The vector current_cluster_indices contains all "umbrella" indices.
751 // There is one cluster for each entry in this vector.
752 // Some entries might not be clustered. Remember: We stopped clustering
753 // if the remaining distances are above the threshold.
754 // Starting from the indices in current_cluster_indices, we obtain
755 // the subclusters from following the cluster_hierarchy.
756
757 // Gets one cluster by index. Returns false if the index is out of range.
758 // Returns true if in range.
759
760 void add_to_set(short node, std::set<short> &cluster, double &max_distance)
761 {
762 short child1 = cluster_hierarchy[node].child1;
763 short child2 = cluster_hierarchy[node].child2;
764 double within_distance = cluster_hierarchy[node].dist;
765 bool isterminal = cluster_hierarchy[node].is_terminal();
766
767 if (cluster_hierarchy[node].this_nodes_index != node)
768 {
769 std::cerr << "Error in cluster hierarchy" << std::endl;
770 exit(-1);
771 }
772
773 if (isterminal)
774 {
775 cluster.insert(node);
776 }
777 else
778 {
779 add_to_set(child1, cluster, max_distance);
780 add_to_set(child2, cluster, max_distance);
781 if (within_distance > max_distance)
782 max_distance = within_distance;
783
784 // str.append(faststring(within_distance));
785 }
786 }
787
788 // The index must be 0 based.
789 bool get_cluster_by_index(short i, std::set<short> &cluster, double &max_dist)
790 {
791 std::set<short>::iterator it_cluster_indices = current_cluster_indices.begin();
792 std::set<short>::iterator it_cluster_indices_end = current_cluster_indices.end();
793
794 advance(it_cluster_indices, i);
795
796 if (it_cluster_indices == it_cluster_indices_end)
797 return false;
798
799 cluster.clear();
800 max_dist = 0;
801 add_to_set(*it_cluster_indices, cluster, max_dist);
802
803 return true;
804 }
805
806
807
808
809 };
810
811 #endif