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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-10-20 22:36:03

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