Opened 16 years ago

Closed 13 years ago

#694 closed Feature Requests (fixed)

Add Maximum Common Subgraph (MCS) algorithm

Reported by: wegner Owned by: jsiek
Milestone: Component: graph
Version: None Severity:
Keywords: Cc:

Description

A very easy way to implement this is to generate a
product graph of two graphs and find cliques in this graph.
Every clique is a MCS.

I prefer that you provide the base objects for that
instead of implementing them on my own.

We need this for the OpenBabel project finding MCS in
molecules. BTW, a short hint how to transform a
molecule into a nominal or numerical labelled graph
would be nice.

And the product graph should allow both label types.

Change History (1)

comment:1 by Jeremiah Willcock, 13 years ago

Resolution: Nonefixed
Status: assignedclosed

(In [54342]) Added example for McGregor algorithm from Michael Hansen; refs #3134; fixes #694

Note: See TracTickets for help on using tickets.