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.
Note:
See TracTickets
for help on using tickets.
(In [54342]) Added example for McGregor algorithm from Michael Hansen; refs #3134; fixes #694