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

[Tamás Nepusz]

> 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.
In this case, take a look at the upcoming igraph 0.6 (currently in development 
stage), where the signature of igraph_subisomorphism_function_vf2() is extended 
to accomodate for vertex and edge "colors":

http://bazaar.launchpad.net/~igraph/igraph/0.6-main/view/head:/src/topology.c#L1801

Would this be a suitable solution for you (i.e. can you group your vertices 
into "classes" such that vertices in the same class are compatible with each 
other)? If not, I believe it is not too complicated to tweak 
subisomorphic_function_vf2 further; the comparisons between vertex and edge 
colors are currently in the following lines:

http://bazaar.launchpad.net/~igraph/igraph/0.6-main/view/head:/src/topology.c#L2115
http://bazaar.launchpad.net/~igraph/igraph/0.6-main/view/head:/src/topology.c#L2154
http://bazaar.launchpad.net/~igraph/igraph/0.6-main/view/head:/src/topology.c#L2181

Theoretically, the only modification required would be to call an external 
function here instead of doing a simple comparison.

Cheers,
Tamas