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

[Gabor Csardi]

On Fri, Sep 21, 2007 at 10:27:41PM +0300, address@hidden wrote:
[...]
> 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.

I see. The first is basically motif-finding. This wouldn't be very hard 
to do for larger graphs than the currently supported 3-4 vertices
(actually there are no such limits in the current implementation, 
only we didn't have good graph-isomorphism code when i wrote this, but 
now we do), but in practice the number of non-isomorphic graphs is
growing so fast that it makes sense only for at most eight vertices,
or so. How large are your graphs and what is the size of the
subgraphs you're enumerating?

Zero-predessor means in-degree zero? This is a bit more specific,
so there is more hope than for the other problem. But i'm not an expert 
on this, could you point me to some algorithms for 1) enumerating 
all non-isomorphic graphs with n vertices and k zero-predessor nodes, and/or
2) an algorithm for finding all subgraphs of a graph 
with n vertices and k zero-predessor nodes?

I guess VF2 could be easily modified for 2, but more efficient approaches 
might exist.

Gabor
 
> Thank you very much for answer.
> 
> Kind regards
> Nikolaos Kavvadias
> 
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK