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-21 16:22:15

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