c# - 在有向图中查找由某些属性隔离的子图

Question

请原谅我对图论词汇的了解不多。

我只能用常见的英文单词来描述问题。也许有人可以指出正确的方向和/或要查找的术语。

这个问题是作为可视化编程语言实现的一部分出现的。其中顶点是函数/方法，边在函数之间传输数据。现在有以下问题:

可以允许将类型为 Collection< TItem > 的顶点 A 的输出连接到类型为 TItem 的顶点 B 的输入。然后将类型为 TItem 的顶点 B 输出到类型为 Collection< TItem > 的输入顶点 C。这将告诉编译器它必须围绕顶点 B 包装一个 foreach 函数，以将 B 的函数应用于 A 集合中的每个项目，并将新项目作为集合输出到 C 的输入。所以从 A 到 B 的边是多对一的连接，从 B 到 C 的边是一对多的。

现在实际的问题是，什么样的算法会找到一个被一对多连接包围/隔离的(有向)子图？以便编译器围绕这个特定的子图包装一个 foreach 函数？我试图在这张图片中想象问题:

Answer 1

请注意，您的图中可能有多个这样的子图。

要找到每个节点，您需要访问图中的所有节点并计算父/子节点以确定它是否是所需集合的成员，然后将所有标记的节点分离到它们各自的子图或cliques。可以在维基百科上找到使用 cliques 的一般程序:The Clique Problem .