<s> """<STR_LIT>""" <EOL> import networkx as nx <EOL> __author__ = """<STR_LIT>""" <EOL> __all__ = [ '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' ] <EOL> def floyd_warshall_numpy ( G , nodelist = None , weight = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> try : <EOL> import numpy as np <EOL> except ImportError : <EOL> raise ImportError ( "<STR_LIT>" ) <EOL> A = nx . to_numpy_matrix ( G , nodelist = nodelist , multigraph_weight = min , <EOL> weight = weight , nonedge = np . inf ) <EOL> n , m = A . shape <EOL> I = np . identity ( n ) <EOL> A [ I == <NUM_LIT:1> ] = <NUM_LIT:0> <EOL> for i in range ( n ) : <EOL> A = np . minimum ( A , A [ i , : ] + A [ : , i ] ) <EOL> return A <EOL> def floyd_warshall_predecessor_and_distance ( G , weight = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> from collections import defaultdict <EOL> dist = defaultdict ( lambda : defaultdict ( lambda : float ( '<STR_LIT>' ) ) ) <EOL> for u in G : <EOL> dist [ u ] [ u ] = <NUM_LIT:0> <EOL> pred = defaultdict ( dict ) <EOL> undirected = not G . is_directed ( ) <EOL> for u , v , d in G . edges ( data = True ) : <EOL> e_weight = d . get ( weight , <NUM_LIT:1.0> ) <EOL> dist [ u ] [ v ] = min ( e_weight , dist [ u ] [ v ] ) <EOL> pred [ u ] [ v ] = u <EOL> if undirected : <EOL> dist [ v ] [ u ] = min ( e_weight , dist [ v ] [ u ] ) <EOL> pred [ v ] [ u ] = v <EOL> for w in G : <EOL> for u in G : <EOL> for v in G : <EOL> if dist [ u ] [ v ] > dist [ u ] [ w ] + dist [ w ] [ v ] : <EOL> dist [ u ] [ v ] = dist [ u ] [ w ] + dist [ w ] [ v ] <EOL> pred [ u ] [ v ] = pred [ w ] [ v ] <EOL> return dict ( pred ) , dict ( dist ) <EOL> def floyd_warshall ( G , weight = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> return floyd_warshall_predecessor_and_distance ( G , weight = weight ) [ <NUM_LIT:1> ] <EOL> def setup_module ( module ) : <EOL> from nose import SkipTest <EOL> try : <EOL> import numpy <EOL> except : <EOL> raise SkipTest ( "<STR_LIT>" ) </s>
