Проверка и нормализация частично упорядоченного набора

Question

У меня есть массив таких пар:

[["a", "b"], ["b", "d"], ["a", "c"], ["e", "d"], ["a", "d"], ..., ["s", "f"]]

1. Как эффективный способ проверить, может ли данный массив выражать частичное упорядочение? То есть в данном массиве нет «петли», такой как ["a", "b"], ["b", "c"], ["c", "a"].

2. Если будет подтверждено, что массив выражает частичный порядок, я хочу нормализовать это, удалив все пары, которые могут быть получены рефлексивностью или транзитивностью. Например, как указано выше, поскольку существует ["a", "b"] и ["b", "d"], пара ["a", "d"] является избыточной и должна быть удалена.

Порядок между 1 и 2 не имеет значения. Если 2 следует сделать до или в процессе 1, то это нормально.

Предпочтительно, я хочу это в Ruby 1.9.3, но достаточно просто псевдокода.

Answer 1

Вторая проблема известна как переходное сокращение .

Answer 2

Для номера 1:
Вы можете смоделировать вашу проблему как график , и каждая пара будет ребром, затем вы можете запустить топологическую сортировку - если алгоритм терпит неудачу, график не является DAG - и существует "цикл" - в противном случае - вы получаете возможный частичный порядок в качестве результата топологической сортировки.

Для номера2:
Я вообще не уверен насчет этой части, так что этот ответ на самом деле только частичный, извините за это, - но всего лишь предварительная мысль:
Вы можете использовать DFS и удалять ребра из "уже обнаруженных" вершин в "только что обнаруженные вершины" [по тому же пути]. Хотя я не думаю, что это оптимально, но предварительное выполнение этого итеративно [до тех пор, пока не будет внесено никаких изменений], улучшит его.

Глубже, для номера2:
Я не уверен, что вы имеете в виду, но лес, созданный DFS, выполнит ваш запрос, однако, боюсь, вы можете потерять слишком много данных при его использовании, например: ["a","b"],["a","c"],["b",d"],["c","d"] обрежет один из ["b","d"] ИЛИ ["c","d"], что может быть слишком много, но оно также обрезает все «лишние» края, как описано в примере.

Answer 3

Для первой части вопроса я придумал свой собственный ответ здесь с помощью ответа на математическом сайте.

Для второй части вопроса:Следуя предложениям, данным в других ответах, я реализовал в Ruby (i) алгоритм Флойда-Варшалла для расчета транзитивного замыкания, (ii) композиции и (iii) транзитивного сокращения с использованием формулы R ^ -= R - R \ cdot R ^ +.

module Digraph; module_function
    def vertices graph; graph.flatten(1).uniq end
    ## Floyd-Warshall algorithm
    def transitive_closure graph
        vs = vertices(graph)
        path = graph.inject({}){|path, e| path[e] = true; path}
        vs.each{|k| vs.each{|i| vs.each{|j| path[[i, j]] ||= true if path[[i, k]] && path[[k, j]]}}}
        path.keys
    end
    def compose graph1, graph2
        vs = (vertices(graph1) + vertices(graph2)).uniq
        path1 = graph1.inject({}){|path, e| path[e] = true; path}
        path2 = graph2.inject({}){|path, e| path[e] = true; path}
        path = {}
        vs.each{|k| vs.each{|i| vs.each{|j| path[[i, j]] ||= true if path1[[i, k]] && path2[[k, j]]}}}
        path.keys
    end
    def transitive_reduction graph
            graph - compose(graph, transitive_closure(graph))
    end
end

Примеры использования:

Digraph.transitive_closure([[1, 2], [2, 3], [3, 4]])
#=> [[1, 2], [2, 3], [3, 4], [1, 3], [1, 4], [2, 4]]

Digraph.compose([[1, 2], [2, 3]], [[2, 4], [3, 5]])
#=> [[1, 4], [2, 5]]

Digraph.transitive_reduction([[1, 2], [2, 3], [3, 4], [1, 3], [1, 4], [2, 4]])
#=> [[1, 2], [2, 3], [3, 4]]