Questions about using "mcregor_common_subgraphs" algorithm in Boost Graph Library

18 Apr 2012

      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 

....

Bin Ren

Jeremiah Willcock

Bin Ren

Jeremiah Willcock

Bin Ren

tags

participants (2)