graph-theory - 将控制流图转换为有向无环图

Question

假设我有一个循环控制流图

A -> B -> C -> D -> G
     ^         |
     |         v
     F <------ E

每个节点都与一个成本相关联。我还有一个状态变量，每次进入节点 D 时都会修改它。 的概率D -> E和D -> G由这个状态变量决定。

我想要的是枚举所有可能的路径（在某个状态P( D -> G) = 1），并找到每条路径的概率和成本。第一步，我认为是通过展开将带有状态变量的控制流图转换为有向无环图。有没有一个简单的算法呢？任何可以提供帮助的库（如networkx）？

Answer 1

我不认为这是可能的。

https://cs.stackexchange.com/questions/90481/how-to-remove-cycles-from-a-directed-graph

您始终可以通过删除所有边来使有向图无环。