On Wed, 21 Mar 2012, Suhas Chakravarty wrote:
HiThe documentation for the mcgregor common subgraph library, at http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/mcgregor_common_subgraph..., says that " "mcgregor_common_subgraphs_maximum_unique(...); Explores the entire search space and invokes the user_callback afterward with each of the largest, unique discovered subgraphs. Returning false from the user_callback will not terminate the search because it is invoked after the search has been completed.
"
Given graph 1 A |__ B_| (Self loop on B) | C / \ D E \ / F | G / \ \ H \ / I
And graph 2 A |__ B_| (Self loop on B) | C | D | E / \ \ F \ / G
The application of mcgregor_common_subgraphs_maximum_unique gives me the following mapping: G1 <-> E2 H1 <-> F2 I1 <-> G2 But in addition, I was also expecting the mappings A1<-A2, B1<->B2 and C1<-E2, D1<-F2, since these are separate, maximum subgraphs
I see these (along with other smaller subgraphs) when I use simply "mcgregor_common_subgraphs" or "mcgregor_common_subgraphs_unique". Why do I not see them with the "maximum" version?
The "maximum" version only returns the largest common subgraph found in absolute size (or all of them in case of a tie), not all of them. What you want is called "maximal" common subgraphs, which does not appear to be implemented in BGL. You could do that with a custom callback, however. -- Jeremiah Willcock