7

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)

enter image description here

13

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}

Hypercubes on 3,4,5 generators

  • @hhh Re compiling: commandline with TL2013. Re ordering of vertices: vertical is by number of 1s in the binary expansion, horizontal is then by natural order. – Loop Space Aug 23 '13 at 11:27
  • 2
    Start with a number k between 0 and 2^n-1. Convert it to binary. Count the 1s in the binary representation. That gives the height of the node. Then order all of the nodes that are at the same height by numerical order. So 1,2,4,8,16 all have a single 1 in their binary expansion so are at the same height, and we order them 1,2,4,8,16. – Loop Space Aug 23 '13 at 12:12
  • How can I plot seventh hypercube with this? It is so large picture that I cannot see it -- asked in chat. – hhh Aug 25 '13 at 19:05
  • @hhh You want to visualize traversing a 7-hypercube? Have you seen the thing? emeagwali.com/education/inventions-discoveries/… That'd be quite a visualization challenge in itself, nothing a web platform will likely solve for you. And especially not without some more ideas how you think this should look. – Christian Sep 17 '13 at 13:35
13

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

enter image description here

Algorithm (beamer, step-for-step)

enter image description here

  • Is the beamer, step-for-step something you can use in every tikz Drawing? or is it just a title in your answer – Arne Timperman Jan 23 '16 at 13:35
8
+150

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:

enter image description here

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

  • 2
    There shouldn't be a line from 3 to 6 (I know that there is in the handdrawn picture, but there shouldn't be). – Loop Space Aug 22 '13 at 20:34
  • @AndrewStacey Thank you, I corrected the code and the image. – Christoph Aug 22 '13 at 20:42
  • +1 nice answer. You'll see a few folks on the site use the standalone documentclass for images. imho, it's also nice to use arara for the directives, especially for code that uses PSTricks- the compilation process can be intimidating for some folks not familiar with it :) – cmhughes Aug 22 '13 at 20:52
  • @hhh Go with latex-dvips-ps2pdf or xelatex route of compilation or \usepackage[pdf]{pstricks} before \usepackage{pst-node} with pdflatex -shell-escape test. – texenthusiast Aug 22 '13 at 21:08
  • 1
    @hhh To add arrows, use e.g. \ncline[arrows=->] or \ncline[arrows=<-]. You could also use \ncarc to have slightly curved connections. – Christoph Aug 22 '13 at 21:15
5

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

fourth hypercube graph

4

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

enter image description here

4

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

enter image description here

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}
  • pstricks option and preview environment can be removed, see my edit in Christoph's answer. – kiss my armpit Aug 23 '13 at 12:59
  • @PSTikZ thank you, removed them as you guided. – hhh Aug 23 '13 at 13:05
  • Where did you know that mnode must be Circle rather than circle to make radius option works as expected? I do not find it in the documentation. – kiss my armpit Aug 23 '13 at 13:30
  • @PSTikZ Found an example here, "psmatrix circle radius" returned the result :) – hhh Aug 23 '13 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.