''' 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