-1

我有一个找到传递闭包的 Python 代码。

例子：

输入：{('A','B'),('B','C'),('C','D'),('E','F')}

输出： {('B', 'C'), ('A', 'D') , ('A', 'B'), ('C', 'D'), ('B', 'D' ') , ('E', 'F'), ('A', 'C') }

该代码完美无缺，但我正在寻找的是将输出作为一组子图。我是 Python 的初学者，我不知道该怎么做。

根据给定的输入，这是我正在寻找的输出，它在集合中有两个元素，每个元素代表传递闭包输出的一个子图：{(A, B, C, D), (E, F) }

这是代码：

from collections import defaultdict

def transitive_closure(elements):
    edges = defaultdict(set)
    # map from first element of input tuples to "reachable" second elements
    for x, y in elements: edges[x].add(y)

    for _ in range(len(elements) - 1):
        edges = defaultdict(set, (
                                  (k, v.union(*(edges[i] for i in v)))
                                  for (k, v) in edges.items()
                                  ))

    return set((k, i) for (k, v) in edges.items() for i in v)

result = set(transitive_closure([('A','B'),('B','C'),('C','D'),('E','F')]))
print result
4

1 回答 1

1

在 Python 中使用networkx解决了问题。networkx提供了查找给定子图的所有子图的功能。

我所需要做的就是获得transitive_closure()方法的输出，将其转换为networkx 的图，然后将新创建的图作为networkx 提供的connected_component_subgraphs()方法的输入。

H=nx.connected_component_subgraphs(G)

H 是一个包含所有需要的子图的集合。

主要缺点是处理时间，但这是我能找到的最好的。

于 2012-12-23T23:54:38.327 回答