Calculate connections between clusters and merge clusters accordingly as
long as connections exceed threshold
542649
private void calculateGTClusterConnections(){
        for (int c0 = 0; c0 < gt0Clusters.size(); c0++) {
            for (int c1 = 0; c1 < gt0Clusters.size(); c1++) {
                    gt0Clusters.get(c0).calculateClusterConnection(c1, true);
            }
        }

        boolean changedConnection = true;
        while(changedConnection){
            if(debug){
                System.out.println("Cluster Connection");
                for (int c = 0; c < gt0Clusters.size(); c++) {
                    System.out.print("C"+gt0Clusters.get(c).label+" --> ");
                    for (int c1 = 0; c1 < gt0Clusters.get(c).connections.size(); c1++) {
                        System.out.print(" C"+gt0Clusters.get(c1).label+": "+gt0Clusters.get(c).connections.get(c1));
                    }
                    System.out.println("");
                }
                System.out.println("");
            }

            double max = 0;
            int maxIndexI = -1;
            int maxIndexJ = -1;

            changedConnection = false;
            for (int c0 = 0; c0 < gt0Clusters.size(); c0++) {
                for (int c1 = c0+1; c1 < gt0Clusters.size(); c1++) {
                    if(c0==c1) continue;
                        double min =Math.min(gt0Clusters.get(c0).connections.get(c1), gt0Clusters.get(c1).connections.get(c0));
                        if(min > max){
                            max = min;
                            maxIndexI = c0;
                            maxIndexJ = c1;
                        }
                }
            }
            if(maxIndexI!=-1 && max > tauConnection){
                gt0Clusters.get(maxIndexI).mergeCluster(maxIndexJ);
                if(debug)
                    System.out.println("Merging "+maxIndexI+" and "+maxIndexJ+" because of connection "+max);

                changedConnection = true;
            }
        }
        numGT0Classes = gt0Clusters.size();
    }
1312203
def connected_sets(C, mincount_connectivity=0, strong=True):
    
    import msmtools.estimation as msmest
    Cconn = C.copy()
    Cconn[np.where(C <= mincount_connectivity)] = 0
    # treat each connected set separately
    S = msmest.connected_sets(Cconn, directed=strong)
    return S
533837
private void mergeClusters (int smallClus, int bigClus)
	{		
		//System.out.println("Merge clusters "+smallClus+" and "+bigClus+".");
		// Iterate through the density grids in grid_list to find those which are in highClass
		for (Map.Entry<DensityGrid, CharacteristicVector> grid : grid_list.entrySet())
		{
			DensityGrid dg = grid.getKey();
			CharacteristicVector cv = grid.getValue();

			// Assign density grids in smallClus to bigClus
			if(cv.getLabel() == smallClus)
			{
				cv.setLabel(bigClus);
				this.grid_list.put(dg, cv);
			}
		}
		//System.out.println("Density grids assigned to cluster "+bigClus+".");
		
		// Merge the GridCluster objects representing each cluster
		GridCluster bGC = this.cluster_list.get(bigClus);
		bGC.absorbCluster(this.cluster_list.get(smallClus));
		this.cluster_list.set(bigClus, bGC);
		this.cluster_list.remove(smallClus);
		//System.out.println("Cluster "+smallClus+" removed from list.");
		cleanClusters();
	}
1028700
def _group_adjacency(self, clusters, adj_list, counts):
        ''' '''

        groups = []

        for cluster in clusters:
            if len(cluster) == 1:
                groups.append(list(cluster))

            else:
                observed = set()

                lead_umis = self._get_best_min_account(cluster,
                                                       adj_list, counts)
                observed.update(lead_umis)

                for lead_umi in lead_umis:
                    connected_nodes = set(adj_list[lead_umi])
                    groups.append([lead_umi] +
                                  list(connected_nodes - observed))
                    observed.update(connected_nodes)

        return groups
352691
protected void bicoCFUpdate(ClusteringTreeNode x) {
		// Starts with the global root node as the current root node
		ClusteringTreeNode r = this.root;
		int i = 1;
		while (true) {
			ClusteringTreeNode y = r.nearestChild(x.getCenter());
			// Checks if the node can not be merged to the current level
			if (r.hasNoChildren()
					|| y == null
					|| Metric.distanceSquared(x.getCenter(), y.getCenter()) > calcRSquared(i)) {
				// Adds the node to the current root node
				x.setThreshold(calcR(i));
				r.addChild(x);
				this.rootCount++;
				break;
			} else {
				// Checks if the node can be merged to the nearest node without
				// exceeding the global threshold
				if (y.getClusteringFeature().calcKMeansCosts(y.getCenter(),
						x.getClusteringFeature()) <= this.T) {
					// Merges the ClusteringFeature of the node to the
					// ClusteringFeature of the nearest node
					y.getClusteringFeature().merge(x.getClusteringFeature());
					break;
				} else {
					// Navigates one level down in the tree
					r = y;
					i++;
				}
			}
		}
	}
122375
void mergeClusters_(int cluster_1, int cluster2) {
		// dbg_check_cluster_(cluster_1);
		// dbg_check_cluster_(cluster2);
		int eventQnode = getClusterEventQNode(cluster2);
		if (eventQnode != -1) {
			m_event_q.deleteNode(eventQnode, -1);
			setClusterEventQNode_(cluster2, -1);
		}

		int firstEdge1 = getClusterFirstEdge(cluster_1);
		int firstEdge2 = getClusterFirstEdge(cluster2);

		if (firstEdge2 != -1) {// scope
			int edge2 = firstEdge2;
			int lastEdge = firstEdge2;
			boolean bForceContinue = false;
			// Delete edges that connect cluster_1 and cluster2.
			do {
				// dbg_check_edge_(edge2);
				bForceContinue = false;
				// assert(!StridedIndexTypeCollection.isValidElement(getEdgeSweepNode(edge2)));
				int end = getEdgeEnd(edge2, cluster2);
				int nextEdge2 = getNextEdgeEx(edge2, end);
				if (getEdgeCluster(edge2, (end + 1) & 1) == cluster_1) { // Snapping
																			// clusters
																			// that
																			// are
																			// connected
																			// with
																			// an
																			// edge
																			// Delete
																			// the
																			// edge.
					disconnectEdge_(edge2);
					int edgeOrigins2 = getEdgeOriginVertices(edge2);
					m_edge_vertices.deleteList(edgeOrigins2);
					deleteEdge_(edge2);
					if (edge2 == nextEdge2) {// deleted last edge connecting to
												// the cluster2 (all connections
												// are degenerate)
						firstEdge2 = -1;
						break;
					}
					if (firstEdge2 == edge2) {
						firstEdge2 = getClusterFirstEdge(cluster2);
						lastEdge = nextEdge2;
						bForceContinue = true;
					}
				} else {
					assert (edge2 != getClusterFirstEdge(cluster_1));
				}
				edge2 = nextEdge2;
			} while (edge2 != lastEdge || bForceContinue);

			if (firstEdge2 != -1) {
				// set the cluster to the edge ends
				do {
					int end = getEdgeEnd(edge2, cluster2);
					int nextEdge2 = getNextEdgeEx(edge2, end);
					assert (edge2 != getClusterFirstEdge(cluster_1));
					setEdgeCluster_(edge2, end, cluster_1);
					edge2 = nextEdge2;
				} while (edge2 != lastEdge);

				firstEdge1 = getClusterFirstEdge(cluster_1);
				if (firstEdge1 != -1) {
					int next1 = getNextEdge(firstEdge1, cluster_1);
					int next2 = getNextEdge(firstEdge2, cluster_1);
					if (next1 == firstEdge1) {
						setClusterFirstEdge_(cluster_1, firstEdge2);
						addEdgeToClusterImpl_(firstEdge1, cluster_1);
						setClusterFirstEdge_(cluster_1, firstEdge1);
					} else if (next2 == firstEdge2) {
						addEdgeToClusterImpl_(firstEdge2, cluster_1);
					}

					setNextEdge_(firstEdge2, cluster_1, next1);
					setPrevEdge_(next1, cluster_1, firstEdge2);
					setNextEdge_(firstEdge1, cluster_1, next2);
					setPrevEdge_(next2, cluster_1, firstEdge1);
				} else {
					setClusterFirstEdge_(cluster_1, firstEdge2);
				}
			}
		}

		int vertices1 = getClusterVertices(cluster_1);
		int vertices2 = getClusterVertices(cluster2);
		// Update cluster info on vertices.
		for (int vh = m_cluster_vertices.getFirst(vertices2); vh != -1; vh = m_cluster_vertices
				.getNext(vh)) {
			int v = m_cluster_vertices.getElement(vh);
			m_shape.setUserIndex(v, m_vertex_cluster_index, cluster_1);
		}
		m_cluster_vertices.concatenateLists(vertices1, vertices2);
		deleteCluster_(cluster2);
		// dbg_check_cluster_(cluster_1);
	}
724162
public void process( FastQueue<TldRegion> regions , FastQueue<TldRegion> output ) {

		final int N = regions.size;

		// set all connections to be a local maximum initially
		conn.growArray(N);
		for( int i = 0; i < N; i++ ) {
			conn.data[i].reset();
		}

		// Create the graph of connected regions and mark which regions are local maximums
		for( int i = 0; i < N; i++ ) {
			TldRegion ra = regions.get(i);
			Connections ca = conn.data[i];

			for( int j = i+1; j < N; j++ ) {
				TldRegion rb = regions.get(j);
				Connections cb = conn.data[j];

				// see if they are connected
				double overlap = helper.computeOverlap(ra.rect,rb.rect);
				if( overlap < connectionThreshold ) {
					continue;
				}

				// connect the two and check for strict maximums
				ca.maximum &= ra.confidence > rb.confidence;
				cb.maximum &= rb.confidence > ra.confidence;
				ra.connections++;
				rb.connections++;
			}
		}

		// Compute the output from local maximums.
		for( int i = 0; i < N; i++ ) {
			TldRegion ra = regions.get(i);
			Connections ca = conn.data[i];

			if( ca.maximum ) {
				TldRegion o = output.grow();
				o.connections = ra.connections;
				o.confidence = ra.confidence;
				o.rect.set(ra.rect);
			} else if( ra.connections == 0 ) {
				System.out.println("Not a maximum but has zero connections?");
			}
		}
	}
687463
def _split_cluster(c, pairs, n):
    """"""
    old = c[p[0]]
    new = c[p[1]]
    new_c = cluster(n)
    common = set(_get_seqs(old)).intersection(_get_seqs(new))
    for idl in old.loci2seq:
        in_common = list(set(common).intersection(old.loci2seq[idl]))
        if len(in_common) > 0:
            logger.debug("_split_cluster: in_common %s with pair 1" % (len(in_common)))
            new_c.add_id_member(in_common, idl)
            old.loci2seq[idl] = list(set(old.loci2seq[idl]) - set(common))
            logger.debug("_split_cluster: len old %s with pair 1" % (len(old.loci2seq)))
    for idl in new.loci2seq:
        in_common = list(set(common).intersection(new.loci2seq[idl]))
        if len(in_common) > 0:
            logger.debug("_split_cluster: in_common %s with pair 2" % (len(in_common)))
            new_c.add_id_member(in_common, idl)
            new.loci2seq[idl] = list(set(new.loci2seq[idl]) - set(common))
            logger.debug("_split_cluster: len old %s with pair 2" % (len(new.loci2seq)))
    old.update()
    new.update()
    old.loci2seq = {k: v for k, v in old.loci2seq.iteritems() if len(v) > 0}
    new.loci2seq = {k: v for k, v in new.loci2seq.iteritems() if len(v) > 0}
    c[n] = new
    c[p[0]] = old
    c[p[1]] = new
    return c
7072
def connect(polylines, max_dist=10):
    
    ll = len(polylines)
    remove = []
    for n in range(ll - 1, -1, -1):
        c = polylines[n]
        if len(c) > 1:
            for d0, p0 in enumerate((c[0, 0], c[-1, 0])):
                for m in range(len(polylines) - 1, -1, -1):
                    # combine all x all polylines
                    if n == m:
                        continue
                    cc = polylines[m]

                    for d1, p1 in enumerate((cc[0, 0], cc[-1, 0])):
                        # for end points of other polylines:
                        # measure closest distance for current polyline
                        ndist = norm(p0 - p1)
                        if ndist < max_dist:
                            is_same, c = _connect(c, cc, d0, d1)
                            if is_same:
                                if m not in remove:
                                    remove.append(m)
                                polylines[n] = c
                                break
    # remove those which are already in connected to other polyline:
    remove.sort()
    remove.reverse()
    for r in remove:
        polylines.pop(r)
648384
void connect(List<EllipseInfo> ellipses) {
		for (int i = 0; i < ellipses.size(); i++) {
			EllipseInfo info1 = ellipses.get(i);
			EllipseRotated_F64 e1 = info1.ellipse;
			Node node1 = nodes.get(i);

			// Only search the maximum of the major axis times two
			// add a fudge factor.  won't ever be perfect
			double maxDistance = e1.a * maxDistanceToMajorAxisRatio;
			maxDistance *= maxDistance;

			searchResults.reset();
			search.findNearest( ellipses.get(i), maxDistance, Integer.MAX_VALUE, searchResults );

			// if this node already has a cluster look it up, otherwise create a new one
			List<Node> cluster1;

			if( node1.cluster == -1 ) {
				node1.cluster = clusters.size;
				cluster1 = clusters.grow();
				cluster1.clear();
				cluster1.add( node1 );
			} else {
				cluster1 = clusters.get( node1.cluster );
			}

			double edge1 = info1.averageOutside-info1.averageInside;

			// only accept ellipses which have a similar size
			for (int j = 0; j < searchResults.size(); j++) {
				NnData<EllipseInfo> d = searchResults.get(j);
				EllipseInfo info2 = ellipses.get(d.index);
				EllipseRotated_F64 e2 = info2.ellipse;
				if( e2 == e1 )
					continue;

				// see of they are already connected
				if( node1.connections.indexOf(d.index) != -1 ) {
					continue;
				}

				// test the appearance of the ellipses edge
				double edge2 = info2.averageOutside-info2.averageInside;
				double intensityRatio = Math.abs(edge1-edge2)/Math.max(edge1,edge2);

				if( intensityRatio > edgeIntensitySimilarityTolerance)
					continue;

				// the initial search was based on size of major axis.  Now prune and take in account the distance
				// from the minor axis
				if( axisAdjustedDistanceSq(e1,e2) > maxDistance ) {
					continue;
				}

				// TODO take in in account how similar their orientation is, but less important when they are circular
				//      somehow work into aspect ratio test?

				// smallest shape divided by largest shape
				double ratioA = e1.a > e2.a ? e2.a / e1.a : e1.a / e2.a;
				double ratioB = e1.b > e2.b ? e2.b / e1.b : e1.b / e2.b;

				if( ratioA < sizeSimilarityTolerance && ratioB < sizeSimilarityTolerance ) {
					continue;
				}

				// axis ratio similarity check
				double ratioC = (e1.a*e2.b)/(e1.b*e2.a);
				if( ratioC > 1 ) ratioC = 1.0/ratioC;

				if( ratioC < ratioSimilarityTolerance ) {
					continue;
				}

				// Apply rule which combines two features
				if( intensityRatio + (1-ratioC) >
						(edgeIntensitySimilarityTolerance/1.5+(1-ratioSimilarityTolerance)) )
					continue;

				int indexNode2 = d.index;
				Node node2 = nodes.get(indexNode2);

				// node2 isn't in a cluster already.  Add it to this one
				if( node2.cluster == -1 ) {
					node2.cluster = node1.cluster;
					cluster1.add( node2 );
					node1.connections.add( indexNode2 );
					node2.connections.add( i );
				} else if( node2.cluster != node1.cluster ) {
					// Node2 is in a different cluster.  Merge the clusters
					joinClusters( node1.cluster , node2.cluster );
					node1.connections.add( indexNode2 );
					node2.connections.add( i );
				} else {
					node1.connections.add( indexNode2 );
					node2.connections.add( i );
				}
			}
		}
	}
205768
def initialize_connections(self):
        
        n, m = self.connections.visible_to_hidden.shape
        self.connections.visible_to_hidden = np.zeros((n, m))

        for i in range(n):
            random_vector = self._random.rand(m)
            # norm          = np.sqrt( np.sum(random_vector * random_vector) )
            self.connections.visible_to_hidden[i]  = random_vector
299763
def run
      return if _clusters.empty?
      warn "warning: running aggregation on many clusters (#{_clusters.size})" if _clusters.size > 100

      if DENSITY_BIAS_FACTOR
        @min_density, @max_density = _clusters.collect(&:density).minmax
      end

      # build the set of pairs (n²/2)
      pairs  = []
      source = _clusters.dup
      while left = source.pop
        source.each do |right| 
          pairs << _build_pair(left, right, _fence)
        end
      end

      # pop & merge
      while pairs.any?
        best_pair = pairs.min
        break if best_pair.distance > min_distance

        # remove the closest pair
        left, right = best_pair.values
        left_id  = left.id
        right_id = right.id

        # remove pairs containing one of the items
        pairs.delete_if { |p| p.has?(left) || p.has?(right) }

        # merge clusters
        left.merge(right)
        _clusters.delete_if { |c| c.id == right_id }
        _updated_clusters.remove right
        _dropped_clusters.add    right
        _updated_clusters.add    left

        # create new pairs
        _clusters.each do |cluster|
          next if cluster.id == left_id
          pairs << _build_pair(left, cluster, _fence)
        end
      end
      nil
    end
780374
function cluster(k) {
                var Centroids = this.createCentroids(k);
                var LastDistances = Matrix$d.Zero(this.Observations.rows(), this.Observations.cols());
                var Distances = this.distanceFrom(Centroids);
                var Groups;

                while(!(LastDistances.eql(Distances))) {
                Groups = Distances.minColumnIndexes();
                LastDistances = Distances;

                var newCentroids = [];

                for(var i = 1; i <= Centroids.rows(); i++) {
                    var centroid = [];

                    for(var j = 1; j <= Centroids.cols(); j++) {
                    var sum = 0;
                    var count = 0;

                    for(var l = 1; l <= this.Observations.rows(); l++) {
                        if(Groups.e(l) == i) {
                        count++;
                        sum += this.Observations.e(l, j);
                        }
                    }

                    centroid.push(sum / count);
                    }

                    newCentroids.push(centroid);
                }

                Centroids = $M(newCentroids);
                Distances = this.distanceFrom(Centroids);
                }

                return Groups;
            }
1196084
private int getClusterBoundary(Relation<O> relation, List<? extends Cluster<MeanModel>> clusters) {
    int totalSize = relation.size();
    int clusterBoundary = clusters.size() - 1;
    int cumulativeSize = 0;
    for(int i = 0; i < clusters.size() - 1; i++) {
      cumulativeSize += clusters.get(i).size();

      // Given majority covered by large cluster
      if(cumulativeSize >= totalSize * alpha) {
        clusterBoundary = i;
        break;
      }

      // Relative difference in cluster size between two consecutive clusters
      if(clusters.get(i).size() / (double) clusters.get(i + 1).size() >= beta) {
        clusterBoundary = i;
        break;
      }
    }
    return clusterBoundary;
  }
1272577
def skip_connections_distance(list_a, list_b):
    """"""
    distance_matrix = np.zeros((len(list_a), len(list_b)))
    for i, a in enumerate(list_a):
        for j, b in enumerate(list_b):
            distance_matrix[i][j] = skip_connection_distance(a, b)
    return distance_matrix[linear_sum_assignment(distance_matrix)].sum() + abs(
        len(list_a) - len(list_b)
    )
1042502
private void checkClusters(Relation<V> relation, Object2ObjectMap<long[], List<ArrayModifiableDBIDs>> clustersMap) {
    final int dimensionality = RelationUtil.dimensionality(relation);
    // check if there are clusters < minpts
    // and add them to not assigned
    List<Pair<long[], ArrayModifiableDBIDs>> notAssigned = new ArrayList<>();
    Object2ObjectMap<long[], List<ArrayModifiableDBIDs>> newClustersMap = new Object2ObjectOpenCustomHashMap<>(BitsUtil.FASTUTIL_HASH_STRATEGY);
    Pair<long[], ArrayModifiableDBIDs> noise = new Pair<>(BitsUtil.zero(dimensionality), DBIDUtil.newArray());
    for(long[] pv : clustersMap.keySet()) {
      // noise
      if(BitsUtil.cardinality(pv) == 0) {
        List<ArrayModifiableDBIDs> parallelClusters = clustersMap.get(pv);
        for(ArrayModifiableDBIDs c : parallelClusters) {
          noise.second.addDBIDs(c);
        }
      }
      // clusters
      else {
        List<ArrayModifiableDBIDs> parallelClusters = clustersMap.get(pv);
        List<ArrayModifiableDBIDs> newParallelClusters = new ArrayList<>(parallelClusters.size());
        for(ArrayModifiableDBIDs c : parallelClusters) {
          if(!BitsUtil.isZero(pv) && c.size() < mu) {
            notAssigned.add(new Pair<>(pv, c));
          }
          else {
            newParallelClusters.add(c);
          }
        }
        newClustersMap.put(pv, newParallelClusters);
      }
    }

    clustersMap.clear();
    clustersMap.putAll(newClustersMap);

    for(Pair<long[], ArrayModifiableDBIDs> c : notAssigned) {
      if(c.second.isEmpty()) {
        continue;
      }
      Pair<long[], ArrayModifiableDBIDs> parent = findParent(relation, c, clustersMap);
      (parent != null ? parent : noise).second.addDBIDs(c.second);
    }

    List<ArrayModifiableDBIDs> noiseList = new ArrayList<>(1);
    noiseList.add(noise.second);
    clustersMap.put(noise.first, noiseList);
  }
1108092
def _rebalance_partition_replicas(
            self,
            partition,
            max_movement_count=None,
            max_movement_size=None,
    ):
        """"""
        # Separate replication-groups into under and over replicated
        total = partition.replication_factor
        over_replicated_rgs, under_replicated_rgs = separate_groups(
            list(self.cluster_topology.rgs.values()),
            lambda g: g.count_replica(partition),
            total,
        )

        # Move replicas from over-replicated to under-replicated groups
        movement_count = 0
        movement_size = 0
        while (
            under_replicated_rgs and over_replicated_rgs
        ) and (
            max_movement_size is None or
            movement_size + partition.size <= max_movement_size
        ) and (
            max_movement_count is None or
            movement_count < max_movement_count
        ):
            # Decide source and destination group
            rg_source = self._elect_source_replication_group(
                over_replicated_rgs,
                partition,
            )
            rg_destination = self._elect_dest_replication_group(
                rg_source.count_replica(partition),
                under_replicated_rgs,
                partition,
            )
            if rg_source and rg_destination:
                # Actual movement of partition
                self.log.debug(
                    'Moving partition {p_name} from replication-group '
                    '{rg_source} to replication-group {rg_dest}'.format(
                        p_name=partition.name,
                        rg_source=rg_source.id,
                        rg_dest=rg_destination.id,
                    ),
                )
                rg_source.move_partition(rg_destination, partition)
                movement_count += 1
                movement_size += partition.size
            else:
                # Groups balanced or cannot be balanced further
                break
            # Re-compute under and over-replicated replication-groups
            over_replicated_rgs, under_replicated_rgs = separate_groups(
                list(self.cluster_topology.rgs.values()),
                lambda g: g.count_replica(partition),
                total,
            )
        return movement_count, movement_size