python - Networkx:随机遍历有向图
问题描述
我有一个带加权边的有向图。每个节点都连接到其他每个节点,权重表示从节点 X 移动到节点 Y 的可能性(每个节点的权重总和 = 1 - 这是一个随机矩阵)。
我需要创建一个随机遍历图形的函数,每个节点只进出一次,返回起点
我不想返回最有可能的输出,只是第一次随机遍历树,它只命中每个节点一次并返回它所走的路径,以及每次跳跃的可能性。
这是我正在寻找的一个简单实现:
import pandas as pd
import numpy as np
from numpy.random import choice
import networkx as nx
testData = [('A','B',.5),('A','C',.4),('A','D',.1),('B','A',.5),('B','C',.3),('B','D',.2),('C','A',.3),('C','B',.1),
('C','D',.6),('D','A',.35),('D','B',.15),('D','C',.5)]
G = nx.DiGraph()
G.add_weighted_edges_from(testData)
#traverse g from randomly selected starting node to every other node randomly and back to random start node
def randomWalk(g):
start_node = choice(G.nodes())
#dfs implementation available?
return pathTaken
print (randomWalk(G))
>>> [('C','A',.3),('A':'D',.1),('D':'B',.15),('B':'C',.3)]
我找不到将随机游走组件合并到任何可用遍历算法的方法。
关于我可以使用的可用实现的任何想法?如果可以避免的话,我宁愿不编写自定义 DFS ......
谢谢!
解决方案
我最终做的是在使用节点时删除它们,然后将最后一个节点分配给第一个节点。在每一步,我都会重新加权以获得 100% 的可能性。我敢肯定这不是超级有效,但我的图表很小,所以没关系。然后我合并了每个项目最后发生的可能性。
matchedPath = []
currNode = choice(G.nodes())
firstNode = currNode
while G.number_of_nodes() >1:
connectNodes = [x[1] for x in G.out_edges(currNode,data = True)]
connectWeights = [x[2]['weight'] for x in G.out_edges(currNode,data = True)]
remainingWeights = [z/sum(connectWeights) for z in connectWeights]
nextNode = choice(connectNodes, 1, p=remainingWeights)[0]
matchedPath.append((currNode,nextNode))
G.remove_node(currNode)
currNode = nextNode
matchedPath.append((currNode,firstNode))
matched_df = pd.DataFrame(matchedPath,columns = ['from','to'])
matched_df = pd.merge(matched_df,rawData,how = 'outer',left_on =['from'],right_on = ['Name']).drop(['Name'],axis = 1)
matched_df = pd.merge(matched_df,link_df,how = 'left',left_on = ['from','to'],right_on = ['person_x','person_y']).drop(['person_x','person_y'],axis = 1)
推荐阅读
- javascript - 如何在 mongodb 聚合中展开嵌套对象数组?
- ios - ScrollView 不会让我快速滚动 StackView
- exist-db - 如何使用letsencrypt CA签名证书在Jetty中为exist-db配置SSL
- google-cloud-dataflow - 现在在 apache Beam 中默认启用 Shuffle 服务?
- c# - 实体核心中的一对多关系删除子表中的先前记录作为父子更新的一部分
- c# - SSIS 脚本任务未在 SSDT 外部执行
- c# - Log4Net 错误:log4net 中基于文件的登录不起作用
- python - statsmodels.graphics.tsaplots 绘图问题(jupyter)
- linux-kernel - 支持 SCO over PCM
- postgresql - 通过 Docker 的 Liquibase - 更改日志未写入磁盘