''' drawgraph
Make a picture of a graph
'''
from math import ceil, floor, sin, cos, pi, sqrt
from graphics import GraphWin, Point, Circle, Line, Text

charMult = .65 # fudge factor to make string fit in circle
sepTangent = 8  # min dist from passing arrow to other vertex circle
minCircleSep = 40 # grows whole pic
arrowMult = .4  # one limit on arrow head size, based on vertex size
lineWidthMin = 2
arrowNSepFactor = .15 #factor of vertex radius for separation of opposite arrows
arrowRSepFactor = .2 # proportion of vertex radius that arrows are away
arrowRSepMin = 3     #   unless their distance goes below this minimum 

def _getW(n):
    '''width in characters for chopped up string of length n
    '''
    return ceil(n/floor(sqrt(n)))

def _splitV(s, w):
    ''' chop s into a roughly square, possibly multiline string.'''
    n = len(s)
    k = ceil(n/w)
    split = [int(round(i*n/k)) for i in range(k+1)]
    lines = [s[split[i]:split[i+1]] for i in range(k)]
    return '\n'.join(lines)
    
def draw(vertices, adjMatrix, isDirected, fontSize = 30, title = "Graph"):
    '''Draw graph in a Tk graphics window.
       vertices:  a sequence of vertex label strings
       adjMatrix:  adjacency matrix in order of vertices
       isDirected:  True if graph is directed
       fontSize:  The font determines the scale of the image
       title:  for the graphics window
    '''
    w = max((_getW(len(v)) for v in vertices)) # width for label chopping
    vertices = [_splitV(v, w) for v in vertices] # split labels
    n = len(vertices)
    A = 2*pi/n  # angle between vertex centers around a big circle
    # r is radius of vertex circles
    r = charMult*fontSize*max(w, 1.2) # fudge factors making string fit
    # R is distance from pic center to vertex centers
    if n > 2: # make sure arrows do not hit other circles
       R = max((r + sepTangent)/(1.0 - cos(A)), (r + minCircleSep/2.0)/sin(A/2))
    elif n == 2:
       R = 1.5*r
    else:
       R = 0
    lim = max(int(R + r + 3), 30 + 8*len(title)) # radius to edge of screen
    circleSep = 2*(R*sin(A/2) - r)
    arrowRSep = max(arrowRSepMin, circleSep*arrowRSepFactor)
    headMin = r*arrowMult
    arrowNSep = r*arrowNSepFactor
    lineWidth = max(lineWidthMin, r/15)

    win = GraphWin(title, 2*lim, 2*lim)
    win.setBackground('white')

    centerCoord = [(R * sin(i*A) + lim, -R * cos(i*A) + lim) for i in range(n)]
    for i, v in enumerate(vertices):
        center = Point(*centerCoord[i])
        c = Circle(center, r)
        c.draw(win)
        tx = Text(center, v)
        tx.setSize(fontSize)
        tx.draw(win)

    for i in range(n):
        (x, y) = centerCoord[i]
        for j in range(n):
            if i == j or not adjMatrix[i][j]: continue
            (ex, ey) = centerCoord[j]
            d = sqrt((x-ex)**2 + (y-ey)**2)
            (ux, uy) = (ex - x)/d, (ey - y)/d # unit vector for edge
            
            shaftLen = d - 2*(r+arrowRSep)
            headSize = min(headMin, shaftLen/1.5)
            (tailX, tailY) = (x + (r+arrowRSep)*ux,  # tail of edge
                              y + (r+arrowRSep)*uy)
            (headX, headY) = (ex - (r+arrowRSep)*ux,     # head of edge
                              ey - (r+arrowRSep)*uy)
            if isDirected:
                (nx, ny) = (-uy, ux)  # normal vector for edge
                if adjMatrix[j][i]: # shift sideways so not on head of reverse
                    tailX += arrowNSep*nx
                    tailY += arrowNSep*ny
                    headX += arrowNSep*nx
                    headY += arrowNSep*ny
            tail = Point(tailX, tailY)
            head = Point(headX, headY)
            ln = Line(tail, head)
            ln.setWidth(lineWidth)
            ln.draw(win)
            if isDirected: # add head arrow
                h1 = Line(head, Point(headX - headSize*ux + headSize*nx,
                                     headY - headSize*uy + headSize*ny))
                h2 = Line(head, Point(headX - headSize*ux - headSize*nx,
                                     headY - headSize*uy - headSize*ny))
                h1.setWidth(lineWidth)
                h2.setWidth(lineWidth)
                h1.draw(win)
                h2.draw(win)   
    return win

# test from graph.py