Maximum Common Subgraph

[Mark]

Hi there,

I am trying to find to get the maximum common subgraph given two
graphs however I cannot seem to find this in the library. Am I
missing something?

Given that Graph 1 is

A - B
A - C
B - D
D - E

Graph 2 is

A - B
A - E
B - D

Than the algorithm should return
A - B
B - D

Sub-isomorphism is not taking into account the unique node labels. Is
there a way to do this? It is a bit odd that such a functionality is
not provided.

Regards ,

Mark

[Aric Hagberg]

That looks like the "maximum common subgraph isomorphism problem"
http://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem
and you are right that there isn't an algorithm in NetworkX that does that.

I'm not familiar with algorithms for this (it's NP-hard) according to
that Wikipedia page.
Can someone comment on whether the maximal clique algorithm in
NetworkX can be used to solve this problem (using a product graph
G1XG2)?

Aric

[Aric Hagberg]

On Wed, May 4, 2011 at 3:23 AM, wellmannb <wellm...@googlemail.com> wrote:
> Hi, I'm also looking for a solution to this problem (MCS).
>
> I generated the product graph of the two graphs (G1,G22) and looked
> for the the max. clique with:
>
> product = nx.algorithms.operators.cartesian_product(G1,G2)
>
> cliques=nx.algorithms.clique.find_cliques(product)
>
> But the output was not really useful or to be more precise: the MCS
> was not among the found cliques.
>

I think that method of finding the MCS uses a different product graph
(not cartesian product) but I don't have the reference in front of me
to check.

Aric

[wellmannb]

Hi, I'm also looking for a solution to this problem (MCS).

I generated the product graph of the two graphs (G1,G22) and looked
for the the max. clique with:

product = nx.algorithms.operators.cartesian_product(G1,G2)

cliques=nx.algorithms.clique.find_cliques(product)

But the output was not really useful or to be more precise: the MCS
was not among the found cliques.

Thanks for any help!
Benjamin

On Mar 11, 5:24 am, Aric Hagberg <ahagb...@gmail.com> wrote:

> On Thu, Mar 10, 2011 at 6:46 PM, Mark <mmga...@gmail.com> wrote:
> > Hi there,
>

> > I am trying to find to get the maximum commonsubgraphgiven two

> > graphs however I cannot seem to find this in the library.  Am I
> > missing something?
>
> > Given that Graph 1 is
>
> > A - B
> > A - C
> > B - D
> > D - E
>
> > Graph 2 is
>
> > A - B
> > A - E
> > B - D
>
> > Than the algorithm should return
> > A - B
> > B - D
>
> > Sub-isomorphism is not taking into account the unique node labels.  Is
> > there a way to do this? It is a bit odd that such a functionality is
> > not provided.
>

> That looks like the "maximum commonsubgraphisomorphism problem"http://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem