[Tex/LaTex] Cayley Graph of Free Group in TikZ

tikz-pgftikz-trees

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?

Caylay Graph of free group generated by two elements

Best Answer

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}
\newcount\quadrant
\pgfdeclarelindenmayersystem{cayley}{
  \rule{A -> B [ R [A] [+A] [-A] ]}
  \symbol{R}{ \pgflsystemstep=0.5\pgflsystemstep } 
  \symbol{-}{
    \pgfmathsetcount\quadrant{Mod(\quadrant+1,4)}
    \tikzset{rotate=90}
  }
  \symbol{+}{
    \pgfmathsetcount\quadrant{Mod(\quadrant-1,4)}
    \tikzset{rotate=-90}
  }
  \symbol{B}{
    \draw [dot-cayley] (0,0) -- (\pgflsystemstep,0) 
       node [font=\footnotesize, midway, 
         anchor={270-mod(\the\quadrant,2)*90}, inner sep=.5ex] 
           {\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}

enter image description here

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}

enter image description here

and by using:

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

the result is

enter image description here

and 

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

gives

enter image description here

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}

enter image description here

Related Question