# Cayley Graph of Free Group in TikZ

What is the best way to create a TikZ picture which resembles the image below (Caylay Graph of a free group) without using absolute positions and doing everything "manually"?

The picture has a very recursive structure, so I figured there might be a more efficient way to do it using automatic generation. Am I right?

• Yes, check out the lindenmayer section of the PGF Manual. – percusse Jan 13 '15 at 11:23

And here is an example using the lindenmayersystems library. It requires the latest PGF release for the arrows.meta library.

\documentclass[tikz,border=5]{standalone}
\usetikzlibrary{lindenmayersystems,arrows.meta}
\pgfdeclarelindenmayersystem{cayley}{
\rule{A -> B [ R [A] [+A] [-A] ]}
\symbol{R}{ \pgflsystemstep=0.5\pgflsystemstep }
\symbol{-}{
\tikzset{rotate=90}
}
\symbol{+}{
\tikzset{rotate=-90}
}
\symbol{B}{
\draw [dot-cayley] (0,0) -- (\pgflsystemstep,0)
node [font=\footnotesize, midway,
{\ifcase\quadrant$a$\or$b$\or$a^{-1}$\or$b^{-1}$\fi};
\tikzset{xshift=\pgflsystemstep}
}
}
\tikzset{
dot/.tip={Circle[sep=-1.5pt,length=3pt]}, cayley/.tip={Stealth[]dot[]}
}
\begin{document}
\begin{tikzpicture}
\draw l-system [l-system={cayley, axiom=[A] [+A] [-A] [++A], step=5cm, order=4}];
\end{tikzpicture}
\end{document}


And if the labels aren't required (or the arrows) then it can be even simpler:

\documentclass[tikz,border=5]{standalone}
\usetikzlibrary{lindenmayersystems}
\pgfdeclarelindenmayersystem{cayley}{
\rule{F -> F [ R [F] [+F] [-F] ]}
\symbol{R}{
\pgflsystemstep=0.5\pgflsystemstep
}
}
\begin{document}
\begin{tikzpicture}
\draw l-system [l-system={cayley, axiom=[F] [+F] [-F] [++F], step=5cm, order=6}];
\end{tikzpicture}
\end{document}


and by using:

\draw l-system [l-system={cayley, axiom=[F] [+F] [-F] [++F] [--F],
angle=72, step=5cm, order=6}];


the result is

and

\draw l-system [l-system={cayley, axiom=[F] [+F] [-F], angle=120,step=5cm, order=6}];


gives

Finally, as requested in the comments, here is a version with starts off with an angle of 90 degrees and after the first iteration switches to a custom angle. It wasn't clear what the logic for the labelling is in this case so the lines are labelled with their angles (for which a bit of messing around was required):

\documentclass[tikz,border=5]{standalone}
\usetikzlibrary{lindenmayersystems,arrows.meta,calc}
\def\tikzpoint{\csname tikz@scan@one@point\endcsname\pgfpointtransformed}
\pgfdeclarelindenmayersystem{cayley}{
\rule{A -> B [ R [A] [+A] [-A] ]}
\symbol{R}{ \pgflsystemstep=0.5\pgflsystemstep }
\symbol{>}{\tikzset{rotate=90}}
\symbol{B}{
\pgfmathanglebetweenpoints{\tikzpoint(0,0)}{\tikzpoint(\pgflsystemstep,0)}
\pgfmathparse{int(round(\pgfmathresult))}%
\let\lineangle=\pgfmathresult
\draw [dot-cayley] (0,0) -- (\pgflsystemstep,0)
node [pos=2/3, transform shape, font=\tiny, above] {$\lineangle$};
\tikzset{xshift=\pgflsystemstep}
}
}
\tikzset{
dot/.tip={Circle[sep=-1.5pt,length=3pt]}, cayley/.tip={Stealth[]dot[]}
}
\begin{document}
\begin{tikzpicture}
\draw l-system [l-system={cayley, axiom=[A] [>A] [>>A] [>>>A], step=5cm, angle=60, order=4}];
\end{tikzpicture}
\end{document}


• Your solution is far more elegant than my own approach using a Lindenmayer system. Thank you very much! Still, it would be nice to be able to specify angle and to display the labels nevertheless (ideally, while maintaining the 90 degree angle for the first "recursion") – JPW Jan 14 '15 at 10:58
• @JPW part of what you want is easy. Just add \symbol{>}{ \pgftransformrotate{-90} } and \symbol{<}{ \pgftransformrotate{90} } to the lindenmayer system definition. Then you can use axiom=[F] [>F] [<F] [>>F], angle=72 and the angle first step will be 90 degrees and then 72 from then on. – Mark Wibrow Jan 14 '15 at 11:27
• the 5-fold example unfortunately has overlaps when done this way... – yo' Jan 17 '15 at 20:13
• @yo' so change the reduction in the step (i.e., the R) symbol. For example, using \symbol{R}{\pgfmathsetlength\pgflsystemstep{4/9*\pgflsystemstep}} will produce no overlap. A constant factor would be quite easy to parametrize as a key. – Mark Wibrow Jan 18 '15 at 10:17
• Sorry if I was unclear about the labeling. The labels should not change when using angle, only the node positions. – JPW Jan 19 '15 at 8:16

Here is one possibility using tikzmath, but probably not "the best way".

\documentclass[border=7mm]{standalone}
\usepackage{tikz}
\usetikzlibrary{calc,math}
\tikzmath{
% function that draws the edge (\x1,\y1) -- (\x2,\y2)
%   with label depending on: \l=0 => "a", \l=1 => "b"
%   \c is a count downd counter, we stop at \c=0
function drawgen(\x1,\y1,\x2,\y2,\c,\l)
coordinate \p;
\p1 = (\x1 pt,\y1 pt);\p2 = (\x2 pt,\y2 pt);
if (\l < .5) then {let \g=a;let \a=above;} else {let \g=b;let \a=right;};
if (\x1 > \x2 || \y1 > \y2 ) then {let \e=^{-1};} else {let \e={};};
{
\draw[draw=red,-latex] (\px1,\py1)  -- node[\a,pos=.55]{$\g\e$} (\px2,\py2);
};
if (\c > 0) then {
\c = \c-1;
\p3 = 1.5*(\px2,\py2)-.5*(\px1,\py1);
drawgen(\px2,\py2,\px3,\py3,\c,\l);
\p3 = (\px2,\py2)+.5*(\py2,\px2)-.5*(\py1,\px1);
drawgen(\px2,\py2,\px3,\py3,\c,1-\l);
\p3 = (\px2,\py2)-.5*(\py2,\px2)+.5*(\py1,\px1);
drawgen(\px2,\py2,\px3,\py3,\c,1-\l);
};
};
}
\begin{document}
\begin{tikzpicture}
\tikzmath{
\d=5cm; \n=3;
drawgen(0,0,\d,0,\n,0);
drawgen(0,0,-\d,0,\n,0);
drawgen(0,0,0,\d,\n,1);
drawgen(0,0,0,-\d,\n,1);
}
\end{tikzpicture}
\end{document}


UPDATE 1: In my first version, I forgot the $^{-1}$. So I added the following line:

if (\x1 > \x2 || \y1 > \y2 ) then {let \e=^{-1};} else {let \e={};};


to set the power to -1 for edges going down and right. And as some overlaps appeared, I adjusted the edge label position.

UPDATE 2: As everybody goes with his own unlabeled method, here is one with math tikz library.

\documentclass[border=7mm]{standalone}
\usepackage{tikz}
\usetikzlibrary{calc,math}
\begin{document}
\begin{tikzpicture}[scale=.02pt]
\tikzmath{
\power=2; \deviation=90; \numsteps=7; let \startcolor=green; let \endcolor=red;
function branch(\x,\y,\rotate,\step){ \step=\step-1;
if (\step >= 0) then { \mix = int(100*\step/(\numsteps-1));
{\draw[shift={(\x pt,\y pt)},scale=\power^\step, rotate=\rotate, color=\startcolor!\mix!\endcolor]
(0,0)--(1,0) coordinate(newbase);};
coordinate \b; \b1 = (newbase);
for \a in {-\deviation,0,\deviation}{
branch(\bx1,\by1,mod(\rotate+\a,360),\step);
};
};
};
for \angle in {0,90,180,-90}{
branch(0,0,\angle,\numsteps);
};
}
\end{tikzpicture}
\end{document}


With the parameters:

\power=2.3; \deviation=70; \numsteps=7; let \startcolor=magenta; let \endcolor=black;


With the parameters:

\power=2.5; \deviation=120; \numsteps=7; let \startcolor=black; let \endcolor=orange;


## Second proposition

If arrows and labels are not required, here is a very simple recursive solution using a single path, at order 8 (if you try order 9, pdflatex stops with an error: TeX capacity exceeded...).

\documentclass[tikz]{standalone}
\usetikzlibrary{calc}
\newcommand\caley[3]{% level, length, angle
\ifnum0<#1 \pgfextra{
\pgfmathtruncatemacro\newlev{#1-1}
\pgfmathsetmacro\len{#2}
\pgfmathtruncatemacro\angle{#3}
} -- ++(\angle:\len pt)
\foreach \a in {-90,0,90}{\caley{\newlev}{\len/2}{\angle+\a}} ++(\angle:-1*\len pt)
\fi%
}
\begin{document}
\tikz \draw[red] (0,0) \foreach \a in {-90,0,90,180}{\caley{8}{4cm}{\a}};
\end{document}


## First proposition

Here is a solution using a recursive rotating macro:

\documentclass[tikz]{standalone}
\usepackage{ifthen}
\usetikzlibrary{calc}
\tikzset{
my label/.style={font=\scriptsize,inner sep=2pt},
a/.style={my label,above,node contents={$a$}},
b/.style={my label,right,node contents={$b$}},
a-1/.style={my label,above,node contents={$a^{-1}$}},
b-1/.style={my label,right,node contents={$b^{-1}$}},
}
\newcommand\caley[6]{% level, length, l1, l2, l3, l4
\ifthenelse{0<#1}{
\pgfmathtruncatemacro\newlev{#1-1}
\pgfmathtruncatemacro\len{#2}
\draw[draw=red,-latex] (0,0) -- (\len pt,0) node[pos=.6,#3] coordinate (O);
\begin{scope}[shift={(O)}]
\begin{scope}[rotate=90] \caley{\newlev}{\len/2}{#4}{#5}{#6}{#3} \end{scope}
\begin{scope}[rotate=0]  \caley{\newlev}{\len/2}{#3}{#4}{#5}{#6} \end{scope}
\begin{scope}[rotate=-90]\caley{\newlev}{\len/2}{#6}{#3}{#4}{#5} \end{scope}
\end{scope}
}{\fill[red] circle(1pt);}
}
\begin{document}
\begin{tikzpicture}
\begin{scope}[rotate=-90] \caley{4}{4cm}{b-1}{a}{b}{a-1} \end{scope}
\begin{scope}[rotate=0]   \caley{4}{4cm}{a}{b}{a-1}{b-1} \end{scope}
\begin{scope}[rotate=90]  \caley{4}{4cm}{b}{a-1}{b-1}{a} \end{scope}
\begin{scope}[rotate=180] \caley{4}{4cm}{a-1}{b-1}{a}{b} \end{scope}
\end{tikzpicture}
\end{document}

• could you explain at order 9 (the limit with pdflatex) ? – user4686 Jan 17 '15 at 8:59
• @jfbu 9 is a typo. I edited my answer. – Paul Gaborit Jan 17 '15 at 9:20

first animation

second animation

My initial impulse, knowing there would be excellent TikZ answers was to do it in a pure TeXish way of macro expansion, using package pict2e to have a more powerful picture environment. I did it, but then wasted time (and sleep, sadly) on adding node labels, because computation inside parameters of a \put, even with package picture loaded are extremely annoying, due to the presence of an ending \unitlength. Basically one has to set \unitlength to 1sp and do all computations with big integers inside \numexpr. At some point I was using a delimited macro to remove \unitlength alltogether, but in the end, I accepted also doing some TikZ picture, for the labels. I only needed to copy the \draw from the other answers to learn how to do it. Position is not optimal (the size of the labels should decrease in proportion of the level).

Anyway, the point is that it is fun to translate the graph generation into pure macro expansion, and this is what I do here.

Update: re-generated the initial picture with a larger linethickness, because I noticed that on some systems the edges looked too faint. I also increased by 2 the depth of the graph.

Second Update: I explained above that in the end I dropped pict2e in favor of TikZ for doing the labels. But I had left in the first code sample which does only edges the use of pict2e. I have now edited the code for doing without its \Line command, hence only with standard original LaTeX2e picture environment (package picture is loaded for convenience). The original macros are still part of the second code sample below, which uses TikZ. For clarity I added a \L count which is the level, i.e. the number of edges from center to extremities.

\documentclass[border=.5cm]{standalone}
% second version, not using package pict2e and its \Line command
\usepackage{picture}
\newcount\X % integer horizontal coordinate
\newcount\Y % integer vertical coordinate
\newcount\L % level= number of edges from center to extremities
\newcount\E % length of the current edge to be drawn.

\def\a {\put (\X,\Y){\line(1,0){\E}}

\def\b {\put (\X,\Y){\line(0,1){\E}}

\def\c {\put (\X,\Y){\line(-1,0){\E}}

\def\d {\put (\X,\Y){\line(0,-1){\E}}

\def\s {\ifnum\L = 1
\expandafter\gobblethree
\else
\divide\E by 2
\fi }

\def\gobblethree #1#2#3{}

\def\A {\a\s{\D}{\A}{\B}}
\def\B {\b\s{\A}{\B}{\C}}
\def\C {\c\s{\B}{\C}{\D}}
\def\D {\d\s{\C}{\D}{\A}}

\X 0
\Y 0

% we choose 4cm as the length of each of the 4 segments connected to the center
\setlength{\unitlength}{\dimexpr 4cm/256\relax}%

\E 256 % a length expressed as integer multiple of \unitlength

\L 8 % level 9 would still be ok, but not level 10 which leads to
% ERROR: TeX capacity exceeded, sorry [main memory size=5000000].

\begin{document}

% Without package picture one could use \numexpr 4*\E\relax, etc...
\begin{picture}(16cm,16cm)(-8cm,-8cm)
\linethickness{1.5pt}
{\A}
{\B}
{\C}
{\D}
\end{picture}
\end{document}


The picture above was at level 8 and line thickness set to 2pt. One can use the code up to level 9, but at level 10 one hits ERROR: TeX capacity exceeded, sorry [main memory size=5000000]. The picture below had been generated at level 6 with default line thickness. Its edges may look faint on some screens. (the two pictures were generated with the code using pict2e which is like the code below for TikZ but using \Line command and not doing labels).

And now code for using (not efficiently) TikZ. Besides in the \draw one should intervert \x<->\X and \y<->\Y but I leave the code as is, as the image below was generated using it.

\documentclass[border=.5cm, tikz]{standalone}

\newcount\x
\newcount\y
\newcount\X
\newcount\Y
\newcount\E

\def\a {\x\X
\y\Y
\DrawVecA
\X\x }

\def\b {\y\Y
\x\X
\DrawVecB
\Y\y }

\def\c {\x\X
\y\Y
\DrawVecC
\X\x }

\def\d {\y\Y
\x\X
\DrawVecD
\Y\y }

\def\s {\ifnum\E = 1
\expandafter\gobblethree
\else
\divide\E by 2
\fi }

\def\gobblethree #1#2#3{}

\def\A {\a\s{\D}{\A}{\B}}
\def\B {\b\s{\A}{\B}{\C}}
\def\C {\c\s{\B}{\C}{\D}}
\def\D {\d\s{\C}{\D}{\A}}

\newbox\boxa
\setbox\boxa\hbox{$a$}

\newbox\boxb
\setbox\boxb\hbox{$b$}

\newbox\boxc
\setbox\boxc\hbox{$a^{-1}$}

\newbox\boxd
\setbox\boxd\hbox{$b^{-1}$}

% I should have put \X where \x is and vice versa, idem for \Y and \y

\def\DrawVecA
{\draw[draw=red,latex-] (\x,\y)  -- node[above,pos=.55]{\copy\boxa} (\X,\Y);}

\def\DrawVecB
{\draw[draw=red,latex-] (\x,\y)  -- node[right,pos=.55]{\copy\boxb} (\X,\Y);}

\def\DrawVecC
{\draw[draw=red,latex-] (\x,\y)  -- node[below,pos=.55]{\copy\boxc} (\X,\Y);}

\def\DrawVecD
{\draw[draw=red,latex-] (\x,\y)  -- node[left,pos=.55]{\copy\boxd} (\X,\Y);}

\x 0
\y 0
\X 0
\Y 0
\E 8

\begin{document}

\begin{tikzpicture}
\begin{scope} \A\end{scope}
\begin{scope} \B\end{scope}
\begin{scope} \C\end{scope}
\begin{scope} \D\end{scope}
\end{tikzpicture}

\end{document}


• Some edges are very faint when I view them on my my current HP monitor on a Linux, but they looked perfectly ok on my mac os x laptop under mavericks (both with firefox). – user4686 Jan 14 '15 at 10:42
• (+1) I'm always impressed by this old school style ;) – Kpym Jan 14 '15 at 12:53
• nice animations! I think you should stop your animations at the last frame for a second, before to restart. – Kpym Jan 17 '15 at 12:48
• @Kpym pause inserted in the animations, at each loop. – user4686 Jan 17 '15 at 18:57
• perfect ! (for me) – Kpym Jan 17 '15 at 19:01

Just another recursive try with MetaPost, different from Thruston's and not so good as his (my labelling is somewhat crude), but I managed to produce something acceptable in my view. To be compiled with MetaPost and the numbersystem option set to "double":

input latexmp; setupLaTeXMP(mode = rerun, textextlabel = enable);
u := 1cm ; % Scaling
m := 3; % Number of recursions
d := m;% Depth labelling
labeloffset := 2bp;

% the recursive macro
vardef free_group(expr loc, v, n) =
save w ; pair w; w = v rotated 90;
if (n>0):
drawdblarrow loc - v -- loc + v withcolor red;
drawarrow loc -- loc + w withcolor red;
% labels (the hard part)
if (m-n)<d:
if (xpart v) > epsilon :
label.top("$a$", loc + 0.5v);
label.rt("$b$", loc + 0.5w);
label.top("$a^{-1}$", loc - 0.5v);
elseif (xpart v) < -epsilon:
label.top("$a^{-1}$", loc + 0.5v);
label.rt("$b^{-1}$", loc + 0.5w);
label.top("$a$", loc - 0.5v);
elseif (xpart w) > epsilon:
label.rt("$b^{-1}$", loc + 0.5v);
label.top("$a$", loc + 0.5w);
label.rt("$b$", loc - 0.5v);
else:
label.top("$a^{-1}$", loc + 0.5w);
label.rt("$b$", loc + 0.5v);
label.rt("$b^{-1}$", loc - 0.5v);
fi;
fi;
free_group(loc + v, 0.5v rotated -90, n-1) ;
free_group(loc + w, 0.5v, n-1);
free_group(loc - v, 0.5v rotated 90, n-1);
fi;
enddef;

beginfig(1);
pair v, w, loc; v = (6u, 0) ; w = v rotated 90; loc = origin;
% First "star"
draw origin withpen pencircle scaled 3bp withcolor red;
drawdblarrow -v -- v withcolor red; drawdblarrow -w -- w withcolor red;
label.top("$a$", 0.5v); label.top("$a^{-1}$", -0.5v);
label.rt("$b$", 0.5w); label.rt("$b^{-1}$", -0.5w);
% Recursion calls on each apex
free_group(v, -0.5w, m);
free_group(w, 0.5v, m);
free_group(-v, 0.5w, m);
free_group(-w, -0.5v, m);
endfig;

end.


With the number of recursions m and the labeling depth d both set to 3, it produces this:

With m = 8 and d = 2, it produces this picture. Beyond m=8, MetaPost may still work, but MPtoPDF fails.

Edit Oddly enough, including the previous code in a LuaLaTeX file gives better results than with MPtoPDF. With LuaLaTeX I've managed to produce a result up to 11 levels of recursion. The resulting PDF file is enormous: 11,2 Mo, so I dare not updload a bitmap version of it here! The program can even go further than 11 levels of recursion, but it would take an unreasonable amount of time and the figure would not change in appearance anyway.

Here's a recursive solution in Metapost.

prologues := 3;
outputtemplate := "%j%c.eps";

vardef do_label(expr arrow) =
save d; pair d;
if arclength(arrow) > 7mm:
d = unitvector(direction 0 of arrow);
if d = right:
label.top(btex $a$ etex scaled defaultscale, point 1/2 of arrow);
elseif d = up:
label.rt (btex $b$ etex scaled defaultscale, point 1/2 of arrow);
elseif d = left:
label.top(btex $a^{-1}$ etex scaled defaultscale, point 1/2 of arrow);
elseif d = down:
label.rt (btex $b^{-1}$ etex scaled defaultscale, point 1/2 of arrow);
fi
fi
enddef;

vardef branch(expr p, depth) =
save h, c, d; path h, c; pair d;
interim ahlength := 0.8 * ahlength;
interim defaultscale := 0.9 * defaultscale;
if depth > 0:
for t=90 step 90 until 270:
h := (subpath (1,.5) of p) rotatedabout(point 1 of p, t);
c := fullcircle scaled ahlength shifted point 1 of h;
drawarrow h cutafter c; do_label(h);
fill c if depth=1: withcolor .67 red fi;
branch(h,depth-1);
endfor
fi
enddef;

beginfig(1);
path a, c; u = 3cm;
for t=0 step 90 until 270:
a := origin -- right scaled u rotated t;
c := fullcircle scaled ahlength shifted point 1 of a;
drawarrow a cutafter c; do_label(a); fill c;
% start recursive call
branch(a,2);
endfor
dotlabel.urt(btex $1$ etex, origin);

setbounds currentpicture to bbox currentpicture scaled 1.1;
endfig;
end.


I left out the surrounding ellipsis dots from the OP picture because they are slightly misleading; the figure does not actually get much bigger. No matter how deep you make the branches it will always fit inside a square with sides sqrt(8)*unit length. Here's a version with depth set to 5. Metapost takes a long time to compile it with depth set to 7 or more.