
Boost Users : 
Subject: [Boostusers] mcgregor_common_subgraphs usage/complexity/performance/runtime
From: Julian Wolf (julian.jw.wolf_at_[hidden])
Date: 20180831 21:45:03
Hello everyone,
I'm new to Boost and today I tried to use the mcgregor_common_subgraphs
functions but can't find an explanation why the function shows such bad
performance when I use it.
According to the documentation [1] the algorithm runs in O(V1 * V2) for the
entire space with V being the number of vertices in the two graphs. So not
great, but I'd expect that to run in reasonable time for graphs with less than
100 vertices.
But in my case it doesn't, therefore any help appreciated whether I have some
error or misconception on my side or whether this is expected performance.
What I'm trying to achieve: I want to check whether two graphs have a common
subgraph of size x. x depends on the size of smaller graph, I'm using a factor
y for this with 0 < y < 1.
With smaller values for x (e.g. x = 0.7 * V1) the example returns very fast,
which makes sense since a smaller part of the search space needs to be
explored.
If I increase the factor to 0.8 * V1 or even run through the whole search
space the program does not terminate within 10 minutes (where I canceled)
I'll attach a working example as well as two graphs (44 and 46 vertices)
showing the behaviour described.
# gcc CommonSubgraph.cpp o common_subgraph_example lboost_graph lstdc++
# time ./common_subgraph_example 0.7 graph1.dot graph2.dot
Factor 0.7
Size: 30
real 0m0.043s
# time ./common_subgraph_example 0.8 graph1.dot graph2.dot
Factor 0.8
^C
real 10m39.741s
My system runs openSUSE Tumbleweed with Boost 1.67
> rpm q whatprovides /usr/include/boost/graph/mcgregor_common_subgraphs.hpp
libboost_headers1_67_0devel1.67.02.3.x86_64
Thank you!
Julian
[1] https://www.boost.org/doc/libs/1_68_0/libs/graph/doc/
mcgregor_common_subgraphs.html
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net