[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Tamás Nepusz
Subject: Re: [igraph] Complex node attributes for subgraph isomorphism via vf2
Date: Tue, 17 Jan 2012 14:16:24 +0100

> 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":


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:


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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]