Is there any algorithm to find all sub control flow graphs with single input/output in a control flow graph?

Question

This is a control flow graph, with an entry point(A), a body, and an exit point(H)

https://i.sstatic.net/rCb941kZ.png

I want to find all sub control flow graphs

In the graph I want to find:

1. entry point(B) and exit point(D2)
2. body(set[A2,B2,C2])

Take this set [A2,B2,C2] as a whole node N, N has single input from exteral B to A2, and single output from C2 to external D2, and there is no other input/output node outside N connected to N

Is there any algorithms to do so? The algorithm should be able to find sub entry point and sub exit point pair properly, and find a proper set accordingly

Answer 1

I think that the first step here is to develop a clear and complete definition of what you mean by a "sub control flow graph".

As far as I can make out from your description

A sub control flow graph is a subset of the vertices and edges of a directed acyclic graph where:

• one subset vertex ( the entry point ) has an in-degree of one and can reach every other subset vertex
• one subset vertex ( the exit point ) has an out degree of one and is reachable from every other subset vertex
• no vertex in the original graph but not in the subset can reach any subset vertex except the entry point
• no subset vertex except the exit point can reach any vertex outside the subset.

Assuming you agree with this, then the original graph has to be searched for subgraphs that fit the definition.

• remove original entry and exit points along with the edges connected to them.

• identify all possible entry points in remaining graph

• identify all possible exit points in remaining graph

• loop over every pair of entry and exit points

• Use yen's algorithm to find all the vertices between the current entry and exit points

• if the in-between vertices are isolated from others ( bullets 3 and 4 of definition ) then add to list of sub control flow graphs