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