[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
soon.
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.
Gabor
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