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
Implementacija se bazira na matričnom teoremu o stablima.
def BrojRazapinjucihStabala(H):
if nx.number_connected_components(H)>1: return 0
G=H.copy()
for (u,v) in list(G.edges()):
if u==v:
G.remove_edge(u,v)
bridovi=list(G.edges())
vrhovi=list(G.nodes())
nu=len(vrhovi)
mat=np.matrix([[0 for i in range(nu)] for j in range(nu)])
for i in range(nu):
for j in range(nu):
if ((vrhovi[i],vrhovi[j]) in bridovi):
m=bridovi.count((vrhovi[i],vrhovi[j]))
mat[i,j]+=m
mat[j,i]+=m
for i in range(nu):
for j in range(nu):
if i==j:
mat[i,j]=G.degree(vrhovi[i])
else:
mat[i,j]=-mat[i,j]
mat2=mat[1:,1:]
return int(np.round(np.linalg.det(mat2)))
Funkcije za prikazivanje DFS ili BFS stabla na grafu ili kao korijenskog stabla.
Ostale varijable služe za dodatno kontroliranje izgleda slike.
def DFSstablo(G,pos,pocetak,slika=None,velicinaVrha=300,bojaVrha='y',oblikVrha='o',rubVrha=None,debljinaBrida=1,bojaBrida='k',
fontVrh=12,alfa=0.5,bojaStabla='r',debljinaStabla=5,bojaVrha2='cyan'):
vrhovi=list(G.nodes())
vrhovi.remove(pocetak)
dfs_bridovi=list(nx.dfs_edges(G,pocetak))
if rubVrha == None:
nx.draw_networkx_nodes(G,pos,nodelist=vrhovi,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha)
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=vrhovi,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha,edgecolors=rubVrha)
nx.draw_networkx_nodes(G,pos,nodelist=[pocetak],node_size=velicinaVrha,node_color=bojaVrha2,node_shape=oblikVrha,
edgecolors=rubVrha)
nx.draw_networkx_labels(G,pos,font_size=fontVrh)
nx.draw_networkx_edges(G,pos,width=debljinaBrida,edge_color=bojaBrida)
nx.draw_networkx_edges(G,pos,edgelist=dfs_bridovi,width=debljinaStabla,edge_color=bojaStabla,alpha=alfa)
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 DFSkorijenskoStablo(G,pocetak,slika=None,velicinaVrha=300,bojaVrha='y',oblikVrha='o',rubVrha=None,debljinaBrida=1,bojaBrida='k',
fontVrh=12):
dfs_stablo=nx.Graph(list(nx.dfs_edges(G,pocetak)))
pozicije=RootedEmbedding(dfs_stablo,pocetak)
if rubVrha == None:
nx.draw_networkx_nodes(dfs_stablo,pozicije,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha)
else:
nx.draw_networkx_nodes(dfs_stablo,pozicije,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha,edgecolors=rubVrha)
nx.draw_networkx_labels(dfs_stablo,pozicije,font_size=fontVrh)
nx.draw_networkx_edges(dfs_stablo,pozicije,width=debljinaBrida,edge_color=bojaBrida)
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 BFSstablo(G,pos,pocetak,slika=None,velicinaVrha=300,bojaVrha='y',oblikVrha='o',rubVrha=None,debljinaBrida=1,bojaBrida='k',
fontVrh=12,alfa=0.5,bojaStabla='r',debljinaStabla=5,bojaVrha2='cyan'):
vrhovi=list(G.nodes())
vrhovi.remove(pocetak)
bfs_bridovi=list(nx.bfs_edges(G,pocetak))
if rubVrha == None:
nx.draw_networkx_nodes(G,pos,nodelist=vrhovi,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha)
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=vrhovi,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha,edgecolors=rubVrha)
nx.draw_networkx_nodes(G,pos,nodelist=[pocetak],node_size=velicinaVrha,node_color=bojaVrha2,node_shape=oblikVrha,
edgecolors=rubVrha)
nx.draw_networkx_labels(G,pos,font_size=fontVrh)
nx.draw_networkx_edges(G,pos,width=debljinaBrida,edge_color=bojaBrida)
nx.draw_networkx_edges(G,pos,edgelist=bfs_bridovi,width=debljinaStabla,edge_color=bojaStabla,alpha=alfa)
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 BFSkorijenskoStablo(G,pocetak,slika=None,velicinaVrha=300,bojaVrha='y',oblikVrha='o',rubVrha=None,debljinaBrida=1,bojaBrida='k',
fontVrh=12):
bfs_stablo=nx.Graph(list(nx.bfs_edges(G,pocetak)))
pozicije=RootedEmbedding(bfs_stablo,pocetak)
if rubVrha == None:
nx.draw_networkx_nodes(bfs_stablo,pozicije,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha)
else:
nx.draw_networkx_nodes(bfs_stablo,pozicije,node_size=velicinaVrha,node_color=bojaVrha,node_shape=oblikVrha,edgecolors=rubVrha)
nx.draw_networkx_labels(bfs_stablo,pozicije,font_size=fontVrh)
nx.draw_networkx_edges(bfs_stablo,pozicije,width=debljinaBrida,edge_color=bojaBrida)
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 is_acyclic(G):
if G.number_of_selfloops()>0: return False
if G.is_multigraph(): return False
parent={}
for v in G.nodes():
S=[]
R=[v]
parent[v]='null'
while len(R)!=0:
x=R[0]
S.append(x)
del R[0]
for y in G.neighbors(x):
if y==parent[x]:
continue
if not(y in S):
parent[y]=x
R.append(y)
else:
return False
return True
def rezni_bridovi(G):
komponente=nx.connected_component_subgraphs(G)
rezni=[]
for H in komponente:
rezni_kandidati=nx.dfs_edges(H,list(H.nodes())[0])
for brid in rezni_kandidati:
graf=H.copy()
graf.remove_edge(*brid)
if nx.number_connected_components(graf)>nx.number_connected_components(H):
rezni.append(brid)
return rezni
def dfs_graf(G,v0):
V=list(G.nodes())
V.remove(v0)
vrhovi=[v0]+V
d={}
f={}
P={}
color={}
tree_edges=[]
back_edges=[]
for u in vrhovi:
color[u]="WHITE"
P[u]=None
time=0
for u in vrhovi:
if color[u]=="WHITE":
S=[u]
while S!=[]:
x=S[-1]
del S[-1]
if color[x]=="WHITE":
time+=1
d[x]=time
color[x]="GRAY"
S.append(x)
for v in G.neighbors(x):
if color[v]=="WHITE":
P[v]=x
S.append(v)
elif color[x]=="GRAY":
time+=1
f[x]=time
color[x]="BLACK"
redoslijed_vrhova=sorted(G.nodes(),key=lambda x: d[x])
tree_edges=[]
for u in redoslijed_vrhova:
if P[u]!=None:
tree_edges.append((u,P[u]))
back_edges=[]
for (u,v) in G.edges():
if ((u,v) in tree_edges) or ((v,u) in tree_edges):
pass
else:
back_edges.append((u,v))
return (redoslijed_vrhova,d,f,P,tree_edges,back_edges)
def random_cycle(G):
v0=random.choice(list(G.nodes()))
alg=dfs_graf(G,v0)
if alg[5]==[]: return False
dfs_forest=nx.Graph(alg[4])
brid_ciklus=random.choice(alg[5])
u1=brid_ciklus[0]
u2=brid_ciklus[1]
ciklus=nx.shortest_path(dfs_forest,u1,u2)+[u1]
return ciklus
def random_cycle_graph(G,pos,slika=None,velicinaVrha=300,bojaVrha='y',oblikVrha='o',rubVrha=None,
debljinaBrida=1,bojaBrida='k',fontVrh=12,alfa=0.5,bojaCiklusa='r',debljinaCiklusa=5):
vrhovi=G.nodes()
ciklus=random_cycle(G)
bridovi_ciklus=[]
for k in range(len(ciklus)-1):
bridovi_ciklus.append((ciklus[k],ciklus[k+1]))
bridovi_ciklus.append((ciklus[-1],ciklus[0]))
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_labels(G,pos,font_size=fontVrh)
nx.draw_networkx_edges(G,pos,width=debljinaBrida,edge_color=bojaBrida)
nx.draw_networkx_edges(G,pos,edgelist=bridovi_ciklus,width=debljinaCiklusa,edge_color=bojaCiklusa,alpha=alfa)
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
Funkcije za prikazivanje minimalnog ili maksimalnog stabla na grafu ili kao korijenskog stabla.
Ostale varijable služe za dodatno kontroliranje izgleda slike.
def KruskalStablo(G,pos,opcija='min',omjeri=None,pomaci=None,slika=None,velicinaVrha=300,bojaVrha='y', oblikVrha='o',debljinaBrida=1,
rubVrha=None,bojaBrida='k',fontTezine=12,fontVrh=12,alfa=0.5,bojaStabla='r',debljinaStabla=5):
#crtanje tezinskog grafa
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,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_labels(G,pos,font_size=fontVrh)
#isticanje minimalnog stabla
istaknutiBridovi=[]
if opcija=='min':
lista=list(nx.minimum_spanning_edges(G,data=False))
if opcija=='max':
lista=list(nx.maximum_spanning_edges(G,data=False))
#for u in lista:
# istaknutiBridovi.append((u[0],u[1]))
nx.draw_networkx_edges(G,pos,edgelist=lista,width=debljinaStabla,edge_color=bojaStabla,alpha=alfa)
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 PrimStablo(G,v0,pos,opcija='min',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,bojaStabla='r',debljinaStabla=5):
#crtanje tezinskog grafa
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,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_labels(G,pos,font_size=fontVrh)
#isticanje minimalnog stabla
istaknutiBridovi=[]
if opcija=='min':
lista=list(map(lambda x:(x[0],x[1]), prim_alg_min(G,v0)))
if opcija=='max':
lista=list(map(lambda x:(x[0],x[1]), prim_alg_max(G,v0)))
#for u in lista:
# istaknutiBridovi.append((u[0],u[1]))
nx.draw_networkx_edges(G,pos,edgelist=lista,width=debljinaStabla,edge_color=bojaStabla,alpha=alfa)
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 KruskalKorijenskoStablo(G,korijen,opcija='min',omjeri=None,pomaci=None,slika=None,velicinaVrha=300,bojaVrha='y',oblikVrha='o',
rubVrha=None,debljinaBrida=1,bojaBrida='k',fontTezine=12,fontVrh=12):
istaknutiBridovi=[]
if opcija=='min':
stablo=list(nx.minimum_spanning_edges(G,data=False))
if opcija=='max':
stablo=list(nx.maximum_spanning_edges(G,data=False))
#for u in stablo:
# istaknutiBridovi.append((u[0],u[1]))
G1=nx.Graph(stablo)
pos=RootedEmbedding(G1,korijen)
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 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 PrimKorijenskoStablo(G,korijen,opcija='min',omjeri=None,pomaci=None,slika=None,velicinaVrha=300,bojaVrha='y',oblikVrha='o',
rubVrha=None,debljinaBrida=1,bojaBrida='k',fontTezine=12,fontVrh=12):
istaknutiBridovi=[]
if opcija=='min':
stablo=map(lambda x:(x[0],x[1]), prim_alg_min(G,korijen))
if opcija=='max':
stablo=map(lambda x:(x[0],x[1]), prim_alg_max(G,korijen))
#for u in stablo:
# istaknutiBridovi.append((u[0],u[1]))
G1=nx.Graph(stablo)
pos=RootedEmbedding(G1,korijen)
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 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 prim_alg_min(G,v1):
vrhovi=list(G.nodes())
vrhovi.remove(v1)
oznake_vrhova={}
bridovi_stablo=[]
odabrani_vrhovi=[v1]
for v in vrhovi:
if G.get_edge_data(v,v1)!=None:
oznake_vrhova[v]=(v1,G.get_edge_data(v,v1)['weight'])
else:
oznake_vrhova[v]=(None,np.inf)
while vrhovi!=[]:
#biranje vrha s najmanjom oznakom
m=np.inf
for x in vrhovi:
if oznake_vrhova[x][1]<m:
m=oznake_vrhova[x][1]
u=x
#dodavanje brida
bridovi_stablo.append((oznake_vrhova[u][0],u,G.get_edge_data(oznake_vrhova[u][0],u)['weight']))
#promjena oznaka susjednim neodabranim vrhovima
for x in G.neighbors(u):
if (x in oznake_vrhova) and (G.get_edge_data(u,x)['weight']<oznake_vrhova[x][1]):
oznake_vrhova[x]=(u,G.get_edge_data(u,x)['weight'])
#brisanje odabranog vrha
vrhovi.remove(u)
return bridovi_stablo
def prim_alg_max(H,v1):
max_tezine=map(lambda x: (x[0],x[1],-x[2]['weight']), H.edges(data=True))
G=nx.Graph()
G.add_weighted_edges_from(max_tezine)
vrhovi=list(G.nodes())
vrhovi.remove(v1)
oznake_vrhova={}
bridovi_stablo=[]
odabrani_vrhovi=[v1]
for v in vrhovi:
if G.get_edge_data(v,v1)!=None:
oznake_vrhova[v]=(v1,G.get_edge_data(v,v1)['weight'])
else:
oznake_vrhova[v]=(None,np.inf)
while vrhovi!=[]:
#biranje vrha s najmanjom oznakom
m=np.inf
for x in vrhovi:
if oznake_vrhova[x][1]<m:
m=oznake_vrhova[x][1]
u=x
#dodavanje brida
bridovi_stablo.append((oznake_vrhova[u][0],u,H.get_edge_data(oznake_vrhova[u][0],u)['weight']))
#promjena oznaka susjednim neodabranim vrhovima
for x in G.neighbors(u):
if (x in oznake_vrhova) and (G.get_edge_data(u,x)['weight']<oznake_vrhova[x][1]):
oznake_vrhova[x]=(u,G.get_edge_data(u,x)['weight'])
#brisanje odabranog vrha
vrhovi.remove(u)
return bridovi_stablo
def rucni_Kruskal(G,opcija='min'):
if opcija=='min':
bridovi_stablo=list(nx.minimum_spanning_edges(G))
else:
bridovi_stablo=list(nx.maximum_spanning_edges(G))
prvi_redak=['korak']+list(range(1,G.number_of_nodes()))
drugi_redak=['brid']+list(map(lambda x: (x[0],x[1]), bridovi_stablo))
treci_redak=['tezina']+list(map(lambda x: x[2]['weight'], bridovi_stablo))
tezina=sum(map(lambda x: x[2]['weight'], bridovi_stablo))
print("tezina stabla: ",tezina)
tablica = make_table([prvi_redak, drugi_redak, treci_redak])
apply_theme('basic_both')
set_global_style(align='center')
return tablica
def rucni_Prim(G,v0,opcija='min'):
if opcija=='min':
bridovi_stablo=prim_alg_min(G,v0)
else:
bridovi_stablo=prim_alg_max(G,v0)
prvi_redak=[str(v0)+' | korak']+list(range(1,G.number_of_nodes()))
drugi_redak=['brid']+list(map(lambda x: (x[0],x[1]), bridovi_stablo))
treci_redak=['tezina']+list(map(lambda x: x[2], bridovi_stablo))
tezina=sum(map(lambda x: x[2], bridovi_stablo))
print("tezina stabla: ",tezina)
tablica = make_table([prvi_redak, drugi_redak, treci_redak])
apply_theme('basic_both')
set_global_style(align='center')
return tablica