Implements Kruskal's Algorithm for finding minimum spanning trees.
    Assumes a non-empty, connected graph.
320971
def kruskal_mst(graph):
    
    edges_accepted = 0
    ds = DisjointSet()
    pq = PriorityQueue()
    accepted_edges = []
    label_lookup = {}

    nodes = graph.get_all_node_ids()
    num_vertices = len(nodes)
    for n in nodes:
        label = ds.add_set()
        label_lookup[n] = label

    edges = graph.get_all_edge_objects()
    for e in edges:
        pq.put(e['id'], e['cost'])

    while edges_accepted < (num_vertices - 1):
        edge_id = pq.get()

        edge = graph.get_edge(edge_id)
        node_a, node_b = edge['vertices']
        label_a = label_lookup[node_a]
        label_b = label_lookup[node_b]

        a_set = ds.find(label_a)
        b_set = ds.find(label_b)

        if a_set != b_set:
            edges_accepted += 1
            accepted_edges.append(edge_id)
            ds.union(a_set, b_set)

    return accepted_edges
1104273
def optimize(self, graph):
        
        for start in graph.nodes():
            for end in graph.nodes():
                for each in graph.node_attributes(start):
                    if (each[0] == 'position'):
                        start_attr = each[1]
                        break
                for each in graph.node_attributes(end):
                    if (each[0] == 'position'):
                        end_attr = each[1]
                        break
                dist = 0
                for i in range(len(start_attr)):
                    dist = dist + (float(start_attr[i]) - float(end_attr[i]))**2
                self.distances[(start,end)] = dist
12424
def _sparse_neighbor_graph(X, k, binary=False, metric='l2'):
  ''''''
  knn = NearestNeighbors(n_neighbors=k, metric=metric).fit(X)
  mode = 'connectivity' if binary else 'distance'
  try:
    adj = knn.kneighbors_graph(None, mode=mode)
  except IndexError:
    # XXX: we must be running an old (<0.16) version of sklearn
    #  We have to hack around an old bug:
    if binary:
      adj = knn.kneighbors_graph(X, k+1, mode=mode)
      adj.setdiag(0)
    else:
      adj = knn.kneighbors_graph(X, k, mode=mode)
  return Graph.from_adj_matrix(adj)
1174769
function(node, l, b, r, t)
{
    return (max(node.bb_r, r) - min(node.bb_l, l))*(max(node.bb_t, t) - min(node.bb_b, b));
}
1078076
def connected_components(graph):
    
    recursionlimit = getrecursionlimit()
    setrecursionlimit(max(len(graph.nodes())*2,recursionlimit))
    
    visited = {}
    count = 1

    # For 'each' node not found to belong to a connected component, find its connected
    # component.
    for each in graph:
        if (each not in visited):
            _dfs(graph, visited, count, each)
            count = count + 1
    
    setrecursionlimit(recursionlimit)
    return visited
1296468
def transitively_reduce(self):
        
        removals = set()

        for from_node, neighbors in self._edges.items():
            childpairs = \
                [(c1, c2) for c1 in neighbors for c2 in neighbors if c1 != c2]

            for child1, child2 in childpairs:
                if self.has_path(child1, child2) \
                   and not self.has_path(child1, from_node):
                    removals.add((from_node, child2))

        for edge in removals:
            self.remove_edge(edge[0], edge[1])
867365
def configure(self, graph, spanning_tree):
        
        self.graph = graph
        self.spanning_tree = spanning_tree
404947
def _solve_tsp(dist, niter):
    

    # number of nodes
    N = dist.shape[0]

    # tsp path for quick calculation of cost
    ii = np.arange(N)
    jj = np.hstack((np.arange(1, N), 0))

    # for each node, cache a sorted list of all other nodes in order of
    # increasing distance.
    dsort = [np.argsort(d) for d in dist]
    dsort = [d[d != i] for i, d in enumerate(dsort)]

    # randomly initialize path through graph
    path = np.random.permutation(N)
    idx = np.argsort(path)
    cost = np.sum(dist[path[ii], path[jj]])

    # keep track of objective function over time
    cost_hist = [cost]

    # optimization loop
    node = 0
    itercount = 0
    n = 0

    while n < N and itercount < niter:

        # count iterations
        itercount += 1

        # we'll try breaking the connection i -> j
        i = path[node]
        j = path[(node+1) % N]

        # We are breaking i -> j so we can remove the cost of that connection.
        c = cost - dist[i, j]

        # Search over nodes k that are closer to j than i.
        for k in dsort[j]:

            # Can safely continue if dist[i,j] < dist[k,j] for the remaining k.
            if k == i:
                n += 1
                break

            # Break connection k -> p.
            # Add connection j -> p.
            # Add connection i -> k.
            p = path[(idx[k]+1) % N]
            new_cost = c - dist[k, p] + dist[j, p] + dist[i, k]

            # If this swap improves the cost, implement it and move to next i.
            if new_cost < cost:
                path = reverse_segment(path, idx[j], idx[k])
                idx = np.argsort(path)
                cost = new_cost
                # Restart from the begining of the graph.
                cost_hist.append(cost)
                n = 0
                break

        # move to next node
        node = (node + 1) % N

    return path, cost_hist
1258468
public static int findEdge(Poly node, Poly neighbour, MeshData tile, MeshData neighbourTile) {
		// Compare indices first assuming there are no duplicate vertices
		for (int i = 0; i < node.vertCount; i++) {
			int j = (i + 1) % node.vertCount;
			for (int k = 0; k < neighbour.vertCount; k++) {
				int l = (k + 1) % neighbour.vertCount;
				if ((node.verts[i] == neighbour.verts[l] && node.verts[j] == neighbour.verts[k])
						|| (node.verts[i] == neighbour.verts[k] && node.verts[j] == neighbour.verts[l])) {
					return i;
				}
			}
		}
		// Fall back to comparing actual positions in case of duplicate vertices
		for (int i = 0; i < node.vertCount; i++) {
			int j = (i + 1) % node.vertCount;
			for (int k = 0; k < neighbour.vertCount; k++) {
				int l = (k + 1) % neighbour.vertCount;
				if ((samePosition(tile.verts, node.verts[i], neighbourTile.verts, neighbour.verts[l])
						&& samePosition(tile.verts, node.verts[j], neighbourTile.verts, neighbour.verts[k]))
						|| (samePosition(tile.verts, node.verts[i], neighbourTile.verts, neighbour.verts[k])
								&& samePosition(tile.verts, node.verts[j], neighbourTile.verts, neighbour.verts[l]))) {
					return i;
				}
			}
		}
		return -1;
	}
1026074
def kruskal(graph, weight):
    
    uf = UnionFind(len(graph))
    edges = []
    for u in range(len(graph)):
        for v in graph[u]:
            edges.append((weight[u][v], u, v))
    edges.sort()
    mst = []
    for w, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v))
    return mst
1768
def incremental_neighbor_graph(X, precomputed=False, k=None, epsilon=None,
                               weighting='none'):
  ''''''
  assert ((k is not None) or (epsilon is not None)
          ), "Must provide `k` or `epsilon`"
  assert (_issequence(k) ^ _issequence(epsilon)
          ), "Exactly one of `k` or `epsilon` must be a sequence."
  assert weighting in ('binary','none'), "Invalid weighting param: " + weighting
  is_weighted = weighting == 'none'

  if precomputed:
    D = X
  else:
    D = pairwise_distances(X, metric='euclidean')
  # pre-sort for efficiency
  order = np.argsort(D)[:,1:]

  if k is None:
    k = D.shape[0]

  # generate the sequence of graphs
  # TODO: convert the core of these loops to Cython for speed
  W = np.zeros_like(D)
  I = np.arange(D.shape[0])
  if _issequence(k):
    # varied k, fixed epsilon
    if epsilon is not None:
      D[D > epsilon] = 0
    old_k = 0
    for new_k in k:
      idx = order[:, old_k:new_k]
      dist = D[I, idx.T]
      W[I, idx.T] = dist if is_weighted else 1
      yield Graph.from_adj_matrix(W)
      old_k = new_k
  else:
    # varied epsilon, fixed k
    idx = order[:,:k]
    dist = D[I, idx.T].T
    old_i = np.zeros(D.shape[0], dtype=int)
    for eps in epsilon:
      for i, row in enumerate(dist):
        oi = old_i[i]
        ni = oi + np.searchsorted(row[oi:], eps)
        rr = row[oi:ni]
        W[i, idx[i,oi:ni]] = rr if is_weighted else 1
        old_i[i] = ni
      yield Graph.from_adj_matrix(W)
128163
def dominator_tree(graph):
    
    todo = Queue()
    done = set()
    dominator = Tree(None)
    nodes = list(graph.nodes)

    while True:
        # FIGURE OUT NET ITEM TO WORK ON
        if todo:
            node = todo.pop()
        elif nodes:
            node = nodes.pop()
            if len(nodes) % 1000 == 0:
                Log.note("{{num}} nodes remaining", num=len(nodes))
        else:
            break
        if node in done:
            continue

        parents = graph.get_parents(node) - {node}
        if not parents:
            # node WITHOUT parents IS A ROOT
            done.add(node)
            dominator.add_edge(Edge(ROOTS, node))
            continue

        not_done = parents - done
        if not_done:
            # THERE ARE MORE parents TO DO FIRST
            more_todo = not_done - todo
            if not more_todo:
                # ALL PARENTS ARE PART OF A CYCLE, MAKE node A ROOT
                done.add(node)
                dominator.add_edge(Edge(LOOPS, node))
            else:
                # DO THE PARENTS BEFORE node
                todo.push(node)
                for p in more_todo:
                    todo.push(p)
            continue

        # WE CAN GET THE DOMINATORS FOR ALL parents
        if len(parents) == 1:
            # SHORTCUT
            dominator.add_edge(Edge(list(parents)[0], node))
            done.add(node)
            continue

        paths_from_roots = [
            list(reversed(dominator.get_path_to_root(p)))
            for p in parents
        ]

        if any(p[0] is ROOTS for p in paths_from_roots):
            # THIS OBJECT CAN BE REACHED FROM A ROOT, IGNORE PATHS FROM LOOPS
            paths_from_roots = [p for p in paths_from_roots if p[0] is ROOTS]
            if len(paths_from_roots) == 1:
                # SHORTCUT
                dom = paths_from_roots[0][-1]
                dominator.add_edge(Edge(dom, node))
                done.add(node)
                continue

        # FIND COMMON PATH FROM root
        num_paths = len(paths_from_roots)
        for i, x in enumerate(zip_longest(*paths_from_roots)):
            if x.count(x[0]) != num_paths:
                dom = paths_from_roots[0][i-1]
                if dom is LOOPS:
                    # CAN BE REACHED FROM MORE THAN ONE LOOP, PICK ONE TO BLAME
                    dom = paths_from_roots[0][-1]
                break
        else:
            # ALL PATHS IDENTICAL
            dom = paths_from_roots[0][-1]

        dominator.add_edge(Edge(dom, node))
        done.add(node)

    return dominator
103278
def minimum_spanning_subtree(self):
    ''''''
    dist = self.matrix('dense', copy=True)
    dist[dist==0] = np.inf
    np.fill_diagonal(dist, 0)
    mst = ssc.minimum_spanning_tree(dist)
    return self.__class__.from_adj_matrix(mst + mst.T)
452445
function dijkstra(graph, s) {
  const distance = {};
  const previous = {};
  const q = new PriorityQueue();
  // Initialize
  distance[s] = 0;
  graph.vertices.forEach(v => {
    if (v !== s) {
      distance[v] = Infinity;
    }
    q.insert(v, distance[v]);
  });

  let currNode;
  const relax = v => {
    const newDistance = distance[currNode] + graph.edge(currNode, v);
    if (newDistance < distance[v]) {
      distance[v] = newDistance;
      previous[v] = currNode;
      q.changePriority(v, distance[v]);
    }
  };
  while (!q.isEmpty()) {
    currNode = q.extract();
    graph.neighbors(currNode).forEach(relax);
  }
  return {
    distance,
    previous
  };
}
966043
def matrix_from_edges(edges):
    ''''''
    max_col = 0
    cols = []
    rows = []
    vals = []
    if type(edges) is defaultdict:
        edge_list = []
        for i, neighbors in edges.items():
            for j in neighbors:
                if i <= j:
                    edge_list.append((i,j))
        edges = edge_list
    for i, edge in enumerate(edges):
        s, t = edge[0], edge[1]
        weight = 1 if len(edge) == 2 else edge[2]
        cols.append(min(s,t))
        cols.append(max(s,t))
        rows.append(i)
        rows.append(i)
        vals.append(weight)
        vals.append(-weight)
        if cols[-1] > max_col:
            max_col = cols[-1]
    return coo_matrix((vals, (rows, cols)), shape=(rows[-1]+1, max_col+1))
246917
def find_cycle(graph):
    
    n = len(graph)
    prec = [None] * n  # ancestor marks for visited vertices
    for u in range(n):
        if prec[u] is None:  # unvisited vertex
            S = [u]  # start new DFS
            prec[u] = u  # mark root (not necessary for this algorithm)
            while S:
                u = S.pop()
                for v in graph[u]:  # for all neighbors
                    if v != prec[u]:  # except arcs to father in DFS tree
                        if prec[v] is not None:
                            cycle = [v, u]  # cycle found, (u,v) back edge
                            while u != prec[v] and u != prec[u]:  # directed
                                u = prec[u]  # climb up the tree
                                cycle.append(u)
                            return cycle
                        else:
                            prec[v] = u  # v is new vertex in tree
                            S.append(v)
    return None
285846
def tarjan_recursif(graph):
    
    global sccp, waiting, dfs_time, dfs_num
    sccp = []
    waiting = []
    waits = [False] * len(graph)
    dfs_time = 0
    dfs_num = [None] * len(graph)

    def dfs(node):
        global sccp, waiting, dfs_time, dfs_num
        waiting.append(node)           # new node is waiting
        waits[node] = True
        dfs_num[node] = dfs_time       # mark visit
        dfs_time += 1
        dfs_min = dfs_num[node]        # compute dfs_min
        for neighbor in graph[node]:
            if dfs_num[neighbor] is None:
                dfs_min = min(dfs_min, dfs(neighbor))
            elif waits[neighbor] and dfs_min > dfs_num[neighbor]:
                dfs_min = dfs_num[neighbor]
        if dfs_min == dfs_num[node]:   # representative of a component
            sccp.append([])            # make a component
            while True:                # add waiting nodes
                u = waiting.pop()
                waits[u] = False
                sccp[-1].append(u)
                if u == node:          # until representative
                    break
        return dfs_min

    for node in range(len(graph)):
        if dfs_num[node] is None:
            dfs(node)
    return sccp