我正在尝试在Python中执行有向图的可传递约简 [英] I'm trying to perform the transitive reduction of directed graph in Python

问题描述

作为警告，我对python还是没有经验

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

我正在尝试使用networkx库执行有向图的可传递约简.我已经找到一种算法，但是在实现它时遇到了麻烦.快速搜索之后，我在其他堆栈交换问题中发现了与我的算法相似的算法，但未演示如何实际编码该算法.

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.

这是我的算法:

    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中表达的内容:

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)

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

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!

推荐答案

以下内容似乎有效，至少对于我提供的示例数据而言.如果您遇到的情况不是这样，那么对您有所帮助.

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)

输出:

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

这篇关于我正在尝试在Python中执行有向图的可传递约简的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！