[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 11:37:55 +0000

Hi Tamas,

Will try that soon. Could you perhaps provide an example or the api call I actually need to use. 

Thanks a lot. 


On Mar 11, 2011, at 11:04 AM, Tamas Nepusz <address@hidden> wrote:

Hi Mark,

I've just realized that the "labeled subisomorphism" you are looking for has been added in igraph 0.6 a while ago, and it supports both vertex and edge labels. Try compiling and installing the latest nightly snapshot of igraph from http://code.google.com/p/igraph.


On 03/11/2011 11:56 AM, Mark Galea wrote:
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]