verzija: SageMath 8.4
Kod konstrukcije digrafa vrijede sva ista pravila kao i kod konstrukcije grafa, jedino umjesto klase Graph treba koristiti klasu DiGraph.
from IPython.core.display import Image
digraf1=DiGraph({"u":["x"],"v":["u","x"],"w":["u"],"x":["w"]})
Kod crtanja digrafa vrijede ista pravila kao i kod crtanja grafa. Također, sve one opcije koje smo koristili kod crtanja grafa se mogu koristiti i kod crtanja digrafa pa ovdje nećemo toliko posebno spominjati sve te opcije.
digraf1.show(graph_border=True,vertex_color="yellow",pos={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]},figsize=[3,3])
outstupanj vrha v
digraf1.out_degree("v")
instupanj vrha v
digraf1.in_degree("v")
outstupnjevi svih vrhova
digraf1.out_degree()
digraf1.out_degree(labels=True)
instupnjevi svih vrhova
digraf1.in_degree()
digraf1.in_degree(labels=True)
outstupnjevi vrhova u i v
digraf1.out_degree(["u","v"])
digraf1.out_degree(["u","v"],labels=True)
instupnjevi vrhova u i v
digraf1.in_degree(["u","v"])
digraf1.in_degree(["u","v"],labels=True)
možemo analogno tražiti stupnjeve vrhova u pripadnom grafu
digraf1.degree(labels=True)
matrica susjedstva
vrhovi se smještaju u matricu susjedstva onim redom kojim su u listi digraf1.vertices()
digraf1.vertices()
digraf1.adjacency_matrix()
vrhovi iz kojih postoji luk prema vrhu x (in-susjedi vrha x)
digraf1.neighbors_in("x")
vrhovi prema kojima postoji luk iz vrha x (out-susjedi vrha x)
digraf1.neighbors_out("x")
susjedni vrhovi vrha x u pripadnom grafu
digraf1.neighbors("x")
da li je digraf povezan
digraf1.is_connected()
komponente povezanosti - ima samo jednu komponentu jer je digraf povezan
digraf1.connected_components()
da li je digraf dipovezan (jako povezan)
digraf1.is_strongly_connected()
dikomponente - digraf1 ima dvije dikomponente
digraf1.strongly_connected_components()
dikomponenta koja sadrži vrh x
digraf1.strongly_connected_component_containing_vertex("x")
digraf dikomponenata - vrhovi predstavljaju dikomponente, a iz prvog vrha prema drugom postoji luk jedino ako se iz prve dikomponente može ući u drugu dikomponentu.
dig1=digraf1.strongly_connected_components_digraph()
dig1.show(pos={dig1.vertices()[0]:[0,0],dig1.vertices()[1]:[20,0]},vertex_shape='h',vertex_size=5000)
dikomponente kao inducirani podgrafovi
dikomponente=digraf1.strongly_connected_components_subgraphs();dikomponente
graphs_list.show_graphs(dikomponente)
graphics_array([dikomponente[0].plot(graph_border=True),dikomponente[1].plot(graph_border=True)]).show(figsize=[4,2])
da li digraf nema usmjerenih ciklusa
digraf1.is_directed_acyclic()
najkraći usmjereni put od vrha v prema vrhu u i njegova duljina
digraf1.shortest_path("v","u")
digraf1.shortest_path_length("v","u")
ne postoji usmjereni put od vrha u prema vrhu v
digraf1.shortest_path("u","v")
digraf1.shortest_path_length("u","v")
najkraći usmjereni putovi od vrha u prema svim preostalim vrhovima i njihove udaljenosti
digraf1.shortest_paths("u")
digraf1.shortest_path_lengths("u")
digraf2=DiGraph({"u":["v"],"v":["u","x"],"w":["u","x"]})
digraf2.show(graph_border=True,vertex_color="yellow",pos={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]},figsize=[3,3])
matrica susjedstva
digraf2.vertices()
digraf2.adjacency_matrix()
digraf nije dipovezan
digraf2.is_strongly_connected()
digraf ima tri dikomponente
digraf2.strongly_connected_components()
digraf dikomponenata
dig2=digraf2.strongly_connected_components_digraph();dig2
dig2.show(pos={dig2.vertices()[0]:[0,0],dig2.vertices()[1]:[20,-10],dig2.vertices()[2]:[40,0]},
vertex_shape='h',vertex_size=3000,figsize=[5,3],ymax=3)
dikomponente kao inducirani podgrafovi
dikomponente2=digraf2.strongly_connected_components_subgraphs();dikomponente2
graphs_list.show_graphs(dikomponente2)
gr2=graphics_array([dikomponente2[0].plot(graph_border=True),dikomponente2[1].plot(graph_border=True,
pos={"u":[0,1],"v":[1,0]}),dikomponente2[2].plot(graph_border=True)])
gr2.show(figsize=[7,4])
digraf2 sadrži usmjerene cikluse
digraf2.is_directed_acyclic()
digraf3=DiGraph({"u":["v","v"],"v":["x"],"w":["u","x"]})
digraf3.show(graph_border=True,vertex_color="yellow",pos={"u":[0,1],"v":[1,1],"w":[0,0],"x":[1,0]},
vertex_size=500,figsize=[3,3])
matrica susjedstva
digraf3.vertices()
digraf3.adjacency_matrix()
digraf nije dipovezan
digraf3.is_strongly_connected()
digraf ima četiri dikomponente
digraf3.strongly_connected_components()
digraf ne sadrži usmjerene cikluse
digraf3.is_directed_acyclic()
digraf4=DiGraph({"u1":["u3"],"u2":["u1"],"u3":["u2"],"u4":["u1","u3"]})
digraf4.show(graph_border=True,vertex_color="yellow",pos={"u1":[0,0],"u2":[2,0],"u3":[1,1],"u4":[1,2]},vertex_size=400,figsize=[3,3])
matrica susjedstva
digraf4.vertices()
mat4=digraf4.adjacency_matrix();mat4
ukupni broj usmjerenih $(u_1,u_2)$-šetnji duljine 2
(mat4^2)[0,1]
ukupni broj usmjerenih $(u_2,u_1)$-šetnji duljine 2
(mat4^2)[1,0]
ukupni broj usmjerenih $(u_4,u_3)$-šetnji duljine 5
(mat4^5)[3,2]
digraf5=DiGraph({"v1":["v2","v4"],"v2":["v4"],"v3":["v2"],"v4":["v3"]})
digraf5.show(graph_border=True,vertex_color="yellow",pos={"v1":[0,1],"v2":[0,0],"v3":[1,0],"v4":[1,1]},vertex_size=400,figsize=[3,3])
digraf4 i digraf5
graphics_array([digraf4.plot(graph_border=True,vertex_color="yellow",pos={"u1":[0,0],"u2":[2,0],"u3":[1,1],"u4":[1,2]},
vertex_size=400),digraf5.plot(graph_border=True,vertex_color="yellow",
pos={"v1":[0,1],"v2":[0,0],"v3":[1,0],"v4":[1,1]},vertex_size=400)]).show(figsize=[6,4])
digraf4 i digraf5 su izomorfni digrafovi
digraf4.is_isomorphic(digraf5)
izomorfizam: $u_1\leftrightarrow v_2,\quad u_2\leftrightarrow v_3,\quad u_3\leftrightarrow v_4,\quad u_4\leftrightarrow v_1$
digraf4.is_isomorphic(digraf5,certificate=True)
ispitivanje izomornosti pomoću networkx modula
import networkx as nx
D4=nx.DiGraph()
D4.add_edges_from([('u1','u3'),('u2','u1'),('u3','u2'),('u4','u1'),('u4','u3')])
D5=nx.DiGraph()
D5.add_edges_from([('v1','v2'),('v1','v4'),('v2','v4'),('v3','v2'),('v4','v3')])
DM=nx.isomorphism.DiGraphMatcher(D4,D5)
DM.is_isomorphic()
DM.mapping
postoji samo jedan izomorfizam između digrafova digraf4 i digraf5
for u in DM.isomorphisms_iter():
print u
matrica permutacije
grupa=SymmetricGroup(4)
grupa([2,3,4,1])
P=grupa([2,3,4,1]).matrix().transpose();P
P*digraf4.adjacency_matrix()*P.transpose()==digraf5.adjacency_matrix()
turnir=DiGraph({'a':['c','d'],'b':['a','c','e'],'c':['f'],'d':['b','c'],'e':['a','c','d','f'],'f':['a','b','d']})
turpoz={'a':[2,0],'b':[4,0],'c':[6,2],'d':[4,4],'e':[2,4],'f':[0,2]}
turnir.show(pos=turpoz,vertex_color="yellow",figsize=(5,5),vertex_size=600,ymax=4.2)
vektor uspjeha turnira
turnir.vertices()
turnir.out_degree(labels=True)
turnir.out_degree()
najkraći usmjereni put od vrha a do vrha d
turnir.shortest_path("a","d")
najkraći usmjereni put od vrha a do vrha e
turnir.shortest_path("a","e")
najkraći put istaknut na digrafu
def najkraci_put(G,v1,v2,raspored_vrhova=None,tezine=False,laj="circular",velicina_vrha=300):
put=G.shortest_path(v1,v2,by_weight=tezine)
ostali_vrhovi=list(set(G.vertices()).difference(set([v1,v2])))
bridovi=G.edges(labels=False)
bridovi_put=[]
for i in xrange(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_color={"cyan":[v1,v2],"yellow":ostali_vrhovi},
layout=laj,edge_labels=tezine,vertex_size=velicina_vrha)
else:
slika=G.plot(edge_colors={"red":bridovi_put},vertex_color={"cyan":[v1,v2],"yellow":ostali_vrhovi},
pos=raspored_vrhova,edge_labels=tezine,vertex_size=velicina_vrha)
return slika
najkraci_put(turnir,"a","d",turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
najkraci_put(turnir,"a","e",turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
Za traženje usmjerenih ciklusa u bilo kojem digrafu, dolje je implementiran Brentov algoritam. Taj algoritam za zadani digraf daje neki, na slučajni način pronađeni, usmjereni ciklus.
def usmjereni_ciklus(D):
if not(D.is_directed_acyclic): return "nema usmjerenih ciklusa"
x0 = choice(D.vertices())
f = {}
for v in D.vertices():
f[v] = choice(D.neighbors_out(v))
#racunanje lambde
power = 1
lam = 1
tortoise = x0
hare = f[x0]
while tortoise != hare:
if power == lam:
tortoise = hare
power *= 2
lam = 0
hare = f[hare]
lam += 1
# mu = pozicija prvog ponavljanja duljine lambda
mu = 0
tortoise = hare = x0
for i in xrange(lam):
hare = f[hare]
while tortoise != hare:
tortoise = f[tortoise]
hare = f[hare]
mu += 1
ciklus=[tortoise]
for i in xrange(lam):
tortoise=f[tortoise]
ciklus.append(tortoise)
return ciklus
nekoliko usmjerenih ciklusa u našem promatranom turniru
for i in xrange(5):
print usmjereni_ciklus(turnir)
ako želimo usmjereni ciklus istaknuti na digrafu
def usmjereni_ciklus_digraf(D,raspored_vrhova=None,laj="circular",velicina_vrha=300):
ciklus = usmjereni_ciklus(D)
vrhovi2 = list(set(D.vertices()).difference(set(ciklus)))
lukovi_ciklus = []
for i in xrange(len(ciklus)-1):
lukovi_ciklus.append((ciklus[i],ciklus[i+1]))
if raspored_vrhova == None:
slika = D.plot(edge_colors={"red":lukovi_ciklus},vertex_colors={"red":ciklus[0:-1],"yellow":vrhovi2},
layout=laj,vertex_size=velicina_vrha)
else:
slika = D.plot(edge_colors={"red":lukovi_ciklus},vertex_colors={"red":ciklus[0:-1],"yellow":vrhovi2},
pos=raspored_vrhova,vertex_size=velicina_vrha)
return slika
nekoliko usmjerenih ciklusa istaknutih na digrafu
usmjereni_ciklus_digraf(turnir,raspored_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
usmjereni_ciklus_digraf(turnir,raspored_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
usmjereni_ciklus_digraf(turnir,raspored_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
usmjereni_ciklus_digraf(turnir,raspored_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5],ymax=4.2)
promatrani turnir je Hamiltonov digraf
turnir.is_hamiltonian()
turnir.hamiltonian_cycle().show()
Hamiltonov ciklus istaknut na digrafu
def hamiltonov_ciklus(G,pozicije_vrhova=None,laj="spring",boja="red",velicina_vrha=300):
if not(G.is_hamiltonian()):
return "Error: Graf nije Hamiltonov"
bridovi=G.hamiltonian_cycle().edges(labels=False)
if pozicije_vrhova==None:
slika=G.plot(graph_border=True,edge_colors={boja:bridovi},layout=laj,vertex_size=velicina_vrha)
else:
slika=G.plot(graph_border=True,edge_colors={boja:bridovi},pos=pozicije_vrhova,vertex_size=velicina_vrha)
return slika
hamiltonov_ciklus(turnir,pozicije_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5])
Neki Hamiltonov put u promatranom turniru
def usmjereni_hamiltonov_put(G):
try:
H=G.copy()
H.add_edges(zip(G.vertices(),['vrh']*G.num_verts()))
H.add_edges(zip(['vrh']*G.num_verts(),G.vertices()))
ciklus=H.hamiltonian_cycle()
ciklus.delete_vertex('vrh')
return ciklus.edges(labels=False)
except ValueError:
return "Error: Digraf nema Hamiltonov put"
usmjereni_hamiltonov_put(turnir)
Neki Hamiltonov put istaknut na digrafu
def usmjereni_hamiltonov_put_digraf(G,pozicije_vrhova=None,laj="spring",boja="red",velicina_vrha=300):
bridovi = usmjereni_hamiltonov_put(G)
if pozicije_vrhova==None:
slika=G.plot(graph_border=True,edge_colors={boja:bridovi},layout=laj,vertex_size=velicina_vrha)
else:
slika=G.plot(graph_border=True,edge_colors={boja:bridovi},pos=pozicije_vrhova,vertex_size=velicina_vrha)
return slika
usmjereni_hamiltonov_put_digraf(turnir,pozicije_vrhova=turpoz,velicina_vrha=600).show(figsize=[5,5])
promatrani turnir nije Eulerov digraf
turnir.is_eulerian()
trokut1=DiGraph({"a":["b"],"b":["c"],"c":["a"]})
trokut2=DiGraph({"a":["b","c"],"b":["c"]})
trokutpoz={"a":[0,0],"b":[2,0],"c":[1,1.5]}
graphics_array([trokut1.plot(graph_border=true,pos=trokutpoz),trokut2.plot(graph_border=true,pos=trokutpoz)]).show(figsize=[6,4])
trokut1 je Eulerov digraf, a trokut2 nije Eulerov digraf
trokut1.is_eulerian()
trokut2.is_eulerian()
trokut1 je Hamiltonov digraf, a trokut2 nije Hamiltonov digraf
trokut1.is_hamiltonian()
trokut2.is_hamiltonian()
međutim, trokut2 ipak ima usmjereni Hamiltonov put
usmjereni_hamiltonov_put_digraf(trokut2,trokutpoz).show(figsize=[3,3])
def snaga_vrha(T,v0):
indeks=T.vertices().index(v0)
matrica=T.adjacency_matrix()+(T.adjacency_matrix())^2
return sum(matrica.row(indeks))
def rang_lista(turnir,izlaz="html"):
rezultat=map(lambda v: [v,turnir.out_degree(v),snaga_vrha(turnir,v)],turnir.vertices())
rezultat=sorted(rezultat,key=lambda x: x[2],reverse=True)
if izlaz == "lista":
return rezultat
elif izlaz == "html":
return table([['igrači','broj pobjeda','snaga pobjeda']]+rezultat)
rang lista za turnir
turnir.show(pos=turpoz,vertex_color="yellow",figsize=(5,5),vertex_size=600,ymax=4.2)
def rang_lista(turnir,izlaz="html"):
rezultat=map(lambda v: [v,turnir.out_degree(v),snaga_vrha(turnir,v)],turnir.vertices())
rezultat=sorted(rezultat,key=lambda x: x[2],reverse=True)
if izlaz == "lista":
return rezultat
elif izlaz == "html":
return table([['igraci','broj pobjeda','snaga pobjeda']]+rezultat)
rang_lista(turnir)
rang_lista(turnir,izlaz="lista")
rang lista za turnir2
turnir2=DiGraph({"A":["B","C","D"],"B":["D","E"],"C":["B","D"],"E":["A","C","D"]})
turnir2.plot(layout="circular",vertex_size=400,vertex_color="yellow").show(figsize=(3,3))
rang_lista(turnir2)
rang_lista(turnir2,izlaz="lista")
rang lista za turnir3
turnir3=DiGraph({"A":["C","D"],"B":["A","C","E"],"C":["D"],"D":["B"],"E":["A","C","D"]})
turnir3.plot(layout="circular",vertex_size=400,vertex_color="yellow").show(figsize=(3,3))
rang_lista(turnir3)
U ovom dijelu je napravljena implementacija Bellman-Fordovog algoritma (posebno prilagođena ručnom rješavanju zadataka). Također, implementirana je i poboljšana verzija Dijkstrinog algoritma koja je također posebno prilagođena ručnom rješavanju zadataka. Inače, Dijkstrin algoritam je implementiran u SAGE-u i već smo ga koristili kod težinskih grafova. Bellman-Fordov algoritam je implementiran samo za težinske digrafove, a Dijkstrin algoritam je implementiran za težinske grafove i digrafove.
def BellmanFord(D,v0):
tezina_brida={}
for e in D.edges():
tezina_brida[(e[0],e[1])]=e[2]
P = {}
udaljenost = {}
V = D.vertices()
E = D.edges()
udaljenost[0]={}
for v in V:
if v == v0:
udaljenost[0][v] = 0
P[v] = None
else:
udaljenost[0][v] = Infinity
P[v] = None
for i in range(1, len(V)+1):
udaljenost[i]=copy(udaljenost[i-1])
promjena=False
for v in V:
for u in D.neighbors_in(v):
if udaljenost[i][v] > udaljenost[i-1][u]+tezina_brida[(u,v)]:
udaljenost[i][v] = udaljenost[i-1][u]+tezina_brida[(u,v)]
P[v]=u
promjena=True
if promjena==False:
break
if udaljenost[len(udaljenost)-1]!=udaljenost[len(udaljenost)-2]: print "error: digraf ima negativne cikluse"
return (udaljenost[len(udaljenost)-1], P)
def Dijkstra_digraf(D,v0):
MM=min(map(lambda x: x[2],D.edges()))
tezina_brida={}
for e in D.edges():
tezina_brida[(e[0],e[1])]=e[2]
P={}
udaljenost={}
Q=set(D.vertices())
for v in Q:
if v == v0:
udaljenost[v]=0
P[v]=None
else:
udaljenost[v]=Infinity
P[v]=None
while len(Q)>0:
m=min([udaljenost[u] for u in Q])
if m == Infinity: break
v=choice(filter(lambda x: udaljenost[x]==m, Q))
Q.remove(v)
for u in set(D.neighbors_out(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 težinama"
return (udaljenost,P)
def Dijkstra_graf(G,v0):
MM=min(map(lambda x: x[2],G.edges()))
tezina_brida={}
for e in G.edges():
tezina_brida[(e[0],e[1])]=e[2]
tezina_brida[(e[1],e[0])]=e[2]
P={}
udaljenost={}
Q=set(G.vertices())
for v in Q:
if v == v0:
udaljenost[v]=0
P[v]=None
else:
udaljenost[v]=Infinity
P[v]=None
while len(Q)>0:
m=min([udaljenost[u] for u in Q])
if m == Infinity: break
v=choice(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 težinama"
return (udaljenost,P)
def rucni_BellmanFord(D,v0,poredak=None):
koraci={}
if poredak==None:
V=D.vertices()
else:
V=poredak
tezina_brida={}
for e in D.edges():
tezina_brida[(e[0],e[1])]=e[2]
koraci[0]={}
for v in V:
if v==v0:
koraci[0][v]=('-',0)
else:
koraci[0][v]=('-',Infinity)
for i in xrange(1,len(V)+1):
koraci[i]=copy(koraci[i-1])
promjena=False
for v in V:
for u in D.neighbors_in(v):
if koraci[i][v][1] > koraci[i-1][u][1]+tezina_brida[(u,v)]:
koraci[i][v] = (u, koraci[i-1][u][1]+tezina_brida[(u,v)])
promjena=True
if promjena==False:
break
tablica=[]
for i in xrange(len(koraci)):
redak=[i]
for v in V:
redak.append(koraci[i][v])
tablica.append(redak)
tablica=[['vrh | korak']+V]+tablica
tablica=map(list,zip(*tablica))
if koraci[len(koraci)-1]!=koraci[len(koraci)-2]: print "error: digraf ima negativne cikluse"
return table(tablica)
def rucni_Dijkstra_digraf(D,v0,poredak=None):
if poredak==None:
V=D.vertices()
else:
V=poredak
koraci={}
tezina_brida={}
for e in D.edges():
tezina_brida[(e[0],e[1])]=e[2]
MM=min(map(lambda x: x[2],D.edges()))
koraci[0]={}
for v in V:
if v==v0:
koraci[0][v]=('-',0)
else:
koraci[0][v]=('-',Infinity)
Q=set(D.vertices())
k=1
while len(Q)>1:
m=min([koraci[k-1][x][1] for x in Q])
if m==Infinity:
break
else:
koraci[k]=copy(koraci[k-1])
w=choice(filter(lambda x: koraci[k-1][x][1]==m, Q))
Q.remove(w)
koraci[k][w]='*'
for v in set(D.neighbors_out(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 xrange(len(koraci)):
redak=[i]
for v in V:
redak.append(koraci[i][v])
tablica.append(redak)
tablica=[['vrh | korak']+V]+tablica
tablica=map(list,zip(*tablica))
if MM<0: print "error: Dijkstra ne radi ispravno na negativnim tezinama"
return table(tablica)
def rucni_Dijkstra_graf(G,v0, poredak=None):
if poredak==None:
V=G.vertices()
else:
V=poredak
koraci={}
tezina_brida={}
for e in G.edges():
tezina_brida[(e[0],e[1])]=e[2]
tezina_brida[(e[1],e[0])]=e[2]
koraci[0]={}
for v in V:
if v==v0:
koraci[0][v]=('-',0)
else:
koraci[0][v]=('-',Infinity)
Q=set(G.vertices())
k=1
while len(Q)>1:
m=min([koraci[k-1][x][1] for x in Q])
if m==Infinity:
break
else:
koraci[k]=copy(koraci[k-1])
w=choice(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 xrange(len(koraci)):
redak=[i]
for v in V:
redak.append(koraci[i][v])
tablica.append(redak)
tablica=[['vrh | korak']+V]+tablica
tablica=map(list,zip(*tablica))
return table(tablica)
Funkcija stablo_min_putova_DSTG služi za isticanje stabla najkraćih putova od nekog vrha na težinskom grafu ili digrafu na kojeg je primijenjen neki od naših implementiranih algoritama. Stoga opcija algoritam može imati neku od tri vrijednosti: BellmanFord, Dijkstra_digraf, Dijkstra_graf. Pritom, prva dva algoritma primijenjujemo na težinske digrafove, a zadnji na težinske grafove.
def stablo_min_putova_DSTG(D,v0,algoritam=BellmanFord,raspored_vrhova=None,laj="circular",brid0="red",vrh0="yellow",velicina=300):
P=algoritam(D,v0)[1]
bridovi=[]
for x in P:
if D.is_directed():
if P[x]!=None: bridovi.append((P[x],x))
else:
if P[x]!=None:
if (P[x],x) in D.edges(labels=False):
bridovi.append((P[x],x))
else:
bridovi.append((x,P[x]))
ostali_bridovi=list(set(D.edges(labels=False)).difference(set(bridovi)))
if raspored_vrhova==None:
slika=D.plot(edge_colors={brid0:bridovi,"black":ostali_bridovi},vertex_color=vrh0,layout=laj,
edge_labels=True,vertex_size=velicina)
else:
slika=D.plot(edge_colors={brid0:bridovi,"black":ostali_bridovi},vertex_color=vrh0,pos=raspored_vrhova,
edge_labels=True,vertex_size=velicina)
return slika
def graf_string(G,slika=None,fontV=12,fontE=12,xy=None,bojaVrha="white",bojaBrida="black",debljinaV=1,debljinaE=1,
bojaTezine="black",bojeVrhova=None,bojeBridova=None,tezine=True,dekor=False,d={},kut={}):
"""Pretvara sage graf G u graphviz format.
slika -> dimenzije nacrtane slike na izlazu
fontV -> velicina fonta oznake vrhova
fontE -> velicina fonta tezina bridova
xy -> rjecnik koordinata vrhova grafa G
bojaVrha -> boje svih vrhova na slici
bojaBrida -> boje svih bridova na slici
debljinaV -> debljina linije kod vrhova
debljinaE -> debljina bridova
bojaTezine -> boja u kojoj ce biti ispisane tezine bridova
bojeVrhova -> rjecnik boja za svaki pojedini vrh ako zelimo da vrhovi budu razlicito obojani
bojeBridova -> rjecnik boja za svaki pojedini brid ako zelimo bridove obojati u razlicitim bojama
tezine -> da li ce tezine bridova biti ispisane ili nece
dekor -> dekorirani ili nedekorirani ispis tezina
d -> udaljenost tezine brida od njegovog kraja
kut -> kut za koji je rotirana tezina brida oko njegovog kraja"""
if G.is_directed():
rijec='digraph {\n '
strelica='>'
else:
rijec='graph {\n '
strelica='-'
if slika!=None:
rijec+='size="%d,%d!"\n ' % slika
rijec+='node [shape=circle width=0 height=0 margin=0 style=filled fontsize=%d penwidth=%d];\n ' % (fontV,debljinaV)
if dekor:
rijec+=('edge[color=%s,fontcolor=%s overlap=false splines=true decorate=true fontsize=%d penwidth=%d];\n '
% (bojaBrida,bojaTezine,fontE,debljinaE))
else:
rijec+=('edge[color=%s,fontcolor=%s overlap=false splines=true,fontsize=%d penwidth=%d];\n '
% (bojaBrida,bojaTezine,fontE,debljinaE))
if bojeVrhova==None:
bojeVrhova={}
for v in G.vertices():
bojeVrhova[v]=bojaVrha
if xy!=None:
for v in G.vertices():
rijec+='"%s" [label="%s" pos="%d,%d!" fillcolor=%s];\n ' % (str(v),str(v),xy[v][0],xy[v][1],bojeVrhova[v])
else:
for v in G.vertices():
rijec+='"%s" [label="%s" style=filled fillcolor=%s];\n ' % (str(v),str(v),bojeVrhova[v])
if bojeBridova==None:
bojeBridova={}
for e in G.edges():
bojeBridova[(e[0],e[1])]=bojaBrida
if tezine==False:
for e in G.edges():
rijec+='"%s" -> "%s" [color=%s];\n ' % (str(e[0]),str(e[1]),bojeBridova[(e[0],e[1])])
if tezine==True:
if d=={}:
for e in G.edges():
rijec+='"%s" -%s "%s" [color=%s label="%d"];\n ' % (str(e[0]),strelica,str(e[1]),bojeBridova[(e[0],e[1])],e[2])
else:
for e in G.edges():
if (e[0],e[1]) in d.keys():
rijec+=('"%s" -%s "%s" [color=%s headlabel="%d" labeldistance=%d labelangle=%d];\n '
% (str(e[0]),strelica,str(e[1]),bojeBridova[(e[0],e[1])],e[2],d[(e[0],e[1])],kut[(e[0],e[1])]))
else:
rijec+=('"%s" -%s "%s" [color=%s label="%d"];\n '
% (str(e[0]),strelica,str(e[1]),bojeBridova[(e[0],e[1])],e[2]))
rijec+='}'
return rijec
def crtaj_graphviz(G,ime,slika=None,fontV=12,fontE=12,xy=None,bojaVrha="white",bojaBrida="black",debljinaV=1,debljinaE=1,
bojaTezine="black",bojeVrhova=None,bojeBridova=None,tezine=True,dekor=False,d={},kut={}):
"""Crta sage graf G pomocu graphviza.
ime -> ime datoteke u koju ce biti spremljena slika
slika -> dimenzije nacrtane slike na izlazu
fontV -> velicina fonta oznake vrhova
fontE -> velicina fonta tezina bridova
xy -> rjecnik koordinata vrhova grafa G
bojaVrha -> boje svih vrhova na slici
bojaBrida -> boje svih bridova na slici
debljinaV -> debljina linije kod vrhova
debljinaE -> debljina bridova
bojaTezine -> boja u kojoj ce biti ispisane tezine bridova
bojeVrhova -> rjecnik boja za svaki pojedini vrh ako zelimo da vrhovi budu razlicito obojani
bojeBridova -> rjecnik boja za svaki pojedini brid ako zelimo bridove obojati u razlicitim bojama
tezine -> da li ce tezine bridova biti ispisane ili nece
dekor -> dekorirani ili nedekorirani ispis tezina
d -> udaljenost tezine brida od njegovog kraja
kut -> kut za koji je rotirana tezina brida oko njegovog kraja"""
rijec=graf_string(G,slika,fontV,fontE,xy,bojaVrha,bojaBrida,debljinaV,debljinaE,bojaTezine,bojeVrhova,bojeBridova,tezine,dekor,d,kut)
os.system("echo '%s' | dot -Kfdp -Tpng > %s" % (rijec,ime))
return Image(filename=ime)
def graphviz_stablo_min_putova(D,v0,ime,algoritam=BellmanFord,slika=None,fontV=12,fontE=12,xy=None,debljinaV=1,debljinaE=1,
vrh0="yellow",vrh1="pink",brid0="red",brid1="black",bojaTezine="black",tezine=True,
dekor=False,d={},kut={}):
"""Istice stablo najkracih putova od vrha v0 prema svim preostalim vrhovima na tezinskom digrafu (ili grafu) na
kojeg je primijenjen neki od nasih implementiranih algoritama.
Opcija 'algoritam' moze imati neku od tri vrijednosti: BellmanFord, Dijkstra_digraf, Dijkstra_graf.
Slika se crta u graphviz formatu.
ime -> ime datoteke u koju ce biti spremljena slika
slika -> dimenzije nacrtane slike na izlazu
fontV -> velicina fonta oznake vrhova
fontE -> velicina fonta tezina bridova
xy -> rjecnik koordinata vrhova grafa G
debljinaV -> debljina linije kod vrhova
debljinaE -> debljina bridova
vrh0 -> boje vrha v0
vrh1 -> boja preostalih vrhova
brid0 -> boja bridova koji pripadaju stablu
brid1 -> boja bridova koji ne pripadaju stablu
bojaTezine -> boja u kojoj ce biti ispisane tezine bridova
tezine -> da li ce tezine bridova biti ispisane ili nece
dekor -> dekorirani ili nedekorirani ispis tezina
d -> udaljenost tezine brida od njegovog kraja
kut -> kut za koji je rotirana tezina brida oko njegovog kraja"""
P=algoritam(D,v0)[1]
bridovi=[]
for x in P:
if D.is_directed():
if P[x]!=None: bridovi.append((P[x],x))
else:
if P[x]!=None:
if (P[x],x) in D.edges(labels=False):
bridovi.append((P[x],x))
else:
bridovi.append((x,P[x]))
ostali_vrhovi=D.vertices()
ostali_vrhovi.remove(v0)
bojeVrhova={v0:vrh0}
for v in ostali_vrhovi:
bojeVrhova[v]=vrh1
bojeBridova={}
for e in D.edges():
if (e[0],e[1]) in bridovi:
bojeBridova[(e[0],e[1])]=brid0
else:
bojeBridova[(e[0],e[1])]=brid1
rijec=graf_string(D,slika,fontV,fontE,xy,vrh1,brid1,debljinaV,debljinaE,bojaTezine,bojeVrhova,bojeBridova,tezine,dekor,d,kut)
os.system("echo '%s' | dot -Kfdp -Tpng > %s" % (rijec,ime))
return Image(filename=ime)
digraf6 - Bellman-Ford i Dijkstra dobro rade
var('v1 v2 v3 v4 v5 v6 v7 v8')
digraf6=DiGraph({v1:{v2:1,v5:4},
v2:{v3:1,v5:3},
v3:{v4:5,v5:1},
v4:{v3:1},
v5:{v3:1,v4:1}
},weighted=True)
D6pos={v1:[0,2],v2:[2,4],v3:[5,4],v4:[6,0],v5:[2,0]}
rucni_BellmanFord(digraf6,v1,[v1,v2,v3,v4,v5])
BellmanFord(digraf6,v1)
stablo_min_putova_DSTG(digraf6,v1,algoritam=BellmanFord,raspored_vrhova=D6pos,velicina=2000).show(figsize=[6,4])
ljepša slika
graphviz_stablo_min_putova(digraf6,v1,"D6.png",algoritam=BellmanFord,slika=(7,6),xy=D6pos,vrh0="yellow",vrh1="pink",
brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
rucni_Dijkstra_digraf(digraf6,v1,[v1,v2,v3,v4,v5])
Dijkstra_digraf(digraf6,v1)
stablo_min_putova_DSTG(digraf6,v1,algoritam=Dijkstra_digraf,raspored_vrhova=D6pos,velicina=1500).show(figsize=[6,4])
ljepša slika
graphviz_stablo_min_putova(digraf6,v1,"D6dva.png",algoritam=Dijkstra_digraf,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
pogledajmo još iz vrha $v_4$ kao početnog vrha
rucni_BellmanFord(digraf6,v4,[v1,v2,v3,v4,v5])
BellmanFord(digraf6,v4)
stablo_min_putova_DSTG(digraf6,v4,algoritam=BellmanFord,raspored_vrhova=D6pos,velicina=1500).show(figsize=[6,4])
ljepša slika
graphviz_stablo_min_putova(digraf6,v4,"D6tri.png",algoritam=BellmanFord,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
rucni_Dijkstra_digraf(digraf6,v4,[v1,v2,v3,v4,v5])
Dijkstra_digraf(digraf6,v4)
graphviz_stablo_min_putova(digraf6,v4,"D6cetiri.png",algoritam=Dijkstra_digraf,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
digraf7 - zbog negativnih težina Dijkstra ne radi dobro; a kako nema negativnih ciklusa, Bellman-Ford radi ispravno
digraf7=DiGraph({v1:{v2:1,v5:4},
v2:{v3:2,v5:3},
v3:{v4:5,v5:4},
v4:{v3:-1},
v5:{v3:1,v4:-1}
},weighted=True)
rucni_BellmanFord(digraf7,v1,[v1,v2,v3,v4,v5])
BellmanFord(digraf7,v1)
graphviz_stablo_min_putova(digraf7,v1,"D7.png",algoritam=BellmanFord,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
rucni_Dijkstra_digraf(digraf7,v1,[v1,v2,v3,v4,v5])
Dijkstra_digraf(digraf7,v1)
graphviz_stablo_min_putova(digraf7,v1,"D7dva.png",algoritam=Dijkstra_digraf,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
digraf8 - ima usmjereni ciklus negativne težine. Stoga, niti Bellman-Ford, niti Dijkstra ne rade dobro na ovom digrafu.
digraf8=DiGraph({v1:{v2:1,v5:4},
v2:{v3:2,v5:3},
v3:{v4:5,v5:1},
v4:{v3:-1},
v5:{v3:1,v4:-1}
},weighted=True)
rucni_BellmanFord(digraf8,v1)
BellmanFord(digraf8,v1)
graphviz_stablo_min_putova(digraf8,v1,"D8.png",algoritam=BellmanFord,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
rucni_Dijkstra_digraf(digraf8,v1)
Dijkstra_digraf(digraf8,v1)
graphviz_stablo_min_putova(digraf8,v1,"D8dva.png",algoritam=Dijkstra_digraf,slika=(7,6),xy=D6pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v4,v3):10,(v3,v4):15,(v5,v3):15,(v3,v5):15,(v1,v5):10},
kut={(v4,v3):-3,(v3,v4):-1,(v5,v3):-1,(v3,v5):-2,(v1,v5):-5})
digraf9 - digraf sadrži usmjereni ciklus negativne težine koji se dvaput obišao u toku izvođenja Bellman-Fordovog algoritma i naravno dobivamo krive rezultate. U ovom slučaju Dijkstra radi ispravno, ali to je samo splet okolnosti zbog same strukture digrafa koja ovdje dobro odgovara Dijkstrinom algoritmu iz vrha $v_1$ (općenito ne možemo garantirati točnost rezultata).
digraf9=DiGraph({v1:{v2:3},
v2:{v3:-2},
v3:{v4:1},v4:{v2:-1,v5:1},
v5:{v6:1},v6:{v7:1},v7:{v8:1}},weighted=True)
D9pos={v1:[0,0.5],v2:[2,0.4],v3:[4,1],v4:[6,0.4],v5:[8,0.4],v6:[10,0.3],v7:[12,1],v8:[8,2]}
rucni_BellmanFord(digraf9,v1,[v1,v2,v3,v4,v5,v6,v7,v8])
BellmanFord(digraf9,v1)
stablo_min_putova_DSTG(digraf9,v1,algoritam=BellmanFord,raspored_vrhova=D9pos,velicina=400).show(xmax=15,ymax=3,ymin=-1,figsize=(10,15))
graphviz_stablo_min_putova(digraf9,v1,"D9.png",algoritam=BellmanFord,slika=(9,8),xy=D9pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",fontV=16,debljinaE=2,fontE=16)
rucni_Dijkstra_digraf(digraf9,v1,[v1,v2,v3,v4,v5,v6,v7,v8])
Dijkstra_digraf(digraf9,v1)
stablo_min_putova_DSTG(digraf9,v1,algoritam=Dijkstra_digraf,raspored_vrhova=D9pos,
velicina=400).show(xmax=15,ymax=3,ymin=-1,figsize=(10,15))
graphviz_stablo_min_putova(digraf9,v1,"D9dva.png",algoritam=Dijkstra_digraf,slika=(9,8),xy=D9pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",fontV=16,debljinaE=2,fontE=16)
digraf10 - iako ima usmjereni ciklus negativne težine, Bellman-Ford radi ispravno iz vrha $v_1$ kao početnog vrha, zato jer se taj negativni ciklus ne može doseći iz vrha $v_1$ pa su rezultati točni i možemo garantirati njihovu točnost. I Dijkstra također radi ispravno iz vrha $v_1$, ali općenito ne možemo garantirati njegovu točnost.
digraf10=DiGraph({v1:{v4:1},
v2:{v1:1,v3:1},
v3:{v2:-2,v4:1}},weighted=True)
D10pos={v1:[0,2],v2:[4,3],v3:[7,3.5],v4:[1,0]}
rucni_BellmanFord(digraf10,v1,[v1,v2,v3,v4])
BellmanFord(digraf10,v1)
graphviz_stablo_min_putova(digraf10,v1,"D10.png",algoritam=BellmanFord,slika=(7,6),xy=D10pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v2,v3):10,(v3,v2):10,(v1,v4):8},kut={(v2,v3):-2,(v3,v2):-2,(v1,v4):-5})
rucni_Dijkstra_digraf(digraf10,v1)
Dijkstra_digraf(digraf10,v1)
graphviz_stablo_min_putova(digraf10,v1,"D10dva.png",algoritam=Dijkstra_digraf,slika=(7,6),xy=D10pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",
d={(v2,v3):10,(v3,v2):10,(v1,v4):8},kut={(v2,v3):-2,(v3,v2):-2,(v1,v4):-5})
algoritam Dijkstra_graf primijenjen na težinski graf
var('A,B,C,D,E,F,G,H,I')
graf=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)
grafPOS={A:[-2,0],B:[-2,2],C:[-2,-2],D:[0,2],E:[0,0],F:[0,-2],G:[2,2],H:[2,0],I:[2,-2]}
rucni_Dijkstra_graf(graf,A,[A,B,C,D,E,F,G,H,I])
Dijkstra_graf(graf,A)
stablo_min_putova_DSTG(graf,A,algoritam=Dijkstra_graf,raspored_vrhova=grafPOS,velicina=300).show(figsize=[4,4])
graphviz_stablo_min_putova(graf,A,"tezinski.png",algoritam=Dijkstra_graf,xy=grafPOS,slika=(4,4),vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",bojaTezine="black",fontE=16,debljinaE=1.5)
acDigraf=DiGraph({2:[1,4],3:[1,4,5],4:[5],6:[1,4],7:[2,3,6,8],8:[5,6]})
acPOS={1:[0,0],2:[8,0],3:[2,-2],4:[6,-2],5:[4,-4],6:[2,2],7:[6,2],8:[4,4]}
acDigraf.show(pos=acPOS)
digraf jest aciklički
acDigraf.is_directed_acyclic()
topološki sortirani vrhovi promatranog acikličkog digrafa
acDigraf.topological_sort()
graf2=graphs.Grid2dGraph(3,3)
graf2.relabel()
graf2.show(save_pos=True,figsize=[3,3])
jedna jaka orijentacija na promatranom grafu
jaki_graf2=graf2.strong_orientation();jaki_graf2
jaki_graf2.show(pos=graf2.get_pos(),figsize=[3,3])
jedna jaka orijentacija na kubnom grafu
kub=graphs.CubeGraph(3)
kub.relabel()
kub.strong_orientation().show(figsize=[3,3])
var('i u x v y w z p')
mreza1=DiGraph({i:{u:7,x:2},u:{x:1,v:5},x:{y:4},
v:{x:3,y:2,w:4},y:{z:5},w:{z:3,p:3},
z:{p:6}},weighted=True)
mreza1_pos={i:[0,2],x:[2,0],y:[6,0],z:[10,0],p:[12,2],u:[2,4],v:[6,4],w:[10,4]}
mreza1.show(pos=mreza1_pos,edge_labels=True,figsize=(7,4))
vrijednost maksimalnog protoka od izvora $i$ do ponora $p$
mreza1.flow(i,p)
možemo dobiti i digraf u kojemu će težina luka biti količina protoka kroz pojedini luk. Ukoliko kroz neki luk nema protoka, taj luk se neće nacrtati.
mreza1.flow(i,p,value_only=False)
mreza1.flow(i,p,value_only=False)[1].show(pos=mreza1_pos,edge_labels=True,figsize=(7,4))
možemo dobiti potrebne informacije u obliku tablice ako definiramo svoju funkciju
def maksimalni_protok(mreza,v0,v1):
protok=mreza.flow(v0,v1,value_only=False)
lukovi=mreza.edges(labels=False)
lukovi2=protok[1].edges(labels=False)
kapacitet_luk=[]
protok_luk=[]
for e in lukovi:
kapacitet_luk.append(mreza.edge_label(e[0],e[1]))
if (e[0],e[1]) in lukovi2:
protok_luk.append(protok[1].edge_label(e[0],e[1]))
else:
protok_luk.append(0)
lukovi=['luk']+lukovi
kapacitet_luk=['kapacitet luka']+kapacitet_luk
protok_luk=['protok kroz luk']+protok_luk
tablica=[lukovi,kapacitet_luk,protok_luk]
tablica=map(list,zip(*tablica))
print "Vrijednost maksimalnog protoka: ", protok[0]
return table(tablica)
maksimalni_protok(mreza1,i,p)
možemo općenito tražiti vrijednost maksimalnog protoka između bilo koja dva vrha koja nisu nužno izvor i ponor
mreza1.flow(i,v)
maksimalni_protok(mreza1,i,v)
mreza1.flow(u,z)
maksimalni_protok(mreza1,u,z)
od vrha $z$ do vrha $u$ ne postoji protok
mreza1.flow(z,u)
maksimalni_protok(mreza1,z,u)
minimalni $(i,p)$-rez
vrijednost minimalnog reza
mreza1.edge_cut(i,p,use_edge_labels=True)
vrijednost minimalnog reza i bridovi iz tog reza
mreza1.edge_cut(i,p,use_edge_labels=True,value_only=False)
vrijednost minimalnog reza, bridovi iz tog reza i particija vrhova
mreza1.edge_cut(i,p,use_edge_labels=True,vertices=True)
Želimo li minimalni rez istaknuti na digrafu, definiramo svoju funkciju. Lukovi iz minimalnog reza su po defaultu obojani crvenom bojom (može se njihova boja po želji promijeniti), a vrhovi iz jedne particije su obojani žutom bojom, a iz druge particije svijetlo plavom bojom.
def minimalni_rez(mreza,v1,v2,metoda="FF",raspored_vrhova=None,laj="circular",brid="red",velicina=300):
rez=mreza.edge_cut(v1,v2,use_edge_labels=True,vertices=True,algorithm=metoda)
bridovi=map(lambda e: (e[0],e[1]),rez[1])
ostali_bridovi=list(set(mreza.edges(labels=False)).difference(set(bridovi)))
if raspored_vrhova==None:
slika=mreza.plot(edge_colors={brid:bridovi,"black":ostali_bridovi},
vertex_color={"yellow":rez[2][0],"cyan":rez[2][1]},layout=laj,edge_labels=True,vertex_size=velicina)
else:
slika=mreza.plot(edge_colors={brid:bridovi,"black":ostali_bridovi},
vertex_color={"yellow":rez[2][0],"cyan":rez[2][1]},pos=raspored_vrhova,edge_labels=True,vertex_size=velicina)
return slika
def graphviz_minimalni_rez(mreza,v1,v2,ime,metoda="FF",slika=None,fontV=12,fontE=12,debljinaV=1,debljinaE=1,xy=None,
vrh0="yellow",vrh1="pink",brid0="red",brid1="black",bojaTezine="black",tezine=True,dekor=False,d={},kut={}):
"""Istice minimalni (v1,v2)-rez na transportnoj mrezi.
metoda='FF' -> rez se trazi Ford-Fulkersonovim algoritmom
metoda='LP' -> rez se trazi metodom linearnog programiranja
Slika se crta u graphviz formatu.
ime -> ime datoteke u koju ce biti spremljena slika
slika -> dimenzije nacrtane slike na izlazu
xy -> rjecnik koordinata vrhova grafa G
vrh0 -> boja vrhova iz particije vrha v1
vrh1 -> boja vrhova iz particije vrha v2
brid0 -> boja bridova koji pripadaju minimalnom rezu
brid1 -> boja bridova koji ne pripadaju minimalnom rezu
bojaTezine -> boja u kojoj ce biti ispisane tezine bridova
tezine -> da li ce tezine bridova biti ispisane ili nece
dekor -> dekorirani ili nedekorirani ispis tezina
d -> udaljenost tezine brida od njegovog kraja
kut -> kut za koji je rotirana tezina brida oko njegovog kraja"""
rez=mreza.edge_cut(v1,v2,use_edge_labels=True,vertices=True,algorithm=metoda)
bridovi=map(lambda e: (e[0],e[1]),rez[1])
bojeVrhova={}
for v in rez[2][0]:
bojeVrhova[v]=vrh0
for v in rez[2][1]:
bojeVrhova[v]=vrh1
bojeBridova={}
for e in mreza.edges(labels=False):
if e in bridovi:
bojeBridova[e]=brid0
else:
bojeBridova[e]=brid1
rijec=graf_string(mreza,slika,fontV,fontE,xy,vrh1,brid1,debljinaV,debljinaE,bojaTezine,bojeVrhova,bojeBridova,tezine,dekor,d,kut)
os.system("echo '%s' | dot -Kfdp -Tpng > %s" % (rijec,ime))
return Image(filename=ime)
minimalni_rez(mreza1,i,p,raspored_vrhova=mreza1_pos).show(figsize=(8,5))
graphviz_minimalni_rez(mreza1,i,p,"mreza1.png",metoda="FF",slika=(8,4),xy=mreza1_pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",fontV=18,fontE=18,debljinaE=2,
d={(w,p):8,(i,x):10},kut={(w,p):-9,(i,x):-7})
minimalni $(u,z)$-rez
mreza1.edge_cut(u,z,use_edge_labels=True,vertices=True)
minimalni_rez(mreza1,u,z,raspored_vrhova=mreza1_pos).show(figsize=(8,5))
graphviz_minimalni_rez(mreza1,u,z,"mreza1dva.png",metoda="FF",slika=(8,4),xy=mreza1_pos,vrh0="yellow",
vrh1="pink",brid0="red",brid1="black",fontV=18,fontE=18,debljinaE=2,
d={(w,p):8,(i,x):10},kut={(w,p):-9,(i,x):-7})
mreza2=DiGraph({i:{A:3,C:2,E:6},A:{B:4},C:{D:2},
D:{p:4},E:{F:2,H:2},F:{B:2,G:1},
G:{p:5},H:{D:4,G:1},B:{p:6}},weighted=True)
mreza2_pos={i:[0,4],A:[2,8],B:[7,8],C:[2,0],D:[7,0],E:[3,4],F:[4.5,6.5],G:[6,4],H:[4.5,1.5],p:[10,4]}
mreza2.show(pos=mreza2_pos,edge_labels=True,vertex_size=500,figsize=(6,4),ymin=-0.1)
crtaj_graphviz(mreza2,"mreza2.png",slika=(6,4),xy=mreza2_pos,bojaVrha="khaki",bojaBrida="black",bojaTezine="blue",
fontV=24,fontE=24,debljinaE=2,d={(i,C):13,(E,H):10,(F,G):9,(B,p):18},kut={(i,C):-7,(E,H):8,(F,G):-7,(B,p):-5})
vrijednost maksimalnog protoka od izvora do ponora
mreza2.flow(i,p)
količina protoka kroz pojedine lukove
maksimalni_protok(mreza2,i,p)
minimalni $(i,p)$-rez
mreza2.edge_cut(i,p,use_edge_labels=True,vertices=True)
minimalni_rez(mreza2,i,p,raspored_vrhova=mreza2_pos).show(figsize=[6,4])
graphviz_minimalni_rez(mreza2,i,p,"mreza2.png",slika=(6,4),xy=mreza2_pos,bojaTezine="blue",fontV=24,fontE=24,debljinaE=2,
d={(i,C):13,(E,H):10,(F,G):9,(B,p):18},kut={(i,C):-7,(E,H):8,(F,G):-7,(B,p):-5})