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