Boost-users

boost-users@lists.boost.org

September 2018

31 participants
27 discussions

ASIO?
by tim＠raisedbar.net 05 Sep '18

05 Sep '18

Hi, I'm looking for a mechanism allowing me to enumerate serial (Com) ports on Windows/Mac. I also need to be able to retrieve the name of a given serial device. I've had a quick look at boost::asio, but it isn't clear to me if it can do what I want. I'd be grateful for any advice, including alternatives if boost and/or ASIO aren't up to the job. Best wishes. Tim Burgess Raised Bar Ltd. E: <mailto:tim@raisedbar.net> tim(a)raisedbar.net M: +44 (0)7989 486976

3 2

mcgregor_common_subgraphs usage/complexity/performance/runtime
by Julian Wolf 01 Sep '18

01 Sep '18

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

2 2