The goal is to assign scaffold orders. To help order the scaffolds, two
        dummy node, START and END, mark the ends of the chromosome. We connect
        START to each scaffold (directed), and each scaffold to END.
764780
def assign_order(self):
        
        linkage_groups = self.linkage_groups
        for mlg in linkage_groups:
            mapname = mlg.mapname
            if mapname == self.pivot:
                pivot_position = mlg.position

        for mlg in linkage_groups:
            position = mlg.position
            # Flip order if path goes in the opposite direction to the pivot
            common = []
            for a, ap in position.items():
                if a not in pivot_position:
                    continue
                pp = pivot_position[a]
                common.append((ap, pp))

            mlg.rho = get_rho(common)
            if mlg.rho < 0:
                mlg.path = mlg.path[::-1]

            mlg.populate_pairwise_distance()

        # Preparation of TSP
        distances = defaultdict(list)
        for mlg in linkage_groups:
            mapname = mlg.mapname
            position = mlg.position
            length = mlg.length
            path = mlg.path
            rho = mlg.rho
            dd = mlg.distances
            for a, b in combinations(path, 2):
                d = dd[a, b]
                distances[a, b].append((d, mapname))
            for p in path:
                adist, bdist = position[p], length - position[p]
                if rho < 0:
                    adist, bdist = bdist, adist
                distances[START, p].append((adist, mapname))
                distances[p, END].append((bdist, mapname))

        self.distances = distances
        tour = self.distances_to_tour()
        return tour
1236563
def _generate_draw_order(self, node=None):
        
        if node is None:
            node = self._scene
        order = [(node, True)]
        children = node.children
        children.sort(key=lambda ch: ch.order)
        for ch in children:
            order.extend(self._generate_draw_order(ch))
        order.append((node, False))
        return order
889252
def scaffold(args):
    
    p = OptionParser(scaffold.__doc__)
    p.set_aligner(aligner="bwa")
    p.set_home("sspace")
    p.set_cpus()
    opts, args = p.parse_args(args)

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

    contigs = args[0]
    libtxt = write_libraries(args[1:], aligner=opts.aligner)
    # Requires getopts.pl which may be missing
    download("http://web.vims.edu/bridge/bridge2/aw/lib/getopts.pl")

    cmd = "perl " + op.join(opts.sspace_home, "SSPACE_Standard_v3.0.pl")
    cmd += " -l {0} -s {1} -T {2}".format(libtxt, contigs, opts.cpus)
    runsh = "run.sh"
    write_file(runsh, cmd)
373225
def _create_initial_solution(self) -> _STATE:
        

        def extract_sequences() -> List[List[GridQubit]]:
            """Creates list of sequcenes for initial state.

            Returns:
              List of lists of sequences constructed on the chip.
            """
            seqs = []
            prev = None
            seq = None
            for node in self._c:
                if prev is None:
                    seq = [node]
                else:
                    if node in self._c_adj[prev]:
                        # Expand current sequence.
                        seq.append(node)
                    else:
                        # Create new sequence, there is no connection between
                        # nodes.
                        seqs.append(seq)
                        seq = [node]
                prev = node
            if seq:
                seqs.append(seq)
            return seqs

        def assemble_edges() -> Set[EDGE]:
            """Creates list of edges for initial state.

            Returns:
              List of all possible edges.
            """
            nodes_set = set(self._c)
            edges = set()
            for n in self._c:
                if above(n) in nodes_set:
                    edges.add(self._normalize_edge((n, above(n))))
                if right_of(n) in nodes_set:
                    edges.add(self._normalize_edge((n, right_of(n))))
            return edges

        return extract_sequences(), assemble_edges()
321299
def init_genome_coordinates(self) :
        """"""
        self.seqpos2genome = {}

        # record genome positions for each sequence position
        seq_pos = 0
        for estart, eend in self.exons:
            for genome_pos in range(estart, eend):
                if self.strand == '+':
                    self.seqpos2genome[seq_pos] = genome_pos
                elif self.strand == '-':
                    tmp = self.cds_len - seq_pos - 1
                    self.seqpos2genome[tmp] = genome_pos
                seq_pos += 1

        # recode 5' splice site locations
        for i in range(0, self.five_ss_len):
            seq_pos = self.cds_len + i
            ss_ix = i // 2  # the ss_ix'th 5'ss starting from upstream tx
            pos_in_ss = i % 2  # whether first/second nuc in splice site

            # determine genome coordinates for 5' splice site
            if self.strand == '+':
                self.seqpos2genome[seq_pos] = self.exons[ss_ix][1] + pos_in_ss
            else:
                exon_pos = -1 - ss_ix
                self.seqpos2genome[seq_pos] = self.exons[exon_pos][0] - pos_in_ss - 1

        # recode 3' splice site locations
        for i in range(0, self.three_ss_len):
            seq_pos = self.cds_len + self.five_ss_len + i
            ss_ix = i // 2  # the ss_ix'th 3'ss starting from upstream tx
            pos_in_ss = i % 2  # whether first/second nuc in splice site

            # determine genome coordinates for 3' splice site
            if self.strand == '+':
                self.seqpos2genome[seq_pos] = self.exons[ss_ix+1][0] - 2 + pos_in_ss
            else:
                exon_pos = -1 - ss_ix
                self.seqpos2genome[seq_pos] = self.exons[exon_pos-1][1] + 1 - pos_in_ss
676523
def prepare_ec(self, scaffolds, tour, weights):
        
        scaffolds_ii = dict((s, i) for i, s in enumerate(scaffolds))
        scfs = []
        ww = []
        for mlg in self.linkage_groups:
            w = float(weights[mlg.mapname])
            scf = {}
            for s, o in tour:
                si = scaffolds_ii[s]
                scf[si] = self.get_series(mlg.lg, s, orientation=o)
            scfs.append(scf)
            ww.append(w)
        tour = [scaffolds_ii[x] for x, o in tour]

        return scfs, tour, ww
907453
protected function moveNode()
    {
        if ($this->exists) {
            if (is_null($this->closure->ancestor)) {
                $primaryKey = $this->getKey();
                $this->closure->ancestor = $primaryKey;
                $this->closure->descendant = $primaryKey;
                $this->closure->depth = 0;
            }

            if ($this->isDirty($this->getParentIdColumn())) {
                $this->reorderSiblings(true);
                $this->closure->moveNodeTo($this->parent_id);
            }
        }
    }
441101
protected function assemble()
    {
        $this->push('SELECT');
        $this->pushDistinct();
        $this->pushColumns();
        $this->push('FROM');
        $this->pushTable();
        $this->pushHint();
        $this->pushJoin();
        $this->pushWhere();
        $this->pushGroup();
        $this->pushOrder();
        $this->pushLimit();
    }
1200645
def post_order(self):
        
        def _visit(n, cnt):
            visited.add(n)
            for suc in self.all_sucs(n):
                if suc not in visited:
                    for cnt, s in _visit(suc, cnt):
                        yield cnt, s
            n.po = cnt
            yield cnt + 1, n

        visited = set()
        for _, node in _visit(self.entry, 1):
            yield node
1248836
void append(@NonNull Node<E> first, @NonNull Node<E> last) {
    for (;;) {
      Node<E> t = tail;
      if (casTail(t, last)) {
        t.lazySetNext(first);
        if (factory == OPTIMISIC) {
          return;
        }
        for (;;) {
          first.complete();
          if (first == last) {
            return;
          }
          Node<E> next = first.getNextRelaxed();
          if (next.value == null) {
            first.next = null; // reduce nepotism
          }
          first = next;
        }
      }
      Node<E> node = transferOrCombine(first, last);
      if (node == null) {
        first.await();
        return;
      } else if (node != first) {
        last = node;
      }
    }
  }
92000
protected int addNodeInDocOrder(int node)
   {
      assertion(hasCache(), "addNodeInDocOrder must be done on a mutable sequence!");

      int insertIndex = -1;
      
      NodeVector vec = getVector();

      // This needs to do a binary search, but a binary search 
      // is somewhat tough because the sequence test involves 
      // two nodes.
      int size = vec.size(), i;

      for (i = size - 1; i >= 0; i--)
      {
        int child = vec.elementAt(i);

        if (child == node)
        {
          i = -2; // Duplicate, suppress insert

          break;
        }

        DTM dtm = m_dtmMgr.getDTM(node);
        if (!dtm.isNodeAfter(node, child))
        {
          break;
        }
      }

      if (i != -2)
      {
        insertIndex = i + 1;

        vec.insertElementAt(node, insertIndex);
      }

      // checkDups();
      return insertIndex;
    }
882323
void sortEdgesCCW(FastQueue<Node> corners) {
		for (int nodeIdx = 0; nodeIdx < corners.size; nodeIdx++) {
			Node na = corners.get(nodeIdx);

			// reference node to do angles relative to.
			double ref = Double.NaN;
			int count = 0;
			for (int i = 0; i < 4; i++) {
				order[i] = i;
				tmpEdges[i] = na.edges[i];
				if( na.edges[i] == null ) {
					directions[i] = Double.MAX_VALUE;
				} else {
					Node nb = na.edges[i];
					double angleB = Math.atan2(nb.y-na.y,nb.x-na.x);
					if( Double.isNaN(ref) ) {
						ref = angleB;
						directions[i] = 0;
					} else {
						directions[i] = UtilAngle.distanceCCW(ref,angleB);
					}
					count++;
				}
			}

			sorter.sort(directions,0,4,order);
			for (int i = 0; i < 4; i++) {
				na.edges[i] = tmpEdges[ order[i] ];
			}
			if( count == 2 ) {
				// If there are only two then we define the order to be defined by the one which minimizes
				// CCW direction
				if( directions[order[1]] > Math.PI ) {
					na.edges[0] = tmpEdges[ order[1] ];
					na.edges[1] = tmpEdges[ order[0] ];
				} else {
					na.edges[0] = tmpEdges[ order[0] ];
					na.edges[1] = tmpEdges[ order[1] ];
				}
			} else if( count == 3 ) {
				// Edges need to point along the 4 possible directions, in the case of 3 edges, there might
				// need to be a gap at a different location than at the end
				int selected = -1;
				double largestAngle = 0;
				for (int i = 0,j=2; i < 3; j=i,i++) {
					double ccw = UtilAngle.distanceCCW(directions[order[j]],directions[order[i]]);
					if( ccw > largestAngle ) {
						largestAngle = ccw;
						selected = j;
					}
				}

				for (int i = 2; i > selected; i--) {
					na.edges[i+1] = na.edges[i];
				}
				na.edges[selected+1]=null;

			}
		}
	}
1094136
function walk(node, cb) {
  nast.walk(node,
    function (node) {
      cb(node);
    },
    function (node) {
      cb({type: 'end', node: node});
    }
  );
}
1024390
def identify_assembly_points(graph, bgtree, target_multicolor, exclude=None, verbose=False, verbose_destination=None):
    
    if verbose:
        print(">>Identifying assemblies for target multicolor:",
              [e.name for e in target_multicolor.multicolors.elements()], file=verbose_destination)
    guidance = bgtree.consistent_multicolors[:]
    offset = len(Multicolor.split_colors(target_multicolor, guidance=guidance,
                                         account_for_color_multiplicity_in_guidance=False)) - 1
    assemblies = []  # the overall result
    if exclude is None:
        exclude = []  # a container with single colors of genomes, that are to be considered fully assembled
    multicolor_scores = {}
    surroundings = {}
    full_irregular_multicolors = {}
    for i, cc in enumerate(graph.connected_components_subgraphs(copy=True)):
        subnets, possible_assemblies, h_support, t_support, repeats = get_irregular_subnets(cc, target_multicolor, exclude)
        for subnet in subnets:
            vertices = [vertex for vertex in subnet.nodes() if not vertex.is_irregular_vertex]
            repeats_h = {repeat for vertex in vertices for repeat in h_support[vertex]}
            repeats_t = {repeat for vertex in vertices for repeat in t_support[vertex]}
            repeats = repeats_h.intersection(repeats_t)
            for repeat in repeats:
                g = nx.Graph()
                for edge in filter(lambda edge: not edge.is_irregular_edge, subnet.edges()):
                    v1, v2 = sorted((edge.vertex1, edge.vertex2), key=lambda vertex: vertex.name)
                    if v1 in h_support and repeat in h_support[v1] and v2 in t_support and repeat in t_support[v2]:
                        before, after = get_assembly_score(graph, v1, v2, target_multicolor, bgtree,
                                                           multicolor_scores, surroundings, full_irregular_multicolors)
                        if before - after - offset > 1:
                            g.add_edge((v1, "h"), (v2, "t"), weight=before - after - offset)
                    if v1 in t_support and repeat in t_support[v1] and v2 in h_support and repeat in h_support[v2]:
                        before, after = get_assembly_score(graph, v1, v2, target_multicolor, bgtree,
                                                           multicolor_scores, surroundings, full_irregular_multicolors)
                        if before - after - offset > 1:
                            g.add_edge((v1, "t"), (v2, "h"), weight=before - after - offset)
                edges = g.edges(data=True)
                if len(edges) == 0:
                    continue
                new_edges = []
                for edge in edges:
                    first, second = edge[0], edge[1]
                    v1, v2 = sorted((first, second), key=lambda item: item[0].name)
                    new_edges.append((v1, v2, edge[2]))
                edges = sorted(new_edges, reverse=True, key=lambda e: (e[2]["weight"], e[0][0].name, e[0][1], e[1][0].name, e[0][1]))
                visited = set()
                for v1, v2, data in edges:
                    weight = data["weight"]
                    if v1 not in visited and v2 not in visited:
                        visited.add(v1)
                        visited.add(v2)
                        v1, dir1 = v1
                        v2, dir2 = v2
                        assert (dir1 == "h" and dir2 == "t") or (dir1 == "t" and dir2 == "h")
                        if dir1 == "h":
                            assemblies.append((v2, v1, weight, repeat))
                        else:
                            assemblies.append((v1, v2, weight, repeat))
    return assemblies
967779
function assignHelixSheet(structure) {
  console.time('mol.assignHelixSheet');
  var chains = structure.chains();
  for (var ci = 0; ci < chains.length; ++ci) {
    var chain = chains[ci];
    chain.eachBackboneTrace(traceAssignHelixSheet);
  }
  console.timeEnd('mol.assignHelixSheet');
}
855602
def plot_info_frags(scaffolds):

    

    scaffolds = format_info_frags(scaffolds)
    for name, scaffold in scaffolds.items():
        plt.figure()
        xs = range(len(scaffold))
        color = []
        names = {}
        ys = []
        for my_bin in scaffold:
            current_color = "r" if my_bin[4] > 0 else "g"
            color += [current_color]
            name = my_bin[0]
            if name in names:
                ys.append(names[name])
            else:
                names[name] = len(names)
                ys.append(names[name])
        plt.scatter(xs, ys, c=color)
    plt.show()
748965
private void rotateTwiceOrdered() {
		Point2D_F64 a = ordered[0];
		Point2D_F64 b = ordered[1];
		Point2D_F64 c = ordered[2];
		Point2D_F64 d = ordered[3];

		ordered[0] = c;
		ordered[1] = d;
		ordered[2] = a;
		ordered[3] = b;
	}