igraph-help
[Top][All Lists]

## Re: [igraph] Maximum Common Subgraph

 From: Mark Galea Subject: Re: [igraph] Maximum Common Subgraph Date: Fri, 11 Mar 2011 10:56:56 +0000

Hi Tamas,

The problem I am facing with that approach is that the subgraph isomorphism is just considering the structure of the graph and thus is not restricting the sub-isomorphism to just labels which match.

Given Graph 1:
A - B
B - C

Graph 2:
D - E

The sub graph isomorphism returns something like this ( I will be using : to imply maps to)
A:D, B: E
B:D, A: E
B:D, C: E
C:D, B: E

In this case there is no common subgraph and the result should have been {}

Regards,

Mark

On Fri, Mar 11, 2011 at 10:50 AM, Tamas Nepusz wrote:

> I think, it is quite easy to write a code to select the edges, that are
> including in both graphs.
Assuming that the vertices are in the same order in both graphs (i.e.
vertex C has the same index in both graphs). Otherwise it is equivalent
to the subgraph isomorphism problem; one possible way to solve it would
be to re-arrange the vertices in both graphs such that vertices with the
same name also have the same ID, and then run the subgraph isomorphism
search.

--
Tamas

_______________________________________________
igraph-help mailing list