почему nx.subgraph_view удивительно быстрее, чем G.subgraph (). edge_subgraph ()? - PullRequest
Новая
       32

почему nx.subgraph_view удивительно быстрее, чем G.subgraph (). edge_subgraph ()?

0 голосов
/ 29 января 2020

почему nx.subgraph_view удивительно быстрее, чем G.subgraph().edge_subgraph()?

Прошлой ночью мне просто интересно, как извлечь подграф из исходного графа с помощью NetworkX (python networkx library). Есть два способа его извлечь.

Первый равен nx.subgraph_view(G, filter_node, filter_edge), тип параметра filter_node и filter_edge являются просто функциональными.

Второй равен G.subgraph(nodes).edge_subgraph(edges). Использование метода сцепления, фильтрации узлов и фильтрации ребер. тип параметра nodes и edge - это просто list строки (имя_узла или краевой кортеж)

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

Ниже приведены результаты эксперимента и код для эксперимента.

В заключение, nx.subgraph_view(G, filter_node, filter_edge) примерно в 3000 раз быстрее , чем G.subgraph(nodes).edge_subgraph(edges) Я не могу понять, почему это произошло, даже если я прочитал документацию Networkx.

Если есть кто-нибудь, кто знает, почему это произошло, пожалуйста, скажите мне.

Спасибо за вашу помощь заранее.

Если вы не поняли мои вопросы или не чувствовали себя невежливыми, это вызвано моим отсутствием английского sh. Прости за это.

выход 

== Graph Generation Done
nx.subgraph_view(G)         :     0.000141
G.subgraph().edge_subgraph():     0.485764
========================================

код 

import networkx as nx
import numpy as np
import time

# GENERATE Graph size
N = 1000  # 3000
p = 0.6
G = nx.fast_gnp_random_graph(N, p)

# UPDATE weight-dict for nodes and edges
node_weight_dict = {n: v for n, v in zip(G.nodes(), np.random.uniform(0, 1, len(G.nodes())))}
edge_weight_dict = {e: v for e, v in zip(G.edges(), np.random.uniform(0, 1, len(G.edges())))}
for n in (n for n in G.nodes()):
    G.nodes[n]['weight'] = node_weight_dict[n]
for e, v in edge_weight_dict.items():
    G.edges[e]['weight'] = edge_weight_dict[e]
print("== Graph Generation Done")
#print("==" * 20)

########################################
# USE nx.subgraph_view(G, filter_node, filter_edge)
########################################
start_time = time.time()
nx_subG = nx.subgraph_view(G=G,
                           filter_node=lambda n_name: True
                           if G.nodes[n_name]['weight'] > 0.5 else False,
                           filter_edge=lambda n1_name, n2_name: True
                           if G.edges[
                               (n1_name, n2_name)]['weight'] > 0.5 else False)
#print(G.nodes(data=True))
print(f"nx.subgraph_view(G)         : {time.time() - start_time:12.6f}")
#print(f"FROZEN: {nx.is_frozen(nx_subG)}")
########################################
# G.subgraph().edge_subgraph()
########################################
start_time = time.time()
# make node subg
NODE_subG = G.subgraph(
    nodes=(n for n, n_attr in G.nodes(data=True) if n_attr['weight'] > 0.5))
# make edge subg
subG = NODE_subG.edge_subgraph(
    edges=((e1, e2) for e1, e2, e_attr in NODE_subG.edges(data=True)
           if e_attr['weight'] > 0.5))
print(f"G.subgraph().edge_subgraph(): {time.time() - start_time:12.6f}")
#print(f"FROZEN: {nx.is_frozen(subG)}")
print("=="*20)

assert len(nx_subG.nodes()) == len(subG.nodes())
assert len(nx_subG.edges()) == len(subG.edges())
# Checking isomophism by is_isomorphic is better and exact but it takes much time.
# print(nx.is_isomorphic(subG, nx_subG))
...