< Summary

Class:AgglomerativeClusterer
Assembly:bamlab.micromissiles
File(s):/github/workspace/Assets/Scripts/Algorithms/Clustering/AgglomerativeClusterer.cs
Covered lines:63
Uncovered lines:1
Coverable lines:64
Total lines:101
Line coverage:98.4% (63 of 64)
Covered branches:0
Total branches:0
Covered methods:2
Total methods:3
Method coverage:66.6% (2 of 3)

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity NPath complexity Sequence coverage
AgglomerativeClusterer(...)0%2100%
AgglomerativeClusterer(...)0%110100%
Cluster()0%18180100%

File(s)

/github/workspace/Assets/Scripts/Algorithms/Clustering/AgglomerativeClusterer.cs

#LineLine coverage
 1using System.Collections;
 2using System.Collections.Generic;
 3using UnityEngine;
 4
 5// The agglomerative clusterer class performs agglomerative clustering with the stopping condition
 6// given by the size and radius constraints.
 7public class AgglomerativeClusterer : ISizeAndRadiusConstrainedClusterer {
 8  public AgglomerativeClusterer(List<GameObject> objects, int maxSize, float maxRadius)
 09      : base(objects, maxSize, maxRadius) {}
 10  public AgglomerativeClusterer(List<Agent> agents, int maxSize, float maxRadius)
 3011      : base(agents, maxSize, maxRadius) {}
 12
 13  // Cluster the game objects.
 1014  public override void Cluster() {
 15    // Add a cluster for every game object.
 229516    foreach (var obj in _objects) {
 75517      Cluster cluster = new Cluster(obj);
 75518      cluster.AddObject(obj);
 75519      _clusters.Add(cluster);
 75520    }
 21
 22    // Create a set containing all valid cluster indices.
 1023    HashSet<int> validClusterIndices = new HashSet<int>();
 228524    for (int i = 0; i < _clusters.Count; ++i) {
 75525      validClusterIndices.Add(i);
 75526    }
 27
 28    // Find the pairwise distances between all clusters.
 29    // The upper triangular half of the distances matrix is unused.
 1030    float[,] distances = new float[_clusters.Count, _clusters.Count];
 228531    for (int i = 0; i < _clusters.Count; ++i) {
 39691032      for (int j = 0; j < i; ++j) {
 13180033        distances[i, j] = Vector3.Distance(_clusters[i].Coordinates, _clusters[j].Coordinates);
 13180034      }
 75535    }
 36
 182237    while (true) {
 38      // Find the minimum distance between two clusters.
 91139      float minDistance = Mathf.Infinity;
 91140      int clusterIndex1 = -1;
 91141      int clusterIndex2 = -1;
 112250842      for (int i = 0; i < _clusters.Count; ++i) {
 27314879243        for (int j = 0; j < i; ++j) {
 9080663744          if (distances[i, j] < minDistance) {
 608145            minDistance = distances[i, j];
 608146            clusterIndex1 = i;
 608147            clusterIndex2 = j;
 608148          }
 9080055649        }
 37356250      }
 51
 52      // Check whether the minimum distance exceeds the maximum cluster radius, in which case the
 53      // algorithm has converged. This produces a conservative solution because the radius of a
 54      // merged cluster is less than or equal to the sum of the original cluster radii.
 92155      if (minDistance >= _maxRadius) {
 1056        break;
 57      }
 58
 59      // Check whether merging the two clusters would violate the size constraint.
 121960      if (_clusters[clusterIndex1].Size() + _clusters[clusterIndex2].Size() > _maxSize) {
 31861        distances[clusterIndex1, clusterIndex2] = Mathf.Infinity;
 31862        continue;
 63      }
 64
 65      // Merge the two clusters together.
 58366      int minClusterIndex = Mathf.Min(clusterIndex1, clusterIndex2);
 58367      int maxClusterIndex = Mathf.Max(clusterIndex1, clusterIndex2);
 58368      _clusters[minClusterIndex].Merge(_clusters[maxClusterIndex]);
 58369      _clusters[minClusterIndex].Recenter();
 58370      validClusterIndices.Remove(maxClusterIndex);
 71
 72      // Update the distances matrix using the distance between the cluster centroids.
 73      // TODO(titan): Change the distance metric to use average or maximum linkage.
 29548474      for (int i = 0; i < minClusterIndex; ++i) {
 15776675        if (distances[minClusterIndex, i] < Mathf.Infinity) {
 5966076          distances[minClusterIndex, i] =
 77              Vector3.Distance(_clusters[minClusterIndex].Coordinates, _clusters[i].Coordinates);
 5966078        }
 9810679      }
 35732080      for (int i = minClusterIndex + 1; i < _clusters.Count; ++i) {
 18655481        if (distances[i, minClusterIndex] < Mathf.Infinity) {
 6783682          distances[i, minClusterIndex] =
 83              Vector3.Distance(_clusters[minClusterIndex].Coordinates, _clusters[i].Coordinates);
 6783684        }
 11871885      }
 33750886      for (int i = 0; i < maxClusterIndex; ++i) {
 11211487        distances[maxClusterIndex, i] = Mathf.Infinity;
 11211488      }
 31529689      for (int i = maxClusterIndex + 1; i < _clusters.Count; ++i) {
 10471090        distances[i, maxClusterIndex] = Mathf.Infinity;
 10471091      }
 58392    }
 93
 94    // Select only the valid clusters.
 228595    for (int i = _clusters.Count - 1; i >= 0; --i) {
 133896      if (!validClusterIndices.Contains(i)) {
 58397        _clusters.RemoveAt(i);
 58398      }
 75599    }
 10100  }
 101}