传递闭包

Question

我想在 python 中创建一个 TransitiveClosure() 函数，它可以输入一个字典并输出一个新的传递闭包字典。

例如 R = {1: [3], 2: [4], 3: [], 4: [1]} 将输出 R R = {1 : [3], 2 : [1, 3, 4], 3 : [], 4 : [1, 3]}.

我知道传递属性是 a->b，b->c 而不是 a->c。

我不能使用矩阵和实际点，因为我需要创建一个新字典。我试过将字典转换为包含集合的列表，但这也有它的问题。有人能帮忙吗？

谢谢！

def transitiveClosure(r):
  d ={}
  R = list(r.items())
    # loop for a,b
  for a, b in R:
    #loop for c, d
    for c, d in R:
      # checks if b = c and if a, d are in R
      if b == c and ((a, d) not in R):
        print("Not Transitive")
        return False
  print("is Transitive")
  return True

这会告诉我字典是否可传递，我很难尝试使用此逻辑创建新字典。由于我将输入字典转换为集合列表，我是否需要将元素添加到列表中然后将其转换回字典？

Answer 1

我可以想到以下使用递归函数的解决方案

def reachable_items(R,k):
    ans = R[k]
    if ans != []:
        for v in ans:
            ans = ans + reachable_items(R,v)
    return ans
    
def transitive_closure(R):
    ans = dict()
    for k in R.keys():
        ans[k] = reachable_items(R,k)
    return ans

示例：

>>> R1 = {1: [3], 2: [4], 3: [], 4: [1]}
>>> transitive_closure(R1)
{1: [3], 2: [4, 1, 3], 3: [], 4: [1, 3]}

>>> R2 = {1:[2],2:[],3:[4,5],4:[1],5:[]}
>>> transitive_closure(R2)
{1: [2], 2: [], 3: [4, 5, 1, 2], 4: [1, 2], 5: []}

传递闭包

Transitive closure

python

dictionary

function

discrete-mathematics

transitive-closure