The person who associated a work with this deed has dedicated the work to the public domain by waiving all of their rights to the work worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law. You can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission.
http://creativecommons.org/publicdomain/zero/1.0/deed.enCC0Creative Commons Zero, Public Domain Dedicationfalsefalse
Source code
fromPADS.SVGimport*fromPADS.StrongConnectivityimport*fromrandomimportrandomfromsysimportstdout# ===================================================# Generate a random graph and random layout# ===================================================n=1000vertices=range(n)edgeprob=1./(n-1)halfG={v:set(wforwinverticesifv<wandrandom()<edgeprob)forvinvertices}G={v:set(wforwinverticesifvinhalfG[w]orwinhalfG[v])forvinvertices}# ===================================================# Pull giant component in and push all the rest out# ===================================================weight={}SCC=StronglyConnectedComponents(G)giant=max(len(C)forCinSCC)forCinStronglyConnectedComponents(G):forvinC:iflen(C)==giant:weight[v]=giantelse:weight[v]=-1# ===================================================# Social gravity# ===================================================D={v:(random()-0.5)+1j*(random()-0.5)forvinvertices}natlength=n**(-0.5)iterations=150increment=0.01foriinrange(iterations):social=0.25forces={v:-D[v]*socialforvinvertices}forvinvertices:forwinvertices:ifv!=w:forces[v]+=(natlength/abs(D[v]-D[w]))**2*(D[v]-D[w])forvinvertices:forwinG[v]:forces[v]+=abs(D[v]-D[w])*(D[w]-D[v])/natlengthforvinvertices:D[v]+=increment*forces[v]# ===================================================# Renormalize# ===================================================minx=min(D[v].realforvinvertices)miny=min(D[v].imagforvinvertices)offset=minx+1j*minyforvinvertices:D[v]-=offsetmaxx=max(D[v].realforvinvertices)maxy=max(D[v].imagforvinvertices)rescale=1./max(maxx,maxy)forvinvertices:D[v]*=rescale# ===================================================# Turn layout into drawing# ===================================================scale=1000radius=6margin=9bbox=scale*(1+1j)defplace(v):returnD[v]*(scale-2*margin)+margin*(1+1j)drawing=SVG(bbox,stdout)drawing.group(style={"stroke":"#000","stroke-width":"2"})forvinvertices:forwinhalfG[v]:drawing.segment(place(v),place(w))drawing.ungroup()drawing.group(fill=colors.red,stroke=colors.black)forvinvertices:drawing.circle(place(v),radius)drawing.ungroup()drawing.close()
Captions
An Erdős–Rényi–Gilbert graph with 1000 vertices at the critical edge probability