Hi, Jeremiah,
Thank you very much for your feedback.
>>What error do you get?
If I compiled it with both edges and vertices_equivalent:
mcgregor_common_subgraphs_maximum_unique(*pInputGraphi, *pGraphj, true, my_callback,
edges_equivalent(make_property_map_equivalent(ename_mapi, ename_mapj)),
vertices_equivalent(make_property_map_equivalent(vname_mapi, vname_mapj)));
I got some error message like:
comgraph.cpp: In function ‘int main()’:
comgraph.cpp:157: error: no matching function for call to ‘mcgregor_common_subgraphs_maximum_unique(boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, int, boost::no_property>, boost::property<boost::edge_name_t, int, boost::no_property>, boost::no_property, boost::listS>&, boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, int, boost::no_property>, boost::property<boost::edge_name_t, int, boost::no_property>, boost::no_property, boost::listS>&, bool, example_callback<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, int, boost::no_property>, boost::property<boost::edge_name_t, int, boost::no_property>, boost::no_property, boost::listS> >&, boost::bgl_named_params<boost::property_map_equivalent<boost::adj_list_edge_property_map<boost::undirected_tag, int, int&, long unsigned int, boost::property<boost::edge_name_t, int, boost::no_property>, boost::edge_name_t>, boost::adj_list_edge_property_map<boost::undirected_tag, int, int&, long unsigned int, boost::property<boost::edge_name_t, int, boost::no_property>, boost::edge_name_t> >, boost::edges_equivalent_t, boost::no_property>, boost::bgl_named_params<boost::property_map_equivalent<boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, int, boost::no_property>, boost::property<boost::edge_name_t, int, boost::no_property>, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, int, boost::no_property>, boost::property<boost::edge_name_t, int, boost::no_property>, boost::no_property, boost::listS>*, int, int&, boost::vertex_name_t>, boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, int, boost::no_property>, boost::property<boost::edge_name_t, int, boost::no_property>, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, int, boost::no_property>, boost::property<boost::edge_name_t, int, boost::no_property>, boost::no_property, boost::listS>*, int, int&, boost::vertex_name_t> >, boost::vertices_equivalent_t, boost::no_property>)’
make: *** [comgraph.o] Error 1
>>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).
The edge names are not unique. They can be classified into different groups, and identified by the group id.
For example:
e 1 7 0
means there is an edge between vertex "1" and vertex "7", and it is named as "0".
I use integer as the type of edge names. (And the same to vertex names).
I did another small test to test the attached graph (only 26vertices and 28edges) with itself, which means there are a lot of subgraphs, and it enters into an infinite loop.
My question is whether there is a way to speed up this kind of comparison with our build-in algorithm.
Thanks again, and have a nice day,
Bin
Attached Graph:
t # 0 //Graph 0
v 0 0 //vertex 0 with name 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 //edge 0<--->1 with name 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
Date: Wed, 18 Apr 2012 00:03:47 -0400
From: jewillco@osl.iu.edu
To: boost-users@lists.boost.org
Subject: 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<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
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users