433 isomorphism $\Leftrightarrow$ $M$ is whole mapping and $\forall u,v |
433 isomorphism $\Leftrightarrow$ $M$ is whole mapping and $\forall u,v |
434 \in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow |
434 \in{V_{small}} : (u,v)\in{E_{small}} \Leftrightarrow |
435 (Pair(M,u),Pair(M,v))\in E_{large}$. |
435 (Pair(M,u),Pair(M,v))\in E_{large}$. |
436 \end{center} |
436 \end{center} |
437 |
437 |
438 \begin{definition} |
|
439 A set of whole mappings is called \textbf{problem type}. |
|
440 \end{definition} |
|
441 Throughout the paper, $\mathbf{PT}$ denotes a generic problem type |
438 Throughout the paper, $\mathbf{PT}$ denotes a generic problem type |
442 which can be substituted by any problem type. |
439 which can be substituted by any of $\mathbf{ISO}$, $\mathbf{SUB}$ |
443 |
|
444 A whole mapping $W\mathbf{\ is\ of\ type\ PT}$, if $W\in PT$. Using |
|
445 this notations, VF2 searches a whole mapping $W$ of type $PT$. |
|
446 |
|
447 For example the problem type of graph isomorphism problem is the |
|
448 following. A whole mapping $W$ is in $\mathbf{ISO}$, iff the |
|
449 bijection represented by $W$ satisfies Definition~\ref{sec:ismorphic}. |
|
450 The subgraph- and induced subgraph matching problems can be formalized |
|
451 in a similar way. Let their problem types be denoted as $\mathbf{SUB}$ |
|
452 and $\mathbf{IND}$. |
440 and $\mathbf{IND}$. |
453 |
|
454 \begin{definition} |
|
455 \label{expPT} |
|
456 $PT$ is an \textbf{expanding problem type} if $\ \forall\ W\in |
|
457 PT:\ \forall u_1,u_2\in V_{small}:\ (u_1,u_2)\in E_{small}\Rightarrow |
|
458 (Pair(W,u_1),Pair(W,u_2))\in E_{large}$, that is each edge of |
|
459 $G_{small}$ has to be mapped to an edge of $G_{large}$ for each |
|
460 mapping in $PT$. |
|
461 \end{definition} |
|
462 |
|
463 Note that $ISO$, $SUB$ and $IND$ are expanding problem types. |
|
464 |
|
465 This paper deals with the three problem types mentioned above only, |
|
466 but the following generic definitions make it possible to handle other |
|
467 types as well. Although it may be challenging to find a proper |
|
468 consistency function and an efficient cutting function. |
|
469 |
441 |
470 \begin{definition} |
442 \begin{definition} |
471 Let M be a mapping. A logical function $\mathbf{Cons_{PT}}$ is a |
443 Let M be a mapping. A logical function $\mathbf{Cons_{PT}}$ is a |
472 \textbf{consistency function by } $\mathbf{PT}$, if the following |
444 \textbf{consistency function by } $\mathbf{PT}$, if the following |
473 holds. If there exists whole mapping $W$ of type PT for which |
445 holds. If there exists whole mapping $W$ of type $PT$ for which |
474 $M\subseteq W$, then $Cons_{PT}(M)$ is true. |
446 $M\subseteq W$, then $Cons_{PT}(M)$ is true. |
475 \end{definition} |
447 \end{definition} |
476 |
448 |
477 \begin{definition} |
449 \begin{definition} |
478 Let M be a mapping. A logical function $\mathbf{Cut_{PT}}$ is a |
450 Let M be a mapping. A logical function $\mathbf{Cut_{PT}}$ is a |
479 \textbf{cutting function by } $\mathbf{PT}$, if the following |
451 \textbf{cutting function by } $\mathbf{PT}$, if the following |
480 holds. $\mathbf{Cut_{PT}(M)}$ is false if $M$ can be extended to a |
452 holds. $\mathbf{Cut_{PT}(M)}$ is false if $M$ can be extended to a |
481 whole mapping W of type PT. |
453 whole mapping $W$ of type $PT$. |
482 \end{definition} |
454 \end{definition} |
483 |
455 |
484 \begin{definition} |
456 \begin{definition} |
485 $M$ is said to be \textbf{consistent mapping by} $\mathbf{PT}$, if |
457 $M$ is said to be \textbf{consistent mapping by} $\mathbf{PT}$, if |
486 $Cons_{PT}(M)$ is true. |
458 $Cons_{PT}(M)$ is true. |
570 Note that the cornerstone of the improvements to VF2 is a proper |
542 Note that the cornerstone of the improvements to VF2 is a proper |
571 choice of a total ordering. |
543 choice of a total ordering. |
572 |
544 |
573 \subsection{The candidate set P(s)} |
545 \subsection{The candidate set P(s)} |
574 \label{candidateComputingVF2} |
546 \label{candidateComputingVF2} |
575 $P(s)$ is the set of the candidate pairs for inclusion in $M(s)$. |
547 Let $P(s)$ be the set of the candidate pairs for inclusion in $M(s)$. |
576 Suppose that $PT$ is an expanding problem type, see |
|
577 Definition~\ref{expPT}. |
|
578 |
548 |
579 \begin{notation} |
549 \begin{notation} |
580 Let $\mathbf{T_{small}(s)}:=\{u \in V_{small} : u$ is not covered by |
550 Let $\mathbf{T_{small}(s)}:=\{u \in V_{small} : u$ is not covered by |
581 $M(s)\wedge\exists \tilde{u}\in{V_{small}: (u,\tilde{u})\in E_{small}} |
551 $M(s)\wedge\exists \tilde{u}\in{V_{small}: (u,\tilde{u})\in E_{small}} |
582 \wedge \tilde{u}$ is covered by $M(s)\}$, and |
552 \wedge \tilde{u}$ is covered by $M(s)\}$, and |
972 |
942 |
973 \subsubsection{Calculating the candidates for a node} |
943 \subsubsection{Calculating the candidates for a node} |
974 Being aware of Claim~\ref{claim:claimCoverFromLeft}, the |
944 Being aware of Claim~\ref{claim:claimCoverFromLeft}, the |
975 task is not to maintain the candidate set, but to generate the |
945 task is not to maintain the candidate set, but to generate the |
976 candidate nodes in $G_{large}$ for a given node $u\in V_{small}$. In |
946 candidate nodes in $G_{large}$ for a given node $u\in V_{small}$. In |
977 case of an expanding problem type and $M$ mapping, if a node $v\in |
947 case of any of the three problem type and a mapping $M$, if a node $v\in |
978 V_{large}$ is a potential pair of $u\in V_{small}$, then $\forall |
948 V_{large}$ is a potential pair of $u\in V_{small}$, then $\forall |
979 u'\in V_{small} : (u,u')\in |
949 u'\in V_{small} : (u,u')\in |
980 E_{small}\ and\ u'\ is\ covered\ by\ M\ \Rightarrow (v,Pair(M,u'))\in |
950 E_{small}\ and\ u'\ is\ covered\ by\ M\ \Rightarrow (v,Pair(M,u'))\in |
981 E_{large}$. That is, each covered neighbour of $u$ has to be mapped to |
951 E_{large}$. That is, each covered neighbour of $u$ has to be mapped to |
982 a covered neighbour of $v$. |
952 a covered neighbour of $v$. |