igraph-help
[Top][All Lists]

## [igraph] Re: Enumeration of subgraphs under constaints

 From: nkavv Subject: [igraph] Re: Enumeration of subgraphs under constaints Date: Fri, 21 Sep 2007 22:27:41 +0300 User-agent: Internet Messaging Program (IMP) 3.2.6

```> these are all we have:
> http://cneurocvs.rmki.kfki.hu/igraph/doc/html/igraph-Motifs.html
> and the VF2 subgraph isomorphism algorithm is included in the development
> branch. (The one in 0.4.3 can only decide graph isomorphism.)
>
> Could you explain it briefly what kind of functionality you want?
> You want to create all non-isomorphic graphs with some constraints?
> Or you want to count the number of subgraph isomorphisms of G1 in G2, with
> either G1 and G2 fixed while other varies?
> Maybe giving a link is enough.
>
> Thanks,
> Gabor

Dear sir,

the VF2 (of Paolo Foggia's fame) is a quite efficient algorithm and it is very
nice that igraph supports it. I use VF2 quite a lot, from Foggia's
implementation.

I would say, yes, i want to create all non-isomorphic graphs with some
constraints.

What i have in mind is enumeration of subgraphs that are more general than
small-sized motifs. Also, i'm looking for a way to apply constraints (e.g. in
the form of queries) to a given graph for its subgraphs. Such constraints would
regard:
1. Number of vertices (size)
2. Number of zero-predecessor and zero-successor nodes within the subgraph
3. Other user-defined properties regarding semantics/attributes of nodes and
edges that this would be very application-specific and difficult to derive a
generic solution for.

Having the possibility to set 1. and 2. would be much of what i'm looking for.

Thank you very much for answer.

Kind regards