Re: [Boost-users] mcgregor_common_subgraphs usage/complexity/performance/runtime

Subject: Re: [Boost-users] mcgregor_common_subgraphs usage/complexity/performance/runtime
From: Julian Wolf (julian.jw.wolf_at_[hidden])
Date: 2018-09-01 09:32:23

On Saturday, 1 September 2018 05:26:59 CEST you wrote:
> On Sat, 1 Sep 2018 at 01:09, Julian Wolf via Boost-users <
> 
> boost-users_at_[hidden]> 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