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

In a DAG, I calculate the longest path between two nodes with weights.

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

It returns 663.6671428571427, but the longest path goes throw many nodes. In the project which I'm working on, I need to find the longest path weight only visiting a maximum of three nodes. Is it possible to find it?

Solution 1:

Here is a way to do what you want. You can compute all possible path of size 3 nodes starting from each node. I did that by using the findPaths function described here. You can then sum the weights of the edges in each path and find the longest path by returning the max value.

See example below on the 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))

And the output gives:

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