[Top][All Lists]

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

Re: [igraph] Help for subisomorphism problem

From: Gabor Csardi
Subject: Re: [igraph] Help for subisomorphism problem
Date: Mon, 3 Mar 2008 08:53:55 +0100
User-agent: Mutt/1.5.13 (2006-08-11)

Constraints like that are currently not allowed in our VF2 implementation.
What you can do is to calculate all subgraph isomorphisms and then
check whether one of them fulfills the constaints.

If you program in C then you can use igraph_subisomorphic_function_vf2,
to which you can supply a user-defined function, and this function
will be called whenever a subgraph isomorphism is found. This way you
can stop the search as soon as the mapping satisfies the constaints.

Btw. adding constraints to VF2 would be a nice extension, so i add it 
to our TODO list. The list is long, so don't expect this to be added 

The other thing you can to is to check the original VF2
implementation; if i remember correctly it does not allow constraints 
either, but it is worth checking it.
See P. Foggia, C. Sansone, M. Vento, An Improved algorithm for
matching large graphs, Proc. of the 3rd IAPR-TC-15 International
Workshop on Graph-based Representations, Italy, 2001.


On Mon, Mar 03, 2008 at 10:10:23AM +0800, Zhigang Wu wrote:
> Dear all,
> I want to check if graph2 is a subgraph of graph1, while the node order can be
> changed. However, there are some constrants, for example, node 5 in graph2 
> must
> correspond to node 6 in graph1, and node 6 in graph 2 must correspond to node
> 15 in graph1. My question is, how can I invoke the subisomorphic procedure to
> solve the problem?
> Many thanks in advance!
> Regards
> Zhigang Wu

> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

Csardi Gabor <address@hidden>    UNIL DGM

reply via email to

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