Try to rearrange the cut planes of the given node.
518905
private static <P extends GISPrimitive, N extends AbstractGISTreeSetNode<P, N>>
		N rearrangeTree(AbstractGISTreeSet<P, N> tree, N node, Rectangle2afp<?, ?, ?, ?, ?, ?> desiredBounds,
				GISTreeSetNodeFactory<P, N> builder) {
		// Search for the node that completely contains the desired area
		N topNode = node.getParentNode();
		while (topNode != null && isOutsideNodeBuildingBounds(topNode, desiredBounds)) {
			topNode = topNode.getParentNode();
		}

		final Rectangle2afp<?, ?, ?, ?, ?, ?> dr;
		if (topNode == null) {
			// Node node found, the entire tree should be rebuilt
			topNode = tree.getTree().getRoot();
			if (topNode == null) {
				throw new IllegalStateException();
			}
			dr = union(topNode, desiredBounds);
		} else {
			dr = getNormalizedNodeBuildingBounds(topNode, desiredBounds);
		}

		// Build a new subtree
		final N parent = topNode.getParentNode();
		final Iterator<P> dataIterator = new PrefixDataDepthFirstTreeIterator<>(topNode);
		final N newTopNode = builder.newNode(
				topNode.getZone(),
				dr.getMinX(), dr.getMinY(), dr.getWidth(), dr.getHeight());
		while (dataIterator.hasNext()) {
			if (!addInside(tree, newTopNode, dataIterator.next(), builder, false)) {
				throw new IllegalStateException();
			}
		}

		// Replace rearranged subtree by the new one
		if (parent != null) {
			parent.setChildAt(topNode.getZone().ordinal(), newTopNode);
			return parent;
		}
		tree.getTree().setRoot(newTopNode);
		return newTopNode;
	}
1353001
function recurse(data, depth, nodes) {
    var childs = children.call(hierarchy, data, depth),
        node = d3_layout_hierarchyInline ? data : {data: data};
    node.depth = depth;
    nodes.push(node);
    if (childs && (n = childs.length)) {
      var i = -1,
          n,
          c = node.children = [],
          v = 0,
          j = depth + 1,
          d;
      while (++i < n) {
        d = recurse(childs[i], j, nodes);
        d.parent = node;
        c.push(d);
        v += d.value;
      }
      if (sort) c.sort(sort);
      if (value) node.value = v;
    } else if (value) {
      node.value = +value.call(hierarchy, data, depth) || 0;
    }
    return node;
  }
259799
def move_edge_target(self, edge_id, node_a):
        """"""
        # Grab the edge
        edge = self.get_edge(edge_id)

        # Remove the edge from the original "target node"
        original_target_node_id = edge['vertices'][1]
        original_target_node = self.get_node(original_target_node_id)
        original_target_node['edges'].remove(edge_id)

        # Add the edge to the new target node
        new_target_node_id = node_a
        new_target_node = self.get_node(new_target_node_id)
        new_target_node['edges'].append(edge_id)

        # Alter the vertices on the edge
        edge['vertices'] = (edge['vertices'][0], node_a)
71014
def cut(self, a, b, bstjoin=False):
        
        if self.first_lookup[a] > self.last_lookup[b]:
            a, b = b, a

        o_a1 = self.first_lookup[a]
        o_a2 = self.last_lookup[a]
        o_b1 = self.first_lookup[b]
        o_b2 = self.last_lookup[b]
        assert o_a1 < o_b1
        # assert o_b1 < o_b2
        assert o_b2 < o_a2

        # splice out the inside contiguous range inplace
        inside, outside = self.tour_tree.splice_inplace(o_b1, o_b2 + 1)
        # Remove unneeded values
        outside = outside.splice_inplace(o_b1, o_a2 + 1)[1]

        other = EulerTourTree()
        other.tour_tree = inside
        # We can reuse these pointers without any modification
        other.first_lookup = self.first_lookup
        other.first_lookup = self.last_lookup
        # Should make an O(n) cleanup step at some point
        return other
935855
def merge_nodes(nodes, plane, page_stat, merge_indices):
    
    # Merge inner boxes to the best outer box
    # nodes.sort(key=Node.area)
    to_be_removed = set()
    for inner_idx in range(len(nodes)):
        inner = nodes[inner_idx]
        outers = []
        outers_indices = []
        for outer_idx in range(len(nodes)):
            outer = nodes[outer_idx]
            if outer is inner or outer in to_be_removed:
                continue
            if intersect(outer.bbox, inner.bbox):
                outers.append(outer)
                outers_indices.append(outer_idx)
        if not outers:
            continue
        # Best is defined as min L1 distance to outer center
        best_outer = min(
            outers, key=lambda outer: l1(center(outer.bbox), center(inner.bbox))
        )
        best_outer_idx = outers_indices[outers.index(best_outer)]
        to_be_removed.add(inner)
        best_outer.merge(inner)
        for cid_iter in range(len(merge_indices)):
            if merge_indices[cid_iter] == merge_indices[inner_idx]:
                merge_indices[cid_iter] = merge_indices[best_outer_idx]
    return nodes, merge_indices
835190
function recursivePartitioner(graph, node, call_stack){
	
	var curr_level = call_stack.length -1;
	var next_level = curr_level +1;

	ll("recur on " + node.id() + " at level " + curr_level);

	// Get children and see where there are.
	//var child_nodes = graph.get_child_nodes(node.id(), relation);
	var child_nodes = graph.get_child_nodes(node.id());
	ll(node.id() + " has " + (child_nodes.length || 'no' ) + ' child(ren)');
	for( var i = 0; i < child_nodes.length; i++ ){
	    var cnode = child_nodes[i];

	    ll("looking at " + cnode.id());

	    if( _cycle_p(cnode, call_stack) ){
		ll('no update to ' + cnode.id() + ': cycle');
	    }else{

		// Add edges--safe since they're definition-based and will
		// clobber if they're already in.
		var new_edge =
		    new bbop.layout.sugiyama.simple_edge(cnode.id(), node.id());
		edge_set[ new_edge.id() ] = new_edge;

		// Nodes we have to be a little more careful with since
		// they're what we're using for traversal.
		if( ! vertex_set[ cnode.id() ] ){
		
		    // Create new vertex and add to set.
		    _new_node_at(cnode, next_level);
		    
		    // Since it is a new node, we traverse it.
		    ll('cs (a): ' + call_stack);
		    var new_cs = bbop.core.clone(call_stack);
		    ll('cs (b): ' + new_cs);
		    new_cs.push(cnode.id());
		    ll('cs (c): ' + new_cs);
		    recursivePartitioner(graph, cnode, new_cs);
		    
		}else{
		    
		    ll('to update ' + cnode.id() + ' level to ' + next_level +
		       '; fsr: '+ first_seen_reference[ cnode.id() ] +
		       '; lsr: '+ last_seen_reference[ cnode.id() ]);
		    
		    // Otherwise, just update the levels that we've seen
		    // the child at--do not descend.
		    if( first_seen_reference[ cnode.id() ] > next_level ){
			first_seen_reference[ cnode.id() ] = next_level;
		    }
		    if( last_seen_reference[ cnode.id() ] < next_level ){
			last_seen_reference[ cnode.id() ] = next_level;
			// LSR is also the level that things will
			// appear at, so update.
			// I believe node and simple node IDs are the same?
			vertex_set[ cnode.id() ].level = next_level;

			// Recur if the LSR has change--we need to
			// update all of the nodes below.
			ll('cs (a): ' + call_stack);
			var new_cs = bbop.core.clone(call_stack);
			ll('cs (b): ' + new_cs);
			new_cs.push(cnode.id());
			ll('cs (c): ' + new_cs);
			recursivePartitioner(graph, cnode, new_cs);
		    }

		    // ll('updated ' + cnode.id() + ' level to ' + next_level +
		    //    '; fsr: '+ first_seen_reference[ cnode.id() ] +
		    //    '; lsr: '+ last_seen_reference[ cnode.id() ]);
		}
	    }
	}
    }
920479
protected void prunePlanAlternatives(List<PlanNode> plans) {
		if (plans.isEmpty()) {
			throw new CompilerException("No plan meeting the requirements could be created @ " + this + ". Most likely reason: Too restrictive plan hints.");
		}
		// shortcut for the simple case
		if (plans.size() == 1) {
			return;
		}
		
		// we can only compare plan candidates that made equal choices
		// at the branching points. for each choice at a branching point,
		// we need to keep the cheapest (wrt. interesting properties).
		// if we do not keep candidates for each branch choice, we might not
		// find branch compatible candidates when joining the branches back.
		
		// for pruning, we are quasi AFTER the node, so in the presence of
		// branches, we need form the per-branch-choice groups by the choice
		// they made at the latest un-joined branching node. Note that this is
		// different from the check for branch compatibility of candidates, as
		// this happens on the input sub-plans and hence BEFORE the node (therefore
		// it is relevant to find the latest (partially) joined branch point.
		
		if (this.openBranches == null || this.openBranches.isEmpty()) {
			prunePlanAlternativesWithCommonBranching(plans);
		} else {
			// partition the candidates into groups that made the same sub-plan candidate
			// choice at the latest unclosed branch point
			
			final OptimizerNode[] branchDeterminers = new OptimizerNode[this.openBranches.size()];
			
			for (int i = 0; i < branchDeterminers.length; i++) {
				branchDeterminers[i] = this.openBranches.get(this.openBranches.size() - 1 - i).getBranchingNode();
			}
			
			// this sorter sorts by the candidate choice at the branch point
			Comparator<PlanNode> sorter = new Comparator<PlanNode>() {
				
				@Override
				public int compare(PlanNode o1, PlanNode o2) {
					for (OptimizerNode branchDeterminer : branchDeterminers) {
						PlanNode n1 = o1.getCandidateAtBranchPoint(branchDeterminer);
						PlanNode n2 = o2.getCandidateAtBranchPoint(branchDeterminer);
						int hash1 = System.identityHashCode(n1);
						int hash2 = System.identityHashCode(n2);

						if (hash1 != hash2) {
							return hash1 - hash2;
						}
					}
					return 0;
				}
			};
			Collections.sort(plans, sorter);
			
			List<PlanNode> result = new ArrayList<PlanNode>();
			List<PlanNode> turn = new ArrayList<PlanNode>();
			
			final PlanNode[] determinerChoice = new PlanNode[branchDeterminers.length];

			while (!plans.isEmpty()) {
				// take one as the determiner
				turn.clear();
				PlanNode determiner = plans.remove(plans.size() - 1);
				turn.add(determiner);
				
				for (int i = 0; i < determinerChoice.length; i++) {
					determinerChoice[i] = determiner.getCandidateAtBranchPoint(branchDeterminers[i]);
				}

				// go backwards through the plans and find all that are equal
				boolean stillEqual = true;
				for (int k = plans.size() - 1; k >= 0 && stillEqual; k--) {
					PlanNode toCheck = plans.get(k);
					
					for (int i = 0; i < branchDeterminers.length; i++) {
						PlanNode checkerChoice = toCheck.getCandidateAtBranchPoint(branchDeterminers[i]);
					
						if (checkerChoice != determinerChoice[i]) {
							// not the same anymore
							stillEqual = false;
							break;
						}
					}
					
					if (stillEqual) {
						// the same
						plans.remove(k);
						turn.add(toCheck);
					}
				}

				// now that we have only plans with the same branch alternatives, prune!
				if (turn.size() > 1) {
					prunePlanAlternativesWithCommonBranching(turn);
				}
				result.addAll(turn);
			}

			// after all turns are complete
			plans.clear();
			plans.addAll(result);
		}
	}
911045
def permute(self, ordering: np.ndarray, *, axis: int) -> None:
		
		if axis not in (0, 1):
			raise ValueError("Axis must be 0 (rows) or 1 (columns)")
		for layer in self.layers.values():
			layer._permute(ordering, axis=axis)
		if axis == 0:
			if self.row_graphs is not None:
				for g in self.row_graphs.values():
					g._permute(ordering)
			for a in self.row_attrs.values():
				a._permute(ordering)
		elif axis == 1:
			if self.col_graphs is not None:
				for g in self.col_graphs.values():
					g._permute(ordering)
			for a in self.col_attrs.values():
				a._permute(ordering)
564268
def del_node(self, n):
        '''
        
        '''
        parent = self.get_node_attr(n, 'parent')
        if self.get_node_attr(n, 'direction') == 'R':
            self.set_node_attr(parent, 'Rchild', None)
        else:
            self.set_node_attr(parent, 'Lchild', None)
        Graph.del_node(self, n)
1355750
def concept_cuts(direction, node_indices, node_labels=None):
    """"""
    for partition in mip_partitions(node_indices, node_indices):
        yield KCut(direction, partition, node_labels)
198255
def rebin(a, newshape):
    """"""

    slices = [slice(0, old, float(old)/new)
              for old, new in zip(a.shape, newshape)]
    coordinates = numpy.mgrid[slices]
    # choose the biggest smaller integer index
    indices = coordinates.astype('i')
    return a[tuple(indices)]
950831
def delete_edge_by_nodes(self, node_a, node_b):
        """"""
        node = self.get_node(node_a)

        # Determine the edge ids
        edge_ids = []
        for e_id in node['edges']:
            edge = self.get_edge(e_id)
            if edge['vertices'][1] == node_b:
                edge_ids.append(e_id)

        # Delete the edges
        for e in edge_ids:
            self.delete_edge_by_id(e)
1171451
def cut_nodes_edges(graph):
    
    n = len(graph)
    time = 0
    num = [None] * n
    low = [n] * n
    father = [None] * n        # father[v] = None if root else father of v
    critical_childs = [0] * n  # c_c[u] = #childs v s.t. low[v] >= num[u]
    times_seen = [-1] * n
    for start in range(n):
        if times_seen[start] == -1:               # init DFS path
            times_seen[start] = 0
            to_visit = [start]
            while to_visit:
                node = to_visit[-1]
                if times_seen[node] == 0:         # start processing
                    num[node] = time
                    time += 1
                    low[node] = float('inf')
                children = graph[node]
                if times_seen[node] == len(children):  # end processing
                    to_visit.pop()
                    up = father[node]            # propagate low to father
                    if up is not None:
                        low[up] = min(low[up], low[node])
                        if low[node] >= num[up]:
                            critical_childs[up] += 1
                else:
                    child = children[times_seen[node]]   # next arrow
                    times_seen[node] += 1
                    if times_seen[child] == -1:   # not visited yet
                        father[child] = node      # link arrow
                        times_seen[child] = 0
                        to_visit.append(child)    # (below) back arrow
                    elif num[child] < num[node] and father[node] != child:
                        low[node] = min(low[node], num[child])
    cut_edges = []
    cut_nodes = []                                # extract solution
    for node in range(n):
        if father[node] is None:                  # characteristics
            if critical_childs[node] >= 2:
                cut_nodes.append(node)
        else:                                     # internal nodes
            if critical_childs[node] >= 1:
                cut_nodes.append(node)
            if low[node] >= num[node]:
                cut_edges.append((father[node], node))
    return cut_nodes, cut_edges
374444
def _cut_tree(tree, n_clusters, membs):
    
    ## starting from root,
    ## a node is added to the cut_set or 
    ## its children are added to node_set
    assert(n_clusters >= 2)
    assert(n_clusters <= len(tree.leaves()))

    cut_centers = dict() #np.empty(shape=(n_clusters, ndim), dtype=float)
    
    for i in range(n_clusters-1):
        if i==0:
            search_set = set(tree.children(0))
            node_set,cut_set = set(), set()
        else:
            search_set = node_set.union(cut_set)
            node_set,cut_set = set(), set()

        if i+2 == n_clusters:
            cut_set = search_set
        else:
            for _ in range(len(search_set)):
                n = search_set.pop()
            
                if n.data['ilev'] is None or n.data['ilev']>i+2:
                    cut_set.add(n)
                else:
                    nid = n.identifier
                    if n.data['ilev']-2==i:
                        node_set = node_set.union(set(tree.children(nid)))
   
    conv_membs = membs.copy()
    for node in cut_set:
        nid = node.identifier
        label = node.data['label']
        cut_centers[label] = node.data['center']
        sub_leaves = tree.leaves(nid)
        for leaf in sub_leaves:
            indx = np.where(conv_membs == leaf)[0]
            conv_membs[indx] = nid

    return(conv_membs, cut_centers)
1210953
def process_slice(self, b_rot90=None):
        '''
        
        '''
        if b_rot90:
            self._Mnp_2Dslice = np.rot90(self._Mnp_2Dslice)
        if self.func == 'invertIntensities':
            self.invert_slice_intensities()
983654
def prune(self, node_thres, edge_thres, paths, color_nodes_by_selftime):
        """"""

        # compute the prune ratios
        for function in compat_itervalues(self.functions):
            try:
                function.weight = function[TOTAL_TIME_RATIO]
            except UndefinedEvent:
                pass

            for call in compat_itervalues(function.calls):
                callee = self.functions[call.callee_id]

                if TOTAL_TIME_RATIO in call:
                    # handle exact cases first
                    call.weight = call[TOTAL_TIME_RATIO] 
                else:
                    try:
                        # make a safe estimate
                        call.weight = min(function[TOTAL_TIME_RATIO], callee[TOTAL_TIME_RATIO]) 
                    except UndefinedEvent:
                        pass

        # prune the nodes
        for function_id in compat_keys(self.functions):
            function = self.functions[function_id]
            if function.weight is not None:
                if function.weight < node_thres:
                    del self.functions[function_id]
        
        # prune file paths
        for function_id in compat_keys(self.functions):
            function = self.functions[function_id]
            if paths and function.filename and not any(function.filename.startswith(path) for path in paths):
                del self.functions[function_id]
            elif paths and function.module and not any((function.module.find(path)>-1) for path in paths):
                del self.functions[function_id]

        # prune the edges
        for function in compat_itervalues(self.functions):
            for callee_id in compat_keys(function.calls):
                call = function.calls[callee_id]
                if callee_id not in self.functions or call.weight is not None and call.weight < edge_thres:
                    del function.calls[callee_id]

        if color_nodes_by_selftime:
            weights = []
            for function in compat_itervalues(self.functions):
                try:
                    weights.append(function[TIME_RATIO])
                except UndefinedEvent:
                    pass
            max_ratio = max(weights or [1])

            # apply rescaled weights for coloriung
            for function in compat_itervalues(self.functions):
                try:
                    function.weight = function[TIME_RATIO] / max_ratio
                except (ZeroDivisionError, UndefinedEvent):
                    pass
842389
def merge_cycles(self):
      """"""
      while True:
         ### remove any self edges
         own_edges = self.get_self_edges()
         if len(own_edges) > 0:
            for e in own_edges: self.remove_edge(e)
         c = self.find_cycle()
         if not c: return
         keep = c[0]
         remove_list = c[1:]
         for n in remove_list: self.move_edges(n,keep)
         for n in remove_list: keep.payload_list += n.payload_list
         for n in remove_list: self.remove_node(n)