@not_implemented_for('undirected')
def dag_longest_path(G, weight='weight', default_weight=1):
 dist = {}
 for v in nx.topological_sort(G):
  us = [((dist[u][0] + data.get(weight, default_weight)), u) for (u, data) in G.pred[v].items()]
  maxu = (max(us, key=(lambda x: x[0])) if us else (0, v))
  dist[v] = (maxu if (maxu[0] >= 0) else (0, v))
 u = None
 v = max(dist, key=(lambda x: dist[x][0]))
 path = []
 while (u != v):
  path.append(v)
  u = v
  v = dist[v][1]
 path.reverse()
 return path

@ not_implemented_for ( 'undirected' ) def dag_longest_path ( G , weight = 'weight' , default_weight = 1 ) : dist = { } for v in nx . topological_sort ( G ) : us = [ ( ( dist [ u ] [ 0 ] + data . get ( weight , default_weight ) ) , u ) for ( u , data ) in G . pred [ v ] . items ( ) ] maxu = ( max ( us , key = ( lambda x : x [ 0 ] ) ) if us else ( 0 , v ) ) dist [ v ] = ( maxu if ( maxu [ 0 ] >= 0 ) else ( 0 , v ) ) u = None v = max ( dist , key = ( lambda x : dist [ x ] [ 0 ] ) ) path = [ ] while ( u != v ) : path . append ( v ) u = v v = dist [ v ] [ 1 ] path . reverse ( ) return path
returns the longest path in a dag if g has edges with weight attribute the edge data are used as weight values .