how to reduce the time complexity of this code?
-
29-09-2020 - |
Question
I have a graph G=(V,E)
. A list of nodes NODE
subset of V
. I want to find out all the neighbor nodes of each node in NODE
and add edge if those neighbors have distance greater than 2. Can anyone here please help me to reduce the time complexity of this code to quadratic time or less.
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])
Solution
To get quadratic time, do the following:
Let $M = N(\text{NODE})$ be the neighbours of NODE in $G$.
Compute $G' = (G - \text{NODE})^3$, the 2nd power graph of $G$ without the vertices from NODE.
Then you do the following: For every two vertices $u$ and $v$ in $M$, if $uv \notin E(G')$, add $uv$ to $G$.
This way you don't have to compute shortest_path
anymore.
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange