
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)? 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...). Looking forward to your feedback. Thanks and have a good night, Bin ----------------------------------------------------------------------------------------------- Small Test Case: For test, I only use one graph for "graphInputs", and one graph for "graphForest": graphInputs: (v: vertex, 1st number: the vertex id, 2nd number: the vertex name; e: edge, 1st: source vertex, 2nd: target vertex, 3rd: edge name) t # 0 v 0 0 v 1 0 v 2 0 v 3 0 v 4 0 v 5 0 v 6 1 v 7 1 v 8 1 v 9 1 v 10 2 v 11 0 v 12 0 v 13 2 v 14 0 v 15 0 v 16 0 v 17 0 v 18 1 v 19 1 v 20 1 v 21 3 v 22 3 v 23 4 v 24 5 v 25 5 e 0 1 3 e 1 2 3 e 2 3 3 e 3 4 3 e 4 5 3 e 5 0 3 e 0 6 0 e 1 7 0 e 4 8 0 e 5 9 0 e 2 10 0 e 10 11 0 e 11 12 3 e 12 13 0 e 13 3 0 e 11 14 3 e 14 15 3 e 15 16 3 e 16 17 3 e 17 12 3 e 14 18 0 e 15 19 0 e 17 20 0 e 13 21 1 e 10 22 1 e 16 23 0 e 23 24 0 e 23 25 0 graphForest: t # 1 v 0 0 v 1 0 v 2 0 v 3 0 v 4 0 v 5 0 v 6 1 v 7 1 v 8 1 v 9 1 v 10 1 v 11 4 v 12 4 v 13 6 v 14 5 v 15 3 e 0 1 3 e 1 2 3 e 2 3 3 e 3 4 3 e 4 5 3 e 5 0 3 e 0 6 0 e 1 7 0 e 2 8 0 e 3 9 0 e 5 10 0 e 4 11 0 e 11 12 0 e 11 13 0 e 13 14 0 e 12 15 1 If we only use vertex_equivalent, we can get some result like this: This is input Graph 0 <--> 1 5 6 1 <--> 0 2 7 2 <--> 1 3 10 3 <--> 2 4 13 4 <--> 3 5 8 5 <--> 4 0 9 6 <--> 0 7 <--> 1 8 <--> 4 9 <--> 5 10 <--> 2 11 22 11 <--> 10 12 14 12 <--> 11 13 17 13 <--> 12 3 21 14 <--> 11 15 18 15 <--> 14 16 19 16 <--> 15 17 23 17 <--> 16 12 20 18 <--> 14 19 <--> 15 20 <--> 17 21 <--> 13 22 <--> 10 23 <--> 16 24 25 24 <--> 23 25 <--> 23 This is the Graph in Forest: 0 <--> 1 5 6 1 <--> 0 2 7 2 <--> 1 3 8 3 <--> 2 4 9 4 <--> 3 5 11 5 <--> 4 0 10 6 <--> 0 7 <--> 1 8 <--> 2 9 <--> 3 10 <--> 5 11 <--> 4 12 13 12 <--> 11 15 13 <--> 11 14 14 <--> 13 15 <--> 12 Start to do Maximum Common Subgraph Search: Found common subgraph (size 10) 0 <--> 1 5 6 1 <--> 0 2 7 2 <--> 1 3 3 <--> 2 4 4 <--> 3 5 8 5 <--> 4 0 9 6 <--> 0 7 <--> 1 8 <--> 4 9 <--> 5 ....