我正在尝试在Python中执行有向图的传递约简

作为警告，我对 python 仍然有点缺乏经验

我正在尝试使用 networkx 库执行有向图的传递约简。我已经想出了一个算法，但在实现它时遇到了困难。经过快速搜索，我在其他堆栈交换问题中找到了与我类似的算法，但没有演示如何实际编码该算法。

这是我的算法：

    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

这是我用 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)

我认为我没有正确调用网络中边的每个排列，并且正在考虑尝试使用 itertools。即使我有所有可能的排列，我也不知道如何使用这些信息来实现算法。

任何帮助都会很棒。谢谢！

以下似乎有效，至少对于我提供的示例数据而言。如果您有一个具体的案例，但没有看到它会很有帮助。

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