Ovdje je implementirano nekoliko dodatnih funkcija za lakši i brži rad u pythonu.
Funkcije se nalaze u datoteci DSTG.py.
import networkx as nx
from ipy_table import *
import numpy as np
import matplotlib.pyplot as plt
import pylab
import random
import copy
from IPython.core.display import HTML
def CrtajTezinskiGraf(G,pos,omjeri=None,pomaci=None,slika=None,velicinaVrha=300,bojaVrha='y',rubVrha=None,oblikVrha='o',
debljinaBrida=1,bojaBrida='k',fontTezine=12,fontVrh=12):
pozicijaOznake={}
if omjeri==None:
for u in G.edges().__iter__():
pozicijaOznake[u]=0.5
else:
pozicijaOznake=omjeri
for u in G.edges().__iter__():
if not(u in pozicijaOznake.keys()):
pozicijaOznake[u]=0.5
dxdy={}
if pomaci==None:
for u in G.edges().__iter__():
dxdy[u]=(0,0)
else:
dxdy=pomaci
for u in G.edges().__iter__():
if not(u in dxdy.keys()):
dxdy[u]=(0,0)
rjecnik={}
for u in G.edges(data=True).__iter__():
rjecnik[(u[0],u[1])]=str(u[2]['weight'])
if rubVrha == None:
nx.draw_networkx_nodes(G,pos,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha)
else:
nx.draw_networkx_nodes(G,pos,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha,edgecolors=rubVrha)
nx.draw_networkx_edges(G,pos,width=debljinaBrida,edge_color=bojaBrida)
#nx.draw_networkx_edge_labels(G,pos,edge_labels=rjecnik)
for (u,v) in G.edges().__iter__():
plt.text((1-pozicijaOznake[(u,v)])*pos[u][0]+pozicijaOznake[(u,v)]*pos[v][0]+dxdy[(u,v)][0],
(1-pozicijaOznake[(u,v)])*pos[u][1]+pozicijaOznake[(u,v)]*pos[v][1]+dxdy[(u,v)][1],
rjecnik[(u,v)], bbox=dict(facecolor='white', edgecolor='white',alpha=1),size=fontTezine)
nx.draw_networkx_labels(G,pos,font_size=fontVrh)
#pylab.gcf().gca().set_axis_off()
plt.axis('off')
pylab.gcf().set_facecolor('w')
if slika==None:
plt.axis('auto')
else:
plt.xlim(*slika[0])
plt.ylim(*slika[1])
plt.show()
return
def CrtajNajkraciPut(G,pos,prvi,drugi,tezine=True,omjeri=None,pomaci=None,slika=None,velicinaVrha=300,bojaVrha='y',
oblikVrha='o',rubVrha=None,debljinaBrida=1,bojaBrida='k',fontTezine=12,fontVrh=12,alfa=0.5,
bojaPuta='r',debljinaPuta=5,bojaVrha2='cyan'):
#crtanje tezinskog grafa
vrhovi=list(G.nodes())
vrhovi.remove(prvi)
vrhovi.remove(drugi)
if tezine:
pozicijaOznake={}
if omjeri==None:
for u in G.edges().__iter__():
pozicijaOznake[u]=0.5
else:
pozicijaOznake=omjeri
for u in G.edges().__iter__():
if not(u in pozicijaOznake.keys()):
pozicijaOznake[u]=0.5
dxdy={}
if pomaci==None:
for u in G.edges().__iter__():
dxdy[u]=(0,0)
else:
dxdy=pomaci
for u in G.edges().__iter__():
if not(u in dxdy.keys()):
dxdy[u]=(0,0)
rjecnik={}
for u in G.edges(data=True).__iter__():
rjecnik[(u[0],u[1])]=str(u[2]['weight'])
for (u,v) in G.edges().__iter__():
plt.text((1-pozicijaOznake[(u,v)])*pos[u][0]+pozicijaOznake[(u,v)]*pos[v][0]+dxdy[(u,v)][0],
(1-pozicijaOznake[(u,v)])*pos[u][1]+pozicijaOznake[(u,v)]*pos[v][1]+dxdy[(u,v)][1],
rjecnik[(u,v)], bbox=dict(facecolor='white', edgecolor='white',alpha=1),size=fontTezine)
if rubVrha == None:
nx.draw_networkx_nodes(G,pos,nodelist=vrhovi,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha)
else:
nx.draw_networkx_nodes(G,pos,nodelist=vrhovi,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha,edgecolors=rubVrha)
nx.draw_networkx_edges(G,pos,width=debljinaBrida,edge_color=bojaBrida)
nx.draw_networkx_labels(G,pos,font_size=fontVrh)
#isticanje najkraceg puta
istaknutiBridovi=[]
if tezine:
for i in range(len(nx.dijkstra_path(G,prvi,drugi))-1):
istaknutiBridovi.append((nx.dijkstra_path(G,prvi,drugi)[i],nx.dijkstra_path(G,prvi,drugi)[i+1]))
else:
for i in range(len(nx.shortest_path(G,prvi,drugi))-1):
istaknutiBridovi.append((nx.shortest_path(G,prvi,drugi)[i],nx.shortest_path(G,prvi,drugi)[i+1]))
nx.draw_networkx_edges(G,pos,edgelist=istaknutiBridovi,width=debljinaPuta,edge_color=bojaPuta,alpha=alfa)
if rubVrha == None:
nx.draw_networkx_nodes(G,pos,nodelist=[prvi,drugi],node_size=velicinaVrha,node_color=bojaVrha2,node_shape=oblikVrha)
else:
nx.draw_networkx_nodes(G,pos,nodelist=[prvi,drugi],node_size=velicinaVrha,node_color=bojaVrha2,node_shape=oblikVrha,
edgecolors=rubVrha)
plt.axis('off')
pylab.gcf().set_facecolor('w')
if slika==None:
plt.axis('auto')
else:
plt.xlim(*slika[0])
plt.ylim(*slika[1])
plt.show()
return
def StabloNajkracihPutova(G,pos,pocetak,tezine=True,omjeri=None,pomaci=None,slika=None,velicinaVrha=300,bojaVrha='y',
oblikVrha='o',rubVrha=None,debljinaBrida=1,bojaBrida='k',fontTezine=12,fontVrh=12,alfa=0.5,
bojaPuta='r',debljinaPuta=5,bojaVrha2='cyan'):
#crtanje tezinskog grafa
vrhovi=list(G.nodes())
vrhovi.remove(pocetak)
if tezine:
pozicijaOznake={}
if omjeri==None:
for u in G.edges().__iter__():
pozicijaOznake[u]=0.5
else:
pozicijaOznake=omjeri
for u in G.edges().__iter__():
if not(u in pozicijaOznake.keys()):
pozicijaOznake[u]=0.5
dxdy={}
if pomaci==None:
for u in G.edges().__iter__():
dxdy[u]=(0,0)
else:
dxdy=pomaci
for u in G.edges().__iter__():
if not(u in dxdy.keys()):
dxdy[u]=(0,0)
rjecnik={}
for u in G.edges(data=True).__iter__():
rjecnik[(u[0],u[1])]=str(u[2]['weight'])
for (u,v) in G.edges().__iter__():
plt.text((1-pozicijaOznake[(u,v)])*pos[u][0]+pozicijaOznake[(u,v)]*pos[v][0]+dxdy[(u,v)][0],
(1-pozicijaOznake[(u,v)])*pos[u][1]+pozicijaOznake[(u,v)]*pos[v][1]+dxdy[(u,v)][1],
rjecnik[(u,v)], bbox=dict(facecolor='white', edgecolor='white',alpha=1),size=fontTezine)
if rubVrha == None:
nx.draw_networkx_nodes(G,pos,nodelist=vrhovi,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha)
else:
nx.draw_networkx_nodes(G,pos,nodelist=vrhovi,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha,edgecolors=rubVrha)
nx.draw_networkx_edges(G,pos,width=debljinaBrida,edge_color=bojaBrida)
nx.draw_networkx_labels(G,pos,font_size=fontVrh)
#isticanje stabla najkracih putova
istaknutiBridovi=[]
if tezine:
stablo=nx.dijkstra_predecessor_and_distance(G,pocetak)[0]
del stablo[pocetak]
for u in stablo:
istaknutiBridovi.append((u,stablo[u][0]))
else:
stablo=nx.predecessor(G,pocetak)
del stablo[pocetak]
for u in stablo:
istaknutiBridovi.append((u,stablo[u][0]))
nx.draw_networkx_edges(G,pos,edgelist=istaknutiBridovi,width=debljinaPuta,edge_color=bojaPuta,alpha=alfa)
if rubVrha == None:
nx.draw_networkx_nodes(G,pos,nodelist=[pocetak],node_size=velicinaVrha,node_color=bojaVrha2,node_shape=oblikVrha)
else:
nx.draw_networkx_nodes(G,pos,nodelist=[pocetak],node_size=velicinaVrha,node_color=bojaVrha2,node_shape=oblikVrha,
edgecolors=rubVrha)
plt.axis('off')
pylab.gcf().set_facecolor('w')
if slika==None:
plt.axis('auto')
else:
plt.xlim(*slika[0])
plt.ylim(*slika[1])
plt.show()
return
def RootedEmbedding(G,korijen):
root=korijen
n=G.number_of_nodes()
e=dict(G.adjacency())
pos=dict(zip(G.nodes(),[(-np.ceil(np.sqrt(n)),np.ceil(np.sqrt(n))) for i in range(n)]))
v=dict(zip(G.nodes(),[(0,0) for i in range(n)]))
next=[root]
done=[root]
while next != []:
root=next[0]
new=[]
for i in e[root]:
if not(i in done): new.append(i)
for i in range(len(new)):
dx=(pos[root][1]-pos[root][0])/len(new)
pos[new[i]]=(pos[root][0]+i*dx,pos[root][0]+(i+1)*dx)
x=sum(pos[new[i]])/2.0
v[new[i]]=(x,v[root][1]-1)
next=next[1:]+new
done=done+new
return v
def KorijenskoStabloNajkracihPutova(G,korijen,tezine=True,omjeri=None,pomaci=None,slika=None,velicinaVrha=300,bojaVrha='y',
oblikVrha='o',rubVrha=None,debljinaBrida=1,bojaBrida='k',fontTezine=12,fontVrh=12):
istaknutiBridovi=[]
if tezine:
stablo=nx.dijkstra_predecessor_and_distance(G,korijen)[0]
else:
stablo=nx.predecessor(G,korijen)
del stablo[korijen]
for u in stablo:
if (u,stablo[u][0]) in G.edges():
istaknutiBridovi.append((u,stablo[u][0]))
else:
istaknutiBridovi.append((stablo[u][0],u))
G1=nx.Graph(istaknutiBridovi)
pos=RootedEmbedding(G1,korijen)
pozicijaOznake={}
if tezine:
if omjeri==None:
for u in G.edges().__iter__():
pozicijaOznake[u]=0.5
else:
pozicijaOznake=omjeri
for u in G.edges().__iter__():
if not(u in pozicijaOznake.keys()):
pozicijaOznake[u]=0.5
dxdy={}
if pomaci==None:
for u in G.edges().__iter__():
dxdy[u]=(0,0)
else:
dxdy=pomaci
for u in G.edges().__iter__():
if not(u in dxdy.keys()):
dxdy[u]=(0,0)
rjecnik={}
for u in G.edges(data=True).__iter__():
rjecnik[(u[0],u[1])]=str(u[2]['weight'])
for (u,v) in G1.edges().__iter__():
try:
plt.text((1-pozicijaOznake[(u,v)])*pos[u][0]+pozicijaOznake[(u,v)]*pos[v][0]+dxdy[(u,v)][0],
(1-pozicijaOznake[(u,v)])*pos[u][1]+pozicijaOznake[(u,v)]*pos[v][1]+dxdy[(u,v)][1],
rjecnik[(u,v)], bbox=dict(facecolor='white', edgecolor='white',alpha=1),size=fontTezine)
except:
plt.text((1-pozicijaOznake[(v,u)])*pos[v][0]+pozicijaOznake[(v,u)]*pos[u][0]+dxdy[(v,u)][0],
(1-pozicijaOznake[(v,u)])*pos[v][1]+pozicijaOznake[(v,u)]*pos[u][1]+dxdy[(v,u)][1],
rjecnik[(v,u)], bbox=dict(facecolor='white', edgecolor='white',alpha=1),size=fontTezine)
if rubVrha == None:
nx.draw_networkx_nodes(G1,pos,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha)
else:
nx.draw_networkx_nodes(G1,pos,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha,edgecolors=rubVrha)
nx.draw_networkx_edges(G1,pos,width=debljinaBrida,edge_color=bojaBrida)
nx.draw_networkx_labels(G1,pos,font_size=fontVrh)
#pylab.gcf().gca().set_axis_off()
plt.axis('off')
pylab.gcf().set_facecolor('w')
if slika==None:
plt.axis('auto')
else:
plt.xlim(*slika[0])
plt.ylim(*slika[1])
plt.show()
return
def Dijkstra_graf(G,v0,v1=None):
"""Poboljsana verzija Dijkstrinog algoritma za najkrace putove u tezinskom grafu G od vrha v0.
Ako graf ima i negativnih tezina, tada algoritam vraca error.
Ako je v1=None, na izlazu se daje uredjeni par od dva rjecnika. U prvom rjecniku su dane
udaljenosti pojedinih vrhova od vrha v0, a u drugom neposredni prethodnici pojedinih vrhova
na najkracem putu od vrha v0.
U protivnom se daje najkraci put izmedju vrhova v0 i v1 ukoliko postoji."""
MM=min(map(lambda x: x[2]['weight'],G.edges(data=True)))
tezina_brida={}
for e in G.edges(data=True):
if e[2]!={}:
tezina_brida[(e[0],e[1])]=e[2]['weight']
tezina_brida[(e[1],e[0])]=e[2]['weight']
else:
tezina_brida[(e[0],e[1])]=1
tezina_brida[(e[1],e[0])]=1
P={}
udaljenost={}
Q=set(G.nodes())
for v in Q:
if v == v0:
udaljenost[v]=0
P[v]=None
else:
udaljenost[v]=np.inf
P[v]=None
while len(Q)>0:
m=min([udaljenost[u] for u in Q])
if m == np.inf: break
v=random.choice(list(filter(lambda x: udaljenost[x]==m, Q)))
Q.remove(v)
for u in set(G.neighbors(v)).intersection(Q):
if udaljenost[u] > udaljenost[v]+tezina_brida[(v,u)]:
udaljenost[u] = udaljenost[v]+tezina_brida[(v,u)]
P[u] = v
if MM<0: print("error: Dijkstra ne radi ispravno na negativnim tezinama")
if v1==None: return (udaljenost,P)
v=v1
min_put=[v1]
while v!=v0 and v!=None:
v=P[v]
min_put=[v]+min_put
if v==None:
return []
else:
return min_put
def to_latex_dijkstra(tablica):
"""Pomocna funkcija za latex prikaz tablice kod rucnih prikaza Dijkstrinih algoritama."""
for i in range(len(tablica)):
for j in range(len(tablica[0])):
if type(tablica[i][j]) in (int,str):
pass
elif tablica[i][j][0] == '-':
if tablica[i][j][1] == np.inf:
tablica[i][j] = '$(-,\\infty)$'
else:
tablica[i][j] = '$(-,0)$'
else:
tablica[i][j] = '$('+str(tablica[i][j][0])+','+str(tablica[i][j][1])+')$'
return tablica
def rucni_Dijkstra_graf(G,v0,poredak=None):
"""Na izlazu daje tablicu kakva se dobiva kod rucnog provodjenja poboljsane verzije
Dijkstrinog algoritma na tezinskom grafu s pocetnim vrhom v0.
Opcija poredak=None daje poredak vrhova u tablici kako se oni javljaju u listi
G.nodes(), a ako zelimo neki drugi poredak, onda mozemo sami navesti listu sa
zeljenim poretkom."""
if poredak==None:
V=list(G.nodes())
else:
V=poredak
koraci={}
tezina_brida={}
for e in G.edges(data=True):
tezina_brida[(e[0],e[1])]=e[2]['weight']
tezina_brida[(e[1],e[0])]=e[2]['weight']
koraci[0]={}
for v in V:
if v==v0:
koraci[0][v]=('-',0)
else:
koraci[0][v]=('-',np.inf)
Q=set(G.nodes())
k=1
while len(Q)>1:
m=min([koraci[k-1][x][1] for x in Q])
if m==np.inf:
break
else:
koraci[k]=koraci[k-1].copy()
w=random.choice(list(filter(lambda x: koraci[k-1][x][1]==m, Q)))
Q.remove(w)
koraci[k][w]='*****'
for v in set(G.neighbors(w)).intersection(Q):
if koraci[k-1][v][1] > koraci[k-1][w][1]+tezina_brida[(w,v)]:
koraci[k][v] = (w, koraci[k-1][w][1]+tezina_brida[(w,v)])
k += 1
tablica=[]
for i in range(len(koraci)):
redak=[str(i)]
for v in V:
redak.append(koraci[i][v])
tablica.append(redak)
tablica=[['vrh | korak']+V]+tablica
broj_stupaca=len(koraci)+1
tablica=list(map(list,zip(*tablica)))
tablica = to_latex_dijkstra(tablica)
tablica = make_table(tablica)
apply_theme('basic_both')
set_global_style(align='center')
return tablica
def FW_html(lista,redak,stupac,korak=' '):
stupac=[korak]+stupac
for k in range(len(lista)):
lista[k]=[redak[k]]+lista[k]
lista = [stupac] + lista
for i in range(len(lista)):
for j in range(len(lista[0])):
if lista[i][j] != np.inf:
lista[i][j] = '$' + str(lista[i][j]) + '$'
else:
lista[i][j] = '$\\infty$'
lista=make_table(lista)
apply_theme('basic_both')
set_global_style(align='center')
return lista
def FW(graf,step,ncol,redoslijed_vrhova=None):
if redoslijed_vrhova==None:
redoslijed_vrhova=list(graf.nodes())
bridovi=graf.edges()
matrica=[[0 for j in range(len(redoslijed_vrhova))] for i in range(len(redoslijed_vrhova))]
for i in range(len(redoslijed_vrhova)):
for j in range(i+1,len(redoslijed_vrhova)):
if (redoslijed_vrhova[i],redoslijed_vrhova[j]) in bridovi:
matrica[i][j]=graf.get_edge_data(redoslijed_vrhova[i],redoslijed_vrhova[j])['weight']
matrica[j][i]=graf.get_edge_data(redoslijed_vrhova[i],redoslijed_vrhova[j])['weight']
elif (redoslijed_vrhova[j],redoslijed_vrhova[i]) in bridovi:
matrica[i][j]=graf.get_edge_data(redoslijed_vrhova[j],redoslijed_vrhova[i])['weight']
matrica[j][i]=graf.get_edge_data(redoslijed_vrhova[j],redoslijed_vrhova[i])['weight']
else:
matrica[i][j]=np.inf
matrica[j][i]=np.inf
koraci={0:copy.deepcopy(matrica)}
for k in range(len(redoslijed_vrhova)):
for i in range(len(redoslijed_vrhova)):
for j in range(len(redoslijed_vrhova)):
matrica[i][j]=min(matrica[i][j],matrica[i][k]+matrica[k][j])
koraci[k+1]=copy.deepcopy(matrica)
lista_tablica = []
for t in step:
lista_tablica.append(FW_html(koraci[t],redoslijed_vrhova,redoslijed_vrhova,'k='+str(t)))
prikaz = '<table><tr style="background-color:white;">'
for i in range(len(step)):
prikaz = prikaz + '<td>' + lista_tablica[i]._repr_html_() + '</td>'
if (i+1) % ncol == 0:
prikaz = prikaz + '</tr>'
if i+1 < len(step):
prikaz = prikaz + '<tr style="background-color:white;">'
if len(step) % ncol != 0:
prikaz = prikaz + '</tr></table>'
else:
prikaz = prikaz + '</table>'
return HTML(prikaz)