咨询：寻找控制流图中单一输入输出子控制流图的算法

存在符合需求的算法，这类算法属于控制流图的结构化分解范畴，核心是识别满足「单一外部输入、单一外部输出、内部节点无额外外部连接」的子图单元，具体实现思路如下：

核心步骤 #

• 定义边界规则

  • 子入口点：仅存在1条来自外部节点的边指向子图内部节点（如示例中外部节点B指向子图内的A2）
  • 子出口点：仅存在1条从子图内部节点指向外部节点的边（如示例中子图内的C2指向外部节点D2）
  • 子图内部所有节点的其他入/出边均仅连接子图内节点，无额外外部关联

• 候选子图遍历与验证

  1. 遍历控制流图中所有外部节点对（S, T），筛选存在路径从S到T的节点对
  2. 提取所有位于S到T的所有路径上的节点集合C
  3. 验证集合C：仅存在S到C内某节点的唯一外部输入，仅存在C内某节点到T的唯一外部输出，且C内所有节点的邻接节点均属于C
  4. 满足条件的（S, T, C）即为目标的子入口-子出口-主体集合三元组

• 结果优化

  • 对嵌套子图可按需保留指定粒度结果
  • 去除重复的候选集合（如不同节点对对应同一主体集合的情况）

针对示例的匹配说明 #

针对你提供的控制流图，算法会精准识别：

• 子入口点为B，子出口点为D2
• 主体集合为[A2,B2,C2]：验证后确认仅存在B→A2的外部输入、C2→D2的外部输出，且A2、B2、C2的所有关联边均在集合内部，完全符合规则

内容的提问来源于stack exchange，提问作者chao li