给定图(维数未知)中的传递闭包
提问于 2015-11-12 18:39:53
我有一个有向图
a,b,.....,z,a',b'.... c'' 但是我不知道里面有多少元素。它可以用不同的词来表达。例如，它们可以以a-b、b-c、c-d、……的方式连接。
我想添加到这个图传递闭包，它将创建a-c，a-d等之间的连接。
对于任何给定的图，我应该在算法中进行哪些更改才能达到传递闭包。现在，它只适用于包含3个节点的图。我的代码如下。
for x in G:
# Extract all neighbours of neighbours of x (from G)
all_nh = []
for y in G.neighbours(x):
all_nh += G.neighbours(y)
# Remove from the list of neighbors the current node and its immediate neighbors
all_nh = set(all_nh) - set([x]) - set(G.neighbours(x))
# Create new edges (x -> z)
edges = map(lambda z: (x, z), all_nh)
# Add them to the new graph
TC.add_edges_from(edges)好的，我试着实现下面给出的伪代码。但是我仍然需要帮助，因为编译器返回了很多错误。对于ex。TypeError：'NoneType‘类型的对象没有len()
class FlowGraph:
def __init__(self):
self.G=nx.DiGraph()
self.I=[]
self.O=[]
F2=FlowGraph()
#F2.G=nx.Graph()
F2.G.add_node(1)
F2.G.add_node(2)
F2.G.add_node(3)
F2.G.add_node(4)
F2.G.add_edge(1,2)
F2.G.add_edge(2,3)
F2.G.add_edge(3,4)
def transitive_closure(G):
TC = G.copy()
n_nodes = len(G)
#print(n_nodes)
for i in range(n_nodes):
for j in range(n_nodes):
for k in range(n_nodes):
if TC.has_edge(i,k) and TC.has_edge(k,j):
TC.add_edge(i,j)
Z = transitive_closure(F2.G)
nx.draw(Z, with_labels = True)
plt.show()
回答 1
Stack Overflow用户
发布于 2015-11-12 19:01:41
计算传递闭包的最简单方法是使用Floyd-Warshall。设TC是传递闭包图，G是原始闭包图
TC = G # copy all edges from G to TC
for i in range(n_nodes):
for j in range(n_nodes):
for k in range(n_nodes):
if TC.has_edge(i,k) and TC.has_edge(k,j):
TC.add_edge(i,j)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33678867
复制相关文章
点击加载更多
腾讯云开发者
