[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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 {}



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


igraph-help mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]