эффективная проекция двудольного графа в python (с использованием networkx)

Question

Используя модуль networkx, я делаю некоторый сетевой анализ в Python 3.2, где мне нужно спроецировать двудольный граф (заключенных, связанных с их ячейкой: входной граф B в коде ниже) на подграф (связывающий сокамерников друг с другом если оба имеют заклинание с перекрытием в одной и той же ячейке: использование входных данных множества узлов, определяющих узлы-заключенные графа B, генерирует выходной граф G). Мне не нужен специальный алгоритм, чтобы найти какое-либо или оптимальное соответствие, мне просто нужно собрать все ссылки, которые удовлетворяют некоторым условиям. Таким образом, другие SO сообщения, которые я нашел, на самом деле не применяются. Но:

Мой текущий код взрывается (RAM, swap и CPU), поскольку я даю ему все больше и больше данных. Пожалуйста, дайте мне знать, если вы видите способы упростить код ниже с 5 слоями циклов. Я не уверен, что нужны какие-либо знания о networkx или что у меня есть соответствующие сведения о моей маркировке пограничных атрибутов. Спасибо!

def time_overlap_projected_graph_parallel(B, nodes):
    G=nx.MultiGraph()
    G.add_nodes_from((n,B.node[n]) for n in nodes)
    for u in nodes:
        unbrs = set(B[u])
        nbrs2 = set((n for nbr in unbrs for n in B[nbr])) - set([u])
        for v in nbrs2:
            for mutual_cell in set(B[u]) & set(B[v]):
                for uspell in B.get_edge_data(u,mutual_cell).values():
                    ustart = uspell[1]
                    uend = uspell[2]
                    for vspell in B.get_edge_data(v,mutual_cell).values():
                        vstart = vspell[1]
                        vend = vspell[2]
                        if uend > vstart and vend > ustart:
                            ostart = max(ustart,vstart)
                            oend = min(uend,vend)
                            olen = (oend-ostart+1)/86400
                            ocell = mutual_cell
                            if (v not in G[u] or ostart not in [ edict[1] for edict in G[u][v].values() ]):
                                G.add_edges_from([(u,v,{0: olen,1: ostart,2: oend,3: ocell})])
    return G

Answer 1

Теперь можно использовать двудольные графы.Как

import networkx as nx
from networkx.algorithms import bipartite

B.add_nodes_from(inmates_list, bipartite=0)
B.add_nodes_from(cells_list, bipartite=1)

inmates = set(n for n,d in B.nodes(data=True) if d['bipartite']==0)
cells = = set(B) - inmates
G = bipartite.projected_graph(B, inmates)

(http://networkx.lanl.gov/reference/algorithms.bipartite.html)

Answer 2

Я публикую этот ответ, чтобы предложить несколько улучшений. Я предполагаю, что ваш двудольный граф не мультиграф, а нормальный nx.Graph. Я изменил B на bi и G на uni, поскольку имена в верхнем регистре зарезервированы для классов по соглашению. Кстати, что если заклинания начинаются и заканчиваются в одно и то же время?

def time_overlap_projected_graph_parallel(bi, nodes):
    uni = nx.MultiGraph()
    for u in nodes: #inmate
        uni.add_node(u) # do this to prevent iterating nodes twice
        u_adj = bi.adj[u] # bi.adj is a dict of dicts
        for (w, uw_attr) in u_adj.iteritems(): # cell
            w_adj = bi.adj[w]
            for (v, wv_attr) in w_adj.iteritems():#cellmate
                if v == u:
                    continue
                elif uni.has_edge(u, v): # avoid computing twice
                    continue
                for uspell in uw_attr.itervalues():
                    ustart = uspell[1]
                    uend = uspell[2]
                    for vspell in wv_attr.itervalues():
                        vstart = vspell[1]
                        vend = vspell[2]
                        if uend > vstart and vend > ustart:
                            ostart = max(ustart, vstart)
                            oend = min(uend, vend)
                            olen = (oend - ostart + 1) / 86400 # this assumes floats or Python 3 otherwise will be 0
                            ocell = w
                            # I would change this to uni.add_edge(u, v, length=olen, start=ostart, end=oend, cell=ocell)
                            # or to uni.add_edge(u, v, spell=[olen, ostart, oend, ocell])
                            uni.add_edge(u, v, **{0: olen, 1: ostart, 2: oend, 3: ocell})
    return uni

Answer 3

Вот мой дубль. В зависимости от среднего числа заключенных на одну камеру, это может улучшить производительность. Если у вас есть лучший способ получить ячейки (например, свойства узла?), Замените

cells = [n for n in B.nodes() if n[0] not in nodes]

с этим (здесь я предполагаю, что узлы - это список всех заключенных).

from itertools import combinations

def time_overlap_projected_graph_parallel(B, nodes):
    G=nx.MultiGraph()
    G.add_nodes_from((n,B.node[n]) for n in nodes)
    cells = [n for n in B.nodes() if n[0] not in nodes]
    for cell in cells:
        for u,v in combinations(B[cell],2):
            for uspell in B.get_edge_data(u,cell).values():
                ustart = uspell[1]
                uend = uspell[2]
                for vspell in B.get_edge_data(v,cell).values():
                    vstart = vspell[1]
                    vend = vspell[2]
                    if uend > vstart and vend > ustart:
                        ostart = max(ustart,vstart)
                        oend = min(uend,vend)
                        olen = (oend-ostart+1)/86400
                        ocell = cell
                        if (v not in G[u] or ostart not in [ edict[1] for edict in G[u][v].values() ]):
                            G.add_edge(u,v,{0: olen,1: ostart,2: oend,3: ocell})
    return G

Answer 4

Рассмотрим пересмотренный код, который может делать то же самое, но с итераторами (хотя я также пересмотрел несколько вызовов функций / методов, связанных с сетью x, но я все еще проверяю, не сломал ли я что-то):

def time_overlap_projected_graph_parallel(B, nodes):
    G=nx.MultiGraph()
    G.add_nodes_from(nodes)
    for u in G.nodes_iter():#inmate
        for w in B.neighbors_iter(u):#cell
            for v in B.neighbors_iter(w):#cellmate
                if v == u:
                    continue
                for uspell in B[u][w].values():
                    ustart = uspell[1]
                    uend = uspell[2]
                    for vspell in B[v][w].values():
                        vstart = vspell[1]
                        vend = vspell[2]
                        if uend > vstart and vend > ustart:
                            ostart = max(ustart,vstart)
                            oend = min(uend,vend)
                            olen = (oend-ostart+1)/86400
                            ocell = w
                            if (v not in G[u] or ostart not in [ edict[1] for edict in G[u][v].values() ]):
                                G.add_edges_from([(u,v,{0: olen,1: ostart,2: oend,3: ocell})])
    return G