计算节点最长路径时如何限制节点数？

Question

在DAG中，我计算了两个有权重的节点之间的最长路径。

nx.dag_longest_path_length(G7, weight='weight')

它returns663.6671428571427，但最长的路径会抛出很多节点。在我正在进行的项目中，我需要找到最多只访问三个节点的最长路径权重。能找到吗？

Answer 1

这里有一种方法可以做你想做的事。您可以计算从每个节点开始的大小为 3 的节点的所有可能路径。我通过使用描述的 findPaths 函数来做到这一点。然后，您可以对每条路径中的边的权重求和，并通过返回最大值来找到最长的路径。

参见下面关于 karate club graph to which I added random weights 的示例：

import networkx as nx
import random
import numpy as np

random.seed(0)

#usoing Karate club graph as an example
G = nx.karate_club_graph()

#Computing random weights for this graph
for (u, v) in G.edges():
    G.edges[u,v]['weight'] = random.randint(0,10)

#Plotting graphs and weights for reference
labels = nx.get_edge_attributes(G,'weight')
pos=nx.circular_layout(G)
nx.draw(G,pos=pos, with_labels=True)
nx.draw_networkx_edge_labels(G,pos=pos,edge_labels=labels)

#Function to find all possible path of size n from node u   
def findPaths(G,u,n):
    if n==0:
        return [[u]]
    paths = [[u]+path for neighbor in G.neighbors(u) for path in findPaths(G,neighbor,n-1) if u not in path]
    return paths

#Function to compute the some of weights for each path in path_list
def sum_weights_path(G,path_list):
  sum_weights=[]
  for i in range(len(path_list)):
    temp=0
    for j in range(len(path_list[i])-1):
      temp+=G.edges[path_list[i][j],path_list[i][j+1]]['weight']
    sum_weights.append(temp)
  return sum_weights

len_path=2
N_nodes=G.number_of_nodes()
paths_list=[[] for i in range(N_nodes)]
weights_paths_list=[[] for i in range(N_nodes)]

#Find max value and index of paths weights max value for each nodes
for node,i in zip(G.nodes,range(N_nodes)):
  temp=findPaths(G,node,len_path)
  paths_list[i].append(temp)
  weights_paths_list[i].append(sum_weights_path(G,temp))

ind_max_val=[]
max_val=[]
#Compute overall max path weights across nodes and return index
for i in range(N_nodes):
  ind_max_val.append(np.argmax(weights_paths_list[i]))
  max_val.append(np.amax(weights_paths_list[i]))


overall_max=np.amax(max_val)
ind_overall_max=np.argmax(max_val)
longest_path=paths_list[ind_overall_max][0][ind_max_val[ind_overall_max]]

#print max value and path
print('Max path sum of weights:'+str(overall_max))
print('longest_path: '+str(longest_path))

并且输出给出：

Max path sum of weights:20
longest_path: [32, 14, 33]

计算节点最长路径时如何限制节点数？

How can I limit the number of nodes when calculating node longest path?

python

graph

nodes

networkx

directed-acyclic-graphs