Re: [igraph] Maximum Common Subgraph

[Mark Galea]

Hey Tamas,

Thanks a lot for your help.  The sub-isomorphism together with the presented algorithm worked like a charm.  .  

Cheers, 

M

On Fri, Mar 11, 2011 at 7:18 PM, Tamás Nepusz <address@hidden> wrote:

Hi,

> Thanks for your reply.  Given the following example and the following background info http://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem
>
> g1 = Graph.Formula("A--B, A--E")
> g2 = Graph.Formula("A--B, A--C")
>
> Shouldn't the sub isomorphism problem return "A--B".

Well, the maximum common subgraph isomorphism problem should, but this is not what is implemented in igraph_subisomorphic_vf2. The subgraph isomorphism problem is as follows:

"In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H."
http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

> The current code base seems to require that the whole graph g2 matches some subgraph g1.  Is this the intended behavior?

Yes, it is.

> Is there a way to enumerate all possible subgraphs from a given graph?

Yes, there is, but you would have to write some code yourself; basically, you have to iterate over the powerset of the vertices and construct a subgraph for each element of the powerset. (Well, you may skip the empty graph or subgraphs with one vertex only as they are not really of any interest to you I guess).

Basically the solution is something along the lines of:

from itertools import powerset

def all_subgraphs(graph):
   for vertices in powerset(range(graph.vcount()):
       yield graph.subgraph(vertices)

Cheers,
--
Tamas