igraph-help
[Top][All Lists]

## 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