diff options
| -rw-r--r-- | mgr.tex | 22 | ||||
| -rw-r--r-- | tree-marked.pdf | bin | 0 -> 10975 bytes | |||
| -rw-r--r-- | tree-marked.pdf_tex | 58 |
3 files changed, 79 insertions, 1 deletions
@@ -668,6 +668,24 @@ and $k$ will correspond to a marked node that's not on the path from $x$ to $y$ (or some unmarked vertex if there were no marked vertices at all in the range we check). +\begin{figure} + \centering + \def\svgwidth{0.5\columnwidth} + \input{tree-marked.pdf_tex} + \caption{ + A preprocessed marked tree. The marked vertices are colored dark grey. + To the left of each vertex is its pre-order number. To the right is its + post-order number. On the bottom is the table $\prefixtable$ with only + the marked vertices' prefix numbers not replaced by $\infty$. The red + rectangle marks the range for which we issue an RMQ question when + answering a highest marked descendant question form the vertex with + post-order index 7 down to the one with post-order index 2. + }\label{marked-figure} +\end{figure} + +See Figure \ref{marked-figure} for a visual example of the data structure +described. + \section{Answering branch infix regular questions} With the above problem solved, we are ready to finish our algorithm for branch @@ -685,7 +703,9 @@ copy of $Q$ on the path towards the copy of $Q$ that contains $y$?''. To achieve this, we create a copy of $T$ in which we mark the vertices where an edge from a $c$-colored vertex points to a vertex with a lower color. This tree we preprocess for highest marked descendant on path questions, solved in the -previous section. +previous section. Note that Figure \ref{marked-figure} is exactly the marked +tree we create and preprocess for the green color of the colored graph in Figure +\ref{tree-figure}. Now question answering can proceed similar to the word case. Given a question ``does the word on vertices from $x$ down to $y$ belong to $L$?'', let $x'$ be diff --git a/tree-marked.pdf b/tree-marked.pdf Binary files differnew file mode 100644 index 0000000..a98d784 --- /dev/null +++ b/tree-marked.pdf diff --git a/tree-marked.pdf_tex b/tree-marked.pdf_tex new file mode 100644 index 0000000..a205788 --- /dev/null +++ b/tree-marked.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 'tree-marked.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}{1322.73120886bp}% + \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,1.07734081)% + \lineheight{1}% + \setlength\tabcolsep{0pt}% + \put(0,0){\includegraphics[width=\unitlength,page=1]{tree-marked.pdf}}% + \end{picture}% +\endgroup% |