trjhtr

This program is used to find the nodes in a grid network, between which, if an edge is added, the average shortest path length of the entire grid reduces by the most.

"Average shortest path length" is the statistic computed by the NetworkX function average_shortest_path_length, that is, $$ sum_s,t∈V d(s, t) over n(n-1) $$ where $V$ is the set of nodes, $n = left|Vright|$ is the number of nodes, and $d(s, t)$ is the length of the shortest path from $s$ to $t$.

My original program was taking a long time to execute so I decided to make a multiprocessing program, but it is taking even more time than the original one.

So the function that is called by the processes needs to return three values: distance, node1, and node2; and so I used three queues for that. Now I need to get the values of node1 and node2 for which the distance is minimum(of the four processes. I used a while and a for loop just to get those two nodes.

I believe this must be the reason for the slow execution of my program. So is there a better way to get the nodes with minimum distance?

import networkx as nx
import itertools

no_of_nodes = 4

no_of_links = 4

#generates a grid of size specified
G = nx.grid_graph(dim=[no_of_nodes,no_of_nodes], periodic=False)

#for APL
distance=nx.average_shortest_path_length(G)

#to keep track of how many links have been added
nloops=1

def f(l1,l2, q, r, s):

 distance=nx.average_shortest_path_length(G)
 for x,y in itertools.product(range(no_of_nodes), range(no_of_nodes)):
 for i,j in itertools.product(range(l1,l2), range(no_of_nodes)): 
 #if loop to prevent self loops and multilinks
 if (i,j) not in G[(x,y)] and (i,j)!=(x,y):
 G.add_edge((x, y), (i, j))
 newdistance= nx.average_shortest_path_length(G)
 G.remove_edge((x, y), (i, j))
 if newdistance<distance:
 distance= newdistance
 node1a=x
 node1b=y
 node2a=i
 node2b=j

 q.put(distance)
 r.put((node1a, node1b))
 s.put((node2a, node2b))


while nloops<=llno:
 if __name__ == '__main__':
 q = Queue()
 r = Queue()
 s = Queue()

 p1 = Process(target=f, args=(0, no_of_nodes/4, q, r, s))
 p1.start() 
 p2 = Process(target=f, args=(no_of_nodes/4, no_of_nodes/2, q, r, s))
 p2.start()
 p3 = Process(target=f, args=(no_of_nodes/2, 3*no_of_nodes/4, q, r, s))
 p3.start()
 p4 = Process(target=f, args=(3*no_of_nodes/4, no_of_nodes, q, r, s))
 p4.start()

 min_d = 100
 count = 0
 dists= 
 nodesa= 
 nodesb= 

 while count<4:
 dists.append(q.get())
 nodesa.append(r.get())
 nodesb.append(s.get())
 count+=1
 for x in range(4):
 if dists[x]<min_d:
 min_d=dists[x]
 n1a=nodesa[x]
 n2a=nodesb[x]
 print (min_d, n1a, n2a)
 G.add_edge(n1a, n2a)

In the sequential solution, it was possible to find the nodes with minimum distance from the function itself, unlike multiprocessing where it can't be found from the function because I need all possible cases from the four processes.

import networkx as nx
import itertools

no_of_nodes = 4

no_of_links = 4

#generates a grid of size specified 
G = nx.grid_graph(dim=[no_of_nodes,no_of_nodes], periodic=False)

#for APL
distance=nx.average_shortest_path_length(G)

#to keep track of how many links have been added
nloops=1

while nloops<=llno:
 for x,y in itertools.product(range(no_of_nodes), range(no_of_nodes)):
 for i,j in itertools.product(range(x,no_of_nodes), range(no_of_nodes)): 
 #if loop to prevent self loops and multilinks
 if (i,j) not in G[(x,y)] and (i,j)!=(x,y):
 G.add_edge((x, y), (i, j))
 newdistance= nx.average_shortest_path_length(G)
 if newdistance<distance:
 distance= newdistance
 node1a=x
 node1b=y
 node2a=i
 node2b=j
 #removes the last added edge
 G.remove_edge((x, y), (i, j))

print "minimum APL = ",distance, " node 1 =",(node1a, node1b), " node 2=" ,(node2a, node2b) 
G.add_edge((node1a, node1b), (node2a, node2b))

nloops+=1