from PADS.SVG import *
from PADS.StrongConnectivity import *
from random import random
from sys import stdout

# ===================================================
# Generate a random graph and random layout
# ===================================================

n = 1000
vertices = range(n)
edgeprob = 1./(n-1)

halfG = {v : set(w for w in vertices if v<w and random() < edgeprob) for v in vertices}
G = {v : set(w for w in vertices if v in halfG[w] or w in halfG[v]) for v in vertices}

# ===================================================
# Pull giant component in and push all the rest out
# ===================================================
weight = {}
SCC = StronglyConnectedComponents(G)
giant = max(len(C) for C in SCC)
for C in StronglyConnectedComponents(G):
    for v in C:
        if len(C) == giant:
            weight[v] = giant
        else:
            weight[v] = -1

# ===================================================
# Social gravity
# ===================================================

D = {v : (random()-0.5) + 1j* (random()-0.5) for v in vertices}
natlength = n**(-0.5)
iterations = 150
increment = 0.01

for i in range(iterations):
    social = 0.25
    forces = {v : -D[v]*social for v in vertices}

    for v in vertices:
        for w in vertices:
            if v != w:
                forces[v] += (natlength/abs(D[v]-D[w]))**2*(D[v]-D[w])

    for v in vertices:
        for w in G[v]:
            forces[v] += abs(D[v]-D[w])*(D[w]-D[v])/natlength

    for v in vertices:
        D[v] += increment * forces[v]

# ===================================================
# Renormalize
# ===================================================

minx = min(D[v].real for v in vertices)
miny = min(D[v].imag for v in vertices)
offset = minx + 1j*miny
for v in vertices:
    D[v] -= offset

maxx = max(D[v].real for v in vertices)
maxy = max(D[v].imag for v in vertices)
rescale = 1./max(maxx,maxy)
for v in vertices:
    D[v] *= rescale

# ===================================================
# Turn layout into drawing
# ===================================================

scale = 1000
radius = 6
margin = 9
bbox = scale*(1+1j)

def place(v):
    return D[v]*(scale-2*margin) + margin*(1+1j)

drawing = SVG(bbox,stdout)

drawing.group(style={"stroke":"#000","stroke-width":"2"})
for v in vertices:
    for w in halfG[v]:
        drawing.segment(place(v),place(w))
drawing.ungroup()

drawing.group(fill=colors.red,stroke=colors.black)
for v in vertices:
    drawing.circle(place(v),radius)
drawing.ungroup()

drawing.close()