matching a list of 2D positions to consecutive edges in a network
498460
def mapTrace(trace, net, delta, verbose=False):
    
    result = []
    paths = {}
    if verbose:
        print("mapping trace with %s points" % len(trace))
    for pos in trace:
        newPaths = {}
        candidates = net.getNeighboringEdges(pos[0], pos[1], delta)
        if len(candidates) == 0 and verbose:
            print("Found no candidate edges for %s,%s" % pos)
        for edge, d in candidates:
            if paths:
                minDist = 1e400
                minPath = None
                for path, dist in paths.iteritems():
                    if dist < minDist:
                        if edge == path[-1]:
                            minPath = path
                            minDist = dist
                        elif edge in path[-1].getOutgoing():
                            minPath = path + (edge,)
                            minDist = dist
                        else:
                            minPath = path + (edge,)
                            minDist = dist + euclidean(
                                path[-1].getToNode().getCoord(),
                                edge.getFromNode().getCoord())
                if minPath:
                    newPaths[minPath] = minDist + d * d
            else:
                newPaths[(edge,)] = d * d
        if not newPaths:
            if paths:
                result += [e.getID() for e in _getMinPath(paths)]
        paths = newPaths
    if paths:
        return result + [e.getID() for e in _getMinPath(paths)]
    return result
684930
def neighbors(self, key):
        """"""
        return {n: attr["bond"] for n, attr in self.graph[key].items()}
585453
def neighbors(self, node_id):
        """"""
        node = self.get_node(node_id)
        flattened_nodes_list = []
        for a, b in [self.get_edge(edge_id)['vertices'] for edge_id in node['edges']]:
            flattened_nodes_list.append(a)
            flattened_nodes_list.append(b)
        node_set = set(flattened_nodes_list)
        if node_id in node_set:
            node_set.remove(node_id)
        return [nid for nid in node_set]
1373526
def find_biconnected_components_as_subgraphs(graph):
    """"""
    list_of_graphs = []

    list_of_components = find_biconnected_components(graph)
    for edge_list in list_of_components:
        subgraph = get_subgraph_from_edge_list(graph, edge_list)
        list_of_graphs.append(subgraph)

    return list_of_graphs
1026345
def neighbors(self, obj):
        
        neighbors = set([])
        
        for e in self.node_links[obj]:
            neighbors.update(set(self.edge_links[e]))
        
        return list(neighbors - set([obj]))
883429
def distance_function_match(l1, l2, thresh, dist_fn, norm_funcs=[]):
    """"""
    common = []
    # We will keep track of the global index in the source list as we
    # will successively reduce their sizes.
    l1 = list(enumerate(l1))
    l2 = list(enumerate(l2))

    # Use the distance function and threshold on hints given by normalization.
    # See _match_by_norm_func for implementation details.
    # Also wrap the list element function function to ignore the global list
    # index computed above.
    for norm_fn in norm_funcs:
        new_common, l1, l2 = _match_by_norm_func(
                l1, l2,
                lambda a: norm_fn(a[1]),
                lambda a1, a2: dist_fn(a1[1], a2[1]),
                thresh)
        # Keep only the global list index in the end result.
        common.extend((c1[0], c2[0]) for c1, c2 in new_common)

    # Take any remaining umatched entries and try to match them using the
    # Munkres algorithm.
    dist_matrix = [[dist_fn(e1, e2) for i2, e2 in l2] for i1, e1 in l1]

    # Call Munkres on connected components on the remaining bipartite graph.
    # An edge links an element from l1 with an element from l2 only if
    # the distance between the elements is less (or equal) than the theshold.
    components = BipartiteConnectedComponents()
    for l1_i in range(len(l1)):
        for l2_i in range(len(l2)):
            if dist_matrix[l1_i][l2_i] > thresh:
                continue
            components.add_edge(l1_i, l2_i)

    for l1_indices, l2_indices in components.get_connected_components():
        # Build a partial distance matrix for each connected component.
        part_l1 = [l1[i] for i in l1_indices]
        part_l2 = [l2[i] for i in l2_indices]

        part_dist_matrix = [[dist_matrix[l1_i][l2_i] for l2_i in l2_indices]
                            for l1_i in l1_indices]
        part_cmn = _match_munkres(part_l1, part_l2, part_dist_matrix, thresh)

        common.extend((c1[0], c2[0]) for c1, c2 in part_cmn)

    return common
599255
def get_subgraph_from_edge_list(graph, edge_list):
    """"""
    node_list = get_vertices_from_edge_list(graph, edge_list)
    subgraph = make_subgraph(graph, node_list, edge_list)

    return subgraph
378993
def digraph_walker_backwards(graph, element, call_back):
    """"""
    call_back(graph, element)
    for predecessor in graph.predecessors(element):
        call_back(graph, predecessor)
    for predecessor in graph.predecessors(element):
        digraph_walker_backwards(graph, predecessor, call_back)
56294
public static List<SubGraph> getSubgraphsMatching(SameDiff sd, SubGraphPredicate p) {
        List<SubGraph> out = new ArrayList<>();
        for (DifferentialFunction df : sd.functions()) {
            if (p.matches(sd, df)) {
                SubGraph sg = p.getSubGraph(sd, df);
                out.add(sg);
            }
        }

        return out;
    }
346228
def find(self, i):
        '''
        
        '''
        current = i
        edge_list = []
        while len(self.get_neighbors(current)) != 0:
            successor = self.get_neighbors(current)[0]
            edge_list.append((current, successor))
            current = successor
        if self.optimize:
            for e in edge_list:
                if e[1] != current:
                    self.del_edge((e[0], e[1]))
                    self.add_edge(e[0], current)
        return current
823928
def from_edge_pairs(pairs, num_vertices=None, symmetric=False, weights=None):
  '''
  '''
  if not symmetric:
    if weights is None:
      return EdgePairGraph(pairs, num_vertices=num_vertices)
    row, col = np.asarray(pairs).T
    row, weights = np.broadcast_arrays(row, weights)
    shape = None if num_vertices is None else (num_vertices, num_vertices)
    adj = ss.coo_matrix((weights, (row, col)), shape=shape)
    return SparseAdjacencyMatrixGraph(adj)
  # symmetric case
  G = SymmEdgePairGraph(pairs, num_vertices=num_vertices)
  if weights is None:
    return G
  # Convert to sparse adj graph with provided edge weights
  s = G.matrix('coo').astype(float)
  # shenanigans to assign edge weights in the right order
  flat_idx = np.ravel_multi_index(s.nonzero(), s.shape)
  r, c = np.transpose(pairs)
  rc_idx = np.ravel_multi_index((r,c), s.shape)
  cr_idx = np.ravel_multi_index((c,r), s.shape)
  order = np.argsort(flat_idx)
  flat_idx = flat_idx[order]
  s.data[order[np.searchsorted(flat_idx, rc_idx)]] = weights
  s.data[order[np.searchsorted(flat_idx, cr_idx)]] = weights
  return SparseAdjacencyMatrixGraph(s)
120639
boolean arbitaryMatching(final int[][] graph, final BitSet subset) {

        final BitSet unmatched = new BitSet();

        // indicates the deg of each vertex in unmatched subset
        final int[] deg = new int[graph.length];

        // queue/stack of vertices with deg1 vertices
        final int[] deg1 = new int[graph.length];
        int nd1 = 0, nMatched = 0;

        for (int v = subset.nextSetBit(0); v >= 0; v = subset.nextSetBit(v + 1)) {
            if (matched(v)) {
                assert subset.get(other(v));
                nMatched++;
                continue;
            }
            unmatched.set(v);
            for (int w : graph[v])
                if (subset.get(w) && unmatched(w)) deg[v]++;
            if (deg[v] == 1) deg1[nd1++] = v;
        }

        while (!unmatched.isEmpty()) {

            int v = -1;

            // attempt to select a vertex with degree = 1 (in matched set)
            while (nd1 > 0) {
                v = deg1[--nd1];
                if (unmatched.get(v)) break;
            }

            // no unmatched degree 1 vertex, select the first unmatched
            if (v < 0 || unmatched.get(v)) v = unmatched.nextSetBit(0);

            unmatched.clear(v);

            // find a unmatched edge and match it, adjacent degrees are updated
            for (final int w : graph[v]) {
                if (unmatched.get(w)) {
                    match(v, w);
                    nMatched += 2;
                    unmatched.clear(w);
                    // update neighbors of w and v (if needed)
                    for (final int u : graph[w])
                        if (--deg[u] == 1 && unmatched.get(u)) deg1[nd1++] = u;

                    // if deg == 1, w is the only neighbor
                    if (deg[v] > 1) {
                        for (final int u : graph[v])
                            if (--deg[u] == 1 && unmatched.get(u)) deg1[nd1++] = u;
                    }
                    break;
                }
            }
        }

        return nMatched == subset.cardinality();
    }
989325
def B(u, v, dfs_data):
    """Bu(v) = {wx | w is in S*(v)}"""
    if a(v, dfs_data) != u:
        return None

    return list(set([edge_id for w in S_star(v, dfs_data) for edge_id in dfs_data['graph'].get_node(w)['edges']]))
1293134
def _init_edges(p2cs, c2ps):
        """"""
        edge_from_to = []
        for parent, children in p2cs.items():
            for child in children:
                # if child in goids_present and parent in goids_present:
                edge_from_to.append((child, parent))
        for parent, children in c2ps.items():
            for child in children:
                # if child in goids_present and parent in goids_present:
                edge_from_to.append((child, parent))
        return edge_from_to
854401
def _graph_reduction(adj, x, g, f):
    
    as_list = set()
    as_nodes = {v for v in adj if len(adj[v]) <= f and is_almost_simplicial(adj, v)}
    while as_nodes:
        as_list.union(as_nodes)
        for n in as_nodes:

            # update g and f
            dv = len(adj[n])
            if dv > g:
                g = dv
            if g > f:
                f = g

            # eliminate v
            x.append(n)
            _elim_adj(adj, n)

        # see if we have any more simplicial nodes
        as_nodes = {v for v in adj if len(adj[v]) <= f and is_almost_simplicial(adj, v)}

    return g, f, as_list
1320308
def p_edgesigs(self, p):
        ''
        p[0] = p[1] + (p[3],)
        p.set_lineno(0, p.lineno(1))
1010877
def __calculate_adjacency_lists(graph):
    """"""
    adj = {}
    for node in graph.get_all_node_ids():
        neighbors = graph.neighbors(node)
        adj[node] = neighbors
    return adj