代码之家 › 专栏 › 技术社区 › shantanuo

寻找并发数据之间的关系

graph-databases networkx pandas python

shantanuo · 技术社区 · 6 年前

我有一个看起来像图形数据库的数据框。

import pandas as pd
mycols=['china', 'england', 'france', 'india', 'pakistan', 'taiwan']

df=pd.DataFrame([[0, 0, 0, 3, 0, 0],
       [0, 0, 1, 1, 0, 0],
       [0, 1, 0, 1, 0, 0],
       [3, 1, 1, 0, 1, 0],
       [0, 0, 0, 1, 0, 4],
       [0, 0, 0, 0, 4, 0]], columns=mycols)

df.index=mycols

简化的虚拟数据帧如下所示:

           china    england france  india   pakistan    taiwan
china          0          0      0      3          0    0
england        0          0      1      1          0    0
france         0          1      0      1          0    0
india          3          1      1      0          1    0
pakistan       0          0      0      1          0    4
taiwan         0          0      0      0          4    0

假设一个用户想从中国到印度,有直接的路线。

df[df['china'] > 0].index.str.contains('india')
array([ True])

但没有直达英格兰的路线:

df[df['china'] > 0].index.str.contains('england')
array([False])

在这种情况下,我需要找到共同的国家:

set(df[df.loc['china'] > 0].index.values) & set(df[df.loc['england'] > 0].index.values)
{'india'}

但是有些情况下没有共同的朋友,我需要找到朋友的朋友才能到达目的地。例如

set(df[df.loc['china'] > 0].index.values) & set(df[df.loc['taiwan'] > 0].index.values)

1)在这种情况下,我如何编写一个将返回中国-印度-巴基斯坦-台湾的查询?

2)有没有更好的储存方法?或者类似sql的(行/列)可以吗?

2 回复 | 直到 6 年前

Gambit1614 6 年前

你可以用 Networkx 以如下方式

加载图形

import pandas as pd
import networkx as nx
mycols=['china', 'england', 'france', 'india', 'pakistan', 'taiwan']

df=pd.DataFrame([[0, 0, 0, 3, 0, 0],
   [0, 0, 1, 1, 0, 0],
   [0, 1, 0, 1, 0, 0],
   [3, 1, 1, 0, 1, 0],
   [0, 0, 0, 1, 0, 4],
   [0, 0, 0, 0, 4, 0]], columns=mycols)

#Load the graph from dataframe
G = nx.from_numpy_matrix(df.values)

#set the nodes names
G = nx.relabel_nodes(graph, dict(enumerate(mycols)))

测试图形是否正确加载

print G.edges()
#EdgeView([('pakistan', 'taiwan'), ('pakistan', 'india'), ('england', 'india'), ('england', 'france'), ('india', 'china'), ('india', 'france')])

print graph['china']
#AtlasView({'india': {'weight': 3}})

print graph['england']
#AtlasView({'india': {'weight': 1}, 'france': {'weight': 1}})

现在假设你需要找到 china 到 india

for path in nx.all_simple_paths(graph, source='china', target='taiwan'):
    print path
#Output : ['china', 'india', 'pakistan', 'taiwan']

如果要查找从一个节点到另一个节点的最短路径

for path in nx.all_shortest_paths(graph, source='taiwan', target='india'):
    print path
#Output : ['taiwan', 'pakistan', 'india']

您可以找到其他多种算法来查找短文本路径、全对最短路径、dijsktra算法等。 at their documentation 以满足您的查询

注释可能有一种方法可以使用 from_pandas_dataframe ,但我不确定用例是否正确,因为它需要源和目标

Unni Summer_More_More_Tea 6 年前

你的问题(我假设)基本上是找到加权图中任意两个给定节点之间的最短路径。从算法上讲,这叫做 Shortest path problem (或者更准确地说 单对最短路径问题 )NetworkX 2.1有一个函数 shortest_path 因为你真的这么做了

从他们的例子来看,

G = nx.path_graph(5)
>>> print(nx.shortest_path(G, source=0, target=4))
[0, 1, 2, 3, 4]

如果同时指定了源和目标,则返回从源到目标的最短路径中的节点。

如果要从源获取到所有节点的最短路径,请跳过 target 节点(本质上使其成为 单源最短路径问题 )