Drawing a Cayley tree

Question

I'm new to Tikz so sorry if this is trivial. I'd like to draw a Cayley tree in Tikz that looks something like image I found on Google.

The catch is that I want alternating layers to be alternate node shapes -- circle and square nodes. Secondly, I would like the circular nodes to have degree 3 and the square nodes to have degree 5. Is there some way to generate this without having to place each node manually where I want?

Answer 1

Second proposition (using two nested loops as suggested by marsupilam)

(Note: My previous proposition did not use the correct definition of degrees. Thanks to cfr and marsupilam for having noticed.)

Here is a pdflatex solution. The first node (the center) is c-0-1. The first level nodes are c-1-1, c-1-2 and c-1-3... The fourth level nodes are c-4-1, c-4-2, ... and c-4-96.

\documentclass[tikz]{standalone}
\tikzset{
  common/.style={draw,name=#1,node contents={},inner sep=0,minimum size=3},
  disc/.style={circle,common=#1},
  square/.style={rectangle,common={#1}},
}
\begin{document}
\begin{tikzpicture}
  \draw (0,0) node[disc=c-0-1];
  \xdef\radius{0cm}
  \xdef\level{0}
  \xdef\nbnodes{1}
  \xdef\degree{(3+1)} % special degree just for the root node
  \foreach \ndegree/\form in {5/square,3/disc,5/square,3/disc}{
    \pgfmathsetmacro\nlevel{int(\level+1)}
    \pgfmathsetmacro\nnbnodes{int(\nbnodes*(\degree-1))}
    \pgfmathsetmacro\nradius{\radius+1cm}
    \draw[red] (c-0-1) circle(\nradius pt);
    \foreach \div in {1,...,\nnbnodes} {
      \pgfmathtruncatemacro\src{((\div+\degree-2)/(\degree-1))}
      \path (c-0-1) ++({\div*(360/\nnbnodes)-180/\nnbnodes}:\nradius pt) node[\form=c-\nlevel-\div];
      \draw (c-\level-\src) -- (c-\nlevel-\div);
    }
    \xdef\radius{\nradius}
    \xdef\level{\nlevel}
    \xdef\nbnodes{\nnbnodes}
    \xdef\degree{\ndegree}
  }
\end{tikzpicture}
\end{document}

Answer 2

I followed the advice by JPi and cfr, and went for lua.

(edit : I think this style gives a nice blooming sakura vibe.)

The output

The tikz

Compile with lualatex

\RequirePackage{luatex85}
\documentclass[12pt,tikz]{standalone}
\usepackage{luacode}
\begin{luacode*}
  print=tex.print
  makeGrow=require("makeGrow.lua")
\end{luacode*}
\begin{document}
\tikzset
{
  odd/.style = {draw=blue!50!pink,circle,ultra thick},
  even/.style = {draw=red,line width=3pt,minimum size=4mm},
}
\begin{tikzpicture}[scale=20]
  \directlua{makeGrow.make(4)}
\end{tikzpicture}
\end{document}

The lua

-- makeGrow.lua
-- mode = {totalAngle = totalAngle, number = numberOfChildren, radius = lengthOrArm}
local function makeChildren(parent,mode,f)
  local f = f or function() return end
  parent.children = {}
  for k=1,mode.number do
    parent.children[k] = {
      generation = parent.generation + 1,
      angle = parent.angle + (k-.5*(mode.number+1)) * mode.totalAngle / mode.number,
      parent = parent,
      label = parent.label .. tostring(k),
    }
    f(parent.children[k]) -- we smuggled f in there to recurse.
  end
end
local function tikzNode(node)
  return {
    name = "(myNode-" .. node.label .. ")",
    style = "[" .. ({"even","odd"})[node.generation%2+1] .. "]",
  }
end
local function draw(node,mode)
  if node.parent then
    print([[\path]] .. tikzNode(node.parent).name .. " -- ++(" .. node.angle .. ":" ..  mode.radius .. ") node" .. tikzNode(node).style .. tikzNode(node).name .. "{} ;")
    print([[\draw]] .. tikzNode(node.parent).name .. " -- " .. tikzNode(node).name .. ";")
  else
    print([=[\node[odd]]=] .. tikzNode(node).name .. "at (0,0) {};")
  end
end
local function drawMakeChild(n,modes)
  local function recurse(node)
      draw(node,modes[node.generation-1])
      if node.generation<=n then
        makeChildren(node,modes[node.generation],recurse)
      end
  end
  return recurse
end
local function computeMode(generation,hash)
  local number = ({5,3})[generation%2+1] -- alternating number of children
  local radius = hash.radRatio^generation
  local totalAngle = 360 * hash.angRatio^(generation-1)
  return {totalAngle = totalAngle , number = number, radius = radius}
end
local function make(n)
  local origin = {
    generation = 1,
    angle = 0,
    label = ""
  }
  local modes = {}
  for k=1,n do modes[k] = computeMode(k,{angRatio=.98,radRatio=.35}) end
  drawMakeChild(n,modes)(origin)
end
return {make=make}

Edit : Using Paul's style

The output

or with \def\N{4}

The tikz

\RequirePackage{luatex85}
\documentclass[12pt,tikz]{standalone}
\usepackage{luacode}
\begin{luacode*}
  print=tex.print
  makeGrow=require("paulStyle.lua")
\end{luacode*}
\begin{document}
\tikzset
{
  commons/.style={fill=white},
  odd/.style = {draw=red,circle,ultra thick,commons},
  even/.style = {draw=blue,ultra thick,minimum size=3mm,commons},
}
\def\N{3}
\begin{tikzpicture}[scale=4]
  \foreach \k in {1,...,\N} \draw[help lines,purple] (0,0) circle (\k);
  \directlua{makeGrow.make(\N)}
\end{tikzpicture}
\end{document}

The lua

-- paulStyle.lua
local function makeChildren(parent,multiplicity,f)
  parent.children = {}
  for k=1,multiplicity do
    parent.children[k] = {
      generation = parent.generation + 1,
      cumProd = parent.cumProd * multiplicity,
      angle = parent.angle + ((k-.5)/multiplicity-.5 ) * 360 / parent.cumProd,
      parent = parent,
      label = parent.label .. tostring(k),
    }
    f(parent.children[k]) -- we smuggled f in there to recurse.
  end
end
local function tikzNode(node)
  return {
    name = "(myNode-" .. node.label .. ")",
    style = "[" .. ({"odd","even"})[node.generation%2+1] .. "]",
  }
end
local function draw(node)
  if node.parent then
    print([[\node]].. tikzNode(node).style .. tikzNode(node).name .. " at " .. "(" .. node.angle .. ":" ..  node.generation .. ") {};")
    print([[\draw]] .. tikzNode(node.parent).name .. " -- " .. tikzNode(node).name .. ";")
  else
    print([=[\node]=] .. tikzNode(node).style .. tikzNode(node).name .. "at (0,0) {};")
  end
end
local function drawMakeChild(n,multiplicities)
  local function recurse(node)
      draw(node,multiplicities[node.generation-1])
      if node.generation<n then
        makeChildren(node,multiplicities[node.generation],recurse)
      end
  end
  return recurse
end
local function make(n)
  local origin = {
    cumProd = 1,
    generation = 0,
    angle = 0,
    label = ""
  }
  local multiplicities = {}
  for k=1,n do multiplicities[k-1] = ({5,3})[k%2+1] end
  drawMakeChild(n,multiplicities)(origin)
end
return {make=make}

Answer 3

Here's mine. Despite my comments, this is, in fact, pure TikZ without any of the graphs stuff. That is, you can compile it with LaTeX, pdfLaTeX or whatever and it should work. (You can presumably convert it into a TeX version, should you so wish.) I planned to use graphs to draw the connections, which doesn't need LuaTeX anyway. But, somehow, I never got around to it as, once I'd placed the nodes, this seemed easier.

Change the maximum value for the outer loop to increase the number of levels. I practised with values of 3 and 4, but use 5 for the 'display' version here. The complication is that the first node gets 3 children, in order to have degree 3, while later nodes of degree 3 only need 2, because they have a parent. This requires special treatment of the first 3 levels to get things to line up correctly. After that, subsequent levels are just a question of TeX capacity and your patience.

Use \showtrue to draw a labelled version, for debugging purposes.

\documentclass[border=10pt]{standalone}
\usepackage{tikz}
\newif\ifshow\showfalse % set true to debug
\begin{document}
\begin{tikzpicture}
  % \i: level \s: shape \a: angle \t: turn \d: degree -1 \j: number \m: rotation \g: group \k: number \c: colour
  \def\j{1}\def\dlast{1}\def\tlast{0}
  \foreach \i [remember=\i as \ilast] in {0,...,5}
  {
    \draw [darkgray] (0,0) circle (\i cm);
    \pgfmathsetmacro\a{360/\j}
    \ifodd\i\def\s{}\def\c{magenta}\def\d{4}\pgfmathsetmacro\t{\tlast-1.5*\a}\else\def\c{blue!50!cyan}\def\s{circle}\def\d{2}\pgfmathsetmacro\t{\tlast-2.5*\a}\fi
    \ifnum\i=1\pgfmathsetmacro\t{-\a}\fi
    \ifnum\i=0\def\d{3}\def\t{0}\fi
    \foreach \k [evaluate=\k as \m using {(\k*\a)+\t}, evaluate=\k as \g using {int((floor((\k-1)/\dlast)))}, count=\n from 0 ] in {1,...,\j}
    {
      \ifshow\def\tempa{n-\i-\g-\n:\k}\else\let\tempa\relax\fi
      \node (n-\i-\n) [draw, fill, \c, \s, minimum size=2.5pt, inner sep=0pt, label={[font=\tiny]{\tempa}} ] at (\m:\i cm) {};
      \ifnum\i>0 \draw [darkgray] (n-\i-\n) -- (n-\ilast-\g); \fi
    }
    \pgfmathsetmacro\j { \j*\d }
    \global\let\j\j
    \global\let\dlast\d
    \pgfmathsetmacro\tlast{(\i==1) ? 0 : (\t+\a) }
    \global\let\tlast\tlast
  }
\end{tikzpicture}
\end{document}

Here's a more parametized version, with (optional) special effects.

• circle colour=<colour> will give a uniform colour for the circles;
• circle colours=<colour>:<colour> will give shades varying between the two colours for the circles;
• square colour=<colour> will give a uniform colour for the circles;
• square colours=<colour>:<colour> will give shades varying between the two colours for the squares;
• circle degree=<integer> sets the degree for the circular nodes;
• square degree=<integer> sets the degree for the square nodes;
• connection colour<colour> sets the colour for the circles and the background;
• levels=<integer> sets the number of levels.

If you don't want the background, just delete the line

\scoped[on background layer]{\shade [inner color=lcol!5, outer color=lcol!35] circle (\l cm);}

In that case, you don't need the backgrounds library and can delete

\usetikzlibrary{backgrounds}

if you don't need it for anything else.

\documentclass[border=10pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{backgrounds}
\newif\ifshow\showfalse % set true to debug
\begin{document}
\begin{tikzpicture}
  % \i: level \s: shape \a: angle \t: turn \d: degree -1 \j: number \m: rotation \g: group \k: number ncol: colour
  \tikzset{
    circle degree/.code={\def\dr{#1}\pgfmathsetmacro\dc{int(#1-1)}\pgfmathsetmacro\tc{((\dc-1)/2)+1}},
    square degree/.code={\pgfmathsetmacro\ds{int(#1-1)}\pgfmathsetmacro\ts{((\ds-1)/2)+1}},
    levels/.code={\pgfmathsetmacro\l{int(#1-1)}},
    connection colour/.code={\colorlet{lcol}{#1}},
    circle colours/.code args={#1:#2}{\colorlet{ccol1}{#1}\colorlet{ccol2}{#2}},
    square colours/.code args={#1:#2}{\colorlet{scol1}{#1}\colorlet{scol2}{#2}},
    circle colour/.style={circle colours=#1:#1},
    square colour/.style={square colours=#1:#1},
    circle degree=3,
    square degree=5,
    levels=6,
    connection colour=darkgray,
    square colours=green:blue,
    circle colours=blue:magenta,
  }
  \def\j{1}\def\dlast{1}\def\tlast{0}
  \foreach \i [remember=\i as \ilast] in {0,...,\l}
  {
    \draw [lcol] (0,0) circle (\i cm);
    \pgfmathsetmacro\a{360/\j}
    \pgfmathsetmacro\z{6.5-\i*.8}
    \ifodd\i\def\s{}\colorlet{ncol1}{scol1}\colorlet{ncol2}{scol2}\let\d\dc\pgfmathsetmacro\t{\tlast-\ts*\a}\else\colorlet{ncol1}{ccol1}\colorlet{ncol2}{ccol2}\def\s{circle}\let\d\ds\pgfmathsetmacro\t{\tlast-\tc*\a}\fi
    \ifnum\i=1\pgfmathsetmacro\t{-\a}\fi
    \ifnum\i=0\let\d\dr\def\t{0}\fi
    \foreach \k [evaluate=\k as \m using {(\k*\a)+\t}, evaluate=\k as \g using {int((floor((\k-1)/\dlast)))}, count=\n from 0, evaluate=\k as \p using { (\k > \j/2) ? ((1-\k/\j)*200) : ((200/\j)*\k)} ] in {1,...,\j}
    {
      \ifshow\def\tempa{n-\i-\g-\n:\k}\else\let\tempa\relax\fi
      \node (n-\i-\n) [draw, fill, ncol1!\p!ncol2, \s, minimum size=\z pt, inner sep=0pt, label={[font=\tiny]{\tempa}} ] at (\m:\i cm) {};
      \ifnum\i>0 \draw [ncol1!\p!ncol2] (n-\i-\n) -- (n-\ilast-\g); \fi
    }
    \pgfmathsetmacro\j { \j*\d }
    \global\let\j\j
    \global\let\dlast\d
    \pgfmathsetmacro\tlast{(\i==1) ? 0 : (\t+\a) }
    \global\let\tlast\tlast
  }
  \scoped[on background layer]{\shade [inner color=lcol!5, outer color=lcol!35] circle (\l cm);}
\end{tikzpicture}
\end{document}