1
$\begingroup$

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])
$\endgroup$
6

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ is there any other efficient way of writing those loops so that complexity becomes quadratic time or less @Pål GD $\endgroup$ Commented Jun 4, 2020 at 14:36
  • $\begingroup$ Yes, if you do it my way, you can do it in quadratic time. Feel free to upvote (and accept) the answer if you feel that it answers your question. $\endgroup$
    – Pål GD
    Commented Jun 5, 2020 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.