[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 18:33:40 +0000

Hi Tamas, 

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".  

The current code base seems to require that the whole graph g2 matches some subgraph g1.  Is this the intended behavior?

Is there a way to enumerate all possible subgraphs from a given graph? For example given g1 we would have the following possible graphs.  

A--B A--E



On Fri, Mar 11, 2011 at 3:58 PM, Tamas Nepusz <address@hidden> wrote:

g = Graph.Formula("A-B-D-E")

g2 = Graph.Formula("B-C")


Clearly we are expecting to find the mapping [1,0] Referring to the mapping B from the first graph to B onto the second graph.  Am I missing something. 

Well, I don't expect to find it; the mapping [1, 0] would mean that vertex 0 of the second graph maps to vertex 1 of the first graph and vertex 1 of the second graph maps to vertex 0 of the first graph. Considering that graphs g and g2 have only one vertex in common (that has the same name, i.e. "B"), I wouldn't expect any subisomorphisms between the two graphs.


reply via email to

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