Re: [Boost-users] [BGL] Auto Connect vertexes by predicate?

Subject: Re: [Boost-users] [BGL] Auto Connect vertexes by predicate?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-05-09 02:16:06

> Hello,
> Oh, no I do not have 3D grid I have only points.
> To clear: My task is following: Find the cluster of the points in 3D. There
> is a known algorithm widely used in astrophysics: Friends of Friends (FOF)(
> for ex: http://www-hpcc.astro.washington.edu/tools/afof.html).
> You link in to the group all particles with given the distance (linking
> length - LL). The more general extended method is MST (minimum spanning
> tree) based groups. So you link particles in 3d with only closest neighbor.
> Then you cut and separate all groups by given maximum LL.
> I would like to implement this algorithm by BGL.
>
> Using STL stack sorted by distance I can make pairs and put them one by one
> to the graph (your suggestion #3) , but I would like to know for more
> efficient way to do it.

What do you mean using a stack?  Are you not using the cell-list-based 
algorithm described in the paper you linked to?  Are you going to be 
mutating the graph after you create it, or is the graph going to be a 
static representation of the points within a given range?  If it is going 
to be static, I would recommend creating a compressed_sparse_row_graph and 
then using its add_edge function (faster than the one in adjacency_list 
but requires the edges to be sorted) to build the graph.  Please use the 
version from Boost's SVN head, though, since it has looser sorting 
requirements (the out edges of a vertex do not need to be sorted by 
target).  You probably already can create the edges sorted by source 
vertex; if not, there are other options available within the CSR format, 
or you can just add edges to an adjacency_list like you're currently 
planning to do.  Note that the CSR graph is only for directed graphs right 
now; undirected graphs will either require inserting each edge as two 
separate edges or using adjacency_list.  Is that closer to answering your 
question?

-- Jeremiah Willcock