algorithmgraph-theorydirected-graphcontrol-flow-graph

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


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


Solution

  • 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:

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