1 // ******************************************************************************
2 //
3 // Title: Force Field X.
4 // Description: Force Field X - Software for Molecular Biophysics.
5 // Copyright: Copyright (c) Michael J. Schnieders 2001-2025.
6 //
7 // This file is part of Force Field X.
8 //
9 // Force Field X is free software; you can redistribute it and/or modify it
10 // under the terms of the GNU General Public License version 3 as published by
11 // the Free Software Foundation.
12 //
13 // Force Field X is distributed in the hope that it will be useful, but WITHOUT
14 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15 // FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
16 // details.
17 //
18 // You should have received a copy of the GNU General Public License along with
19 // Force Field X; if not, write to the Free Software Foundation, Inc., 59 Temple
20 // Place, Suite 330, Boston, MA 02111-1307 USA
21 //
22 // Linking this library statically or dynamically with other modules is making a
23 // combined work based on this library. Thus, the terms and conditions of the
24 // GNU General Public License cover the whole combination.
25 //
26 // As a special exception, the copyright holders of this library give you
27 // permission to link this library with independent modules to produce an
28 // executable, regardless of the license terms of these independent modules, and
29 // to copy and distribute the resulting executable under terms of your choice,
30 // provided that you also meet, for each linked independent module, the terms
31 // and conditions of the license of that module. An independent module is a
32 // module which is not derived from or based on this library. If you modify this
33 // library, you may extend this exception to your version of the library, but
34 // you are not obligated to do so. If you do not wish to do so, delete this
35 // exception statement from your version.
36 //
37 // ******************************************************************************
38 package ffx.numerics.clustering;
39
40 import java.util.ArrayList;
41 import java.util.Collection;
42 import java.util.List;
43
44 /**
45 * Performs agglomerative steps to build a clustering hierarchy from an initial set
46 * of singleton clusters and a map of pairwise distances.
47 *
48 * @author Lars Behnke, 2013
49 * @author Michael J. Schnieders
50 * @since 1.0
51 */
52 public class HierarchyBuilder {
53
54 private final DistanceMap distances;
55 private final List<Cluster> clusters;
56 private int globalClusterIndex = 0;
57
58 /**
59 * Gets the DistanceMap used to track inter-cluster distances during agglomeration.
60 *
61 * @return the DistanceMap backing this builder
62 */
63 public DistanceMap getDistances() {
64 return distances;
65 }
66
67 /**
68 * Returns the current working list of clusters (not necessarily a single root).
69 *
70 * @return the list of current clusters
71 */
72 public List<Cluster> getClusters() {
73 return clusters;
74 }
75
76 /**
77 * Constructs a HierarchyBuilder with an initial set of clusters and inter-cluster distances.
78 *
79 * @param clusters initial clusters (typically singletons)
80 * @param distances map of inter-cluster distances
81 */
82 public HierarchyBuilder(List<Cluster> clusters, DistanceMap distances) {
83 this.clusters = clusters;
84 this.distances = distances;
85 }
86
87 /**
88 * Performs agglomeration until the minimal inter-cluster distance exceeds the threshold,
89 * and returns the remaining clusters (flat clustering at that cut).
90 *
91 * @param linkageStrategy linkage strategy to compute inter-cluster distances
92 * @param threshold maximum allowed linkage distance for merging
93 * @return flat list of clusters remaining at the specified threshold
94 */
95 public List<Cluster> flatAgg(LinkageStrategy linkageStrategy, Double threshold) {
96 while ((!isTreeComplete()) && (distances.minDist() != null) && (distances.minDist() <= threshold)) {
97 agglomerate(linkageStrategy);
98 }
99 return clusters;
100 }
101
102 /**
103 * Performs one agglomerative step by merging the two closest clusters and updating linkages.
104 *
105 * @param linkageStrategy strategy to compute new distances to the merged cluster
106 */
107 public void agglomerate(LinkageStrategy linkageStrategy) {
108 ClusterPair minDistLink = distances.removeFirst();
109 if (minDistLink != null) {
110 clusters.remove(minDistLink.getrCluster());
111 clusters.remove(minDistLink.getlCluster());
112
113 Cluster oldClusterL = minDistLink.getlCluster();
114 Cluster oldClusterR = minDistLink.getrCluster();
115 Cluster newCluster = minDistLink.agglomerate(++globalClusterIndex);
116
117 for (Cluster iClust : clusters) {
118 ClusterPair link1 = findByClusters(iClust, oldClusterL);
119 ClusterPair link2 = findByClusters(iClust, oldClusterR);
120 ClusterPair newLinkage = new ClusterPair();
121 newLinkage.setlCluster(iClust);
122 newLinkage.setrCluster(newCluster);
123 Collection<Distance> distanceValues = new ArrayList<>();
124
125 if (link1 != null) {
126 Double distVal = link1.getLinkageDistance();
127 Double weightVal = link1.getOtherCluster(iClust).getWeightValue();
128 distanceValues.add(new Distance(distVal, weightVal));
129 distances.remove(link1);
130 }
131 if (link2 != null) {
132 Double distVal = link2.getLinkageDistance();
133 Double weightVal = link2.getOtherCluster(iClust).getWeightValue();
134 distanceValues.add(new Distance(distVal, weightVal));
135 distances.remove(link2);
136 }
137
138 Distance newDistance = linkageStrategy.calculateDistance(distanceValues);
139
140 newLinkage.setLinkageDistance(newDistance.getDistance());
141 distances.add(newLinkage);
142 }
143 clusters.add(newCluster);
144 }
145 }
146
147 private ClusterPair findByClusters(Cluster c1, Cluster c2) {
148 return distances.findByCodePair(c1, c2);
149 }
150
151 /**
152 * Returns true if only a single cluster remains (i.e., the hierarchy has a root).
153 *
154 * @return true if a single root cluster remains; false otherwise
155 */
156 public boolean isTreeComplete() {
157 return clusters.size() == 1;
158 }
159
160 /**
161 * Returns the root cluster if the hierarchy is complete.
162 *
163 * @return the single remaining root cluster
164 * @throws RuntimeException if the tree is not complete
165 */
166 public Cluster getRootCluster() {
167 if (!isTreeComplete()) {
168 throw new RuntimeException("No root available");
169 }
170 return clusters.getFirst();
171 }
172
173 }