Re: [igraph] Maximum Common Subgraph

[Tamás Nepusz]

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