1.1 --- a/damecco.tex	Wed Nov 30 16:13:29 2016 +0100
     1.2 +++ b/damecco.tex	Wed Nov 30 16:52:36 2016 +0100
     1.3 @@ -274,7 +274,9 @@
     1.4  code --- has been published as a part of LEMON\cite{LEMON} open source
     1.5  graph library.
     1.6  
     1.7 -\section{Problem Statement}
     1.8 +Outline: Section~\ref{sec:ProbStat} defines the problems to be solved, Section~\ref{sec:VF2Alg} provides a description of VF2, Section~\ref{sec:VF2ppAlg} introduces VF2++, a new graph matching algorithm, Section~\ref{sec:VF2ppImpl} presents the details of an efficient implementation of VF2++, and Section~\ref{sec:ExpRes} compares VF2++ to a state of the art algorithm.
     1.9 +
    1.10 +\section{Problem Statement}\label{sec:ProbStat}
    1.11  This section provides a formal description of the problems to be
    1.12  solved.
    1.13  \subsection{Definitions}
    1.14 @@ -340,17 +342,13 @@
    1.15  The \textbf{graph isomorphism problem} can be defined as induced
    1.16  subgraph matching problem where the sizes of the two graphs are equal.
    1.17  
    1.18 -In addition to existence, it may be needed to show such a subgraph, or
    1.19 -it may be necessary to list all of them.
    1.20 +In addition, one may want to find a \textbf{single} mapping or \textbf{enumerate} all of them.
    1.21  
    1.22 -It should be noted that some authors misleadingly refer to the term
    1.23 +Note that some authors refer to the term
    1.24  \emph{subgraph isomorphism problem} as an \emph{induced subgraph
    1.25    isomorphism problem}.
    1.26  
    1.27 -The following sections give the descriptions of VF2, VF2++, VF2 Plus
    1.28 -and a particular comparison.
    1.29 -
    1.30 -\section{The VF2 Algorithm}
    1.31 +\section{The VF2 Algorithm}\label{sec:VF2Alg}
    1.32  This algorithm is the basis of both the VF2++ and the VF2 Plus.  VF2
    1.33  is able to handle all the variations mentioned in Section
    1.34    \ref{sec:CommProb}.  Although it can also handle directed graphs,
    1.35 @@ -549,7 +547,7 @@
    1.36    \tilde{T}_{1}(\mathfrak{m})|$ is a cutting function by $IND$.
    1.37  \end{claim}
    1.38  
    1.39 -\section{The VF2++ Algorithm}
    1.40 +\section{The VF2++ Algorithm}\label{sec:VF2ppAlg}
    1.41  Although any total ordering relation makes the search space of VF2 a
    1.42  tree, its choice turns out to dramatically influence the number of
    1.43  visited states. The goal is to determine an efficient one as quickly
    1.44 @@ -564,18 +562,15 @@
    1.45  
    1.46  In addition to the usual subgraph isomorphism, specialized versions
    1.47  for induced subgraph isomorphism and for graph isomorphism have been
    1.48 -designed. VF2++ has gained a runtime improvement of one order of
    1.49 -magnitude respecting induced subgraph isomorphism and a better
    1.50 -asymptotical behaviour in the case of graph isomorphism problem.
    1.51 +designed.
    1.52  
    1.53 -Note that a weaker version of the cutting rules and the more efficient
    1.54 -candidate set calculating were described in \cite{VF2Plus}, too.
    1.55 +Note that a weaker version of the cutting rules and an efficient
    1.56 +candidate set calculating were described in \cite{VF2Plus}.
    1.57  
    1.58  It should be noted that all the methods described in this section are
    1.59 -extendable to handle directed graphs and edge labels as well.\newline
    1.60 -
    1.61 +extendable to handle directed graphs and edge labels as well.
    1.62  The basic ideas and the detailed description of VF2++ are provided in
    1.63 -the following.
    1.64 +the following.\newline
    1.65  
    1.66  The goal is to find a matching order in which the algorithm is able to
    1.67  recognize inconsistency or prune the infeasible branches on the
    1.68 @@ -624,11 +619,11 @@
    1.69  \newline
    1.70  $\mathcal{L}(v):=black$
    1.71  \newline
    1.72 -$\mathcal{L}(\tilde{u}):=red \ \forall \tilde{u}\in (V_{1}\backslash
    1.73 -\{u\})$
    1.74 +$\mathcal{L}(\tilde{u}):=red \ \forall \tilde{u}\in V_{1}\backslash
    1.75 +\{u\}$
    1.76  \newline
    1.77 -$\mathcal{L}(\tilde{v}):=red \ \forall \tilde{v}\in (V_{2}\backslash
    1.78 -\{v\})$
    1.79 +$\mathcal{L}(\tilde{v}):=red \ \forall \tilde{v}\in V_{2}\backslash
    1.80 +\{v\}$
    1.81  \newline
    1.82  
    1.83  Now, any mapping by $\mathcal{L}$ must contain $(u,v)$, since
    1.84 @@ -732,7 +727,7 @@
    1.85  \caption{\hspace{.5cm}$The\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess1}
    1.86  \begin{algorithmic}[1]
    1.87  \Procedure{VF2++ProcessLevel}{$V_{d}$} \While{$V_d\neq\emptyset$}
    1.88 -\State $m\in$ arg min$_{F_\mathcal{M}\circ\ \mathcal{L}}($ arg max$_{deg}($arg
    1.89 +\State $m\in$ arg min$_{F_{\mathcal{M}\circ\ \mathcal{L}}}($ arg max$_{deg}($arg
    1.90  max$_{Conn_{\mathcal{M}}}(V_{d})))$ \State $V_d:=V_d\backslash m$
    1.91  \State Append node $m$ to the end of $\mathcal{M}$ \State Refresh
    1.92  $F_\mathcal{M}$ \EndWhile \EndProcedure
    1.93 @@ -778,10 +773,10 @@
    1.94  
    1.95  
    1.96  
    1.97 -\section{Implementation details}
    1.98 +\section{Implementation details}\label{sec:VF2ppImpl}
    1.99  This section provides a detailed summary of an efficient
   1.100  implementation of VF2++.
   1.101 -\subsubsection{Storing a mapping}
   1.102 +\subsection{Storing a mapping}
   1.103  After fixing an arbitrary node order ($u_0, u_1, ..,
   1.104  u_{|G_{1}|-1}$) of $G_{1}$, an array $M$ is usable to store
   1.105  the current mapping in the following way.
   1.106 @@ -794,7 +789,7 @@
   1.107  \]
   1.108  where $i\in\{0,1, ..,|G_{1}|-1\}$, $v\in V_{2}$ and $INV\!ALI\!D$
   1.109  means "no node".
   1.110 -\subsubsection{Avoiding the recurrence}
   1.111 +\subsection{Avoiding the recurrence}
   1.112  The recursion of Algorithm~\ref{alg:VF2Pseu} can be realized
   1.113  as a \textit{while loop}, which has a loop counter $depth$ denoting the
   1.114  all-time depth of the recursion. Fixing a matching order, let $M$
   1.115 @@ -811,7 +806,7 @@
   1.116  has been designed for biological- and sparse graphs, see the next
   1.117  section for details.
   1.118  
   1.119 -\subsubsection{Calculating the candidates for a node}
   1.120 +\subsection{Calculating the candidates for a node}
   1.121  Being aware of Claim~\ref{claim:claimCoverFromLeft}, the
   1.122  task is not to maintain the candidate set, but to generate the
   1.123  candidate nodes in $G_{2}$ for a given node $u\in V_{1}$.  In
   1.124 @@ -827,7 +822,7 @@
   1.125  $u$, and a linear one otherwise.
   1.126  
   1.127  
   1.128 -\subsubsection{Determining the node order}
   1.129 +\subsection{Determining the node order}
   1.130  This section describes how the node order preprocessing method of
   1.131  VF2++ can efficiently be implemented.
   1.132  
   1.133 @@ -841,7 +836,7 @@
   1.134  Representing $\mathcal{M}\subseteq V_{1}$ as an array of
   1.135  size $|V_{1}|$, both the computation of the BFS tree, and processing its levels by Algorithm~\ref{alg:VF2PPProcess1} can be done inplace by swapping nodes.
   1.136  
   1.137 -\subsubsection{Cutting rules}
   1.138 +\subsection{Cutting rules}
   1.139  In Section~\ref{VF2PPCuttingRules}, the cutting rules were
   1.140  described using the sets $T_{1}$, $T_{2}$, $\tilde T_{1}$
   1.141  and $\tilde T_{2}$, which are dependent on the all-time mapping
   1.142 @@ -876,7 +871,7 @@
   1.143  Using similar techniques, the consistency function can be evaluated in
   1.144  $\Theta(deg)$ steps, as well.
   1.145  
   1.146 -\section{Experimental results}
   1.147 +\section{Experimental results}\label{sec:ExpRes}
   1.148  This section compares the performance of VF2++ and VF2 Plus. According to
   1.149  our experience, both algorithms run faster than VF2 with orders of
   1.150  magnitude, thus its inclusion was not reasonable.