[BGL] Auto Connect vertexes by predicate?
Hello,
Are there ways to generate Graph with edges by the user defined function?
Should I generate Vertex relations by hand then put it in to Graph?
I would like to feed graph by points 3d and each point is linked to its
closest neighbor by distance. Then as a next step I would like to dig in the
graph the sub-graphs with the given linking length.
My Data structure is following:
_____________________
class CCoord
{
public:
CCoord(){};
CCoord(int id_,MyFloat x_,MyFloat y_,MyFloat z_, MyFloat w_=0):
id(id_), x(x_), y(y_), z(z_), w(w_){
if(w==0.0)
w=sqrt(x*x+y*y+z*z);
};
MyFloat x, y, z;
int id;
MyFloat w;
}
typedef std::vector<CCoord> typeVecData;
typedef adjacency_list < vecS, vecS, undirectedS,
no_property, property < edge_weight_t, MyFloat > > Graph;
typedef graph_traits < Graph >::edge_descriptor Edge;
typedef graph_traits < Graph >::vertex_descriptor Vertex;
typedef std::pair
On Fri, 8 May 2009, arm2arm wrote:
Hello, Are there ways to generate Graph with edges by the user defined function? Should I generate Vertex relations by hand then put it in to Graph? I would like to feed graph by points 3d and each point is linked to its closest neighbor by distance. Then as a next step I would like to dig in the graph the sub-graphs with the given linking length.
There are two basic, efficient ways to do this: use an implicit graph, or
create a pair of edge iterators and use those to create a concrete graph.
You could also add edges one at a time using a loop, but that is likely to
be less efficient.
1. Implicit graph: if you are not mutating the structure of the graph at
all and your relation is fairly simple (which yours appears to be), you do
not need to create an adjacency_list data structure at all. Just define
your own graph type: your type would have coordinate triples as vertex
descriptors, and an out_edges function that returns all adjacent triples.
You would not store the edges explicitly at all, but could still define
external properties on them that you could mutate (if you created an
edge_index property map for your graph type). I believe an example of
this is in chapter 9 of the BGL book. I was not able to find a good
example online, but some related comments are at:
http://www.nabble.com/-Graph--is-it-possible-to-define-my-own-edge_descripto...
2. Edge iterators: there are many graph generators in BGL that are
implemented as iterator ranges over pairs of vertices. Look in
On Fri, 8 May 2009, arm2arm wrote:
Hello, Are there ways to generate Graph with edges by the user defined function? Should I generate Vertex relations by hand then put it in to Graph? I would like to feed graph by points 3d and each point is linked to its closest neighbor by distance. Then as a next step I would like to dig in the graph the sub-graphs with the given linking length.
Sorry -- I misunderstood your question and assumed you wanted to create a grid on a 3-D lattice. If you already have a list of vertex pairs that you want to use as edges, just pass the begin and end iterators of that list (vector, etc.) to the graph constructor. If you are willing to sort the vertex pairs in advance and will not be mutating the graph's structure, you can use compressed_sparse_row_graph to save memory and computation time. Is that closer to what you wanted? I don't fully understand what you are computing from the points and what you want the BGL graph to contain. -- Jeremiah Willcock
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. Thanks Arman. Sorry -- I misunderstood your question and assumed you wanted to create a grid on a 3-D lattice. If you already have a list of vertex pairs that you want to use as edges, just pass the begin and end iterators of that list (vector, etc.) to the graph constructor. If you are willing to sort the vertex pairs in advance and will not be mutating the graph's structure, you can use compressed_sparse_row_graph to save memory and computation time. Is that closer to what you wanted? I don't fully understand what you are computing from the points and what you want the BGL graph to contain. -- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users -- View this message in context: http://www.nabble.com/-BGL--Auto-Connect-vertexes-by-predicate--tp23451992p2... Sent from the Boost - Users mailing list archive at Nabble.com.
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
arm2arm escribió:
Hello, Are there ways to generate Graph with edges by the user defined function? Should I generate Vertex relations by hand then put it in to Graph? Hi, I think it is going to be implemented soon: http://socghop.appspot.com/student_project/show/google/gsoc2009/boost/t12402...
Regards, Dmitry
Are there ways to generate Graph with edges by the user defined function? Should I generate Vertex relations by hand then put it in to Graph?
Hi, I think it is going to be implemented soon:
http://socghop.appspot.com/student_project/show/google/gsoc2009/boost/t12402...
I don't know if "soon" is quite the right word :) but it does sound like this might address your problem. Andrew Sutton andrew.n.sutton@gmail.com
participants (4)
-
Andrew Sutton -
arm2arm -
Dmitry Bufistov -
Jeremiah Willcock