%% Macros for Computational Theory diagrams %% by Russ Ross %% Last revised September 2015 verbatimtex \documentclass [10pt]{article} \usepackage{amsmath} \begin {document} etex; % set up for huge nodes def hugenodes = node_radius := 0.5cm; final_radius := node_radius-.075cm; loop_size := 0.7cm; loop_emerge := 9; ahlength := 4bp; edgecolor := black; edgedash := 0; edgedirected := 1; curve := 25; enddef; % set up for big nodes (default) def bignodes = node_radius := 0.35cm; final_radius := node_radius-.05cm; loop_size := node_radius * 2; loop_emerge := 9; ahlength := 3bp; edgecolor := black; edgedash := 0; edgedirected := 1; curve := 25; enddef; % set up for medium nodes def mediumnodes = node_radius := 0.25cm; final_radius := 0.2cm; loop_size := 0.5cm; loop_emerge := 9; ahlength := 3bp; edgecolor := black; edgedash := 0; edgedirected := 1; curve := 25; enddef; % set up for small nodes def smallnodes = node_radius := 0.15cm; final_radius := 0.1cm; loop_size := 0.5cm; loop_emerge := 9; ahlength := 2bp; edgecolor := black; edgedash := 0; edgedirected := 1; curve := 25; enddef; % set up for tiny nodes def tinynodes = node_radius := 0.1cm; final_radius := 0.05cm; loop_size := 0.1cm; loop_emerge := 9; ahlength := 2bp; edgecolor := black; edgedash := 0; edgedirected := 1; curve := 25; enddef; % set up for mini nodes def mininodes = node_radius := 0.05cm; final_radius := 0.05cm; loop_size := 0.1cm; loop_emerge := 9; ahlength := 2bp; edgecolor := black; edgedash := 0; edgedirected := 1; curve := 25; enddef; % to change all lines (including boxes): % drawoptions(withcolor blue) % drawoptions(dashed evenly) % % to reset: % drawoptions() % change edge colors def rededges = edgecolor := red enddef; def blueedges = edgecolor := blue enddef; def greenedges = edgecolor := green enddef; def blackedges = edgecolor := black enddef; % change between dashed and solid edges def dashededges = edgedash := 1 enddef; def solidedges = edgedash := 0 enddef; % change between arrows and lines def directededges = edgedirected := 1 enddef; def undirectededges = edgedirected := 0 enddef; % set up some handy labels picture A, B, AB, C, E, K, N, X, Y, Z, ZERO, ONE, ZEROONE, SIGMA, EMPTYSET, CDOTS, VDOTS, SQCUP, BLANK, BIGGEST; A = btex $a$ etex; B = btex $b$ etex; AB = btex $a,b$ etex; C = btex $c$ etex; E = btex $\varepsilon$ etex; K = btex $k$ etex; N = btex $n$ etex; X = btex $x$ etex; Y = btex $y$ etex; Z = btex $z$ etex; ZERO = btex $0$ etex; ONE = btex $1$ etex; ZEROONE = btex $0,1$ etex; SIGMA = btex $\Sigma$ etex; EMPTYSET = btex $\emptyset$ etex; CDOTS = btex $\cdots$ etex; VDOTS = btex $\vdots$ etex; SQCUP = btex $\sqcup$ etex; BLANK = nullpicture; % other letters will be put into a box big enough for % this letter when using tape squares BIGGEST = B; % create (but don't actually draw) a node, e.g.: % node.a("a"); % The node is a circle from the "boxes" package % use drawboxed(a,b,c); drawunboxed(a,b,c); drawboxes(a,b,c); to render nodes vardef node@#(text tt) = circleit@#(tt); @#e-@#c = (node_radius,0); @#n-@#c = (0,node_radius) enddef; % draw a smaller circle inside some nodes, making them final states def makefinal(text t) = forsuffixes s=t: draw s.c + (final_radius,0) .. s.c + (0,final_radius) .. s.c - (final_radius,0) .. s.c - (0,final_radius) .. cycle; endfor enddef; % draw a start symbol to the left of some nodes, making them start states def makestart(text t) = forsuffixes $=t: draw ((-.8,.8)--(0,0)--(-.8,-.8)) scaled node_radius shifted$.w; endfor enddef; % draw a start symbol above some nodes def makestart_top(text t) = forsuffixes s=t: draw ((-.8,.8)--(0,0)--(.8,.8)) scaled node_radius shifted s.n; endfor enddef; % internal macro used for placing a label % the label is placed at p, pushed along % the direction vector far enough that the bbox % just touches p def put_label(expr anchorpath, anchorpoint, movedir)(text lab) = begingroup; save pic, nudgedir, shiftedpath; picture pic; pair nudgedir; path shiftedpath; % move the path enough to create a bit of whitespace shiftedpath := anchorpath shifted ((unitvector movedir) scaled bboxmargin); % start with a centered picture if string lab: pic := lab infont defaultfont scaled defaultscale; pic := pic shifted -center(pic) elseif picture lab: pic := lab shifted -center(lab) else: pic := nullpicture fi; if length (ulcorner pic - lrcorner pic) = 0: setbounds pic to (1,1) -- (1,-1) -- (-1,-1) -- (-1,1) -- cycle fi; % xpart of movedir scaled by the width of the label, ypart scaled by the % height of the label nudgedir := unitvector (xpart movedir * xpart urcorner pic, ypart movedir * ypart urcorner pic) scaled 0.1bp; % shift the center of the picture in the requested direction pic := pic shifted anchorpoint; % now nudge it repeatedly until there are no more intersections forever: exitif (-1, -1) = shiftedpath intersectiontimes (ulcorner pic -- urcorner pic -- lrcorner pic -- llcorner pic -- cycle); pic := pic shifted nudgedir; endfor; draw pic endgroup enddef; % draw an edge between two nodes. A few ways to use it: % edge(start,end,curve,"label"); % curved, labeled edge % edge(start,end,45,"label"); % curved edge with a specific angle % edge(start,end,left,"label"); % straight edge with the label to the left % edge(start,end,curve,BLANK); % curved edge with no label % edge(start,end,left,BLANK); % straight edge with no label def edge(suffix from, to)(expr direction)(text lab) = begingroup; save pth,z; save edgedir; numeric edgedir; path pth; pair z[]; z0 = from.c; z1 = to.c; z2 = z1-z0; % "direction" is an angle for curves, or the direction to shift the label % for straight edges if pair direction : edgedir := 0 else : edgedir := direction fi; pth = z0{dir ((angle z2) + edgedir)} ... {dir ((angle z2) - edgedir)}z1 cutbefore bpath.from cutafter bpath.to; % half way along the curve z3 = point .5 of pth; % direction to shift label (as a vector) if pair direction: z3 := z3 - unitvector z2 scaled if edgedirected = 1: 0.5 ahlength else: 0 fi; z4 := z2 rotated ((angle direction) - 90) else: z4 := z3 - (1/2[z0,z1]) fi; put_label(pth, z3, z4, lab); if edgedirected = 1: drawarrow else: draw fi pth withcolor edgecolor if edgedash = 1: dashed evenly fi endgroup enddef; % draw a straight edge between two nodes. % sedge(start,end); def sedge(suffix from, to) = edge(from, to, left, BLANK) enddef; % draw a loop: % loop(node,up,"label"); % labeled loop going up % loop(node,right,BLANK); % unlabeled loop to the right def loop(suffix from)(expr direction)(text lab) = begingroup save p,z,n; path p; pair z[]; z0 = from.c; z1 = unitvector direction scaled (loop_size + node_radius) shifted z0; z2 = unitvector (direction rotated loop_emerge) scaled node_radius shifted z0; z3 = unitvector (direction rotated -loop_emerge) scaled node_radius shifted z0; p = z0...z2...z1...z3...z0 cutbefore bpath.from cutafter bpath.from; % draw the label put_label(p, z1, direction, lab); if edgedirected = 1: drawarrow else: draw fi p withcolor edgecolor if edgedash = 1: dashed evenly fi endgroup enddef; % start a group of boxes joined left-to-right def begintape = boxjoin(a.e = b.w) enddef; % start a group of boxes joined top-to-bottom def beginverticaltape = boxjoin(a.s = b.n) enddef; % end a group of joined boxes def endtape = boxjoin() enddef; % create (but don't actually draw) a tape square, e.g.: % tapesquare.a("a"); % The node is a box from the "boxes" package % use drawboxed(a,b,c); drawunboxed(a,b,c); drawboxes(a,b,c); to render nodes vardef tapesquare@#(text in) = boxit@#(begingroup save l, r, t, b, p; picture p; % make sure we have a picture if string in: p := in infont defaultfont scaled defaultscale; p := p shifted -(xpart center p, 0) elseif picture in: p := in shifted -(xpart center in, 0) else: p := nullpicture fi; % put the picture in a square box, or one wide enough to fit the label r = -l = .5 * if (ypart ulcorner BIGGEST - ypart llcorner BIGGEST) > (xpart urcorner p - xpart ulcorner p): (ypart ulcorner BIGGEST - ypart llcorner BIGGEST) else: (xpart urcorner p - xpart ulcorner p) fi; t = ypart ulcorner BIGGEST; b = ypart llcorner BIGGEST; setbounds p to (l,b)--(r,b)--(r,t)--(l,t)--cycle; p endgroup) enddef; % add an open-ended square with CDOTS to the right of given square def tapecontinueright(text in) = draw in.ne -- in.ne + (in.ne - in.nw); draw in.se -- in.se + (in.se - in.sw); label.rt(CDOTS, in.e) enddef; % add an open-ended square with CDOTS to the left of given square def tapecontinueleft(text in) = draw in.nw -- in.nw - (in.ne - in.nw); draw in.sw -- in.sw - (in.se - in.sw); label.lft(CDOTS, in.w) enddef; % draw a line across the bottom of the given square, extending out % beyond the edges to mark the bottom of a stack def stackbottom(text in) = draw in.sw - 0.5(in.s - in.sw) -- in.se + 0.5(in.se - in.s) enddef; % draw a box with the given left, right, top, and bottom positions def drawbox(expr l,r,t,b) = draw (l,t)--(r,t)--(r,b)--(l,b)--cycle enddef; % draw an arrow with the ends clipped def shortarrow(expr a, b, eps) = drawarrow a -- b cutbefore fullcircle scaled eps shifted a cutafter fullcircle scaled eps shifted b enddef; % set default starting values color edgecolor; numeric edgedirected, edgedash; bignodes;