Re: [Boost-users] Clarification on McGregor common subgraph library

Subject: Re: [Boost-users] Clarification on McGregor common subgraph library
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-03-22 17:04:10

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_subgraphs.html,%a0%a0says 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