1.1 --- a/damecco.tex	Wed Nov 23 02:07:56 2016 +0100
     1.2 +++ b/damecco.tex	Wed Nov 23 18:59:25 2016 +0100
     1.3 @@ -944,8 +944,8 @@
     1.4  \end{definition}
     1.5  
     1.6  \begin{algorithm}
     1.7 -\algtext*{EndIf}%ne nyomtasson end if-et \algtext*{EndFor}%ne
     1.8 -nyomtasson ..  \algtext*{EndProcedure}%ne nyomtasson ..
     1.9 +\algtext*{EndIf}
    1.10 +\algtext*{EndProcedure}
    1.11  \algtext*{EndWhile}
    1.12  \caption{\hspace{0.5cm}$The\ method\ of\ VF2++\ for\ determining\ the\ node\ order$}\label{alg:VF2PPPseu}
    1.13  \begin{algorithmic}[1]
    1.14 @@ -956,16 +956,16 @@
    1.15  \mathcal{M})$)\label{alg:findMin} \State Compute $T$, a BFS tree with
    1.16  root node $r$.  \For{$d=0,1,...,depth(T)$} \State $V_d$:=nodes of the
    1.17  $d$-th level \State Process $V_d$ \Comment{See Algorithm
    1.18 -  \ref{alg:VF2PPProcess1}) and \ref{alg:VF2PPProcess2}} \EndFor
    1.19 +  \ref{alg:VF2PPProcess1}} \EndFor
    1.20  \EndWhile \EndProcedure
    1.21  \end{algorithmic}
    1.22  \end{algorithm}
    1.23  
    1.24  \begin{algorithm}
    1.25 -\algtext*{EndIf}%ne nyomtasson end if-et \algtext*{EndFor}%ne
    1.26 -nyomtasson ..  \algtext*{EndProcedure}%ne nyomtasson ..
    1.27 +\algtext*{EndIf}
    1.28 +\algtext*{EndProcedure}%ne nyomtasson ..
    1.29  \algtext*{EndWhile}
    1.30 -\caption{\hspace{.5cm}$A\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess1}
    1.31 +\caption{\hspace{.5cm}$The\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess1}
    1.32  \begin{algorithmic}[1]
    1.33  \Procedure{VF2++ProcessLevel1}{$V_{d}$} \While{$V_d\neq\emptyset$}
    1.34  \State $m\in$ arg min$_{F_\mathcal{M}\circ\ lab}($ arg max$_{deg}($arg
    1.35 @@ -975,33 +975,13 @@
    1.36  \end{algorithmic}
    1.37  \end{algorithm}
    1.38  
    1.39 -\begin{algorithm}
    1.40 -\algtext*{EndIf}%ne nyomtasson end if-et \algtext*{EndFor}%ne
    1.41 -nyomtasson ..  \algtext*{EndProcedure}%ne nyomtasson ..
    1.42 -\algtext*{EndWhile}
    1.43 -\caption{\hspace{0.5cm}$Another\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess2}
    1.44 -\begin{algorithmic}[1]
    1.45 -\Procedure{VF2++ProcessLevel2}{$V_{d}$} \State Sort $V_d$ in
    1.46 -descending lex. order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$
    1.47 -\State Append the sorted $V_d$ to the end of $\mathcal{M}$ \State
    1.48 -Refresh $F_\mathcal{M}$ \EndProcedure
    1.49 -\end{algorithmic}
    1.50 -\end{algorithm}
    1.51  Algorithm~\ref{alg:VF2PPPseu} is a high level description of the
    1.52  matching order procedure of VF2++. It computes a BFS tree for each
    1.53  component in ascending order of their rarest $lab$ and largest $deg$,
    1.54  whose root vertex is the component's minimal
    1.55 -node. Algorithms~\ref{alg:VF2PPProcess1} and \ref{alg:VF2PPProcess2}
    1.56 -are two different methods to process a level of the BFS tree.
    1.57 -
    1.58 -After sorting the nodes of the current level in descending
    1.59 -lexicographic order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$,
    1.60 -Algorithm~\ref{alg:VF2PPProcess2} appends them simultaneously to the
    1.61 -matching order $\mathcal{M}$ and refreshes $F_\mathcal{M}$ just once,
    1.62 -whereas Algorithm~\ref{alg:VF2PPProcess1} appends the nodes separately
    1.63 -to $\mathcal{M}$ and refreshes $F_\mathcal{M}$ immediately, so it
    1.64 -provides up-to-date label information and may result in a more
    1.65 -efficient matching order.
    1.66 +node. Algorithm~\ref{alg:VF2PPProcess1} is a method to process a level of the BFS tree, which appends the nodes of the current level in descending
    1.67 +lexicographic order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$ separately
    1.68 +to $\mathcal{M}$, and refreshes $F_\mathcal{M}$ immediately.
    1.69  
    1.70  Claim~\ref{claim:MOclaim} shows that Algorithm~\ref{alg:VF2PPPseu}
    1.71  provides a matching order.
    1.72 @@ -1156,8 +1136,7 @@
    1.73  seen before, a pointer shows where the first node of the FIFO is, and
    1.74  another one shows where the next explored node has to be inserted. So
    1.75  the nodes of each level of the BFS tree can be processed by
    1.76 -Algorithms~\ref{alg:VF2PPProcess1} and
    1.77 -\ref{alg:VF2PPProcess2} in place by swapping nodes.
    1.78 +Algorithms~\ref{alg:VF2PPProcess1} in place by swapping nodes.
    1.79  
    1.80  After a node $u$ gets to the next place of the node order,
    1.81  $F_\mathcal{M}[lab[u]]$ has to be decreased by one, because there is
    1.82 @@ -1165,15 +1144,6 @@
    1.83  min selection sort is preferred which gives the elements from left to
    1.84  right in descending order, see Algorithm~\ref{alg:VF2PPProcess1}.
    1.85  
    1.86 -Note that using a $\Theta(n^2)$ sort absolutely does not slow down the
    1.87 -procedure on biological (and on sparse) graphs, since they have few
    1.88 -nodes on a level. If a level had a large number of nodes,
    1.89 -Algorithm~\ref{alg:VF2PPProcess2} would seem to be a better
    1.90 -choice with a $\Theta(nlog(n))$ or Bucket sort, but it may reduce the
    1.91 -efficiency of the matching procedure, since $F_\mathcal{M}(i)$ can not
    1.92 -be immediately refreshed, so it is unable to provide up-to-date label
    1.93 -information.
    1.94 -
    1.95  Note that the \textit{while loop} of Algorithm~\ref{alg:VF2PPPseu}
    1.96  takes one iteration per graph component and the graphs in biology are
    1.97  mostly connected.