igraph-help
[Top][All Lists]

## Re: [igraph] Maximum Common Subgraph

 From: Tamás Nepusz Subject: Re: [igraph] Maximum Common Subgraph Date: Fri, 11 Mar 2011 20:18:01 +0100

```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

```