--------------------------------------------------------------------------- Private Code ----------------------------------------------------------------------------*/ * This routine performs a bottoms-up clustering on the samples * held in the kd-tree of the Clusterer data structure. The * result is a cluster tree. Each node in the tree represents * a cluster which conceptually c
| 702 | * @note History: 5/29/89, DSJ, Created. |
| 703 | */ |
| 704 | void CreateClusterTree(CLUSTERER *Clusterer) { |
| 705 | ClusteringContext context; |
| 706 | ClusterPair HeapEntry; |
| 707 | TEMPCLUSTER *PotentialCluster; |
| 708 | |
| 709 | // each sample and its nearest neighbor form a "potential" cluster |
| 710 | // save these in a heap with the "best" potential clusters on top |
| 711 | context.tree = Clusterer->KDTree; |
| 712 | context.candidates = (TEMPCLUSTER *) |
| 713 | Emalloc(Clusterer->NumberOfSamples * sizeof(TEMPCLUSTER)); |
| 714 | context.next = 0; |
| 715 | context.heap = new ClusterHeap(Clusterer->NumberOfSamples); |
| 716 | KDWalk(context.tree, (void_proc)MakePotentialClusters, &context); |
| 717 | |
| 718 | // form potential clusters into actual clusters - always do "best" first |
| 719 | while (context.heap->Pop(&HeapEntry)) { |
| 720 | PotentialCluster = HeapEntry.data; |
| 721 | |
| 722 | // if main cluster of potential cluster is already in another cluster |
| 723 | // then we don't need to worry about it |
| 724 | if (PotentialCluster->Cluster->Clustered) { |
| 725 | continue; |
| 726 | } |
| 727 | |
| 728 | // if main cluster is not yet clustered, but its nearest neighbor is |
| 729 | // then we must find a new nearest neighbor |
| 730 | else if (PotentialCluster->Neighbor->Clustered) { |
| 731 | PotentialCluster->Neighbor = |
| 732 | FindNearestNeighbor(context.tree, PotentialCluster->Cluster, |
| 733 | &HeapEntry.key); |
| 734 | if (PotentialCluster->Neighbor != NULL) { |
| 735 | context.heap->Push(&HeapEntry); |
| 736 | } |
| 737 | } |
| 738 | |
| 739 | // if neither cluster is already clustered, form permanent cluster |
| 740 | else { |
| 741 | PotentialCluster->Cluster = |
| 742 | MakeNewCluster(Clusterer, PotentialCluster); |
| 743 | PotentialCluster->Neighbor = |
| 744 | FindNearestNeighbor(context.tree, PotentialCluster->Cluster, |
| 745 | &HeapEntry.key); |
| 746 | if (PotentialCluster->Neighbor != NULL) { |
| 747 | context.heap->Push(&HeapEntry); |
| 748 | } |
| 749 | } |
| 750 | } |
| 751 | |
| 752 | // the root node in the cluster tree is now the only node in the kd-tree |
| 753 | Clusterer->Root = (CLUSTER *) RootOf(Clusterer->KDTree); |
| 754 | |
| 755 | // free up the memory used by the K-D tree, heap, and temp clusters |
| 756 | FreeKDTree(context.tree); |
| 757 | Clusterer->KDTree = NULL; |
| 758 | delete context.heap; |
| 759 | memfree(context.candidates); |
| 760 | } // CreateClusterTree |
| 761 |
no test coverage detected