Реализация сильно связанных компонентов Тарьяна, не полагаясь на потенциальный сбой в качестве эффекта

Question

Я пытаюсь реализовать алгоритмы графа в стандарте ML, при условии, что единственный допустимый эффект - это мутирование ссылочных ячеек. Исключения и нетерминации запрещены. Сам по себе стандарт ML не имеет значения для вопроса. Я приму ответ на любом другом типизированном языке программирования, если он удовлетворяет моим ограничениям. (К сожалению, нетипизированные языки отсутствуют: проверка правильности данных и возможного сбоя сама по себе является эффектом, которого я хочу избежать.)

Я проиллюстрирую, как можно программировать под моими ограничениями, реализуя алгоритм Косараджу. ,Мой вопрос заключается в том, может ли алгоритм сильно связанных компонентов Тарьяна быть реализован в этом стиле.

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))

Возможно ли реализовать алгоритм сильно связанных компонентов Тарьяна в этом стиле?

Answer 1

У меня есть проект с открытым исходным кодом, который производит дискретные конечные автоматы: https://github.com/mtimmerm/dfalex

Он включает в себя реализацию алгоритма Тарьяна в стиле, который несколько похож на то, что вы хотите, но функция DFS требует3 лямбда-выражения:

   /**
     * 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)
    {

Алгоритм Тарьяна находится в этом файле в строке 200, вызов метода "getCycleNumbers":

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

Ваше определение посетителя отсутствуетне поддерживает все эти 3 различных вида событий. Это только обеспечивает "onEnter". Все они необходимы для алгоритма Тарьяна. можно восстановить их из того, что вы получаете, но это будет сложнее, чем просто написать новую DFS, которая предоставляет все 3.