Re: [Boost-users] Connected components not working Boost Graph library

Could you post a full executable program that gets the 938 answer? Thanks, Marcin On Tue, Jul 28, 2015 at 9:45 AM Choppin, Simon wrote:

My problem is the same,

I create a graph using the boost graph library. Each vertices of the graph is equivalent to a point in 3D space. If two points are within a given threshold distance, I create an edge between them on the graph.

My problem is that BOOST never seems to separate the points correctly. I have a Matlab script which always successfully partitions my point data into groups of points separated by distance. BOOST always incorrectly partitions.

I have simplified my code as much as possible to try and find the root of the issue (I no longer explicitly create vertices) but the results are always the same:

adjacency_list Graph;

for (size_t i = 0; i < PointDat.size(); i++)

{

for (size_t j = i; j < PointDat.size(); j++)

{

double thisdist = PointDat [i].Distance(PointDat [j]);

if (thisdist < distance && thisdist > 0)

{

add_edge(i, j, Graph);

}

}

}

std::vector<int> comp(num_vertices(Graph));

int num = connected_components(Graph, &comp[0]);

components_num = num;

components = comp;

Using the data I have here https://dl.dropboxusercontent.com/u/1584218/test.xyz (I set all z values to 0) BOOST always finds 938 vertices in the main component while Matlab (correctly) find 920. I have even exported the edges of the BOOST graph to matlab and it is still able to get the correct result, suggesting the structure of the graph is correct.

Thanks for any help,

Simon Choppin

*From:* Boost-users [mailto:boost-users-bounces@lists.boost.org] *On Behalf Of *Marcin Zalewski *Sent:* 28 July 2015 14:16

*To:* boost-users@lists.boost.org *Subject:* Re: [Boost-users] Connected components not working Boost Graph library

OK, but then do you have a different problem than the one posed in your original question? Maybe you can show us what problem do you have now?

On Tue, Jul 28, 2015 at 8:50 AM Choppin, Simon wrote:

Not at all!

I thanked the user in the comments for putting in so much work but the issue is not resolved! I use a threshold distance of 15 to separate the points but the connected components are still not calculated correctly. I’m on the verge of trying to write an algorithm from scratch. If you can help at all it would be much appreciated.

Simon C

*From:* Boost-users [mailto:boost-users-bounces@lists.boost.org] *On Behalf Of *Marcin Zalewski *Sent:* 28 July 2015 12:00 *To:* boost-users@lists.boost.org *Subject:* Re: [Boost-users] Connected components not working Boost Graph library

I can see that you answered yourself on stackoverflow. :)

On Mon, Jul 27, 2015 at 11:36 AM Choppin, Simon wrote:

Hello all,

I hope you can help me, I’m trying to group 3D point data in clusters according to the distance between points. I.e. different groups (or components) are separated by a minimum threshold distance.

To do this I am creating a boost graph (using the Boost Graph library), adding vertices (with 3D point information) and adding edges between nodes of the graph that are within my threshold distance.

However, when I find the connected components on the resulting graph I’m getting an incorrect answer. The vertices of the graph are not grouped correctly. I am comparing my results with a Matlab script (and their proprietary programs) which correctly separates the points.

I have a stackoverflow post with more detail (and no answers) http://stackoverflow.com/questions/27001402/connected-components-boost-c.

If you are able to help in any way I’d be very appreciative. I really don’t want to use compiled Matlab for this solution.

Thanks

Simon Choppin

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users