Re: [Boost-users] Can't link subgraphs because remove_vertex is a TODO

Subject: Re: [Boost-users] Can't link subgraphs because remove_vertex is a TODO
From: Trevor Harmon (Trevor.W.Harmon_at_[hidden])
Date: 2010-10-20 19:47:43

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