Iterative reordering method based on alternating rounds of node-centering
  and hill-climbing search.
184116
def node_centroid_hill_climbing(G, relax=1, num_centerings=20, verbose=False):
  ''''''
  # Initialize order with BFS from a random start node.
  order = _breadth_first_order(G)
  for it in range(num_centerings):
    B = permute_graph(G, order).bandwidth()
    nc_order = _node_center(G, order, relax=relax)
    nc_B = permute_graph(G, nc_order).bandwidth()
    if nc_B < B:
      if verbose:  # pragma: no cover
        print('post-center', B, nc_B)
      order = nc_order
    order = _hill_climbing(G, order, verbose=verbose)
  return permute_graph(G, order)
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;
  }
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;
	}
723690
function orderNodes(ast) {
  var comments  = Array.isArray(ast.comments) ? ast.comments.slice() : [];
  var comparitor = ('sortIndex' in ast) ? compareIndex : compareLocation;
  return comments
    .concat(depthFirst(ast, ast.parent))
    .sort(comparitor)
    .map(setSortIndex);
}
1220853
def laplacian_reordering(G):
  ''''''
  L = G.laplacian()
  vals, vecs = np.linalg.eigh(L)
  min_positive_idx = np.argmax(vals == vals[vals>0].min())
  vec = vecs[:, min_positive_idx]
  return permute_graph(G, np.argsort(vec))
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();
}
1137906
protected void orderNodeGrid(SquareGrid grid, int row, int col) {
		SquareNode node = grid.get(row,col);

		if(grid.rows==1 && grid.columns==1 ) {
			for (int i = 0; i < 4; i++) {
				ordered[i] = node.square.get(i);
			}
		} else if( grid.columns==1 ) {
			if (row == grid.rows - 1) {
				orderNode(node, grid.get(row - 1, col), false);
				rotateTwiceOrdered();
			} else {
				orderNode(node, grid.get(row + 1, col), false);
			}
		} else {
			if( col == grid.columns-1) {
				orderNode(node, grid.get(row, col-1), true);
				rotateTwiceOrdered();
			} else {
				orderNode(node, grid.get(row, col+1), true);
			}
		}
	}
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
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;

			}
		}
	}
586248
def group_and_sort_nodes(self):
        
        if self.node_grouping and not self.node_order:
            if self.group_order == "alphabetically":
                self.nodes = [
                    n
                    for n, d in sorted(
                        self.graph.nodes(data=True),
                        key=lambda x: x[1][self.node_grouping],
                    )
                ]

            elif self.group_order == "default":
                grp = [
                    d[self.node_grouping]
                    for _, d in self.graph.nodes(data=True)
                ]
                grp_name = list(unique_everseen(grp))
                nodes = []
                for key in grp_name:
                    nodes.extend(
                        [
                            n
                            for n, d in self.graph.nodes(data=True)
                            if key in d.values()
                        ]
                    )
                self.nodes = nodes

        elif self.node_order and not self.node_grouping:
            self.nodes = [
                n
                for n, _ in sorted(
                    self.graph.nodes(data=True),
                    key=lambda x: x[1][self.node_order],
                )
            ]

        elif self.node_grouping and self.node_order:
            if self.group_order == "alphabetically":
                self.nodes = [
                    n
                    for n, d in sorted(
                        self.graph.nodes(data=True),
                        key=lambda x: (
                            x[1][self.node_grouping],
                            x[1][self.node_order],
                        ),
                    )
                ]
            elif self.group_order == "default":
                grp = [
                    d[self.node_grouping]
                    for _, d in self.graph.nodes(data=True)
                ]
                grp_name = list(unique_everseen(grp))
                nodes = []
                for key in grp_name:
                    nodes.extend(
                        [
                            n
                            for n, d in sorted(
                                self.graph.nodes(data=True),
                                key=lambda x: x[1][self.node_order],
                            )
                            if key in d.values()
                        ]
                    )
                self.nodes = nodes
190842
def _iterative_matches(self, nodes):
        """"""
        nodelen = len(nodes)
        if 0 >= self.min:
            yield 0, {}

        results = []
        # generate matches that use just one alt from self.content
        for alt in self.content:
            for c, r in generate_matches(alt, nodes):
                yield c, r
                results.append((c, r))

        # for each match, iterate down the nodes
        while results:
            new_results = []
            for c0, r0 in results:
                # stop if the entire set of nodes has been matched
                if c0 < nodelen and c0 <= self.max:
                    for alt in self.content:
                        for c1, r1 in generate_matches(alt, nodes[c0:]):
                            if c1 > 0:
                                r = {}
                                r.update(r0)
                                r.update(r1)
                                yield c0 + c1, r
                                new_results.append((c0 + c1, r))
            results = new_results
713431
def astar(problem, graph_search=False, viewer=None):
    '''
    
    '''
    return _search(problem,
                   BoundedPriorityQueue(),
                   graph_search=graph_search,
                   node_factory=SearchNodeStarOrdered,
                   graph_replace_when_better=True,
                   viewer=viewer)
921897
private static int binarySearch(int[] a, int start, int end, int key) {
        int lo = start, hi = end-1; // search range is [lo,hi]

        // invariant lo<=hi
        while (lo <= hi) {
            int pivot = (lo + hi)/2;
            int v = a[pivot];

            if (v < key)        // needs to search upper half
                lo = pivot+1;
            else if (v > key)   // needs to search lower half
                hi = pivot-1;
            else    // eureka!
                return pivot;
        }
        return -(lo + 1); // insertion point
    }
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() ]);
		}
	    }
	}
    }
979852
def sort_cyclic_graph_best_effort(graph, pick_first='head'):
    """"""
    ordered = []
    visited = set()
    # Go first on the pick_first chain then go back again on the others
    # that were not visited. Given the way the graph is built both chains
    # will always contain all the elements.
    if pick_first == 'head':
        fst_attr, snd_attr = ('head_node', 'update_node')
    else:
        fst_attr, snd_attr = ('update_node', 'head_node')

    current = FIRST
    while current is not None:
        visited.add(current)
        current = getattr(graph[current], fst_attr)
        if current not in visited and current is not None:
            ordered.append(current)
    current = FIRST
    while current is not None:
        visited.add(current)
        current = getattr(graph[current], snd_attr)
        if current not in visited and current is not None:
            ordered.append(current)
    return ordered
1034205
function(instance, searchNode, x, y, cost) {
        var adjacentCoordinateX = searchNode.x+x;
        var adjacentCoordinateY = searchNode.y+y;

        if ((pointsToAvoid[adjacentCoordinateY] === undefined ||
             pointsToAvoid[adjacentCoordinateY][adjacentCoordinateX] === undefined) &&
            isTileWalkable(collisionGrid, acceptableTiles, adjacentCoordinateX, adjacentCoordinateY, searchNode)) {
            var node = coordinateToNode(instance, adjacentCoordinateX,
                adjacentCoordinateY, searchNode, cost);

            if (node.list === undefined) {
                node.list = OPEN_LIST;
                instance.openList.push(node);
            } else if (searchNode.costSoFar + cost < node.costSoFar) {
                node.costSoFar = searchNode.costSoFar + cost;
                node.parent = searchNode;
                instance.openList.updateItem(node);
            }
        }
    }
193064
@SuppressWarnings("InnerAssignment")
    private void quickSort(PagesIndex pagesIndex, int from, int to)
    {
        int len = to - from;
        // Insertion sort on smallest arrays
        if (len < SMALL) {
            for (int i = from; i < to; i++) {
                for (int j = i; j > from && (comparator.compareTo(pagesIndex, j - 1, j) > 0); j--) {
                    pagesIndex.swap(j, j - 1);
                }
            }
            return;
        }

        // Choose a partition element, v
        int m = from + len / 2; // Small arrays, middle element
        if (len > SMALL) {
            int l = from;
            int n = to - 1;
            if (len > MEDIUM) { // Big arrays, pseudomedian of 9
                int s = len / 8;
                l = median3(pagesIndex, l, l + s, l + 2 * s);
                m = median3(pagesIndex, m - s, m, m + s);
                n = median3(pagesIndex, n - 2 * s, n - s, n);
            }
            m = median3(pagesIndex, l, m, n); // Mid-size, med of 3
        }
        // int v = x[m];

        int a = from;
        int b = a;
        int c = to - 1;
        // Establish Invariant: v* (<v)* (>v)* v*
        int d = c;
        while (true) {
            int comparison;
            while (b <= c && ((comparison = comparator.compareTo(pagesIndex, b, m)) <= 0)) {
                if (comparison == 0) {
                    if (a == m) {
                        m = b; // moving target; DELTA to JDK !!!
                    }
                    else if (b == m) {
                        m = a; // moving target; DELTA to JDK !!!
                    }
                    pagesIndex.swap(a++, b);
                }
                b++;
            }
            while (c >= b && ((comparison = comparator.compareTo(pagesIndex, c, m)) >= 0)) {
                if (comparison == 0) {
                    if (c == m) {
                        m = d; // moving target; DELTA to JDK !!!
                    }
                    else if (d == m) {
                        m = c; // moving target; DELTA to JDK !!!
                    }
                    pagesIndex.swap(c, d--);
                }
                c--;
            }
            if (b > c) {
                break;
            }
            if (b == m) {
                m = d; // moving target; DELTA to JDK !!!
            }
            else if (c == m) {
                m = c; // moving target; DELTA to JDK !!!
            }
            pagesIndex.swap(b++, c--);
        }

        // Swap partition elements back to middle
        int s;
        int n = to;
        s = Math.min(a - from, b - a);
        vectorSwap(pagesIndex, from, b - s, s);
        s = Math.min(d - c, n - d - 1);
        vectorSwap(pagesIndex, b, n - s, s);

        // Recursively sort non-partition-elements
        if ((s = b - a) > 1) {
            quickSort(pagesIndex, from, from + s);
        }
        if ((s = d - c) > 1) {
            quickSort(pagesIndex, n - s, n);
        }
    }