From b0982e0ec16f870a1f37dbe01c8b9e7da19656f4 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 Apr 2008 12:39:47 +0200 Subject: [PATCH] Fixes to ET-trees. --- dyn.tex | 100 +++++++++++++++++++++++++++------------------------ macros.tex | 2 +- notation.tex | 1 - 3 files changed, 54 insertions(+), 49 deletions(-) diff --git a/dyn.tex b/dyn.tex index 5a7a879..9432318 100644 --- a/dyn.tex +++ b/dyn.tex @@ -198,32 +198,36 @@ trees, but it is much simpler and instead of path operations it offers efficient subtrees. It is also possible to attach auxiliary data to vertices and edges of the original tree. \defn\id{eulseq}% -The \df{Eulerian Tour sequence} $\Eul(T)$ of a~rooted tree~$T$ is the sequence of vertices of~$T$ as visited -by the depth-first traversal of~$T$. More precisely, it is generated by the following algorithm $\(v)$ +Let~$T$ be a~rooted tree. We will call a~sequence of vertices of~$T$ its \df{Eulerian Tour sequence (ET-sequence)} +if it lists the vertices visited by the depth-first traversal of~$T$. +More precisely, it can be generated by the following procedure $\(v)$ when it is invoked on the root of the tree: \algo \:Record~$v$ in the sequence. \:For each son~$w$ of~$v$: -\::Call $\(w)$ recursively. +\::Call $\(w)$. \::Record~$w$. \endalgo -\>One of the occurrences of each vertex is defined as its \df{active occurrence} and it will -be used to store auxiliary data associated with the vertex. +\>A~single tree can have multiple ET-sequences, corresponding to different orders in which the +sons can be enumerated in step~2. + +In every ET-tree, one of the occurrences of each vertex is defined as its \df{active occurrence} and +it will be used to store auxiliary data associated with that vertex. \obs -The ET-sequence contains a~vertex of degree~$d$ exactly $d$~times except for the root which +An~ET-sequence contains a~vertex of degree~$d$ exactly $d$~times except for the root which occurs $d+1$ times. The whole sequence therefore contains $2n-1$ elements. It indeed describes the order vertices on an~Eulerian tour in the tree with all edges doubled. Let us observe what happens -to the ET-sequence when we modify the tree. +to an~ET-sequence when we modify the tree. When we \em{delete} an~edge $uv$ from the tree~$T$ (let $u$~be the parent of~$v$), the sequence -$\Eul(T) = AuvBvuC$ (with no~$u$ nor~$v$ in~$B$) splits to two ET-sequences $AuC$ and $vBv$. -If there was only a~single occurrence of~$v$, it corresponded to a~leaf and thus the second -sequence should consist of $v$~alone. +$AuvBvuC$ (with no~$u$ nor~$v$ in~$B$) splits to two sequences $AuC$ and $vBv$. +If there was only a~single occurrence of~$v$, then $v$~was a~leaf and thus the sequence +transforms from $AuvuC$ to $AuC$ and $v$~alone. -\em{Changing the root} of the tree~$T$ from~$v$ to~$w$ changes $\Eul(T)$ from $vAwBwCv$ to $wBwCvAw$. +\em{Changing the root} of the tree~$T$ from~$v$ to~$w$ changes the sequence from $vAwBwCv$ to $wBwCvAw$. If $w$~was a~leaf, the sequence changes from $vAwCv$ to $wCvAw$. If $vw$ was the only edge of~$T$, -the sequence $vw$ becomes $wv$. Note that this works regardless of the presence of~$w$ inside~$B$. +the sequence $vw$ becomes $wv$. Note that this works regardless of the possible presence of~$w$ inside~$B$. \em{Joining} the roots of two trees by a~new edge makes their ET-sequences $vAv$ and~$wBw$ combine to $vAvwBwv$. Again, we have to handle the cases when $v$ or~$w$ has degree~1 separately: @@ -233,64 +237,66 @@ $v$~and~$wBw$ combine to $vwBwv$, and $v$~with~$w$ makes $vwv$. \hbox{\epsfbox{pic/ettree.eps}}\cr \noalign{\qquad\quad} \halign{#\hfil\cr - $\Eul(T_1) = 0121034546474308980$,~~$\Eul(T_2) = aba$. \cr - $\Eul(T_1-34) = 01210308980, 4546474$. \cr - $\Eul(T_1\hbox{~rooted at~3}) = 3454647430898012103$. \cr - $\Eul(T_1+0a+T_2)$: $0121034546474308980aba0$. \cr + $T_1: 0121034546474308980$,~~$T_2: aba$. \cr + $T_1-34: 01210308980, 4546474$. \cr + $T_1\hbox{~rooted at~3}: 3454647430898012103$. \cr + $T_1+0a+T_2$: $0121034546474308980aba0$. \cr }\cr }}{Trees and their ET-sequences} If any of the occurrences that we have removed from the sequence was active, there is always a~new occurrence of the same vertex that can stand in its place and inherit the auxiliary data. -The ET-trees will represent the ET-sequences by $(a,b)$-trees with the parameter~$a$ set upon +The ET-trees will store the ET-sequences as $(a,b)$-trees with the parameter~$a$ set upon initialization of the structure and with $b=2a$. We know from the standard theorems of $(a,b)$-trees (see for example \cite{clrs}) that the depth of a~tree with $n$~leaves is always $\O(\log_a n)$ and that all basic operations including insertion, deletion, search, splitting and joining the trees -run in time $\O(a\log_a n)$ in the worst case. +run in time $\O(b\log_a n)$ in the worst case. -We will use the ET-trees to maintain a~spanning forest of the current graph. The auxiliary data of -each vertex will hold a~list of edges incident with the given vertex, which do not lie in the +We will use the ET-trees to maintain a~spanning forest of the dynamic graph. The auxiliary data of +each vertex will hold a~list of edges incident with the given vertex, that do not lie in the forest. Such edges are usually called the \df{non-tree edges.} \defn -\df{Eulerian Tour trees} are a~data structure that represents a~forest of trees and a~set of non-tree +\df{Eulerian Tour trees (ET-trees)} are a~data structure that represents a~forest of trees and a~set of non-tree edges associated with the vertices of the forest. To avoid confusion, we will distinguish between -\df{original} vertices and edges (of the original trees) and the vertices and edges of the +\df{original} vertices and edges (of the given trees) and the vertices and edges of the data structure. The structure consists of: \itemize\ibull -\:A~collection of $(a,b)$-trees with some fixed parameters $a$ and~$b$. +\:A~collection of $(a,b)$-trees of some fixed parameters $a$ and~$b$. Each such tree corresponds to one of the original trees~$T$. Its leaves (in the usual tree order) correspond to the elements - of the ET-sequence $\Eul(T)$. Each two consecutive leaves $u$ and~$v$ are separated + of an~ET-sequence for~$T$. Each two consecutive leaves $u$ and~$v$ are separated by a~unique key stored in an~internal vertex of the $(a,b)$-tree. This key is used to represent the original edge~$uv$. Each original edge is therefore kept in both its orientations. -\:A~mapping $\(v)$ that maps each original vertex to the leaf containing its active occurrence. -\:A~mapping $\(e)$ that maps an~original edge~$e$ to one of the internal keys representing it. -\:A~mapping $\(k)$ that maps an~internal key~$k$ to the other internal key of the same - original edge. +\:Mappings \, \ and \: + \itemize\icirc + \:$\(v)$ maps each original vertex to the leaf containing its active occurrence; + \:$\(e)$ of an~original edge~$e$ is one of the internal keys representing~it; + \:$\(k)$ pairs an~internal key~$k$ with the other internal key of the same original edge. + \endlist \:A~list of non-tree edges placed in each leaf. The lists are allowed to be non-empty only in the leaves that represent active occurrences of original vertices. \:Boolean \df{markers} in the internal vertices that signal presence of a~non-tree - edge anywhere in the subtree rooted at that internal vertex. + edge anywhere in the subtree rooted at the internal vertex. \:Counters $\(v)$ that contain the number of leaves in the subtree rooted at~$v$. \endlist -\>The structure supports the following operations on the original trees: + +\defn +The ET-trees support the following operations on the original trees: \itemize\ibull \:\ --- Create a~single-vertex tree. \:$\(u,v)$ --- Join two different trees by an~edge~$uv$ and return a~unique identifier of this edge. \:$\(e)$ --- Split a~tree by removing the edge~$e$ given by its identifier. -\:$\(v)$ --- Return the root of the ET-tree containing the vertex~$v$. This can be used - to test whether two vertices lie in the same tree. However, the root is not guaranteed - to stay the same when the tree is modified by a~\ or \. +\:$\(u,v)$ --- Test if the vertices $u$ and~$v$ lie in the same tree. \:$\(v)$ --- Return the number of vertices in the tree containing the vertex~$v$. \:$\(v,e)$ --- Add a~non-tree edge~$e$ to the list at~$v$ and return a~unique identifier of this edge. \:$\(e)$ --- Delete a~non-tree edge~$e$ given by its identifier. -\:$\(v)$ --- Return non-tree edges stored in the same tree as~$v$. +\:$\(v)$ --- Return a~list of non-tree edges associated with the vertices + of the $v$'s tree. \endlist -\>If the non-tree edges have weights, \impl We will implement the operations on the ET-trees by translating the intended changes of the @@ -302,12 +308,12 @@ the $(a,b)$-trees. and joins them back in the different order. \ of two trees can be accomplished by making both vertices the roots of their trees first -and joining the roots by an~edge afterwards. Re-rooting again involves splits and joins of $(a,b)$-trees. +and joining the roots by an~edge afterwards. Re-rooting involves splits and joins of $(a,b)$-trees. As we can split at any occurrence of the new root vertex, we will use the active occurrence -which we remember. Joining of the roots translated to joining of the $(a,b)$-trees. +which we remember. Linking of the roots is translated to joining of the $(a,b)$-trees. -\ just follows parent pointers in the $(a,b)$-tree and it walks the path from the leaf -to the root. +\ follows parent pointers from both $u$ and~$v$ to the roots of their trees. +Then it checks if the roots are equal. \ finds the root and returns its counter. @@ -322,17 +328,17 @@ counter and, if necessary, the markers and counters on the path to the root. \ traverses the tree recursively from the root, but it does not enter the subtrees whose roots are not marked. -Analysis of the time complexity is now straightforward: +Analysis of time complexity of the operations is now straightforward: \thmn{Eulerian Tour trees, Henzinger and Rauch \cite{henzinger:randdyn}}\id{etthm}% The ET-trees perform the operations \ and \ in time $\O(a\log_a n)$, \ -in $\O(1)$, \, \, and \ in $\O(\log_a n)$, and +in $\O(1)$, \, \, \, and \ in $\O(\log_a n)$, and \ in $\O(a\log_a n)$ per edge reported. Here $n$~is the number of vertices in the original forest and $a\ge 2$ is an~arbitrary constant. \proof We set $b=2a$. Our implementation performs $\O(1)$ operations on the $(a,b)$-trees -per operation on the ET-tree, plus $\O(1)$ other operations. We apply the standard theorems +per operation on the ET-tree, plus $\O(1)$ other work. We apply the standard theorems on the complexity of $(a,b)$-trees \cite{clrs}. \qed @@ -342,18 +348,18 @@ of~$n$ can also have its beauty. Suppose that there is a~data structure which ma spanning forest of a~dynamic graph. Suppose also that the structure works in time $\O(\log^k n)$ per operation and that it reports $\O(1)$ changes in the spanning forest for every change in the graph. If we keep the spanning forest in ET-trees with $a=\log n$, the updates of the -data structure cost an~extra $\O(\log^2 n / \log\log n)$, but queries accelerate to $\O(\log +data structure cost an~additional $\O(\log^2 n / \log\log n)$, but connectivity queries accelerate to $\O(\log n/\log\log n)$. \paran{ET-trees with weights} -In some cases, we will also need to represent weighted graphs and enumerate the non-tree +In some cases, we will also need a~representation of weighted graphs and enumerate the non-tree edges in order of their increasing weights (in fact, it will be sufficient to find the lightest one, remove it and iterate). This can be handled by a~minute modification of the ET-trees. The tree edges will remember their weight in the corresponding internal keys of the ET-tree. We replace each list of non-tree edges by an~$(a,b)$-tree keeping the edges sorted by weight. -We also store the minimum element of the tree separately, so that it can be accessed in constant +We also store the minimum element of that tree separately, so that it can be accessed in constant time. The boolean \em{marker} will then become the minimum weight of a~non-tree edge attached to the particular subtree, which can be recalculated as easy as the markers can. Searching for the lightest non-tree edge then just follows the modified markers. @@ -373,7 +379,7 @@ The time bounds in Theorem \ref{etthm} hold for the weighted ET-trees, too. \section{Dynamic connectivity} The fully dynamic connectivity problem has a~long and rich history. In the 1980's, Frederickson \cite{frederickson:dynamic} -has used his topological trees to construct a~dynamic connectivity algorithm of complexity $\O(\sqrt m)$ per update +has used his topological trees to construct a~dynamic connectivity algorithm of complexity $\O(\sqrt m)$ per update and $\O(1)$ per query. Eppstein et al.~\cite{eppstein:sparsify} have introduced a~sparsification technique which can bring the updates down to $\O(\sqrt n)$. Later, several different algorithms with complexity on the order of $n^\varepsilon$ were presented by Henzinger and King \cite{henzinger:mst} and also by Mare\v{s} \cite{mares:dga}. @@ -396,7 +402,7 @@ We will maintain the following \em{invariants:} \def\iinv{{\bo I\the\itemcount~}} \numlist\iinv \:$F$~is the maximum spanning forest of~$G$ with respect to the levels. In other words, -if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uw)}$. +if $uv$ is a~non-tree edge, then $u$ and~$v$ are connected in~$F_{\ell(uv)}$. \:For each~$i$, the components of~$F_i$ have at most $\lfloor n/2^i \rfloor$ vertices. This implies that all~$F_i$ for $i>L$ are empty. \endlist diff --git a/macros.tex b/macros.tex index 21ef178..52b2835 100644 --- a/macros.tex +++ b/macros.tex @@ -54,7 +54,6 @@ \def\E{{\bb E}} \def\crpt{\mathbin{\Uparrow}} \def\C{{\cal C}} -\def\Eul{{\cal E}} \def\brk{\hfil\break} @@ -195,6 +194,7 @@ \def\endlist{\interlistskip\endgroup} \def\ibull{\raise0.2ex\hbox{$\bullet$}} % Signs frequently used for \itemize +\def\icirc{\raise0.2ex\hbox{$\circ$}} % Signs frequently used for \itemize \def\idot{\raise0.2ex\hbox{$\cdot$}} \def\istar{\raise0.2ex\hbox{$\ast$}} diff --git a/notation.tex b/notation.tex index daba11c..8693a5d 100644 --- a/notation.tex +++ b/notation.tex @@ -92,7 +92,6 @@ \n{$a(x,n)$}{The inverse of the $x$-th row of the Ackermann's function \[ackerinv]} \n{$a(n)$}{The diagonal inverse of the Ackermann's function \[ackerinv]} \n{$\alpha(m,n)$}{$\alpha(m,n) := \min\{ x\ge 1 \mid A(x,4\lceil m/n\rceil) > \log n \}$ \[ackerinv]} -\n{$\Eul(T)$}{The Eulerian tour sequence for a~tree~$T$ \[eulseq]} } %-------------------------------------------------------------------------------- -- 2.39.2