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