def predecessor(G, source, target=None, cutoff=None, return_seen=None):
 if (source not in G):
  raise nx.NodeNotFound('Source {} not in G'.format(source))
 level = 0
 nextlevel = [source]
 seen = {source: level}
 pred = {source: []}
 while nextlevel:
  level = (level + 1)
  thislevel = nextlevel
  nextlevel = []
  for v in thislevel:
   for w in G[v]:
    if (w not in seen):
     pred[w] = [v]
     seen[w] = level
     nextlevel.append(w)
    elif (seen[w] == level):
     pred[w].append(v)
  if (cutoff and (cutoff <= level)):
   break
 if (target is not None):
  if return_seen:
   if (not (target in pred)):
    return ([], (-1))
   return (pred[target], seen[target])
  else:
   if (not (target in pred)):
    return []
   return pred[target]
 elif return_seen:
  return (pred, seen)
 else:
  return pred

def predecessor ( G , source , target = None , cutoff = None , return_seen = None ) : if ( source not in G ) : raise nx . NodeNotFound ( 'Source {} not in G' . format ( source ) ) level = 0 nextlevel = [ source ] seen = { source : level } pred = { source : [ ] } while nextlevel : level = ( level + 1 ) thislevel = nextlevel nextlevel = [ ] for v in thislevel : for w in G [ v ] : if ( w not in seen ) : pred [ w ] = [ v ] seen [ w ] = level nextlevel . append ( w ) elif ( seen [ w ] == level ) : pred [ w ] . append ( v ) if ( cutoff and ( cutoff <= level ) ) : break if ( target is not None ) : if return_seen : if ( not ( target in pred ) ) : return ( [ ] , ( - 1 ) ) return ( pred [ target ] , seen [ target ] ) else : if ( not ( target in pred ) ) : return [ ] return pred [ target ] elif return_seen : return ( pred , seen ) else : return pred
returns dictionary of predecessors for the path from source to all nodes in g .