for every node in a revision tree computes its distance from the closest leaf
764150
function computeHeight(revs) {
  var height = {};
  var edges = [];
  pouchdbMerge.traverseRevTree(revs, function (isLeaf, pos, id, prnt) {
    var rev = pos + "-" + id;
    if (isLeaf) {
      height[rev] = 0;
    }
    if (prnt !== undefined) {
      edges.push({from: prnt, to: rev});
    }
    return rev;
  });

  edges.reverse();
  edges.forEach(function (edge) {
    if (height[edge.from] === undefined) {
      height[edge.from] = 1 + height[edge.to];
    } else {
      height[edge.from] = Math.min(height[edge.from], 1 + height[edge.to]);
    }
  });
  return height;
}
52268
def update_sibling_distance(self, sibling_distance, dest, topic):
        """"""
        for source in six.iterkeys(sibling_distance[dest]):
            sibling_distance[dest][source][topic] = \
                dest.count_partitions(topic) - \
                source.count_partitions(topic)
        return sibling_distance
1310279
double treeNodeCostOfPoint(treeNode node, Point p){
		if(p.weight == 0.0){
			return 0.0;
		}

		//stores the distance between centre and p
		double distance = 0.0;
		
		//loop counter variable
		int l;

		for(l=0;l<p.dimension;l++){
			//centroid coordinate of the point
			double centroidCoordinatePoint;
			if(p.weight != 0.0){
				centroidCoordinatePoint = p.coordinates[l] / p.weight;
			} else {
				centroidCoordinatePoint = p.coordinates[l];
			}
			//centroid coordinate of the centre
			double centroidCoordinateCentre;
			if(node.centre.weight != 0.0){
				centroidCoordinateCentre = node.centre.coordinates[l] / node.centre.weight;
			} else {
				centroidCoordinateCentre = node.centre.coordinates[l];
			}
			distance += (centroidCoordinatePoint-centroidCoordinateCentre) * 
					(centroidCoordinatePoint-centroidCoordinateCentre) ;
					
		}
		return distance * p.weight;
	}
940611
def nearest_neighbor(x, tSet):
    
    assert isinstance(x, tuple) and isinstance(tSet, dict)
    current_key = ()
    min_d = float('inf')
    for key in tSet:
        d = distance(x, key)
        if d < min_d:
            min_d = d
            current_key = key
    return tSet[current_key]
193385
private void checkBestDistance(KdTree.Node node, FastQueue<KdTreeResult> neighbors) {
		double distSq = distance.distance((P)node.point,target);
		// <= because multiple nodes could be at the bestDistanceSq
		if( distSq <= mostDistantNeighborSq) {
			if( neighbors.size() < searchN ) {
				// the list of nearest neighbors isn't full yet so it doesn't know what the distance will be
				// so just keep on adding them to the list until it is full
				KdTreeResult r = neighbors.grow();
				r.distance = distSq;
				r.node = node;
				if( neighbors.size() == searchN ) {
					// find the most distant
					mostDistantNeighborSq = -1;
					for( int i = 0; i < searchN; i++ ) {
						r = neighbors.get(i);
						if( r.distance > mostDistantNeighborSq ) {
							mostDistantNeighborSq = r.distance;
							mostDistantNeighborIndex = i;
						}
					}
				}
			} else {
				for( int i = 0; i < searchN; i++ ) {
					KdTreeResult r = neighbors.get(i);
					if( r.distance > mostDistantNeighborSq ) {
						throw new RuntimeException("Most distant isn't the most distant");
					}
				}

				// Write over the most distant neighbor since we known this node must be closer
				// and update the maximum distance
				KdTreeResult r = neighbors.get(mostDistantNeighborIndex);
				r.node = node;
				r.distance = distSq;

				// If there are multiple points then there can be more than one point with the value of
				// 'bestDistanceSq', which is why two searches are required
				mostDistantNeighborSq = -1;
				for( int i = 0; i < searchN; i++ ) {
					r = neighbors.get(i);
					if( r.distance > mostDistantNeighborSq ) {
						mostDistantNeighborSq = r.distance;
						mostDistantNeighborIndex = i;
					}
				}
			}
		}
	}
243566
@Override
	protected void checkBestDistance(KdTree.Node node, P target) {
		double distanceSq = distance.distance((P)node.point,target);
		if( distanceSq <= bestDistanceSq ) {
			if( bestNode == null || distanceSq < bestDistanceSq ) {
				bestDistanceSq = distanceSq;
				bestNode = node;
			}
		}
	}
997108
def k_closest(points, k, origin=(0, 0)):
    # Time: O(k+(n-k)logk)
    # Space: O(k)
    
    heap = [(-distance(p, origin), p) for p in points[:k]]
    heapify(heap)

    """
    For every point p in points[k:],
    check if p is smaller than the root of the max heap;
    if it is, add p to heap and remove root. Reheapify.
    """
    for p in points[k:]:
        d = distance(p, origin)

        heappushpop(heap, (-d, p))  # heappushpop does conditional check
        """Same as:
            if d < -heap[0][0]:
                heappush(heap, (-d,p))
                heappop(heap)

        Note: heappushpop is more efficient than separate push and pop calls.
        Each heappushpop call takes O(logk) time.
        """

    return [p for nd, p in heap]
49536
private TreeNode split(TreeNode node, ClusteringFeature newchild) {
    final int capacity = node.children.length;
    assert (node.children[capacity - 1] != null) : "Node to split is not empty!";
    TreeNode newn = new TreeNode(node.getDimensionality(), capacity);
    final int size = capacity + 1;
    // Find farthest pair:
    int m1 = -1, m2 = -1;
    double maxd = Double.NEGATIVE_INFINITY;
    double[][] dists = new double[size][size];
    for(int i = 0; i < capacity; i++) {
      ClusteringFeature ci = node.children[i];
      for(int j = i + 1; j < capacity; j++) {
        double d = dists[i][j] = dists[j][i] = distance.squaredDistance(ci, node.children[j]);
        if(d > maxd) {
          maxd = d;
          m1 = i;
          m2 = j;
        }
      }
      double d = dists[i][capacity] = dists[capacity][i] = distance.squaredDistance(ci, newchild);
      if(d > maxd) {
        maxd = d;
        m1 = i;
        m2 = capacity;
      }
    }
    // Reset node statistics:
    node.resetStatistics();
    newn.resetStatistics();
    // Redistribute entries:
    int si = 0, sj = 0; // Output positions.
    double[] d1s = dists[m1], d2s = dists[m2];
    for(int i = 0; i < capacity; i++) {
      double d1 = d1s[i], d2 = d2s[i];
      if(i == m1 || i != m2 && (d1 < d2 || (d1 == d2 && si <= sj))) {
        node.addToStatistics(node.children[si++] = node.children[i]);
      }
      else {
        newn.addToStatistics(newn.children[sj++] = node.children[i]);
      }
    }
    {
      double d1 = d1s[capacity], d2 = d2s[capacity];
      if(capacity != m2 && (d1 < d2 || (d1 == d2 && si <= sj))) {
        node.addToStatistics(node.children[si++] = newchild);
      }
      else {
        newn.addToStatistics(newn.children[sj++] = newchild);
      }
    }
    for(int j = si; j < capacity; j++) {
      node.children[j] = null;
    }
    for(int j = sj; j < capacity; j++) {
      assert (newn.children[j] == null);
    }
    return newn;
  }
930532
protected static NodeInfo findClosestEdge( NodeInfo n , Point2D_F64 p ) {
		double bestDistance = Double.MAX_VALUE;
		NodeInfo best = null;

		for (int i = 0; i < n.edges.size(); i++) {
			Edge e = n.edges.get(i);
			if( e.target.marked )
				continue;

			double d = e.target.ellipse.center.distance2(p);
			if( d < bestDistance ) {
				bestDistance = d;
				best = e.target;
			}
		}

		return best;
	}
1077937
def compute_node_positions(self):
        
        xs = []
        ys = []
        self.locs = dict()

        for node in self.nodes:
            x = self.graph.node[node][self.node_lon]
            y = self.graph.node[node][self.node_lat]
            xs.append(x)
            ys.append(y)
            self.locs[node] = (x, y)

        self.node_coords = {"x": xs, "y": ys}
462256
def compute_node_positions(self):
        
        xs = [0] * len(self.nodes)
        ys = [0] * len(self.nodes)
        for i, _ in enumerate(self.nodes[1:], start=1):
            prev_r = self.node_sizes[i - 1] / 2
            curr_r = self.node_sizes[i] / 2
            xs[i] = xs[i - 1] + prev_r + curr_r

        self.node_coords = {"x": xs, "y": ys}
685209
function getCoefedDistance(box1, box2) {
            var xMin, xMax, yMin, yMax, xDist, yDist, dist, cx, cy;
            xMin = min(box1.left, box2.left);
            xMax = max(box1.right, box2.right);
            yMin = min(box1.top, box2.top);
            yMax = max(box1.bottom, box2.bottom);

            xDist = xMax - xMin - box1.width - box2.width;
            yDist = yMax - yMin - box1.height - box2.height;

            if (xDist < 0) dist = yDist;
            else if (yDist < 0) dist = xDist;
            else dist = sqrt(xDist * xDist + yDist * yDist);

            var node1 = box1.node;
            var node2 = box2.node;

            // sibling
            if (node1.parent == node2.parent) {
                dist /= 10;
            }
            // parent
            if (node2.parent == node1) {
                dist /= 5;
            }

            return dist;
        }
561103
function nearest(predicate, node) {
    while ((node = node.parent)) {
        if (predicate(node)) return node;
    }

    return undefined;
}
777484
def subtree_leaf_positions(subtree):
    """"""
    relative_leaf_positions = subtree.treepositions('leaves')
    subtree_root_pos = subtree.treeposition()
    absolute_leaf_positions = []
    for rel_leaf_pos in relative_leaf_positions:
        absolute_leaf_positions.append( subtree_root_pos + rel_leaf_pos)
    return absolute_leaf_positions
515320
function computeNodeBreadths() {
    var remainingNodes = nodes,
        nextNodes,
        x = 0;

    while (remainingNodes.length) {
      nextNodes = [];
      remainingNodes.forEach(function(node) {
        node.x = x;
        node.dx = nodeWidth;
        node.sourceLinks.forEach(function(link) {
          if (!link.causesCycle) {
            nextNodes.push(link.target);
          }
        });
      });
      remainingNodes = nextNodes;
      ++x;
    }

    //
    moveSinksRight(x);
    scaleNodeBreadths((size[0] - nodeWidth) / (x - 1));
  }
883429
def distance_function_match(l1, l2, thresh, dist_fn, norm_funcs=[]):
    """"""
    common = []
    # We will keep track of the global index in the source list as we
    # will successively reduce their sizes.
    l1 = list(enumerate(l1))
    l2 = list(enumerate(l2))

    # Use the distance function and threshold on hints given by normalization.
    # See _match_by_norm_func for implementation details.
    # Also wrap the list element function function to ignore the global list
    # index computed above.
    for norm_fn in norm_funcs:
        new_common, l1, l2 = _match_by_norm_func(
                l1, l2,
                lambda a: norm_fn(a[1]),
                lambda a1, a2: dist_fn(a1[1], a2[1]),
                thresh)
        # Keep only the global list index in the end result.
        common.extend((c1[0], c2[0]) for c1, c2 in new_common)

    # Take any remaining umatched entries and try to match them using the
    # Munkres algorithm.
    dist_matrix = [[dist_fn(e1, e2) for i2, e2 in l2] for i1, e1 in l1]

    # Call Munkres on connected components on the remaining bipartite graph.
    # An edge links an element from l1 with an element from l2 only if
    # the distance between the elements is less (or equal) than the theshold.
    components = BipartiteConnectedComponents()
    for l1_i in range(len(l1)):
        for l2_i in range(len(l2)):
            if dist_matrix[l1_i][l2_i] > thresh:
                continue
            components.add_edge(l1_i, l2_i)

    for l1_indices, l2_indices in components.get_connected_components():
        # Build a partial distance matrix for each connected component.
        part_l1 = [l1[i] for i in l1_indices]
        part_l2 = [l2[i] for i in l2_indices]

        part_dist_matrix = [[dist_matrix[l1_i][l2_i] for l2_i in l2_indices]
                            for l1_i in l1_indices]
        part_cmn = _match_munkres(part_l1, part_l2, part_dist_matrix, thresh)

        common.extend((c1[0], c2[0]) for c1, c2 in part_cmn)

    return common
39478
public ClusteringTreeNode nearestChild(double[] pointA) {
		assert (this.center.length == pointA.length);
		double minDistance = Double.POSITIVE_INFINITY;
		ClusteringTreeNode min = null;
		for (ClusteringTreeNode node : this.getChildren()) {
			double d = Metric.distance(pointA, node.getCenter());
			if (d < minDistance) {
				minDistance = d;
				min = node;
			}
		}
		return min;
	}