Can't link subgraphs because remove_vertex is a TODO
Hi, I have two directed subgraphs that I want to link together in a particular way. To illustrate: BEFORE 1 ---> 2 ---> 3 4 ---> 5 ---> 6 AFTER 1 ---> 2 ---> 3 \---> 5 ---> 6 Note that vertex 4 is removed, and the edge that was linking 4 to 5 now links 1 to 5. Seems simple enough, but there are two problems, one minor and one major: 1) To rewire the edge's source from 4 to 1, I'd like to simply change the edge's source. But that doesn't seem possible in Boost. It appears I must remove the edge and add a new one with the desired source. This can get complicated when it comes to preserving the edge's properties, index maps, and such, but hey, at least it's doable. 2) This one I can't work around. Calling remove_vertex on a subgraph gives an assertion failure: Assertion failed: (false), function remove_vertex, file /usr/local/ boost_1_43_0/boost/graph/subgraph.hpp, line 733. It turns out that subgraph's remove_vertex method is not implemented at all, which is quite the showstopper for my project. I don't know enough about Boost to implement it myself. Any suggestions? Thanks, Trevor
On Wed, 13 Oct 2010, Trevor Harmon wrote:
Hi,
I have two directed subgraphs that I want to link together in a particular way. To illustrate:
BEFORE 1 ---> 2 ---> 3 4 ---> 5 ---> 6
AFTER 1 ---> 2 ---> 3 \---> 5 ---> 6
Note that vertex 4 is removed, and the edge that was linking 4 to 5 now links 1 to 5.
Seems simple enough, but there are two problems, one minor and one major:
1) To rewire the edge's source from 4 to 1, I'd like to simply change the edge's source. But that doesn't seem possible in Boost. It appears I must remove the edge and add a new one with the desired source. This can get complicated when it comes to preserving the edge's properties, index maps, and such, but hey, at least it's doable.
Yes, you do need to remove the edge and re-add it. Remember that changing an edge's source in an adjacency list structure does not just involve changing one value, but removing the edge from one list and adding it to another. Thus, changing the source vertex is basically the same as removing the edge and re-adding it with the new source.
2) This one I can't work around. Calling remove_vertex on a subgraph gives an assertion failure:
Assertion failed: (false), function remove_vertex, file /usr/local/boost_1_43_0/boost/graph/subgraph.hpp, line 733.
It turns out that subgraph's remove_vertex method is not implemented at all, which is quite the showstopper for my project. I don't know enough about Boost to implement it myself. Any suggestions? Thanks,
I've now #if 0'ed it out so code using remove_vertex on subgraphs no longer compiles, rather than getting a run-time error. I don't know the code well enough to implement it either. What exactly are you trying to do with subgraphs? Maybe there is another way to do it that doesn't hit these problems. -- Jeremiah Willcock
On Oct 19, 2010, at 9:20 AM, Jeremiah Willcock wrote:
What exactly are you trying to do with subgraphs? Maybe there is another way to do it that doesn't hit these problems.
I'm trying to link two subgraphs in such a way that requires vertex removal. Attached are two PDFs showing the "before" and "after" for a simple example. Note that the entry and exit vertices (4 and 5) are removed. Luckily, the remove_edge method works for subgraphs, so I'm able to rewire the edges as illustrated. Although this leaves the unremovable vertices dangling, they are effectively removed from all traversal algorithms. However, I do have to add some special case code to skip them whenever I output the graph data. Trevor P.S. I have created a bug report on this: https://svn.boost.org/trac/boost/ticket/4752
On Tue, 19 Oct 2010, Trevor Harmon wrote:
On Oct 19, 2010, at 9:20 AM, Jeremiah Willcock wrote:
What exactly are you trying to do with subgraphs? Maybe there is another way to do it that doesn't hit these problems.
I'm trying to link two subgraphs in such a way that requires vertex removal. Attached are two PDFs showing the "before" and "after" for a simple example. Note that the entry and exit vertices (4 and 5) are removed.
Are you doing this process once, or iteratively? I.e., do you merge the results of merging rather than just merging disjoint parts of the original graph? Is there a standard name for the algorithm you're trying to implement so I can read about it in detail?
Luckily, the remove_edge method works for subgraphs, so I'm able to rewire the edges as illustrated. Although this leaves the unremovable vertices dangling, they are effectively removed from all traversal algorithms. However, I do have to add some special case code to skip them whenever I output the graph data.
You can use filtered_graph for that if you feel like it; it will automatically remove those vertices.
P.S. I have created a bug report on this: https://svn.boost.org/trac/boost/ticket/4752
I saw that -- that's why the function is commented out now rather than always failing at runtime. -- Jeremiah Willcock
On Oct 19, 2010, at 2:14 PM, Jeremiah Willcock wrote:
I'm trying to link two subgraphs in such a way that requires vertex removal. Attached are two PDFs showing the "before" and "after" for a simple example. Note that the entry and exit vertices (4 and 5) are removed.
Are you doing this process once, or iteratively? I.e., do you merge the results of merging rather than just merging disjoint parts of the original graph?
Iteratively, yes. After linking subgraph B to subgraph A, subgraph C will be linked to subgraph A or B or both. The process repeats for subgraphs D and so on.
Is there a standard name for the algorithm you're trying to implement so I can read about it in detail?
I don't think it's generic enough to be a standard graph algorithm. The context is a control flow graph, where each subgraph represents a C function. Each of these (directed) subgraphs has a single entry node and single exit node. The purpose of the linking is to build up a global control flow graph representing the call graph for a given starting function. Wherever there's a function call, the callee subgraph is linked to its caller. After the linking, the entry and exit nodes of the callee no longer have meaning and must be removed. Trevor
On Wed, 20 Oct 2010, Trevor Harmon wrote:
On Oct 19, 2010, at 2:14 PM, Jeremiah Willcock wrote:
I'm trying to link two subgraphs in such a way that requires vertex removal. Attached are two PDFs showing the "before" and "after" for a simple example. Note that the entry and exit vertices (4 and 5) are removed.
Are you doing this process once, or iteratively? I.e., do you merge the results of merging rather than just merging disjoint parts of the original graph?
Iteratively, yes. After linking subgraph B to subgraph A, subgraph C will be linked to subgraph A or B or both. The process repeats for subgraphs D and so on.
Is there a standard name for the algorithm you're trying to implement so I can read about it in detail?
I don't think it's generic enough to be a standard graph algorithm. The context is a control flow graph, where each subgraph represents a C function. Each of these (directed) subgraphs has a single entry node and single exit node. The purpose of the linking is to build up a global control flow graph representing the call graph for a given starting function. Wherever there's a function call, the callee subgraph is linked to its caller. After the linking, the entry and exit nodes of the callee no longer have meaning and must be removed.
In that case, I think you could avoid removing vertices in the way you're doing now. Even if you're removing entry and exit nodes, you will most likely eventually want to ignore nodes marked as dead code by an analysis, so you might need the code to skip particular vertices even if you do remove them. BTW, what are you using subgraphs for? Why not have a single big graph, possibly filtered to limit algorithms to subgraphs of interest? -- Jeremiah Willcock
On Oct 20, 2010, at 7:36 PM, Jeremiah Willcock wrote:
I don't think it's generic enough to be a standard graph algorithm. The context is a control flow graph, where each subgraph represents a C function. Each of these (directed) subgraphs has a single entry node and single exit node. The purpose of the linking is to build up a global control flow graph representing the call graph for a given starting function. Wherever there's a function call, the callee subgraph is linked to its caller. After the linking, the entry and exit nodes of the callee no longer have meaning and must be removed.
In that case, I think you could avoid removing vertices in the way you're doing now. Even if you're removing entry and exit nodes, you will most likely eventually want to ignore nodes marked as dead code by an analysis, so you might need the code to skip particular vertices even if you do remove them.
For this research project, I'm not concerned with code optimizations, but if I were, the optimizations would be performed before I make a pass on the code.
BTW, what are you using subgraphs for? Why not have a single big graph,
Without subgraphs, the call graph structure is lost. It becomes very difficult to identify where one function ends and another begins. But if I have subgraphs, I can very easily iterate over them to produce a GraphViz DOT file that clusters a function's basic blocks into one group. And I can still treat the control flow as one big graph simply by accessing the subgraph root, so I get the best of both worlds. Trevor
participants (2)
-
Jeremiah Willcock -
Trevor Harmon