在python中查找加权图中所有负圈和正圈的代码？
在python中查找加权图中所有负圈和正圈的代码？
提问于 2016-03-11 00:44:17
我是python的新手，我正在处理复杂的网络。我想找出一个图中所有的负圈和正圈，并找出参与构成圈(正圈或负圈)的边的权重。有人能帮我这个忙吗？例如：
nodes:[1,2,3,4,5]
edges:[(1,2,w=1),(1,4,w=4),(2,3,w=2),(3,1,w=2),(3,5,w=1),(4,5,w=2),
(5,4,w=7),(4,3,w=-6),(5,1,w=3)]
cycles:[(1-2-3-1,sum=1),(1-4-3-1,sum=0)....etc]回答 1
Stack Overflow用户
发布于 2016-03-11 01:45:36
使用节点、边和边属性创建DiGraph：
nodes = [1,2,3,4,5]
edges = edges = [(1,2,{'w': 1}), (1,4,{'w': 4}), (2,3,{'w':2}), (3,1,{'w': 2}), (3,5,{'w': 1}), (4,5,{'w':2}), (5,4,{'w': 7}), (4,3,{'w': -6}), (5,1,{'w': 3})]
G = nx.DiGraph()
G.add_nodes_from(nodes)
G.add_edges_from(edges)查找循环并计算它们的权重：
>>> cycles = nx.simple_cycles(G)
>>> weights = nx.get_edge_attributes(dgraph, 'w')
>>> for cycle in cycles:
cycle.append(cycle[0])
sumw = sum([weights[(cycle[i-1], cycle[i])] for i in range(1, len(cycle))])
print cycle, sumw
[1, 4, 5, 1] 9
[1, 4, 3, 5, 1] 2
[1, 4, 3, 1] 0
[1, 2, 3, 5, 1] 7
[1, 2, 3, 1] 5
[3, 5, 4, 3] 2
[4, 5, 4] 9页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/35922369
复制相关文章
相似问题
腾讯云开发者
