首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >Networkx:随机遍历有向图

问Networkx:随机遍历有向图
EN

Stack Overflow用户
提问于 2018-11-20 00:59:48
回答 2查看 1.2K关注 0票数 1

我有一个带权重边的有向图。每个节点都连接到每个其他节点,并且权重表示从节点X移动到节点Y的可能性(每个节点的权重总和out =1-这是一个随机矩阵)。

我需要创建一个函数,它随机遍历图,并且只进出每个节点一次,返回到起始点

我不想返回最可能的输出,只想返回第一次随机遍历树,该树只命中每个节点一次,并返回它所采用的路径,以及它所采用的每一次跳跃的可能性。

下面是我正在寻找的一个简单的实现:

代码语言:javascript
复制
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文件系统。

谢谢!

EN

回答 2

Stack Overflow用户

发布于 2018-11-20 18:48:21

我不知道您是否会认为这是一个可用的实现,但这是:

代码语言:javascript
复制
random.sample(G.nodes(), len(G.nodes()))

将为您的问题返回一个随机有效的路径,因为该图是强连接的。

然后,您需要处理结果以获得元组列表:

代码语言:javascript
复制
def random_walk(G):
    path = random.sample(G.nodes(), len(G.nodes()))
    return [(path[i-1], node, G[path[i-1]][node]['weight']) for i, node in enumerate(path)]

在您的示例中:

代码语言:javascript
复制
print(random_walk(G))
>>> [('B', 'C', 0.3), ('C', 'D', 0.6), ('D', 'A', 0.35), ('A', 'B', 0.5)]
票数 0
EN

Stack Overflow用户

发布于 2018-11-20 23:13:11

我最终做的是在使用节点时将其删除,然后将最后一个节点分配给第一个节点。在每一步,我都会重新加权,以获得100%的可能性。我确信这不是非常有效,但是我的图很小,所以它是可以的。然后我合并了每一项在结束时发生的可能性。

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

https://stackoverflow.com/questions/53379409

复制
相关文章

相似问题

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