def generiranje_matrik(m, n):
d = m * n # število vrstic in stolpcev
rd = range(d) # obseg indeksov
matrika = Matrix(d, d) # matrika samih ničel
for i in rd:
for j in (i-1, i+1, i-n, i+n):
if j in rd:
matrika[i, j] = 1
return matrika
def matrika_mreza(m, n): #že vgrajena funkcija, .am() vrne matriko in ne grafa
return graphs.Grid2dGraph(m, n).am()
def izris_grafa(matrika): #izriše graf za dano matriko
matrika = Matrix(matrika)
G = Graph(matrika)
return G.plot().show()
def prehodna_matrika_M(matrika): #vrne matriko katere (i,j)-ti element prikazuje verjetnost, da se bomo iz i-tega vozlišča premaknili v j-to
return Matrix([r/v for r, v in zip(matrika, sum(matrika))]) # vrstica / vsota vrstice
def brisanje(j, matrika): #izbriše j-ti stolpec in j-to vrstico
return matrika.delete_columns([j]).delete_rows([j])
def dodajanje(j, matrika): #doda j-to vrstico in j-ti stolpec (ničle)
return block_matrix([[matrika[:j, :j], 0, matrika[:j, j:]],
[0, Matrix(1, 1), 0],
[matrika[j:, :j], 0, matrika[j:, j:]]])
def element_H(i, j, matrika): #izračuna (i,j)-ti element matrike H
IM = dodajanje(j, (identity_matrix(matrika.nrows()-1) - brisanje(j, matrika))^-2)
return sum(IM[i, k] * matrika[k, j] for k in range(matrika.nrows()) if k != j)
def matrika_H(matrika): #vrne celotno matriko H
return Matrix([next(zip(*dodajanje(j, (identity_matrix(matrika.nrows()-1) - brisanje(j, matrika))^-2) * matrika[:, j]))
for j in range(matrika.ncols())]).transpose()
def nakjucni_sprehod_blizine_centralnosti(i,matrika): #sprejme incidenčno matriko!
vsota = 0
n = matrika.nrows()
rd = range(0,n)
M = prehodna_matrika_M(matrika) #izračun matrike M
for j in rd:
vsota += matrika_H(M)[j,i]
return n/vsota
#def centralno_po_npbc(matrika):
# n = matrika.nrows()
# rd = range(0,n)
# rez = Matrix(n,1)
# for i in rd: #za vsako vozlišče izračunamo nsbc
# print(nakjucni_sprehod_blizine_centralnosti(i,matrika))
# rez[i] = int(nakjucni_sprehod_blizine_centralnosti(i,matrika))
# print(rez[i])
# return rez
def centralno_po_nsbc(matrika):
n = matrika.nrows()
rd = range(0,n)
najvecji = [0,0]
for i in rd:
if nakjucni_sprehod_blizine_centralnosti(i,matrika) > najvecji[1]:
najvecji = [i][nakjucni_sprehod_blizine_centralnosti(i,matrika)] #ne zna prevest rational v integer, vprašaj vidali
return najvecji
A = matrika_mreza(3,6)
#show(nakjucni_sprehod_blizine_centralnosti(1,A),nakjucni_sprehod_blizine_centralnosti(2,A))
#max(nakjucni_sprehod_blizine_centralnosti(1,A),nakjucni_sprehod_blizine_centralnosti(2,A))
#B = [4,5]
#show(B[0])
#centralno_po_nobc(A)
#centralno_po_npbc(A)
#rez = Matrix(18,1)
#type(A)
#(A^3)[1][1]
type(nakjucni_sprehod_blizine_centralnosti(1,A))
#rez[1] = tuple(nakjucni_sprehod_blizine_centralnosti(1,A))
#show(rez)
<class 'sage.rings.rational.Rational'>
def oddaljenost_i(i,matrika): #vrne oddaljenost (najkrajšo pot) i-tega vozlišča do vseh ostalih vozlišč
n = matrika.nrows()
rd = range(0,n)
vektor = Matrix(n,1)
for j in rd: #j != i
if j == i: #spusti
vektor = vektor
elif matrika[i,j] != 0: #sosednja vozlišča
vektor[j] = 1
else:
for l in range(1,n):
if vektor[j] != 0:
vektor = vektor
elif (matrika^l)[i,j] != 0:
vektor[j] = l
return vektor
def centralnost_i(i,matrika): #centralno vozlišče
return 1/sum(oddaljenost_i(i,matrika)) #sum() ne zna delit, vprašaj vidali
A = matrika_mreza(3,6)
v=oddaljenost_i(1,A)
show(v)
s=sum(v)
#C=centralnost_i(1,A)
show(s)
type(s)
<class 'sage.modules.vector_integer_dense.Vector_integer_dense'>
#def 3Dmreza(m,n,z):
# d = m*n*z #dimenzije matrike
# rd = range(d)
# matrika = Matrix(d, d) # matrika samih ničel
def generator_binarnih_dreves(k): #vrne binarno drevo
G = graphs.BalancedTree(2,k)
show(G)
return G
#def bd_matrika(k):
# return graphs.Grid2dGraph(m, n).am()
import networkx
import random
#def krozni_graf(n,k): #n vozlisc, vsako ima k povezav
# sez1 = list(range(0,n))
# #n = networkx.cycle_graph(n)
# C = graphs.CycleGraph(n)
# sez2 = []
# if k < n - 2:
# for i in C:
# while k>0:
# r = random.choice(sez1)
# if r == i-1 or r == i+1 or r == i:
# pass
# else:
# sez2.append(r)
# k -= 1
# for j in sez2:
# C.add_edges([(j, i)])
sez2 = []
return C.show()
krozni_graf(8,2)
#C.show() # long time
--------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-4-7e73a075fc87> in <module>() 35 sez2 = [] 36 return C.show() ---> 37 krozni_graf(Integer(8),Integer(2)) 38 39 #C.show() # long time <ipython-input-4-7e73a075fc87> in krozni_graf(n, k) 32 k -= Integer(1) 33 for j in sez2: ---> 34 C.add_edges([(j, i)]) 35 sez2 = [] 36 return C.show() /ext/sage/sage-9.1/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py in add_edges(self, edges, loops) 10925 raise TypeError("cannot interpret {!r} as graph edge".format(t)) 10926 if loops or u != v: > 10927 self._backend.add_edge(u, v, label, self._directed) 10928 10929 def subdivide_edge(self, *args): /ext/sage/sage-9.1/local/lib/python3.7/site-packages/sage/graphs/base/sparse_graph.pyx in sage.graphs.base.sparse_graph.SparseGraphBackend.add_edge (build/cythonized/sage/graphs/base/sparse_graph.c:16220)() 1358 1359 if u_int == v_int and not self._loops: -> 1360 raise ValueError(f"cannot add edge from {u!r} to {v!r} in graph without loops") 1361 1362 if not self.multiple_edges(None): ValueError: cannot add edge from 2 to 2 in graph without loops
#def sprehod(matrika,v1,v2):
# a = 0
# while v1 < v2:
# for v1 in matrika:
# for j in matrika:
# while j < matrika.nrows():
# b = 0
# if matrika[v1][j] == 1:
# j += 1
# b = j
# else:
# j += 1
# v1 = b
# a += 1
# return a
def oddaljenost_i_j(matrika,i,j): #izračuna dolžino najkrajše poti med i in j
n = matrika.nrows()
rd = range(0,n)
razdalja = 0
if matrika[i,j] != 0:
razdalja = 1
else:
for l in range(2,n):
if (matrika^l)[i,j] != 0:
while razdalja == 0:
razdalja = l
return razdalja
def povprecje_sprehodov(matrika,k): #sešteje najkrajše razdalje do drugih vozlišč in to deli s številom vozlišč-1
koraki = 0
for i in range(0, matrika.nrows):
if i != k:
koraki += oddaljenost_i_j(matrika,i,k)
else:
pass
return koraki/(matrika.nrows()-1) #se poglej malo mislim da ne klices prav funkcije
import random
def nakljucni_sprehod(matrika, k):
sez2 = list(range(0, (matrika.nrows()))) #seznam neobiskanih vozlišč
zacetno = k
a = len(sez2)
koraki = 0
koncni_sez = [0] * a
koncni_sez[zacetno] = 1 #v to vozlišče ni potrebno priti, na koncu popravimo na 0
sez2.remove(zacetno) #odstranimo začetno vozlišče, ker v njega ni potrebno priti
while len(sez2) > 0:
sez3 = []
for k in range(0,matrika.nrows()):
for j in range(0,matrika.nrows()):
if matrika[k,j] != 0: #naredimo seznam sosednjih vozlišč
sez3.append(j)
else:
pass
c = random.choice(sez3) #naključno izbere v kako vozlišče se premaknemo
k = c #k označuje trenutno vozlišče
sez3 = []
koraki += 1
if koncni_sez[c] == 0:
koncni_sez[c] = koraki #dodamo število korakov, ki smo jih potrebovali, da smo prišli do tega vozlišča
sez2.remove(c) #in ga odstranimo iz seznama neobiskanih vozlišč
else:
pass
#for i in sez2:
# if sez2[i] == c:
# sez2.pop(c)
# else:
# pass
koncni_sez[zacetno] = 0 #nastavimo začetno vozlišče nazaj na 0
return koncni_sez
def n_nakljucnih_sprehodov(matrika,k,n): #funkcija naredi n naključnih sprehodov iz k-tega vozlišča
d = matrika.nrows()
povp = [0] * d
for ponovitev in range(0,n):
v = nakljucni_sprehod(matrika,k)
for i in range(0,d):
povp[i] += v[i]
povp[:] = [x / n for x in povp] #deli vse elemente z n; da dobimo povprečno dolžino
return povp
def dolzina_vseh(matrika,n): #naredi n naključnih sprehodov; vrne povprečno hitrost, s katero procesi naključnega sprehajanja dosežejo vozlišče iz drugih vozlišč v omrežju
d = matrika.nrows()
povp = [0] * d
for vozlisce in range(0,d):
v = n_nakljucnih_sprehodov(matrika,vozlisce,n)
for i in range(0,d):
povp[i] += v[i]
povp[:] = [x / (n-1)*d for x in povp] #deli vse elemente s številom sprehodov; da dobimo povprečno dolžino
return povp
def nsbc(matrika,n):
rez = dolzina_vseh(matrika,n)
rez[:] = [1 / x for x in rez]
return rez
#v=oddaljenost_i(1,A)
#u=oddaljenost_i_j(A,1,15)
#show(v)
#show(u)
#izris_grafa(A)
#nakljucni_sprehod(A, 2)
#n_nakljucnih_sprehodov(A,2,500)
a=nsbc(A,10)
max(a)
5/2103
show(nakjucni_sprehod_blizine_centralnosti(0,A),nakjucni_sprehod_blizine_centralnosti(1,A),nakjucni_sprehod_blizine_centralnosti(2,A))