I’m trying to perform the transitive reduction of directed graph in Python

As a warning, I’m still a bit inexperienced in python

I’m trying to perform the transitive reduction of directed graph using the networkx library. I’ve figured out an algorithm but I’m having trouble implementing it. After a quick search, I found algorithms similar to mine in other stack exchange questions but no demonstrations of how to actually code the algorithm.

Here’s my algorthm:

    For X in Nodes
    For Y in Nodes
    For z in Nodes
    if (x,y) != (y,z) and (x,y) != (x,z)
    if edges xy and yz are in Graph
    delete xz

Here’s my attempt at expressing this in python :

    G = graph
    N = G.Nodes()
    for  x in N:
       for y in N:
          for z in N:
             if (x,y) != (y,z) and (x,y) != (x,z):
                if (x,y) and (y,z) in G:
                    G.remove_edge(x,z)

I don’t think I’m properly calling every permutation of edges in the network and was thinking of trying to use itertools. Even if I had every possible permutation, I don’t know how to implement the algorithm with that information.

Any help would be wonderful. Thanks!

Answer

The following seems to work, at least for the sample data I provided. If you have a specific case that doesn’t it’d be helpful to see it.

import random
import pprint

class Graph:
    nodes = []
    edges = []
    removed_edges = []
    def remove_edge(self,x,y):
        e = (x,y)
        try:
            self.edges.remove(e)
            print("Removed edge %s" % str(e))
            self.removed_edges.append(e)
        except:
            print("Attempted to remove edge %s, but it wasn't there" % str(e))

    def Nodes(self):
        return self.nodes

    # Sample data
    def __init__(self):
        self.nodes = [1,2,3,4,5]
        self.edges = [
            (1,2),
            (1,3),
            (1,4),
            (1,5),
            (2,4),
            (3,4),
            (3,5),
            (4,5),
        ]

G = Graph()
N = G.Nodes()
for  x in N:
   for y in N:
      for z in N:
         #print("(%d,%d,%d)" % (x,y,z))
         if (x,y) != (y,z) and (x,y) != (x,z):
            if (x,y) in G.edges and (y,z) in G.edges:
                G.remove_edge(x,z)

print("Removed edges:")
pprint.pprint(G.removed_edges)
print("Remaining edges:")
pprint.pprint(G.edges)

Output:

Removed edge (1, 4)
Attempted to remove edge (1, 4), but it wasn't there
Removed edge (1, 5)
Attempted to remove edge (2, 5), but it wasn't there
Removed edge (3, 5)
Removed edges:
[(1, 4), (1, 5), (3, 5)]
Remaining edges:
[(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]