[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [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
Nikolaos Kavvadias

**[igraph] Re: Enumeration of subgraphs under constaints**,
*nkavv* **<=**