Create a connectivity matrix where each incoming edge becomes outgoing.
499478
def reversed(self):
        """"""
        n_rows = len(self)
        reversed = DirectedAdjacencyMatrix(n_rows, self.dtype)
        for r, row in enumerate(py.prog_iter(self)):
            for c in row:
                reversed[c].append(r)
                
        return reversed
1124543
protected void setUpEdges(GrayS32 input , GrayS32 output  ) {
		if( connectRule == ConnectRule.EIGHT ) {
			setUpEdges8(input,edgesIn);
			setUpEdges8(output,edgesOut);

			edges[0].set( 1, 0);
			edges[1].set( 1, 1);
			edges[2].set( 0, 1);
			edges[3].set(-1, 0);
		} else {
			setUpEdges4(input,edgesIn);
			setUpEdges4(output,edgesOut);

			edges[0].set( 1,0);
			edges[1].set( 0, 1);
		}
	}
383279
def graph_simplify(G):
    
    spurs = []
    path_nodes = []
    for k, d in G.degree().iteritems():
        if d == 1:
            spurs.append(k)
        elif d == 2:
            path_nodes.append(k)

    logging.debug("Remove {0} spurs.".format(len(spurs)))
    G.remove_nodes_from(spurs)

    SG = G.subgraph(path_nodes)
    cc = nx.connected_components(SG)
    for c in cc:
        if len(c) == 1:
            continue
        c = set(c)
        neighbors = set()
        for x in c:
            neighbors |= set(G.neighbors(x))
        neighbors -= c
        newtag = list(c)[0] + "*"
        for n in neighbors:
            G.add_edge(newtag, n)
        G.remove_nodes_from(c)
    logging.debug("Contract {0} path nodes into {1} nodes.".\
                    format(len(path_nodes), len(cc)))
470656
def edges2nodes(edges):
    """"""
    nodes = []
    for e1, e2 in edges:
        nodes.append(e1)
        nodes.append(e2)
    nodedict = dict([(n, None) for n in nodes])
    justnodes = list(nodedict.keys())
    # justnodes.sort()
    justnodes = sorted(justnodes, key=lambda x: str(x[0]))
    return justnodes
534870
def connectivity_map(dset,prefix,x,y,z,radius=2):
    ''''''
    seed_series = nl.sphere_average(dset,x,y,z,radius)
    with tempfile.NamedTemporaryFile(delete=False) as temp:
        temp.write('\n'.join([str(x) for x in seed_series]))
    decon = nl.Decon()
    decon.input_dsets = dset
    decon.stim_files = {'seed':temp.name}
    decon.prefix = prefix
    decon.run()
    try:
        os.remove(temp.name)
    except:
        pass
662579
def prevnode(edges, component):
    """"""
    e = edges
    c = component
    n2c = [(a, b) for a, b in e if type(a) == tuple]
    c2n = [(a, b) for a, b in e if type(b) == tuple]
    node2cs = [(a, b) for a, b in e if b == c]
    c2nodes = []
    for node2c in node2cs:
        c2node = [(a, b) for a, b in c2n if b == node2c[0]]
        if len(c2node) == 0:
            # return []
            c2nodes = []
            break
        c2nodes.append(c2node[0])
    cs = [a for a, b in c2nodes]
    # test for connections that have no nodes
    # filter for no nodes
    nonodes = [(a, b) for a, b in e if type(a) != tuple and type(b) != tuple]
    for a, b in nonodes:
        if b == component:
            cs.append(a)
    return cs
58669
def connect_edges(graph):
    
    paths = []
    for start, end in graph.array(graph.kdims):
        start_ds = graph.nodes[:, :, start]
        end_ds = graph.nodes[:, :, end]
        if not len(start_ds) or not len(end_ds):
            raise ValueError('Could not find node positions for all edges')
        start = start_ds.array(start_ds.kdims[:2])
        end = end_ds.array(end_ds.kdims[:2])
        paths.append(np.array([start[0], end[0]]))
    return paths
777730
def transfer_causal_edges(graph, source: BaseEntity, target: BaseEntity) -> Iterable[str]:
    """"""
    for _, v, data in graph.out_edges(source, data=True):
        if data[RELATION] not in CAUSAL_RELATIONS:
            continue

        yield graph.add_qualified_edge(
            target,
            v,
            relation=data[RELATION],
            evidence=data[EVIDENCE],
            citation=data[CITATION],
            annotations=data.get(ANNOTATIONS),
            subject_modifier=data.get(SUBJECT),
            object_modifier=data.get(OBJECT),
        )

    for u, _, data in graph.in_edges(source, data=True):
        if data[RELATION] not in CAUSAL_RELATIONS:
            continue

        yield graph.add_qualified_edge(
            u,
            target,
            relation=data[RELATION],
            evidence=data[EVIDENCE],
            citation=data[CITATION],
            annotations=data.get(ANNOTATIONS),
            subject_modifier=data.get(SUBJECT),
            object_modifier=data.get(OBJECT),
        )
1002643
def tsp(edges, constraint_generation=False):
    
    edges = populate_edge_weights(edges)
    incoming, outgoing, nodes = node_to_edge(edges)

    nedges, nnodes = len(edges), len(nodes)
    L = LPInstance()

    L.add_objective(edges, objective=MINIMIZE)
    balance = []
    # For each node, select exactly 1 incoming and 1 outgoing edge
    for v in nodes:
        incoming_edges = incoming[v]
        outgoing_edges = outgoing[v]
        icc = summation(incoming_edges)
        occ = summation(outgoing_edges)
        balance.append("{0} = 1".format(icc))
        balance.append("{0} = 1".format(occ))

    # Subtour elimination - Miller-Tucker-Zemlin (MTZ) formulation
    # <http://en.wikipedia.org/wiki/Travelling_salesman_problem>
    # Desrochers and laporte, 1991 (DFJ) has a stronger constraint
    # See also:
    # G. Laporte / The traveling salesman problem: Overview of algorithms
    start_step = nedges + 1
    u0 = nodes[0]
    nodes_to_steps = dict((n, start_step + i) for i, n in enumerate(nodes[1:]))
    edge_store = dict((e[:2], i) for i, e in enumerate(edges))
    mtz = []
    for i, e in enumerate(edges):
        a, b = e[:2]
        if u0 in (a, b):
            continue
        na, nb = nodes_to_steps[a], nodes_to_steps[b]
        con_ab = " x{0} - x{1} + {2}x{3}".format(na, nb, nnodes - 1, i + 1)
        if (b, a) in edge_store:  # This extra term is the stronger DFJ formulation
            j = edge_store[(b, a)]
            con_ab += " + {0}x{1}".format(nnodes - 3, j + 1)
        con_ab += " <= {0}".format(nnodes - 2)
        mtz.append(con_ab)

    # Step variables u_i bound between 1 and n, as additional variables
    bounds = []
    for i in xrange(start_step, nedges + nnodes):
        bounds.append(" 1 <= x{0} <= {1}".format(i, nnodes - 1))

    L.add_vars(nedges)

    """
    Constraint generation seek to find 'cuts' in the LP problem, by solving the
    relaxed form. The subtours were then incrementally added to the constraints.
    """
    if constraint_generation:
        L.constraints = balance
        subtours = []
        while True:
            selected, obj_val = L.lpsolve()
            results = sorted(x for i, x in enumerate(edges) if i in selected) \
                if selected else None
            if not results:
                break
            G = edges_to_graph(results)
            cycles = list(nx.simple_cycles(G))
            if len(cycles) == 1:
                break
            for c in cycles:
                incident = [edge_store[a, b] for a, b in pairwise(c + [c[0]])]
                icc = summation(incident)
                subtours.append("{0} <= {1}".format(icc, len(incident) - 1))
            L.constraints = balance + subtours
    else:
        L.constraints = balance + mtz
        L.add_vars(nnodes - 1, offset=start_step, binary=False)
        L.bounds = bounds
        selected, obj_val = L.lpsolve()
        results = sorted(x for i, x in enumerate(edges) if i in selected) \
            if selected else None

    return results
782359
def connectivity(self, bus):
        """"""
        if not self.n:
            return
        n = self.nb
        fr = self.a1
        to = self.a2
        os = [0] * self.n

        # find islanded buses
        diag = list(
            matrix(
                spmatrix(self.u, to, os, (n, 1), 'd') +
                spmatrix(self.u, fr, os, (n, 1), 'd')))
        nib = bus.n_islanded_buses = diag.count(0)
        bus.islanded_buses = []
        for idx in range(n):
            if diag[idx] == 0:
                bus.islanded_buses.append(idx)

        # find islanded areas
        temp = spmatrix(
            list(self.u) * 4, fr + to + fr + to, to + fr + fr + to, (n, n),
            'd')
        cons = temp[0, :]
        nelm = len(cons.J)
        conn = spmatrix([], [], [], (1, n), 'd')
        bus.island_sets = []
        idx = islands = 0
        enum = 0

        while 1:
            while 1:
                cons = cons * temp
                cons = sparse(cons)  # remove zero values
                new_nelm = len(cons.J)
                if new_nelm == nelm:
                    break
                nelm = new_nelm
            if len(cons.J) == n:  # all buses are interconnected
                return
            bus.island_sets.append(list(cons.J))
            conn += cons
            islands += 1
            nconn = len(conn.J)
            if nconn >= (n - nib):
                bus.island_sets = [i for i in bus.island_sets if i != []]
                break

            for element in conn.J[idx:]:
                if not diag[idx]:
                    enum += 1  # skip islanded buses
                if element <= enum:
                    idx += 1
                    enum += 1
                else:
                    break

            cons = temp[enum, :]
156700
def get_vert_connectivity(mesh_v, mesh_f):
    """"""

    vpv = sp.csc_matrix((len(mesh_v),len(mesh_v)))

    # for each column in the faces...
    for i in range(3):
        IS = mesh_f[:,i]
        JS = mesh_f[:,(i+1)%3]
        data = np.ones(len(IS))
        ij = np.vstack((row(IS.flatten()), row(JS.flatten())))
        mtx = sp.csc_matrix((data, ij), shape=vpv.shape)
        vpv = vpv + mtx + mtx.T

    return vpv
1039874
def connect_from(self, vertex, weight=1):
        
        for edge in self.edges_in:
            if vertex == edge.vertex_out:
                return edge
        return Edge(vertex, self, weight)
1040156
def neighborhood(self, node, degree=4):
    """"""
    assert self.by_name[node.name] == node
    already_visited = frontier = set([node.name])
    for _ in range(degree):
      neighbor_names = set()
      for node_name in frontier:
        outgoing = set(n.name for n in self.by_input[node_name])
        incoming = set(self.by_name[node_name].input)
        neighbor_names |= incoming | outgoing
      frontier = neighbor_names - already_visited
      already_visited |= neighbor_names
    return [self.by_name[name] for name in already_visited]
1066954
def from_out_edges(cls, vertices, edge_mapper):
        
        vertices = set(vertices)
        edges = set()
        heads = {}
        tails = {}

        # Number the edges arbitrarily.
        edge_identifier = itertools.count()
        for tail in vertices:
            for head in edge_mapper[tail]:
                edge = next(edge_identifier)
                edges.add(edge)
                heads[edge] = head
                tails[edge] = tail

        return cls._raw(
            vertices=vertices,
            edges=edges,
            heads=heads,
            tails=tails,
        )
1114004
def cuts_connections(self, a, b):
        
        n = max(self.indices) + 1
        return self.cut_matrix(n)[np.ix_(a, b)].any()
704943
def make_mesh( coor, ngroups, conns, mesh_in ):
    """"""
    mat_ids = []
    for ii, conn in enumerate( conns ):
        mat_id = nm.empty( (conn.shape[0],), dtype = nm.int32 )
        mat_id.fill( mesh_in.mat_ids[ii][0] )
        mat_ids.append( mat_id )
        
    mesh_out = Mesh.from_data( 'merged mesh', coor, ngroups, conns,
                               mat_ids, mesh_in.descs )
    return mesh_out
477968
def build_groetzch_graph():
    """"""
    # Because the graph is so complicated, we want to
    # build it via adjacency matrix specification
    
    # -- Initialize the matrix to all zeros
    adj = [[0 for _ in range(11)] for _ in range(11)]

    # -- Add individual edge connections
    row_connections = []

    row_connections.append( (1,2,7,10) )
    row_connections.append( (0,3,6,9) )
    row_connections.append( (0,4,6,8) )
    row_connections.append( (1,4,8,10) )
    row_connections.append( (2,3,7,9) )
    row_connections.append( (6,7,8,9,10) )
    row_connections.append( (1,2,5) )
    row_connections.append( (0,4,5) )
    row_connections.append( (2,3,5) )
    row_connections.append( (1,4,5) )
    row_connections.append( (0,3,5) )

    for j, tpl in enumerate(row_connections):
        for i in tpl:
            adj[j][i] = 1
            adj[i][j] = 1
    
    # Debug print the adjacency matrix
    #for row in adj:
    #    print row

    graph, _ = create_graph_from_adjacency_matrix(adj)

    return graph