验证和标准化偏序集 [英] Validating and normalizing a partially ordered set

问题描述

我对数组是这样的：

  [A，B]，[B，D]，[A，C]，[E，D ]，[一个，D]，...，[S，F]]
 

1. 什么是有效的方法来检查，如果给定阵列的前preSS偏序？也就是说，有是给定的数组中没有循环像 [A，B]，[B，C]，[C，A] 。

2. 如果可以确认，在阵列前presses偏序，我要通过除去所有能够由自反或传递性衍生的对正常化此。例如，在上述中，由于存在 [一个，B] 和 [B，D] ，这对 [A，D] 是多余的，应当删除。

1和2之间的顺序并不重要。如果2前或1的过程中完成，那么，这很好。

preferably我希望它用Ruby 1.9.3，而只是伪code就足够了。

解决方案

有关问题的第一部分，我来到了我自己的答案这里一个答案的帮助下在数学的网站。

有关问题的第二部分，而对其他的答案中给出的建议后，我实现了在Ruby中（I）的弗洛伊德算法以计算的传递闭包，（ⅱ）组合物，和（iii）用式R传递还原^ - = R - r \ CDOT R 2 +。

 模块有向图; module_function
    DEF顶点图; graph.flatten（1）.uniq结束
    ##弗洛伊德算法
    高清transitive_closure图
        VS =顶点（图）
        PATH = graph.inject（{}）{|路径，E |路径[E] =真;路径}
        vs.each {| K | vs.each {| I | vs.each {|百灵|路径[I，J] || = true，如果路径[I，K]]＆功放;＆安培;路径[K，J]]}}}
        path.keys
    结束
    DEF撰写graph1，graph2
        VS =（顶点（graph1）+顶点（graph2））。uniq的
        PATH1 = graph1.inject（{}）{|路径，E |路径[E] =真;路径}
        路径2 = graph2.inject（{}）{|路径，E |路径[E] =真;路径}
        PATH = {}
        vs.each {| K | vs.each {| I | vs.each {|百灵|路径[I，J] || = true，如果路径1 [I，K]]＆功放;＆安培; PATH2 [[K，J]]}}}
        path.keys
    结束
    高清transitive_reduction图
            图 - 组成（图，transitive_closure（图））
    结束
结束
 

使用示例：

的 Digraph.transitive_closure（[[1,2]，[2，3]，[3，4]]）
＃=＆GT; [[1,2]，[2，3]，[3,4]，[1,3]，[1,4]，[2,4]

Digraph.compose（[[1,2]，[2，3]]，[[2,4]，[3,5]）
＃=＆GT; [[1，4]，[2,5]

Digraph.transitive_reduction（[[1,2]，[2，3]，[3,4]，[1,3]，[1,4]，[2,4]）
＃=＆GT; [[1,2]，[2，3]，[3，4]]
 

I have an array of pairs like this:

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

1. What is an efficient way to check if the given array can express a partial ordering? That is, there is no "loop" in the given array like ["a", "b"], ["b", "c"], ["c", "a"].

2. If it is confirmed that the array expresses a partial order, I want to normalize this by removing all of the pairs that can be derived by reflexivity or transitivity. For example, in the above, since there is ["a", "b"] and ["b", "d"], the pair ["a", "d"] is redundant, and should be removed.

The order between 1 and 2 does not matter. If 2 should be done before or within the process of 1, then, that is fine.

Preferably I want it in Ruby 1.9.3, but just pseudo-code will suffice.

解决方案

For the first part of the question, I came up with my own answer here with the help of an answer at a mathematics site.

For the second part of the question, after following the suggestions given in the other answers, I implemented in Ruby (i) Floyd-Warshall algorithm to calculate the transitive closure, (ii) composition, and (iii) transitive reduction using the formula 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

Usage examples:

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

这篇关于验证和标准化偏序集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！