Re: [igraph] Maximum Common Subgraph

[Mark Galea]

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

A--E

A--B

A

B

E

Cheers

M

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.

--
Tamas