Random SPR, with prune and regraft edges chosen randomly, and
        lengths drawn uniformly from the available edge lengths.

        N1: disallow_sibling_sprs prevents sprs that don't alter the topology
        of the tree
484454
def rspr(self, times=1, **kwargs):
        

        spr = SPR(self.copy())
        for _ in range(times):
            spr.rspr(**kwargs)
        return spr.tree
167250
def reduce_tree(node, parent=None):
    

    new_node = None
    #switch on the node type
    if node.type == syms.Matcher:
        #skip
        node = node.children[0]

    if node.type == syms.Alternatives  :
        #2 cases
        if len(node.children) <= 2:
            #just a single 'Alternative', skip this node
            new_node = reduce_tree(node.children[0], parent)
        else:
            #real alternatives
            new_node = MinNode(type=TYPE_ALTERNATIVES)
            #skip odd children('|' tokens)
            for child in node.children:
                if node.children.index(child)%2:
                    continue
                reduced = reduce_tree(child, new_node)
                if reduced is not None:
                    new_node.children.append(reduced)
    elif node.type == syms.Alternative:
        if len(node.children) > 1:

            new_node = MinNode(type=TYPE_GROUP)
            for child in node.children:
                reduced = reduce_tree(child, new_node)
                if reduced:
                    new_node.children.append(reduced)
            if not new_node.children:
                # delete the group if all of the children were reduced to None
                new_node = None

        else:
            new_node = reduce_tree(node.children[0], parent)

    elif node.type == syms.Unit:
        if (isinstance(node.children[0], pytree.Leaf) and
            node.children[0].value == '('):
            #skip parentheses
            return reduce_tree(node.children[1], parent)
        if ((isinstance(node.children[0], pytree.Leaf) and
               node.children[0].value == '[')
               or
               (len(node.children)>1 and
               hasattr(node.children[1], "value") and
               node.children[1].value == '[')):
            #skip whole unit if its optional
            return None

        leaf = True
        details_node = None
        alternatives_node = None
        has_repeater = False
        repeater_node = None
        has_variable_name = False

        for child in node.children:
            if child.type == syms.Details:
                leaf = False
                details_node = child
            elif child.type == syms.Repeater:
                has_repeater = True
                repeater_node = child
            elif child.type == syms.Alternatives:
                alternatives_node = child
            if hasattr(child, 'value') and child.value == '=': # variable name
                has_variable_name = True

        #skip variable name
        if has_variable_name:
            #skip variable name, '='
            name_leaf = node.children[2]
            if hasattr(name_leaf, 'value') and name_leaf.value == '(':
                # skip parenthesis
                name_leaf = node.children[3]
        else:
            name_leaf = node.children[0]

        #set node type
        if name_leaf.type == token_labels.NAME:
            #(python) non-name or wildcard
            if name_leaf.value == 'any':
                new_node = MinNode(type=TYPE_ANY)
            else:
                if hasattr(token_labels, name_leaf.value):
                    new_node = MinNode(type=getattr(token_labels, name_leaf.value))
                else:
                    new_node = MinNode(type=getattr(pysyms, name_leaf.value))

        elif name_leaf.type == token_labels.STRING:
            #(python) name or character; remove the apostrophes from
            #the string value
            name = name_leaf.value.strip("'")
            if name in tokens:
                new_node = MinNode(type=tokens[name])
            else:
                new_node = MinNode(type=token_labels.NAME, name=name)
        elif name_leaf.type == syms.Alternatives:
            new_node = reduce_tree(alternatives_node, parent)

        #handle repeaters
        if has_repeater:
            if repeater_node.children[0].value == '*':
                #reduce to None
                new_node = None
            elif repeater_node.children[0].value == '+':
                #reduce to a single occurence i.e. do nothing
                pass
            else:
                #TODO: handle {min, max} repeaters
                raise NotImplementedError
                pass

        #add children
        if details_node and new_node is not None:
            for child in details_node.children[1:-1]:
                #skip '<', '>' markers
                reduced = reduce_tree(child, new_node)
                if reduced is not None:
                    new_node.children.append(reduced)
    if new_node:
        new_node.parent = parent
    return new_node
129716
static SquareNode pickNot( SquareNode target , SquareNode child0 , SquareNode child1 ) {
		for (int i = 0; i < 4; i++) {
			SquareEdge e = target.edges[i];
			if( e == null ) continue;
			SquareNode c = e.destination(target);
			if( c != child0 && c != child1 )
				return c;
		}
		throw new RuntimeException("There was no odd one out some how");
	}
729508
def copy_random_pointer_v1(head):
    
    dic = dict()
    m = n = head
    while m:
        dic[m] = RandomListNode(m.label)
        m = m.next
    while n:
        dic[n].next = dic.get(n.next)
        dic[n].random = dic.get(n.random)
        n = n.next
    return dic.get(head)
545094
def prune(args):
    
    from collections import defaultdict

    p = OptionParser(prune.__doc__)
    add_graph_options(p)
    opts, args = p.parse_args(args)

    if len(args) != 1:
        sys.exit(not p.print_help())

    bestedges, = args
    G = read_graph(bestedges, maxerr=opts.maxerr)
    reads_to_ctgs = parse_ctgs(bestedges, opts.frgctg)
    edges = defaultdict(int)
    r = defaultdict(int)
    for a, b, d in G.edges_iter(data=True):
        ua, ub = reads_to_ctgs.get(a), reads_to_ctgs.get(b)
        nn = (ua, ub).count(None)
        if nn == 0:
            if ua == ub:
                r["Same tigs"] += 1
            else:
                r["Diff tigs"] += 1
                if ua > ub:
                    ua, ub = ub, ua
                edges[(ua, ub)] += 1
        elif nn == 1:
            r["One null"] += 1
        else:
            assert nn == 2
            r["Two nulls"] += 1

    U = nx.Graph()
    difftigs = "diff_tigs.txt"
    neighbors = defaultdict(list)
    fw = open(difftigs, "w")
    for (ua, ub), count in edges.items():
        print("\t".join((ua, ub, str(count))), file=fw)
        U.add_edge(ua, ub, weight=count)
        neighbors[ua].append((ub, count))
        neighbors[ub].append((ua, count))
    fw.close()

    print("[Unitig edge property]", file=sys.stderr)
    for k, v in r.items():
        print(": ".join((k, str(v))), file=sys.stderr)
    print("Total: {0}".format(sum(r.values())), file=sys.stderr)

    print("[Unitig degree distribution]", file=sys.stderr)
    degrees = U.degree()
    degree_counter = Counter(degrees.values())
    for degree, count in sorted(degree_counter.items()):
        print("{0}\t{1}".format(degree, count), file=sys.stderr)

    # To find associative contigs, one look for a contig that is connected and
    # only connected to another single contig - and do that recursively until no
    # more contigs can be found
    associative = {}
    for ua, ubs in neighbors.items():
        if len(ubs) == 1:   # Only one neighbor
            ub, count = ubs[0]
            if count >= 2:  # Bubble
                associative[ua] = (ub, count)
    print("A total of {0} associative contigs found"\
                        .format(len(associative)), file=sys.stderr)

    # Keep only one for mutual associative
    for ua, ub in associative.items():
        if ub in associative and ua < ub:
            print(ua, "mutually associative with", ub, file=sys.stderr)
            del associative[ub]
    print("A total of {0} associative contigs retained"\
                        .format(len(associative)), file=sys.stderr)

    assids = "associative.ids"
    fw = open(assids, "w")
    for ua, (ub, count) in sorted(associative.items(), key=lambda x:(x[1], x[0])):
        print("\t".join((ua, ub, str(count))), file=fw)
    fw.close()
    logging.debug("Associative contigs written to `{0}`".format(assids))
1047844
def suppress_deg_one_node(self, to_par_edge, nd_id, to_child_edge):
        """"""
        # circumvent the node with nd_id
        to_child_edge_id = to_child_edge['@id']
        par = to_par_edge['@source']
        self._edge_by_source[par][to_child_edge_id] = to_child_edge
        to_child_edge['@source'] = par
        # make it a tip...
        del self._edge_by_source[nd_id]
        # delete it
        self._del_tip(nd_id)
100294
function rbInsertFixup(tree, n) {
    // When inserting the node (at any place other than the root), we always color it red.
    // This is so that we don't violate the height invariant.
    // However, this may violate the color invariant, which we address by recursing back up the tree.
    n.flag = true;
    if (!n.p.flag) {
        throw new Error("n.p must be red.");
    }
    while (n.flag) {
        /**
         * The parent of n.
         */
        var p = n.p;
        if (n === tree.root) {
            tree.root.flag = false;
            return;
        }
        else if (p === tree.root) {
            tree.root.flag = false;
            return;
        }
        /**
         * The leader of the formation.
         */
        var lead = p.p;
        // Establish the n = red, p = red, g = black condition for a transformation.
        if (p.flag && !lead.flag) {
            if (p === lead.l) {
                var aux = lead.r;
                if (aux.flag) {
                    n = colorFlip(p, lead, aux);
                }
                else if (n === p.r) {
                    n = diamondLeftToVic(lead);
                }
                else {
                    n = echelonLeftToVic(lead);
                }
            }
            else {
                var aux = lead.l;
                if (aux.flag) {
                    n = colorFlip(p, lead, aux);
                }
                else if (n === n.p.l) {
                    n = diamondRightToVic(lead);
                }
                else {
                    n = echelonRightToVic(lead);
                }
            }
        }
        else {
            break;
        }
    }
    tree.root.flag = false;
}
415758
def get_graph_with_random_edges(graph, n_edges: int):
    
    result = graph.fresh_copy()
    result.add_edges_from(_random_edge_iterator(graph, n_edges))

    update_metadata(graph, result)
    update_node_helper(graph, result)
    return result
820180
private static void randomGaussian( Random rand , double sigma , int radius , Point2D_I32 pt ) {

		int x,y;

		while( true ) {
			x = (int)(rand.nextGaussian()*sigma);
			y = (int)(rand.nextGaussian()*sigma);
			if( Math.sqrt(x*x + y*y) < radius )
				break;
		}

		pt.set(x,y);
	}
828925
def ipcidr(self, *args):
        
        call_args = list(args)
        return self.random.choice(IPNetwork(call_args.pop(0)))
928675
def generate(self):
        '''
        '''
        offsets = (0., 0.)

        n_previous = 0

        # set recursion limit with respect to
        # the max number of nodes on the trees
        old_depth = sys.getrecursionlimit()
        max_depth = old_depth if old_depth > self._max_rec_depth else self._max_rec_depth
        # TODO: This should be fixed so we don't set sys.setrecursionlimit at all
        sys.setrecursionlimit(max_depth)

        if isinstance(self._obj, Neurite):

            max_diameter = _max_diameter(self._obj.root_node)

            dummy_section = Tree()
            dummy_section.add_child(self._obj.root_node)
            self._generate_dendro(dummy_section, (max_diameter, 0.), offsets)

            self._groups.append((0, self._n))

            self._dims.append(self._max_dims)

        else:

            for neurite in self._obj.neurites:

                neurite = neurite.root_node
                max_diameter = _max_diameter(neurite)
                dummy_section = Tree()

                dummy_section.add_child(neurite)
                self._generate_dendro(dummy_section, (max_diameter, 0.), offsets)

                # store in trees the indices for the slice which corresponds
                # to the current neurite
                self._groups.append((n_previous, self._n))

                # store the max dims per neurite for view positioning
                self._dims.append(self._max_dims)

                # reset the max dimensions for the next tree in line
                self._max_dims = [0., 0.]

                # keep track of the next tree start index in list
                n_previous = self._n

        # set it back to its initial value
        sys.setrecursionlimit(old_depth)
951998
def _choose_random_edge(self, edges: Set[EDGE]) -> Optional[EDGE]:
        
        if edges:
            index = self._rand.randint(len(edges))
            for e in edges:
                if not index:
                    return e
                index -= 1
        return None
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)
1133048
def flattenTrees(root, nodeSelector: Callable[[LNode], bool]):
    
    for ch in root.children:
        if ch.children:
            flattenTrees(ch, nodeSelector)

    # collect all nodes which can be potentialy reduced
    reducibleChildren = set()
    for ch in root.children:
        if nodeSelector(ch):
            reducibleChildren.add(ch)

    while reducibleChildren:
        # try to pick a node from random tree and search it's root
        _treeRoot = reducibleChildren.pop()
        reducibleChildren.add(_treeRoot)
        # we need to keep order of inputs, use preorder
        treeRoot = searchRootOfTree(reducibleChildren, _treeRoot)

        reducedNodes, inputEdges = collectNodesInTree(treeRoot, reducibleChildren)
        # if tree is big enoguh for reduction, reduce it to single node
        if len(reducedNodes) > 1:
            newName = reducedNodes[0].name
            newNode = root.addNode(newName)

            o = newNode.addPort("", PortType.OUTPUT, PortSide.EAST)

            oEdges = treeRoot.east[0].outgoingEdges
            for outputedge in list(oEdges):
                dsts = list(outputedge.dsts)
                assert len(dsts) > 0
                outputedge.remove()
                root.addHyperEdge([o, ], dsts, originObj=outputedge.originObj)

            for i, (iN, iP, iE) in enumerate(inputEdges):
                name = None
                index = len(inputEdges) - i - 1
                if hasattr(iE.originObj, "_dtype"):
                    w = iE.originObj._dtype.bit_length()
                    if w > 1:
                        name = "[%d:%d]" % ((index + 1) * w, index * w)
                    else:
                        name = None

                if name is None:
                    name = "[%d]" % (index)

                inp = newNode.addPort(name,
                                      PortType.INPUT, PortSide.WEST)
                iE.removeTarget(iP)
                iE.addTarget(inp)

            for n in reducedNodes:
                root.children.remove(n)
                reducibleChildren.remove(n)
        else:
            reducibleChildren.remove(reducedNodes[0])
1309932
def _prune_edges(G, X, traj_lengths, pruning_thresh=0.1, verbose=False):
  ''''''
  W = G.matrix('dense', copy=True)
  degree = G.degree(kind='out', weighted=False)
  i = 0
  num_bad = 0
  for n in traj_lengths:
    s, t = np.nonzero(W[i:i+n-1])
    graph_edges = X[t] - X[s+i]
    traj_edges = np.diff(X[i:i+n], axis=0)
    traj_edges = np.repeat(traj_edges, degree[i:i+n-1], axis=0)
    theta = paired_distances(graph_edges, traj_edges, 'cosine')
    bad_edges = theta > pruning_thresh
    s, t = s[bad_edges], t[bad_edges]
    if verbose:  # pragma: no cover
      num_bad += np.count_nonzero(W[s,t])
    W[s,t] = 0
    i += n
  if verbose:  # pragma: no cover
    print('removed %d bad edges' % num_bad)
  return Graph.from_adj_matrix(W)
707419
def random_filter(objects, reduction_factor, seed=42):
    
    assert 0 < reduction_factor <= 1, reduction_factor
    rnd = random.Random(seed)
    out = []
    for obj in objects:
        if rnd.random() <= reduction_factor:
            out.append(obj)
    return out
720145
protected boolean setupPruneList(GrowQueue_I32 regionMemberCount) {
		segmentPruneFlag.resize(regionMemberCount.size);
		pruneGraph.reset();
		segmentToPruneID.resize(regionMemberCount.size);
		for( int i = 0; i < regionMemberCount.size; i++ ) {
			if( regionMemberCount.get(i) < minimumSize ) {
				segmentToPruneID.set(i, pruneGraph.size());
				Node n = pruneGraph.grow();
				n.init(i);
				segmentPruneFlag.set(i, true);
			} else {
				segmentPruneFlag.set(i, false);
			}
		}

		return pruneGraph.size() != 0;
	}