/*
Finds a maximal tree of tight edges and returns the number of nodes in the
tree.
435820
function tightTree(t, g) {
  function dfs(v) {
    _.forEach(g.nodeEdges(v), function(e) {
      var edgeV = e.v,
        w = (v === edgeV) ? e.w : edgeV;
      if (!t.hasNode(w) && !slack(g, e)) {
        t.setNode(w, {});
        t.setEdge(v, w, {});
        dfs(w);
      }
    });
  }

  _.forEach(t.nodes(), dfs);
  return t.nodeCount();
}
749602
final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
            if (k != null) {
                TreeNode<K,V> p = this;
                do {
                    int ph, dir; K pk; TreeNode<K,V> q;
                    TreeNode<K,V> pl = p.left, pr = p.right;
                    if ((ph = p.hash) > h)
                        p = pl;
                    else if (ph < h)
                        p = pr;
                    else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                        return p;
                    else if (pl == null)
                        p = pr;
                    else if (pr == null)
                        p = pl;
                    else if ((kc != null ||
                              (kc = comparableClassFor(k)) != null) &&
                             (dir = compareComparables(kc, k, pk)) != 0)
                        p = (dir < 0) ? pl : pr;
                    else if ((q = pr.findTreeNode(h, k, kc)) != null)
                        return q;
                    else
                        p = pl;
                } while (p != null);
            }
            return null;
        }
639550
final TreeMapEntry<K,V> getLastEntry() {
        TreeMapEntry<K,V> p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;
    }
258261
private Node findBestLeafNode(ClusKernel newPoint) {
    	double minDist = Double.MAX_VALUE;
    	Node bestFit = null;
    	for (Node e: collectLeafNodes(root)){
    		if (newPoint.calcDistance(e.nearestEntry(newPoint).getData())<minDist){
    			bestFit = e;
    			minDist = newPoint.calcDistance(e.nearestEntry(newPoint).getData());
    		}
    	}
    	if (bestFit!=null)
    		return bestFit;
    	else
    		return root;
	}
584827
def find_minimum_spanning_forest_as_subgraphs(graph):
    """"""
    forest = find_minimum_spanning_forest(graph)
    list_of_subgraphs = [get_subgraph_from_edge_list(graph, edge_list) for edge_list in forest]

    return list_of_subgraphs
157619
public void getMaxBranching(CompleteGraph graph, int root,
                                int[] invertedMaxBranching) {
        // Number of nodes.
        int numNodes = graph.getNumberOfNodes();

        // Branching.
        SparseGraph maxBranching = new SparseGraph();

        /*
         * Weighted edges used to allow weight modification and avoid any impact
         * in the original graph.
         */
        SimpleWeightedEdge[][] edges = new SimpleWeightedEdge[numNodes][numNodes];

        // Disjoint sets for the strongly connected components (SCC).
        DisjointSets sPartition = new DisjointSets(numNodes);
        // Disjoint sets for the weakly connected components (WCC).
        DisjointSets wPartition = new DisjointSets(numNodes);

        /*
         * Priority queues for each strongly connected component. In the
         * beginning, each SCC is composed by exactly one node.
         */
        ArrayList<PriorityQueue<SimpleWeightedEdge>> incomingEdges = new ArrayList<PriorityQueue<SimpleWeightedEdge>>(
                                                                                                                      numNodes);

        // Unique incoming edges for each SCC. Initially, no SCC has such edge.
        SimpleWeightedEdge[] enter = new SimpleWeightedEdge[numNodes];

        /*
         * List of root components, i.e., SCCs that have no incoming edges
         * (enter[scc] == null). In the beginning, every SCC is a root
         * component.
         */
        LinkedList<Integer> rootComponents = new LinkedList<Integer>();

        // Root node of each root component.
        int[] min = new int[numNodes];

        for (int node = 0; node < numNodes; ++node) {

            // Every SCC is a root component.
            rootComponents.add(node);

            /*
             * The head of its root component is its only node. This array is
             * called min in Tarjan's paper.
             */
            min[node] = node;

            // Create a priority queue for each SCC.
            PriorityQueue<SimpleWeightedEdge> sccPriorityQueue = new PriorityQueue<SimpleWeightedEdge>();
            incomingEdges.add(sccPriorityQueue);

            // No incoming edge is considered (nor created) for the root node.
            if (node != root) {
                /*
                 * Create and add all incoming edges of <code>node</code> to its
                 * SCC priority queue.
                 */
                for (int from = 0; from < numNodes; ++from) {
                    if (from == node)
                        // Skip autocycle edges.
                        continue;
                    // Create an weighted edge and add it to the priority queue.
                    edges[from][node] = new SimpleWeightedEdge(from, node,
                                                               graph.getEdgeWeight(from, node));
                    sccPriorityQueue.add(edges[from][node]);
                }
            }
        }

        // Root component with no available incoming edges.
        LinkedList<Integer> doneRootComponents = new LinkedList<Integer>();

        while (!rootComponents.isEmpty()) {
            // Get some arbitrary root component.
            int sccTo = rootComponents.pop();
            // Maximum edge entering the root component 'sccTo'.
            SimpleWeightedEdge maxInEdge = incomingEdges.get(sccTo).poll();

            if (maxInEdge == null) {
                // No edge left to consider in this component.
                doneRootComponents.add(sccTo);
                continue;
            }

            // SCC component of edge 'e' from node: e = (from, to).
            int sccFrom = sPartition.find(maxInEdge.from);

            if (sccFrom == sccTo) {
                // Skip, for now, this component.
                rootComponents.add(sccTo);
                continue;
            }

            // Include the selected edge in the current branching.
            maxBranching.addEdge(maxInEdge.from, maxInEdge.to);

            // SCC component of edge 'e' from node, where e = (from, to).
            int wssFrom = wPartition.find(maxInEdge.from);
            // SCC component of edge 'e' to node, where e = (from, to).
            int wssTo = wPartition.find(maxInEdge.to);

            // Edge connects two weakly connected components.
            if (wssFrom != wssTo) {
                wPartition.union(wssFrom, wssTo);
                enter[sccTo] = maxInEdge;
                continue;
            }

            /*
             * Edge is within the same WCC, thus it inclusion will create a new
             * SCC by uniting some old SCCs (the ones on the path from e.to to
             * e.from).
             */
            double minEdgeWeight = Double.POSITIVE_INFINITY;
            int minScc = -1;
            SimpleWeightedEdge tmpEdge = maxInEdge;
            while (tmpEdge != null) {
                if (tmpEdge.weight < minEdgeWeight) {
                    minEdgeWeight = tmpEdge.weight;
                    minScc = sPartition.find(tmpEdge.to);
                }

                tmpEdge = enter[sPartition.find(tmpEdge.from)];
            }

            // Increment incoming edges weight.
            double inc = minEdgeWeight - maxInEdge.weight;
            for (SimpleWeightedEdge e : incomingEdges.get(sccTo))
                e.weight += inc;

            // Set the head of the current SCC.
            min[sccTo] = min[minScc];

            // Include all used SCCs in the current SCC.
            tmpEdge = enter[sccFrom];
            while (tmpEdge != null) {
                /*
                 * Increment incoming edges weight and include them in the
                 * current SCC priority queue.
                 */
                int tmpSccTo = sPartition.find(tmpEdge.to);
                inc = minEdgeWeight - tmpEdge.weight;
                for (SimpleWeightedEdge e : incomingEdges.get(tmpSccTo)) {
                    e.weight += inc;
                    incomingEdges.get(sccTo).add(e);
                }
                // Remove the priority queue of this SCC.
                incomingEdges.set(tmpSccTo, null);
                sPartition.union(sccTo, tmpSccTo);

                // Next edge.
                tmpEdge = enter[sPartition.find(tmpEdge.from)];
            }

            // Include the new SCC to be considered in the future.
            rootComponents.add(sccTo);
        }

        // Invert the maximum branching.
        boolean[] visited = new boolean[numNodes];
        for (int scc : doneRootComponents)
            invertMaximumBranching(min[scc], maxBranching, visited,
                                   invertedMaxBranching);
    }

    /**
     * Walk through the given branching from <code>node</code> and store the
     * inverted branching in <code>invertedMaxBranching</code>.
     * 
     * In fact, the given branching can include cycles. But it is only necessary
     * to disconsider the last edges of each cycle to get the real branching.
     * Thus, we use the array <code>visited</code>.
     * 
     * @param node
     * @param branching
     * @param visited
     * @param invertedMaxBranching
     */
    private void invertMaximumBranching(int node, SparseGraph branching,
                                        boolean[] visited, int[] invertedMaxBranching) {
        visited[node] = true;
        Set<Integer> toNodes = branching.getOutEdges(node);
        if (toNodes == null)
            return;
        for (int to : toNodes) {
            if (visited[to])
                continue;
            invertedMaxBranching[to] = node;
            invertMaximumBranching(to, branching, visited, invertedMaxBranching);
        }
    }
1125011
private static int findNodesToRelocate(final int[] array, final int maximumLength) {
        int currentNode = array.length - 2;
        for (int currentDepth = 1; currentDepth < maximumLength - 1 && currentNode > 1; currentDepth++) {
            currentNode =  first(array, currentNode - 1, 0);
        }
        return currentNode;
    }
738625
function(tree, n, m) {
    return tree[n].fc < tree[m].fc ||
      (tree[n].fc == tree[m].fc && zip_depth[n] <= zip_depth[m]);
}
223242
private RedBlackTreeNode<Key, Value> max(RedBlackTreeNode<Key, Value> x) {
	// assert x != null;
	if (x.getRight() == null)
	    return x;
	else
	    return max(x.getRight());
    }
768097
private ClusteringFeature findLeaf(TreeNode node, NumberVector nv) {
    // Find closest child:
    ClusteringFeature[] cfs = node.children;
    assert (cfs[0] != null) : "Unexpected empty node!";

    // Find the best child:
    ClusteringFeature best = cfs[0];
    double bestd = distance.squaredDistance(nv, best);
    for(int i = 1; i < cfs.length; i++) {
      ClusteringFeature cf = cfs[i];
      if(cf == null) {
        break;
      }
      double d2 = distance.squaredDistance(nv, cf);
      if(d2 < bestd) {
        best = cf;
        bestd = d2;
      }
    }

    return (best instanceof TreeNode) ? findLeaf((TreeNode) best, nv) : best;
  }
751879
public static Weighted<Arborescence<Node>> getMaxArborescence(WeightedGraph graph, Node root) {
        // remove all edges incoming to `root`. resulting arborescence is then forced to be rooted at `root`.
        return getMaxArborescence(graph.filterEdges(not(DirectedEdge.hasDestination(root))));
    }
658439
def get_all_edge_nodes(self):
        """"""
        edge_nodes = set(e for es in self.edges for e in es)
        for edges in self.edges_rel.values():
            rel_nodes = set(e for es in edges for e in es)
            edge_nodes.update(rel_nodes)
        return edge_nodes
253600
function countSubTreeDepth(scope) {
          var thisLevelDepth = 0,
              childNodes = scope.childNodes(),
              childNode,
              childDepth,
              i;
          if (!childNodes || childNodes.length === 0) {
            return 0;
          }
          for (i = childNodes.length - 1; i >= 0 ; i--) {
            childNode = childNodes[i],
            childDepth = 1 + countSubTreeDepth(childNode);
            thisLevelDepth = Math.max(thisLevelDepth, childDepth);
          }
          return thisLevelDepth;
        }
1150367
function nodes(){
    var nodeSet = {};
    Object.keys(edges).forEach(function (u){
      nodeSet[u] = true;
      edges[u].forEach(function (v){
        nodeSet[v] = true;
      });
    });
    return Object.keys(nodeSet);
  }
721296
function rbushTreeItem(ring, edge) {

    var start = coord[ring][edge];
    var end = coord[ring][edge+1];

    if (start[0] < end[0]) {
      var minX = start[0], maxX = end[0];
    } else {
      var minX = end[0], maxX = start[0];
    };
    if (start[1] < end[1]) {
      var minY = start[1], maxY = end[1];
    } else {
      var minY = end[1], maxY = start[1];
    }
    return {minX: minX, minY: minY, maxX: maxX, maxY: maxY, ring: ring, edge: edge};
  }
1048639
def find_minimum_spanning_tree_as_subgraph(graph):
    """"""
    edge_list = find_minimum_spanning_tree(graph)
    subgraph = get_subgraph_from_edge_list(graph, edge_list)

    return subgraph
661208
function glb(tree, node, key, comp, low) {
    if (node === tree.z) {
        return low;
    }
    else if (comp(key, node.key) >= 0) {
        // The node key is a valid lower bound, but may not be the greatest.
        // Take the right link in search of larger keys.
        return maxNode(node, glb(tree, node.r, key, comp, low), comp);
    }
    else {
        // Take the left link in search of smaller keys.
        return glb(tree, node.l, key, comp, low);
    }
}