Making Tikz automatic node placement work

Question

I have found some tikz code that uses a development build (past 2.10) and I am trying to get it to work (I sense that I am doing something rather silly).

For what is it worth, I confirmed that the correct version of tikz is being used via the method suggested in the second answer to this question.

I am attempting to use the following code:

  \documentclass[12pt]{article}
  \usepackage{tikz}
  \usetikzlibrary{positioning,graphs}
  \begin{document}
  \begin{tikzpicture}
      \begin{graph} [circular placement,branch right,nodes={draw,circle},edges=  {>=latex}] {
"0,0,0,0" <->
    { "1,0,0,0"<->
        {"1,1,0,0"<->
         {"1,1,1,0"<->"1,1,1,1","1,1,0,0"}
        ,"1,0,1,0"<->
            {"1,1,1,0","1,0,1,1"<->"1,1,1,1"},
        "1,0,0,1"<->
            {"1,1,0,1","1,0,1,1"}
        },
    "0,1,0,0"<->
        {"1,1,0,0","0,1,1,0","0,1,0,1"<->
            {"1,1,0,1","0,1,1,1"}
        },
    ,"0,0,1,0"<->
        {"1,0,1,0","0,1,1,0","0,0,1,1"}<->
            {"1,0,1,1","0,1,1,1"<->"1,1,1,1"},
    ,"0,0,0,1"<->
        {"1,0,0,1","0,1,0,1","0,0,1,1"}
    }
};
\end{graph}
\end{tikzpicture}
\end{document}

It generates the following graph:

I am looking for this:

Is there a way to generate that using the automatic node positioning from tikz? If not, how can it be done with the "older" syntax?

Note: I am using the 2012-11-04 build of tikz if that matters.

Answer 1

Probably could be done with the the new graph library, but I went for an old fashioned approach, by drawing the nodes first and then determining which nodes should be connected by using the base conversion stuff. No commas between the digits, but that is left as an exercise for the reader :).

\documentclass[border=0.125cm]{standalone}
\usepackage{tikz}
\usetikzlibrary{shapes.geometric}

\pgfmathsetbasenumberlength{4}

% Take two decimal numbers from 0 - 15, convert them
% to binary and detemine if their nodes should be
% connected.
\def\process#1#2{%
    \pgfmathdectobase{\x}{#1}{2}%
    \pgfmathdectobase{\y}{#2}{2}%
    % Expand the arguments...
    \edef\args{\x\y}%
    % ...so that the next line produces (for example)
    % \Process01000111
    \expandafter\Process\args}

% #1#2#3#4 correspond to the bits of the first number
% #5#6#7#8 correspond to the bits of the second number
\def\Process#1#2#3#4#5#6#7#8{%
    % Nodes are connected if they differ by exactly one bit.
    % So a function is required such that:
    %
    % sum(f(x_i, y_i)) = 1 for i = 1,...,n
    %
    % Where n is the number of bits, and x_i and y_i
    % are the i'th bits of the numbers x and y. 
    % The function f must return 1 if the bits are different,
    % and zero otherwise.
    %
    % Consider the function 
    %
    %   f(x,y) = (x | y) - (x & y)
    %
    % For all combinations of x and y:
    %
    % f(0, 0) = 0
    % f(1, 0) = 1
    % f(1, 1) = 0
    % f(0, 1) = 1
    %
    % So by summing this function over the bits of x and y
    % the nodes will be connected iff the sum is equal to 1
    %
    % Here I've sort of done the same thing 'by hand', and
    % separated the 'or' and 'and' operations as a separate
    % function isn't really necessary.
  \pgfmathparse{int(or(#1,#5)+or(#2,#6)+or(#3,#7)+or(#4,#8)-and(#1,#5)-and(#2,#6)-and(#3,#7)-and(#4,#8))}%
}

\begin{document}

\begin{tikzpicture}[>=stealth, 
    % Installed for every node.
    every byte/.style={
        ellipse, 
        draw,
        font=\sf,
        fill=black!50,
        text=white
},
% Set some node styles if required
0101/.style={fill=blue!20, text=black},
0001/.style={fill=red!20, text=black}]

\foreach \bytes [count=\y from 0] in {
    {0000},
    {1000,0100,0010,0001}, 
    {1100,1010,0110,1001,0101,0011}, 
    {1110,1101,1011,0111}, 
    {1111}}
    \foreach \byte [count=\x from 0] in \bytes
    % Use \byte/.try to install a style if it exists.
        \node [x=3cm, y=2cm, every byte/.try, \byte/.try] 
            % This positioning is a bit of a kludge
            at ({\x+abs(2-\y)+(mod(\y, 4)==0)/2}, -\y) 
            (\byte) {\byte};

% Now go over every combination of numbers to
% to determine if their nodes are connected.
\foreach \x in {0,...,15}{
    \foreach \y in {\x,...,15}{
        \ifnum\x=\y
        \else
            \process{\x}{\y}
            \ifnum\pgfmathresult=1
                \draw [<->] (\x) -- (\y);
            \fi
        \fi     
    }
}

\end{tikzpicture}

\end{document}

Answer 2

A recursive function for producing the same tree, it is not that productive because it needs an extra loop to replace one 0 by a 1. The positioning of the nodes is a little different from Op.

And yes, the names of the nodes are stupid: n-{0,0,0}, n-{1,0,0}, …, n-{1,1,1}. The prefix n- is only there so that the braces aren’t getting stript accidentally.

With \pgfutil@ifundefined{}, we can check whether a node has been defined before and avoid creating a duplicate node with the same content that has been recursively reached from another node from the level before. This has one major disadvantage:
As nodes are defined globally, we cannot have the same tree (of the same number of digits) per document. This can be worked around by using \pgfid directly in the node name or by checking it against the node’s id directly (the \pgfid is saved with every node).

Code

\documentclass[tikz{standalone}
\usetikzlibrary{chains}
\makeatletter
%% Auxiliary things: \pgfMathifthenelse (used twice) and strrepeat function (used once)
\newcommand*{\pgfMathifthenelse}[1]{\pgfmathparse{#1}\ifnum\pgfmathresult=0\relax
  \expandafter\pgfutil@secondoftwo\else\expandafter\pgfutil@firstoftwo\fi}
\newcommand*{\pgfMathsetmacro}[2]{\pgfmathparse{#2}\let#1\pgfmathresult}% 2.10 fix
\pgfmathdeclarefunction{strrepeat}{2}{% from http://tex.stackexchange.com/a/120605/16595
  \begingroup\pgfmathint{#2}\pgfmath@count\pgfmathresult
    \let\pgfmathresult\pgfutil@empty
    \pgfutil@loop\ifnum\pgfmath@count>0\relax
      \expandafter\def\expandafter\pgfmathresult\expandafter{\pgfmathresult#1}%
      \advance\pgfmath@count-1\relax
    \pgfutil@repeat\pgfmath@smuggleone\pgfmathresult\endgroup}
\tikzset{
  % the number of digits is saved in /tikz/digits; a pgfmath function for easier acess
  digits/.initial=2, declare function={digits=\pgfkeysvalueof{/tikz/digits};},
  edge node/.code={% from CVS
    \expandafter\def\expandafter\tikz@tonodes\expandafter{\tikz@tonodes #1}},
  binary tree/.style 2 args={% initializes the tree, digits must be set before
    start chain/.list={ch1 going #1, ch... going #1,%
                                          ch\pgfkeysvalueof{/tikz/digits} going #1},
    /utils/exec={\pgfMathsetmacro\digits@temp{strrepeat("0,",digits-1)}
                 \edef\digits@temp{{\digits@temp0}}
                 \node [name=n-\digits@temp, alias=ch0-begin] {$\digits@temp$};},
    start tree/.expanded={0}{\digits@temp}{#2}},
  start tree/.code n args={3}{% recursive tree-ing
    \pgfmathtruncatemacro\level{#1+1}%
    \foreach \digit in {1,...,\pgfkeysvalueof{/tikz/digits}}{
      \pgfMathifthenelse{#2[\digit-1]==0}{
        \let\digits@temp\pgfutil@gobble
        \foreach \mDigit in {1, ..., \pgfkeysvalueof{/tikz/digits}}{
          \ifnum\mDigit=\digit\relax\def\pgfmathresult{1}
            \else\pgfmathparse{#2[\mDigit-1]}\fi
          \xdef\digits@temp{\digits@temp,\pgfmathresult}}
        \edef\digits@temp{{\digits@temp}}%
        \pgfutil@ifundefined{pgf@sh@ns@n-\digits@temp}{%
          \node[#3=of ch#1-begin, on chain=ch\level, alias=n-\digits@temp]
                                                                    {$\digits@temp$};
           \pgfMathifthenelse{\level+1>digits}{}{% faster stop of recursion
             \def\digits@next{\tikzset{start tree/.expanded={\level}{\digits@temp}{#3}}}}
        }{\let\digits@next\relax}
        \path ({n-#2}) edge [binary edge/.try/.expanded={\level}{\digit}]
                                                                      ({n-\digits@temp});
        \digits@next}{}}}}
\makeatother
\begin{document}
\tikz[binary tree={right}{below}]{}
\tikz[digits=3,
  binary edge/.style 2 args={->, edge node={
    node[near start, sloped, allow upside down, rotate=90, fill=white, inner sep=+2pt]
    {\scriptsize#2}}},
  binary tree={right}{below}]{}
\tikz[digits=4, binary tree={right}{below}]{}
\tikz[digits=5, node distance=0em and 1cm,
      every edge/.append style={to path=(\tikztostart.east) -- (\tikztotarget.west)},
      binary tree={above}{right}]{}
\end{document}

Output