[graph] Any plans to finish implementing subgraph?
Hi, I am using the subgraph class template in my work and I have noticed a number of issues. (1) I am unable to use boost::listS as the storage type for vertices or edges. I see that this is because the association between the local and global vertices is stored (in part) in a std::vector. Is there a plan to support subgraphs of non-array-indexed graphs? (2) The remove_edge_if() and clear_vertex() functions have comments stating that they are wrong. Are the functions wrong or are the comments wrong? If the functions are wrong, is there a plan to fix them? (3) The remove_vertex() function states that it is "under construction". Who is doing the construction? Is there a time-frame for this? I am asking these questions because I don't want to work on my own fixes/implementations of these issues if someone else is already putting forth the effort. Thanks, David
Responding to part of my own query...
(2) The remove_edge_if() and clear_vertex() functions have comments stating that they are wrong. Are the functions wrong or are the comments wrong? If the functions are wrong, is there a plan to fix them? (3) The remove_vertex() function states that it is "under construction". Who is doing the construction? Is there a time-frame for this?
I now see the problem with implementing clear_vertex() and remove_vertex() for subgraphs. In order for these two functions to have the same meaning for subgraphs that they have for regular graphs, they would have to operate on the set of all subgraphs -- not just induced subgraphs. This is because, in general, clear_vertex() will cause a subgraph to become non-induced and the context for calling remove_vertex() will usually make sense if the subgraph is non-induced. What we really need is at atomic operation that is "clear_vertex() followed by remove_vertex()". This makes me wonder why the remove_vertex() function does not do this for graphs in general. Any insight into this would be helpful. David
On Monday 24 January 2005 11:52 am, David M. Jones wrote:
I am using the subgraph class template in my work and I have noticed a number of issues.
The subgraph adaptor was never really finished; it has quite a few lingering bugs that need to be addressed, but thus far nobody has taken on that responsibility.
(1) I am unable to use boost::listS as the storage type for vertices or edges. I see that this is because the association between the local and global vertices is stored (in part) in a std::vector. Is there a plan to support subgraphs of non-array-indexed graphs?
Oh, yuck. subgraph should really take a VertexIndex parameter to map from global vertices to indices.
(2) The remove_edge_if() and clear_vertex() functions have comments stating that they are wrong. Are the functions wrong or are the comments wrong?
The functions are definitely wrong.
If the functions are wrong, is there a plan to fix them?
Not currently. They are, unfortunately, hard to implement well.
(3) The remove_vertex() function states that it is "under construction". Who is doing the construction? Is there a time-frame for this?
Nobody is doing the construction now :( remove_vertex is one of the nastier functions to implement, because it requires traversing both up and down the subgraph hierarchy removing all of the local vertices, which can invalidate descriptors. Doug
participants (2)
-
David M. Jones -
Douglas Gregor