首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >在python中查找加权图中所有负圈和正圈的代码?

在python中查找加权图中所有负圈和正圈的代码?
EN

Stack Overflow用户
提问于 2016-03-11 00:44:17
回答 1查看 996关注 0票数 0

我是python的新手,我正在处理复杂的网络。我想找出一个图中所有的负圈和正圈,并找出参与构成圈(正圈或负圈)的边的权重。有人能帮我这个忙吗?例如:

代码语言:javascript
运行
复制
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]
EN

回答 1

Stack Overflow用户

发布于 2016-03-11 01:45:36

使用节点、边和边属性创建DiGraph:

代码语言:javascript
运行
复制
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)

查找循环并计算它们的权重:

代码语言:javascript
运行
复制
>>> 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
票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/35922369

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档