在有向图中查找由某些属性隔离的子图(Find subgraphs in a directed graph which are isolated by certain properties)

在有向图中查找由某些属性隔离的子图(Find subgraphs in a directed graph which are isolated by certain properties)

请原谅我对图论词汇的小知识。

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

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

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

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

Please excuse my small knowledge of graph theory vocabulary.

I can only describe the problem with common english words. Maybe someone can point me into the right direction and/or terms to look up.

The problem came up as part of the implementation of a visual programming language. Where a vertex is a function/method and the edges transport data between the functions. Now there is the following problem:

It could be allowed to connect the output of vertex A with the type of Collection< TItem > to the input of vertex B with type TItem. And then the output of vertex B with type TItem to the input vertex C with type Collection< TItem >. This would tell the compiler that it has to wrap a foreach function around vertex B to apply the function of B to each item in the collection from A and output the new items as collection to the input of C. So the edge from A to B is a many to one connection and from B to C is one to many.

Now the actual problem is, what kind of algorithm would find a (directed) subgraph that is surrounded/isolated by one to many connections? so that the compiler would wrap a foreach function around this particular subgraph? I've tried to visualize the problem in this picture:

最满意答案

我建议使用以下算法：

步骤1遍历所有节点。 如果找到蓝色节点，请在有向图中执行深度优先搜索 ，以找出可从中获取的白色节点集。 在执行DFS时不要交叉蓝色节点。 与节点集一起，存储在DFS期间发现的起始蓝色节点和外出蓝色节点。

您最终得到了多组白色节点，以及有关传入和传出蓝色节点的信息：

（忍受我，我的鼠标绘图技巧真的很糟糕）

第2步如您所见，您可能有重叠。 解决这个问题有两种可能性：

之后使用不相交的数据结构合并重叠集。 这导致O（n²+ m）最坏情况运行时。

通过修改标准DFS算法，避免首先创建重叠。 它应该检测您何时到达您在之前探索过的集合中已经看到的节点。 然后它不应该进一步探索子图，但记录当前探索的集合和重叠的集合将在以后合并。 之后，您可以在合并图中找到已连接的组件。 这将为您提供O（n + m）运行时，这要好得多。

最终得到一组不相交的白色节点以及相应的传入和传出蓝色节点：

I would suggest the following algorithm:

Step 1 Walk through all the nodes. If you find a blue node, do a depth-first search in the directed graph to find out the set of white nodes reachable from it. Don't cross blue nodes while doing the DFS. Along with the set of nodes, store the starting blue node and the outgoing blue nodes that you discovered during the DFS.

You end up with multiple sets of white nodes, along with information about the incoming and outgoing blue nodes:

(bear with me, my mouse drawing skills are really bad)

Step 2 As you can see, you might have overlaps. There are two possibilities to resolve this:

Merge overlapping sets by using a disjoint-set data structure afterwards. This results in a O(n² + m) worst case runtime.

Avoid creating the overlaps in the first place by modifying the standard DFS algorithm. It should detect when you reach a node that you have already seen in one of the previously explored sets. It should then not explore the subgraph further, but record that the currently explored set and the overlapping one are to be merged later. Afterwards you can find the connected components in the merging graph. This will give you a O(n + m) runtime, which is a lot better.

You end up with a collection of disjoint sets of white nodes together with respective incoming and outgoing blue nodes: