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@lists.boost.org> 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