I want to create a TransitiveClosure() function in python that can input a dictionary and output a new dictionary of the transitive closure.
for example R = {1: [3], 2: [4], 3: [], 4: [1]}
will output R R = {1 : [3], 2 : [1, 3, 4], 3 : [], 4 : [1, 3]}
.
I know the transitive property is a->b
, b->c
than a->c
.
I can't use a matrix and actually point as I need to create a new dictionary. I've tried converting the dictionary to a list to contain sets but that also has its problems. Could anyone help?
Thank You!
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
this will tell me if a dictionary is transitive, I'm having a hard time trying to create a new dictionary using this logic. since I converted the input dictionary into a list of sets do i need to add the elements to a list then convert that back to a dictionary?
CodePudding user response:
I can think of the following solution using a recursive function
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
Examples:
>>> 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: []}