From 9eac34349bdf4a0e7a7c57f62a7c8f97ef93d510 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Mon, 6 Dec 2021 19:10:21 +0100
Subject: Add word figure

---
 .gitignore   |   2 +-
 mgr.tex      |  25 ++++++++++++++++++++++---
 word.pdf     | Bin 0 -> 27577 bytes
 word.pdf_tex |  58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 81 insertions(+), 4 deletions(-)
 create mode 100644 word.pdf
 create mode 100644 word.pdf_tex

diff --git a/.gitignore b/.gitignore
index 7ca729e..a8d3e03 100644
--- a/.gitignore
+++ b/.gitignore
@@ -3,6 +3,6 @@
 *.bcf
 *.blg
 *.log
-*.pdf
+mgr.pdf
 *.run.xml
 *.toc
diff --git a/mgr.tex b/mgr.tex
index f64300f..c2d3405 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -4,6 +4,7 @@
 
 \usepackage{definitions}
 \usepackage[backend=biber]{biblatex}
+\usepackage{graphicx}
 \addbibresource{mgr.bib}
 
 \usepackage{amsmath}
@@ -431,12 +432,30 @@ The construction is as follows:
     \item Repeat steps 3.-5. for each successive color up to $|Q|$.
 \end{enumerate}
 
-Additionally, for each vertex $i.q$, we store the index of the next copy of $Q$ in
-which the path of this vertex's color is broken by a lower color. Put this
+\begin{figure}
+    \centering
+    \def\svgwidth{\columnwidth}
+    \input{word.pdf_tex}
+    \caption{
+        The data structure for infix regular queries over word $abaacbc$ and a
+        simple automaton with 4 states. As shown by the color blotches below the
+        graph, red is color 1, with the highest priority, green is color 2 with
+        the next priority, pink is color 3, blue is color 4, with the lowest
+        priority.
+        The information from $\breaktable$ is not shown in the figure, but it
+        amounts to a pointer from each vertex to the last vertex on its
+        connected single color component.
+    }\label{word-figure}
+\end{figure}
+
+Additionally, for each vertex $i.q$, we store the index of the next copy of $Q$
+in which the path of this vertex's color is broken by a lower color. Put this
 information in table $\breaktable$. For example, if $i.q$ is colored with color
 $c$, and when following the deterministic path from $i.q$, all encountered
 vertices are colored $c$ until $j.q'$ which is colored $c'$, then we set
-$\breaktable[i.q] = j - 1$.
+$\breaktable[i.q] = j - 1$. See Figure \ref{word-figure} for a visual
+representation of the data structure described for an example word and
+automaton.
 
 We can compute $\breaktable$ in linear time with a single backwards pass through
 the colored graph.
diff --git a/word.pdf b/word.pdf
new file mode 100644
index 0000000..2be51a6
Binary files /dev/null and b/word.pdf differ
diff --git a/word.pdf_tex b/word.pdf_tex
new file mode 100644
index 0000000..8589096
--- /dev/null
+++ b/word.pdf_tex
@@ -0,0 +1,58 @@
+%% Creator: Inkscape 1.1.1 (3bf5ae0d25, 2021-09-20, custom), www.inkscape.org
+%% PDF/EPS/PS + LaTeX output extension by Johan Engelen, 2010
+%% Accompanies image file 'word.pdf' (pdf, eps, ps)
+%%
+%% To include the image in your LaTeX document, write
+%%   \input{<filename>.pdf_tex}
+%%  instead of
+%%   \includegraphics{<filename>.pdf}
+%% To scale the image, write
+%%   \def\svgwidth{<desired width>}
+%%   \input{<filename>.pdf_tex}
+%%  instead of
+%%   \includegraphics[width=<desired width>]{<filename>.pdf}
+%%
+%% Images with a different path to the parent latex file can
+%% be accessed with the `import' package (which may need to be
+%% installed) using
+%%   \usepackage{import}
+%% in the preamble, and then including the image with
+%%   \import{<path to file>}{<filename>.pdf_tex}
+%% Alternatively, one can specify
+%%   \graphicspath{{<path to file>/}}
+%% 
+%% For more information, please see info/svg-inkscape on CTAN:
+%%   http://tug.ctan.org/tex-archive/info/svg-inkscape
+%%
+\begingroup%
+  \makeatletter%
+  \providecommand\color[2][]{%
+    \errmessage{(Inkscape) Color is used for the text in Inkscape, but the package 'color.sty' is not loaded}%
+    \renewcommand\color[2][]{}%
+  }%
+  \providecommand\transparent[1]{%
+    \errmessage{(Inkscape) Transparency is used (non-zero) for the text in Inkscape, but the package 'transparent.sty' is not loaded}%
+    \renewcommand\transparent[1]{}%
+  }%
+  \providecommand\rotatebox[2]{#2}%
+  \newcommand*\fsize{\dimexpr\f@size pt\relax}%
+  \newcommand*\lineheight[1]{\fontsize{\fsize}{#1\fsize}\selectfont}%
+  \ifx\svgwidth\undefined%
+    \setlength{\unitlength}{1493.00403586bp}%
+    \ifx\svgscale\undefined%
+      \relax%
+    \else%
+      \setlength{\unitlength}{\unitlength * \real{\svgscale}}%
+    \fi%
+  \else%
+    \setlength{\unitlength}{\svgwidth}%
+  \fi%
+  \global\let\svgwidth\undefined%
+  \global\let\svgscale\undefined%
+  \makeatother%
+  \begin{picture}(1,0.50303459)%
+    \lineheight{1}%
+    \setlength\tabcolsep{0pt}%
+    \put(0,0){\includegraphics[width=\unitlength,page=1]{word.pdf}}%
+  \end{picture}%
+\endgroup%
-- 
cgit v1.2.3