Another optimization request :-)

jeffg jeffgemail at gmail.com
Thu Feb 12 02:48:55 CET 2009


If anyone wants to take this on... I would really really like to have
the spring_layout modified to support multi-threading if at all
possible.
My test data is 20,000, which makes this process 20,000 x 20,000 or
400,000,000 (400 million) calculations.  This is taking somewhere
between 2-3 hours an iteration.
I plan to plot out over 1,000,000 data points or more, which would put
this at 1,000,000,000,000 (1 trillion) calculations.  Any help in
making this more efficient would be much appreciated.

def spring_layout(G, iterations=50, dim=2, node_pos=None,
verbose=False):
    """Spring force model layout"""
    if node_pos==None :  # set the initial positions randomly in 1x1
box
        vpos=random_layout(G, dim=dim)
    else:
        vpos=node_pos
    if iterations==0:
        return vpos
    if G.order()==0:
        k=1.0
    else:
        k=N.sqrt(1.0/G.order()) # optimal distance between nodes
    disp={}         # displacements

    # initial "temperature" (about .1 of domain area)
    # this is the largest step allowed in the dynamics
    # linearly step down by dt on each iteration so
    # on last iteration it is size dt.
    t=0.1
    dt=0.1/float(iterations+1)
    for i in range(0,iterations):
        for v in G:
            if verbose==True:
                print("Interation: " + str(i + 1) + ", Calculating: "
+ str(v.encode('iso-8859-15', "replace")))
            disp[v]=N.zeros(dim)
            for u in G:
                delta=vpos[v]-vpos[u]
                dn=max(sqrt(N.dot(delta,delta)),0.01)
                # repulsive force between all
                deltaf=delta*k**2/dn**2
                disp[v]=disp[v]+deltaf
                # attractive force between neighbors
                if G.has_edge(v,u):
                    deltaf=-delta*dn**2/(k*dn)
                    disp[v]=disp[v]+deltaf

        # update positions
        for v in G:
            l=max(sqrt(N.dot(disp[v],disp[v])),0.01)
            vpos[v]=vpos[v]+ disp[v]*t/l
        t-=dt
    return vpos



More information about the Python-list mailing list