Jademaster · September 28, 2021 16:47
diff --git a/freemetricspace.py b/freemetricspace.py
 import matplotlib.pyplot as plt
 import numpy as np
 import math 
 from PIL import Image

 #this code takes a matrix M, regards it as a weighted graph where the entry M_ij indicates the weight between vertex i and vertex j. The free category on this graph is computed using the geometric series formula F(M) = Sum_{n geq 0} M^n with operations valued in the min plus semiring. The function freemetricspace(M,res) computes this formula to the first res terms. In words, this computes the shortest paths which occur in <= n steps.

 #this function computes naive matrix multiplication in the min plus semiring
 def mult(m1,m2):
  assert (m1.shape[1] == m2.shape[0]), "shape mismatch"
  newsize = (m1.shape[0],m2.shape[1])
  prod = np.zeros(newsize)
  for i in range(newsize[0]):
    for j in range(newsize[1]):
      prod[i,j]= int(min([ m1[i,k] + m2[k,j] for k in range(m1.shape[1])]))
  return prod

 #this function returns the idenity matrix in the min plus semiring
 def id(n):
  result= np.full((n,n),math.inf)
  for i in range(n):
    result[i,i]=0
  return result
  
 def freemetricspace(M,res):
  x=[id(M.shape[0])]
  for i in range(1,res):
    a=mult(M,x[-1])
    plt.matshow(a)
    x.append(a)
  return np.min(x,axis=0) 
  
 #the image I used as input can be found here: https://philogb.github.io/blog/2010/02/12/voronoi-tessellation/
 im= Image.open("tess.png")
 im=im.convert('L')
 mat = np.array(im)
 met = freemetricspace(mat,7)
 plt.show()


 \
	import matplotlib.pyplot as plt
	import numpy as np
	import math
	from PIL import Image

	#this code takes a matrix M, regards it as a weighted graph where the entry M_ij indicates the weight between vertex i and vertex j. The free category on this graph is computed using the geometric series formula F(M) = Sum_{n geq 0} M^n with operations valued in the min plus semiring. The function freemetricspace(M,res) computes this formula to the first res terms. In words, this computes the shortest paths which occur in <= n steps.

	#this function computes naive matrix multiplication in the min plus semiring
	def mult(m1,m2):
	assert (m1.shape[1] == m2.shape[0]), "shape mismatch"
	newsize = (m1.shape[0],m2.shape[1])
	prod = np.zeros(newsize)
	for i in range(newsize[0]):
	for j in range(newsize[1]):
	prod[i,j]= int(min([ m1[i,k] + m2[k,j] for k in range(m1.shape[1])]))
	return prod

	#this function returns the idenity matrix in the min plus semiring
	def id(n):
	result= np.full((n,n),math.inf)
	for i in range(n):
	result[i,i]=0
	return result

	def freemetricspace(M,res):
	x=[id(M.shape[0])]
	for i in range(1,res):
	a=mult(M,x[-1])
	plt.matshow(a)
	x.append(a)
	return np.min(x,axis=0)

	#the image I used as input can be found here: https://philogb.github.io/blog/2010/02/12/voronoi-tessellation/
	im= Image.open("tess.png")
	im=im.convert('L')
	mat = np.array(im)
	met = freemetricspace(mat,7)
	plt.show()


	\