algorithm - 在有向图中找到所有可能路径中的公共(public)路径

Question

我试图找到循环有向图中每条可能路径总是访问的公共(public)节点。我的想法是计算所有可能的路径，然后搜索公共(public)元素。但是，a) 似乎不是很有效，b) 它没有考虑周期。

目标:是实现oblivious hashing perimeter作为一种防篡改方法。为此，我需要确定一组在控制流图中输入不可知的通用基本 block 。换句话说，我想找到将针对任何给定输入执行的程序的确定性 block (一组基本 block )。

Answer 1

要做您想做的事，您需要为路径提供一组起始顶点和结束顶点。所以你的声明是:

Find all vertices that are always passed when traversing from any vertex in set S to any vertex in set E.

然后您会注意到您要搜索的顶点是顶点分隔符。存在计算最小顶点分隔符的算法。