Add an edge to a graph to minimize the average shortest path length

Question

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|V\right|\$ 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

Answer 1

First things first:

while nloops<=llno:
    if __name__ == '__main__':

would make more sense with the order reversed; and

def f(l1,l2, q, r, s):
    ...
    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()

has a race condition which makes the results untrustworthy. It probably makes more sense for each process to produce its output independently, rather than to synchronise access to the queues.

---

    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)): 

itertools also has combinations, which will give you unordered pairs of elements.

---

The overall complexity: this is doing \$\Theta(V^2)\$ iterations of average_shortest_path_length. Since it's a sparse graph, the best case is that average_shortest_path_length takes \$\Theta(VE + V^2\lg V)\$. But I wouldn't be surprised if the generic average_shortest_path_length uses a \$\Theta(V^3)\$ algorithm such as Floyd-Warshall. So overall, it's probably \$\Theta(V^5)\$.

If instead you do one calculation of all-pairs-shortest-paths on the original graph (let's be pessimistic and say \$\Theta(V^3)\$) and store the result as \$d\$, then for each candidate inserted edge \$(u,v)\$ and each pair of edges \$(x,y)\$ the shortest distance in the modified graph is \$\min(d(x,y), d(x,u)+1+d(v,y))\$. So by brute force you can get a \$\Theta(V^4)\$ algorithm.

An obvious heuristic is to pick a pair of points which are the furthest apart and insert the edge between them. By doing this first and aborting the analysis of \$(u,v)\$ when you exceed the best score found so far, there will probably be a reasonable speedup.

I would expect that there might be further improvements which would reduce the asymptotic complexity.