lemon-vf2: comparison damecco.tex

equal deleted inserted replaced

-:eace827f74a9
+:1942b1d71a41
 \end{cases}
 \]
 Where $i\in\{0,1, ..,|G_{small}|-1\}$, $v\in V_{large}$ and $INVALID$
 means "no node".
 \subsubsection{Avoiding the recurrence}
-Exploring the state space was described in a recursive fashion using
-sets (see Algorithm~\ref{alg:VF2Pseu}), which makes the
-algorithm easy to understand but does not show directly an efficient
-way of implementation. The following approach avoiding recursion and
-using lookup tables instead of sets is not only fast but has linear
-space complexity as well.
 The recursion of Algorithm~\ref{alg:VF2Pseu} can be realized
-as a while loop, which has a loop counter $depth$ denoting the
+as a \textit{while loop}, which has a loop counter $depth$ denoting the
-all-time depth of the recursion.  Fixing a matching order, let $M$
+all-time depth of the recursion. Fixing a matching order, let $M$
-denote the array storing the all-time mapping.  The initial state is
+denote the array storing the all-time mapping. Based on Claim~\ref{claim:claimCoverFromLeft},
-associated with the empty mapping, which means that $\forall i:
-M[i]=INVALID$ and $depth=0$.  In case of a recursive call, $depth$ has
-to be incremented, while in case of a return, it has to be
-decremented.  Based on Claim~\ref{claim:claimCoverFromLeft},
 $M$ is $INVALID$ from index $depth$+1 and not $INVALID$ before
-$depth$, i.e. $\forall i: i < depth \Rightarrow M[i]\neq INVALID$ and
+$depth$. $M[depth]$ changes
-$\forall i: i > depth \Rightarrow M[i]= INVALID$. $M[depth]$ changes
 while the state is being processed, but the property is held before
 both stepping back to a predecessor state and exploring a successor
 state.
 The necessary part of the candidate set is easily maintainable or
 E_{large}$. That is, each covered neighbour of $u$ has to be mapped to
 a covered neighbour of $v$.
 Having said that, an algorithm running in $\Theta(deg)$ time is
 describable if there exists a covered node in the component containing
-$u$. In this case choose a covered neighbour $u'$ of $u$ arbitrarily
+$u$, and a linear one other wise.
---- such a node exists based on
-Claim~\ref{claim:MOclaim}. With all the candidates of $u$
-being among the uncovered neighbours of $Pair(M,u')$, there are solely
-$deg(Pair(M,u'))$ nodes to check.
-An easy trick is to choose an $u'$, for which
-$|\{uncovered\ neighbours\ $ $of\ Pair(M,u')\}|$ is the smallest
-possible.
-Note that if $u$ is the first node of its component, then all the
-uncovered nodes of $G_{large}$ are candidates, so giving a sublinear
-method is impossible.
 \subsubsection{Determining the node order}
 This section describes how the node order preprocessing method of
 VF2++ can efficiently be implemented.
 For using lookup tables, the node labels are associated with the
 numbers $\{0,1,..,|K|-1\}$, where $K$ is the set of the labels. It
-enables $F_\mathcal{M}$ to be stored in an array, for which
+enables $F_\mathcal{M}$ to be stored in an array. At first, the node order
-$F_\mathcal{M}[i]=F_\mathcal{M}(i)$ where $i=0,1,..,|K|-1$. At first,
 $\mathcal{M}=\emptyset$, so $F_\mathcal{M}[i]$ is the number of nodes
 in $V_{small}$ having label i, which is easy to compute in
 $\Theta(|V_{small}|)$ steps.
-$\mathcal{M}\subseteq V_{small}$ can be represented as an array of
+Representing $\mathcal{M}\subseteq V_{small}$ as an array of
-size $|V_{small}|$.
+size $|V_{small}|$, both the computation of the BFS tree, and processing its levels by Algorithm~\ref{alg:VF2PPProcess1} can be done inplace by swapping nodes.
-The BFS tree is computed by using a FIFO data structure which is
-usually implemented as a linked list, but one can avoid it by using
-the array $\mathcal{M}$ itself. $\mathcal{M}$ contains all the nodes
-seen before, a pointer shows where the first node of the FIFO is, and
-another one shows where the next explored node has to be inserted. So
-the nodes of each level of the BFS tree can be processed by
-Algorithms~\ref{alg:VF2PPProcess1} in place by swapping nodes.
 After a node $u$ gets to the next place of the node order,
 $F_\mathcal{M}[lab[u]]$ has to be decreased by one, because there is
 one less covered node in $V_{large}$ with label $lab(u)$, that is why
 min selection sort is preferred which gives the elements from left to
 right in descending order, see Algorithm~\ref{alg:VF2PPProcess1}.
-Note that the \textit{while loop} of Algorithm~\ref{alg:VF2PPPseu}
-takes one iteration per graph component and the graphs in biology are
-mostly connected.
 \subsubsection{Cutting rules}
 In Section~\ref{VF2PPCuttingRules}, the cutting rules were
 described using the sets $T_{small}$, $T_{large}$, $\tilde T_{small}$
 and $\tilde T_{large}$, which are dependent on the all-time mapping
 $L[lab(u')]$ for all $u'\in \Gamma_{small}(u) \cap T_{small}(s)$ and
 decrementing $L[lab(v')]$ for all $v'\in\Gamma_{large} (v) \cap
 T_{large}(s)$, the first part of the cutting rules is checkable in
 $\Theta(deg)$ time by considering the proper signs of $L$. Setting $L$
 to zero takes $\Theta(deg)$ time again, which makes it possible to use
-the same table through the whole algorithm.  The second part of the
+the same table through the whole algorithm. The second part of the
 cutting rules can be verified using the same method with $\tilde
 T_{small}$ and $\tilde T_{large}$ instead of $T_{small}$ and
 $T_{large}$. Thus, the overall complexity is $\Theta(deg)$.
 An other integer lookup table storing the number of covered neighbours

changeset 9	2ad9aa6d7f63
parent 8	49574b75404b
child 10	1e4a79cd8332