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

Subject: Re: [Boost-users] Connected components not working Boost Graph library
From: Marcin Zalewski (marcin.zalewski_at_[hidden])
Date: 2015-07-29 01:32:34

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 <S.Choppin_at_[hidden]> 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<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]>
> 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]] *On
> Behalf Of *Marcin Zalewski
> *Sent:* 28 July 2015 12:00
> *To:* 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]>
> 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]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
>   _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
>  _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users