<jupyter_start><jupyter_text>**Floyd–Warshall Algorithm**This code is used to implement the Floyd–Warshall Algorithm.  <NAME> (lin.3326 at osu.edu)  Created: 5/30/2020<jupyter_code>from google.colab import drive
drive.mount('/content/gdrive')<jupyter_output>Go to this URL in a browser: https://accounts.google.com/o/oauth2/auth?client_id=947318989803-6bn6qk8qdgf4n4g3pfee6491hc0brc4i.apps.googleusercontent.com&redirect_uri=urn%3aietf%3awg%3aoauth%3a2.0%3aoob&response_type=code&scope=email%20https%3a%2f%2fwww.googleapis.com%2fauth%2fdocs.test%20https%3a%2f%2fwww.googleapis.com%2fauth%2fdrive%20https%3a%2f%2fwww.googleapis.com%2fauth%2fdrive.photos.readonly%20https%3a%2f%2fwww.googleapis.com%2fauth%2fpeopleapi.readonly

Enter your authorization code:
··········
Mounted at /content/gdrive<jupyter_text>**Install packages**<jupyter_code>!pip install timeout-decorator<jupyter_output>Collecting timeout-decorator
  Downloading https://files.pythonhosted.org/packages/07/1c/0d9adcb848f1690f3253dcb1c1557b6cf229a93e724977cb83f266cbd0ae/timeout-decorator-0.4.1.tar.gz
Building wheels for collected packages: timeout-decorator
  Building wheel for timeout-decorator (setup.py) ... [?25l[?25hdone
  Created wheel for timeout-decorator: filename=timeout_decorator-0.4.1-cp36-none-any.whl size=5021 sha256=ef9ee56ad3c92e809a70ebcb0858c91dc07bdbf78b6c83446931a5fea0f775e9
  Stored in directory: /root/.cache/pip/wheels/f1/e6/ea/7387e3629cb46ba65140141f972745b823f4486c6fe884ccb8
Successfully built timeout-decorator
Installing collected packages: timeout-decorator
Successfully installed timeout-decorator-0.4.1<jupyter_text>**Generate graph data**  Data from the original article<jupyter_code>## [node i, node j, distance between node i and j]
## using data from example 1: San Francisco Bay Area Graph of Time-Distances (in minutes)
data = [[1, 2, 30], [1, 4, 30], [1, 9, 40],
        [2, 3, 25], [2, 4, 40], [3, 4, 50],
        [4, 5, 30], [4, 6, 20], [5, 7, 25],
        [6, 7, 20], [6, 9, 20], [7, 8, 25],
        [8, 9, 20]]
nodes = 9<jupyter_output><empty_output><jupyter_text>Create random graph<jupyter_code>%cd '/content/gdrive/My Drive/Colab Notebooks/hedetniemi_matrix_sum'
import networkx as nx
import random

## Number of nodes (100/1,000/10,000/100,000/1,000,000)
nodes = 10000
print('Nodes: ', nodes)
## Total degree
degree = 3
print('Degree: ', degree)

G = nx.random_regular_graph(degree,nodes)
for (u, v) in G.edges():
    G.edges[u,v]['weight'] = random.uniform(1,100)
nx.draw(G)
nx.write_weighted_edgelist(G, 'graph_n' + str(nodes) + '_d' + str(degree) + '.txt')<jupyter_output><empty_output><jupyter_text>Read random graph<jupyter_code>%cd '/content/gdrive/My Drive/Colab Notebooks/hedetniemi_matrix_sum'

## Number of nodes (100/1,000/10,000/100,000/1,000,000)
nodes = 100
print('Nodes: ', nodes)
## Total degree
degree = 3
print('Degree: ', degree)

data = []
with open('graph_n' + str(nodes) + '_d' + str(degree) + '.txt', 'r') as f:
  lines = f.read().splitlines()
  for line in lines:
    l = line.split()
    item = [int(l[0]), int(l[1]), float(l[2])]
    data.append(item)

print(data[0])<jupyter_output>/content/gdrive/My Drive/Colab Notebooks/hedetniemi_matrix_sum
Nodes:  100
Degree:  3
[77, 86, 89.39726376738572]<jupyter_text>**Implementation 1: list**   Construct distance matrix<jupyter_code>from timeit import default_timer
import timeout_decorator

@timeout_decorator.timeout(100)
def distance_matrix(graph, n):
  ## calculate distance matrix
  INF = float('inf')
  dist_mtx = [[INF] * n for i in range(n)]
  for g in graph:
    i = g[0] - 1
    j = g[1] - 1
    d = g[2]
    dist_mtx[i][j] = d
    dist_mtx[j][i] = d

  ## set diagonal to 0
  for i in range(n):
    dist_mtx[i][i] = 0.0
 
  return dist_mtx


## print time costs
try:
  start = default_timer()
  dist_mtx = distance_matrix(data, nodes)
  stop = default_timer()
  print('Time: ', stop - start)
except:
  print('Time: inf')<jupyter_output>Time:  0.0002120919999981652<jupyter_text>Calculate Floyd–Warshall distance<jupyter_code>from timeit import default_timer
import timeout_decorator

@timeout_decorator.timeout(10)
def floyd_distance(matrix, n):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if matrix[i][j] > matrix[i][k] + matrix[k][j]:
          matrix[i][j] = matrix[i][k] + matrix[k][j]
  
  return matrix


## print time costs
try:
  start = default_timer()
  mtx_a_t = floyd_distance(dist_mtx, nodes)
  stop = default_timer()
  print('Time: ', stop - start)
except:
  print('Time: inf')

## print shortest path matrix
with open('floyd_mtx_list.txt', 'w') as fw:
  fw.write('\n'.join(['\t'.join([str(round(cell,2)) for cell in row]) for row in mtx_a_t]))<jupyter_output>Time:  0.12673904499999367<jupyter_text>**Implementation 2: numpy**   Construct distance matrix<jupyter_code>from timeit import default_timer
import numpy as np
import timeout_decorator

@timeout_decorator.timeout(100)
def distance_matrix(graph, n):
  ## calculate distance matrix
  dist_mtx = np.full((n,n), np.inf)
  for g in graph:
    i = int(g[0]) - 1
    j = int(g[1]) - 1
    d = g[2]
    dist_mtx[i,j] = d
    dist_mtx[j,i] = d

  ## set diagonal to 0
  np.fill_diagonal(dist_mtx, 0)
 
  return dist_mtx


## print time costs
try:
  start = default_timer()
  dist_mtx = distance_matrix(data, nodes)
  stop = default_timer()
  print('Time: ', stop - start)
except:
  print('Time: inf')<jupyter_output>Time:  0.0005170190000001185<jupyter_text>Calculate Floyd–Warshall distance<jupyter_code>from timeit import default_timer
import numpy as np
import timeout_decorator

@timeout_decorator.timeout(100)
def floyd_distance(matrix, n):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if matrix[i,j] > matrix[i,k] + matrix[k,j]:
          matrix[i,j] = matrix[i,k] + matrix[k,j]
  
  return matrix


## print time costs
try:
  start = default_timer()
  mtx_a_t = floyd_distance(dist_mtx, nodes)
  stop = default_timer()
  print('Time: ', stop - start)
except:
  print('Time: inf')

## print shortest path matrix
with open('floyd_mtx_np.txt', 'w') as fw:
  fw.write('\n'.join(['\t'.join([str(round(cell,2)) for cell in row]) for row in mtx_a_t]))<jupyter_output>Time:  0.6864518139999802<jupyter_text>**Implementation 3: numba (njit)**   Construct distance matrix<jupyter_code>from timeit import default_timer
import numpy as np
import numba
import timeout_decorator

@timeout_decorator.timeout(10)
@numba.njit
def distance_matrix(graph, n):
  ## calculate distance matrix
  dist_mtx = np.full((n,n), np.inf)
  for g in numba.prange(graph.shape[0]):
    i = int(graph[g,0]) - 1
    j = int(graph[g,1]) - 1
    d = graph[g,2]
    dist_mtx[i,j] = d
    dist_mtx[j,i] = d

  ## set diagonal to 0
  np.fill_diagonal(dist_mtx, 0)
 
  return dist_mtx


## print time costs
try:
  start = default_timer()
  dist_mtx = distance_matrix(np.array(data), nodes)
  stop = default_timer()
  print('Time: ', stop - start)
except:
  print('Time: inf')<jupyter_output>Time:  1.4400049600000102<jupyter_text>Calculate Floyd–Warshall distance<jupyter_code>from timeit import default_timer
import numpy as np
import numba
import timeout_decorator


@timeout_decorator.timeout(100)
@numba.njit
def floyd_distance(matrix, n):
  for k in numba.prange(n):
    for i in numba.prange(n):
      for j in numba.prange(n):
        if matrix[i,j] > matrix[i,k] + matrix[k,j]:
          matrix[i,j] = matrix[i,k] + matrix[k,j]
  return matrix


## print time costs
try:
  start = default_timer()
  mtx_a_t = floyd_distance(dist_mtx, nodes)
  stop = default_timer()
  print('Time: ', stop - start)
except:
  print('Time: inf')

## print shortest path matrix
with open('floyd_mtx_nb.txt', 'w') as fw:
  fw.write('\n'.join(['\t'.join([str(round(cell,2)) for cell in row]) for row in mtx_a_t]))
!diff dist_mtx_list.txt dist_mtx_nb.txt<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14118693607828187, 'fraction_numerical': 0.0621425848265345, 'mean_word_length': 4.877520537714712, 'pattern_counts': {'":': 0, '<': 38, '<?xml version=': 0, '>': 41, 'https://': 2, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '234727', 'license': 'Apache-2.0', 'n_tokens_mistral': 3370, 'n_tokens_neox': 3055, 'n_words': 665, 'path': 'floyd_distance.ipynb', 'repo_name': 'linyuehzzz/hedetniemi_distance', 'size': '7870'}