BGL and threaded graph modification
Hi! I am wondering if it is possible to modify a single graph object by multiple threads which attach edges into seperated regions of the graph? To be exact: I have a set of vertices in my graph with index 0-maxIndex which I want to copy a couple of times into that same graph structure one after another. Of course, I assure that there are no resize events during copying and no overlapping. This should be possible, I think, at least in theory, but I found no word about that in the docs of the BGL. So, should it work or not? Thanks, Sebastian
I am wondering if it is possible to modify a single graph object by multiple threads which attach edges into seperated regions of the graph? To be exact: I have a set of vertices in my graph with index 0-maxIndex which I want to copy a couple of times into that same graph structure one after another. Of course, I assure that there are no resize events during copying and no overlapping. This should be possible, I think, at least in theory, but I found no word about that in the docs of the BGL. So, should it work or not?
It depends on your choice of graph data structure. If you're using an adjacency_matrix, then trivially yes. If you're using adjacency_list, then you may have problems. The adjacency_list contains a global list of edges that is modified on add_edge so you're probably going to run into race conditions. Andrew Sutton andrew.n.sutton@gmail.com
Hi!
Well, I am using adjacency list with vecS vecS as storage. So I guess it is
not possible. BTW, is it possible to reserve the storage for the edges at
creation time of the graph? This would speed up things in case things get
large...
Sebastian
On Wed, Jul 29, 2009 at 2:17 PM, Andrew Sutton
I am wondering if it is possible to modify a single graph object by
multiple threads which attach edges into seperated regions of the graph? To be exact: I have a set of vertices in my graph with index 0-maxIndex which I want to copy a couple of times into that same graph structure one after another. Of course, I assure that there are no resize events during copying and no overlapping. This should be possible, I think, at least in theory, but I found no word about that in the docs of the BGL. So, should it work or not?
It depends on your choice of graph data structure. If you're using an adjacency_matrix, then trivially yes. If you're using adjacency_list, then you may have problems. The adjacency_list contains a global list of edges that is modified on add_edge so you're probably going to run into race conditions.
Andrew Sutton andrew.n.sutton@gmail.com
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Well, I am using adjacency list with vecS vecS as storage. So I guess it is not possible. BTW, is it possible to reserve the storage for the edges at creation time of the graph? This would speed up things in case things get large...
Not in a very obvious way. The adjacency_list inherits from a metafunction (sort of) called adj_list_gen<...> type, which turns out to be either an adj_list_impl or a vec_adj_list_impl, with the latter corresponding to the vertex list selector == vecS. Both of these have members m_edges, and m_vertices, which correspond to the global edge and vertex sets. The types of these containers are (should be?) determined by the vecS, listS stuff, and (more importantly) appear to be public for both implementations. I wrote that mainly for my own sake. If you have a graph g, you might just try writing: g.m_edges.reserve(n); Andrew Sutton andrew.n.sutton@gmail.com
Hi!
Thanks for the info, that should help a lot. BTW, next boost version has a
major enhancement of the BGL as the PBGL got integrated, right? Very cool!!
Sebastian
On Thu, Jul 30, 2009 at 1:52 PM, Andrew Sutton
Well, I am using adjacency list with vecS vecS as storage. So I guess it is
not possible. BTW, is it possible to reserve the storage for the edges at creation time of the graph? This would speed up things in case things get large...
Not in a very obvious way. The adjacency_list inherits from a metafunction (sort of) called adj_list_gen<...> type, which turns out to be either an adj_list_impl or a vec_adj_list_impl, with the latter corresponding to the vertex list selector == vecS. Both of these have members m_edges, and m_vertices, which correspond to the global edge and vertex sets. The types of these containers are (should be?) determined by the vecS, listS stuff, and (more importantly) appear to be public for both implementations.
I wrote that mainly for my own sake.
If you have a graph g, you might just try writing:
g.m_edges.reserve(n);
Andrew Sutton andrew.n.sutton@gmail.com
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (2)
-
Andrew Sutton -
Sebastian Weber