All non isomorphic subgraphs of a directed complete graph of order 3 (number of different hook graphs)

Hello everyone , I meet you again , I'm your friend, Quan Jun .

Subgraph isomorphism is essentially a kind of matching ,VF2 The algorithm adds a lot feasibility rules, Ensure the efficiency of the algorithm . Here is only the most basic algorithm to judge the isomorphism of subgraphs ：

References are （ Actually google You can get these out with one hand ）：

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)

The first link gives an example ：

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 :

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 :

Hope you can better understand this algorithm with this illustration.

Here is my algorithm design （ Here consider edges and points except ID outside , also label）：

Edge and graph structure ：

struct EDGE
{
	int id2;
	int label;
	EDGE(int _id2, int _label)
	{
		id2=_id2;
		label=_label;
	}
};


// Adjacency list structure , It's just using vector To achieve 
struct GRAPH
{
	int graphID;
	vector<int> vID;
	vector<int> vLabel;


	vector<vector<EDGE> > vAdjacencyEdge;
	// Big outside vector< >, Save an adjacency table for each node , How many nodes are there in a graph ,vAdjacencyEdge Of size How much? 
	//vector<EDGE> Deposit EDGE[id2,label] Component , Represents the sibling node corresponding to each node id And the edge between these two nodes label,
	//vector<EDGE> The size is determined by the number of brothers in each node （ The so-called brothers here , Is refers to “ Adjacency point ”）
	// Because it is feasible pair(m,n) From the current state M(s) In the adjacency point of , So this structure can speed up the search 
};

Copy

every last match structure ：

//match structure , Corresponding to core_1 and core_2,
//whose dimensions correspond to the number of nodes in G1 and G2
struct MATCH
{
	//int *dbMATCHqu; // Storage DB The nodes in the id And with it match Of QU The nodes in the id
	//int *quMATCHdb; // Storage QU The nodes in the id And with it match Of DB The nodes in the id
	// Use map Programming is more convenient , Search faster !
	map<int, int> dbMATCHqu;
	map<int, int> quMATCHdb;
};

Copy

Reading data from a file （ It is mainly to ensure the adjacent edges of each point / Points can follow struct GRAPH Correct storage ）：

vector<GRAPH *> ReadGraph(const char *filename)
{
	FILE *fp = fopen(filename, "r");
	/*
	if (!fp)
	{
		printf("fp is NULL, file [%s] doesn't exist...\n", 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);// Apply for one for each node vAdjacencyEdge, among v Just occupy the position , It's no use ！
		}
		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 The edge of 
			e.id2=id; e.label=label;
			g->vAdjacencyEdge[id2].push_back(e);//id2->id The edge of 
		}
	}

	fclose(fp);
	printf("graph number:%d\n", gSet.size());
	return gSet;

}

Copy

Judge a candidate pair Is it satisfactory? feasibility rules：

// Actually  pair(quG->vID[i], dbG->vID[j]) Is a candidate pair candidate
// Judge the candidate pair Is it satisfactory? 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;

	// First , Judge quG_vID and dbG_vID Corresponding label Are they the same? 
	if(quG->vLabel[quG_vID]!=dbG->vLabel[dbG_vID]) // If two points label Different , be 【 Definitely not 】 Satisfy feasibility rules
	{
		return false;
	}
	
	// secondly , Judge whether every time match The first comparison of pair
	if(match.quMATCHdb.size()==0) // If it is the first comparison pair
	{
		// Only these two points are needed label identical （ The judgment has been established ） The meet feasibility rules
		return true;
	}

	// Last （label identical , Not the first one pair【 namely , It's been match Some nodes 】）, Then as long as the following conditions are true, the simplest feasibility rules：
	//1）quG_vID and dbG_vID And have match Of those node pairs 【 At least 】 a pair (quVid,dbVid) Adjacent to each other （quG_vID and dbG_vID They are already match The node of quVid and dbVid Of “neighbor node ”）
	//2） If there are multiple adjacent pairs (quVid,dbVid), Must be required 【 be-all 】 Adjacent edge pairs ( edge(quG_vID,quVid), edge(dbG_vID,dbVid) ) Of label equally 
	for(map<int, int>::iterator iter=match.quMATCHdb.begin();iter!=match.quMATCHdb.end();iter++) // Traverse all that have match Node pairs for 
	{
		quVid=iter->first;
		quGadjacencyEdgeSize=quG->vAdjacencyEdge[quVid].size();
		for(i=1;i<quGadjacencyEdgeSize;i++) // from 1 Start scanning in sequence quVid The adjacency point , The first 0 What you save is (-1,-1)
		{
			//quG_vID Is already match Of quG The nodes in the quVid Of “ The first i individual neighbor node ”
			if( quG->vAdjacencyEdge[quVid][i].id2==quG_vID ) 
			{
				dbVid=iter->second;
				dbGadjacencyEdgeSize=dbG->vAdjacencyEdge[dbVid].size();
				for(j=1;j<dbGadjacencyEdgeSize;j++) // from 1 Start scanning in sequence dbVid The adjacency point , The first 0 What you save is (-1,-1)
				{
					// meanwhile , And quVid phase match The node of dbVid stay dbG Medium “ The first j individual neighbor node ” Is precisely dbG_vID
					if( dbG->vAdjacencyEdge[dbVid][j].id2==dbG_vID )
					{
						// Judge 2） Is it true 
						if( quG->vAdjacencyEdge[quVid][i].label != dbG->vAdjacencyEdge[dbVid][j].label )
						{
							// because 2） requirement 【 be-all 】label equally , As long as one is different , Then return to false
							return false;
						}
						else
						{
							// Mark ：flag=true It means that at least one pair is satisfied 1） Of pair(dbVid,quVid), At the same time, it satisfies 2）
							// Because it is possible that the cycle is over , In all already match The node of , Can't find one pair(dbVid,quVid) At the same time meet the conditions 1） and 2）
							flag=true;
						}
					}
				}
			}
		}
	}
	return flag;
}

Copy

Finally, the pseudo code of the algorithm is given ：

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/127834.html Link to the original text ：https://javaforall.cn