mcgregor_common_subgraphs usage/complexity/performance/runtime

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

mcgregor_common_subgraphs usage/complexity/performance/runtime

Boost - Users mailing list
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_0-devel-1.67.0-2.3.x86_64


Thank you!
Julian


[1] https://www.boost.org/doc/libs/1_68_0/libs/graph/doc/
mcgregor_common_subgraphs.html
_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users

CommonSubgraph.cpp (2K) Download Attachment
graph1.dot (3K) Download Attachment
graph2.dot (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: mcgregor_common_subgraphs usage/complexity/performance/runtime

Boost - Users mailing list

On Sat, 1 Sep 2018 at 01:09, Julian Wolf via Boost-users <[hidden email]> wrote:
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.

On windows/vc/boost-1.68, the same thing happens. The graphs are tiny [reading and parsing should take most of the time], it looks more like you [the algo] get stuck in a loop, i.e. you hit a cycle (in a graph) with 0.8 and not with 0.7 (or there's a bug in your algo, creating an endless loop).
 
degski
---
If something cannot go on forever, it will stop" - Herbert Stein
“No, it isn’t truth. Truth isn’t truth" - Rudolph W. L. Giuliani

_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: mcgregor_common_subgraphs usage/complexity/performance/runtime

Boost - Users mailing list
On Saturday, 1 September 2018 05:26:59 CEST you wrote:

> On Sat, 1 Sep 2018 at 01:09, Julian Wolf via Boost-users <
>
> [hidden email]> wrote:
> > 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.
>
> On windows/vc/boost-1.68, the same thing happens. The graphs are tiny
> [reading and parsing should take most of the time], it looks more like you
> [the algo] get stuck in a loop, i.e. you hit a cycle (in a graph) with 0.8
> and not with 0.7 (or there's a bug in your algo, creating an endless loop).

Thank you for taking a look. It appears it's getting stuck around the
can_extend_graph function:

#0  0x000000000040da2b in
boost::iterators::detail::enable_if_interoperable<boost::detail::out_edge_iter...
#1  0x000000000040b8eb in bool boost::detail::can_extend_graph
#2  0x000000000040a4d0 in bool
boost::detail::mcgregor_common_subgraphs_internal
#3  0x000000000040a67f in bool
boost::detail::mcgregor_common_subgraphs_internal
...
#34 0x0000000000406e4e in void boost::mcgregor_common_subgraphs_unique
#35 0x0000000000404b02 in sufficient_mcgregor_common_subgraph
#36 0x0000000000404c9b in main ()


Breaking at the beginning of the can_extend_graph gives me the impression that
the current subgraph is being extended endlessly, therefore it indeed looks
like cycle thing. I wouldn't expect subgraphs being bigger than the actual
graphs (e.g. size 1000):

(gdb) break mcgregor_common_subgraphs.hpp:125 if subgraph_size = 1000
Breakpoint 13 at 0x40b802: file /usr/include/boost/graph/
mcgregor_common_subgraphs.hpp, line 125.
(gdb) c
Continuing.

Breakpoint 13,
[...]
 correspondence_map_1_to_2=..., subgraph_size=1000, new_vertex1=1,
new_vertex2=30, edges_equivalent=..., vertices_equivalent=...,
only_connected_subgraphs=true)
    at /usr/include/boost/graph/mcgregor_common_subgraphs.hpp:130


I guess the recursive DFS method mcgregor_common_subgraphs_internal runs
circles and doesn't find a stop condition?

I tried to reduce my graphs to find what vertices/edges cause this condition
but so far no success.

Since the implementation is around since 2009 and I have no experience with
the BGL I tend to blame my usage (e.g. graph type/storage/properties) or the
graphs I'm using though. Maybe some constraints I'm not aware of?


Other things I've tried:
- setting the only_connected_subgraphs parameter to false
- setting the edges to setS to disallow parallel edges since according to a
comment in the header parallel edges don't work:
typedef adjacency_list<setS, vecS, bidirectionalS, PDGNode, PDGEdge, PDGInfo>
graph_t;
No change, but I also didn't find any parallel edges in the graph in the first
place
- Simplify the call by ignoring the properties:  
mcgregor_common_subgraphs(graph1, graph2, true, callback);


Thanks!
Julian




_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users