exact_path_len.py

gistfile1.py

from functools import reduce

def psum(G, P):
  if len(P) > 1:
    elist = list(zip(P,P[1:]))
    return reduce(lambda x, y: x+y, [G.edges[e]['length'] for e in elist])
  return 0

def exactpath(G,S,D,T,eps,sp_memo,curpath=[], pc=[], lc=[]):
  if T < 0:
    return
  
  if S==D:
    if T < eps:
      pc.append(curpath)
      lc.append(psum(G,curpath))
      return
    else:
      return
  
  sp = []
  if (S,D) in sp_memo:
    plen = sp_memo[(S,D)]
  else:
    sp = nx.shortest_path(G,S,D,weight='length')
    if sp:
      plen = psum(G, sp)
      sp_memo[(S,D)] = plen
    else:
      return
  
  if plen > T+eps:
    return

  if plen > T-eps and plen < T+eps:
    if not sp:
      sp = nx.shortest_path(G,S,D,weight='length')
    curpath.extend(sp)
    #print(curpath)
    #print("len={}".format(psum(G,curpath)))
    pc.append(curpath)
    lc.append(psum(G,curpath))
    return
  
  for n in G.neighbors(S):
    if n not in curpath:
      curp = curpath.copy()
      curp.append(S)
      exactpath(G,n,D,T-g.edges[(S,n)]['length'],eps,sp_memo,curpath=curp,pc=pc,lc=lc)