import arcpy, traceback, os, sys
import itertools as itt
sys.path.append(r'C:Usersfelix_pertzigerAppDataRoamingPythonPython27site-packages')
import networkx as nx
RATIO = int(arcpy.GetParameterAsText(0))
tolerance=float(arcpy.GetParameterAsText(1))
try:
    def showPyMessage():
        arcpy.AddMessage(str(time.ctime()) + " - " + message)
# FIND LAYERS
    mxd = arcpy.mapping.MapDocument("CURRENT")
        theNodesLayer = arcpy.mapping.ListLayers(mxd,"nodes")[0]
        theLinksLayer = arcpy.mapping.ListLayers(mxd,"links")[0]
        arcpy.SelectLayerByAttribute_management(theLinksLayer, "CLEAR_SELECTION")
        linksFromI="TARGET_FID"
        linksToI="JOIN_FID"
        G=nx.Graph()
        arcpy.AddMessage("Adding links to graph")
        with arcpy.da.SearchCursor(theLinksLayer, (linksFromI,linksToI,"Times")) as cursor:
                for row in cursor:
                    (f,t,c)=row
                    G.add_edge(f,t,weight=c)
        pops=[row[0] for row in arcpy.da.TableToNumPyArray(theNodesLayer,("P2013"))]
        arcpy.AddMessage("Computing distance matrix")
        length0=nx.all_pairs_dijkstra_path_length(G)

        nNodes=len(pops)
        aBmNodes=[]
        aBig=xrange(nNodes)
        host=[-1]*nNodes

        while True:
                RATIO+=-1
                if RATIO==0:
                        break
                arcpy.AddMessage ('Target ratio %i' %RATIO)
                aBig = set(aBig).difference(set(aBmNodes))
                p=itt.combinations(aBig, 2)
                nBig=len(aBig)
                nTotal=nBig*(nBig-1)/2
                arcpy.SetProgressor("step", "", 0, nTotal,1)
                pMin=1000000
                for a in p:
                        arcpy.SetProgressorPosition()
                        S0,S1=pops[a[0]],pops[a[1]]
                        others=set(aBig).difference(set(a))
                        for i in others:
                                p=pops[i]
                                L0=length0[a[0]][i]
                                L1=length0[a[1]][i]
                                if L0<L1:S0+=p
                                else: S1+=p
                        if S0!=0 and S1!=0:
                                sMin=min(S0,S1)
                                sMax=max(S0,S1)
                                df=abs(float(sMax)/sMin-RATIO)
                                if df<pMin:
                                        pMin=df
                                        aBest=a[:]
                                        arcpy.AddMessage('%s %i : %i = %.2f' %(aBest,sMax,sMin, float(sMax)/sMin))
                                if df<=tolerance:break
                lSmall,lBig,S0,S1=[],[],0,0
                for i in aBig:
                        p=pops[i]
                        L0=length0[aBest[0]][i]
                        L1=length0[aBest[1]][i]
                        if L0<L1:
                                lSmall.append(i)
                                S0+=p
                        else:
                                lBig.append(i)
                                S1+=p

                aBmNodes,m,n=lSmall[:],0,1
                if S0>=S1:
                        aBmNodes,m,n,lBig = lBig[:],1,0,lSmall[:]
                for i in aBmNodes:
                        host[i]=aBest[m]
                for i in lBig:
                        host[i]=aBest[n]
# save results in nodes' table
        with arcpy.da.UpdateCursor(theNodesLayer, "rcvnode") as cursor:
                i=0
                for row in cursor:
                        row[0]=host[i]
                        cursor.updateRow(row)
                        i+=1
                del row, cursor
except:
    message = "n*** PYTHON ERRORS *** "; showPyMessage()
    message = "Python Traceback Info: " + traceback.format_tb(sys.exc_info()[2])[0]; showPyMessage()
    message = "Python Error Info: " +  str(sys.exc_type)+ ": " + str(sys.exc_value) + "n"; showPyMessage()