Оптимизация Networkx, смежные множества вершин, сокращающиеся подграфы - PullRequest
Новая
       15

Оптимизация Networkx, смежные множества вершин, сокращающиеся подграфы

0 голосов
/ 06 февраля 2019

У меня есть функция, которая возвращает подграф S из G. Я хочу создать граф H, где каждый связанный компонент в S является вершиной в H, и две вершины связаны в H, если междуэти наборы вершин в G.

Сейчас у меня есть кое-что, что работает, но создание H занимает вдвое больше времени, чем создание S. (в основном из-за функций node_boundary и connected_components, согласно cProfile) Этот процесс будетбудет сделано много-много раз, так что я надеюсь побриться хотя бы часть времени.Мне действительно нужен только H, так что я подумывал о создании H без промежуточной функции, но я не мог заставить это работать с сокращением.Проблема в том, что ребра должны выбираться случайным образом из G, но сжатие ребер меняет имена вершин в H, и перевод имени ребра был для меня очень трудным.

Создание S: 

def sp(G):
    nodes = list(G.nodes)
    out = nx.Graph()
    for v in nodes:
        out.add_edge(v, random.choice(list(G.neighbors(v))))
    return out

Создание H из S: 

spr = sp(G)
H = nx.Graph()
bound = []

CC = list(nx.connected_components(spr))
for c in CC:
    H.add_node(CC.index(c))

for c in CC:
    bound.append(nx.node_boundary(G,c))
    for b in bound:
        inter = c.intersection(b)
        if len(inter) > 0:
            H.add_edge(CC.index(c), bound.index(b))

Создание H без S: 

nodes = list(G.nodes)
edges = []
out = G.copy()
for v in nodes:
    edges.append( (v, random.choice(list(G.neighbors(v)))) )

for e in edges:
    out = nx.contracted_edge(out, e)
return out

Ответы [ 2 ]

0 голосов
/ 09 февраля 2019

Я отредактировал твой код.Попробуйте, если это быстрее: 

import networkx as nx
import random

G = nx.random_tree(1000)

def sp(graph, percent_of_edges):
    """returns a subgraph with a certain percentage of edges"""
    out = nx.Graph()
    edges = graph.edges
    sample = random.sample(edges, k = int(len(edges) * percent_of_edges/100))
    out.add_edges_from(sample)
    return out

# Creating H from S
spr = sp(G, 80)
H = nx.Graph()
bound = []

CC = list(nx.connected_components(spr))
H.add_nodes_from(range(len(CC)))

for c in CC:
    bound.append(nx.node_boundary(G, c))

for num1, c in enumerate(CC):
    for num2, b in enumerate(bound):
        if c.intersection(b):
            H.add_edge(num1, num2)
0 голосов
/ 08 февраля 2019

Обычно проще работать с матрицей смежности.Вот быстрый фрагмент грязного кода, который будет выполнять сжатие матрицы при произвольном разбиении.Вы должны быть в состоянии построить свои графики из этого.

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

import numpy as np
import networkx as nx
from itertools import combinations_with_replacement

graph = nx.erdos_renyi_graph(n=40, p=0.05)
A = nx.to_numpy_matrix(graph)

cc_list = [list(cc) for cc in nx.connected_components(graph)]

def matrix_contraction(A, partition):
    contract_A = np.zeros((len(partition), len(partition)))

    for (ipart, ipartidx), (jpart, jpartidx) in combinations_with_replacement(enumerate(partition), 2):
        contract_A[ipart,jpart] = A[ipartidx][:, jpartidx].sum()
        contract_A[jpart,ipart] = A[jpartidx][:, ipartidx].sum()

    return contract_A


contracted_adj_matrix = matrix_contraction(A, cc_list)        




print(cc_list)
print(contracted_adj_matrix)
...