(サブ)図同性アルゴリズムVF 2実装(1)


サブマップ同性問題は本質的にマッチングであり、VF 2アルゴリズムにはfeasibility rulesが多く追加され、アルゴリズムの効率性が保証されている.ここでは、最も基本的な判断サブマップ同構造を実現するアルゴリズムにすぎない.
参考文献には(実はgoogleは1本でこれらが出てくる):
http://stackoverflow.com/questions/8176298/vf2-algorithm-steps-with-example
http://www.zhihu.com/question/27071897
https://github.com/fozziethebeat/S-Space/tree/master/src/main/java/edu/ucla/sspace/graph/isomorphism
http://stackoverflow.com/questions/6743894/any-working-example-of-vf2-algorithm/6744603
Luigi P. Cordella,Pasquale Foggia,Carlo Sansone,Mario Vento: A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.IEEE Trans. Pattern Anal. Mach. Intell. 26(10): 1367-1372 (2004)
最初のリンクは、次の例を示します.
http://stackoverflow.com/questions/8176298/vf2-algorithm-steps-with-example:
I will try to give you a quick explaination of my previous answer to this question :
Any working example of VF2 algorithm?
I will use the same example as the one in my previous answer :
(子)图同构算法VF2实现(1)_第1张图片
The 2 graphs above are V and V' .(V' is not in the drawing but it's the one on the right)
The VF2 algorithm is described in the graph.
Step by step
I want to know if V and V' are isomorphic.
I will use the following notations : XV is the node X in V
In the VF2 algoritm I will try to match each node in V with a node in V'.
step 1 :
I match empty V with empty V' : it always works
step 2 : I can match 1V with 1V',2V' or 3V'
I match 1V witch 1V' : it always works
step 3 :
I can match 2V with 2V' or 3V'
I match 2V with 2V' : it works because {1V 2V} and {1V' 2V} are isomorphic
step 4 :
I try to match 3V with a node in V' : I cannot! {it would be possible if their was an edge between node 3 and 2 in V', and no edge between 3 and 1)
So I go back to step 2
step 5:
I match 2V with 3V'
step 6:
same as step 4
I go back to step 2. there is no solution in step 2 , I go back to step 1
step 7:
I match 1V with 2V'
step 8:
I match 2V with 1V'
step 9 :
I match 3V with 3V'
it works I matched {1V 2V 3V} with { 2V' 1V' 3V'}
The graphs are isomorphic.
If I test all the solution and it never works the graph would not be isomorphic.
Hope this helps
About you're question on "matching", have a look at the wikipedia article on graph isomorphis :
http://en.wikipedia.org/wiki/Graph_isomorphism
this is a good example of a function f that matches graph G and H :  (子)图同构算法VF2实现(1)_第2张图片
Hope you can better understand this algorithm with this illustration.
次に、私のアルゴリズム設計を示します(ここでは、エッジとポイントはIDのほかにlabelもあります):
エッジとグラフの構造:
struct EDGE
{
	int id2;
	int label;
	EDGE(int _id2, int _label)
	{
		id2=_id2;
		label=_label;
	}
};


//      ,    vector   
struct GRAPH
{
	int graphID;
	vector<int> vID;
	vector<int> vLabel;


	vector<vector<EDGE> > vAdjacencyEdge;
	//    vector< >,             ,          ,vAdjacencyEdge size    
	//vector<EDGE>  EDGE[id2,label]  ,             id           label,
	//vector<EDGE>              (       ,   “   ”)
	//    pair(m,n)       M(s)        ,             
};

各match構造:
//match  ,        core_1 and core_2,
//whose dimensions correspond to the number of nodes in G1 and G2
struct MATCH
{
	//int *dbMATCHqu; //  DB    id   match QU    id
	//int *quMATCHdb; //  QU    id   match DB    id
	//  map     ,      !
	map<int, int> dbMATCHqu;
	map<int, int> quMATCHdb;
};

ファイルからデータを読み込む(主に各ポイントの隣接するエッジ/ポイントがstruct GRAPHに従って正しく格納されることを保証する):
vector<GRAPH *> ReadGraph(const char *filename)
{
	FILE *fp = fopen(filename, "r");
	/*
	if (!fp)
	{
		printf("fp is NULL, file [%s] doesn't exist...
", filename); return; } */ EDGE e(-1,-1); vector<EDGE> v; v.push_back(e); char mark[2]; int id,label,id2; vector<GRAPH *> gSet; GRAPH * g = NULL; while(true) { fscanf(fp, "%s", mark); if(mark[0]=='t') { fscanf(fp, "%s%d", mark, &id); if(id==-1) { gSet.push_back(g); break; } else //if input not ending, then { if(g!=NULL) { gSet.push_back(g); } g = new GRAPH; g->graphID=id; } } else if(mark[0]=='v') { fscanf(fp, "%d%d", &id, &label); g->vID.push_back(id); g->vLabel.push_back(label); g->vAdjacencyEdge.push_back(v);// vAdjacencyEdge, v , ! } else if(mark[0]=='e') { fscanf(fp, "%d%d%d", &id, &id2, &label); e.id2=id2; e.label=label; g->vAdjacencyEdge[id].push_back(e);//id->id2 e.id2=id; e.label=label; g->vAdjacencyEdge[id2].push_back(e);//id2->id } } fclose(fp); printf("graph number:%d
", gSet.size()); return gSet; }

候補pairがfeasibility rulesを満たすかどうかを判断します.
//   pair(quG->vID[i], dbG->vID[j])      pair candidate
//     pair    feasibility rules
bool FeasibilityRules(GRAPH *quG, GRAPH *dbG, MATCH match, int quG_vID, int dbG_vID)
{
	int quVid,dbVid,quGadjacencyEdgeSize,dbGadjacencyEdgeSize,i,j;
	bool flag=false;

	//  ,  quG_vID dbG_vID   label    
	if(quG->vLabel[quG_vID]!=dbG->vLabel[dbG_vID]) //      label  , 【   】  feasibility rules
	{
		return false;
	}
	
	//  ,       match      pair
	if(match.quMATCHdb.size()==0) //        pair
	{
		//        label  (       )   feasibility rules
		return true;
	}

	//  (label  ,     pair【 ,    match      】),                  feasibility rules:
	//1)quG_vID dbG_vID   match        【  】  (quVid,dbVid)    (quG_vID dbG_vID     match   quVid dbVid “neighbor  ”)
	//2)         (quVid,dbVid),     【   】    ( edge(quG_vID,quVid), edge(dbG_vID,dbVid) ) label  
	for(map<int, int>::iterator iter=match.quMATCHdb.begin();iter!=match.quMATCHdb.end();iter++) //       match    
	{
		quVid=iter->first;
		quGadjacencyEdgeSize=quG->vAdjacencyEdge[quVid].size();
		for(i=1;i<quGadjacencyEdgeSize;i++) // 1      quVid    , 0    (-1,-1)
		{
			//quG_vID   match quG    quVid “ i neighbor  ”
			if( quG->vAdjacencyEdge[quVid][i].id2==quG_vID ) 
			{
				dbVid=iter->second;
				dbGadjacencyEdgeSize=dbG->vAdjacencyEdge[dbVid].size();
				for(j=1;j<dbGadjacencyEdgeSize;j++) // 1      dbVid    , 0    (-1,-1)
				{
					//  , quVid match   dbVid dbG  “ j neighbor  ”   dbG_vID
					if( dbG->vAdjacencyEdge[dbVid][j].id2==dbG_vID )
					{
						//  2)    
						if( quG->vAdjacencyEdge[quVid][i].label != dbG->vAdjacencyEdge[dbVid][j].label )
						{
							//  2)  【   】label  ,        ,   false
							return false;
						}
						else
						{
							//  :flag=true         1) pair(dbVid,quVid),     2)
							//          ,      match     ,     pair(dbVid,quVid)      1) 2)
							flag=true;
						}
					}
				}
			}
		}
	}
	return flag;
}

最後に、アルゴリズムの疑似コードを示します.
(子)图同构算法VF2实现(1)_第3张图片