Re: [igraph] Maximum Common Subgraph

[Mark Galea]

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 <address@hidden> 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
address@hidden
http://lists.nongnu.org/mailman/listinfo/igraph-help