# Generating adjacency matrices from isomorphic graphs

Here are some isomorphic graphs and their corresponding adjacency matrices. I can draw the graphs with tikz. But I'm not sure the best way to draw the matrices. Is it possible to generate one from the other? What's the right way to approach it?

Here's an example of the code to generate a graph:

\documentclass{standalone}
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}
\tikzset{Bullet/.style={circle,draw,fill=black,scale=0.75}}
\node[Bullet,label=left :{$e_1$}] (E1) at (0,2) {} ;
\node[Bullet,label=above:{$e_2$}] (E2) at (1,3) {} ;
\node[Bullet,label=right:{$e_3$}] (E3) at (2,2) {} ;
\node[Bullet,label=right:{$e_4$}] (E4) at (2,0) {} ;
\node[Bullet,label=left :{$e_5$}] (E5) at (0,0) {} ;
\draw[thick] (E1)--(E2)--(E3)--(E4)--(E5)--(E1) {} ;
\end{tikzpicture}
\end{document}
• Shouldn't it be the other way around: you construct the diagrams from the adjacency matrices? – user121799 Mar 25 '19 at 3:46
• @marmot Probably, normally. Actually I don't think so. I mean.. Either way is probably good. But I have some graphs drawn up, and I want to draw the matrices to suit them. If I can't figure it out programmatically, I'll just draw them up separately. Either with LaTeX somehow or with Adobe Illustrator, or some spreadsheet/word processor. LaTeX would be nice though. – voices Mar 25 '19 at 4:41
• Your graphics would be more informative if you did not shuffle vertex locations around between (a), (b) and (c). – Szabolcs Mar 25 '19 at 8:56
• @Szabolcs that's exactly what I've done. Just need to draw the adjacency matrix. The image I posted was just a screenshot I had on my phone. But I've drawn them like you say. The vertices and labels stay the same, and the edges change. – voices Mar 25 '19 at 9:31

This is in case you change your mind and use the adjacency matrices to draw the graphs. TikZ allows you to define arrays, see p. 999 of the pgfmanual. And these arrays can be converted to tables using this nice answer. And these matrices/arrays can also be used to define the graphs.

\documentclass[tikz,border=3.14mm]{standalone}
\usepackage{etoolbox}
\usetikzlibrary{matrix,positioning}
% building the table in a foreach loop from https://tex.stackexchange.com/a/60400/121799
\begin{document}
\begin{tikzpicture}[Bullet/.style={circle,draw,fill=black,inner sep=1.5pt},
adjacency matrix/.style={ampersand replacement=\&,matrix of math nodes,
row 1/.append style={nodes={font=\boldmath}},
column 1/.append style={nodes={font=\boldmath}},nodes in empty cells,
nodes={draw,minimum width=1.5em,text height=1.8ex},column sep=-\pgflinewidth,row
sep=-\pgflinewidth}]
% first matrix
{{0,0,1,1,0},%
{0,0,0,1,1},%
{1,0,0,0,1},%
{1,1,0,0,0},%
{0,1,1,0,0}}}
\let\mymatrixcontent\empty
\def\mymatrixcontent{|[draw=none]|\& 1 \& 2 \& 3 \& 4  \& 5\\}
\begin{scope}[local bounding box=left]
\foreach \X in {1,...,5}
{\node[Bullet,label=90+72-\X*72:{$e_\X$}] (E\X) at (90+72-\X*72:2) {} ;}
\foreach \X in {1,...,5}
{\begingroup\edef\x{\endgroup
\noexpand\gappto\noexpand\mymatrixcontent{\X }}\x
\foreach \Y in {1,...,5}
\ifnum\itest=1
\draw (E\X) -- (E\Y);
\begingroup\edef\x{\endgroup
\noexpand\gappto\noexpand\mymatrixcontent{\& 1 }}\x
\else
\begingroup\edef\x{\endgroup
\noexpand\gappto\noexpand\mymatrixcontent{ \&}}\x
\fi
}
\gappto\mymatrixcontent{\\}
}
\end{scope}
\matrix (leftmat) [below=of left,adjacency matrix]{
\mymatrixcontent
};
%
% second matrix
{{0,1,0,0,1},%
{1,0,1,0,0},%
{0,1,0,1,0},%
{0,0,1,0,1},%
{1,0,0,1,0}}}
\let\mymatrixcontent\empty
\def\mymatrixcontent{|[draw=none]|\& 1 \& 2 \& 3 \& 4  \& 5\\}
\begin{scope}[local bounding box=middle,xshift=5cm]
\foreach \X in {1,...,5}
{\node[Bullet,label=90+72-\X*72:{$e_\X$}] (E\X) at (90+72-\X*72:2) {} ;}
\foreach \X in {1,...,5}
{\begingroup\edef\x{\endgroup
\noexpand\gappto\noexpand\mymatrixcontent{\X }}\x
\foreach \Y in {1,...,5}
\ifnum\itest=1
\draw (E\X) -- (E\Y);
\begingroup\edef\x{\endgroup
\noexpand\gappto\noexpand\mymatrixcontent{\& 1 }}\x
\else
\begingroup\edef\x{\endgroup
\noexpand\gappto\noexpand\mymatrixcontent{ \&}}\x
\fi
}
\gappto\mymatrixcontent{\\}
}
\end{scope}
\matrix (midmat) [below=of middle,adjacency matrix]{
\mymatrixcontent
};
% third matrix
{{0,1,0,1,0},%
{1,0,0,0,1},%
{0,0,0,1,1},%
{1,0,1,0,0},%
{0,1,1,0,0}}}
\let\mymatrixcontent\empty
\def\mymatrixcontent{|[draw=none]|\& 1 \& 2 \& 3 \& 4  \& 5\\}
\begin{scope}[local bounding box=right,xshift=10cm]
\foreach \X in {1,...,3}
{\node[Bullet,label=90+72-\X*72:{$e_\X$}] (E\X) at (90+72-\X*72:2) {} ;}
\node[Bullet,label=90+72-4*72:{$e_5$}] (E5) at (90+72-4*72:2) {} ;
\node[Bullet,label=90+72-5*72:{$e_4$}] (E4) at (90+72-5*72:2) {} ;
\foreach \X in {1,...,5}
{\begingroup\edef\x{\endgroup
\noexpand\gappto\noexpand\mymatrixcontent{\X }}\x
\foreach \Y in {1,...,5}
\ifnum\itest=1
\draw (E\X) -- (E\Y);
\begingroup\edef\x{\endgroup
\noexpand\gappto\noexpand\mymatrixcontent{\& 1 }}\x
\else
\begingroup\edef\x{\endgroup
\noexpand\gappto\noexpand\mymatrixcontent{ \&}}\x
\fi
}
\gappto\mymatrixcontent{\\}
}
\end{scope}
\matrix (rightmat) [below=of right,adjacency matrix]{
\mymatrixcontent
};

\end{tikzpicture}
\end{document}

• Not bad, can we get the matrix lines drawn in or is it just like that – voices Mar 25 '19 at 6:08
• @tjt263 Yes, sure. – user121799 Mar 25 '19 at 6:16
• Excellent. Wish I could go the other way. Maybe I will just try to draw them manually instead. – voices Mar 25 '19 at 6:31
• What package can I draw them with manually? I like exactly how yours look. – voices Mar 25 '19 at 9:47
• @tjt263 Sorry, I do not understand your question (because I do not know what "manually" means), nor your concerns. In order to draw these graphs, you need to know how they should look. The adjacency matrices have an almost minimal set of information. What kind of minimal set of information are you proposing to define the graphs? – user121799 Mar 25 '19 at 14:49

Here is a sagetex solution which uses the computer algebra system, SAGE, to do the work. SAGE has built in knowledge of different classes of graphs and has some compatibility with LaTeX and Tikz and can solve some graph parameters as well. All that knowledge means SAGE is not part of the LaTeX distribution, but this is easily handled with a free Cocalc account. It might be my lack of knowledge about the subject but I had trouble trying to get the graphs to look exactly the way you have drawn them but if you're willing to give up some control here is a straightforward implementation of what you want.

\documentclass{article}
\usepackage{sagetex}
\usepackage{tikz,tkz-graph,tkz-berge}
\begin{document}
\begin{sagesilent}
H = Graph({1:[2], 2:[3], 3:[4], 4:[5], 5:[1]})
H.set_pos(H.layout_circular()) #arrange the vertices in a circle
H.set_latex_options(scale=1.0,graphic_size=(3,3))
######
J = Graph({1:[2], 2:[5], 3:[4], 4:[1], 5:[3]})
J.set_pos(H.layout_circular()) #arrange the vertices in a circle
J.set_latex_options(scale=1.0,graphic_size=(3,3))
######
K = Graph({1:[3], 2:[4], 3:[5], 4:[1], 5:[2]})
K.set_pos(H.layout_circular()) #arrange the vertices in a circle
K.set_latex_options(scale=1.0,graphic_size=(3,3))
\end{sagesilent}
Consider the three graphs below:\\\\

\begin{tabular}{ccc}
\begin{tikzpicture}
\GraphInit[vstyle=Normal]
\SetVertexNormal[Shape=circle,LineWidth = 1pt]
\tikzset{EdgeStyle/.append style = {color = black, line width=1pt}}
\sage{H}
\end{tikzpicture} &
\begin{tikzpicture}
\GraphInit[vstyle=Normal]
\SetVertexNormal[Shape=circle,LineWidth = 1pt]
\tikzset{EdgeStyle/.append style = {color = black, line width=1pt}}
\sage{J}
\end{tikzpicture} &
\begin{tikzpicture}
\GraphInit[vstyle=Normal]
\SetVertexNormal[Shape=circle,LineWidth = 1pt]
\tikzset{EdgeStyle/.append style = {color = black, line width=1pt}}
\sage{K}
\end{tikzpicture}\\
$\sage{H.adjacency_matrix()}$ & $\sage{J.adjacency_matrix()}$ &    $\sage{K.adjacency_matrix()}$\\\\
(a) & (b) & (c)\\
\end{tabular}
\end{document}

The output is:

I set up the graph as a list of what a vertex is adjacent to; eg, H = Graph({1:[2], 2:[3], 3:[4], 4:[5], 5:1}) says that vertex 1 is adjacent to 2, vertex 2 is adjacent to 3, and so until vertex 5 is adjacent to 1. Setting a circular layout makes Sage place the vertices for you, and by setting options we can change the size of the graphic. So Sage creates the graph with \sage{H} and the adjacency matrix with $\sage{H.adjacency_matrix()}$.

By having a CAS do the work you can change the graph and SAGE will do the work without mistakes. This saves you having to code other examples and possibly making a mistake along the way.

EDIT: Using Cocalc is the easiest way to get started but I should mention that SAGE can be installed on your computer so that Cocalc is not needed. I have this under Linux but, years back, had struggled with Windows installation. Perhaps it's better now? The installation guide is here. It's worth mentioning that you can test out SAGE code found on the website by using a Sage Cell Server like the one here just be aware that getting the code to work via LaTeX is usually a little different, though. Finally, a roughly 900 page reference manual just for graph theory should help answer questions you might have. You can find that in PDF form here. Finally, SAGE allows you to use Python in your LaTeX document. Between LaTeX, Python, and a computer algebra system you have the power to handle just about everything. The CTAN documentation on sagetex is the best place to start for an overview of the package. That is here.

• Not bad, not bad. Cocalc, huh? I use Overleaf (formerly ShareLaTeX). I'll check it out. Thanks. – voices Mar 26 '19 at 4:04
• I added to my response above. It is possible to install SAGE on your computer so Cocalc is not needed but that can be complicated. Link for those instructions, a SAGE graph theory reference guide, and SAGE cell server link (for testing SAGE code on website) are provided above. – DJP Mar 26 '19 at 12:25