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