import sage.misc.banner
banner()
from IPython.core.display import HTML
var('A B C D E F G H I S T')
G1=Graph({A:{B:5,C:2,D:4,E:10},
B:{D:8},
C:{E:7,F:5},
D:{E:6,G:2},
E:{F:3,G:2,H:3},
F:{H:2,I:4},
G:{H:3},
H:{I:5}
},weighted=True)
pozicijeG1={A:[-1,0],B:[-1,1],C:[-1,-1],D:[0,1],E:[0,0],F:[0,-1],G:[1,1],H:[1,0],I:[1,-1]}
G1.plot(pos=pozicijeG1,edge_labels=True,figsize=[4,4])
G1.weighted_adjacency_matrix()
G1.vertices()
matrica=G1.weighted_adjacency_matrix()
G2=Graph(matrica,format="weighted_adjacency_matrix")
G2.vertices()
pozicijeG2={3:[-1,0],0:[-1,1],7:[-1,-1],5:[0,1],2:[0,0],8:[0,-1],6:[1,1],4:[1,0],1:[1,-1]}
G2.plot(pos=pozicijeG2,edge_labels=True,figsize=[4,4])
Možemo koristiti NetworkX modul.
import networkx as nx
G3=nx.read_edgelist("tezinskiGraf1_edgelist.sage",nodetype=str)
pozicije={'A':(0,2),'B':(0,4),'C':(0,0),'D':(2,4),'E':(2,2),'F':(2,0),'G':(4,4),'H':(4,2),'I':(4,0)}
nx.draw(G3,pos=pozicije,with_labels=True,node_color='y')
nx.draw_networkx_edge_labels(G3,pos=pozicije,edge_labels=nx.get_edge_attributes(G3,'weight'));
Najkraći putovi od vrha A prema svim preostalim vrhovima
Po defaultu je by_weight=False, što znači da će metoda shortest_paths zanemariti težine bridova i tražiti najkraće putove u pripadnom netežinskom grafu pomoću BFS algoritma. Ako stavimo by_weight=True, tada će se uzeti težine u obzir i koristit će se Dijkstrin algoritam. Potpuno ista situacija je i za ostale slične metode koje se dolje spominju.
G1.shortest_paths(A)
G1.shortest_paths(A,by_weight=True)
nx.shortest_path(G3,"A")
nx.single_source_dijkstra_path(G3,'A')
Udaljenosti od vrha A prema svim preostalim vrhovima
G1.shortest_path_lengths(A)
G1.shortest_path_lengths(A,by_weight=True)
nx.shortest_path_length(G3,"A")
nx.single_source_dijkstra_path_length(G3,'A')
Najkraći putovi od vrha C prema svim preostalim vrhovima
G1.shortest_paths(C)
G1.shortest_paths(C,by_weight=True)
nx.shortest_path(G3,"C")
nx.single_source_dijkstra_path(G3,"C")
Udaljenosti od vrha C prema svim preostalim vrhovima
G1.shortest_path_lengths(C)
G1.shortest_path_lengths(C,by_weight=True)
nx.shortest_path_length(G3,"C")
nx.single_source_dijkstra_path_length(G3,"C")
Najkraći put od vha A do vrha E
G1.shortest_path(A,E)
G1.shortest_path(A,E,by_weight=True)
nx.shortest_path(G3,"A","E")
nx.dijkstra_path(G3,"A","E")
Udaljenost između vrhova A i E
G1.shortest_path_length(A,E)
G1.shortest_path_length(A,E,by_weight=True)
nx.shortest_path_length(G3,"A","E")
nx.dijkstra_path_length(G3,"A","E")
Najkraći put od vrha F do vrha B
G1.shortest_path(F,B)
G1.shortest_path(F,B,by_weight=True)
nx.shortest_path(G3,"F","B")
nx.dijkstra_path(G3,"F","B")
Udaljenost između vrhova F i B
G1.shortest_path_length(F,B)
G1.shortest_path_length(F,B,by_weight=True)
nx.shortest_path_length(G3,"F","B")
nx.dijkstra_path_length(G3,"F","B")
možemo definirati svoju funkciju koja će nam ispisati konačne oznake vrhova onako kako mi provodimo Dijkstrin algoritam ručno
def rucni_dijkstra(graf,vrh):
udaljenosti=graf.shortest_path_lengths(vrh,by_weight=True)
putovi=graf.shortest_paths(vrh,by_weight=True)
vrhovi=graf.vertices()
oznake=[]
for v in vrhovi:
if v==vrh:
oznake.append(("-",0))
else:
oznake.append((putovi[v][-2],udaljenosti[v]))
return table([vrhovi,oznake])
Najkraći putovi od vrha A
rucni_dijkstra(G1,A)
Najkraći putovi od vrha B
rucni_dijkstra(G1,B)
Ako želimo najkraći put istaknuti na grafu, definiramo svoju funkciju koja će to raditi.
def najkraci_put(G,v1,v2,raspored_vrhova=None,laj="circular"):
put=G.shortest_path(v1,v2,by_weight=True)
bridovi=G.edges(labels=False)
bridovi_put=[]
for i in range(len(put)-1):
if (put[i],put[i+1]) in bridovi:
bridovi_put.append((put[i],put[i+1]))
else:
bridovi_put.append((put[i+1],put[i]))
if raspored_vrhova==None:
slika=G.plot(edge_colors={"red":bridovi_put},vertex_colors={"cyan":[v1,v2]},layout=laj,edge_labels=True)
else:
slika=G.plot(edge_colors={"red":bridovi_put},vertex_colors={"cyan":[v1,v2]},pos=raspored_vrhova,edge_labels=True)
return slika
najkraci_put(G1,A,E,raspored_vrhova=pozicijeG1).show(figsize=[4,4])
najkraci_put(G1,F,B,raspored_vrhova=pozicijeG1).show(figsize=[4,4])
najkraci_put(G1,A,H,raspored_vrhova=pozicijeG1).show(figsize=[4,4])
Ako želimo istaknuti stablo najkraćih putova iz nekog vrha na grafu, definiramo svoju funkciju koja će to raditi
def stablo_najkracih_putova(G,v0,raspored_vrhova=None,laj="circular"):
stablo=G.shortest_paths(v0,by_weight=True)
bridovi=G.edges(labels=False)
bridovi_stablo=[]
for k in stablo:
if k!=v0:
for i in range(len(stablo[k])-1):
if ((stablo[k][i],stablo[k][i+1]) in bridovi) and (not((stablo[k][i],stablo[k][i+1]) in bridovi_stablo)):
bridovi_stablo.append((stablo[k][i],stablo[k][i+1]))
elif ((stablo[k][i+1],stablo[k][i]) in bridovi) and (not((stablo[k][i+1],stablo[k][i]) in bridovi_stablo)):
bridovi_stablo.append((stablo[k][i+1],stablo[k][i]))
if raspored_vrhova==None:
slika=G.plot(edge_colors={"red":bridovi_stablo},vertex_colors={"cyan":[v0]},layout=laj,edge_labels=True)
else:
slika=G.plot(edge_colors={"red":bridovi_stablo},vertex_colors={"cyan":[v0]},pos=raspored_vrhova,edge_labels=True)
return slika
stablo_najkracih_putova(G1,A,raspored_vrhova=pozicijeG1).show(figsize=[4,4])
stablo_najkracih_putova(G1,B,raspored_vrhova=pozicijeG1).show(figsize=[4,4])
Na izlazu daje uređeni par (udaljenosti, prethodnici). Prva komponenta udaljenosti je rječnik čiji ključevi su vrhovi težinskog grafa, a vrijednosti ključeva su ponovno rječnici tako da je udaljenosti[u][v] jednako duljini najkraćeg puta od vrha u do vrha v u težinskom grafu. Druga komponenta prethodnici je također rječnik čiji ključevi su vrhovi težinskog grafa, a vrijednosti ključeva su ponovo rječnici tako da je prethodnici[u][v] prethodnik vrha v na najkraćem putu od vrha u do vrha v u težinskom grafu.
G1.shortest_path_all_pairs()
samo udaljenosti između pojedinih vrhova
G1.shortest_path_all_pairs()[0]
samo prethodnici vrhova na odgovarajućim najkraćim putovima
G1.shortest_path_all_pairs()[1]
Slično radi i floyd_warshall metoda u networkx modulu.
nx.floyd_warshall_predecessor_and_distance(G3)
nx.floyd_warshall_predecessor_and_distance(G3)[0]
nx.floyd_warshall_predecessor_and_distance(G3)[1]
ili preko Dijkstrinog algoritma
dict(nx.all_pairs_dijkstra_path(G3))
dict(nx.all_pairs_dijkstra_path_length(G3))
Možemo definirati funkciju FW koja će ispisati u obliku tablice pojedine korake Floyd-Warshallovog algoritma. Koje točno korake želimo ispisati, navodimo u varijabli step. Na primjer, step=[1,2,5] ako želimo ispisati prvi, drugi i peti korak algoritma, step=[3] ako želimo ispisati treći korak algoritma, step=range(6) ako želimo ispisati prvih 5 koraka, uključujući i nulti korak. Varijabla redoslijed_vrhova nam omogućuje da sami unaprijed rasporedimo vrhove u tablici; ako ništa ne navedemo, vrhovi grafa G će biti raspoređeni onako kako su raspoređeni u listi G.vertices(). Varijabla ncol određuje u koliko stupaca će biti ispisane tablice za pojedine navedene korake algoritma. Funkcija FW_html nam omogućuje ispis u obliku tablice.
def FW_html(lista,redak,stupac,korak=' '):
lista=list(map(list,list(lista)))
stupac=[korak]+stupac
for k in range(len(lista)):
lista[k]=[redak[k]]+lista[k]
lista=[stupac]+lista
return table(lista)
def FW(graf,step,ncol,redoslijed_vrhova=None):
if redoslijed_vrhova==None:
redoslijed_vrhova=graf.vertices()
bridovi=graf.edges(labels=False)
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.edge_label(redoslijed_vrhova[i],redoslijed_vrhova[j])
matrica[j][i]=graf.edge_label(redoslijed_vrhova[i],redoslijed_vrhova[j])
elif (redoslijed_vrhova[j],redoslijed_vrhova[i]) in bridovi:
matrica[i][j]=graf.edge_label(redoslijed_vrhova[j],redoslijed_vrhova[i])
matrica[j][i]=graf.edge_label(redoslijed_vrhova[j],redoslijed_vrhova[i])
else:
matrica[i][j]=Infinity
matrica[j][i]=Infinity
koraci={0: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]=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>' + html(lista_tablica[i]) + '</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)
Nulti, treći i posljednji deveti korak Floyd-Warshallovog algoritma na težinskom grafu G1
FW(G1,step=[0,3,9],ncol=2,redoslijed_vrhova=[A,B,C,D,E,F,G,H,I])
Isprobajmo našu funkciju na dva primjera iz prezentacije
F1=Graph({"v1":{"v2":2},"v2":{"v3":3},"v3":{"v4":1}},weighted=True)
F1.plot(pos={"v1":[0,0],"v2":[1,0.5],"v3":[2,-0.5],"v4":[3,0.5]},edge_labels=True,graph_border=True,figsize=[5,4])
FW(F1,step=range(5),ncol=5)
F2=Graph({"v1":{"v2":15,"v3":5,"v4":1},"v2":{"v3":8,"v5":3},"v4":{"v5":2}},weighted=True)
F2.plot(pos={"v1":[0,3],"v2":[2,3.5],"v3":[1.2,2],"v4":[0.5,0],"v5":[4,0.3]},edge_labels=True,graph_border=True,figsize=[4,4])
FW(F2,step=range(6),ncol=3)
graf=Graph({A:{B:6,D:2,E:9,S:7},B:{C:2,E:3,S:9},
C:{E:2,F:6,S:1},D:{E:5,T:3},E:{F:7,T:9},
F:{T:6}},weighted=True)
pozicijeGraf={A:[2,4],B:[2,2],C:[2,0],D:[4,4],E:[4,2],F:[4,0],S:[0,2],T:[6,2]}
graf.plot(pos=pozicijeGraf,edge_labels=True,graph_border=True,figsize=[5,5])
graf.min_spanning_tree(algorithm="Kruskal")
graf.min_spanning_tree(algorithm="Prim_edge",starting_vertex=F)
Dolje su definicije funkcija rucni_Kruskal i rucni_Prim koje nam na izlazu daju tablice kakve mi dobivamo ručnim provođenjem algoritama. Parametar opcija može imati vrijednosti 'min' ili 'max' ovisno o tome želimo li minimalno ili maksimalno razapinjuće stablo.
def rucni_Kruskal(G,opcija='min'):
if opcija == 'min':
bridovi=G.min_spanning_tree(algorithm="Kruskal")
elif opcija == 'max':
bridovi=G.min_spanning_tree(weight_function=lambda e: -e[2],algorithm="Kruskal")
else:
return "Error: postoje samo 'min' i 'max' opcija za Kruskalov algoritam"
bridovi_stablo=list(map(lambda e: e[0:2],bridovi))
bridovi_tezine=list(map(lambda e: e[2], bridovi))
return table([['korak']+list(range(1,len(G))),['brid']+bridovi_stablo,['tezina']+bridovi_tezine])
rucni_Kruskal(graf)
rucni_Kruskal(graf,'max')
def rucni_Prim(G,v0,opcija='min'):
if opcija == 'min':
bridovi=G.min_spanning_tree(algorithm="Prim_edge",starting_vertex=v0)
elif opcija == 'max':
bridovi=G.min_spanning_tree(weight_function=lambda e: -e[2],algorithm="Prim_edge",starting_vertex=v0)
else:
return "Error: postoje samo 'min' i 'max' opcija za Primov algoritam"
bridovi_stablo=list(map(lambda e: e[0:2],bridovi))
bridovi_tezine=list(map(lambda e: e[2], bridovi))
return table([[str(v0)+' / '+'korak']+list(range(1,len(G))),['brid']+bridovi_stablo,['tezina']+bridovi_tezine])
rucni_Prim(graf,F)
rucni_Prim(graf,F,'max')
želimo li istaknuti minimalno ili maksimalno Kruskal stablo na početnom težinskom grafu
def Kruskal_stablo(G,opcija='min',raspored_vrhova=None,lay="circular"):
if opcija == 'min':
bridovi=G.min_spanning_tree(algorithm="Kruskal")
elif opcija == 'max':
bridovi=G.min_spanning_tree(weight_function=lambda e: -e[2],algorithm="Kruskal")
else:
return "Error: postoje samo 'min' i 'max' opcija za Kruskalov algoritam"
bridovi=map(lambda e: e[0:2], bridovi)
if raspored_vrhova==None:
slika=G.plot(edge_colors={"red":bridovi},layout=laj,edge_labels=True)
else:
slika=G.plot(edge_colors={"red":bridovi},pos=raspored_vrhova,edge_labels=True)
return slika
Kruskal_stablo(graf,raspored_vrhova=pozicijeGraf).show(figsize=[5,5])
Kruskal_stablo(graf,'max',raspored_vrhova=pozicijeGraf).show(figsize=[5,5])
želimo li istaknuti minimalno ili maksimalno Prim stablo na početnom težinskom grafu
def Prim_stablo(G,v0,opcija='min',raspored_vrhova=None,lay="circular"):
if opcija == 'min':
bridovi=G.min_spanning_tree(algorithm="Prim_edge",starting_vertex=v0)
elif opcija == 'max':
bridovi=G.min_spanning_tree(weight_function=lambda e: -e[2],algorithm="Prim_edge",starting_vertex=v0)
else:
return "Error: postoje samo 'min' i 'max' opcija za Primov algoritam"
bridovi=map(lambda e: e[0:2], bridovi)
if raspored_vrhova==None:
slika=G.plot(edge_colors={"red":bridovi},layout=laj,edge_labels=True)
else:
slika=G.plot(edge_colors={"red":bridovi},pos=raspored_vrhova,edge_labels=True)
return slika
Prim_stablo(graf,F,raspored_vrhova=pozicijeGraf).show(figsize=[5,5])
Prim_stablo(graf,F,'max',raspored_vrhova=pozicijeGraf).show(figsize=[5,5])
1. primjer
TSP1=Graph({"A":{"B":5,"C":5,"D":2,"E":3,"F":5},"B":{"C":1,"D":6,"E":6,"F":5},
"C":{"D":6,"E":6,"F":5},"D":{"E":3,"F":5},"E":{"F":2}},weighted=True)
TSP1nx=TSP1.networkx_graph()
nx.draw_circular(TSP1nx,with_labels=True,node_color='y')
nx.draw_networkx_edge_labels(TSP1nx,pos=nx.circular_layout(TSP1nx),edge_labels=nx.get_edge_attributes(TSP1nx,'weight'),
label_pos=0.4);
min_ciklus=TSP1.traveling_salesman_problem()
min_ciklus
min_ciklus.show(edge_labels=True)
2. primjer
TSP2=Graph({"A":{"B":4,"C":9,"D":12,"E":10,"F":3},"B":{"C":6,"D":8,"E":10,"F":6},
"C":{"D":5,"E":9,"F":12},"D":{"E":4,"F":11},"E":{"F":7}},weighted=True)
TSP2nx=TSP2.networkx_graph()
nx.draw_circular(TSP2nx,with_labels=True,node_color='y')
nx.draw_networkx_edge_labels(TSP2nx,pos=nx.circular_layout(TSP2nx),edge_labels=nx.get_edge_attributes(TSP2nx,'weight'),
label_pos=0.4);
min_ciklus2=TSP2.traveling_salesman_problem()
min_ciklus2
min_ciklus2.show(edge_labels=True)