506 Algorithm~\ref{alg:VF2Pseu} is a high level description of |
506 Algorithm~\ref{alg:VF2Pseu} is a high level description of |
507 the VF2 matching algorithm. |
507 the VF2 matching algorithm. |
508 |
508 |
509 |
509 |
510 \begin{algorithm} |
510 \begin{algorithm} |
511 \algtext*{EndIf}%ne nyomtasson end if-et \algtext*{EndFor}%ne |
511 \algtext*{EndIf}%ne nyomtasson end if-et |
512 nyomtasson .. \algtext*{EndProcedure}%ne nyomtasson .. |
512 \algtext*{EndFor}%ne |
|
513 \algtext*{EndProcedure}%ne nyomtasson .. |
513 \caption{\hspace{0.5cm}$A\ high\ level\ description\ of\ VF2$}\label{alg:VF2Pseu} |
514 \caption{\hspace{0.5cm}$A\ high\ level\ description\ of\ VF2$}\label{alg:VF2Pseu} |
514 \begin{algorithmic}[1] |
515 \begin{algorithmic}[1] |
515 |
516 |
516 \Procedure{VF2}{State $s$, ProblemType $PT$} \If{$M(s$) covers |
517 \Procedure{VF2}{State $s$, ProblemType $PT$} \If{$M(s$) covers |
517 $V_{small}$} \State Output($M(s)$) \Else |
518 $V_{small}$} \State Output($M(s)$) \Else |
864 |
865 |
865 \begin{algorithm} |
866 \begin{algorithm} |
866 \algtext*{EndIf} |
867 \algtext*{EndIf} |
867 \algtext*{EndProcedure} |
868 \algtext*{EndProcedure} |
868 \algtext*{EndWhile} |
869 \algtext*{EndWhile} |
|
870 \algtext*{EndFor} |
869 \caption{\hspace{0.5cm}$The\ method\ of\ VF2++\ for\ determining\ the\ node\ order$}\label{alg:VF2PPPseu} |
871 \caption{\hspace{0.5cm}$The\ method\ of\ VF2++\ for\ determining\ the\ node\ order$}\label{alg:VF2PPPseu} |
870 \begin{algorithmic}[1] |
872 \begin{algorithmic}[1] |
871 \Procedure{VF2++order}{} \State $\mathcal{M}$ := $\emptyset$ |
873 \Procedure{VF2++order}{} \State $\mathcal{M}$ := $\emptyset$ |
872 \Comment{matching order} \While{$V_{small}\backslash \mathcal{M} |
874 \Comment{matching order} \While{$V_{small}\backslash \mathcal{M} |
873 \neq\emptyset$} \State $r\in$ arg max$_{deg}$ (arg |
875 \neq\emptyset$} \State $r\in$ arg max$_{deg}$ (arg |
920 |
922 |
921 \subsubsection{Induced subgraph isomorphism} |
923 \subsubsection{Induced subgraph isomorphism} |
922 \begin{claim} |
924 \begin{claim} |
923 \[LabCut_{IND}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!<\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\ \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| < |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|\] is a cutting function by IND. |
925 \[LabCut_{IND}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!<\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\ \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| < |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|\] is a cutting function by IND. |
924 \end{claim} |
926 \end{claim} |
925 The following claims can be proven similarly. |
927 |
926 \subsubsection{Graph isomorphism} |
928 \subsubsection{Graph isomorphism} |
927 \begin{claim} |
929 \begin{claim} |
928 \[LabCut_{ISO}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!\neq\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\ \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| \neq |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|\] is a cutting function by ISO. |
930 \[LabCut_{ISO}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!\neq\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\ \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| \neq |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|\] is a cutting function by ISO. |
929 \end{claim} |
931 \end{claim} |
930 |
932 |
995 in $V_{small}$ having label i, which is easy to compute in |
997 in $V_{small}$ having label i, which is easy to compute in |
996 $\Theta(|V_{small}|)$ steps. |
998 $\Theta(|V_{small}|)$ steps. |
997 |
999 |
998 Representing $\mathcal{M}\subseteq V_{small}$ as an array of |
1000 Representing $\mathcal{M}\subseteq V_{small}$ as an array of |
999 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. |
1001 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. |
1000 |
|
1001 After a node $u$ gets to the next place of the node order, |
|
1002 $F_\mathcal{M}[lab[u]]$ has to be decreased by one, because there is |
|
1003 one less covered node in $V_{large}$ with label $lab(u)$, that is why |
|
1004 min selection sort is preferred which gives the elements from left to |
|
1005 right in descending order, see Algorithm~\ref{alg:VF2PPProcess1}. |
|
1006 |
1002 |
1007 \subsubsection{Cutting rules} |
1003 \subsubsection{Cutting rules} |
1008 In Section~\ref{VF2PPCuttingRules}, the cutting rules were |
1004 In Section~\ref{VF2PPCuttingRules}, the cutting rules were |
1009 described using the sets $T_{small}$, $T_{large}$, $\tilde T_{small}$ |
1005 described using the sets $T_{small}$, $T_{large}$, $\tilde T_{small}$ |
1010 and $\tilde T_{large}$, which are dependent on the all-time mapping |
1006 and $\tilde T_{large}$, which are dependent on the all-time mapping |