algorithm - 在不依赖潜在故障的情况下实现 Tarjan 的强连接组件

Question

我正在尝试在标准 ML 中实现图算法，但前提是唯一允许的效果是改变引用单元格。禁止异常(exception)和不终止。标准 ML 本身对这个问题并不重要。我会接受任何其他类型化编程语言的答案，只要它满足我的约束。 (不幸的是，无类型语言已经过时了:检查数据的格式是否正确以及潜在的失败本身就是我想要避免的影响。)

我将通过实现 Kosaraju 的算法来说明如何在我的约束下进行编程。我的问题是 Tarjan 的强连通分量算法是否也可以用这种方式实现。

datatype 'a node = Node of 'a * bool ref * 'a node list ref * 'a node list ref

fun node x = Node (x, ref false, ref nil, ref nil)
fun mark (Node (_, r, _, _)) = !r before r := true
fun unmark (Node (_, r, _, _)) = !r before r := false

fun value (Node (x, _, _, _)) = x
fun sources (Node (_, _, ref xs, _)) = xs
fun targets (Node (_, _, _, ref ys)) = ys

fun connect (m, n) =
  let
    val Node (_, _, _, ns) = m
    val Node (_, _, ms, _) = n
  in
    ms := m :: !ms;
    ns := n :: !ns
  end

datatype 'a state = Root of 'a node | Children of 'a node list

fun visit (xs, nil) = xs
  | visit (xs, Root x :: ss) = visit (x :: xs, ss)
  | visit (xs, Children nil :: ss) = visit (xs, ss)
  | visit (xs, Children (y :: ys) :: ss) =
    if mark y then
      visit (xs, Children ys :: ss)
    else
      visit (xs, Children (targets y) :: Root y :: Children ys :: ss)

fun assign (xs, nil) = xs
  | assign (xs, nil :: ss) = assign (xs, ss)
  | assign (xs, (x :: s) :: ss) =
    if unmark x then
      assign (x :: xs, sources x :: s :: ss)
    else
      assign (xs, s :: ss)

fun assigns (xs, nil) = xs
  | assigns (xs, y :: ys) =
    case assign (nil, (y :: nil) :: nil) of
        nil => assigns (xs, ys)
      | x => assigns (x :: xs, ys)

fun kosaraju xs = assigns (nil, visit (nil, Children xs :: nil))

是否有可能以这种方式实现 Tarjan 的强连通分量算法？

Answer 1

我这里有一个开源项目可以生成离散有限自动机:https://github.com/mtimmerm/dfalex

它包括 Tarjan 算法的实现，其风格与您想要的有点相似，但 DFS 函数采用 3 个 lambda:

   /**
     * Perform a depth first search of all states, starting at the start states
     * <P>
     * To avoid stack overflow errors on large DFAs, the implementation uses an auxiliary
     * stack on the heap instead of recursing
     * 
     * @param onEnter  called with (parent, child) when a child is entered.  parent == null for roots.
     * @param onSkip  called with (parent, child) when a child is skipped because it has been entered
     *                  previously.  parent == null for roots.
     * @param onLeave  called with (parent, child) when a child is exited.  parent == null for roots.
     */
    public void depthFirstSearch(
            BiConsumer<DfaState<MATCHRESULT>, DfaState<MATCHRESULT>> onEnter,
            BiConsumer<DfaState<MATCHRESULT>, DfaState<MATCHRESULT>> onSkip,
            BiConsumer<DfaState<MATCHRESULT>, DfaState<MATCHRESULT>> onLeave)
    {

Tarjan的算法在这个文件的第200行，一个方法调用“getCycleNumbers”:

https://github.com/mtimmerm/dfalex/blob/master/src/com/nobigsoftware/dfalex/DfaAuxiliaryInformation.java#L200

您对访客的定义不支持所有这 3 种不同类型的事件。它只提供“onEnter”。它们都是 Tarjan 算法所必需的。 是可以从您得到的东西中重构它们，但这比只编写一个提供所有 3 个的新 DFS 更复杂。