Re: [igraph] Complex node attributes for subgraph isomorphism via vf2

[Nicholas Dahm]

Hi Tamas,

Thanks for your reply. However what you have suggested will not work for my case. Let me explain myself better.

In
 my work, I have come across some cases where finding a single subgraph 
isomorphism can take months if labels are not taken into account. 
However by using detailed node labels, each node will only have a 
limited number of compatible nodes in the other graph. This in turn 
greatly reduces the branching factor of the search tree, and hence the 
computational time required.

The catch is that to determine 
whether a node is a compatible match to another, a lengthy matching 
procedure must be completed. This is why I need to write a function that
 is used to check compatibility during the VF2 search.

>From what I have read of the igraph documentation, and from my 
(admittedly limited) understanding of the VF2 code in topology.c, igraph
 currently does not support checking for compatible node labels 
during the matching process.

If I am correct about this, I would like (with your permission) to 
discuss the possibility of adding this functionality to igraph.

cheers

Nick

On 17 January 2012 18:40, Tamás Nepusz <address@hidden> wrote:

> Is there any way to create my own function to compare node attributes
> when using vf2 to find subgraph isomorphism?

Try igraph_subisomorphism_function_vf2():

http://igraph.sourceforge.net/doc/html/igraph_subisomorphic_function_vf2.html

It allows you to call a function when a subgraph isomorphism is found. You can check your extra conditions here and store the isomorphism if you need it.

Cheers,
Tamas