Networkx:计算并存储到 pandas 数据框的图形上的最短路径 [英] Networkx: Calculating and storing shortest paths on a graph to a Pandas Data frame

问题描述

我有一个熊猫数据框，如下所示.该框架中还有许多与任务无关紧要的列. id列显示句子ID，而e1和e2列包含句子的实体(=单词)及其在r

I have a pandas dataframe as shown below. There are many more columns in that frame that are not important concerning the task. The column id shows the sentenceID while the columns e1 and e2 contain entities (=words) of the sentence with their relationship in the column r

id     e1        e2          r
10     a-5       b-17        A 
10     b-17      a-5         N
17     c-1       a-23        N
17     a-23      c-1         N
17     d-30      g-2         N
17     g-20      d-30        B

我还为每个句子创建了一个图表.该图是从看起来像这样

I also created a graph for each sentence. The graph is created from a list of edges that looks somewhat like this

[('wordB-5', 'wordA-1'), ('wordC-8', 'wordA-1'), ...]

所有这些边都在一个列表中.该列表中的每个元素都包含每个句子的所有边.含义list[0]具有句子0的边缘，依此类推.

All of those edges are in one list (of lists). Each element in that list contains all the edges of each sentence. Meaning list[0] has the edges of sentence 0 and so on.

现在我要执行以下操作:

Now I want to perform operations like these:

graph = nx.Graph(graph_edges[i])
shortest_path = nx.shortest_path(graph, source="e1", 
target="e2")
result_length = len(shortest_path)
result_path = shortest_path

对于数据帧中的每一行，我想计算最短路径(从e1中的实体到e2中的实体，并将所有结果保存在DataFrame中的新列中，但是不知道该怎么做.

For each row in the data frame, I'd like to calculate the shortest paths (from the entity in e1 to the entity in e2 and save all of the results in a new column in the DataFrame but I have no idea how to do that.

我尝试使用此类构造

e1 = DF["e1"].tolist()
e2 = DF["e2"].tolist()
for id in Df["sentenceID"]:
    graph = nx.Graph(graph_edges[id])
    shortest_path = nx.shortest_path(graph,source=e1, target=e2)
result_length = len(shortest_path)
result_path = shortest_path

创建数据，但表示目标不在图中.

to create the data but it says the target is not in the graph.

new df=

id     e1        e2          r     length     path
10     a-5       b-17        A       4         ..
10     b-17      a-5         N       4         ..
17     c-1       a-23        N       3         ..
17     a-23      c-1         N       3         ..
17     d-30      g-2         N       7         ..
17     g-20      d-30        B       7         ..

推荐答案

对于对解决方案感兴趣的任何人(感谢

For anyone that's interested in the solution (thanks to Ram Narasimhan) :

 pathlist, len_list = [], []
 so, tar = DF["e1"].tolist(), DF["e2"].tolist()
 id = DF["id"].tolist()

 for _,s,t in zip(id, so, tar):
     graph = nx.Graph(graph_edges[_]) #Constructing each Graph
     try:
         path = nx.shortest_path(graph, source=s, target=t)
         length = nx.shortest_path_length(graph,source=s, target=t)
         pathlist.append(path)
         len_list.append(length)
     except nx.NetworkXNoPath:
         path = "No Path"
         length = "No Pathlength"
         pathlist.append(path)
         len_list.append(length)

 #Add these lists as new columns in the DF
 DF['length'] = len_list
 DF['path'] = pathlist

这篇关于Networkx:计算并存储到 pandas 数据框的图形上的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！