By which pkg to visualize a hypercube graph?

Question

I am trying to visualise hypercube like the below. I have asked help here but getting nodes on top of each other with the packages there. The N-th hypercube has 2^n nodes and each vertex with the degree of n. I am trying to find a way to vizualise hypercubes with larger degree so big challenge for the pkg. My goal is to vizualise traversing of the cube. How would you do this kind of vizualisation?

Example about 3th Hypercube (8 nodes where each vertex has the degree of 3)

Answer 1

I'm going to interpret "hypercube" as a way of specifying a graph.

I use LaTeX3 to do some conversions between integers and binary, and to make the various recursions easier. Then TikZ does the actual rendering.

(It could do with a clean-up with regard to temporary variables, and a few styling options would be a reasonable addition.)

\documentclass{article}
%\url{http://tex.stackexchange.com/q/129613/86}
\usepackage[landscape]{geometry}
\usepackage{tikz}
\usepackage{expl3}
\usepackage{xparse}

\ExplSyntaxOn

\int_new:N \l__binp_int
\int_set:Nn \l__binp_int {4}
\tl_new:N \l__bina_tl
\tl_new:N \l__binb_tl
\tl_new:N \l__binhw_tl
\int_new:N \l__bina_int
\int_new:N \l__binb_int
\int_new:N \l__binc_int
\int_new:N \l__bind_int
\fp_new:N \l__bina_fp

\DeclareDocumentCommand \BinaryPrecision {m}
{
  \int_set:Nn \l__binp_int {#1}
}

\cs_new_nopar:Npn \int_to_bin:Nn #1#2
{
  \tl_clear:N #1
  \int_set:Nn \l__bina_int {#2}
  \prg_replicate:nn {\l__binp_int}
  {
    \int_set:Nn \l__binb_int {\int_mod:nn {\l__bina_int} {2}}
    \tl_put_left:Nx #1 {\int_use:N \l__binb_int}
    \int_set:Nn \l__bina_int {\int_div_truncate:nn {\l__bina_int} {2}}
  }
}

\cs_new_nopar:Npn \bin_hamming_weight:NN #1#2
{
  \tl_set_eq:NN \l__binhw_tl #2
  \tl_replace_all:Nnn \l__binhw_tl {0} {}
  \int_set:Nn #1 {\tl_count:N \l__binhw_tl}
}

\cs_new_nopar:Npn \bin_flip_one:NNn #1#2#3
{
  \tl_set_eq:NN #2#1
  \prg_replicate:nn {#3 - 1}
  {
    \tl_replace_once:Nnn #2 {1} {a}
  }
  \tl_replace_once:Nnn #2 {1} {0}
  \tl_replace_all:Nnn #2 {a} {1}
}

\DeclareDocumentCommand \HammingWeight {m m}
{
  \int_to_bin:Nn \l__binhw_tl {#2}
  \bin_hamming_weight:NN #1 \l__binhw_tl
}

\DeclareDocumentCommand \HyperCube {m}
{
  \int_set:Nn \l__binp_int {#1}
  \int_zero_new:c {l__hyper_0_int}
  \int_set:cn {l__hyper_0_int} {-1}
  \int_step_inline:nnnn {1} {1} {#1}
  {
    \int_zero_new:c {l__hyper_##1_int}
    \int_set:cn  {l__hyper_##1_int} {\int_use:c {l__hyper_\int_eval:n {##1 - 1}_int} * (#1 - ##1 + 1) / ##1}
  }
  \fp_set:Nn \l__bina_fp {2^{#1}-1}
  \int_set:Nn \l__binc_int {\fp_to_int:N \l__bina_fp}
  \int_step_inline:nnnn {0} {1} {\l__binc_int}
  {
    \int_to_bin:Nn \l__bina_tl {##1}
    \bin_hamming_weight:NN \l__binb_int \l__bina_tl
    \node[every~ hypercube~ label/.try] (hg- \l__bina_tl) at (\int_use:c {l__hyper_\int_use:N \l__binb_int _int},\int_use:N \l__binb_int) {##1};
    \int_incr:c {l__hyper_\int_use:N \l__binb_int _int}
    \int_incr:c {l__hyper_\int_use:N \l__binb_int _int}
  }
  \int_step_inline:nnnn {0} {1} {\l__binc_int}
  {
    \int_to_bin:Nn \l__bina_tl {##1}
    \bin_hamming_weight:NN \l__binb_int \l__bina_tl
    \int_step_inline:nnnn {1} {1} {\l__binb_int}
    {
      \bin_flip_one:NNn \l__bina_tl \l__binb_tl {####1}
      \draw[every~ hypercube~ edge/.try] (hg- \l__bina_tl) -- (hg- \l__binb_tl);
    }
  }
}

\ExplSyntaxOff


\begin{document}
\begin{tikzpicture}
\HyperCube{3}
\end{tikzpicture}

\begin{tikzpicture}
\HyperCube{4}
\end{tikzpicture}

\begin{tikzpicture}
\HyperCube{5}
\end{tikzpicture}

\end{document}

Answer 2

This can also be done with TikZ and a \matrix (or tikz-cd) though it gets complicated for more than three dimensions.

Here is a approach that shifts every already placed node for dimension n in the dimension n + 1, n + 2, …, n_total and connects it with its parent node (->).

The \currentTransform macro is setup in a way that it contains for every node all applied transformation (from 0-0), this is used to connect the nodes in their own dimension (<->). (A good reason for a grouped \foreach loop.)

Code

\documentclass[tikz,convert=false]{standalone}
% a little support for all the keys
\def\hyperset{\pgfqkeys{/tikz/hyper}}
\tikzset{hypher/.code=\hyperset{#1}}

% Dimension setup
\hyperset{
  set color/.code 2 args={\colorlet{tikz@hyper@dimen@#1}{#2}},
  set color={0}{black},
  set color={1}{blue!50!black},
  set color={2}{red},
  set color={3}{green},
  set color={4}{yellow!80!black}}
\hyperset{
  set dimens/.style args={#1:(#2)}{
    dimen #1/.style={/tikz/shift={(#2)}}},
  set dimens=0:(0:0),
  set dimens=1:(right:1),
  set dimens=2:(up:1),
  set dimens=3:(30:.75),
  set dimens=4:(180+70:.5),
  every hyper node/.style 2 args={%
    shape=circle,
    inner sep=+0pt,
    fill,
    draw,
    minimum size=+3pt,
    color=tikz@hyper@dimen@#1,
    label={[hyper/label #1/.try, hyper/dimen #1 style/.try]#1-#2}
  },
  every hyper edge/.style={draw},
  every hyper shift edge/.style={->,tikz@hyper@dimen@#1!80},
  every normal hyper edge/.style={<->,tikz@hyper@dimen@#1!40},
}
\newcommand*{\hyper}[1]{% #3 = max level
  \def\currentTransform{}
  \node[hyper/every hyper node/.try={0}{0}, hyper/dimen 0 node/.try] (0-0) {};
  \hyperhyper{0}{0}{#1}}
\newcommand*{\hyperhyper}[3]{% #1 = current level
                             % #2 = current number
                             % #3 = maxlevel
  \foreach \dimension in {#3,...,\the\numexpr#1+1\relax} {
    \edef\newNumber{\the\numexpr#2+\dimension\relax}
    \node[hyper/every hyper node/.try={\dimension}{\newNumber}, hyper/dimen \dimension node/.try, hyper/dimen \dimension\space style/.try] at ([hyper/dimen \dimension] #1-#2) (\dimension-\newNumber) {};
    \path (#1-#2) edge[hyper/every hyper edge/.try=\dimension, hyper/every hyper shift edge/.try=\dimension, hyper/dimen \dimension\space style/.try] (\dimension-\newNumber);
    \ifnum\newNumber>\dimension\relax
      \foreach \oldShift in \currentTransform {
        \if\relax\detokenize\expandafter{\oldShift}\relax\else
          \path (\dimension-\newNumber) edge[hyper/every hyper edge/.try=\dimension, hyper/every normal hyper edge/.try=\dimension, hyper/dimen \dimension\space style/.try] (\dimension-\the\numexpr\newNumber-\oldShift\relax);
        \fi
      }
    \fi
    \edef\currentTransform{\dimension,\currentTransform}%
    \ifnum\dimension<#3\relax
      \edef\temp{{\dimension}{\the\numexpr#2+\dimension\relax}{#3}}
      \expandafter\hyperhyper\temp
    \fi
  }
}
\tikzset{
  @only for the animation/.style={
    hyper/dimen #1 style/.style={opacity=0}}}
\begin{document}
\foreach \DIM in {0,...,4,4,3,...,0} {
\begin{tikzpicture}[
  >=stealth,
  scale=3,
  every label/.append style={font=\tiny,inner sep=+0pt}, label position=above left,
  @only for the animation/.list={\the\numexpr\DIM+1\relax,...,5}
  ]
  \hyper{4}
\end{tikzpicture}}
\end{document}

Output

Algorithm (beamer, step-for-step)

Answer 3

Here a possibility to visualize the 3-hypercube which you show with PSTricks:

% arara: latex
% arara: dvips
% arara: ps2pdf
\documentclass[preview,border=3pt]{standalone}
\usepackage{pst-node}
\begin{document}
\begin{psmatrix}[mnode=circle,colsep=0.8,rowsep=0.8]
& [name=8] 8 \\[-0.4\psyunit]
[name=5] 5 & [name=6] 6 & [name=7] 7\\
[name=2] 2 & [name=3] 3 & [name=4] 4\\[-0.4\psyunit]
& [name=1] 1
\ncline{8}{5}\ncline{8}{6}\ncline{8}{7}
\ncline{5}{3}\ncline{5}{2}
\ncline{6}{2}\ncline{6}{4}
\ncline{7}{3}\ncline{7}{4}
\ncline{1}{2}\ncline{1}{3}\ncline{1}{4}
\ncline[offset=5pt, linewidth=0.5\pslinewidth, arrows=->, nodesep=5pt]{1}{2}
\ncarc[offset=3pt, linewidth=0.5\pslinewidth, arrows=->, nodesep=4pt]{2}{5}
\end{psmatrix}
\end{document}

This gives:

But I don't know of any package capable of doing the N-th hypercube automatically.

Answer 4

The package tkz-berge has many named graphs, and although it does not directly support hypercube graphs, there is an example in the documentation (page 60 of the manual) of fourth hypercube graph:

\documentclass{standalone}
\usepackage{tkz-berge}
\begin{document}
\begin{tikzpicture}
  \grCycle[RA=8]{8}
  \pgfmathparse{8*(1-4*sin(22.5)*sin(22.5))}
  \let\tkzbradius\pgfmathresult
  \grCirculant[prefix=b,RA=\tkzbradius]{8}{3}
  \makeatletter
  \foreach \vx in {0,...,7}{%
    \pgfmathsetcounter{tkz@gr@n}{mod(\vx+1,8)}
    \pgfmathsetcounter{tkz@gr@a}{mod(\vx+7,8)}
    \pgfmathsetcounter{tkz@gr@b}{mod(\thetkz@gr@n+1,8)}
    \Edge(a\thetkz@gr@n)(b\thetkz@gr@b)
    \Edge(b\thetkz@gr@a)(a\vx)
    }
  \makeatother
\end{tikzpicture}
\end{document}

resulting in

Answer 5

For an alternative, here the tikz-cd version of the original image/Op’s real request.

Code

\documentclass[tikz,convert=false]{standalone}
\usepackage{tikz-cd}
\tikzset{
  shorten/.style={/tikz/shorten >={#1},/tikz/shorten <={#1}}}
\begin{document}
\begin{tikzcd}[
  every arrow/.append style={-,thick},
  matrix of math nodes maybe/.append style={/tikz/cells={/tikz/nodes={/tikz/draw,/tikz/shape=circle,align=center,text width=\widthof{$x_1x_2x_3$}}}},
  row sep=large,
  column sep=large,
  thick,
  ]
        & x_1x_2x_3 \dar \dlar \drar \\
 x_1x_2 & x_1   x_3      \dlar \drar & x_2x_3 \\
 x_1 \uar
     \uar[bend left=20, shorten=.1cm, -stealth]
        &    x_2         \ular \urar &    x_3 \uar\\
        & \emptyset \uar \ular \urar \ular[shift left=.25cm, shorten=.25cm, -stealth]
\end{tikzcd}
\end{document}

Output

Answer 6

Building on top of Christoph's work and PSTikZ's work, I was able to get things compiled with XeLaTex so

where you can see a similar image as the handdrawn image here and the code

\documentclass[border=3pt,preview]{standalone}
\usepackage{pst-node}
\begin{document}
\begin{psmatrix}[mnode=Circle,radius=6mm,colsep=0.8,rowsep=0.8]
& [name=8] $x_1x_2x_3$ \\[-0.4\psyunit]
[name=5] $x_1x_2$ & [name=6] $x_1x_3$ & [name=7] $x_2x_3$\\
[name=2] $x_1$ & [name=3] $x_2$ & [name=4] $x_3$\\[-0.4\psyunit]
& [name=1] $\emptyset$
\ncline{8}{5}\ncline{8}{6}\ncline{8}{7}
\ncline{5}{3}\ncline{5}{2}
\ncline{6}{2}\ncline{6}{4}
\ncline{7}{3}\ncline{7}{4}
\ncline{1}{2}\ncline{1}{3}\ncline{1}{4}
\ncline[offset=5pt, linewidth=0.5\pslinewidth, arrows=->, nodesep=5pt]{1}{2}
\ncarc[offset=3pt, linewidth=0.5\pslinewidth, arrows=->, nodesep=4pt]{2}{5}
\end{psmatrix}
\end{document}