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

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 my_callback(*pInputGraphi);

                        property_map::type vname_mapi = get(vertex_name, *pInputGraphi);                                                                                         property_map::type vname_mapj = get(vertex_name, *pGraphj);                                                                                                                      property_map::type ename_mapi = get(edge_name, *pInputGraphi);                             property_map::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