pythonlistgraph-theorytransitive-closure

Transitive reduction - Error with code - Python

So I am trying to write a code to do transitive reduction of Acyclic graph. So the elements are:

(3, 5), (5, 2), (2, 1), (4, 2), (3, 1), (4, 1)

This is what I have written so far: 

graph = [[3, 5],[5, 2],[2, 1],[4, 2],[3, 1],[4, 1]]

for i in range(len(graph)):
    for j in range(len(graph)):
        for k in range(len(graph)):
            if [i,j] in graph and [j,k] in graph:
                a = [i,k]
                graph.pop(a)
print(graph)

After running I am expecting to get the following with (4,1) removed:

>> (3, 5), (5, 2), (2, 1), (4, 2), (3, 1)

But instead it returns:

>> (3, 5), (5, 2), (2, 1), (4, 2), (3, 1), (4, 1)

I cant figure out what I am doing wrong. If someone can point out the error, it would be great!

P.S: Transtive reduction is removing the redundant edges of a graph. For example:

if ( A -> B ) and ( B -> C ), then ( A -> C ), in other words: if A is connected to B and B is connected to C, then A is also connected to C. And in this case ( A -> C ) is redundant because A can reach C through B therefore should be removed.

Solution

  • I improved your code, I added a condition if a in graph: because in some cases the Transtive reduction appears and the element [i,k] doesn't exist. Also the function pop() removes an element by index, not by object like remove().

    graph = [[3, 5],[5, 2],[2, 1],[4, 2],[3, 1],[4, 1]]

for i in range(len(graph)):
    for j in range(len(graph)):
        for k in range(len(graph)):
            if [i,j] in graph and [j,k] in graph:
                a = [i,k]
                if a in graph:
                    graph.remove(a)
print(graph)

    I hope this can help you.