寻找熊猫数据帧中两点之间平均边缘值最高的路径的有效方法？

Question

请原谅这个问题看似混乱的措辞。这是我想做的。

给定数据帧df

Fruit1     Fruit2      Weight
orange     apple       0.2
orange     grape       0.4
orange     pineapple   0.6
orange     banana      0.8
apple      grape       0.9
apple      pineapple   0.3
apple      banana      0.2
grape      pineapple   0.1
pineapple  banana      0.8

以及对允许的最大路径长度L的约束

我希望返回一个具有最高平均路径的数据帧（即点之间的所有边的总和/路径长度最大），其中一个边由权重列表示，假设它不超过长度L。

用一个例子来说明我所说的最高平均路径：

假设我们只有4点A，B，C

最高的平均路径是max（（A-

对于L=2，它将是最大值（（A-

对于df，对于L=2，我们会得到

Fruit1     Fruit2      Weight   MaxAvgPath(L=2)
orange     apple       0.2       [orange, grape, apple]  
orange     grape       0.4       [orange, apple, grape]
orange     pineapple   0.6       [orange, banana, pineapple]
orange     banana      0.8       [orange, banana]
apple      grape       0.9       [apple, grape]
apple      pineapple   0.3       [apple, grape, pineapple]
apple      banana      0.2       [apple, pineapple, banana] 
grape      pineapple   0.1       [grape, orange, pineapple]
grape      banana      0.1       [grape, apple, banana]
pineapple  banana      0.8       [pineapple, banana]

注意：这个边缘集包含的行刚好够代表整个网络。例如，当（橙色，苹果）存在时，（苹果，橙色）不存在，因为（苹果，橙色）的重量是相同的。然而，如果包含那些有助于创建解决方案，请随意使用它们，并在最终输出中忽略它们。镜像对的返回路径应等于原始对的返回路径。

Answer 1

感谢您的澄清，因此您需要在图形中的每对节点之间具有最高成本/（边数）的路径，其中路径限制为连接边的上限。最长路径问题是np难问题，因此只有在有限制的情况下才能有效解决（请参见https://en.wikipedia.org/wiki/Longest_path_problem).我认为你对边缘连接的限制人为地强制了一条长度为L的最长路径，因此可以将它降到指数级。

networkx模块可以通过深度优先搜索来寻找简单的路径，我们可以通过手动求和和排序来对路径进行排名。我们可以对每对节点都这样做，并将其作为一个新系列添加到数据帧中。

import pandas
import networkx

# Create a graph from the dataframe
G = networkx.from_pandas_dataframe(path_frame, 'Fruit1', 'Fruit2', 'Weight')

# Find the longest path between source and target up to length L
def maxpath_cond(G, source, target, edge_attr, L=None):
    #Use networkx simple paths function which uses a depth first search
    paths = networkx.simple_paths.all_simple_paths(G,source, target, L)
    # Calculate and sort the costs of the path
    costs = [(pathcost(G, pth, edge_attr), pth) for pth in paths]
    return sorted(costs, key=lambda x:x[0], reverse=True)

def pathcost(G,path, edge_attr):
    lp = len(path)-1
    return sum(G[path[n]][path[n+1]][edge_attr] for n in range(lp))/lp
#Iterate through the dataframe and create a new series made up of long paths
mxs = []
for n in range(len(path_frame)):
    src, targ = path_frame.loc[n]['Fruit1'], path_frame.loc[n]['Fruit2']
    mxl = maxpath_cond(G, src, targ, 'Weight', 2)[0]
    mxs.append( mxl[1])

print(path_frame.assign(MaxAvgPath=mxs))

哪些产出：

      Fruit1     Fruit2  Weight                   MaxAvgPath
0     orange      apple     0.2       [orange, grape, apple]
1     orange      grape     0.4       [orange, apple, grape]
2     orange  pineapple     0.6  [orange, banana, pineapple]
3     orange     banana     0.8             [orange, banana]
4      apple      grape     0.9               [apple, grape]
5      apple  pineapple     0.3    [apple, grape, pineapple]
6      apple     banana     0.2   [apple, pineapple, banana]
7      grape  pineapple     0.1    [grape, apple, pineapple]
8  pineapple     banana     0.8          [pineapple, banana]