4

作为警告，我对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。即使我有所有可能的排列，我也不知道如何使用该信息实现算法。

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

4

4 回答 4

3

以下似乎有效，至少对于我提供的示例数据。如果您有一个特定的案例，那么查看它会很有帮助。

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)]
于 2013-06-13T04:03:46.763 回答
3

如果我正确阅读了tred实用程序的源代码（它计算了作为 graphviz 实用程序的一部分的点 fromat 中的图形的传递缩减），那么它使用的算法如下：遍历图形的所有顶点和每个顶点，对它的每个孩子做一个 DFS。对于以这种方式遍历的每个顶点，删除从原始父顶点到该顶点的任何边。

我使用networkx实现了该算法，如下所示：

g = nx.read_graphml("input.dot")
for n1 in g.nodes_iter():
    if g.has_edge(n1, n1):
        g.remove_edge(n1, n1)
    for n2 in g.successors(n1):
        for n3 in g.successors(n2):
            for n4 in nx.dfs_preorder_nodes(g, n3):
                if g.has_edge(n1, n4):
                    g.remove_edge(n1, n4)    
nx.write_graphml(g, "output.dot")

嵌套级别暗示了一个可怕的复杂性，但它实际上已经执行了 DFS 的前两个步骤，这将在稍后执行。这样做可以避免在 DFS 部分检查当前节点是否是父节点的直接后继节点（因为 networkx 的 DFS 结果包括开始遍历的顶点）。因此，另一种公式如下，它可以更好地显示该算法的复杂性，但由于在最内部的 looptgoo 中进行了额外检查，因此速度也稍微慢了一点：

g = nx.read_graphml("input.dot")
for n1 in g.nodes_iter():
    c = set(g.successors(n1))
    for n2 in nx.dfs_preorder_nodes(g, n1):
        if n2 in c:
            continue
        if g.has_edge(n1, n2):
            g.remove_edge(n1, n2)    
nx.write_graphml(g, "output.dot")

操作has_edge和remove_edge使用 Python 字典，因此是O(1)平均的。DFS 的最坏情况时间复杂度是图O(E)中E的边数。由于 DFS 执行N次数（N即顶点数），因此上述算法的时间复杂度为O(NE).

另一个有趣的观察是，上面的 Python 代码似乎比tredgraphviz 套件中的实用程序快几个数量级。我不知道为什么会这样。以下是具有 482 个顶点和 9656 个边的非循环图的运行时间比较：

  • tred：58.218 秒
  • 蟒蛇：4.720 秒

我还在一个有 14956 个顶点和 190993 个边的图上尝试了另一个基准测试，但是虽然上面的 Python 代码在 11 分钟内完成，但在tred撰写本文时，在 2 小时的运行时间后仍在运行。

编辑：7 天零 3 小时后，tred仍然在该图表上翻腾。我现在要放弃了。

于 2015-05-31T06:57:04.087 回答
1 
if (x,y) and (y,z) in G:

这需要写成：

if (x,y) in G and (y,z) in G:
于 2013-06-13T03:26:18.277 回答
0

同时，传递归约是内置的networkx。

import networkx as nx
G = nx.DiGraph()
G.add_edges_from([(0,1),(0,2),(0,3),(0,4),(1,2),(1,4),(1,4),(3,4)])
H = nx.transitive_reduction(G)
print(H.edges)
# [(0, 1), (0, 3), (1, 2), (1, 4), (3, 4)]
于 2020-08-15T18:57:28.387 回答