Re: [Boost-users] Questions about using "mcregor_common_subgraphs" algorithm in Boost Graph Library

Subject: Re: [Boost-users] Questions about using "mcregor_common_subgraphs" algorithm in Boost Graph Library
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-04-18 00:03:47

On Tue, 17 Apr 2012, Bin Ren wrote:

> Hi,
> 
> I am a beginner of C++ Boost Library. I am doing a project about "Maximum Common Subgraph" Algorithm, and I found
> there is an implementation in Boost Graph Library:
>  
> "boost/graph/mcgregor_common_subgraphs.hpp"
> 
> I use it like this: (and my question is marked as red)
> ----------------------------------------------------------------------------------------------------
>         //Compare the input graphs against the Graph Forest                            
>        
>         for (int i = 0; i < graphInputs.size(); ++i){                                  
>                 graph_t * pInputGraphi = graphInputs[i];            
> 
>                 for (int j = 0; j < graphForest.size(); ++j) {                         
>                         std::cout << "Common Sub graph of input graph" << i << " and graph" << j << " :" <<
> std::endl;
>                         //Compare one to one among graphi and graphj
>                         graph_t * pGraphj = graphForest[j];                                                      
>         
>                         //Here I am using the callback function from the example code:
> "mcgregor_subgraphs_example.cpp"
>                         example_callback<graph_t> my_callback(*pInputGraphi);
> 
>                         property_map<graph_t, vertex_name_t>::type vname_mapi = get(vertex_name,
> *pInputGraphi);                                                                
>                         property_map<graph_t, vertex_name_t>::type vname_mapj = get(vertex_name,
> *pGraphj);                                                                     
>                        
>                         property_map<graph_t, edge_name_t>::type ename_mapi = get(edge_name, *pInputGraphi);    
>                         property_map<graph_t, edge_name_t>::type ename_mapj = get(edge_name, *pGraphj);         
>                        
>                         //Print out Maximum connected Common Subgraphs between graphi and graphj                
>                                                                                   
> 
>                         mcgregor_common_subgraphs_maximum_unique(*pInputGraphi, *pGraphj, true, my_callback,
>                         //edges_equivalent(make_property_map_equivalent(ename_mapi, ename_mapj)),         
>                         //Here is my problem: if I use both edges_equivalent and vertices_equivalent, the code can
> not be compiled
>                         //However, if I only use vertices_equivalent, I doubt whether the maximum common subgraph
> result is correct.
>                         //If I use edges_equivalent only, the code can be compiled, however, it runs into an
> infinite loop.
>                         vertices_equivalent(make_property_map_equivalent(vname_mapi, vname_mapj)));
>                 }
>         }
> -------------------------------------------------------------------------------------------------------------------
> -----------------------------------------------------------
> 
> Is there any way to use both the edges_equivalent and the vertices_equivalent (Or it is not necessary at all)?

What error do you get?

> BTW, it seems the performance of this algorithm is not perfect; for a small test case below, it needs around 5
> seconds by vertices_equivalent, while it loops for a very long time for edges_equivalent (it might be a infinite
> loop...).

How unique are your edge names?  The algorithm gets very slow when it is
hard to distinguish different subgraphs (i.e., if there are a lot of
common subgraphs).

-- Jeremiah Willcock