1. VF2算法

1.1 基本定义和整体流程

1. 原文An Improved Algorithm for Matching Large Graphs。
2. VF算法能够解决有向/无向，有标签/无标签，图同构问题。原文中的符号和VF3算法不同，这里对某些符号采用了更为广泛地符号定义。
3. 给定两个图$G_1=(V_1,E_1)$, $G_2=(V_2,E_2)$和一个映射$M\subset V_1\times V_2$, 当且仅当$M$是一个双射且对应边也是双射时，$G_1$和$G_2$称为同构。
4. 作者采用了一种称为State Space Representation (SSR)的方法判断同构。假设当前状态为$s$，则$M(s)$表示$M$中与状态$s$相关的映射的集合。则$M_1(s)$表示$M(s)$中属于$V_1$中的点构成的集合，同理$M_2(s)$。$E_1(s)$表示$E_1$中连接$M_1(s)$中点的边，同理$E_2(s)$。
5. 通过$M_1(s)$和$E_1(s)$我们可以得到$G_1$的子图$G_1(s)$，同理$G_2(s)$。
6. 算法整体流程如下图所示
   
   其中$F(s,n,m)$是一个布尔函数，也称为feasibility function。该函数的返回值如果是true，则表明将边$(n,m)$加入到当前状态$s$（$s$状态表示当前的部分映射$M(s)$是满足同构的）后，新状态$s^{\ast }$的部分映射$M(s^{\ast })$仍然满足同构。因此最终的状态可能是$G_1$与$G_2$同构或者两个图的子图同构。返回值为false，则表明$(n,m)$不应该加入到当前状态，能够起到剪枝的作用。

1.2 $P(s)$的定义

1. 给定一个图$G$和图中的一个点$n$，我们定义$Pred(G,n)$为$G$中$n$的入度邻居节点构成的集合（$n$的前继集合），定义$Succ(G,n)$为$G$中$n$的出度邻居节点构成的集合（$n$的后继集合）。
2. 我们定义out-terminal集合$T_1^{out}(s)$为$G_1$中不属于$M_1(s)$但属于$M_1(s)$中节点的后继节点构成的集合。定义in-terminal集合$T_1^{in}(s)$为不属于$M_1(s)$但属于$M_1(s)$中节点的前继节点构成的集合。同理定义$T_2^{out}(s)$和$T_2^{in}(s)$。
3. $P(s)$采用如下的方式构造：
   （1）如果$T_1^{out}(s)$和$T_2^{out}(s)$都不为空，
   P ( s ) = T 1 o u t ( s ) × { m i n   T 2 o u t ( s ) } P(s)=T^{out}_1(s) \times \{min\ T^{out}_2(s)\} P(s)=T1out​(s)×{min T2out​(s)}
   $min{T}_2^{out}(s)$表示$T_2^{out}(s)$中具有最小label的节点（任意一个排序方法均可）。
   （2）如果$T_1^{out}(s)$和$T_2^{out}(s)$都为空，且$T_1^{in}(s)$和$T_2^{in}(s)$均不为空，
   P ( s ) = T 1 i n ( s ) × { m i n   T 2 i n ( s ) } P(s)=T^{in}_1(s) \times \{min\ T^{in}_2(s)\} P(s)=T1in​(s)×{min T2in​(s)}
   （3）如果四个terminal集合都是空的，
   P ( s ) = ( V 1 − M 1 ( s ) ) × { m i n   ( V 2 − M 2 ( s ) ) } P(s)=(V_1-M_1(s)) \times \{min\ (V_2-M_2(s))\} P(s)=(V1​−M1​(s))×{min (V2​−M2​(s))}
4. 当出现只有一个in-terminal集合或者只有一个out-terminal集合为空的时候，可以证明状态$s$不可能构造出最终的同构，因此状态$s$不需要再继续分析。同时$P(s)$的定义可以保证同一个状态不会被访问两次。

1.3 $F(s,n,m)$的定义

为了判断$F(s,n,m)$，算法需要检查所有与$n,m$相连的点。

1. 对于在$M_1(s)$和$M_2(s)$中的节点，算法检查$M_1(s)$中这些节点和$n$的出边入边是否与$M_2(s)$中这些节点和$m$的出边入边一一对应。
2. 对于不在$M_1(s)$和$M_2(s)$中的节点，算法计算$T_i^{in}(s)$，$T_i^{out}(s)$和$V_i-M_i(s)-T_i^{in}(s)-T_i^{out}(s)$中节点的个数。对于$n,m$来说，这三个集合的节点数必须相等才有同构的可能性。对于子图同构来说，小图对应的三个集合的节点数必须小于等于大图对应的三个集合的节点数。
3. 如果是带label的图，那么$F(s,n,m)$还要检查对应的点和边的label是否一致。

1.4 实现细节

1. 两个向量core_1和core_2（维度分别为$G_1$和$G_2$中的节点个数）保存当前的映射。具体来说，如果$n$在$M_1(s)$中则core_1[n]保存了$G_2$中与$n$对应的节点的索引。否则保存了NULL_NODE。
2. 四个向量in_1, out_1, in_2, out_2表示terminal集合。具体来说，如果$n$在$M_1(s)$或者$T_1^{in}(s)$中，则in_1[n]为非零值。存储的实际值为当前状态$s$在SSR树中的深度。

2. VF3算法

2.1 基本定义和简要说明

1. 原文Challenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3 https://mivia.unisa.it/datasets/graph-database/vf3-library/
2. VF3算法在VF2算法的基础上增加了分类的概念，将节点按照某些属性（出度入度，标签等属性）分类，然后确保两个不属于同一个类的节点，是无法加入到匹配集中。这样又进一步裁剪了搜索空间。VF3主要关注的是sub-graph同构，$G_1$表示一个小图，也称为一个pattern，$G_2$是一个大图，也称为目标图。
3. 定义${\lambda }_v:V\to L_v$为节点到标签的映射，${\lambda }_e:E\to L_e$为边到标签的映射。$N_{G_1}$表示$G_1$中节点的遍历顺序。
4. 定义$\psi :V_1\bigcup V_2\to C$，表示给每个节点赋予一个类别 c i ∈ C = { c 1 , c 2 , ⋯   , c q } c_i \in C=\{c_1,c_2,\cdots,c_q\} ci​∈C={c1​,c2​,⋯,cq​}，使得$(u,v)\in M\Rightarrow \psi (u)=\psi (v)$。
5. ${\tilde{P}}_1(s)$相当于$T_1^{in}(s)$，${\tilde{S}}_1(s)$相当于$T_1^{out}(s)$。定义 C i ( V ) = { u ∈ V : ψ ( u ) = c i , i = 1 , ⋯   , q } C_i(V)=\{u \in V : \psi(u)=c_i, i=1,\cdots,q\} Ci​(V)={u∈V:ψ(u)=ci​,i=1,⋯,q}。表示$V$中属于类别$c_i$的节点的集合。${\tilde{V}}_1(s)=V_1-M_1(s)-{\tilde{P}}_1(s)-{\tilde{S}}_1(s)$。
6. 根据类别，细化terminal集合。定义 P ~ 1 c i ( s ) = { u ∈ P ~ 1 ( s ) : ψ ( u ) = c i } \widetilde{P}^{c_i}_1(s) =\{u \in \widetilde{P}_1(s) : \psi(u)=c_i\} P 1ci​​(s)={u∈P 1​(s):ψ(u)=ci​}， S ~ 1 c i ( s ) = { u ∈ S ~ 1 ( s ) : ψ ( u ) = c i } \widetilde{S}^{c_i}_1(s) =\{u \in \widetilde{S}_1(s) : \psi(u)=c_i\} S 1ci​​(s)={u∈S 1​(s):ψ(u)=ci​}， V ~ 1 c i ( s ) = { u ∈ V ~ 1 ( s ) : ψ ( u ) = c i } \widetilde{V}^{c_i}_1(s)=\{u \in \widetilde{V}_1(s): \psi(u)=c_i\} V 1ci​​(s)={u∈V 1​(s):ψ(u)=ci​}。同理定义${\tilde{P}}_2^{c_i}(s)$，${\tilde{S}}_2^{c_i}(s)$，${\tilde{V}}_2^{c_i}(s)$。

2.2 算法整体流程

1. 算法整体流程如下图所示
   
   输入为pattern $G_1$和图$G_2$。首先计算$G_1$中每个节点能够在$G_2$中找到匹配的概率（后面介绍），然后根据这个概率生成$G_1$中节点的访问顺序。第5行对$G_1$和$G_2$中的节点分类，分类后对pattern图进行预处理（后面介绍），最后执行真正的匹配算法。
2. 匹配算法如下图所示
   
   首先判断状态$s_c$是否是目标状态（既是否是同构），如果是，则将结果保存到$Solutions$并返回True。否则判断是否是dead状态，如果是则返回False，否则继续执行。然后将上一次插入的匹配设置为空，并使用GETNEXTCANDIDATE函数寻找候选的匹配。然后循环执行直到没有可选的匹配位置。在循环中，首先判断将候选匹配加入到当前状态后是否满足约束，不满足则继续寻找候选匹配。如果满足，则状态转移到$s_n$，递归的判断$s_n$是否可行。

2.3 GenerateNodeSequence和ComputeProbabilities

1. 对于一个状态$s$，假设它的$M(s)$集中包含$k$对匹配，那么到达状态$s$的路径共有$k!$个。可以看到，如果不对访问顺序加以限制，那么不同的路径就会产生相同的状态。该问题的一个解决方法是通过定义节点的顺序($\prec$)并按照该顺序访问节点，以此生成一个状态空间树。此时又引入了另一个问题，排序算法对性能也有很大的影响。为了解决该问题，VF3对有更多约束的点赋予更高的优先级。例如，$G_1$中的某个点在$G_2$中找到匹配点的概率非常小，此时该点应赋予更高的优先级。再例如，某个点连接了更多了的已匹配的点，此时该点应赋予更高的优先级。主要的考虑是这些点能大概率不满足，因此能够尽早的进行剪枝操作。
2. 定义$P_f(u)$为点$u\in G_1$找到点$v\in G_2$的概率。概率定义的逻辑可以在原文中看到，由于我对这方面不熟，便不在此班门弄斧了，直接给出最终的公式。
   $P_f(u)=P_l({\lambda }_{v1}(u))\cdot \sum _{d^{\prime }\ge d^{in}(u)}{P}_d^{in}(d^{\prime })\cdot \sum _{d^{\prime }\ge d^{out}(u)}{P}_d^{out}(d^{\prime })$
   $P_l(l)$表示节点$v$的标签为$l$的概率，$P_d^{in}(d^{\prime })$表示入度为$d^{\prime }$的概率，$P_d^{out}(d^{\prime })$表示出度为$d^{\prime }$的概率。同时也考虑到了图的结构信息，称之为节点映射度（node mapping degree）$d_M$。对于一个给定的节点$u\in G_1$，$d_M$定义为$u$与$N_{G_1}$中所有节点的入度和出度之和。
3. GenerateNodeSequence首先根据$d_M$排序，如果相等，则$P_f$，如果相等，则根据节点的出度入度之和，如果相等，则随机。

2.4 PreprocessPatternGraph

1. 我们仔细想一下$G_1$的遍历顺序$N_{G_1}$，每次从$N_{G_1}$中取出一个节点加入到$M(s)$中时，状态树都会向下前进一层。对于每一层来说，$G_1$对应的terminal集是不变的，而且我们已经知道了$G_1$的遍历顺序$N_{G_1}$，因此可以提前计算出状态树每层$G_1$对应的terminal集内容。PreprocessPatternGraph迭代的分析$N_{G_1}$中的每个节点$u$，如果其邻居节点$u^{\prime }$是$u$的后继（前继）节点，且没有插入到${\tilde{S}}_1^{\psi (u^{\prime })}$（${\tilde{P}}_1^{\psi (u^{\prime })}$）中，则将其插入。如果$u^{\prime }$不在这两个集合中，则将$u$设置为$Parent(u^{\prime })$。具体算法如下图所示。
   

2.5 GetNextCandidate

1. 为了转移到新状态$s_n$，GetNextCandidate寻找一个匹配对$(u_n,v_n)$，并将其加入到当前状态$s_c$，令生成状态$s_c$是加入的匹配对为$(u_c,v_c)$。
2. 对于pattern图$G_1$，$u_n$的选取的是$u_c$在$N_{G_1}$中的下一个节点。对于目标图$G_2$，算法将$G_2$中所有未匹配的并且和$u_n$类别相同的节点作为$v_n$的候选节点。候选节点集表示为
   R 2 ( s c , ψ ( u n ) ) = { v n ∈ V 2 : v n ∉ M 2 ( s c ) ⋀ ψ ( v n ) = ψ ( u n ) } R_2(s_c,\psi(u_n))=\{v_n \in V_2:v_n\notin M_2(s_c)\bigwedge \psi(v_n)=\psi(u_n)\} R2​(sc​,ψ(un​))={vn​∈V2​:vn​∈/​M2​(sc​)⋀ψ(vn​)=ψ(un​)}
3. 在不同的情况时，我们还可以进一步删减$R_2$。
   （1）如果$u_n$是$N_{G_1}$的第一个节点，其没有父节点，那么$v_n$的候选集就是$R_2$；
   （2）如果$u_n$有父节点，且是父节点的前继节点，则
   R 2 P ( s c , ψ ( u n ) , v ~ ) = { v n ∈ V 2 : v n ∈ P 2 ( v ~ ) ⋂ R 2 ( s c , ψ ( u n ) } R_2^P(s_c,\psi(u_n),\widetilde{v})=\{v_n \in V_2:v_n\in P_2(\widetilde{v})\bigcap R_2(s_c,\psi(u_n)\} R2P​(sc​,ψ(un​),v )={vn​∈V2​:vn​∈P2​(v )⋂R2​(sc​,ψ(un​)}
   （3）如果$u_n$有父节点，且是父节点的后继节点，则
   R 2 S ( s c , ψ ( u n ) , v ~ ) = { v n ∈ V 2 : v n ∈ S 2 ( v ~ ) ⋂ R 2 ( s c , ψ ( u n ) } R_2^S(s_c,\psi(u_n),\widetilde{v})=\{v_n \in V_2:v_n\in S_2(\widetilde{v})\bigcap R_2(s_c,\psi(u_n)\} R2S​(sc​,ψ(un​),v )={vn​∈V2​:vn​∈S2​(v )⋂R2​(sc​,ψ(un​)}
   其中$\tilde{v}$表示$G_2$中与$u_n$的父节点匹配的节点。具体算法如下图所示
   

2.6 IsFeasible

1. 判断能够将匹配对$(u_n,v_n)$将入到当前状态$s_c$中，
   $IsFeasible(s_c,u_n,v_n)=F_s(s_c,u_n,v_n)\wedge F_t(s_c,u_n,v_n)$
   $F_s$判断标签是否一致，$F_t$判断拓扑结构是否一致。
2. $F_t(s_c,u_n,v_n)=F_c(s_c,u_n,v_n)\wedge F_{la1}(s_c,u_n,v_n)\wedge F_{la2}(s_c,u_n,v_n)$，$F_c$检查是否满足一致性，后面会介绍。$F_{la1}$和$F_{la2}$是为了进一步删减搜索空间，代表1-lookahead和2-lookahead。只使用$F_c$便能保证结果的正确性，其余两个是为了加速的。
3. $F_c(s_c,u_n,v_n)\iff$
        $\forall u^{\prime }\in S_1(u_n)\cap M_1(s_c)\exists v^{\prime }=\tilde{\mu }(s_c,u^{\prime })\in S_2(v_n)$
        $\wedge \forall u^{\prime }\in P_1(u_n)\cap M_1(s_c)\exists v^{\prime }=\tilde{\mu }(s_c,u^{\prime })\in P_2(v_n)$
        $\wedge \forall v^{\prime }\in S_2(v_n)\cap M_2(s_c)\exists u^{\prime }={\tilde{\mu }}^{-1}(s_c,v^{\prime })\in S_1(u_n)$
        $\wedge \forall v^{\prime }\in P_2(v_n)\cap M_2(s_c)\exists u^{\prime }={\tilde{\mu }}^{-1}(s_c,v^{\prime })\in P_1(u_n)$
   其中，$S_1(u_n)$表示$u_n$在$G_1$中的后继节点，$P_1(u_n)$表示$u_n$在$G_1$中的前继节点，同理其它集合。$\tilde{\mu }(s_c,u^{\prime })$表示在$M(s_c)$中与$u^{\prime }$对应的点，${\tilde{\mu }}^{-1}(s_c,v^{\prime })$表示在$M(s_c)$中与$v^{\prime }$对应的点。
4. $F_{la1}$检查$u_n$的邻居分散在各个terminal集中每个类别中的个数是否小于等于$v_n$的同样的个数。$F_{la2}$进行同样的操作，不过是在${\tilde{V}}_1(s_c)$和${\tilde{V}}_2(s_c)$上。

写在前面的话

谨以此系列献给 my grandpa~

体验过人间的无常，才知道爱才是宝藏

像孩子依赖着肩膀
像诗人依赖月亮
像眼泪依赖脸庞

你就是我的天使
给我依赖的天使

1.Let us play VF2 algorithm

1.1一些声明

1.2你必需知道的事情

虽然子图的同构问题没有图的同构问题要求这么严，图的同构必须要求结点的度必须相同，否则不同构。

如果在一个图中某个节点的度大于要匹配的图形的或者是它的子图，这样是不可能找到子图和它同构的，因为它本身根本构建不出这么大的度。

子图同构是图的同构中的一种，至少有些该满足的还是要满足。

1.3 算法处理

如果点已经全部用完，那么匹配的部分就是我们的子图同构的部分。

写在后面的话

喜欢的朋友们，支持一下，哈哈哈

写在最后的话

无意中发现了一个巨牛的人工智能教程，忍不住分享一下给大家。教程不仅是零基础，通俗易懂，而且非常风趣幽默，像看小说一样！觉得太牛了，所以分享给大家。点这里可以跳转到教程 https://www.captainbed.net/chichoxian

子图同构算法-VF2（java实现）

  最近在项目中用到了子图同构算法VF2，自己查找的时候发现csdn上没有太详细的博客，所以在这里记录一下。内容主要来自一篇论文（A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs）

一、什么是VF2算法

  VF2算法是一种子图同构算法，而子图同构我们可以这样定义：
  假设有两个图 H=(VH,EH) H=(VH,EH) 和图 G=(V,E) G=(V,E) 子图同构即从H到G存在这样一个函数 f:VH→V 并且 (u,v)∈EH(u,v)∈EH同样成立 f 叫做子图同构的一个映射。

  在VF2算法中，可以将查询图表示为 queryGraph,把数据图表示为 targetGraph,引入一个中间状态 state，用于记录我们当前子图同构进行到的状态。 在每一个中间状态中，VF2算法计算要添加到当前状态state的候选节点对 P(S)（分别由查询图和数据图中的一个节点组成），是否满足 可行性规则，如果该节点对可以满足 可行性规则那么就将其添加到当前状态state中并更新当前状态，整个过程递归的进行。
  其中 可行性规则一共包含五条，这五条规则确保了子图同构过程的正确性。为了方便代码实现，本文将这五条规则归结为三条，每条通过一个java方法实现。分别是：

1. 前驱和后继规则：对于查询节点的每一个前驱节点和后继节点，目标节点一定存在与之对应的。

2. 1-look-ahead规则：在查询图中与查询节点邻接，以查询节点为起点/终点并且属于以已经匹配顶点为起点/终点的部分的数量一定小于等于在数据图中对应部分的数量。

3. 2-look-ahead 规则：在查询图中查询节点与既不是已匹配顶点也不和以匹配顶点相邻的点也应该与数据图中的对应部分满足第二条规则。

  根据这几条规则递归的进行匹配最终可以判断在数据图中是否包含查询图。

二、VF2算法的代码实现（java）

  本文递归的判断目标图是否包含查询图：

private boolean matchRecursive(State state, Graph targetGraph, Graph queryGraph){
		
		if (state.depth == queryGraph.nodes.size()){	// Found a match
			state.matched = true;
			return true;
		} else {	// Extend the state
			ArrayList<Pair<Integer,Integer>> candidatePairs = genCandidatePairs(state, targetGraph, queryGraph);
			for (Pair<Integer, Integer> entry : candidatePairs){
				if (checkFeasibility(state, entry.getKey(), entry.getValue())){
					state.extendMatch(entry.getKey(), entry.getValue()); // extend mapping
					if (matchRecursive(state, targetGraph, queryGraph)){	// Found a match
						return true;
					}
					state.backtrack(entry.getKey(), entry.getValue()); // remove the match added before
				}
			}
		}
		return false;
	}

  其中 genCandidatePairs方法用于生成当前状态的所有候选对，checkFeasibility方法用于检查添加词匹配项的可行性。

  以下是我们编写的方法用于判断 可行性规则是否满足：
验证 规则一的方法：

	private Boolean checkPredAndSucc(State state, int targetNodeIndex , int queryNodeIndex) {
		
		Node targetNode = state.targetGraph.nodes.get(targetNodeIndex);
		Node queryNode = state.queryGraph.nodes.get(queryNodeIndex);
		int[][] targetAdjacency = state.targetGraph.getAdjacencyMatrix();
		int[][] queryAdjacency = state.queryGraph.getAdjacencyMatrix();
		for (Edge e : queryNode.inEdges) {
			if (state.core_2[e.source.id] > -1) {
				if (targetAdjacency[state.core_2[e.source.id]][targetNodeIndex] == -1){
					return false;	// not such edge in target graph
				} else if (targetAdjacency[state.core_2[e.source.id]][targetNodeIndex] != e.label){
					return false;	// label doesn't match
				}
			}
		}
		for (Edge e : queryNode.outEdges) {
			if (state.core_2[e.target.id] > -1) {
				if (targetAdjacency[targetNodeIndex][state.core_2[e.target.id]] == -1){
					return false;	// not such edge in target graph
				} else if (targetAdjacency[targetNodeIndex][state.core_2[e.target.id]] != e.label) {
					return false;	// label doesn't match
				}
			}
		}
		return true;
	}

验证 规则二的方法：

	private boolean checkInAndOut(State state, int targetNodeIndex , int queryNodeIndex) {
		
		Node targetNode = state.targetGraph.nodes.get(targetNodeIndex);
		Node queryNode = state.queryGraph.nodes.get(queryNodeIndex);
		
		int targetPredCnt = 0, targetSucCnt = 0;
		int queryPredCnt = 0, querySucCnt = 0;

		//入度规则
		//目标节点在T1in中的前驱/后继节点数必须大于或者等于查询节点在T2in中的前驱/后继节点数
		for (Edge e : targetNode.inEdges){
			if (state.inT1in(e.source.id)){
				targetPredCnt++;
			}
		}
		for (Edge e : targetNode.outEdges){
			if (state.inT1in(e.target.id)){
				targetSucCnt++;
			}
		}
		for (Edge e : queryNode.inEdges){
			if (state.inT2in(e.source.id)){
				queryPredCnt++;
			}
		}
		for (Edge e : queryNode.outEdges){
			if (state.inT2in(e.target.id)){
				querySucCnt++;
			}
		}
		if (targetPredCnt < queryPredCnt || targetSucCnt < querySucCnt){
			return false;
		}
		
		// T1out中的目标节点的前驱/后继数必须大于或者等于处于T2out中的查询节点的前驱/后继数
		for (Edge e : targetNode.inEdges){
			if (state.inT1out(e.source.id)){
				targetPredCnt++;
			}
		}
		for (Edge e : targetNode.outEdges){
			if (state.inT1out(e.target.id)){
				targetSucCnt++;
			}
		}
		for (Edge e : queryNode.inEdges){
			if (state.inT2out(e.source.id)){
				queryPredCnt++;
			}
		}
		for (Edge e : queryNode.outEdges){
			if (state.inT2out(e.target.id)){
				querySucCnt++;
			}
		}
		if (targetPredCnt < queryPredCnt || targetSucCnt < querySucCnt){
			return false;
		}		
		
		return true;
	}

验证 规则三的方法：

	private boolean checkNew(State state, int targetNodeIndex , int queryNodeIndex){
		
		Node targetNode = state.targetGraph.nodes.get(targetNodeIndex);
		Node queryNode = state.queryGraph.nodes.get(queryNodeIndex);
		
		int targetPredCnt = 0, targetSucCnt = 0;
		int queryPredCnt = 0, querySucCnt = 0;
		for (Edge e : targetNode.inEdges){
			if (state.inN1Tilde(e.source.id)){
				targetPredCnt++;
			}
		}
		for (Edge e : targetNode.outEdges){
			if (state.inN1Tilde(e.target.id)){
				targetSucCnt++;
			}
		}
		for (Edge e : queryNode.inEdges){
			if (state.inN2Tilde(e.source.id)){
				queryPredCnt++;
			}
		}
		for (Edge e : queryNode.outEdges){
			if (state.inN2Tilde(e.target.id)){
				querySucCnt++;
			}
		}
		if (targetPredCnt < queryPredCnt || targetSucCnt < querySucCnt){
			return false;
		}
		
		return true;
	}
}
		

  下面定义了state状态类,以上的验证可行性方法以及VF2算法的整个流程基于该类编写：

package wip.VF2.core;

import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Scanner;

import wip.VF2.graph.Edge;
import wip.VF2.graph.Graph;
import wip.VF2.graph.Node;

public class State {
	
	public int[] core_1; // stores for each target graph node to which query graph node it maps ("-1" indicates no mapping)
	public int[] core_2; // stores for each query graph node to which target graph node it maps ("-1" indicates no mapping)
	
	public int[] in_1; 	// stores for each target graph node the depth in the search tree at which it entered "T_1 in" or the mapping ("-1" indicates that the node is not part of the set)
	public int[] in_2; 	// stores for each query graph node the depth in the search tree at which it entered "T_2 in" or the mapping ("-1" indicates that the node is not part of the set)
	public int[] out_1; // stores for each target graph node the depth in the search tree at which it entered "T_1 out" or the mapping ("-1" indicates that the node is not part of the set)
	public int[] out_2; // stores for each query graph node the depth in the search tree at which it entered "T_2 out" or the mapping ("-1" indicates that the node is not part of the set)
	 
	public HashSet<Integer> T1in;	// nodes that not yet in the partial mapping, that are the destination of branches start from target graph
	public HashSet<Integer> T1out;	// nodes that not yet in the partial mapping, that are the origin of branches end into target graph
	public HashSet<Integer> T2in;	// nodes that not yet in the partial mapping, that are the destination of branches start from query graph
	public HashSet<Integer> T2out;	// nodes that not yet in the partial mapping, that are the origin of branches end into query graph
	
	public HashSet<Integer> unmapped1;	// unmapped nodes in target graph
	public HashSet<Integer> unmapped2;	// unmapped nodes in query graph
	
	public int depth = 0; // current depth of the search tree
	
	public boolean matched = false;
	
	public Graph targetGraph;
	public Graph queryGraph;
	
	/**
	 * Initialize a State
	 * @param targetGraph	The big graph
	 * @param queryGraph	The small graph
	 */
	public State(Graph targetGraph, Graph queryGraph) {
		
		this.targetGraph = targetGraph;
		this.queryGraph = queryGraph;
		
		int targetSize = targetGraph.nodes.size();
		int querySize = queryGraph.nodes.size();
		
		T1in = new HashSet<Integer>(targetSize * 2);
		T1out = new HashSet<Integer>(targetSize * 2);
		T2in = new HashSet<Integer>(querySize * 2);
		T2out = new HashSet<Integer>(querySize * 2);
		
		unmapped1 = new HashSet<Integer>(targetSize * 2);
		unmapped2 = new HashSet<Integer>(querySize * 2);
		
		core_1 = new int[targetSize];
		core_2 = new int[querySize];
		
		in_1 = new int[targetSize];
		in_2 = new int[querySize];
		out_1 = new int[targetSize];
		out_2 = new int[querySize];
		
		// initialize values ("-1" means no mapping / not contained in the set)
		// initially, all sets are empty and no nodes are mapped
		for (int i = 0 ; i < targetSize ; i++) {
			core_1[i] = -1;
			in_1[i] = -1;
			out_1[i] = -1;
			unmapped1.add(i);
		}
		for (int i = 0 ; i < querySize ; i++) {
			core_2[i] = -1;
			in_2[i] = -1;
			out_2[i] = -1;
			unmapped2.add(i);
		}
	}
		
	public Boolean inM1(int nodeId) {
		return (core_1[nodeId] > -1);
	}
	
	public Boolean inM2(int nodeId) {
		return (core_2[nodeId] > -1);
	}
	
	public Boolean inT1in(int nodeId) {
		return ((core_1[nodeId] == -1) && (in_1[nodeId] > -1));
	}
	
	public Boolean inT2in(int nodeId) {
		return ((core_2[nodeId] == -1) && (in_2[nodeId] > -1));
	}
	
	public Boolean inT1out(int nodeId) {
		return ((core_1[nodeId] == -1) && (out_1[nodeId] > -1));
	}
	
	public Boolean inT2out(int nodeId) {
		return ((core_2[nodeId] == -1) && (out_2[nodeId] > -1));
	}
	
	public Boolean inT1(int nodeId) {
		return (this.inT1in(nodeId) || this.inT1out(nodeId));
	}
	
	public Boolean inT2(int nodeId) {
		return (this.inT2in(nodeId) || this.inT2out(nodeId));
	}
	
	public Boolean inN1Tilde(int nodeId) {
		return ((core_1[nodeId] == -1) && (in_1[nodeId] == -1) && (out_1[nodeId] == -1));
	}
	
	public Boolean inN2Tilde(int nodeId) {
		return ((core_2[nodeId] == -1) && (in_2[nodeId] == -1) && (out_2[nodeId] == -1));
	}
	
	/**
	 * Add a new match (targetIndex, queryIndex) to the state
	 * @param targetIndex	Index of the node in target graph
	 * @param queryIndex	Index of the node in query graph
	 */
	public void extendMatch(int targetIndex, int queryIndex) {
		
		core_1[targetIndex] = queryIndex;
		core_2[queryIndex] = targetIndex;
		unmapped1.remove(targetIndex);
		unmapped2.remove(queryIndex);
		T1in.remove(targetIndex);
		T1out.remove(targetIndex);
		T2in.remove(queryIndex);
		T2out.remove(queryIndex);
		
		depth++;	// move down one level in the search tree
		
		Node targetNode = targetGraph.nodes.get(targetIndex);
		Node queryNode = queryGraph.nodes.get(queryIndex);

		for (Edge e : targetNode.inEdges) {
			if (in_1[e.source.id] == -1){	// if the note is not in T1in or mapping 
				in_1[e.source.id] = depth;
				if (!inM1(e.source.id))		// if not in M1, add into T1in
					T1in.add(e.source.id);
			}
		}

		for (Edge e : targetNode.outEdges) {
			if (out_1[e.target.id] == -1){	// if the note is not in T1out or mapping 
				out_1[e.target.id] = depth; 
				if (!inM1(e.target.id))		// if not in M1, add into T1out
					T1out.add(e.target.id); 
			}
		}

		for (Edge e : queryNode.inEdges) {
			if (in_2[e.source.id] == -1){	// if the note is not in T2in or mapping
				in_2[e.source.id] = depth; 
				if (!inM2(e.source.id))		// if not in M1, add into T2in
					T2in.add(e.source.id); 
			}
		}

		for (Edge e : queryNode.outEdges) {
			if (out_2[e.target.id] == -1){	// if the note is not in T2out or mapping
				out_2[e.target.id] = depth; 
				if (!inM2(e.target.id))		// if not in M1, add into T2out
					T2out.add(e.target.id); 
			}
		}
			
	}
	
	/**
	 * Remove the match of (targetNodeIndex, queryNodeIndex) for backtrack
	 * @param targetNodeIndex
	 * @param queryNodeIndex
	 */
	public void backtrack(int targetNodeIndex, int queryNodeIndex) {
		
		core_1[targetNodeIndex] = -1;
		core_2[queryNodeIndex] = -1;
		unmapped1.add(targetNodeIndex);
		unmapped2.add(queryNodeIndex);
		
		for (int i = 0 ; i < core_1.length ; i++) {
			if (in_1[i] == depth) {
				in_1[i] = -1;
				T1in.remove(i);
			}
			if (out_1[i] == depth) {
				out_1[i] = -1;
				T1out.remove(i);
			}
		}
		for (int i = 0 ; i < core_2.length ; i++) {
			if (in_2[i] == depth) {
				in_2[i] = -1;
				T2in.remove(i);
			}
			if (out_2[i] == depth) {
				out_2[i] = -1;
				T2out.remove(i);
			}
		}
		
		// put targetNodeIndex and queryNodeIndex back into Tin and Tout sets if necessary
		if (inT1in(targetNodeIndex))
			T1in.add(targetNodeIndex);
		if (inT1out(targetNodeIndex))
			T1out.add(targetNodeIndex);
		if (inT2in(queryNodeIndex))
			T2in.add(queryNodeIndex);
		if (inT2out(queryNodeIndex))
			T2out.add(queryNodeIndex);
		
		depth--;
	}
	
	/**
	 * Print the current mapping
	 */
	public void printMapping() {
		for (int i = 0 ; i < core_2.length ; i++) {
			System.out.print("(" + core_2[i] + "-" + i + ") ");
		}
		System.out.println();
	}
	
	/**
	 * Write state to file
	 */
	public void writeMapping(PrintWriter writer){
		for (int i = 0 ; i < core_2.length ; i++) {
			writer.write("(" + core_2[i] + "-" + i + ") ");
		}
		writer.write("\n");
	}
}

三、VF2算法的改进思路

1. 查询图的边的匹配顺序可以改进为按照边在数据图上出现的次数从小到大的匹配。（提高边的过滤能力）
2. 顶点的匹配顺序可以改进为顶点出现次数少，度数大的优先匹配。（提高顶点的过滤能力）