¿Cómo reducir la complejidad temporal de este código?
-
29-09-2020 - |
Pregunta
tengo un grafico G=(V,E)
.Una lista de nodos NODE
subconjunto de V
.Quiero conocer todos los nodos vecinos de cada nodo en NODE
y agregue borde si esos vecinos tienen una distancia mayor que 2.¿Alguien aquí puede ayudarme a reducir la complejidad temporal de este código a tiempo cuadrático o menos?
import networkx as nx
import random
G = nx.erdos_renyi_graph(30, 0.05)
node=[]
for j in range(5):
node.append(random.randint(1,30))
for i in node:
lst=list(G.neighbors(i))
if(len(lst)>1):
for j in range(len(lst)):
for k in range(j+1,len(lst)):
if(len(nx.shortest_path(G,lst[j],lst[k]))>2):
G.add_edge(lst[j],lst[k])
Solución
Para obtener el tiempo cuadrático, haga lo siguiente:
Dejar $M = N( ext{NODO})$ ser los vecinos de NODE en $g$.
Calcular $G' = (G - ext{NODO})^3$, el 2do gráfico de potencia de $g$ sin los vértices de NODE.
Luego haces lo siguiente:Por cada dos vértices $u$ y $v$ en $M$, si $uv otin E(G')$, agregar $uv$ a $g$.
De esta manera no tienes que calcular shortest_path
ya no.
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange