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

Subject: Re: [Boost-users] Connected components not working Boost Graph library
From: Choppin, Simon (S.Choppin_at_[hidden])
Date: 2015-07-28 09:44:29

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<vecS, vecS, undirectedS,Point> 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_at_[hidden]] On Behalf Of Marcin Zalewski
Sent: 28 July 2015 14:16
To: boost-users_at_[hidden]
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 <S.Choppin_at_[hidden]<mailto:S.Choppin_at_[hidden]>> 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_at_[hidden]<mailto:boost-users-bounces_at_[hidden]>] On Behalf Of Marcin Zalewski
Sent: 28 July 2015 12:00
To: boost-users_at_[hidden]<mailto:boost-users_at_[hidden]>
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 <S.Choppin_at_[hidden]<mailto:S.Choppin_at_[hidden]>> 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_at_[hidden]<mailto:Boost-users_at_[hidden]>
http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________
Boost-users mailing list
Boost-users_at_[hidden]<mailto:Boost-users_at_[hidden]>
http://lists.boost.org/mailman/listinfo.cgi/boost-users