图算法：通过用单个节点替换节点链来简化图

Question

我正在寻找一种有向加权图简化算法，该算法寻找恰好具有一个入站边缘和恰好一个出站边缘并且互连的节点链，并用权重等于被替换节点权重之和的单个节点替换此类链。

这样，类似这样：

 w=1 → w=3 → w=2 → (w=7 → w=1 → w=1)
  ↓           ↑
(w=4 → w=1 → w=2)

变成：

 w=1 → w=3 → w=2 → w=9
  ↓           ↑
  \--> w=7 ---/

替换的节点链位于第一张图的括号

()

中。显然，编写简单的实现非常简单。

这个算法的名称是什么？我想知道如何在讨论中正确命名它、在参考书中查找、在图形库中搜索实现、比较不同实现的性能等。

Answer 1

我猜是Kosaraju的算法。